BreakCriticalEdges.cpp revision a3ca0b648cd03cb3c003e09f2079f570ce2ac600
1d76efa018660e806cd87c0a24512e3c532fc1d36Chris Lattner//===- BreakCriticalEdges.cpp - Critical Edge Elimination Pass ------------===// 2fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman// 3b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// The LLVM Compiler Infrastructure 4b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// 5b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// This file was developed by the LLVM research group and is distributed under 6b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// the University of Illinois Open Source License. See LICENSE.TXT for details. 7fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman// 8b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell//===----------------------------------------------------------------------===// 9d76efa018660e806cd87c0a24512e3c532fc1d36Chris Lattner// 10d76efa018660e806cd87c0a24512e3c532fc1d36Chris Lattner// BreakCriticalEdges pass - Break all of the critical edges in the CFG by 11d76efa018660e806cd87c0a24512e3c532fc1d36Chris Lattner// inserting a dummy basic block. This pass may be "required" by passes that 12d76efa018660e806cd87c0a24512e3c532fc1d36Chris Lattner// cannot deal with critical edges. For this usage, the structure type is 13d76efa018660e806cd87c0a24512e3c532fc1d36Chris Lattner// forward declared. This pass obviously invalidates the CFG, but can update 14363ca610d1186c34f25ecad00e8dea61cc91b36aChris Lattner// forward dominator (set, immediate dominators, tree, and frontier) 15363ca610d1186c34f25ecad00e8dea61cc91b36aChris Lattner// information. 16d76efa018660e806cd87c0a24512e3c532fc1d36Chris Lattner// 17d76efa018660e806cd87c0a24512e3c532fc1d36Chris Lattner//===----------------------------------------------------------------------===// 18d76efa018660e806cd87c0a24512e3c532fc1d36Chris Lattner 19d216e8ba60494caacf919cbf5fef110d48f0d162Chris Lattner#define DEBUG_TYPE "break-crit-edges" 20d76efa018660e806cd87c0a24512e3c532fc1d36Chris Lattner#include "llvm/Transforms/Scalar.h" 21d23520cd9403c3c6fe8e7ea974ae0b593772345cChris Lattner#include "llvm/Transforms/Utils/BasicBlockUtils.h" 22d76efa018660e806cd87c0a24512e3c532fc1d36Chris Lattner#include "llvm/Analysis/Dominators.h" 230ae380a8ac48cbf3131f96318a15dc5dae8a6c78Chris Lattner#include "llvm/Analysis/LoopInfo.h" 24d76efa018660e806cd87c0a24512e3c532fc1d36Chris Lattner#include "llvm/Function.h" 2547b14a4a6a455c7be169cfd312fcbe796f0ad426Misha Brukman#include "llvm/Instructions.h" 265b3a4553c1da7e417a240379e2f510c77532c5c1Chris Lattner#include "llvm/Type.h" 27eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner#include "llvm/Support/CFG.h" 28a4f0b3a084d120cfc5b5bb06f64b222f5cb72740Chris Lattner#include "llvm/Support/Compiler.h" 2986f7b2100c7b6b426869178327e352d122056f73Chris Lattner#include "llvm/ADT/SmallVector.h" 30551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/ADT/Statistic.h" 31f7703df4968084c18c248c1feea9961c19a32e6aChris Lattnerusing namespace llvm; 32d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 33d216e8ba60494caacf919cbf5fef110d48f0d162Chris LattnerSTATISTIC(NumBroken, "Number of blocks inserted"); 346de302bbdb0ac8a595ca35a06e5bbc1605e1da3eChris Lattner 35d216e8ba60494caacf919cbf5fef110d48f0d162Chris Lattnernamespace { 369525528a7dc5462b6374d38c81ba5c07b11741feChris Lattner struct VISIBILITY_HIDDEN BreakCriticalEdges : public FunctionPass { 376de302bbdb0ac8a595ca35a06e5bbc1605e1da3eChris Lattner virtual bool runOnFunction(Function &F); 38fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 396de302bbdb0ac8a595ca35a06e5bbc1605e1da3eChris Lattner virtual void getAnalysisUsage(AnalysisUsage &AU) const { 40dd9e9566052d02c9fa053756bb0136eb25e9018bChris Lattner AU.addPreserved<ETForest>(); 416de302bbdb0ac8a595ca35a06e5bbc1605e1da3eChris Lattner AU.addPreserved<ImmediateDominators>(); 42a3ca0b648cd03cb3c003e09f2079f570ce2ac600Owen Anderson AU.addPreserved<DominatorTree>(); 436918c079a1393be8ae551d699479fbfa39b99277Chris Lattner AU.addPreserved<DominanceFrontier>(); 440ae380a8ac48cbf3131f96318a15dc5dae8a6c78Chris Lattner AU.addPreserved<LoopInfo>(); 4598bf436e2e2ab463d79c54a42a46b12028905330Chris Lattner 4698bf436e2e2ab463d79c54a42a46b12028905330Chris Lattner // No loop canonicalization guarantees are broken by this pass. 4798bf436e2e2ab463d79c54a42a46b12028905330Chris Lattner AU.addPreservedID(LoopSimplifyID); 486de302bbdb0ac8a595ca35a06e5bbc1605e1da3eChris Lattner } 496de302bbdb0ac8a595ca35a06e5bbc1605e1da3eChris Lattner }; 506de302bbdb0ac8a595ca35a06e5bbc1605e1da3eChris Lattner 517f8897f22e88271cfa114998a4d6088e7c8e8e11Chris Lattner RegisterPass<BreakCriticalEdges> X("break-crit-edges", 526de302bbdb0ac8a595ca35a06e5bbc1605e1da3eChris Lattner "Break critical edges in CFG"); 536de302bbdb0ac8a595ca35a06e5bbc1605e1da3eChris Lattner} 54d76efa018660e806cd87c0a24512e3c532fc1d36Chris Lattner 55eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner// Publically exposed interface to pass... 56f7703df4968084c18c248c1feea9961c19a32e6aChris Lattnerconst PassInfo *llvm::BreakCriticalEdgesID = X.getPassInfo(); 571e5fdf8ba0453baafe062525dc8472846da3ec1fChris LattnerFunctionPass *llvm::createBreakCriticalEdgesPass() { 581e5fdf8ba0453baafe062525dc8472846da3ec1fChris Lattner return new BreakCriticalEdges(); 591e5fdf8ba0453baafe062525dc8472846da3ec1fChris Lattner} 60d76efa018660e806cd87c0a24512e3c532fc1d36Chris Lattner 61363ca610d1186c34f25ecad00e8dea61cc91b36aChris Lattner// runOnFunction - Loop over all of the edges in the CFG, breaking critical 62363ca610d1186c34f25ecad00e8dea61cc91b36aChris Lattner// edges as they are found. 63363ca610d1186c34f25ecad00e8dea61cc91b36aChris Lattner// 64363ca610d1186c34f25ecad00e8dea61cc91b36aChris Lattnerbool BreakCriticalEdges::runOnFunction(Function &F) { 65363ca610d1186c34f25ecad00e8dea61cc91b36aChris Lattner bool Changed = false; 66363ca610d1186c34f25ecad00e8dea61cc91b36aChris Lattner for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I) { 67363ca610d1186c34f25ecad00e8dea61cc91b36aChris Lattner TerminatorInst *TI = I->getTerminator(); 68363ca610d1186c34f25ecad00e8dea61cc91b36aChris Lattner if (TI->getNumSuccessors() > 1) 69363ca610d1186c34f25ecad00e8dea61cc91b36aChris Lattner for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i) 70363ca610d1186c34f25ecad00e8dea61cc91b36aChris Lattner if (SplitCriticalEdge(TI, i, this)) { 71363ca610d1186c34f25ecad00e8dea61cc91b36aChris Lattner ++NumBroken; 72363ca610d1186c34f25ecad00e8dea61cc91b36aChris Lattner Changed = true; 73363ca610d1186c34f25ecad00e8dea61cc91b36aChris Lattner } 74363ca610d1186c34f25ecad00e8dea61cc91b36aChris Lattner } 75363ca610d1186c34f25ecad00e8dea61cc91b36aChris Lattner 76363ca610d1186c34f25ecad00e8dea61cc91b36aChris Lattner return Changed; 77363ca610d1186c34f25ecad00e8dea61cc91b36aChris Lattner} 78363ca610d1186c34f25ecad00e8dea61cc91b36aChris Lattner 79363ca610d1186c34f25ecad00e8dea61cc91b36aChris Lattner//===----------------------------------------------------------------------===// 80363ca610d1186c34f25ecad00e8dea61cc91b36aChris Lattner// Implementation of the external critical edge manipulation functions 81363ca610d1186c34f25ecad00e8dea61cc91b36aChris Lattner//===----------------------------------------------------------------------===// 82eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner 83eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner// isCriticalEdge - Return true if the specified edge is a critical edge. 84eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner// Critical edges are edges from a block with multiple successors to a block 85eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner// with multiple predecessors. 86eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner// 87b57de3328d3826e1f270f3a38256ff67aaec1871Chris Lattnerbool llvm::isCriticalEdge(const TerminatorInst *TI, unsigned SuccNum, 88b57de3328d3826e1f270f3a38256ff67aaec1871Chris Lattner bool AllowIdenticalEdges) { 89eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner assert(SuccNum < TI->getNumSuccessors() && "Illegal edge specification!"); 90e802a023d98b06307831cd122e61da86431e8dacChris Lattner if (TI->getNumSuccessors() == 1) return false; 91eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner 92eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner const BasicBlock *Dest = TI->getSuccessor(SuccNum); 93eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner pred_const_iterator I = pred_begin(Dest), E = pred_end(Dest); 94eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner 95eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner // If there is more than one predecessor, this is a critical edge... 96eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner assert(I != E && "No preds, but we have an edge to the block?"); 97b57de3328d3826e1f270f3a38256ff67aaec1871Chris Lattner const BasicBlock *FirstPred = *I; 98eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner ++I; // Skip one edge due to the incoming arc from TI. 99b57de3328d3826e1f270f3a38256ff67aaec1871Chris Lattner if (!AllowIdenticalEdges) 100b57de3328d3826e1f270f3a38256ff67aaec1871Chris Lattner return I != E; 101b57de3328d3826e1f270f3a38256ff67aaec1871Chris Lattner 102b57de3328d3826e1f270f3a38256ff67aaec1871Chris Lattner // If AllowIdenticalEdges is true, then we allow this edge to be considered 103b57de3328d3826e1f270f3a38256ff67aaec1871Chris Lattner // non-critical iff all preds come from TI's block. 104b57de3328d3826e1f270f3a38256ff67aaec1871Chris Lattner for (; I != E; ++I) 105b57de3328d3826e1f270f3a38256ff67aaec1871Chris Lattner if (*I != FirstPred) return true; 106b57de3328d3826e1f270f3a38256ff67aaec1871Chris Lattner return false; 107eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner} 108eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner 109d23520cd9403c3c6fe8e7ea974ae0b593772345cChris Lattner// SplitCriticalEdge - If this edge is a critical edge, insert a new node to 1102d43519454dbcf17054835ded19b031f66e31670Owen Anderson// split the critical edge. This will update ETForest, ImmediateDominator, 111d23520cd9403c3c6fe8e7ea974ae0b593772345cChris Lattner// DominatorTree, and DominatorFrontier information if it is available, thus 11227e1f90d8551b84db910c93ab21c941031c18b60Chris Lattner// calling this pass will not invalidate any of them. This returns true if 11327e1f90d8551b84db910c93ab21c941031c18b60Chris Lattner// the edge was split, false otherwise. This ensures that all edges to that 11427e1f90d8551b84db910c93ab21c941031c18b60Chris Lattner// dest go to one block instead of each going to a different block. 115eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner// 11627e1f90d8551b84db910c93ab21c941031c18b60Chris Lattnerbool llvm::SplitCriticalEdge(TerminatorInst *TI, unsigned SuccNum, Pass *P, 11727e1f90d8551b84db910c93ab21c941031c18b60Chris Lattner bool MergeIdenticalEdges) { 118b57de3328d3826e1f270f3a38256ff67aaec1871Chris Lattner if (!isCriticalEdge(TI, SuccNum, MergeIdenticalEdges)) return false; 119eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner BasicBlock *TIBB = TI->getParent(); 1206918c079a1393be8ae551d699479fbfa39b99277Chris Lattner BasicBlock *DestBB = TI->getSuccessor(SuccNum); 121eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner 122eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner // Create a new basic block, linking it into the CFG. 1236918c079a1393be8ae551d699479fbfa39b99277Chris Lattner BasicBlock *NewBB = new BasicBlock(TIBB->getName() + "." + 1246918c079a1393be8ae551d699479fbfa39b99277Chris Lattner DestBB->getName() + "_crit_edge"); 125eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner // Create our unconditional branch... 126108e4ab159b59a616b0868e396dc7ddc1fb48616Chris Lattner new BranchInst(DestBB, NewBB); 127fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 12827e1f90d8551b84db910c93ab21c941031c18b60Chris Lattner // Branch to the new block, breaking the edge. 129eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner TI->setSuccessor(SuccNum, NewBB); 130eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner 131eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner // Insert the block into the function... right after the block TI lives in. 132eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner Function &F = *TIBB->getParent(); 133eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner F.getBasicBlockList().insert(TIBB->getNext(), NewBB); 13427e1f90d8551b84db910c93ab21c941031c18b60Chris Lattner 135eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner // If there are any PHI nodes in DestBB, we need to update them so that they 136eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner // merge incoming values from NewBB instead of from TIBB. 137eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner // 1382da5c3dda6f5b9c4ec6d55008d33327764364bd4Reid Spencer for (BasicBlock::iterator I = DestBB->begin(); isa<PHINode>(I); ++I) { 1392da5c3dda6f5b9c4ec6d55008d33327764364bd4Reid Spencer PHINode *PN = cast<PHINode>(I); 14006887c9a2ad0d30c3cdfeff4d5e268a634c9d1a6Chris Lattner // We no longer enter through TIBB, now we come in through NewBB. Revector 14106887c9a2ad0d30c3cdfeff4d5e268a634c9d1a6Chris Lattner // exactly one entry in the PHI node that used to come from TIBB to come 14206887c9a2ad0d30c3cdfeff4d5e268a634c9d1a6Chris Lattner // from NewBB. 143b01bfd49c3353085e9ebb01d7b257f70583ee8c8Chris Lattner int BBIdx = PN->getBasicBlockIndex(TIBB); 144b01bfd49c3353085e9ebb01d7b257f70583ee8c8Chris Lattner PN->setIncomingBlock(BBIdx, NewBB); 145eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner } 14627e1f90d8551b84db910c93ab21c941031c18b60Chris Lattner 14727e1f90d8551b84db910c93ab21c941031c18b60Chris Lattner // If there are any other edges from TIBB to DestBB, update those to go 14827e1f90d8551b84db910c93ab21c941031c18b60Chris Lattner // through the split block, making those edges non-critical as well (and 14927e1f90d8551b84db910c93ab21c941031c18b60Chris Lattner // reducing the number of phi entries in the DestBB if relevant). 15027e1f90d8551b84db910c93ab21c941031c18b60Chris Lattner if (MergeIdenticalEdges) { 15127e1f90d8551b84db910c93ab21c941031c18b60Chris Lattner for (unsigned i = SuccNum+1, e = TI->getNumSuccessors(); i != e; ++i) { 15227e1f90d8551b84db910c93ab21c941031c18b60Chris Lattner if (TI->getSuccessor(i) != DestBB) continue; 15327e1f90d8551b84db910c93ab21c941031c18b60Chris Lattner 15427e1f90d8551b84db910c93ab21c941031c18b60Chris Lattner // Remove an entry for TIBB from DestBB phi nodes. 15527e1f90d8551b84db910c93ab21c941031c18b60Chris Lattner DestBB->removePredecessor(TIBB); 15627e1f90d8551b84db910c93ab21c941031c18b60Chris Lattner 15727e1f90d8551b84db910c93ab21c941031c18b60Chris Lattner // We found another edge to DestBB, go to NewBB instead. 15827e1f90d8551b84db910c93ab21c941031c18b60Chris Lattner TI->setSuccessor(i, NewBB); 15927e1f90d8551b84db910c93ab21c941031c18b60Chris Lattner } 16027e1f90d8551b84db910c93ab21c941031c18b60Chris Lattner } 16127e1f90d8551b84db910c93ab21c941031c18b60Chris Lattner 16227e1f90d8551b84db910c93ab21c941031c18b60Chris Lattner 163eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner 164e802a023d98b06307831cd122e61da86431e8dacChris Lattner // If we don't have a pass object, we can't update anything... 165d23520cd9403c3c6fe8e7ea974ae0b593772345cChris Lattner if (P == 0) return true; 166e802a023d98b06307831cd122e61da86431e8dacChris Lattner 16786f7b2100c7b6b426869178327e352d122056f73Chris Lattner // Now update analysis information. Since the only predecessor of NewBB is 16886f7b2100c7b6b426869178327e352d122056f73Chris Lattner // the TIBB, TIBB clearly dominates NewBB. TIBB usually doesn't dominate 16986f7b2100c7b6b426869178327e352d122056f73Chris Lattner // anything, as there are other successors of DestBB. However, if all other 17086f7b2100c7b6b426869178327e352d122056f73Chris Lattner // predecessors of DestBB are already dominated by DestBB (e.g. DestBB is a 17186f7b2100c7b6b426869178327e352d122056f73Chris Lattner // loop header) then NewBB dominates DestBB. 17286f7b2100c7b6b426869178327e352d122056f73Chris Lattner SmallVector<BasicBlock*, 8> OtherPreds; 173eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner 17486f7b2100c7b6b426869178327e352d122056f73Chris Lattner for (pred_iterator I = pred_begin(DestBB), E = pred_end(DestBB); I != E; ++I) 17586f7b2100c7b6b426869178327e352d122056f73Chris Lattner if (*I != NewBB) 17686f7b2100c7b6b426869178327e352d122056f73Chris Lattner OtherPreds.push_back(*I); 17786f7b2100c7b6b426869178327e352d122056f73Chris Lattner 17886f7b2100c7b6b426869178327e352d122056f73Chris Lattner bool NewBBDominatesDestBB = true; 17986f7b2100c7b6b426869178327e352d122056f73Chris Lattner 1802d43519454dbcf17054835ded19b031f66e31670Owen Anderson // Update the forest? 1812d43519454dbcf17054835ded19b031f66e31670Owen Anderson if (ETForest *EF = P->getAnalysisToUpdate<ETForest>()) { 1822d43519454dbcf17054835ded19b031f66e31670Owen Anderson // NewBB is dominated by TIBB. 1832d43519454dbcf17054835ded19b031f66e31670Owen Anderson EF->addNewBlock(NewBB, TIBB); 1842d43519454dbcf17054835ded19b031f66e31670Owen Anderson 1852d43519454dbcf17054835ded19b031f66e31670Owen Anderson // If NewBBDominatesDestBB hasn't been computed yet, do so with EF. 1862d43519454dbcf17054835ded19b031f66e31670Owen Anderson if (!OtherPreds.empty()) { 1872d43519454dbcf17054835ded19b031f66e31670Owen Anderson while (!OtherPreds.empty() && NewBBDominatesDestBB) { 1882d43519454dbcf17054835ded19b031f66e31670Owen Anderson NewBBDominatesDestBB = EF->dominates(DestBB, OtherPreds.back()); 1892d43519454dbcf17054835ded19b031f66e31670Owen Anderson OtherPreds.pop_back(); 19086f7b2100c7b6b426869178327e352d122056f73Chris Lattner } 1912d43519454dbcf17054835ded19b031f66e31670Owen Anderson OtherPreds.clear(); 19286f7b2100c7b6b426869178327e352d122056f73Chris Lattner } 1932d43519454dbcf17054835ded19b031f66e31670Owen Anderson 1942d43519454dbcf17054835ded19b031f66e31670Owen Anderson // If NewBBDominatesDestBB, then NewBB dominates DestBB, otherwise it 1952d43519454dbcf17054835ded19b031f66e31670Owen Anderson // doesn't dominate anything. 1962d43519454dbcf17054835ded19b031f66e31670Owen Anderson if (NewBBDominatesDestBB) 1972d43519454dbcf17054835ded19b031f66e31670Owen Anderson EF->setImmediateDominator(DestBB, NewBB); 198c178d9459a0e659bedbc1b3c79459ee168453376Chris Lattner } 199eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner 200cf00c4ab3ba308d45d98c5ccab87362cf802facbMisha Brukman // Should we update ImmediateDominator information? 201e802a023d98b06307831cd122e61da86431e8dacChris Lattner if (ImmediateDominators *ID = P->getAnalysisToUpdate<ImmediateDominators>()) { 202caed0e3d718a2c6f7734d19bcf47db0a572b8d83Chris Lattner // Only do this if TIBB is reachable. 203caed0e3d718a2c6f7734d19bcf47db0a572b8d83Chris Lattner if (ID->get(TIBB) || &TIBB->getParent()->getEntryBlock() == TIBB) { 2049fa58b5f66202e06f25446f0aeb60cb716ffa6d4Chris Lattner // TIBB is the new immediate dominator for NewBB. 2059fa58b5f66202e06f25446f0aeb60cb716ffa6d4Chris Lattner ID->addNewBlock(NewBB, TIBB); 2069fa58b5f66202e06f25446f0aeb60cb716ffa6d4Chris Lattner 2079fa58b5f66202e06f25446f0aeb60cb716ffa6d4Chris Lattner // If NewBBDominatesDestBB hasn't been computed yet, do so with ID. 2089fa58b5f66202e06f25446f0aeb60cb716ffa6d4Chris Lattner if (!OtherPreds.empty()) { 2099fa58b5f66202e06f25446f0aeb60cb716ffa6d4Chris Lattner while (!OtherPreds.empty() && NewBBDominatesDestBB) { 2109fa58b5f66202e06f25446f0aeb60cb716ffa6d4Chris Lattner NewBBDominatesDestBB = ID->dominates(DestBB, OtherPreds.back()); 2119fa58b5f66202e06f25446f0aeb60cb716ffa6d4Chris Lattner OtherPreds.pop_back(); 2129fa58b5f66202e06f25446f0aeb60cb716ffa6d4Chris Lattner } 2139fa58b5f66202e06f25446f0aeb60cb716ffa6d4Chris Lattner OtherPreds.clear(); 21486f7b2100c7b6b426869178327e352d122056f73Chris Lattner } 2159fa58b5f66202e06f25446f0aeb60cb716ffa6d4Chris Lattner 2169fa58b5f66202e06f25446f0aeb60cb716ffa6d4Chris Lattner // If NewBBDominatesDestBB, then NewBB dominates DestBB, otherwise it 2179fa58b5f66202e06f25446f0aeb60cb716ffa6d4Chris Lattner // doesn't dominate anything. 2189fa58b5f66202e06f25446f0aeb60cb716ffa6d4Chris Lattner if (NewBBDominatesDestBB) 2199fa58b5f66202e06f25446f0aeb60cb716ffa6d4Chris Lattner ID->setImmediateDominator(DestBB, NewBB); 22086f7b2100c7b6b426869178327e352d122056f73Chris Lattner } 221c178d9459a0e659bedbc1b3c79459ee168453376Chris Lattner } 2222d43519454dbcf17054835ded19b031f66e31670Owen Anderson 223c178d9459a0e659bedbc1b3c79459ee168453376Chris Lattner // Should we update DominatorTree information? 224e802a023d98b06307831cd122e61da86431e8dacChris Lattner if (DominatorTree *DT = P->getAnalysisToUpdate<DominatorTree>()) { 225c178d9459a0e659bedbc1b3c79459ee168453376Chris Lattner DominatorTree::Node *TINode = DT->getNode(TIBB); 226fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 227c178d9459a0e659bedbc1b3c79459ee168453376Chris Lattner // The new block is not the immediate dominator for any other nodes, but 228c178d9459a0e659bedbc1b3c79459ee168453376Chris Lattner // TINode is the immediate dominator for the new node. 229c178d9459a0e659bedbc1b3c79459ee168453376Chris Lattner // 23086f7b2100c7b6b426869178327e352d122056f73Chris Lattner if (TINode) { // Don't break unreachable code! 23186f7b2100c7b6b426869178327e352d122056f73Chris Lattner DominatorTree::Node *NewBBNode = DT->createNewNode(NewBB, TINode); 23286f7b2100c7b6b426869178327e352d122056f73Chris Lattner DominatorTree::Node *DestBBNode = 0; 23386f7b2100c7b6b426869178327e352d122056f73Chris Lattner 23486f7b2100c7b6b426869178327e352d122056f73Chris Lattner // If NewBBDominatesDestBB hasn't been computed yet, do so with DT. 23586f7b2100c7b6b426869178327e352d122056f73Chris Lattner if (!OtherPreds.empty()) { 23686f7b2100c7b6b426869178327e352d122056f73Chris Lattner DestBBNode = DT->getNode(DestBB); 23786f7b2100c7b6b426869178327e352d122056f73Chris Lattner while (!OtherPreds.empty() && NewBBDominatesDestBB) { 23886f7b2100c7b6b426869178327e352d122056f73Chris Lattner if (DominatorTree::Node *OPNode = DT->getNode(OtherPreds.back())) 23986f7b2100c7b6b426869178327e352d122056f73Chris Lattner NewBBDominatesDestBB = DestBBNode->dominates(OPNode); 24086f7b2100c7b6b426869178327e352d122056f73Chris Lattner OtherPreds.pop_back(); 24186f7b2100c7b6b426869178327e352d122056f73Chris Lattner } 24286f7b2100c7b6b426869178327e352d122056f73Chris Lattner OtherPreds.clear(); 24386f7b2100c7b6b426869178327e352d122056f73Chris Lattner } 24486f7b2100c7b6b426869178327e352d122056f73Chris Lattner 24586f7b2100c7b6b426869178327e352d122056f73Chris Lattner // If NewBBDominatesDestBB, then NewBB dominates DestBB, otherwise it 24686f7b2100c7b6b426869178327e352d122056f73Chris Lattner // doesn't dominate anything. 24786f7b2100c7b6b426869178327e352d122056f73Chris Lattner if (NewBBDominatesDestBB) { 24886f7b2100c7b6b426869178327e352d122056f73Chris Lattner if (!DestBBNode) DestBBNode = DT->getNode(DestBB); 24986f7b2100c7b6b426869178327e352d122056f73Chris Lattner DT->changeImmediateDominator(DestBBNode, NewBBNode); 25086f7b2100c7b6b426869178327e352d122056f73Chris Lattner } 25186f7b2100c7b6b426869178327e352d122056f73Chris Lattner } 252eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner } 2536918c079a1393be8ae551d699479fbfa39b99277Chris Lattner 2546918c079a1393be8ae551d699479fbfa39b99277Chris Lattner // Should we update DominanceFrontier information? 2556918c079a1393be8ae551d699479fbfa39b99277Chris Lattner if (DominanceFrontier *DF = P->getAnalysisToUpdate<DominanceFrontier>()) { 25686f7b2100c7b6b426869178327e352d122056f73Chris Lattner // If NewBBDominatesDestBB hasn't been computed yet, do so with DF. 25786f7b2100c7b6b426869178327e352d122056f73Chris Lattner if (!OtherPreds.empty()) { 25886f7b2100c7b6b426869178327e352d122056f73Chris Lattner // FIXME: IMPLEMENT THIS! 2593a15503c82a804fcca47b5490e8fb42735ca4131Chris Lattner assert(0 && "Requiring domfrontiers but not idom/domtree/domset." 2603a15503c82a804fcca47b5490e8fb42735ca4131Chris Lattner " not implemented yet!"); 26186f7b2100c7b6b426869178327e352d122056f73Chris Lattner } 26286f7b2100c7b6b426869178327e352d122056f73Chris Lattner 2636918c079a1393be8ae551d699479fbfa39b99277Chris Lattner // Since the new block is dominated by its only predecessor TIBB, 26486f7b2100c7b6b426869178327e352d122056f73Chris Lattner // it cannot be in any block's dominance frontier. If NewBB dominates 26586f7b2100c7b6b426869178327e352d122056f73Chris Lattner // DestBB, its dominance frontier is the same as DestBB's, otherwise it is 26686f7b2100c7b6b426869178327e352d122056f73Chris Lattner // just {DestBB}. 2676918c079a1393be8ae551d699479fbfa39b99277Chris Lattner DominanceFrontier::DomSetType NewDFSet; 26886f7b2100c7b6b426869178327e352d122056f73Chris Lattner if (NewBBDominatesDestBB) { 26986f7b2100c7b6b426869178327e352d122056f73Chris Lattner DominanceFrontier::iterator I = DF->find(DestBB); 27086f7b2100c7b6b426869178327e352d122056f73Chris Lattner if (I != DF->end()) 27186f7b2100c7b6b426869178327e352d122056f73Chris Lattner DF->addBasicBlock(NewBB, I->second); 27286f7b2100c7b6b426869178327e352d122056f73Chris Lattner else 27386f7b2100c7b6b426869178327e352d122056f73Chris Lattner DF->addBasicBlock(NewBB, DominanceFrontier::DomSetType()); 27486f7b2100c7b6b426869178327e352d122056f73Chris Lattner } else { 27586f7b2100c7b6b426869178327e352d122056f73Chris Lattner DominanceFrontier::DomSetType NewDFSet; 27686f7b2100c7b6b426869178327e352d122056f73Chris Lattner NewDFSet.insert(DestBB); 27786f7b2100c7b6b426869178327e352d122056f73Chris Lattner DF->addBasicBlock(NewBB, NewDFSet); 27886f7b2100c7b6b426869178327e352d122056f73Chris Lattner } 2796918c079a1393be8ae551d699479fbfa39b99277Chris Lattner } 2800ae380a8ac48cbf3131f96318a15dc5dae8a6c78Chris Lattner 2810ae380a8ac48cbf3131f96318a15dc5dae8a6c78Chris Lattner // Update LoopInfo if it is around. 2820ae380a8ac48cbf3131f96318a15dc5dae8a6c78Chris Lattner if (LoopInfo *LI = P->getAnalysisToUpdate<LoopInfo>()) { 2830ae380a8ac48cbf3131f96318a15dc5dae8a6c78Chris Lattner // If one or the other blocks were not in a loop, the new block is not 2840ae380a8ac48cbf3131f96318a15dc5dae8a6c78Chris Lattner // either, and thus LI doesn't need to be updated. 2850ae380a8ac48cbf3131f96318a15dc5dae8a6c78Chris Lattner if (Loop *TIL = LI->getLoopFor(TIBB)) 2860ae380a8ac48cbf3131f96318a15dc5dae8a6c78Chris Lattner if (Loop *DestLoop = LI->getLoopFor(DestBB)) { 2870ae380a8ac48cbf3131f96318a15dc5dae8a6c78Chris Lattner if (TIL == DestLoop) { 2880ae380a8ac48cbf3131f96318a15dc5dae8a6c78Chris Lattner // Both in the same loop, the NewBB joins loop. 2890ae380a8ac48cbf3131f96318a15dc5dae8a6c78Chris Lattner DestLoop->addBasicBlockToLoop(NewBB, *LI); 2900ae380a8ac48cbf3131f96318a15dc5dae8a6c78Chris Lattner } else if (TIL->contains(DestLoop->getHeader())) { 29186f7b2100c7b6b426869178327e352d122056f73Chris Lattner // Edge from an outer loop to an inner loop. Add to the outer loop. 2920ae380a8ac48cbf3131f96318a15dc5dae8a6c78Chris Lattner TIL->addBasicBlockToLoop(NewBB, *LI); 2930ae380a8ac48cbf3131f96318a15dc5dae8a6c78Chris Lattner } else if (DestLoop->contains(TIL->getHeader())) { 29486f7b2100c7b6b426869178327e352d122056f73Chris Lattner // Edge from an inner loop to an outer loop. Add to the outer loop. 2950ae380a8ac48cbf3131f96318a15dc5dae8a6c78Chris Lattner DestLoop->addBasicBlockToLoop(NewBB, *LI); 2960ae380a8ac48cbf3131f96318a15dc5dae8a6c78Chris Lattner } else { 2970ae380a8ac48cbf3131f96318a15dc5dae8a6c78Chris Lattner // Edge from two loops with no containment relation. Because these 2980ae380a8ac48cbf3131f96318a15dc5dae8a6c78Chris Lattner // are natural loops, we know that the destination block must be the 2990ae380a8ac48cbf3131f96318a15dc5dae8a6c78Chris Lattner // header of its loop (adding a branch into a loop elsewhere would 3000ae380a8ac48cbf3131f96318a15dc5dae8a6c78Chris Lattner // create an irreducible loop). 3010ae380a8ac48cbf3131f96318a15dc5dae8a6c78Chris Lattner assert(DestLoop->getHeader() == DestBB && 3020ae380a8ac48cbf3131f96318a15dc5dae8a6c78Chris Lattner "Should not create irreducible loops!"); 3030ae380a8ac48cbf3131f96318a15dc5dae8a6c78Chris Lattner if (Loop *P = DestLoop->getParentLoop()) 3040ae380a8ac48cbf3131f96318a15dc5dae8a6c78Chris Lattner P->addBasicBlockToLoop(NewBB, *LI); 3050ae380a8ac48cbf3131f96318a15dc5dae8a6c78Chris Lattner } 3060ae380a8ac48cbf3131f96318a15dc5dae8a6c78Chris Lattner } 3070ae380a8ac48cbf3131f96318a15dc5dae8a6c78Chris Lattner } 308d23520cd9403c3c6fe8e7ea974ae0b593772345cChris Lattner return true; 309eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner} 310