Transcription

Simple Analysis of Partial Worst-case Execution Paths onGeneral Control Flow Graphs Jan C. KleinsorgeHeiko FalkTU DortmundUlm ni-ulm.dePeter MarwedelTU [email protected] INTRODUCTIONOne of the most important computations in static worst-caseexecution time analyses is the path analysis which computesthe potentially most time-consuming execution path in aprogram. This is typically done either with an implicit pathcomputation based on solving an integer linear program, orwith explicit path computations directly on the program’scontrol flow graph. The former approach is powerful andcomparably simple to use but hard to extend and to combinewith other program analyses due to its restriction to the linearequation model. The latter approaches are often restricted towell-structured graphs, suffer from inaccuracy or require nontrivial structural analyses or graph transformations upfrontor during their computations.In this paper, we propose a generalized computationalmodel and a comprehensive explicit path analysis that operates on arbitrary directed control flow graphs. We proposesimple and yet effective techniques to deal with unstructuredcontrol flows and complex flow fact models. The analysis does not require a control flow graph to be mutable, isnon-recursive, fast, and provides the means to compute allworst-case paths from arbitrary source nodes. It is well suitedfor solving local problems and the computation of partialsolutions, which is highly relevant for problems related toscheduling and execution modes alike.The worst-case execution time (WCET) of tasks is a criticalmetric in all hard real-time systems. An upper bound on theWCET can be estimated by static analysis. Input to suchan analysis is typically a program in its binary form. Forthis, fine grained analyses can be performed as instructions,data and their locations are usually complete and staticallyknown. Worst-case estimations of the execution time ofindividual basic blocks can then be derived from possibleCPU states and the access patterns to memories and caches.Ultimately, this information is used to perform an estimationof the WCET of an entire task. The worst-case path (WCEP)problem is to find the most time-consuming path through thecontrol flow graph (CFG) from its entry to its exit. Cycles inthe control flow pose a particular problem since without anyknowledge of an upper bound on loop iterations, the worstcase path length is unbounded. The required loop bounds canbe determined analytically or need to be supplied manually.As such, it is vital that the control flow reconstruction isable to identify loops correctly and to feature simple meansto (manually) annotate the control flow with flow facts (e.g.,loop bounds, alternative or infeasible paths) where necessary.The predominant approach to WCEP analysis is the implicit path enumeration technique (IPET) [12]. The worstcase path problem is formulated as an integer linear program(ILP) which allows to easily model arbitrarily structuredcontrol flow and flow facts in one monolithic model. A disadvantage is that it only yields the WCET from the entryto the exit of a task and neither directly exposes the WCEPnor any information on subpaths. It is not ideal for modelingproblems related to scheduling, where detailed informationof timing of interior program points is required (e.g. multitask, multicore), for partial analyses in general (e.g. toprovide bounds for schedulability analysis) and for analysesthat could be interleaved with the path analysis to increasetheir accuracy, specifically.As opposed to that, explicit path analysis techniques aresignificantly more difficult to employ and no generally accepted computational model is used. These analyses dependon the availability of high-level structural information ofthe control flow since loops are typically processed one at atime. The rationale is that longest paths are easily computedon the acyclic control flows of the loop bodies. Loops arethen processed in a recursive manner starting from the mostdeeply nested ones. This is unfortunate since contextualinformation for a loop (such as path infeasibility or hardwarestates for timing analysis) is only available after it has beenfully processed. Also, in this model, flow facts are eitherCategories and Subject DescriptorsD.2.4 [Software Engineering]: Software/Program Verification—Formal methods; D.2.8 [Software Engineering]:Metrics—Performance measuresGeneral TermsReliability, Verification, PerformanceKeywordsWorst-case Execution Time, Path Analysis, Static Analysis This work was partially supported by Deutsche Forschungsgesellschaft (DFG)under grant FA 1017/1-1 and EU COST Action IC1202: Timing Analysis onCode-Level (TACLe).Permission to make digital or hard copies of all or part of this work forpersonal or classroom use is granted without fee provided that copies arenot made or distributed for profit or commercial advantage and that copiesbear this notice and the full citation on the first page. To copy otherwise, torepublish, to post on servers or to redistribute to lists, requires prior specificpermission and/or a fee.EMSOFT ’13 09/29/2013, Montreal, Canada978-1-4799-1443-2/13/ 31.00 2013 IEEE

only allowed to be simple (one iteration bound for the entireloop), or the algorithms become significantly more complex[8]. For multi-entry loops, loop nestings are ambiguous andpreprocessing steps [18] are mandatory that enumerate allpossible combinations or even require a modification of theCFG. This can cause redundancies in the computations, requires changes to already existing frameworks and potentiallyreduces the analysis accuracy, as flow facts now do not necessarily match the presumed program semantics anymore.Although rare, it is critical to be able to handle such cases inall generality. Examples are analysis of low-level code, statemachines, co-routines, cooperative scheduling, etc.In this paper, we propose a generalized computationalmodel and a comprehensive explicit worst-case execution pathanalysis for the evaluation of complex (partial) control-flows.Our concrete contributions are: The analysis can directly beperformed on arbitrarily structured and immutable controlflow graphs. The computational model is non-recursive withregard to loops, cleanly isolates problems related to graphstructure and context/path-sensitivity from the actual analysis and only exposes a simple, locally restricted join/transferpropagation model, which is easy to extend and specificallyallows for the easy interleaving with other existing analyses. By means of path-compression and the avoidance ofredundancy where possible, it scales very well. It computesworst-case paths at basic block level from arbitrary sourcepoints to all other points, as opposed to being limited toentry-to-exit paths and allows for the specification of complexflow constraints beyond simple loop bounds. In particular,the fine-grained analysis results provide a basis for improvedinterference analyses in multitask and multicore scenarios.The paper is structured as follows. In Sec. 2, we reviewrelated work. In Sec. 3, we discuss problems related to thestructure of CFGs and propose a simple solution. Sec. 4 addresses the actual path analysis by introducing the technicalfoundation and by presenting our reference implementation.We trade a thorough formal analysis in favor of a practicalevaluation in Sec. 5. In Sec. 6 the paper is concluded andfuture work is discussed.2. RELATED WORKPath analyses in the domain of WCET analysis can roughlybe separated into ones based on IPET [12] and ones based onalgorithms for the classic single-source shortest paths problem[6]. They are two approaches to solve the same problem [16].IPET is predominant in its original form even in industrialWCET analysis solutions [19], although variations based onparametric ILP [3] have been proposed. For explicit pathanalyses, however, different approaches are known [8, 2, 5].For IPET, its limited extensibility inhibits a combined analysis of paths and CPU or cache states [17], which potentiallyprofit from this additional contextual information. As opposed to that, explicit path analyses allow to directly modelproblems beyond the mere longest path problem, so that aninterleaving with other analyses becomes possible [15].Explicit path analysis techniques typically suffer from theirinherent limitation to reducible graphs (single-entry loops)[9] and therefore rely on preprocessing such as node splitting [10] or explicit enumeration of possible permutations ofloop nests [18]. The implication is that either control flowrepresentations must be modified or the analyses must betailored towards the underlying approach. Another typicallimitation is the restriction to simple loop bounds. Mostab2aa daabbbccccdd1(a)(b)dd(c)(d)Figure 1: Examples for (a) ambiguous backward edges, (b)ambiguous scope nesting, (c) virtual exit edges and (d) virtualbottoms.explicit path analyses perform their computations loop-wiseor at a similarly coarse granularity. Mandatory worst-casebounds for loop iterations can then only be specified at thisgranularity as well [2], which can lead to over-estimations.An exception is [8], which comes at the price of a complexcomputational model. Except for [4] which is based on IPET,no approach addresses the problem of partial worst-case pathanalyses to the best of the authors’ knowledge. Notably, theapproach proposed in [2] is capable of recursively computinglongest paths from a global entry node to all others but isrestricted to single-entry, single-exit loops and to a simpleflow fact model. A general overview of different path analysistechniques, in particular in the context of WCET analyses,is given in [19].3. STRUCTURING CONTROL FLOWIn the following, we address problems related to controlflow structure and loops. In particular we propose a verysimple data structure and algorithms upon which a pathanalysis can be performed efficiently and non-recursively.In Sec. 3.1, we propose a data structure that models looprelations in a control flow and serves, along with the CFG,as input to the analysis. In Sec. 3.2, we present our approachto a non-recursive traversal of loop nests.3.1Scope TreeIf a CFG is reducible (all loops have a single entry) [13],we can directly construct a so-called loop nesting forest [14]by means of depth-first search (DFS) [6] to represent therelation of loops to one another and to define the membershipof nodes to loops.Let G (V, E) be a CFG. Given G is reducible, loopnesting forest construction relies on the classification of theCFG edges E(G) into forward (F (G)) and backward (B(G) V (G) \ F (G)) edges. Loops are then uniquely characterizedby B(G) and nesting relations are unambiguous.The problem on irreducible graphs is that B(G) is ambiguous, so that classic approaches to edge classification cannotbe used directly. In Fig. 1(a), depending on whether a DFSstarting in a visits b or c first, backward edges could be either(b, c) or (c, b). Worse yet, loop relations, such as depictedFig. 1(b), can then also be ambiguous. Either loop {a, b, c} or{b, c, d} could be the nested loop, as far as program semanticsare concerned.Our approach is to avoid the problem of ambiguity altogether in the first place instead of being required to try outall possible combinations at some later time. The rationale isthat such an enumeration makes little sense in the first placesince the semantic model that was originally intended (by thedevelopers) is unambiguous. Since a good understanding ofprogram semantics is usually required to provide correct and

tight flow facts in the general case, we propose two simpleextensions to flow facts beyond mere execution bounds.First, we disambiguate the DFS by allowing flow facts toguide the algorithm in ambiguous cases. Such a prenumberingabstracts from the actual order in which nodes will be visited.In Fig. 1(a), only nodes b and c need to be prenumbered(grayed labels) such that the visitation order of a modifiedDFS corresponds to the numeric relation of the two numbers(b before c). For single-entry loops, these annotations areoptional and therefore only required in rare cases.Second, complex nesting relations as in Fig. 1(b) are unambiguously resolved by allowing explicit nesting relationsas flow facts. In the figure, node a is supposed to belongto a loop that is nested in the one of node d (grayed label).Also here, this is optional and rather rare but is sufficient tomodel arbitrarily complex control flows.For our analysis, a minimal data structure (similar to aloop nest forest) to maintain the structural information mustbe constructed. A scope denotes an arbitrary cyclic region inG. A scope tree S (V, E) is a directed graph, where eachnode s V (S) represents a scope and each edge (s, t) E(S)denotes that scope t encloses scope s. A scope label definedby scope : V (G) 7 V (S) uniquely identifies the membershipof a control flow node to a node of the scope tree. If a controlflow node logically belongs to multiple scopes, its label isthat of the innermost scope.Per scope, we explicitly maintain four sets of nodes. Giventhat a scope s can now be unambiguously characterized byits backward edges Bs B(G), the (singleton) set top isdefined as top(s) {v (u, v) Bs }. Analogously, we definebottom(s) {u (u, v) Bs }. (V (G), F (G)) denote the directed acyclic graphLet G(DAG) of G. Let T denote the function that maps to the transitive closure of any directed graph. If (u, v) E(T (G)),then node v can be reached from u.Given the edge (u, v) F (G), the labels ū scope(u),v̄ scope(v) with ū 6 v̄. Then the set of entries are thenodes that can be reached from enclosing or neighboring/ E(T (S)).scopes: entry(v̄) {v (v̄, ū) E(T (S)) (ū, v̄) Analogously, the set of exits are the nodes that either reachan enclosing or neighboring scope: exit(ū) {u (ū, v̄) E(T (S)) (v̄, ū) / E(T (S)).Fig. 2(a) shows a CFG of three scopes (outermost regionand the two loops) that are explicitly depicted in Fig. 2(b)and labeled 0̄, 1̄ and 2̄, respectively. The corresponding scopetree is depicted in Fig. 2(c) along with the node sets.Since we want to focus on the path analysis itself, we haveto leave the algorithmic details for the prenumbering DFSand the scope tree construction aside.3.2Scope OrderFor worst-case path computations, explicit path analysistechniques typically recursively descent into a loop nestingrepresentation similar to our scope tree and compute longestpaths one loop at a time starting from the innermost ones.Since the loop bodies – given nested loops have been successively replaced by (appropriately weighted) representativenodes – are acyclic, longest paths can be computed easily.The global worst-case path is then a comparatively unstructured concatenation of independent subpaths.Although this approach seems quite generally applicable,it has several drawbacks. For multi-entry or multi-exit loops,it is not straightforward to replace a nested loop by somea0̄ab1̄ec b2̄e dff(a) Control flow graph(b) Scope representationctop(1̄) {a}entry(1̄) {a}bottom(1̄) {f }exit(1̄) {f }d0̄1̄2̄top(2̄) {b}entry(2̄) {b, c}bottom(2̄) {e}exit(2̄) {d, e} (IKO)(c) Scope tree and sets(IKO)(IKO)(IKO) 0̄. . . 1̄. . .2̄(d) Unroll modelFigure 2: Concepts of the computational modelrepresentative. Even if measures have been taken earlierto be able to deal with multiple loop entries (cf. Sec. 2),multiple exits are still a problem1 . Depending on the flowfact model, a loss of accuracy has to be accepted [2] orthe control-flow representation becomes significantly morecomplex in addition to previous changes to the original CFG[10, 8]. Moreover, recursion implies that computations onnested loops are context-insensitive. Detection of unnecessarycomputations and early elimination of invalid data is notpossible. For example, only once enclosing loops have beenprocessed, path infeasibility of paths in subloops can bedetected. This can also lead to much redundancy, whichmight not be an apparent problem for just the path analysisby itself. But once it is interleaved with other expensivestatic analyses [19], this can be significant.We propose a simple non-recursive solution. In Fig. 2(a),if we remove the backward edges ((f, a), (e, b)), a possibletopological order of the nodes is (a, b, c, d, e, f ). Replacingnode labels by scope labels yields (1̄, 2̄, 2̄, 2̄, 2̄, 1̄), or, withoutduplicates, (1̄, 2̄, 1̄). This corresponds to the recursive traversal of the scope tree (from 1̄) in Fig. 2(c) and guarantees(here) that all nodes of scope 2̄ have been visited before allnodes of scope 1̄. Specifically, a scope is considered fullyprocessed once all of its bottom nodes (cf. Sec. 3.1) havebeen visited since then all paths are known. Computationsin 2̄ can therefore be context-sensitive and the worst-casepath is composed in the “general direction” of control-flow in not just for single loops.G,In general, loops are not nested such that any arbitrarytopological order yields the property that all nodes of nestedloops have been visited before all nodes of enclosing loops.The rationale is that once all nodes of a scope are known, a(virtual) unrolling can be performed according to the givenflow fact model.The problem is twofold. In Fig. 1(c) (ignoring the dottededge), node d could be visited before node c, which meansthe loop is not fully known once a node of the enclosing loopmight already be dependent on that information.Additionally, even if the topological order is unambiguous,for a graph layout such as depicted in Fig. 1(d), all nodesof a scope could have been visited before any nodes of its1Multiple exits are far more common than multiple entries:e.g. error/exception handling

subscopes. Loops {b, c} and {c, d} are nested in {a, b}.First, let b (s) denote the set of bottoms of scope s andall of its subscopes. We call the set of “bottom-most” nodesof b (s) the set of virtual bottoms and define it as: vbottom(s) {u u b (s), v b (s) : (u, v) / E(T (G))}In Fig. 1(d), the sets of virtual bottoms for all scopes areequal to {d}. All three scopes are fully known only oncenode d is visited.Second, all scope bottoms must have been visited beforeany of the adjacent nodes of the exit nodes (cf. Fig. 1(c)). For the scope order denotes a sequence of nodes (u1 , . . . , un )G, such that for a scope s, a node uj exit(s)with ui V (G)and a node uk vbottom(s) exists with s scope(uj ) scope(uk ): ul successors(uj ) : l k.We can easily achieve the desired result by adding additional virtual exit edges from the (v)bottoms to the exitsuccessors, as indicated by the dotted edge (c, d) in Fig. 1(c).A simple extension to an algorithm for topological sorting[6] suffices to achieve this without modifying the graph itselfand at minimal costs.Scope order simplifies the computation worst-case pathssuch that we can reason about worst-case paths in one control flow node by merely referencing its predecessors in G.4. PATH ANALYSISThe objective of our path analysis is to compute the latestexecution time (LET) for all nodes in the CFG. In the following Sec. 4.1, the overall computational model is presented.We briefly address our flow fact model in Sec. 4.2. Sec. 4.3describes the algorithm itself.4.1Model of ComputationThe basic principle of the LET computation is a virtualunrolling of all scopes. In such a – now – cycle-free controlflow graph, the LET of the exit node of the control flow graphwould be equal to the longest path from the root scope’s topto its bottom.To unroll a scope, we distinguish three phases for eachscope: An entry phase I, a kernel phase K and an exit phaseO. In the I phase, all paths from all entries to the bottomscan be taken. In the K phase, only paths from top to bottomcan be taken. In the O phase, only paths from the top tothe exits can be taken. A longest path through an unrolledscope is a concatenation of a single path of the I phase, asmany paths of the K phase as possible according to someupper bound, and a single path of the O phase.For each path of each phase of a parent scope, all subscopeshave to be unrolled as well. Consider Fig. 2(d) which sketchesthe space of unroll phases for Fig. 2(b). For example, inscope 1̄, the three phases IKO have to be computed. Foreach such phase, three phases in scope 2̄ have to be computedas well, because for each path in 1̄, we also traverse 2̄. Thisis denoted by the edges in Fig. 2(d). All phase triples of onelevel in the figure refer to the same scope. But not all pathsin the same phase of the same scope are feasible at all times.This depends on the current phases of the parent scopes.For example, if scope 1̄ is in phase K, then the edges toand from scope 0̄ via the nodes c and d cannot have beentaken, since only the paths from the top of 1̄ to its bottomsare possible. The observation is that phases of the samescope but under a different context potentially yield differentresults and thus must potentially be distinguished.However, there usually exists a high degree of redundancythat we can exploit. For example, all K phases of scope 2̄will yield identical paths regardless of its context, since theonly paths that are feasible during this phase are the onesfrom the top to the bottoms. Also, the paths of the O phasesare subpaths of the ones of the K phase. Depending on theentries and the context, I paths could also be redundant.Reducible graphs are the special case where all phases ofall scopes under all contexts have identical feasible paths.We propose a virtual unrolling scheme that yields the leastpossible amount of redundancy and the ability to easily scaleup to the most general case.4.2User AnnotationsBesides the annotations for structural disambiguation (cf.Fig. 1(a), Fig. 1(b)) which are only needed in irreducibleCFGs, we support a single numeric constant per node thatbounds the maximal number of occurrences of this nodeon the unrolled path of a single scope. Fig. 3(a) gives anexample of a scope with node a bounded by 1, node b by 2and d by 0. This enables an accurate modeling of controlflows since for multi-entry and multi-exit scopes in particular,bounds at loop-granularity (unroll factor) are insufficientlyaccurate. In addition, this allows for the specification ofmultiple, mutually exclusive longest paths in a scope andcan easily be extended to deal with (global) infeasibilityconstraints. Since, for brevity, the paper focuses on the basealgorithm only, we will not discuss global constraints in thefollowing.4.3LET ComputationThe algorithm is presented in two stages. In Sec. 4.3.1, thebasic data structures, their construction, their relation toeach other and the main pass of the algorithm are presented,which is sufficient to compute the LET of the exit. Withthe algorithm in Sec. 4.3.2, the LET of all interior nodes arecomputed.4.3.1 Single Path LETThe path analysis solely depends on three input entities: scope tree S and flow bounds.DAG G,A node u is called a flow anchor if it has explicitly beenannotated with a bound. The set of flow bounds is definedas B {. . . , (u, c)i B , . . . } where u V (G) is the anchorand c No is its numeric value. We call the index set B theflow bound index.Fig. 3(a) illustrates a scope with annotated flow bounds.Consequently, the set of flow bounds is B {(a, 1)0 , (b, 2)1 }.The subscripted numerals denote the flow bound indices.Also, each basic block represented by a control flow nodehas a specific WCET that is denoted by cost : V (G) 7 N0 .For the sake of simplicity, in the following, we use the tuplenotation (a, ), where the underscore means “don’t care” ifan element is not relevant in the given context.Simple Paths.In a scope s, a simple path is defined as a path ph,j (uh , . . . , uj ) such that its head uh entry(s) Pand scope(uj ) s for any node uj . We define length(ph,j ) h i j cost(ui ).The trace of only the anchors A along such a path is: A(ph,j 1 ).(uj ) if (uj , ) B h jA(ph,j 1 )if (uj , ) / B h jA(ph,j ) ()otherwise

b0 7 1 af0f2b1 7 2 bf1cd 0e(a) Bounded scopef0 7 b0 , f1 7 b1 , f2 7 b1(b) Respective flow treesuabcdeB (a, 1)0(a, 1)0 , (b, 2)1(a, 1)0 , (b, 2)1(a, 1)0 , (b, 2)1(a, 1)0 , (b, 2)1V (F (a)) (b0 , 1)0(b0 , 1)0 , (b1 , 2)1(b0 , 1)0 , (b1 , 2)1(b0 , 1)0 , (b1 , 2)1(b0 , 1)0 , (b1 , 2)1V (F (b)) (b1 , 1)2(b1 , 1)2(b1 , 1)2(b1 , 1)2P (u) (a, f0 , 1)(a, f1 , 2), (b, f2 , 1)(a, f1 , 3), (b, f2 , 2) (a, f1 , 4), (b, f2 , 3)(c) Build-up of flow bounds, flow trees and path statesFigure 3: Interleaved construction of data structuresIn Fig. 3(a), where a and e represent the top and the bottomof the scope, the complete set of traces for all paths pa,e is{(a, b), (a, d), (a, b, d)} and for all paths pb,e it is {(b), (b, d)}.A flow tree F (u) (V, E), where u is an entry node intoa scope, is a compressed representation (a trie [11]) of eachsuch a set of traces with common prefixes. Its set of nodesis defined as V (F (u)) {. . . , (b, l)i F (u) , . . . } where b Brefers to the corresponding flow bound and l length(ph,j )to the length of a simple path to the bound’s anchor uj . Theindex set of V (F (u)) is F (u). We refer to a path in such aflow tree as flow trace.Fig. 3(b) shows the corresponding flow trees for the sets oftraces. The nodes are labeled with the corresponding nodeindices, the mapping from flow tree nodes to flow boundsis shown beneath. Note that since the flow bound of CFGnode d is zero-valued all paths through it are infeasible andwe can ignore the traces that include this node (indicated bythe dashed nodes). Note that the size of the flow trees is afunction of the number of annotations not of the number ofCFG nodes. Fig. 3(a) in turn depicts the mapping from flowbounds to their numeric values.Finally, a path state represents the length of a simple pathto a CFG node uj within a scope. The set of path states isdefined as P (uj ) {. . . , (uh , f, l), . . . } where uh V (G) isthe head node of a path ph,j (which is necessarily an entry),the index f F (uh ) refers to a node of a flow tree andl length(ph,j ) is the length of that path.The following relation of data structures holds: Let uibe the most recent anchor on a path from uh to uj . If apath state (uh , f, l) P (uj ) exists, it references a uniqueflow tree node (b, )f V (F (uh )) which in turn references aflow bound (ui , )b B. In short, a path state summarizes asimple path from an entry to any node in the same scope,while it references a path in the flow tree that summarizesits history of visited flow bounds.Two path states are called comparable iff their heads andflow tree nodes match. To compute the set of path states P (u) in a node u is by propagation from preceding nodes in G.Let Ppred (u) v pred(u) P (v) be the union of all predecessorstates. Then P (u) is the minimal set of predecessor pathstates that consist only of the incomparable path states ofmaximal length, adjusted by the costs of u:P (u) {(uh , f, li cost(u)) (uh , f, lj ) Ppred (u) : li lj }The general idea of this is to solve the k-shortest pathsproblem [7] by precomputing the minimal set of paths thatare not comparable due to their unique flow traces. Thisprevents us from unnecessarily enumerating all paths later.We compute flow bounds, flow trees and path states concurrently while traversing the control flow nodes in scopeorder. Fig. 3(c) illustrates how this is performed in general,assuming that every node has a cost of 1.We start with an empty set of flow bounds, an empty forestof flow trees for either entry a (F (a)) and b (F (b)) and anempty set of path states (P (u)) and traverse the CFG nodesin Fig. 3(a) in scope order. Upon visiting a, an initial flowbound b0 is initialized with an anchor value of a and a boundvalue of 1, according to the annotation in a. Concurrently,the flow tree F (a) is initialized with a node f0 , referencingthe flow bound b0 and a distance value to this anchor of 1.Also an initial path state is emitted, which represents allpaths starting in a, belonging to flow tree node f0 and thesame distance value as it’s corresponding flow tree node.Upon visiting b, a new flow bound b1 and a new flow treeF (b) are emitted. Flow tree F (a) is extended by a new nodef1 , which is now referenced by the path state for the entry a.A new path state is emitted that represents all paths fromthe entry b and which references F (b).Since node c is neither annotated nor an entry, merely thedistance values of the path states are updated. Since node dis bounded by 0, the sets of flow bounds and flow tree nodesremain the same and we clear the set of path statesFinally, in e, the path states are joined by keeping theincomparable ones of maximal distance.The result in e is a minimal set that represents simple pathsthrough the scope and a path-compressed representation ofthe possible paths through the anchors. These paths aremutually dependent in that they refer to the very sameflow bounds. This effectively leaves us with a network flowproblem [6] that is constrained by the flow fact model.Unrolling.An unroll path of a scope is a concatenation of simplepaths such that its first node u is the entry of the scope, itslast node v is any node of the scope and no anchor occursmore often than its flow bound specifies. An unroll path(u, . . . , v) is maximal if no other unroll path of greater lengthexists.Recall from Sec. 4.1 that we conceptually distinguish threeunroll phases I, K and O. For an unroll path to exist, theflow bounds must allow for at least one feasible simple pathfrom an entry u to a bottom b (I path) and at least onefeasible simple path from a top t to an exit v (O path) or,if no such two paths exist, at least a single feasible simplepath from u to v. We refer to the length of a maximal unrollpath from an entry to an exit as the maximal scope weight.As an example,

TU Dortmund [email protected] Heiko Falk Ulm University [email protected] Peter Marwedel TU Dortmund [email protected] ABSTRACT One of the most important computations in static worst-case execution time analyses is the path analysis which computes the pot