LoopSimplify.cpp revision c27e056d4fd7f6ecdd8e40eb92230be380c5c8c9
15976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org//===- LoopSimplify.cpp - Loop Canonicalization Pass ----------------------===// 25976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org// 35976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org// The LLVM Compiler Infrastructure 45976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org// 55976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org// This file was developed by the LLVM research group and is distributed under 65976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org// the University of Illinois Open Source License. See LICENSE.TXT for details. 75976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org// 85976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org//===----------------------------------------------------------------------===// 95976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org// 105976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org// This pass performs several transformations to transform natural loops into a 115976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org// simpler form, which makes subsequent analyses and transformations simpler and 125976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org// more effective. 135976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org// 145976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org// Loop pre-header insertion guarantees that there is a single, non-critical 155976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org// entry edge from outside of the loop to the loop header. This simplifies a 165976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org// number of analyses and transformations, such as LICM. 175976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org// 185976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org// Loop exit-block insertion guarantees that all exit blocks from the loop 195976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org// (blocks which are outside of the loop that have predecessors inside of the 205976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org// loop) only have predecessors from inside of the loop (and are thus dominated 215976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org// by the loop header). This simplifies transformations such as store-sinking 225976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org// that are built into LICM. 235976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org// 245976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org// This pass also guarantees that loops will have exactly one backedge. 255976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org// 265976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org// Note that the simplifycfg pass will clean up blocks which are split out but 275976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org// end up being unnecessary, so usage of this pass should not pessimize 285976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org// generated code. 295976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org// 305976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org// This pass obviously modifies the CFG, but updates loop information and 315976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org// dominator information. 325976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org// 335976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org//===----------------------------------------------------------------------===// 345976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org 355976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org#include "llvm/Transforms/Scalar.h" 365976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org#include "llvm/Constant.h" 375976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org#include "llvm/Instructions.h" 385976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org#include "llvm/Function.h" 395976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org#include "llvm/Type.h" 405976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org#include "llvm/Analysis/AliasAnalysis.h" 415976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org#include "llvm/Analysis/Dominators.h" 425976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org#include "llvm/Analysis/LoopInfo.h" 435976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org#include "llvm/Support/CFG.h" 445976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org#include "llvm/ADT/SetOperations.h" 455976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org#include "llvm/ADT/SetVector.h" 46582fe818e571fa2571267f5e369715188472f352wu@webrtc.org#include "llvm/ADT/Statistic.h" 475976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org#include "llvm/ADT/DepthFirstIterator.h" 485976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.orgusing namespace llvm; 495976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org 505976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.orgnamespace { 515976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org Statistic<> 525976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org NumInserted("loopsimplify", "Number of pre-header or exit blocks inserted"); 535976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org Statistic<> 545976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org NumNested("loopsimplify", "Number of nested loops split out"); 555976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org 565976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org struct LoopSimplify : public FunctionPass { 575976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org // AA - If we have an alias analysis object to update, this is it, otherwise 585976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org // this is null. 595976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org AliasAnalysis *AA; 605976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org LoopInfo *LI; 615976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org 625976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org virtual bool runOnFunction(Function &F); 635976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org 645976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org virtual void getAnalysisUsage(AnalysisUsage &AU) const { 655976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org // We need loop information to identify the loops... 665976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org AU.addRequired<LoopInfo>(); 675976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org AU.addRequired<DominatorSet>(); 685976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org AU.addRequired<DominatorTree>(); 695976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org 705976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org AU.addPreserved<LoopInfo>(); 715976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org AU.addPreserved<DominatorSet>(); 725976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org AU.addPreserved<ImmediateDominators>(); 735976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org AU.addPreserved<ETForest>(); 745976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org AU.addPreserved<DominatorTree>(); 755976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org AU.addPreserved<DominanceFrontier>(); 765976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org AU.addPreservedID(BreakCriticalEdgesID); // No critical edges added. 775976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org } 785976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org private: 795976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org bool ProcessLoop(Loop *L); 805976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org BasicBlock *SplitBlockPredecessors(BasicBlock *BB, const char *Suffix, 815976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org const std::vector<BasicBlock*> &Preds); 825976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org BasicBlock *RewriteLoopExitBlock(Loop *L, BasicBlock *Exit); 835976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org void InsertPreheaderForLoop(Loop *L); 845976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org Loop *SeparateNestedLoop(Loop *L); 855976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org void InsertUniqueBackedgeBlock(Loop *L); 865976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org 875976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org void UpdateDomInfoForRevectoredPreds(BasicBlock *NewBB, 885976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org std::vector<BasicBlock*> &PredBlocks); 895976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org }; 905976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org 915976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org RegisterOpt<LoopSimplify> 925976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org X("loopsimplify", "Canonicalize natural loops", true); 935976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org} 945976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org 955976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org// Publically exposed interface to pass... 965976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.orgconst PassInfo *llvm::LoopSimplifyID = X.getPassInfo(); 975976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.orgFunctionPass *llvm::createLoopSimplifyPass() { return new LoopSimplify(); } 985976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org 995976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org/// runOnFunction - Run down all loops in the CFG (recursively, but we could do 1005976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org/// it in any convenient order) inserting preheaders... 1015976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org/// 1025976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.orgbool LoopSimplify::runOnFunction(Function &F) { 1035976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org bool Changed = false; 1045976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org LI = &getAnalysis<LoopInfo>(); 1055976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org AA = getAnalysisToUpdate<AliasAnalysis>(); 1065976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org 1075976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org for (LoopInfo::iterator I = LI->begin(), E = LI->end(); I != E; ++I) 1085976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org Changed |= ProcessLoop(*I); 1095976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org 1105976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org return Changed; 1115976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org} 1125976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org 1135976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org/// ProcessLoop - Walk the loop structure in depth first order, ensuring that 1145976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org/// all loops have preheaders. 1155976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org/// 1165976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.orgbool LoopSimplify::ProcessLoop(Loop *L) { 1175976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org bool Changed = false; 1185976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org 1195976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org // Check to see that no blocks (other than the header) in the loop have 1205976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org // predecessors that are not in the loop. This is not valid for natural 1215976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org // loops, but can occur if the blocks are unreachable. Since they are 1225976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org // unreachable we can just shamelessly destroy their terminators to make them 1235976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org // not branch into the loop! 1245976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org assert(L->getBlocks()[0] == L->getHeader() && 1255976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org "Header isn't first block in loop?"); 1265976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org for (unsigned i = 1, e = L->getBlocks().size(); i != e; ++i) { 1275976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org BasicBlock *LoopBB = L->getBlocks()[i]; 1285976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org Retry: 1295976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org for (pred_iterator PI = pred_begin(LoopBB), E = pred_end(LoopBB); 1305976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org PI != E; ++PI) 1315976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org if (!L->contains(*PI)) { 1325976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org // This predecessor is not in the loop. Kill its terminator! 1335976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org BasicBlock *DeadBlock = *PI; 1345976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org for (succ_iterator SI = succ_begin(DeadBlock), E = succ_end(DeadBlock); 1355976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org SI != E; ++SI) 1365976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org (*SI)->removePredecessor(DeadBlock); // Remove PHI node entries 1375976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org 1385976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org // Delete the dead terminator. 1395976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org if (AA) AA->deleteValue(&DeadBlock->back()); 1405976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org DeadBlock->getInstList().pop_back(); 1415976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org 1425976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org Value *RetVal = 0; 1435976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org if (LoopBB->getParent()->getReturnType() != Type::VoidTy) 1445976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org RetVal = Constant::getNullValue(LoopBB->getParent()->getReturnType()); 1455976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org new ReturnInst(RetVal, DeadBlock); 1465976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org goto Retry; // We just invalidated the pred_iterator. Retry. 1475976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org } 1485976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org } 1495976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org 1505976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org // Does the loop already have a preheader? If so, don't modify the loop... 1515976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org if (L->getLoopPreheader() == 0) { 1525976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org InsertPreheaderForLoop(L); 1535976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org NumInserted++; 1545976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org Changed = true; 1555976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org } 1565976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org 1575976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org // Next, check to make sure that all exit nodes of the loop only have 1585976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org // predecessors that are inside of the loop. This check guarantees that the 1595976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org // loop preheader/header will dominate the exit blocks. If the exit block has 1605976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org // predecessors from outside of the loop, split the edge now. 1615976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org std::vector<BasicBlock*> ExitBlocks; 1625976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org L->getExitBlocks(ExitBlocks); 1635976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org 1645976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org SetVector<BasicBlock*> ExitBlockSet(ExitBlocks.begin(), ExitBlocks.end()); 1655976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org for (SetVector<BasicBlock*>::iterator I = ExitBlockSet.begin(), 1665976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org E = ExitBlockSet.end(); I != E; ++I) { 1675976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org BasicBlock *ExitBlock = *I; 1685976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org for (pred_iterator PI = pred_begin(ExitBlock), PE = pred_end(ExitBlock); 1695976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org PI != PE; ++PI) 1705976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org // Must be exactly this loop: no subloops, parent loops, or non-loop preds 1715976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org // allowed. 1725976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org if (!L->contains(*PI)) { 1735976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org RewriteLoopExitBlock(L, ExitBlock); 1745976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org NumInserted++; 1755976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org Changed = true; 1765976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org break; 1775976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org } 1785976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org } 1795976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org 1805976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org // If the header has more than two predecessors at this point (from the 1815976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org // preheader and from multiple backedges), we must adjust the loop. 1825976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org if (L->getNumBackEdges() != 1) { 1835976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org 1845976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org // If this is really a nested loop, rip it out into a child loop. 1855976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org if (Loop *NL = SeparateNestedLoop(L)) { 1865976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org ++NumNested; 1875976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org // This is a big restructuring change, reprocess the whole loop. 1885976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org ProcessLoop(NL); 1895976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org return true; 1905976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org } 1915976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org 1925976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org InsertUniqueBackedgeBlock(L); 1935976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org NumInserted++; 1945976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org Changed = true; 1955976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org } 1965976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org 1975976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org // Scan over the PHI nodes in the loop header. Since they now have only two 1985976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org // incoming values (the loop is canonicalized), we may have simplified the PHI 1995976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org // down to 'X = phi [X, Y]', which should be replaced with 'Y'. 2005976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org PHINode *PN; 2015976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org for (BasicBlock::iterator I = L->getHeader()->begin(); 2025976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org (PN = dyn_cast<PHINode>(I++)); ) 2035976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org if (Value *V = PN->hasConstantValue()) { 2045976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org PN->replaceAllUsesWith(V); 2055976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org PN->eraseFromParent(); 2065976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org } 2075976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org 2085976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org for (Loop::iterator I = L->begin(), E = L->end(); I != E; ++I) 2095976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org Changed |= ProcessLoop(*I); 2105976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org 2115976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org return Changed; 2125976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org} 2135976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org 2145976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org/// SplitBlockPredecessors - Split the specified block into two blocks. We want 2155976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org/// to move the predecessors specified in the Preds list to point to the new 2165976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org/// block, leaving the remaining predecessors pointing to BB. This method 2175976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org/// updates the SSA PHINode's, but no other analyses. 2185976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org/// 2195976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.orgBasicBlock *LoopSimplify::SplitBlockPredecessors(BasicBlock *BB, 2205976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org const char *Suffix, 2215976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org const std::vector<BasicBlock*> &Preds) { 2225976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org 2235976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org // Create new basic block, insert right before the original block... 2245976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org BasicBlock *NewBB = new BasicBlock(BB->getName()+Suffix, BB->getParent(), BB); 2255976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org 2265976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org // The preheader first gets an unconditional branch to the loop header... 2275976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org BranchInst *BI = new BranchInst(BB, NewBB); 2285976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org 2295976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org // For every PHI node in the block, insert a PHI node into NewBB where the 2305976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org // incoming values from the out of loop edges are moved to NewBB. We have two 2315976650443d68ccfadf1dea24999ee459dd2819mflodman@webrtc.org // possible cases here. If the loop is dead, we just insert dummy entries 232 // into the PHI nodes for the new edge. If the loop is not dead, we move the 233 // incoming edges in BB into new PHI nodes in NewBB. 234 // 235 if (!Preds.empty()) { // Is the loop not obviously dead? 236 // Check to see if the values being merged into the new block need PHI 237 // nodes. If so, insert them. 238 for (BasicBlock::iterator I = BB->begin(); isa<PHINode>(I); ) { 239 PHINode *PN = cast<PHINode>(I); 240 ++I; 241 242 // Check to see if all of the values coming in are the same. If so, we 243 // don't need to create a new PHI node. 244 Value *InVal = PN->getIncomingValueForBlock(Preds[0]); 245 for (unsigned i = 1, e = Preds.size(); i != e; ++i) 246 if (InVal != PN->getIncomingValueForBlock(Preds[i])) { 247 InVal = 0; 248 break; 249 } 250 251 // If the values coming into the block are not the same, we need a PHI. 252 if (InVal == 0) { 253 // Create the new PHI node, insert it into NewBB at the end of the block 254 PHINode *NewPHI = new PHINode(PN->getType(), PN->getName()+".ph", BI); 255 if (AA) AA->copyValue(PN, NewPHI); 256 257 // Move all of the edges from blocks outside the loop to the new PHI 258 for (unsigned i = 0, e = Preds.size(); i != e; ++i) { 259 Value *V = PN->removeIncomingValue(Preds[i], false); 260 NewPHI->addIncoming(V, Preds[i]); 261 } 262 InVal = NewPHI; 263 } else { 264 // Remove all of the edges coming into the PHI nodes from outside of the 265 // block. 266 for (unsigned i = 0, e = Preds.size(); i != e; ++i) 267 PN->removeIncomingValue(Preds[i], false); 268 } 269 270 // Add an incoming value to the PHI node in the loop for the preheader 271 // edge. 272 PN->addIncoming(InVal, NewBB); 273 274 // Can we eliminate this phi node now? 275 if (Value *V = PN->hasConstantValue(true)) { 276 if (!isa<Instruction>(V) || 277 getAnalysis<DominatorSet>().dominates(cast<Instruction>(V), PN)) { 278 PN->replaceAllUsesWith(V); 279 if (AA) AA->deleteValue(PN); 280 BB->getInstList().erase(PN); 281 } 282 } 283 } 284 285 // Now that the PHI nodes are updated, actually move the edges from 286 // Preds to point to NewBB instead of BB. 287 // 288 for (unsigned i = 0, e = Preds.size(); i != e; ++i) { 289 TerminatorInst *TI = Preds[i]->getTerminator(); 290 for (unsigned s = 0, e = TI->getNumSuccessors(); s != e; ++s) 291 if (TI->getSuccessor(s) == BB) 292 TI->setSuccessor(s, NewBB); 293 } 294 295 } else { // Otherwise the loop is dead... 296 for (BasicBlock::iterator I = BB->begin(); isa<PHINode>(I); ++I) { 297 PHINode *PN = cast<PHINode>(I); 298 // Insert dummy values as the incoming value... 299 PN->addIncoming(Constant::getNullValue(PN->getType()), NewBB); 300 } 301 } 302 return NewBB; 303} 304 305/// InsertPreheaderForLoop - Once we discover that a loop doesn't have a 306/// preheader, this method is called to insert one. This method has two phases: 307/// preheader insertion and analysis updating. 308/// 309void LoopSimplify::InsertPreheaderForLoop(Loop *L) { 310 BasicBlock *Header = L->getHeader(); 311 312 // Compute the set of predecessors of the loop that are not in the loop. 313 std::vector<BasicBlock*> OutsideBlocks; 314 for (pred_iterator PI = pred_begin(Header), PE = pred_end(Header); 315 PI != PE; ++PI) 316 if (!L->contains(*PI)) // Coming in from outside the loop? 317 OutsideBlocks.push_back(*PI); // Keep track of it... 318 319 // Split out the loop pre-header 320 BasicBlock *NewBB = 321 SplitBlockPredecessors(Header, ".preheader", OutsideBlocks); 322 323 //===--------------------------------------------------------------------===// 324 // Update analysis results now that we have performed the transformation 325 // 326 327 // We know that we have loop information to update... update it now. 328 if (Loop *Parent = L->getParentLoop()) 329 Parent->addBasicBlockToLoop(NewBB, *LI); 330 331 DominatorSet &DS = getAnalysis<DominatorSet>(); // Update dominator info 332 DominatorTree &DT = getAnalysis<DominatorTree>(); 333 334 335 // Update the dominator tree information. 336 // The immediate dominator of the preheader is the immediate dominator of 337 // the old header. 338 DominatorTree::Node *PHDomTreeNode = 339 DT.createNewNode(NewBB, DT.getNode(Header)->getIDom()); 340 BasicBlock *oldHeaderIDom = DT.getNode(Header)->getIDom()->getBlock(); 341 342 // Change the header node so that PNHode is the new immediate dominator 343 DT.changeImmediateDominator(DT.getNode(Header), PHDomTreeNode); 344 345 { 346 // The blocks that dominate NewBB are the blocks that dominate Header, 347 // minus Header, plus NewBB. 348 DominatorSet::DomSetType DomSet = DS.getDominators(Header); 349 DomSet.erase(Header); // Header does not dominate us... 350 DS.addBasicBlock(NewBB, DomSet); 351 352 // The newly created basic block dominates all nodes dominated by Header. 353 for (df_iterator<DominatorTree::Node*> DFI = df_begin(PHDomTreeNode), 354 E = df_end(PHDomTreeNode); DFI != E; ++DFI) 355 DS.addDominator((*DFI)->getBlock(), NewBB); 356 } 357 358 // Update immediate dominator information if we have it... 359 if (ImmediateDominators *ID = getAnalysisToUpdate<ImmediateDominators>()) { 360 // Whatever i-dominated the header node now immediately dominates NewBB 361 ID->addNewBlock(NewBB, ID->get(Header)); 362 363 // The preheader now is the immediate dominator for the header node... 364 ID->setImmediateDominator(Header, NewBB); 365 } 366 367 // Update ET Forest information if we have it... 368 if (ETForest *EF = getAnalysisToUpdate<ETForest>()) { 369 // Whatever i-dominated the header node now immediately dominates NewBB 370 EF->addNewBlock(NewBB, oldHeaderIDom); 371 372 // The preheader now is the immediate dominator for the header node... 373 EF->setImmediateDominator(Header, NewBB); 374 } 375 376 // Update dominance frontier information... 377 if (DominanceFrontier *DF = getAnalysisToUpdate<DominanceFrontier>()) { 378 // The DF(NewBB) is just (DF(Header)-Header), because NewBB dominates 379 // everything that Header does, and it strictly dominates Header in 380 // addition. 381 assert(DF->find(Header) != DF->end() && "Header node doesn't have DF set?"); 382 DominanceFrontier::DomSetType NewDFSet = DF->find(Header)->second; 383 NewDFSet.erase(Header); 384 DF->addBasicBlock(NewBB, NewDFSet); 385 386 // Now we must loop over all of the dominance frontiers in the function, 387 // replacing occurrences of Header with NewBB in some cases. If a block 388 // dominates a (now) predecessor of NewBB, but did not strictly dominate 389 // Header, it will have Header in it's DF set, but should now have NewBB in 390 // its set. 391 for (unsigned i = 0, e = OutsideBlocks.size(); i != e; ++i) { 392 // Get all of the dominators of the predecessor... 393 const DominatorSet::DomSetType &PredDoms = 394 DS.getDominators(OutsideBlocks[i]); 395 for (DominatorSet::DomSetType::const_iterator PDI = PredDoms.begin(), 396 PDE = PredDoms.end(); PDI != PDE; ++PDI) { 397 BasicBlock *PredDom = *PDI; 398 // If the loop header is in DF(PredDom), then PredDom didn't dominate 399 // the header but did dominate a predecessor outside of the loop. Now 400 // we change this entry to include the preheader in the DF instead of 401 // the header. 402 DominanceFrontier::iterator DFI = DF->find(PredDom); 403 assert(DFI != DF->end() && "No dominance frontier for node?"); 404 if (DFI->second.count(Header)) { 405 DF->removeFromFrontier(DFI, Header); 406 DF->addToFrontier(DFI, NewBB); 407 } 408 } 409 } 410 } 411} 412 413/// RewriteLoopExitBlock - Ensure that the loop preheader dominates all exit 414/// blocks. This method is used to split exit blocks that have predecessors 415/// outside of the loop. 416BasicBlock *LoopSimplify::RewriteLoopExitBlock(Loop *L, BasicBlock *Exit) { 417 std::vector<BasicBlock*> LoopBlocks; 418 for (pred_iterator I = pred_begin(Exit), E = pred_end(Exit); I != E; ++I) 419 if (L->contains(*I)) 420 LoopBlocks.push_back(*I); 421 422 assert(!LoopBlocks.empty() && "No edges coming in from outside the loop?"); 423 BasicBlock *NewBB = SplitBlockPredecessors(Exit, ".loopexit", LoopBlocks); 424 425 // Update Loop Information - we know that the new block will be in whichever 426 // loop the Exit block is in. Note that it may not be in that immediate loop, 427 // if the successor is some other loop header. In that case, we continue 428 // walking up the loop tree to find a loop that contains both the successor 429 // block and the predecessor block. 430 Loop *SuccLoop = LI->getLoopFor(Exit); 431 while (SuccLoop && !SuccLoop->contains(L->getHeader())) 432 SuccLoop = SuccLoop->getParentLoop(); 433 if (SuccLoop) 434 SuccLoop->addBasicBlockToLoop(NewBB, *LI); 435 436 // Update dominator information (set, immdom, domtree, and domfrontier) 437 UpdateDomInfoForRevectoredPreds(NewBB, LoopBlocks); 438 return NewBB; 439} 440 441/// AddBlockAndPredsToSet - Add the specified block, and all of its 442/// predecessors, to the specified set, if it's not already in there. Stop 443/// predecessor traversal when we reach StopBlock. 444static void AddBlockAndPredsToSet(BasicBlock *BB, BasicBlock *StopBlock, 445 std::set<BasicBlock*> &Blocks) { 446 if (!Blocks.insert(BB).second) return; // already processed. 447 if (BB == StopBlock) return; // Stop here! 448 449 for (pred_iterator I = pred_begin(BB), E = pred_end(BB); I != E; ++I) 450 AddBlockAndPredsToSet(*I, StopBlock, Blocks); 451} 452 453/// FindPHIToPartitionLoops - The first part of loop-nestification is to find a 454/// PHI node that tells us how to partition the loops. 455static PHINode *FindPHIToPartitionLoops(Loop *L, DominatorSet &DS, 456 AliasAnalysis *AA) { 457 for (BasicBlock::iterator I = L->getHeader()->begin(); isa<PHINode>(I); ) { 458 PHINode *PN = cast<PHINode>(I); 459 ++I; 460 if (Value *V = PN->hasConstantValue()) 461 if (!isa<Instruction>(V) || DS.dominates(cast<Instruction>(V), PN)) { 462 // This is a degenerate PHI already, don't modify it! 463 PN->replaceAllUsesWith(V); 464 if (AA) AA->deleteValue(PN); 465 PN->eraseFromParent(); 466 continue; 467 } 468 469 // Scan this PHI node looking for a use of the PHI node by itself. 470 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) 471 if (PN->getIncomingValue(i) == PN && 472 L->contains(PN->getIncomingBlock(i))) 473 // We found something tasty to remove. 474 return PN; 475 } 476 return 0; 477} 478 479/// SeparateNestedLoop - If this loop has multiple backedges, try to pull one of 480/// them out into a nested loop. This is important for code that looks like 481/// this: 482/// 483/// Loop: 484/// ... 485/// br cond, Loop, Next 486/// ... 487/// br cond2, Loop, Out 488/// 489/// To identify this common case, we look at the PHI nodes in the header of the 490/// loop. PHI nodes with unchanging values on one backedge correspond to values 491/// that change in the "outer" loop, but not in the "inner" loop. 492/// 493/// If we are able to separate out a loop, return the new outer loop that was 494/// created. 495/// 496Loop *LoopSimplify::SeparateNestedLoop(Loop *L) { 497 PHINode *PN = FindPHIToPartitionLoops(L, getAnalysis<DominatorSet>(), AA); 498 if (PN == 0) return 0; // No known way to partition. 499 500 // Pull out all predecessors that have varying values in the loop. This 501 // handles the case when a PHI node has multiple instances of itself as 502 // arguments. 503 std::vector<BasicBlock*> OuterLoopPreds; 504 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) 505 if (PN->getIncomingValue(i) != PN || 506 !L->contains(PN->getIncomingBlock(i))) 507 OuterLoopPreds.push_back(PN->getIncomingBlock(i)); 508 509 BasicBlock *Header = L->getHeader(); 510 BasicBlock *NewBB = SplitBlockPredecessors(Header, ".outer", OuterLoopPreds); 511 512 // Update dominator information (set, immdom, domtree, and domfrontier) 513 UpdateDomInfoForRevectoredPreds(NewBB, OuterLoopPreds); 514 515 // Create the new outer loop. 516 Loop *NewOuter = new Loop(); 517 518 // Change the parent loop to use the outer loop as its child now. 519 if (Loop *Parent = L->getParentLoop()) 520 Parent->replaceChildLoopWith(L, NewOuter); 521 else 522 LI->changeTopLevelLoop(L, NewOuter); 523 524 // This block is going to be our new header block: add it to this loop and all 525 // parent loops. 526 NewOuter->addBasicBlockToLoop(NewBB, *LI); 527 528 // L is now a subloop of our outer loop. 529 NewOuter->addChildLoop(L); 530 531 for (unsigned i = 0, e = L->getBlocks().size(); i != e; ++i) 532 NewOuter->addBlockEntry(L->getBlocks()[i]); 533 534 // Determine which blocks should stay in L and which should be moved out to 535 // the Outer loop now. 536 DominatorSet &DS = getAnalysis<DominatorSet>(); 537 std::set<BasicBlock*> BlocksInL; 538 for (pred_iterator PI = pred_begin(Header), E = pred_end(Header); PI!=E; ++PI) 539 if (DS.dominates(Header, *PI)) 540 AddBlockAndPredsToSet(*PI, Header, BlocksInL); 541 542 543 // Scan all of the loop children of L, moving them to OuterLoop if they are 544 // not part of the inner loop. 545 for (Loop::iterator I = L->begin(); I != L->end(); ) 546 if (BlocksInL.count((*I)->getHeader())) 547 ++I; // Loop remains in L 548 else 549 NewOuter->addChildLoop(L->removeChildLoop(I)); 550 551 // Now that we know which blocks are in L and which need to be moved to 552 // OuterLoop, move any blocks that need it. 553 for (unsigned i = 0; i != L->getBlocks().size(); ++i) { 554 BasicBlock *BB = L->getBlocks()[i]; 555 if (!BlocksInL.count(BB)) { 556 // Move this block to the parent, updating the exit blocks sets 557 L->removeBlockFromLoop(BB); 558 if ((*LI)[BB] == L) 559 LI->changeLoopFor(BB, NewOuter); 560 --i; 561 } 562 } 563 564 return NewOuter; 565} 566 567 568 569/// InsertUniqueBackedgeBlock - This method is called when the specified loop 570/// has more than one backedge in it. If this occurs, revector all of these 571/// backedges to target a new basic block and have that block branch to the loop 572/// header. This ensures that loops have exactly one backedge. 573/// 574void LoopSimplify::InsertUniqueBackedgeBlock(Loop *L) { 575 assert(L->getNumBackEdges() > 1 && "Must have > 1 backedge!"); 576 577 // Get information about the loop 578 BasicBlock *Preheader = L->getLoopPreheader(); 579 BasicBlock *Header = L->getHeader(); 580 Function *F = Header->getParent(); 581 582 // Figure out which basic blocks contain back-edges to the loop header. 583 std::vector<BasicBlock*> BackedgeBlocks; 584 for (pred_iterator I = pred_begin(Header), E = pred_end(Header); I != E; ++I) 585 if (*I != Preheader) BackedgeBlocks.push_back(*I); 586 587 // Create and insert the new backedge block... 588 BasicBlock *BEBlock = new BasicBlock(Header->getName()+".backedge", F); 589 BranchInst *BETerminator = new BranchInst(Header, BEBlock); 590 591 // Move the new backedge block to right after the last backedge block. 592 Function::iterator InsertPos = BackedgeBlocks.back(); ++InsertPos; 593 F->getBasicBlockList().splice(InsertPos, F->getBasicBlockList(), BEBlock); 594 595 // Now that the block has been inserted into the function, create PHI nodes in 596 // the backedge block which correspond to any PHI nodes in the header block. 597 for (BasicBlock::iterator I = Header->begin(); isa<PHINode>(I); ++I) { 598 PHINode *PN = cast<PHINode>(I); 599 PHINode *NewPN = new PHINode(PN->getType(), PN->getName()+".be", 600 BETerminator); 601 NewPN->reserveOperandSpace(BackedgeBlocks.size()); 602 if (AA) AA->copyValue(PN, NewPN); 603 604 // Loop over the PHI node, moving all entries except the one for the 605 // preheader over to the new PHI node. 606 unsigned PreheaderIdx = ~0U; 607 bool HasUniqueIncomingValue = true; 608 Value *UniqueValue = 0; 609 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) { 610 BasicBlock *IBB = PN->getIncomingBlock(i); 611 Value *IV = PN->getIncomingValue(i); 612 if (IBB == Preheader) { 613 PreheaderIdx = i; 614 } else { 615 NewPN->addIncoming(IV, IBB); 616 if (HasUniqueIncomingValue) { 617 if (UniqueValue == 0) 618 UniqueValue = IV; 619 else if (UniqueValue != IV) 620 HasUniqueIncomingValue = false; 621 } 622 } 623 } 624 625 // Delete all of the incoming values from the old PN except the preheader's 626 assert(PreheaderIdx != ~0U && "PHI has no preheader entry??"); 627 if (PreheaderIdx != 0) { 628 PN->setIncomingValue(0, PN->getIncomingValue(PreheaderIdx)); 629 PN->setIncomingBlock(0, PN->getIncomingBlock(PreheaderIdx)); 630 } 631 // Nuke all entries except the zero'th. 632 for (unsigned i = 0, e = PN->getNumIncomingValues()-1; i != e; ++i) 633 PN->removeIncomingValue(e-i, false); 634 635 // Finally, add the newly constructed PHI node as the entry for the BEBlock. 636 PN->addIncoming(NewPN, BEBlock); 637 638 // As an optimization, if all incoming values in the new PhiNode (which is a 639 // subset of the incoming values of the old PHI node) have the same value, 640 // eliminate the PHI Node. 641 if (HasUniqueIncomingValue) { 642 NewPN->replaceAllUsesWith(UniqueValue); 643 if (AA) AA->deleteValue(NewPN); 644 BEBlock->getInstList().erase(NewPN); 645 } 646 } 647 648 // Now that all of the PHI nodes have been inserted and adjusted, modify the 649 // backedge blocks to just to the BEBlock instead of the header. 650 for (unsigned i = 0, e = BackedgeBlocks.size(); i != e; ++i) { 651 TerminatorInst *TI = BackedgeBlocks[i]->getTerminator(); 652 for (unsigned Op = 0, e = TI->getNumSuccessors(); Op != e; ++Op) 653 if (TI->getSuccessor(Op) == Header) 654 TI->setSuccessor(Op, BEBlock); 655 } 656 657 //===--- Update all analyses which we must preserve now -----------------===// 658 659 // Update Loop Information - we know that this block is now in the current 660 // loop and all parent loops. 661 L->addBasicBlockToLoop(BEBlock, *LI); 662 663 // Update dominator information (set, immdom, domtree, and domfrontier) 664 UpdateDomInfoForRevectoredPreds(BEBlock, BackedgeBlocks); 665} 666 667/// UpdateDomInfoForRevectoredPreds - This method is used to update the four 668/// different kinds of dominator information (dominator sets, immediate 669/// dominators, dominator trees, and dominance frontiers) after a new block has 670/// been added to the CFG. 671/// 672/// This only supports the case when an existing block (known as "NewBBSucc"), 673/// had some of its predecessors factored into a new basic block. This 674/// transformation inserts a new basic block ("NewBB"), with a single 675/// unconditional branch to NewBBSucc, and moves some predecessors of 676/// "NewBBSucc" to now branch to NewBB. These predecessors are listed in 677/// PredBlocks, even though they are the same as 678/// pred_begin(NewBB)/pred_end(NewBB). 679/// 680void LoopSimplify::UpdateDomInfoForRevectoredPreds(BasicBlock *NewBB, 681 std::vector<BasicBlock*> &PredBlocks) { 682 assert(!PredBlocks.empty() && "No predblocks??"); 683 assert(succ_begin(NewBB) != succ_end(NewBB) && 684 ++succ_begin(NewBB) == succ_end(NewBB) && 685 "NewBB should have a single successor!"); 686 BasicBlock *NewBBSucc = *succ_begin(NewBB); 687 DominatorSet &DS = getAnalysis<DominatorSet>(); 688 689 // Update dominator information... The blocks that dominate NewBB are the 690 // intersection of the dominators of predecessors, plus the block itself. 691 // 692 DominatorSet::DomSetType NewBBDomSet = DS.getDominators(PredBlocks[0]); 693 for (unsigned i = 1, e = PredBlocks.size(); i != e; ++i) 694 set_intersect(NewBBDomSet, DS.getDominators(PredBlocks[i])); 695 NewBBDomSet.insert(NewBB); // All blocks dominate themselves... 696 DS.addBasicBlock(NewBB, NewBBDomSet); 697 698 // The newly inserted basic block will dominate existing basic blocks iff the 699 // PredBlocks dominate all of the non-pred blocks. If all predblocks dominate 700 // the non-pred blocks, then they all must be the same block! 701 // 702 bool NewBBDominatesNewBBSucc = true; 703 { 704 BasicBlock *OnePred = PredBlocks[0]; 705 for (unsigned i = 1, e = PredBlocks.size(); i != e; ++i) 706 if (PredBlocks[i] != OnePred) { 707 NewBBDominatesNewBBSucc = false; 708 break; 709 } 710 711 if (NewBBDominatesNewBBSucc) 712 for (pred_iterator PI = pred_begin(NewBBSucc), E = pred_end(NewBBSucc); 713 PI != E; ++PI) 714 if (*PI != NewBB && !DS.dominates(NewBBSucc, *PI)) { 715 NewBBDominatesNewBBSucc = false; 716 break; 717 } 718 } 719 720 // The other scenario where the new block can dominate its successors are when 721 // all predecessors of NewBBSucc that are not NewBB are dominated by NewBBSucc 722 // already. 723 if (!NewBBDominatesNewBBSucc) { 724 NewBBDominatesNewBBSucc = true; 725 for (pred_iterator PI = pred_begin(NewBBSucc), E = pred_end(NewBBSucc); 726 PI != E; ++PI) 727 if (*PI != NewBB && !DS.dominates(NewBBSucc, *PI)) { 728 NewBBDominatesNewBBSucc = false; 729 break; 730 } 731 } 732 733 // If NewBB dominates some blocks, then it will dominate all blocks that 734 // NewBBSucc does. 735 if (NewBBDominatesNewBBSucc) { 736 BasicBlock *PredBlock = PredBlocks[0]; 737 Function *F = NewBB->getParent(); 738 for (Function::iterator I = F->begin(), E = F->end(); I != E; ++I) 739 if (DS.dominates(NewBBSucc, I)) 740 DS.addDominator(I, NewBB); 741 } 742 743 // Update immediate dominator information if we have it... 744 BasicBlock *NewBBIDom = 0; 745 if (ImmediateDominators *ID = getAnalysisToUpdate<ImmediateDominators>()) { 746 // To find the immediate dominator of the new exit node, we trace up the 747 // immediate dominators of a predecessor until we find a basic block that 748 // dominates the exit block. 749 // 750 BasicBlock *Dom = PredBlocks[0]; // Some random predecessor... 751 while (!NewBBDomSet.count(Dom)) { // Loop until we find a dominator... 752 assert(Dom != 0 && "No shared dominator found???"); 753 Dom = ID->get(Dom); 754 } 755 756 // Set the immediate dominator now... 757 ID->addNewBlock(NewBB, Dom); 758 NewBBIDom = Dom; // Reuse this if calculating DominatorTree info... 759 760 // If NewBB strictly dominates other blocks, we need to update their idom's 761 // now. The only block that need adjustment is the NewBBSucc block, whose 762 // idom should currently be set to PredBlocks[0]. 763 if (NewBBDominatesNewBBSucc) 764 ID->setImmediateDominator(NewBBSucc, NewBB); 765 } 766 767 // Update DominatorTree information if it is active. 768 if (DominatorTree *DT = getAnalysisToUpdate<DominatorTree>()) { 769 // If we don't have ImmediateDominator info around, calculate the idom as 770 // above. 771 DominatorTree::Node *NewBBIDomNode; 772 if (NewBBIDom) { 773 NewBBIDomNode = DT->getNode(NewBBIDom); 774 } else { 775 NewBBIDomNode = DT->getNode(PredBlocks[0]); // Random pred 776 while (!NewBBDomSet.count(NewBBIDomNode->getBlock())) { 777 NewBBIDomNode = NewBBIDomNode->getIDom(); 778 assert(NewBBIDomNode && "No shared dominator found??"); 779 } 780 NewBBIDom = NewBBIDomNode->getBlock(); 781 } 782 783 // Create the new dominator tree node... and set the idom of NewBB. 784 DominatorTree::Node *NewBBNode = DT->createNewNode(NewBB, NewBBIDomNode); 785 786 // If NewBB strictly dominates other blocks, then it is now the immediate 787 // dominator of NewBBSucc. Update the dominator tree as appropriate. 788 if (NewBBDominatesNewBBSucc) { 789 DominatorTree::Node *NewBBSuccNode = DT->getNode(NewBBSucc); 790 DT->changeImmediateDominator(NewBBSuccNode, NewBBNode); 791 } 792 } 793 794 // Update ET-Forest information if it is active. 795 if (ETForest *EF = getAnalysisToUpdate<ETForest>()) { 796 EF->addNewBlock(NewBB, NewBBIDom); 797 if (NewBBDominatesNewBBSucc) 798 EF->setImmediateDominator(NewBBSucc, NewBB); 799 } 800 801 // Update dominance frontier information... 802 if (DominanceFrontier *DF = getAnalysisToUpdate<DominanceFrontier>()) { 803 // If NewBB dominates NewBBSucc, then DF(NewBB) is now going to be the 804 // DF(PredBlocks[0]) without the stuff that the new block does not dominate 805 // a predecessor of. 806 if (NewBBDominatesNewBBSucc) { 807 DominanceFrontier::iterator DFI = DF->find(PredBlocks[0]); 808 if (DFI != DF->end()) { 809 DominanceFrontier::DomSetType Set = DFI->second; 810 // Filter out stuff in Set that we do not dominate a predecessor of. 811 for (DominanceFrontier::DomSetType::iterator SetI = Set.begin(), 812 E = Set.end(); SetI != E;) { 813 bool DominatesPred = false; 814 for (pred_iterator PI = pred_begin(*SetI), E = pred_end(*SetI); 815 PI != E; ++PI) 816 if (DS.dominates(NewBB, *PI)) 817 DominatesPred = true; 818 if (!DominatesPred) 819 Set.erase(SetI++); 820 else 821 ++SetI; 822 } 823 824 DF->addBasicBlock(NewBB, Set); 825 } 826 827 } else { 828 // DF(NewBB) is {NewBBSucc} because NewBB does not strictly dominate 829 // NewBBSucc, but it does dominate itself (and there is an edge (NewBB -> 830 // NewBBSucc)). NewBBSucc is the single successor of NewBB. 831 DominanceFrontier::DomSetType NewDFSet; 832 NewDFSet.insert(NewBBSucc); 833 DF->addBasicBlock(NewBB, NewDFSet); 834 } 835 836 // Now we must loop over all of the dominance frontiers in the function, 837 // replacing occurrences of NewBBSucc with NewBB in some cases. All 838 // blocks that dominate a block in PredBlocks and contained NewBBSucc in 839 // their dominance frontier must be updated to contain NewBB instead. 840 // 841 for (unsigned i = 0, e = PredBlocks.size(); i != e; ++i) { 842 BasicBlock *Pred = PredBlocks[i]; 843 // Get all of the dominators of the predecessor... 844 const DominatorSet::DomSetType &PredDoms = DS.getDominators(Pred); 845 for (DominatorSet::DomSetType::const_iterator PDI = PredDoms.begin(), 846 PDE = PredDoms.end(); PDI != PDE; ++PDI) { 847 BasicBlock *PredDom = *PDI; 848 849 // If the NewBBSucc node is in DF(PredDom), then PredDom didn't 850 // dominate NewBBSucc but did dominate a predecessor of it. Now we 851 // change this entry to include NewBB in the DF instead of NewBBSucc. 852 DominanceFrontier::iterator DFI = DF->find(PredDom); 853 assert(DFI != DF->end() && "No dominance frontier for node?"); 854 if (DFI->second.count(NewBBSucc)) { 855 // If NewBBSucc should not stay in our dominator frontier, remove it. 856 // We remove it unless there is a predecessor of NewBBSucc that we 857 // dominate, but we don't strictly dominate NewBBSucc. 858 bool ShouldRemove = true; 859 if (PredDom == NewBBSucc || !DS.dominates(PredDom, NewBBSucc)) { 860 // Okay, we know that PredDom does not strictly dominate NewBBSucc. 861 // Check to see if it dominates any predecessors of NewBBSucc. 862 for (pred_iterator PI = pred_begin(NewBBSucc), 863 E = pred_end(NewBBSucc); PI != E; ++PI) 864 if (DS.dominates(PredDom, *PI)) { 865 ShouldRemove = false; 866 break; 867 } 868 } 869 870 if (ShouldRemove) 871 DF->removeFromFrontier(DFI, NewBBSucc); 872 DF->addToFrontier(DFI, NewBB); 873 } 874 } 875 } 876 } 877} 878 879