Initial Checking of Interval handling code
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@39 91177308-0d34-0410-b5e6-96231b3b80d8
diff --git a/lib/Analysis/Interval.cpp b/lib/Analysis/Interval.cpp
new file mode 100644
index 0000000..f1737fc
--- /dev/null
+++ b/lib/Analysis/Interval.cpp
@@ -0,0 +1,85 @@
+//===- Intervals.cpp - Interval partition Calculation ------------*- C++ -*--=//
+//
+// This file contains the declaration of the cfg::IntervalPartition class, which
+// calculates and represent the interval partition of a method.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Analysis/Intervals.h"
+#include "llvm/Method.h"
+#include "llvm/BasicBlock.h"
+#include "llvm/CFG.h"
+
+void cfg::IntervalPartition::UpdateSuccessors(cfg::Interval *Int) {
+ BasicBlock *Header = Int->HeaderNode;
+ for (cfg::Interval::succ_iterator I = Int->Successors.begin(),
+ E = Int->Successors.end(); I != E; ++I)
+ getBlockInterval(*I)->Predecessors.push_back(Header);
+}
+
+// IntervalPartition ctor - Build the partition for the specified method
+cfg::IntervalPartition::IntervalPartition(Method *M) {
+ BasicBlock *MethodStart = M->getBasicBlocks().front();
+ assert(MethodStart && "Cannot operate on prototypes!");
+
+ ProcessInterval(MethodStart);
+ RootInterval = getBlockInterval(MethodStart);
+
+ // Now that we know all of the successor information, propogate this to the
+ // predecessors for each block...
+ for(iterator I = begin(), E = end(); I != E; ++I)
+ UpdateSuccessors(*I);
+}
+
+void cfg::IntervalPartition::ProcessInterval(BasicBlock *Header) {
+ if (getBlockInterval(Header)) return; // Interval already constructed
+
+ Interval *Int = new Interval(Header);
+ IntervalList.push_back(Int); // Add the interval to our current set
+ IntervalMap.insert(make_pair(Header, Int));
+
+ // Check all of our successors to see if they are in the interval...
+ for (succ_iterator I = succ_begin(Header), E = succ_end(Header); I != E; ++I)
+ ProcessBasicBlock(Int, *I);
+
+ // Build all of the successor intervals of this interval now...
+ for(Interval::succ_iterator I = Int->Successors.begin(),
+ E = Int->Successors.end(); I != E; ++I)
+ ProcessInterval(*I);
+}
+
+void cfg::IntervalPartition::ProcessBasicBlock(Interval *Int, BasicBlock *BB) {
+ assert(Int && "Null interval == bad!");
+ assert(BB && "Null interval == bad!");
+
+ Interval *CurInt = getBlockInterval(BB);
+ if (CurInt == Int) { // Already in this interval...
+ return;
+ } else if (CurInt != 0) { // In another interval, add as successor
+ if (!Int->isSuccessor(BB)) // Add only if not already in set
+ Int->Successors.push_back(BB);
+ } else { // Otherwise, not in interval yet
+ for (pred_iterator I = pred_begin(BB), E = pred_end(BB); I != E; ++I) {
+ if (!Int->contains(*I)) { // If pred not in interval, we can't be
+ if (!Int->isSuccessor(BB)) // Add only if not already in set
+ Int->Successors.push_back(BB);
+ return; // See you later
+ }
+ }
+
+ // If we get here, then all of the predecessors of BB are in the interval
+ // already. In this case, we must add BB to the interval!
+ Int->Nodes.push_back(BB);
+ IntervalMap.insert(make_pair(BB, Int));
+
+ if (Int->isSuccessor(BB)) {
+ // If we were in the successor list from before... remove from succ list
+ remove(Int->Successors.begin(), Int->Successors.end(), BB);
+ }
+
+ // Now that we have discovered that BB is in the interval, perhaps some of
+ // its successors are as well?
+ for (succ_iterator I = succ_begin(BB), E = succ_end(BB); I != E; ++I)
+ ProcessBasicBlock(Int, *I);
+ }
+}