BreakCriticalEdges.cpp revision fd93908ae8b9684fe71c239e3c6cfe13ff6a2663
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 19d76efa018660e806cd87c0a24512e3c532fc1d36Chris Lattner#include "llvm/Transforms/Scalar.h" 20d23520cd9403c3c6fe8e7ea974ae0b593772345cChris Lattner#include "llvm/Transforms/Utils/BasicBlockUtils.h" 21d76efa018660e806cd87c0a24512e3c532fc1d36Chris Lattner#include "llvm/Analysis/Dominators.h" 22d76efa018660e806cd87c0a24512e3c532fc1d36Chris Lattner#include "llvm/Function.h" 2347b14a4a6a455c7be169cfd312fcbe796f0ad426Misha Brukman#include "llvm/Instructions.h" 245b3a4553c1da7e417a240379e2f510c77532c5c1Chris Lattner#include "llvm/Type.h" 25eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner#include "llvm/Support/CFG.h" 26551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/ADT/Statistic.h" 27f7703df4968084c18c248c1feea9961c19a32e6aChris Lattnerusing namespace llvm; 28d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 296de302bbdb0ac8a595ca35a06e5bbc1605e1da3eChris Lattnernamespace { 30a92f696b74a99325026ebbdbffd2a44317e0c10bChris Lattner Statistic<> NumBroken("break-crit-edges", "Number of blocks inserted"); 316de302bbdb0ac8a595ca35a06e5bbc1605e1da3eChris Lattner 326de302bbdb0ac8a595ca35a06e5bbc1605e1da3eChris Lattner struct BreakCriticalEdges : public FunctionPass { 336de302bbdb0ac8a595ca35a06e5bbc1605e1da3eChris Lattner virtual bool runOnFunction(Function &F); 34fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 356de302bbdb0ac8a595ca35a06e5bbc1605e1da3eChris Lattner virtual void getAnalysisUsage(AnalysisUsage &AU) const { 366de302bbdb0ac8a595ca35a06e5bbc1605e1da3eChris Lattner AU.addPreserved<DominatorSet>(); 376de302bbdb0ac8a595ca35a06e5bbc1605e1da3eChris Lattner AU.addPreserved<ImmediateDominators>(); 386de302bbdb0ac8a595ca35a06e5bbc1605e1da3eChris Lattner AU.addPreserved<DominatorTree>(); 396918c079a1393be8ae551d699479fbfa39b99277Chris Lattner AU.addPreserved<DominanceFrontier>(); 4098bf436e2e2ab463d79c54a42a46b12028905330Chris Lattner 4198bf436e2e2ab463d79c54a42a46b12028905330Chris Lattner // No loop canonicalization guarantees are broken by this pass. 4298bf436e2e2ab463d79c54a42a46b12028905330Chris Lattner AU.addPreservedID(LoopSimplifyID); 436de302bbdb0ac8a595ca35a06e5bbc1605e1da3eChris Lattner } 446de302bbdb0ac8a595ca35a06e5bbc1605e1da3eChris Lattner }; 456de302bbdb0ac8a595ca35a06e5bbc1605e1da3eChris Lattner 466de302bbdb0ac8a595ca35a06e5bbc1605e1da3eChris Lattner RegisterOpt<BreakCriticalEdges> X("break-crit-edges", 476de302bbdb0ac8a595ca35a06e5bbc1605e1da3eChris Lattner "Break critical edges in CFG"); 486de302bbdb0ac8a595ca35a06e5bbc1605e1da3eChris Lattner} 49d76efa018660e806cd87c0a24512e3c532fc1d36Chris Lattner 50eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner// Publically exposed interface to pass... 51f7703df4968084c18c248c1feea9961c19a32e6aChris Lattnerconst PassInfo *llvm::BreakCriticalEdgesID = X.getPassInfo(); 521e5fdf8ba0453baafe062525dc8472846da3ec1fChris LattnerFunctionPass *llvm::createBreakCriticalEdgesPass() { 531e5fdf8ba0453baafe062525dc8472846da3ec1fChris Lattner return new BreakCriticalEdges(); 541e5fdf8ba0453baafe062525dc8472846da3ec1fChris Lattner} 55d76efa018660e806cd87c0a24512e3c532fc1d36Chris Lattner 56363ca610d1186c34f25ecad00e8dea61cc91b36aChris Lattner// runOnFunction - Loop over all of the edges in the CFG, breaking critical 57363ca610d1186c34f25ecad00e8dea61cc91b36aChris Lattner// edges as they are found. 58363ca610d1186c34f25ecad00e8dea61cc91b36aChris Lattner// 59363ca610d1186c34f25ecad00e8dea61cc91b36aChris Lattnerbool BreakCriticalEdges::runOnFunction(Function &F) { 60363ca610d1186c34f25ecad00e8dea61cc91b36aChris Lattner bool Changed = false; 61363ca610d1186c34f25ecad00e8dea61cc91b36aChris Lattner for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I) { 62363ca610d1186c34f25ecad00e8dea61cc91b36aChris Lattner TerminatorInst *TI = I->getTerminator(); 63363ca610d1186c34f25ecad00e8dea61cc91b36aChris Lattner if (TI->getNumSuccessors() > 1) 64363ca610d1186c34f25ecad00e8dea61cc91b36aChris Lattner for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i) 65363ca610d1186c34f25ecad00e8dea61cc91b36aChris Lattner if (SplitCriticalEdge(TI, i, this)) { 66363ca610d1186c34f25ecad00e8dea61cc91b36aChris Lattner ++NumBroken; 67363ca610d1186c34f25ecad00e8dea61cc91b36aChris Lattner Changed = true; 68363ca610d1186c34f25ecad00e8dea61cc91b36aChris Lattner } 69363ca610d1186c34f25ecad00e8dea61cc91b36aChris Lattner } 70363ca610d1186c34f25ecad00e8dea61cc91b36aChris Lattner 71363ca610d1186c34f25ecad00e8dea61cc91b36aChris Lattner return Changed; 72363ca610d1186c34f25ecad00e8dea61cc91b36aChris Lattner} 73363ca610d1186c34f25ecad00e8dea61cc91b36aChris Lattner 74363ca610d1186c34f25ecad00e8dea61cc91b36aChris Lattner//===----------------------------------------------------------------------===// 75363ca610d1186c34f25ecad00e8dea61cc91b36aChris Lattner// Implementation of the external critical edge manipulation functions 76363ca610d1186c34f25ecad00e8dea61cc91b36aChris Lattner//===----------------------------------------------------------------------===// 77eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner 78eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner// isCriticalEdge - Return true if the specified edge is a critical edge. 79eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner// Critical edges are edges from a block with multiple successors to a block 80eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner// with multiple predecessors. 81eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner// 82f7703df4968084c18c248c1feea9961c19a32e6aChris Lattnerbool llvm::isCriticalEdge(const TerminatorInst *TI, unsigned SuccNum) { 83eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner assert(SuccNum < TI->getNumSuccessors() && "Illegal edge specification!"); 84e802a023d98b06307831cd122e61da86431e8dacChris Lattner if (TI->getNumSuccessors() == 1) return false; 85eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner 86eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner const BasicBlock *Dest = TI->getSuccessor(SuccNum); 87eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner pred_const_iterator I = pred_begin(Dest), E = pred_end(Dest); 88eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner 89eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner // If there is more than one predecessor, this is a critical edge... 90eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner assert(I != E && "No preds, but we have an edge to the block?"); 91eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner ++I; // Skip one edge due to the incoming arc from TI. 92eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner return I != E; 93eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner} 94eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner 95d23520cd9403c3c6fe8e7ea974ae0b593772345cChris Lattner// SplitCriticalEdge - If this edge is a critical edge, insert a new node to 96d23520cd9403c3c6fe8e7ea974ae0b593772345cChris Lattner// split the critical edge. This will update DominatorSet, ImmediateDominator, 97d23520cd9403c3c6fe8e7ea974ae0b593772345cChris Lattner// DominatorTree, and DominatorFrontier information if it is available, thus 98d23520cd9403c3c6fe8e7ea974ae0b593772345cChris Lattner// calling this pass will not invalidate either of them. This returns true if 99d23520cd9403c3c6fe8e7ea974ae0b593772345cChris Lattner// the edge was split, false otherwise. 100eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner// 101f7703df4968084c18c248c1feea9961c19a32e6aChris Lattnerbool llvm::SplitCriticalEdge(TerminatorInst *TI, unsigned SuccNum, Pass *P) { 102d23520cd9403c3c6fe8e7ea974ae0b593772345cChris Lattner if (!isCriticalEdge(TI, SuccNum)) return false; 103eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner BasicBlock *TIBB = TI->getParent(); 1046918c079a1393be8ae551d699479fbfa39b99277Chris Lattner BasicBlock *DestBB = TI->getSuccessor(SuccNum); 105eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner 106eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner // Create a new basic block, linking it into the CFG. 1076918c079a1393be8ae551d699479fbfa39b99277Chris Lattner BasicBlock *NewBB = new BasicBlock(TIBB->getName() + "." + 1086918c079a1393be8ae551d699479fbfa39b99277Chris Lattner DestBB->getName() + "_crit_edge"); 109eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner // Create our unconditional branch... 110108e4ab159b59a616b0868e396dc7ddc1fb48616Chris Lattner new BranchInst(DestBB, NewBB); 111fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 112eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner // Branch to the new block, breaking the edge... 113eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner TI->setSuccessor(SuccNum, NewBB); 114eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner 115eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner // Insert the block into the function... right after the block TI lives in. 116eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner Function &F = *TIBB->getParent(); 117eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner F.getBasicBlockList().insert(TIBB->getNext(), NewBB); 118eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner 119eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner // If there are any PHI nodes in DestBB, we need to update them so that they 120eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner // merge incoming values from NewBB instead of from TIBB. 121eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner // 1222da5c3dda6f5b9c4ec6d55008d33327764364bd4Reid Spencer for (BasicBlock::iterator I = DestBB->begin(); isa<PHINode>(I); ++I) { 1232da5c3dda6f5b9c4ec6d55008d33327764364bd4Reid Spencer PHINode *PN = cast<PHINode>(I); 12406887c9a2ad0d30c3cdfeff4d5e268a634c9d1a6Chris Lattner // We no longer enter through TIBB, now we come in through NewBB. Revector 12506887c9a2ad0d30c3cdfeff4d5e268a634c9d1a6Chris Lattner // exactly one entry in the PHI node that used to come from TIBB to come 12606887c9a2ad0d30c3cdfeff4d5e268a634c9d1a6Chris Lattner // from NewBB. 12706887c9a2ad0d30c3cdfeff4d5e268a634c9d1a6Chris Lattner Value *InVal = PN->removeIncomingValue(TIBB, false); 12806887c9a2ad0d30c3cdfeff4d5e268a634c9d1a6Chris Lattner PN->addIncoming(InVal, NewBB); 129eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner } 130eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner 131e802a023d98b06307831cd122e61da86431e8dacChris Lattner // If we don't have a pass object, we can't update anything... 132d23520cd9403c3c6fe8e7ea974ae0b593772345cChris Lattner if (P == 0) return true; 133e802a023d98b06307831cd122e61da86431e8dacChris Lattner 134c178d9459a0e659bedbc1b3c79459ee168453376Chris Lattner // Now update analysis information. These are the analyses that we are 135c178d9459a0e659bedbc1b3c79459ee168453376Chris Lattner // currently capable of updating... 136eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner // 137eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner 138c178d9459a0e659bedbc1b3c79459ee168453376Chris Lattner // Should we update DominatorSet information? 139e802a023d98b06307831cd122e61da86431e8dacChris Lattner if (DominatorSet *DS = P->getAnalysisToUpdate<DominatorSet>()) { 140c178d9459a0e659bedbc1b3c79459ee168453376Chris Lattner // The blocks that dominate the new one are the blocks that dominate TIBB 141c178d9459a0e659bedbc1b3c79459ee168453376Chris Lattner // plus the new block itself. 142c178d9459a0e659bedbc1b3c79459ee168453376Chris Lattner DominatorSet::DomSetType DomSet = DS->getDominators(TIBB); 143c178d9459a0e659bedbc1b3c79459ee168453376Chris Lattner DomSet.insert(NewBB); // A block always dominates itself. 144c178d9459a0e659bedbc1b3c79459ee168453376Chris Lattner DS->addBasicBlock(NewBB, DomSet); 145c178d9459a0e659bedbc1b3c79459ee168453376Chris Lattner } 146eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner 147cf00c4ab3ba308d45d98c5ccab87362cf802facbMisha Brukman // Should we update ImmediateDominator information? 148e802a023d98b06307831cd122e61da86431e8dacChris Lattner if (ImmediateDominators *ID = P->getAnalysisToUpdate<ImmediateDominators>()) { 149c178d9459a0e659bedbc1b3c79459ee168453376Chris Lattner // TIBB is the new immediate dominator for NewBB. NewBB doesn't dominate 150c178d9459a0e659bedbc1b3c79459ee168453376Chris Lattner // anything. 151c178d9459a0e659bedbc1b3c79459ee168453376Chris Lattner ID->addNewBlock(NewBB, TIBB); 152c178d9459a0e659bedbc1b3c79459ee168453376Chris Lattner } 153fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 154c178d9459a0e659bedbc1b3c79459ee168453376Chris Lattner // Should we update DominatorTree information? 155e802a023d98b06307831cd122e61da86431e8dacChris Lattner if (DominatorTree *DT = P->getAnalysisToUpdate<DominatorTree>()) { 156c178d9459a0e659bedbc1b3c79459ee168453376Chris Lattner DominatorTree::Node *TINode = DT->getNode(TIBB); 157fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 158c178d9459a0e659bedbc1b3c79459ee168453376Chris Lattner // The new block is not the immediate dominator for any other nodes, but 159c178d9459a0e659bedbc1b3c79459ee168453376Chris Lattner // TINode is the immediate dominator for the new node. 160c178d9459a0e659bedbc1b3c79459ee168453376Chris Lattner // 161d3d06a5cd80a718a640e26350954197fb133800aChris Lattner if (TINode) // Don't break unreachable code! 162d3d06a5cd80a718a640e26350954197fb133800aChris Lattner DT->createNewNode(NewBB, TINode); 163eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner } 1646918c079a1393be8ae551d699479fbfa39b99277Chris Lattner 1656918c079a1393be8ae551d699479fbfa39b99277Chris Lattner // Should we update DominanceFrontier information? 1666918c079a1393be8ae551d699479fbfa39b99277Chris Lattner if (DominanceFrontier *DF = P->getAnalysisToUpdate<DominanceFrontier>()) { 1676918c079a1393be8ae551d699479fbfa39b99277Chris Lattner // Since the new block is dominated by its only predecessor TIBB, 1686918c079a1393be8ae551d699479fbfa39b99277Chris Lattner // it cannot be in any block's dominance frontier. Its dominance 1696918c079a1393be8ae551d699479fbfa39b99277Chris Lattner // frontier is {DestBB}. 1706918c079a1393be8ae551d699479fbfa39b99277Chris Lattner DominanceFrontier::DomSetType NewDFSet; 1716918c079a1393be8ae551d699479fbfa39b99277Chris Lattner NewDFSet.insert(DestBB); 1726918c079a1393be8ae551d699479fbfa39b99277Chris Lattner DF->addBasicBlock(NewBB, NewDFSet); 1736918c079a1393be8ae551d699479fbfa39b99277Chris Lattner } 174d23520cd9403c3c6fe8e7ea974ae0b593772345cChris Lattner return true; 175eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner} 176