Interval Analysis

Chris Lattner <>
4 Mar 2001 01:51:12 -0500

          From comp.compilers

Related articles
Interval Analysis (Chris Lattner) (2001-03-04)
| List of all articles for this month |

From: Chris Lattner <>
Newsgroups: comp.compilers
Date: 4 Mar 2001 01:51:12 -0500
Organization: University of Illinois at Urbana-Champaign
Keywords: analysis, question
Posted-Date: 04 Mar 2001 01:51:12 EST

Hi everyone,

I'm looking at using intervals to do some loop level analysis of
programs. From what I understand, the interval construction algorithm
works like this:

H = { entry }
while (H != {})
    h <- H; remove h from H
    I(h) = {h};
    while there is a node x with all of its predecessors in I(h)
        I(h) += {x};
    add all successors of I(h) that are not in I(h) and not in H to H

What is the complexity of this algorithm? What are the recommended ways
of implementing it? All of the papers I can find just take for granted
that you can build intervals... and searching for interval analysis turns
up lots of unrelated math topics.



Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.