1 //===- LoopPreheaders.cpp - Loop Preheader Insertion Pass -----------------===//
3 // Insert Loop pre-headers into the CFG for each function in the module. This
4 // pass updates loop information and dominator information.
6 //===----------------------------------------------------------------------===//
8 #include "llvm/Transforms/Scalar.h"
9 #include "llvm/Analysis/Dominators.h"
10 #include "llvm/Analysis/LoopInfo.h"
11 #include "llvm/Function.h"
12 #include "llvm/iTerminators.h"
13 #include "llvm/iPHINode.h"
14 #include "llvm/Constant.h"
15 #include "llvm/Support/CFG.h"
16 #include "Support/Statistic.h"
19 Statistic<> NumInserted("preheaders", "Number of pre-header nodes inserted");
21 struct Preheaders : public FunctionPass {
22 virtual bool runOnFunction(Function &F);
24 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
25 // We need loop information to identify the loops...
26 AU.addRequired<LoopInfo>();
28 AU.addPreserved<LoopInfo>();
29 AU.addPreserved<DominatorSet>();
30 AU.addPreserved<ImmediateDominators>();
31 AU.addPreserved<DominatorTree>();
32 AU.addPreservedID(BreakCriticalEdgesID); // No crit edges added....
35 bool ProcessLoop(Loop *L);
36 void InsertPreheaderForLoop(Loop *L);
39 RegisterOpt<Preheaders> X("preheaders", "Natural loop pre-header insertion");
42 // Publically exposed interface to pass...
43 const PassInfo *LoopPreheadersID = X.getPassInfo();
44 Pass *createLoopPreheaderInsertionPass() { return new Preheaders(); }
47 /// runOnFunction - Run down all loops in the CFG (recursively, but we could do
48 /// it in any convenient order) inserting preheaders...
50 bool Preheaders::runOnFunction(Function &F) {
52 LoopInfo &LI = getAnalysis<LoopInfo>();
54 for (unsigned i = 0, e = LI.getTopLevelLoops().size(); i != e; ++i)
55 Changed |= ProcessLoop(LI.getTopLevelLoops()[i]);
61 /// ProcessLoop - Walk the loop structure in depth first order, ensuring that
62 /// all loops have preheaders.
64 bool Preheaders::ProcessLoop(Loop *L) {
67 // Does the loop already have a preheader? If so, don't modify the loop...
68 if (L->getLoopPreheader() == 0) {
69 InsertPreheaderForLoop(L);
74 const std::vector<Loop*> &SubLoops = L->getSubLoops();
75 for (unsigned i = 0, e = SubLoops.size(); i != e; ++i)
76 Changed |= ProcessLoop(SubLoops[i]);
81 /// InsertPreheaderForLoop - Once we discover that a loop doesn't have a
82 /// preheader, this method is called to insert one. This method has two phases:
83 /// preheader insertion and analysis updating.
85 void Preheaders::InsertPreheaderForLoop(Loop *L) {
86 BasicBlock *Header = L->getHeader();
88 // Compute the set of predecessors of the loop that are not in the loop.
89 std::vector<BasicBlock*> OutsideBlocks;
90 for (pred_iterator PI = pred_begin(Header), PE = pred_end(Header);
92 if (!L->contains(*PI)) // Coming in from outside the loop?
93 OutsideBlocks.push_back(*PI); // Keep track of it...
95 assert(OutsideBlocks.size() != 1 && "Loop already has a preheader!");
97 // Create new basic block, insert right before the header of the loop...
98 BasicBlock *NewBB = new BasicBlock(Header->getName()+".preheader", Header);
100 // The preheader first gets an unconditional branch to the loop header...
101 BranchInst *BI = new BranchInst(Header);
102 NewBB->getInstList().push_back(BI);
104 // For every PHI node in the loop body, insert a PHI node into NewBB where
105 // the incoming values from the out of loop edges are moved to NewBB. We
106 // have two possible cases here. If the loop is dead, we just insert dummy
107 // entries into the PHI nodes for the new edge. If the loop is not dead, we
108 // move the incoming edges in Header into new PHI nodes in NewBB.
110 if (!OutsideBlocks.empty()) { // Is the loop not obviously dead?
111 for (BasicBlock::iterator I = Header->begin();
112 PHINode *PN = dyn_cast<PHINode>(&*I); ++I) {
114 // Create the new PHI node, insert it into NewBB at the end of the block
115 PHINode *NewPHI = new PHINode(PN->getType(), PN->getName()+".ph", BI);
117 // Move all of the edges from blocks outside the loop to the new PHI
118 for (unsigned i = 0, e = OutsideBlocks.size(); i != e; ++i) {
119 Value *V = PN->removeIncomingValue(OutsideBlocks[i]);
120 NewPHI->addIncoming(V, OutsideBlocks[i]);
123 // Add an incoming value to the PHI node in the loop for the preheader
125 PN->addIncoming(NewPHI, NewBB);
128 // Now that the PHI nodes are updated, actually move the edges from
129 // OutsideBlocks to point to NewBB instead of Header.
131 for (unsigned i = 0, e = OutsideBlocks.size(); i != e; ++i) {
132 TerminatorInst *TI = OutsideBlocks[i]->getTerminator();
133 for (unsigned s = 0, e = TI->getNumSuccessors(); s != e; ++s)
134 if (TI->getSuccessor(s) == Header)
135 TI->setSuccessor(s, NewBB);
138 } else { // Otherwise the loop is dead...
139 for (BasicBlock::iterator I = Header->begin();
140 PHINode *PN = dyn_cast<PHINode>(&*I); ++I)
141 // Insert dummy values as the incoming value...
142 PN->addIncoming(Constant::getNullValue(PN->getType()), NewBB);
146 //===--------------------------------------------------------------------===//
147 // Update analysis results now that we have preformed the transformation
150 // We know that we have loop information to update... update it now.
151 if (Loop *Parent = L->getParentLoop())
152 Parent->addBasicBlockToLoop(NewBB, getAnalysis<LoopInfo>());
154 // Update dominator information if it is around...
155 if (DominatorSet *DS = getAnalysisToUpdate<DominatorSet>()) {
156 // The blocks that dominate NewBB are the blocks that dominate Header,
157 // minus Header, plus NewBB.
158 DominatorSet::DomSetType DomSet = DS->getDominators(Header);
159 DomSet.insert(NewBB); // We dominate ourself
160 DomSet.erase(Header); // Header does not dominate us...
161 DS->addBasicBlock(NewBB, DomSet);
163 // The newly created basic block dominates all nodes dominated by Header.
164 for (Function::iterator I = Header->getParent()->begin(),
165 E = Header->getParent()->end(); I != E; ++I)
166 if (DS->dominates(Header, I))
167 DS->addDominator(I, NewBB);
170 // Update immediate dominator information if we have it...
171 if (ImmediateDominators *ID = getAnalysisToUpdate<ImmediateDominators>()) {
172 // Whatever i-dominated the header node now immediately dominates NewBB
173 ID->addNewBlock(NewBB, ID->get(Header));
175 // The preheader now is the immediate dominator for the header node...
176 ID->setImmediateDominator(Header, NewBB);
179 // Update DominatorTree information if it is active.
180 if (DominatorTree *DT = getAnalysisToUpdate<DominatorTree>()) {
181 // The immediate dominator of the preheader is the immediate dominator of
184 DominatorTree::Node *HeaderNode = DT->getNode(Header);
185 DominatorTree::Node *PHNode = DT->createNewNode(NewBB,
186 HeaderNode->getIDom());
188 // Change the header node so that PNHode is the new immediate dominator
189 DT->changeImmediateDominator(HeaderNode, PHNode);