An interval is a subgraph that basically corresponds to a program loop.

An interval I with initial node h is the maximal subgraph (I, &GammaI) of (S, &Gamma) such that:

  1. h &isin I

  2. x &isin I &rarr x &isin &Gamma*h

  3. I - {h} is cycle-free

  4. if x &isin I - {h} , then &Gamma-1x &sub I .

To construct an interval starting with node h :

  1. initially, set I := {h}

  2. repeat I := I &cup { x &isin &Gamma I | &Gamma-1 x &sube I }
    until there are no more additions.

Members of &Gamma I - I must be the heads of other intervals.

Contents    Page-10    Prev    Next    Page+10    Index