IntervalPartition and Intervals per function

Hi,

I wrote a Function pass that requires the IntervalPartition pass in
order to obtain the set of intervals for every function:

virtual void getAnalysisUsage(AnalysisUsage &AU) const {
      AU.addRequired<IntervalPartition>();
}

and get a handle to it in the runOnFunction method of my CustomPass:

bool CustomPass::runOnFunction(Function& F)
{
  IntervalPartition& iPart = getAnalysis<IntervalPartition>();
        const std::vector<Interval*>& intervals = iPart.getIntervals();
        ...
}

However when i access the intervals vector for a particular call of
runOnFunction, it seems that alll intervals computed for the earlier
functions are still in the
vector. To verify this, I added some debug in addIntervalToPartition:

void IntervalPartition::addIntervalToPartition(Interval *I)
{
  DOUT << "Interval Size: " << Intervals.size() << "\n";
...
}

I get the following debug output:

Pass Arguments: -intervals -custom -preverify -domtree -verify
Target Data Layout
  ModulePass Manager
    FunctionPass Manager
      Interval Partition Construction
      Custom Pass
      Preliminary module verification
      Dominator Tree Construction
      Module Verifier

Interval Size: 0
Interval Size: 1
Interval Size: 2
Function: lresurrect
Interval Size: 3
Interval Size: 4
Interval Size: 5
Interval Size: 6
Interval Size: 7
Function: ldndate

As seen above, the intervals computed for lresurrect are still present
in the intervals vector, when function ldndate is accessed. Is this
expected ? Or maybe I am missing something here ?

(Actually I tried to lift the IntervalPartition::destroy() function
from private to public access and call it from CustomPass's
runOnFunction, but it segfaulted. I thought i'd send ask this on the
list before digging further.)

thanks,
Prakash

Hi,

I wrote a Function pass that requires the IntervalPartition pass in
order to obtain the set of intervals for every function:

However when i access the intervals vector for a particular call of
runOnFunction, it seems that alll intervals computed for the earlier
functions are still in the
vector. To verify this, I added some debug in addIntervalToPartition:

Sounds like a bug. Interval analysis is some of the oldest code in LLVM and was never widely used (once I implemented the first dominator info, it became unneeded).

As seen above, the intervals computed for lresurrect are still present
in the intervals vector, when function ldndate is accessed. Is this
expected ? Or maybe I am missing something here ?

I wouldn't be surprised if interval analysis was totally broken. Are you interested in tracking it down and fixing the problem? Alternatively, maybe we should remove the code from LLVM.

-Chris

Hi Chris,

Thanks for the reply. I am actually interested in using the Intervals
Analysis mainly to be able to do Region based analysis. In fact, I
found that the way Intervals are defined mirror exactly the definition
of a Region in the second edition of the Dragon Book (Section 9.7 on
Region-Based Analysis), so it will be great if the Intervals related
code still lives on in LLVM :).

  I found a fix for the bug, which may not be very elegant, but works
none the less. Firstly, the destroy() method in IntervalPartition.cpp
did not clear the Intervals vector and secondly, since destroy() is
only called from the destructor the state of the intervals is
maintained across different runOnFunction() calls. So now I clear the
Intervals vector in destroy() and call destroy() to start on a clean
state before doing the processing (as was done earlier) in
runOnFunction. I am attaching the patch with this mail.

regards,
Prakash

IntervalPartition.cpp.patch (773 Bytes)

Hi Chris,

Thanks for the reply. I am actually interested in using the Intervals
Analysis mainly to be able to do Region based analysis. In fact, I
found that the way Intervals are defined mirror exactly the definition
of a Region in the second edition of the Dragon Book (Section 9.7 on
Region-Based Analysis), so it will be great if the Intervals related
code still lives on in LLVM :).

Ok :slight_smile:

I found a fix for the bug, which may not be very elegant, but works
none the less. Firstly, the destroy() method in IntervalPartition.cpp
did not clear the Intervals vector and secondly,

Applied!
http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20080825/066480.html

since destroy() is
only called from the destructor the state of the intervals is
maintained across different runOnFunction() calls. So now I clear the
Intervals vector in destroy() and call destroy() to start on a clean
state before doing the processing (as was done earlier) in
runOnFunction. I am attaching the patch with this mail.

The right fix for this is to rename destroy() to releaseMemory(). Does that work?

-Chris

Hi Chris,

Thanks for the reply. I am actually interested in using the Intervals
Analysis mainly to be able to do Region based analysis. In fact, I
found that the way Intervals are defined mirror exactly the definition
of a Region in the second edition of the Dragon Book (Section 9.7 on
Region-Based Analysis), so it will be great if the Intervals related
code still lives on in LLVM :).

Ok :slight_smile:

I found a fix for the bug, which may not be very elegant, but works
none the less. Firstly, the destroy() method in IntervalPartition.cpp
did not clear the Intervals vector and secondly,

Applied!
http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20080825/066480.html

since destroy() is
only called from the destructor the state of the intervals is
maintained across different runOnFunction() calls. So now I clear the
Intervals vector in destroy() and call destroy() to start on a clean
state before doing the processing (as was done earlier) in
runOnFunction. I am attaching the patch with this mail.

The right fix for this is to rename destroy() to releaseMemory().
Does that work?

Yeah, that works. Thanks !

- Prakash

Done, thanks:
http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20080825/066519.html

-Chris