The syntax tree is a tree whose nodes represent the structure of programs in the high-level language and whose leaves represent basic blocks. Leaves in the syntax tree coincide with the nodes in the control-flow graph. There are four kinds of tree nodes : leaves, ``SEQUENCE'', ``FOR'' and ``IF''. Note that the init part of ``For'' loops is omitted because such a loop can easily be transformed into a sequence containing the init part and then a loop without an init part.

View larger version of the work1 task after replication

Loop nesting

Taking loop nesting into account is of prime importance for obtaining a tight WCET estimation. The behavior of an instruction within a basic block may depend on the surrounding loop which is executed.

We define a hierarchical naming system for nested loops that reflects the position of a loop relatively to its enclosing and enclosed loops. Each loop is associated with a loop nesting level (ln-level for short). Top level loops are named [0], [1], etc. Loops enclosed in loop [0] are named [0.0], [0.1], and so on. We also define [] which is the level enclosing the whole syntax tree. For example, a loop whose ln-level is [2.3.1.0] is enclosed in loops [2.3.1], [2.3], [2], and lastly []. We add a dummy ln-level named never, upper than [].