1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
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);
}
}
|
