Dominators.cpp revision 7ed54a0ece41faeaac4eec1a1e39789a64c1876e
14c9df7c619ba827729490757dae6dc35bb068a9fChris Lattner//===- Dominators.cpp - Dominator Calculation -----------------------------===// 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//===----------------------------------------------------------------------===// 91715229db9c04e73ba8acb8579eb2b9465209785Chris Lattner// 104c9df7c619ba827729490757dae6dc35bb068a9fChris Lattner// This file implements simple dominator construction algorithms for finding 114c9df7c619ba827729490757dae6dc35bb068a9fChris Lattner// forward dominators. Postdominators are available in libanalysis, but are not 124c9df7c619ba827729490757dae6dc35bb068a9fChris Lattner// included in libvmcore, because it's not needed. Forward dominators are 134c9df7c619ba827729490757dae6dc35bb068a9fChris Lattner// needed to support the Verifier pass. 141715229db9c04e73ba8acb8579eb2b9465209785Chris Lattner// 151715229db9c04e73ba8acb8579eb2b9465209785Chris Lattner//===----------------------------------------------------------------------===// 161715229db9c04e73ba8acb8579eb2b9465209785Chris Lattner 171715229db9c04e73ba8acb8579eb2b9465209785Chris Lattner#include "llvm/Analysis/Dominators.h" 18221d688a5ef21a22c2368c9fff0e92d7966c95e5Chris Lattner#include "llvm/Support/CFG.h" 19a59cbb2043c08f3cfb8fb379f0d336e21e070be8Chris Lattner#include "llvm/Assembly/Writer.h" 20551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/ADT/DepthFirstIterator.h" 21551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/ADT/SetOperations.h" 222ad28e6c486f91d83b2d5bcd30612049a686ad64Devang Patel#include "llvm/ADT/SmallPtrSet.h" 23b9dbc4deccefc062a29bce49dc60bf9d5627e603Devang Patel#include "llvm/Instructions.h" 2479b48b8bc07170656e7e2d7500f7fcbf69ccc923Devang Patel#include "llvm/Support/Streams.h" 258e72749fc0b44ac8b7a5ffbb275f2ad60f2fa41eChris Lattner#include <algorithm> 2631f8499e83dc4dccbb57ea7e76d1fd49b7010d0cChris Lattnerusing namespace llvm; 27d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 283dc6776b338f81e2d47daa42cc12c9f91053043dOwen Andersonnamespace llvm { 293dc6776b338f81e2d47daa42cc12c9f91053043dOwen Andersonstatic std::ostream &operator<<(std::ostream &o, 303dc6776b338f81e2d47daa42cc12c9f91053043dOwen Anderson const std::set<BasicBlock*> &BBs) { 313dc6776b338f81e2d47daa42cc12c9f91053043dOwen Anderson for (std::set<BasicBlock*>::const_iterator I = BBs.begin(), E = BBs.end(); 323dc6776b338f81e2d47daa42cc12c9f91053043dOwen Anderson I != E; ++I) 333dc6776b338f81e2d47daa42cc12c9f91053043dOwen Anderson if (*I) 343dc6776b338f81e2d47daa42cc12c9f91053043dOwen Anderson WriteAsOperand(o, *I, false); 353dc6776b338f81e2d47daa42cc12c9f91053043dOwen Anderson else 363dc6776b338f81e2d47daa42cc12c9f91053043dOwen Anderson o << " <<exit node>>"; 373dc6776b338f81e2d47daa42cc12c9f91053043dOwen Anderson return o; 383dc6776b338f81e2d47daa42cc12c9f91053043dOwen Anderson} 393dc6776b338f81e2d47daa42cc12c9f91053043dOwen Anderson} 403dc6776b338f81e2d47daa42cc12c9f91053043dOwen Anderson 4194108ab8a36806d5c7fb56bed4ddffda064f5c5dChris Lattner//===----------------------------------------------------------------------===// 423dc6776b338f81e2d47daa42cc12c9f91053043dOwen Anderson// DominatorTree Implementation 4316addf87bf331645de63575aa15627c74b9cab66Chris Lattner//===----------------------------------------------------------------------===// 4416addf87bf331645de63575aa15627c74b9cab66Chris Lattner// 453dc6776b338f81e2d47daa42cc12c9f91053043dOwen Anderson// DominatorTree construction - This pass constructs immediate dominator 4616addf87bf331645de63575aa15627c74b9cab66Chris Lattner// information for a flow-graph based on the algorithm described in this 4716addf87bf331645de63575aa15627c74b9cab66Chris Lattner// document: 4816addf87bf331645de63575aa15627c74b9cab66Chris Lattner// 4916addf87bf331645de63575aa15627c74b9cab66Chris Lattner// A Fast Algorithm for Finding Dominators in a Flowgraph 5016addf87bf331645de63575aa15627c74b9cab66Chris Lattner// T. Lengauer & R. Tarjan, ACM TOPLAS July 1979, pgs 121-141. 5116addf87bf331645de63575aa15627c74b9cab66Chris Lattner// 5216addf87bf331645de63575aa15627c74b9cab66Chris Lattner// This implements both the O(n*ack(n)) and the O(n*log(n)) versions of EVAL and 5316addf87bf331645de63575aa15627c74b9cab66Chris Lattner// LINK, but it turns out that the theoretically slower O(n*log(n)) 5416addf87bf331645de63575aa15627c74b9cab66Chris Lattner// implementation is actually faster than the "efficient" algorithm (even for 5516addf87bf331645de63575aa15627c74b9cab66Chris Lattner// large CFGs) because the constant overheads are substantially smaller. The 5616addf87bf331645de63575aa15627c74b9cab66Chris Lattner// lower-complexity version can be enabled with the following #define: 5716addf87bf331645de63575aa15627c74b9cab66Chris Lattner// 5816addf87bf331645de63575aa15627c74b9cab66Chris Lattner#define BALANCE_IDOM_TREE 0 5916addf87bf331645de63575aa15627c74b9cab66Chris Lattner// 6016addf87bf331645de63575aa15627c74b9cab66Chris Lattner//===----------------------------------------------------------------------===// 6116addf87bf331645de63575aa15627c74b9cab66Chris Lattner 621997473cf72957d0e70322e2fe6fe2ab141c58a6Devang Patelchar DominatorTree::ID = 0; 633dc6776b338f81e2d47daa42cc12c9f91053043dOwen Andersonstatic RegisterPass<DominatorTree> 643dc6776b338f81e2d47daa42cc12c9f91053043dOwen AndersonE("domtree", "Dominator Tree Construction", true); 6516addf87bf331645de63575aa15627c74b9cab66Chris Lattner 660e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel// NewBB is split and now it has one successor. Update dominator tree to 670e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel// reflect this change. 680e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patelvoid DominatorTree::splitBlock(BasicBlock *NewBB) { 690e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel assert(NewBB->getTerminator()->getNumSuccessors() == 1 700e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel && "NewBB should have a single successor!"); 710e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel BasicBlock *NewBBSucc = NewBB->getTerminator()->getSuccessor(0); 720e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel 730e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel std::vector<BasicBlock*> PredBlocks; 740e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel for (pred_iterator PI = pred_begin(NewBB), PE = pred_end(NewBB); 750e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel PI != PE; ++PI) 760e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel PredBlocks.push_back(*PI); 770e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel 780e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel assert(!PredBlocks.empty() && "No predblocks??"); 790e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel 800e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel // The newly inserted basic block will dominate existing basic blocks iff the 810e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel // PredBlocks dominate all of the non-pred blocks. If all predblocks dominate 820e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel // the non-pred blocks, then they all must be the same block! 830e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel // 840e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel bool NewBBDominatesNewBBSucc = true; 850e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel { 860e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel BasicBlock *OnePred = PredBlocks[0]; 870e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel unsigned i = 1, e = PredBlocks.size(); 880e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel for (i = 1; !isReachableFromEntry(OnePred); ++i) { 890e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel assert(i != e && "Didn't find reachable pred?"); 900e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel OnePred = PredBlocks[i]; 910e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel } 920e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel 930e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel for (; i != e; ++i) 947ed54a0ece41faeaac4eec1a1e39789a64c1876eChris Lattner if (PredBlocks[i] != OnePred && isReachableFromEntry(OnePred)) { 950e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel NewBBDominatesNewBBSucc = false; 960e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel break; 970e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel } 980e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel 990e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel if (NewBBDominatesNewBBSucc) 1000e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel for (pred_iterator PI = pred_begin(NewBBSucc), E = pred_end(NewBBSucc); 1010e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel PI != E; ++PI) 1020e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel if (*PI != NewBB && !dominates(NewBBSucc, *PI)) { 1030e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel NewBBDominatesNewBBSucc = false; 1040e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel break; 1050e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel } 1060e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel } 1070e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel 1080e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel // The other scenario where the new block can dominate its successors are when 1090e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel // all predecessors of NewBBSucc that are not NewBB are dominated by NewBBSucc 1100e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel // already. 1110e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel if (!NewBBDominatesNewBBSucc) { 1120e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel NewBBDominatesNewBBSucc = true; 1130e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel for (pred_iterator PI = pred_begin(NewBBSucc), E = pred_end(NewBBSucc); 1140e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel PI != E; ++PI) 1150e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel if (*PI != NewBB && !dominates(NewBBSucc, *PI)) { 1160e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel NewBBDominatesNewBBSucc = false; 1170e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel break; 1180e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel } 1190e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel } 1200e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel 121a31965301da89a7d0c829bded72c6b0da0303c54Chris Lattner // Find NewBB's immediate dominator and create new dominator tree node for 122a31965301da89a7d0c829bded72c6b0da0303c54Chris Lattner // NewBB. 1230e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel BasicBlock *NewBBIDom = 0; 1240e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel unsigned i = 0; 1250e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel for (i = 0; i < PredBlocks.size(); ++i) 1260e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel if (isReachableFromEntry(PredBlocks[i])) { 1270e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel NewBBIDom = PredBlocks[i]; 1280e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel break; 1290e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel } 1300e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel assert(i != PredBlocks.size() && "No reachable preds?"); 1310e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel for (i = i + 1; i < PredBlocks.size(); ++i) { 1320e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel if (isReachableFromEntry(PredBlocks[i])) 1330e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel NewBBIDom = findNearestCommonDominator(NewBBIDom, PredBlocks[i]); 1340e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel } 1350e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel assert(NewBBIDom && "No immediate dominator found??"); 1360e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel 1370e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel // Create the new dominator tree node... and set the idom of NewBB. 1380e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel DomTreeNode *NewBBNode = addNewBlock(NewBB, NewBBIDom); 1390e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel 1400e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel // If NewBB strictly dominates other blocks, then it is now the immediate 1410e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel // dominator of NewBBSucc. Update the dominator tree as appropriate. 1420e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel if (NewBBDominatesNewBBSucc) { 1430e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel DomTreeNode *NewBBSuccNode = getNode(NewBBSucc); 1440e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel changeImmediateDominator(NewBBSuccNode, NewBBNode); 1450e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel } 1460e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel} 1470e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel 148e93e31198109b03b8c22296a1500839e95d59b5fChris Lattnerunsigned DominatorTree::DFSPass(BasicBlock *V, unsigned N) { 149a9f120bd9f208f8e7ed03c02cc63b2f487edb84fChris Lattner // This is more understandable as a recursive algorithm, but we can't use the 150a9f120bd9f208f8e7ed03c02cc63b2f487edb84fChris Lattner // recursive algorithm due to stack depth issues. Keep it here for 151a9f120bd9f208f8e7ed03c02cc63b2f487edb84fChris Lattner // documentation purposes. 152a9f120bd9f208f8e7ed03c02cc63b2f487edb84fChris Lattner#if 0 153e93e31198109b03b8c22296a1500839e95d59b5fChris Lattner InfoRec &VInfo = Info[Roots[i]]; 15416addf87bf331645de63575aa15627c74b9cab66Chris Lattner VInfo.Semi = ++N; 15516addf87bf331645de63575aa15627c74b9cab66Chris Lattner VInfo.Label = V; 15616addf87bf331645de63575aa15627c74b9cab66Chris Lattner 15716addf87bf331645de63575aa15627c74b9cab66Chris Lattner Vertex.push_back(V); // Vertex[n] = V; 15816addf87bf331645de63575aa15627c74b9cab66Chris Lattner //Info[V].Ancestor = 0; // Ancestor[n] = 0 159a9f120bd9f208f8e7ed03c02cc63b2f487edb84fChris Lattner //Info[V].Child = 0; // Child[v] = 0 16016addf87bf331645de63575aa15627c74b9cab66Chris Lattner VInfo.Size = 1; // Size[v] = 1 16116addf87bf331645de63575aa15627c74b9cab66Chris Lattner 16216addf87bf331645de63575aa15627c74b9cab66Chris Lattner for (succ_iterator SI = succ_begin(V), E = succ_end(V); SI != E; ++SI) { 16316addf87bf331645de63575aa15627c74b9cab66Chris Lattner InfoRec &SuccVInfo = Info[*SI]; 16416addf87bf331645de63575aa15627c74b9cab66Chris Lattner if (SuccVInfo.Semi == 0) { 16516addf87bf331645de63575aa15627c74b9cab66Chris Lattner SuccVInfo.Parent = V; 166e93e31198109b03b8c22296a1500839e95d59b5fChris Lattner N = DFSPass(*SI, N); 16716addf87bf331645de63575aa15627c74b9cab66Chris Lattner } 16816addf87bf331645de63575aa15627c74b9cab66Chris Lattner } 169a9f120bd9f208f8e7ed03c02cc63b2f487edb84fChris Lattner#else 170a9f120bd9f208f8e7ed03c02cc63b2f487edb84fChris Lattner std::vector<std::pair<BasicBlock*, unsigned> > Worklist; 171a9f120bd9f208f8e7ed03c02cc63b2f487edb84fChris Lattner Worklist.push_back(std::make_pair(V, 0U)); 172a9f120bd9f208f8e7ed03c02cc63b2f487edb84fChris Lattner while (!Worklist.empty()) { 173a9f120bd9f208f8e7ed03c02cc63b2f487edb84fChris Lattner BasicBlock *BB = Worklist.back().first; 174a9f120bd9f208f8e7ed03c02cc63b2f487edb84fChris Lattner unsigned NextSucc = Worklist.back().second; 175a9f120bd9f208f8e7ed03c02cc63b2f487edb84fChris Lattner 176a9f120bd9f208f8e7ed03c02cc63b2f487edb84fChris Lattner // First time we visited this BB? 177a9f120bd9f208f8e7ed03c02cc63b2f487edb84fChris Lattner if (NextSucc == 0) { 178a9f120bd9f208f8e7ed03c02cc63b2f487edb84fChris Lattner InfoRec &BBInfo = Info[BB]; 179a9f120bd9f208f8e7ed03c02cc63b2f487edb84fChris Lattner BBInfo.Semi = ++N; 180a9f120bd9f208f8e7ed03c02cc63b2f487edb84fChris Lattner BBInfo.Label = BB; 181a9f120bd9f208f8e7ed03c02cc63b2f487edb84fChris Lattner 182a9f120bd9f208f8e7ed03c02cc63b2f487edb84fChris Lattner Vertex.push_back(BB); // Vertex[n] = V; 183a9f120bd9f208f8e7ed03c02cc63b2f487edb84fChris Lattner //BBInfo[V].Ancestor = 0; // Ancestor[n] = 0 184a9f120bd9f208f8e7ed03c02cc63b2f487edb84fChris Lattner //BBInfo[V].Child = 0; // Child[v] = 0 185a9f120bd9f208f8e7ed03c02cc63b2f487edb84fChris Lattner BBInfo.Size = 1; // Size[v] = 1 186a9f120bd9f208f8e7ed03c02cc63b2f487edb84fChris Lattner } 187a9f120bd9f208f8e7ed03c02cc63b2f487edb84fChris Lattner 188a9f120bd9f208f8e7ed03c02cc63b2f487edb84fChris Lattner // If we are done with this block, remove it from the worklist. 189a9f120bd9f208f8e7ed03c02cc63b2f487edb84fChris Lattner if (NextSucc == BB->getTerminator()->getNumSuccessors()) { 190a9f120bd9f208f8e7ed03c02cc63b2f487edb84fChris Lattner Worklist.pop_back(); 191a9f120bd9f208f8e7ed03c02cc63b2f487edb84fChris Lattner continue; 192a9f120bd9f208f8e7ed03c02cc63b2f487edb84fChris Lattner } 193a9f120bd9f208f8e7ed03c02cc63b2f487edb84fChris Lattner 194a9f120bd9f208f8e7ed03c02cc63b2f487edb84fChris Lattner // Otherwise, increment the successor number for the next time we get to it. 195a9f120bd9f208f8e7ed03c02cc63b2f487edb84fChris Lattner ++Worklist.back().second; 196a9f120bd9f208f8e7ed03c02cc63b2f487edb84fChris Lattner 197a9f120bd9f208f8e7ed03c02cc63b2f487edb84fChris Lattner // Visit the successor next, if it isn't already visited. 198a9f120bd9f208f8e7ed03c02cc63b2f487edb84fChris Lattner BasicBlock *Succ = BB->getTerminator()->getSuccessor(NextSucc); 199a9f120bd9f208f8e7ed03c02cc63b2f487edb84fChris Lattner 200a9f120bd9f208f8e7ed03c02cc63b2f487edb84fChris Lattner InfoRec &SuccVInfo = Info[Succ]; 201a9f120bd9f208f8e7ed03c02cc63b2f487edb84fChris Lattner if (SuccVInfo.Semi == 0) { 202a9f120bd9f208f8e7ed03c02cc63b2f487edb84fChris Lattner SuccVInfo.Parent = BB; 203a9f120bd9f208f8e7ed03c02cc63b2f487edb84fChris Lattner Worklist.push_back(std::make_pair(Succ, 0U)); 204a9f120bd9f208f8e7ed03c02cc63b2f487edb84fChris Lattner } 205a9f120bd9f208f8e7ed03c02cc63b2f487edb84fChris Lattner } 206a9f120bd9f208f8e7ed03c02cc63b2f487edb84fChris Lattner#endif 20716addf87bf331645de63575aa15627c74b9cab66Chris Lattner return N; 20816addf87bf331645de63575aa15627c74b9cab66Chris Lattner} 20916addf87bf331645de63575aa15627c74b9cab66Chris Lattner 21099c282453af9353ab1be42604414e8f4de338477Devang Patelvoid DominatorTree::Compress(BasicBlock *VIn) { 21116addf87bf331645de63575aa15627c74b9cab66Chris Lattner 21299c282453af9353ab1be42604414e8f4de338477Devang Patel std::vector<BasicBlock *> Work; 2132f0d1ea864ff0fe59c5a2b35390a82fad2865b61Chris Lattner SmallPtrSet<BasicBlock *, 32> Visited; 2140a5f83c22cc5d1fe24e57aadde9399fa90eb5c98Chris Lattner BasicBlock *VInAncestor = Info[VIn].Ancestor; 21599c282453af9353ab1be42604414e8f4de338477Devang Patel InfoRec &VInVAInfo = Info[VInAncestor]; 21616addf87bf331645de63575aa15627c74b9cab66Chris Lattner 21799c282453af9353ab1be42604414e8f4de338477Devang Patel if (VInVAInfo.Ancestor != 0) 21899c282453af9353ab1be42604414e8f4de338477Devang Patel Work.push_back(VIn); 21999c282453af9353ab1be42604414e8f4de338477Devang Patel 22099c282453af9353ab1be42604414e8f4de338477Devang Patel while (!Work.empty()) { 22199c282453af9353ab1be42604414e8f4de338477Devang Patel BasicBlock *V = Work.back(); 22299c282453af9353ab1be42604414e8f4de338477Devang Patel InfoRec &VInfo = Info[V]; 22399c282453af9353ab1be42604414e8f4de338477Devang Patel BasicBlock *VAncestor = VInfo.Ancestor; 22499c282453af9353ab1be42604414e8f4de338477Devang Patel InfoRec &VAInfo = Info[VAncestor]; 22599c282453af9353ab1be42604414e8f4de338477Devang Patel 22699c282453af9353ab1be42604414e8f4de338477Devang Patel // Process Ancestor first 2272f0d1ea864ff0fe59c5a2b35390a82fad2865b61Chris Lattner if (Visited.insert(VAncestor) && 2282f0d1ea864ff0fe59c5a2b35390a82fad2865b61Chris Lattner VAInfo.Ancestor != 0) { 22999c282453af9353ab1be42604414e8f4de338477Devang Patel Work.push_back(VAncestor); 23099c282453af9353ab1be42604414e8f4de338477Devang Patel continue; 23199c282453af9353ab1be42604414e8f4de338477Devang Patel } 23299c282453af9353ab1be42604414e8f4de338477Devang Patel Work.pop_back(); 23316addf87bf331645de63575aa15627c74b9cab66Chris Lattner 2340a5f83c22cc5d1fe24e57aadde9399fa90eb5c98Chris Lattner // Update VInfo based on Ancestor info 23599c282453af9353ab1be42604414e8f4de338477Devang Patel if (VAInfo.Ancestor == 0) 23699c282453af9353ab1be42604414e8f4de338477Devang Patel continue; 23799c282453af9353ab1be42604414e8f4de338477Devang Patel BasicBlock *VAncestorLabel = VAInfo.Label; 23899c282453af9353ab1be42604414e8f4de338477Devang Patel BasicBlock *VLabel = VInfo.Label; 23999c282453af9353ab1be42604414e8f4de338477Devang Patel if (Info[VAncestorLabel].Semi < Info[VLabel].Semi) 24099c282453af9353ab1be42604414e8f4de338477Devang Patel VInfo.Label = VAncestorLabel; 24199c282453af9353ab1be42604414e8f4de338477Devang Patel VInfo.Ancestor = VAInfo.Ancestor; 24299c282453af9353ab1be42604414e8f4de338477Devang Patel } 24316addf87bf331645de63575aa15627c74b9cab66Chris Lattner} 24416addf87bf331645de63575aa15627c74b9cab66Chris Lattner 2453dc6776b338f81e2d47daa42cc12c9f91053043dOwen AndersonBasicBlock *DominatorTree::Eval(BasicBlock *V) { 24616addf87bf331645de63575aa15627c74b9cab66Chris Lattner InfoRec &VInfo = Info[V]; 24716addf87bf331645de63575aa15627c74b9cab66Chris Lattner#if !BALANCE_IDOM_TREE 24816addf87bf331645de63575aa15627c74b9cab66Chris Lattner // Higher-complexity but faster implementation 24916addf87bf331645de63575aa15627c74b9cab66Chris Lattner if (VInfo.Ancestor == 0) 25016addf87bf331645de63575aa15627c74b9cab66Chris Lattner return V; 25199c282453af9353ab1be42604414e8f4de338477Devang Patel Compress(V); 25216addf87bf331645de63575aa15627c74b9cab66Chris Lattner return VInfo.Label; 25316addf87bf331645de63575aa15627c74b9cab66Chris Lattner#else 25416addf87bf331645de63575aa15627c74b9cab66Chris Lattner // Lower-complexity but slower implementation 25516addf87bf331645de63575aa15627c74b9cab66Chris Lattner if (VInfo.Ancestor == 0) 25616addf87bf331645de63575aa15627c74b9cab66Chris Lattner return VInfo.Label; 25799c282453af9353ab1be42604414e8f4de338477Devang Patel Compress(V); 25816addf87bf331645de63575aa15627c74b9cab66Chris Lattner BasicBlock *VLabel = VInfo.Label; 25916addf87bf331645de63575aa15627c74b9cab66Chris Lattner 26016addf87bf331645de63575aa15627c74b9cab66Chris Lattner BasicBlock *VAncestorLabel = Info[VInfo.Ancestor].Label; 26116addf87bf331645de63575aa15627c74b9cab66Chris Lattner if (Info[VAncestorLabel].Semi >= Info[VLabel].Semi) 26216addf87bf331645de63575aa15627c74b9cab66Chris Lattner return VLabel; 26316addf87bf331645de63575aa15627c74b9cab66Chris Lattner else 26416addf87bf331645de63575aa15627c74b9cab66Chris Lattner return VAncestorLabel; 26516addf87bf331645de63575aa15627c74b9cab66Chris Lattner#endif 26616addf87bf331645de63575aa15627c74b9cab66Chris Lattner} 26716addf87bf331645de63575aa15627c74b9cab66Chris Lattner 2683dc6776b338f81e2d47daa42cc12c9f91053043dOwen Andersonvoid DominatorTree::Link(BasicBlock *V, BasicBlock *W, InfoRec &WInfo){ 26916addf87bf331645de63575aa15627c74b9cab66Chris Lattner#if !BALANCE_IDOM_TREE 27016addf87bf331645de63575aa15627c74b9cab66Chris Lattner // Higher-complexity but faster implementation 27116addf87bf331645de63575aa15627c74b9cab66Chris Lattner WInfo.Ancestor = V; 27216addf87bf331645de63575aa15627c74b9cab66Chris Lattner#else 27316addf87bf331645de63575aa15627c74b9cab66Chris Lattner // Lower-complexity but slower implementation 27416addf87bf331645de63575aa15627c74b9cab66Chris Lattner BasicBlock *WLabel = WInfo.Label; 27516addf87bf331645de63575aa15627c74b9cab66Chris Lattner unsigned WLabelSemi = Info[WLabel].Semi; 27616addf87bf331645de63575aa15627c74b9cab66Chris Lattner BasicBlock *S = W; 27716addf87bf331645de63575aa15627c74b9cab66Chris Lattner InfoRec *SInfo = &Info[S]; 278fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 27916addf87bf331645de63575aa15627c74b9cab66Chris Lattner BasicBlock *SChild = SInfo->Child; 28016addf87bf331645de63575aa15627c74b9cab66Chris Lattner InfoRec *SChildInfo = &Info[SChild]; 281fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 28216addf87bf331645de63575aa15627c74b9cab66Chris Lattner while (WLabelSemi < Info[SChildInfo->Label].Semi) { 28316addf87bf331645de63575aa15627c74b9cab66Chris Lattner BasicBlock *SChildChild = SChildInfo->Child; 28416addf87bf331645de63575aa15627c74b9cab66Chris Lattner if (SInfo->Size+Info[SChildChild].Size >= 2*SChildInfo->Size) { 28516addf87bf331645de63575aa15627c74b9cab66Chris Lattner SChildInfo->Ancestor = S; 28616addf87bf331645de63575aa15627c74b9cab66Chris Lattner SInfo->Child = SChild = SChildChild; 28716addf87bf331645de63575aa15627c74b9cab66Chris Lattner SChildInfo = &Info[SChild]; 28816addf87bf331645de63575aa15627c74b9cab66Chris Lattner } else { 28916addf87bf331645de63575aa15627c74b9cab66Chris Lattner SChildInfo->Size = SInfo->Size; 29016addf87bf331645de63575aa15627c74b9cab66Chris Lattner S = SInfo->Ancestor = SChild; 29116addf87bf331645de63575aa15627c74b9cab66Chris Lattner SInfo = SChildInfo; 29216addf87bf331645de63575aa15627c74b9cab66Chris Lattner SChild = SChildChild; 29316addf87bf331645de63575aa15627c74b9cab66Chris Lattner SChildInfo = &Info[SChild]; 29416addf87bf331645de63575aa15627c74b9cab66Chris Lattner } 29516addf87bf331645de63575aa15627c74b9cab66Chris Lattner } 296fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 29716addf87bf331645de63575aa15627c74b9cab66Chris Lattner InfoRec &VInfo = Info[V]; 29816addf87bf331645de63575aa15627c74b9cab66Chris Lattner SInfo->Label = WLabel; 299fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 30016addf87bf331645de63575aa15627c74b9cab66Chris Lattner assert(V != W && "The optimization here will not work in this case!"); 30116addf87bf331645de63575aa15627c74b9cab66Chris Lattner unsigned WSize = WInfo.Size; 30216addf87bf331645de63575aa15627c74b9cab66Chris Lattner unsigned VSize = (VInfo.Size += WSize); 303fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 30416addf87bf331645de63575aa15627c74b9cab66Chris Lattner if (VSize < 2*WSize) 30516addf87bf331645de63575aa15627c74b9cab66Chris Lattner std::swap(S, VInfo.Child); 306fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 30716addf87bf331645de63575aa15627c74b9cab66Chris Lattner while (S) { 30816addf87bf331645de63575aa15627c74b9cab66Chris Lattner SInfo = &Info[S]; 30916addf87bf331645de63575aa15627c74b9cab66Chris Lattner SInfo->Ancestor = V; 31016addf87bf331645de63575aa15627c74b9cab66Chris Lattner S = SInfo->Child; 31116addf87bf331645de63575aa15627c74b9cab66Chris Lattner } 31216addf87bf331645de63575aa15627c74b9cab66Chris Lattner#endif 31316addf87bf331645de63575aa15627c74b9cab66Chris Lattner} 31416addf87bf331645de63575aa15627c74b9cab66Chris Lattner 315e93e31198109b03b8c22296a1500839e95d59b5fChris Lattnervoid DominatorTree::calculate(Function &F) { 316e934fefd6b6c83816e81bc86389cd593fb930773Owen Anderson BasicBlock* Root = Roots[0]; 3179a51157db555395f7a6ad89faec40b3afa121091Devang Patel 3189a51157db555395f7a6ad89faec40b3afa121091Devang Patel // Add a node for the root... 3194d42dea25397f2f822a93edfe9930b36ea85a7e7Devang Patel DomTreeNodes[Root] = RootNode = new DomTreeNode(Root, 0); 32016addf87bf331645de63575aa15627c74b9cab66Chris Lattner 32116addf87bf331645de63575aa15627c74b9cab66Chris Lattner Vertex.push_back(0); 322fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 32316addf87bf331645de63575aa15627c74b9cab66Chris Lattner // Step #1: Number blocks in depth-first order and initialize variables used 32416addf87bf331645de63575aa15627c74b9cab66Chris Lattner // in later stages of the algorithm. 325e93e31198109b03b8c22296a1500839e95d59b5fChris Lattner unsigned N = DFSPass(Root, 0); 32616addf87bf331645de63575aa15627c74b9cab66Chris Lattner 32716addf87bf331645de63575aa15627c74b9cab66Chris Lattner for (unsigned i = N; i >= 2; --i) { 32816addf87bf331645de63575aa15627c74b9cab66Chris Lattner BasicBlock *W = Vertex[i]; 32916addf87bf331645de63575aa15627c74b9cab66Chris Lattner InfoRec &WInfo = Info[W]; 33016addf87bf331645de63575aa15627c74b9cab66Chris Lattner 33116addf87bf331645de63575aa15627c74b9cab66Chris Lattner // Step #2: Calculate the semidominators of all vertices 33216addf87bf331645de63575aa15627c74b9cab66Chris Lattner for (pred_iterator PI = pred_begin(W), E = pred_end(W); PI != E; ++PI) 33316addf87bf331645de63575aa15627c74b9cab66Chris Lattner if (Info.count(*PI)) { // Only if this predecessor is reachable! 33416addf87bf331645de63575aa15627c74b9cab66Chris Lattner unsigned SemiU = Info[Eval(*PI)].Semi; 33516addf87bf331645de63575aa15627c74b9cab66Chris Lattner if (SemiU < WInfo.Semi) 33616addf87bf331645de63575aa15627c74b9cab66Chris Lattner WInfo.Semi = SemiU; 33716addf87bf331645de63575aa15627c74b9cab66Chris Lattner } 338fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 33916addf87bf331645de63575aa15627c74b9cab66Chris Lattner Info[Vertex[WInfo.Semi]].Bucket.push_back(W); 34016addf87bf331645de63575aa15627c74b9cab66Chris Lattner 34116addf87bf331645de63575aa15627c74b9cab66Chris Lattner BasicBlock *WParent = WInfo.Parent; 34216addf87bf331645de63575aa15627c74b9cab66Chris Lattner Link(WParent, W, WInfo); 34316addf87bf331645de63575aa15627c74b9cab66Chris Lattner 34416addf87bf331645de63575aa15627c74b9cab66Chris Lattner // Step #3: Implicitly define the immediate dominator of vertices 34516addf87bf331645de63575aa15627c74b9cab66Chris Lattner std::vector<BasicBlock*> &WParentBucket = Info[WParent].Bucket; 34616addf87bf331645de63575aa15627c74b9cab66Chris Lattner while (!WParentBucket.empty()) { 34716addf87bf331645de63575aa15627c74b9cab66Chris Lattner BasicBlock *V = WParentBucket.back(); 34816addf87bf331645de63575aa15627c74b9cab66Chris Lattner WParentBucket.pop_back(); 34916addf87bf331645de63575aa15627c74b9cab66Chris Lattner BasicBlock *U = Eval(V); 35016addf87bf331645de63575aa15627c74b9cab66Chris Lattner IDoms[V] = Info[U].Semi < Info[V].Semi ? U : WParent; 35116addf87bf331645de63575aa15627c74b9cab66Chris Lattner } 35216addf87bf331645de63575aa15627c74b9cab66Chris Lattner } 35316addf87bf331645de63575aa15627c74b9cab66Chris Lattner 35416addf87bf331645de63575aa15627c74b9cab66Chris Lattner // Step #4: Explicitly define the immediate dominator of each vertex 35516addf87bf331645de63575aa15627c74b9cab66Chris Lattner for (unsigned i = 2; i <= N; ++i) { 35616addf87bf331645de63575aa15627c74b9cab66Chris Lattner BasicBlock *W = Vertex[i]; 35716addf87bf331645de63575aa15627c74b9cab66Chris Lattner BasicBlock *&WIDom = IDoms[W]; 35816addf87bf331645de63575aa15627c74b9cab66Chris Lattner if (WIDom != Vertex[Info[W].Semi]) 35916addf87bf331645de63575aa15627c74b9cab66Chris Lattner WIDom = IDoms[WIDom]; 36016addf87bf331645de63575aa15627c74b9cab66Chris Lattner } 36116addf87bf331645de63575aa15627c74b9cab66Chris Lattner 3623dc6776b338f81e2d47daa42cc12c9f91053043dOwen Anderson // Loop over all of the reachable blocks in the function... 3633dc6776b338f81e2d47daa42cc12c9f91053043dOwen Anderson for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I) 3643dc6776b338f81e2d47daa42cc12c9f91053043dOwen Anderson if (BasicBlock *ImmDom = getIDom(I)) { // Reachable block. 3650a5f83c22cc5d1fe24e57aadde9399fa90eb5c98Chris Lattner DomTreeNode *BBNode = DomTreeNodes[I]; 3660a5f83c22cc5d1fe24e57aadde9399fa90eb5c98Chris Lattner if (BBNode) continue; // Haven't calculated this node yet? 3670a5f83c22cc5d1fe24e57aadde9399fa90eb5c98Chris Lattner 3680a5f83c22cc5d1fe24e57aadde9399fa90eb5c98Chris Lattner // Get or calculate the node for the immediate dominator 3690a5f83c22cc5d1fe24e57aadde9399fa90eb5c98Chris Lattner DomTreeNode *IDomNode = getNodeForBlock(ImmDom); 3700a5f83c22cc5d1fe24e57aadde9399fa90eb5c98Chris Lattner 3710a5f83c22cc5d1fe24e57aadde9399fa90eb5c98Chris Lattner // Add a new tree node for this BasicBlock, and link it as a child of 3720a5f83c22cc5d1fe24e57aadde9399fa90eb5c98Chris Lattner // IDomNode 3730a5f83c22cc5d1fe24e57aadde9399fa90eb5c98Chris Lattner DomTreeNode *C = new DomTreeNode(I, IDomNode); 3740a5f83c22cc5d1fe24e57aadde9399fa90eb5c98Chris Lattner DomTreeNodes[I] = IDomNode->addChild(C); 3753dc6776b338f81e2d47daa42cc12c9f91053043dOwen Anderson } 3763dc6776b338f81e2d47daa42cc12c9f91053043dOwen Anderson 37716addf87bf331645de63575aa15627c74b9cab66Chris Lattner // Free temporary memory used to construct idom's 37816addf87bf331645de63575aa15627c74b9cab66Chris Lattner Info.clear(); 379e934fefd6b6c83816e81bc86389cd593fb930773Owen Anderson IDoms.clear(); 38016addf87bf331645de63575aa15627c74b9cab66Chris Lattner std::vector<BasicBlock*>().swap(Vertex); 3819a51157db555395f7a6ad89faec40b3afa121091Devang Patel 3829a51157db555395f7a6ad89faec40b3afa121091Devang Patel updateDFSNumbers(); 3839a51157db555395f7a6ad89faec40b3afa121091Devang Patel} 3849a51157db555395f7a6ad89faec40b3afa121091Devang Patel 3850a5f83c22cc5d1fe24e57aadde9399fa90eb5c98Chris Lattnervoid DominatorTreeBase::updateDFSNumbers() { 3869a51157db555395f7a6ad89faec40b3afa121091Devang Patel int dfsnum = 0; 3879a51157db555395f7a6ad89faec40b3afa121091Devang Patel // Iterate over all nodes in depth first order. 3889a51157db555395f7a6ad89faec40b3afa121091Devang Patel for (unsigned i = 0, e = Roots.size(); i != e; ++i) 3899a51157db555395f7a6ad89faec40b3afa121091Devang Patel for (df_iterator<BasicBlock*> I = df_begin(Roots[i]), 3909a51157db555395f7a6ad89faec40b3afa121091Devang Patel E = df_end(Roots[i]); I != E; ++I) { 3917ed54a0ece41faeaac4eec1a1e39789a64c1876eChris Lattner if (DomTreeNode *BBNode = getNode(*I)) { 3923726b82a55a1864c2f9af86beaaeb2e1f3fbc99bDevang Patel if (!BBNode->getIDom()) 3933726b82a55a1864c2f9af86beaaeb2e1f3fbc99bDevang Patel BBNode->assignDFSNumber(dfsnum); 394dba2413b2ecf4e781f457036a2eb0f103192e90dDevang Patel } 3959a51157db555395f7a6ad89faec40b3afa121091Devang Patel } 3969a51157db555395f7a6ad89faec40b3afa121091Devang Patel SlowQueries = 0; 3979a51157db555395f7a6ad89faec40b3afa121091Devang Patel DFSInfoValid = true; 3986aba48338f67f08637b05f38005059f27aaf69bfChris Lattner} 3996aba48338f67f08637b05f38005059f27aaf69bfChris Lattner 400dba2413b2ecf4e781f457036a2eb0f103192e90dDevang Patel/// isReachableFromEntry - Return true if A is dominated by the entry 401dba2413b2ecf4e781f457036a2eb0f103192e90dDevang Patel/// block of the function containing it. 402dba2413b2ecf4e781f457036a2eb0f103192e90dDevang Patelconst bool DominatorTreeBase::isReachableFromEntry(BasicBlock* A) { 403d75405fe95660877f62064211e252c8c8c4c05eaDevang Patel assert (!isPostDominator() 404d75405fe95660877f62064211e252c8c8c4c05eaDevang Patel && "This is not implemented for post dominators"); 405dba2413b2ecf4e781f457036a2eb0f103192e90dDevang Patel return dominates(&A->getParent()->getEntryBlock(), A); 406dba2413b2ecf4e781f457036a2eb0f103192e90dDevang Patel} 407dba2413b2ecf4e781f457036a2eb0f103192e90dDevang Patel 408e029b2c36907a77c895e4d646c0e91f18a6dd162Devang Patel// dominates - Return true if A dominates B. THis performs the 409e029b2c36907a77c895e4d646c0e91f18a6dd162Devang Patel// special checks necessary if A and B are in the same basic block. 410e029b2c36907a77c895e4d646c0e91f18a6dd162Devang Patelbool DominatorTreeBase::dominates(Instruction *A, Instruction *B) { 411e029b2c36907a77c895e4d646c0e91f18a6dd162Devang Patel BasicBlock *BBA = A->getParent(), *BBB = B->getParent(); 412e029b2c36907a77c895e4d646c0e91f18a6dd162Devang Patel if (BBA != BBB) return dominates(BBA, BBB); 413e029b2c36907a77c895e4d646c0e91f18a6dd162Devang Patel 414e029b2c36907a77c895e4d646c0e91f18a6dd162Devang Patel // It is not possible to determine dominance between two PHI nodes 415e029b2c36907a77c895e4d646c0e91f18a6dd162Devang Patel // based on their ordering. 416e029b2c36907a77c895e4d646c0e91f18a6dd162Devang Patel if (isa<PHINode>(A) && isa<PHINode>(B)) 417e029b2c36907a77c895e4d646c0e91f18a6dd162Devang Patel return false; 418e029b2c36907a77c895e4d646c0e91f18a6dd162Devang Patel 419e029b2c36907a77c895e4d646c0e91f18a6dd162Devang Patel // Loop through the basic block until we find A or B. 420e029b2c36907a77c895e4d646c0e91f18a6dd162Devang Patel BasicBlock::iterator I = BBA->begin(); 421e029b2c36907a77c895e4d646c0e91f18a6dd162Devang Patel for (; &*I != A && &*I != B; ++I) /*empty*/; 422e029b2c36907a77c895e4d646c0e91f18a6dd162Devang Patel 423e029b2c36907a77c895e4d646c0e91f18a6dd162Devang Patel if(!IsPostDominators) { 424e029b2c36907a77c895e4d646c0e91f18a6dd162Devang Patel // A dominates B if it is found first in the basic block. 425e029b2c36907a77c895e4d646c0e91f18a6dd162Devang Patel return &*I == A; 426e029b2c36907a77c895e4d646c0e91f18a6dd162Devang Patel } else { 427e029b2c36907a77c895e4d646c0e91f18a6dd162Devang Patel // A post-dominates B if B is found first in the basic block. 428e029b2c36907a77c895e4d646c0e91f18a6dd162Devang Patel return &*I == B; 429e029b2c36907a77c895e4d646c0e91f18a6dd162Devang Patel } 430e029b2c36907a77c895e4d646c0e91f18a6dd162Devang Patel} 4319a51157db555395f7a6ad89faec40b3afa121091Devang Patel 432ce6ef112c4abb1f7fd64738c5760f48cddc9a4a5Chris Lattner// DominatorTreeBase::reset - Free all of the tree node memory. 4331715229db9c04e73ba8acb8579eb2b9465209785Chris Lattner// 434fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukmanvoid DominatorTreeBase::reset() { 43587f05a24160805b13bd68f1908589a193497f157Devang Patel for (DomTreeNodeMapType::iterator I = DomTreeNodes.begin(), 43687f05a24160805b13bd68f1908589a193497f157Devang Patel E = DomTreeNodes.end(); I != E; ++I) 4371715229db9c04e73ba8acb8579eb2b9465209785Chris Lattner delete I->second; 438bec7647f985d54d2be2100e3813b85267cf1fe49Devang Patel DomTreeNodes.clear(); 439e934fefd6b6c83816e81bc86389cd593fb930773Owen Anderson IDoms.clear(); 440e934fefd6b6c83816e81bc86389cd593fb930773Owen Anderson Roots.clear(); 4413831c553e33c100b84be8fa95228c315ac4fdc30Devang Patel Vertex.clear(); 442b884f597d62e8596df0b3856e9ca1b2496f81361Chris Lattner RootNode = 0; 4431715229db9c04e73ba8acb8579eb2b9465209785Chris Lattner} 4441715229db9c04e73ba8acb8579eb2b9465209785Chris Lattner 445fe7d4e50b8a34e660a8713da79613041987c19d6Devang Patel/// findNearestCommonDominator - Find nearest common dominator basic block 446fe7d4e50b8a34e660a8713da79613041987c19d6Devang Patel/// for basic block A and B. If there is no such block then return NULL. 44787f05a24160805b13bd68f1908589a193497f157Devang PatelBasicBlock *DominatorTreeBase::findNearestCommonDominator(BasicBlock *A, 44887f05a24160805b13bd68f1908589a193497f157Devang Patel BasicBlock *B) { 449fe7d4e50b8a34e660a8713da79613041987c19d6Devang Patel 45087f05a24160805b13bd68f1908589a193497f157Devang Patel assert (!isPostDominator() 45187f05a24160805b13bd68f1908589a193497f157Devang Patel && "This is not implemented for post dominators"); 45287f05a24160805b13bd68f1908589a193497f157Devang Patel assert (A->getParent() == B->getParent() 45387f05a24160805b13bd68f1908589a193497f157Devang Patel && "Two blocks are not in same function"); 454fe7d4e50b8a34e660a8713da79613041987c19d6Devang Patel 455fe7d4e50b8a34e660a8713da79613041987c19d6Devang Patel // If either A or B is a entry block then it is nearest common dominator. 456fe7d4e50b8a34e660a8713da79613041987c19d6Devang Patel BasicBlock &Entry = A->getParent()->getEntryBlock(); 457fe7d4e50b8a34e660a8713da79613041987c19d6Devang Patel if (A == &Entry || B == &Entry) 458fe7d4e50b8a34e660a8713da79613041987c19d6Devang Patel return &Entry; 459fe7d4e50b8a34e660a8713da79613041987c19d6Devang Patel 4605fd306bf0d75b8dde7e2ff5e42e15e96d5cdfcfeDevang Patel // If B dominates A then B is nearest common dominator. 4617ed54a0ece41faeaac4eec1a1e39789a64c1876eChris Lattner if (dominates(B, A)) 46287f05a24160805b13bd68f1908589a193497f157Devang Patel return B; 46387f05a24160805b13bd68f1908589a193497f157Devang Patel 4645fd306bf0d75b8dde7e2ff5e42e15e96d5cdfcfeDevang Patel // If A dominates B then A is nearest common dominator. 4657ed54a0ece41faeaac4eec1a1e39789a64c1876eChris Lattner if (dominates(A, B)) 46687f05a24160805b13bd68f1908589a193497f157Devang Patel return A; 46787f05a24160805b13bd68f1908589a193497f157Devang Patel 468de6e1320550bf3a6eb249155fcd14e9a0d84488eDevang Patel DomTreeNode *NodeA = getNode(A); 469de6e1320550bf3a6eb249155fcd14e9a0d84488eDevang Patel DomTreeNode *NodeB = getNode(B); 470de6e1320550bf3a6eb249155fcd14e9a0d84488eDevang Patel 471fe7d4e50b8a34e660a8713da79613041987c19d6Devang Patel // Collect NodeA dominators set. 472bdfa1f837cc760da560595b279c171cba8a75781Devang Patel SmallPtrSet<DomTreeNode*, 16> NodeADoms; 473fe7d4e50b8a34e660a8713da79613041987c19d6Devang Patel NodeADoms.insert(NodeA); 474fe7d4e50b8a34e660a8713da79613041987c19d6Devang Patel DomTreeNode *IDomA = NodeA->getIDom(); 4757ed54a0ece41faeaac4eec1a1e39789a64c1876eChris Lattner while (IDomA) { 476fe7d4e50b8a34e660a8713da79613041987c19d6Devang Patel NodeADoms.insert(IDomA); 477fe7d4e50b8a34e660a8713da79613041987c19d6Devang Patel IDomA = IDomA->getIDom(); 478fe7d4e50b8a34e660a8713da79613041987c19d6Devang Patel } 479fe7d4e50b8a34e660a8713da79613041987c19d6Devang Patel 480fe7d4e50b8a34e660a8713da79613041987c19d6Devang Patel // Walk NodeB immediate dominators chain and find common dominator node. 481fe7d4e50b8a34e660a8713da79613041987c19d6Devang Patel DomTreeNode *IDomB = NodeB->getIDom(); 482fe7d4e50b8a34e660a8713da79613041987c19d6Devang Patel while(IDomB) { 483fe7d4e50b8a34e660a8713da79613041987c19d6Devang Patel if (NodeADoms.count(IDomB) != 0) 484fe7d4e50b8a34e660a8713da79613041987c19d6Devang Patel return IDomB->getBlock(); 485fe7d4e50b8a34e660a8713da79613041987c19d6Devang Patel 486fe7d4e50b8a34e660a8713da79613041987c19d6Devang Patel IDomB = IDomB->getIDom(); 487fe7d4e50b8a34e660a8713da79613041987c19d6Devang Patel } 488fe7d4e50b8a34e660a8713da79613041987c19d6Devang Patel 489fe7d4e50b8a34e660a8713da79613041987c19d6Devang Patel return NULL; 490fe7d4e50b8a34e660a8713da79613041987c19d6Devang Patel} 491fe7d4e50b8a34e660a8713da79613041987c19d6Devang Patel 4923726b82a55a1864c2f9af86beaaeb2e1f3fbc99bDevang Patel/// assignDFSNumber - Assign In and Out numbers while walking dominator tree 4933726b82a55a1864c2f9af86beaaeb2e1f3fbc99bDevang Patel/// in dfs order. 4943726b82a55a1864c2f9af86beaaeb2e1f3fbc99bDevang Patelvoid DomTreeNode::assignDFSNumber(int num) { 4953726b82a55a1864c2f9af86beaaeb2e1f3fbc99bDevang Patel std::vector<DomTreeNode *> workStack; 4967ae8c4c810935625bcdbdf832a33ef4032bad906Chris Lattner SmallPtrSet<DomTreeNode *, 32> Visited; 4973726b82a55a1864c2f9af86beaaeb2e1f3fbc99bDevang Patel 4983726b82a55a1864c2f9af86beaaeb2e1f3fbc99bDevang Patel workStack.push_back(this); 4997ae8c4c810935625bcdbdf832a33ef4032bad906Chris Lattner Visited.insert(this); 5003726b82a55a1864c2f9af86beaaeb2e1f3fbc99bDevang Patel this->DFSNumIn = num++; 5013726b82a55a1864c2f9af86beaaeb2e1f3fbc99bDevang Patel 5023726b82a55a1864c2f9af86beaaeb2e1f3fbc99bDevang Patel while (!workStack.empty()) { 5033726b82a55a1864c2f9af86beaaeb2e1f3fbc99bDevang Patel DomTreeNode *Node = workStack.back(); 5043726b82a55a1864c2f9af86beaaeb2e1f3fbc99bDevang Patel 5053726b82a55a1864c2f9af86beaaeb2e1f3fbc99bDevang Patel bool visitChild = false; 5063726b82a55a1864c2f9af86beaaeb2e1f3fbc99bDevang Patel for (std::vector<DomTreeNode*>::iterator DI = Node->begin(), 5073726b82a55a1864c2f9af86beaaeb2e1f3fbc99bDevang Patel E = Node->end(); DI != E && !visitChild; ++DI) { 5083726b82a55a1864c2f9af86beaaeb2e1f3fbc99bDevang Patel DomTreeNode *Child = *DI; 5097ae8c4c810935625bcdbdf832a33ef4032bad906Chris Lattner if (!Visited.insert(Child)) 5107ae8c4c810935625bcdbdf832a33ef4032bad906Chris Lattner continue; 5117ae8c4c810935625bcdbdf832a33ef4032bad906Chris Lattner 5127ae8c4c810935625bcdbdf832a33ef4032bad906Chris Lattner visitChild = true; 5137ae8c4c810935625bcdbdf832a33ef4032bad906Chris Lattner Child->DFSNumIn = num++; 5147ae8c4c810935625bcdbdf832a33ef4032bad906Chris Lattner workStack.push_back(Child); 5153726b82a55a1864c2f9af86beaaeb2e1f3fbc99bDevang Patel } 5163726b82a55a1864c2f9af86beaaeb2e1f3fbc99bDevang Patel if (!visitChild) { 5173726b82a55a1864c2f9af86beaaeb2e1f3fbc99bDevang Patel // If we reach here means all children are visited 5183726b82a55a1864c2f9af86beaaeb2e1f3fbc99bDevang Patel Node->DFSNumOut = num++; 5193726b82a55a1864c2f9af86beaaeb2e1f3fbc99bDevang Patel workStack.pop_back(); 5203726b82a55a1864c2f9af86beaaeb2e1f3fbc99bDevang Patel } 5213726b82a55a1864c2f9af86beaaeb2e1f3fbc99bDevang Patel } 5223726b82a55a1864c2f9af86beaaeb2e1f3fbc99bDevang Patel} 5233726b82a55a1864c2f9af86beaaeb2e1f3fbc99bDevang Patel 52426042420d642e810f5cdfb2da6156b74aaf80945Devang Patelvoid DomTreeNode::setIDom(DomTreeNode *NewIDom) { 525d74472ed21b1ff6d75c8ae2f4f2885e019d0907dChris Lattner assert(IDom && "No immediate dominator?"); 526d74472ed21b1ff6d75c8ae2f4f2885e019d0907dChris Lattner if (IDom != NewIDom) { 527bec7647f985d54d2be2100e3813b85267cf1fe49Devang Patel std::vector<DomTreeNode*>::iterator I = 528d74472ed21b1ff6d75c8ae2f4f2885e019d0907dChris Lattner std::find(IDom->Children.begin(), IDom->Children.end(), this); 529d74472ed21b1ff6d75c8ae2f4f2885e019d0907dChris Lattner assert(I != IDom->Children.end() && 530d74472ed21b1ff6d75c8ae2f4f2885e019d0907dChris Lattner "Not in immediate dominator children set!"); 531d74472ed21b1ff6d75c8ae2f4f2885e019d0907dChris Lattner // I am no longer your child... 532d74472ed21b1ff6d75c8ae2f4f2885e019d0907dChris Lattner IDom->Children.erase(I); 533d74472ed21b1ff6d75c8ae2f4f2885e019d0907dChris Lattner 534d74472ed21b1ff6d75c8ae2f4f2885e019d0907dChris Lattner // Switch to new dominator 535d74472ed21b1ff6d75c8ae2f4f2885e019d0907dChris Lattner IDom = NewIDom; 536d74472ed21b1ff6d75c8ae2f4f2885e019d0907dChris Lattner IDom->Children.push_back(this); 537d74472ed21b1ff6d75c8ae2f4f2885e019d0907dChris Lattner } 538d74472ed21b1ff6d75c8ae2f4f2885e019d0907dChris Lattner} 539d74472ed21b1ff6d75c8ae2f4f2885e019d0907dChris Lattner 54026042420d642e810f5cdfb2da6156b74aaf80945Devang PatelDomTreeNode *DominatorTree::getNodeForBlock(BasicBlock *BB) { 5417ed54a0ece41faeaac4eec1a1e39789a64c1876eChris Lattner if (DomTreeNode *BBNode = DomTreeNodes[BB]) 5427ed54a0ece41faeaac4eec1a1e39789a64c1876eChris Lattner return BBNode; 54316addf87bf331645de63575aa15627c74b9cab66Chris Lattner 54416addf87bf331645de63575aa15627c74b9cab66Chris Lattner // Haven't calculated this node yet? Get or calculate the node for the 54516addf87bf331645de63575aa15627c74b9cab66Chris Lattner // immediate dominator. 5463dc6776b338f81e2d47daa42cc12c9f91053043dOwen Anderson BasicBlock *IDom = getIDom(BB); 547bec7647f985d54d2be2100e3813b85267cf1fe49Devang Patel DomTreeNode *IDomNode = getNodeForBlock(IDom); 548fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 54916addf87bf331645de63575aa15627c74b9cab66Chris Lattner // Add a new tree node for this BasicBlock, and link it as a child of 55016addf87bf331645de63575aa15627c74b9cab66Chris Lattner // IDomNode 5514d42dea25397f2f822a93edfe9930b36ea85a7e7Devang Patel DomTreeNode *C = new DomTreeNode(BB, IDomNode); 552a31965301da89a7d0c829bded72c6b0da0303c54Chris Lattner return DomTreeNodes[BB] = IDomNode->addChild(C); 55316addf87bf331645de63575aa15627c74b9cab66Chris Lattner} 554d74472ed21b1ff6d75c8ae2f4f2885e019d0907dChris Lattner 5557ed54a0ece41faeaac4eec1a1e39789a64c1876eChris Lattnerstatic std::ostream &operator<<(std::ostream &o, const DomTreeNode *Node) { 556c444a4228f31656f854d15eac671b450df557346Chris Lattner if (Node->getBlock()) 557c444a4228f31656f854d15eac671b450df557346Chris Lattner WriteAsOperand(o, Node->getBlock(), false); 558b884f597d62e8596df0b3856e9ca1b2496f81361Chris Lattner else 559b884f597d62e8596df0b3856e9ca1b2496f81361Chris Lattner o << " <<exit node>>"; 5607ed54a0ece41faeaac4eec1a1e39789a64c1876eChris Lattner 5617ed54a0ece41faeaac4eec1a1e39789a64c1876eChris Lattner o << " {" << Node->getDFSNumIn() << "," << Node->getDFSNumOut() << "}"; 5627ed54a0ece41faeaac4eec1a1e39789a64c1876eChris Lattner 563b884f597d62e8596df0b3856e9ca1b2496f81361Chris Lattner return o << "\n"; 564a59cbb2043c08f3cfb8fb379f0d336e21e070be8Chris Lattner} 565a59cbb2043c08f3cfb8fb379f0d336e21e070be8Chris Lattner 56626042420d642e810f5cdfb2da6156b74aaf80945Devang Patelstatic void PrintDomTree(const DomTreeNode *N, std::ostream &o, 567a59cbb2043c08f3cfb8fb379f0d336e21e070be8Chris Lattner unsigned Lev) { 568b884f597d62e8596df0b3856e9ca1b2496f81361Chris Lattner o << std::string(2*Lev, ' ') << "[" << Lev << "] " << N; 56926042420d642e810f5cdfb2da6156b74aaf80945Devang Patel for (DomTreeNode::const_iterator I = N->begin(), E = N->end(); 570b884f597d62e8596df0b3856e9ca1b2496f81361Chris Lattner I != E; ++I) 571a59cbb2043c08f3cfb8fb379f0d336e21e070be8Chris Lattner PrintDomTree(*I, o, Lev+1); 572a59cbb2043c08f3cfb8fb379f0d336e21e070be8Chris Lattner} 573a59cbb2043c08f3cfb8fb379f0d336e21e070be8Chris Lattner 574ce9653ce449f1409815547e1bf60abcd1332d2c9Reid Spencervoid DominatorTreeBase::print(std::ostream &o, const Module* ) const { 5757ed54a0ece41faeaac4eec1a1e39789a64c1876eChris Lattner o << "=============================--------------------------------\n"; 5767ed54a0ece41faeaac4eec1a1e39789a64c1876eChris Lattner o << "Inorder Dominator Tree: "; 5777ed54a0ece41faeaac4eec1a1e39789a64c1876eChris Lattner if (DFSInfoValid) 5787ed54a0ece41faeaac4eec1a1e39789a64c1876eChris Lattner o << "DFSNumbers invalid: " << SlowQueries << " slow queries."; 5797ed54a0ece41faeaac4eec1a1e39789a64c1876eChris Lattner o << "\n"; 5807ed54a0ece41faeaac4eec1a1e39789a64c1876eChris Lattner 581b884f597d62e8596df0b3856e9ca1b2496f81361Chris Lattner PrintDomTree(getRootNode(), o, 1); 582a59cbb2043c08f3cfb8fb379f0d336e21e070be8Chris Lattner} 5831715229db9c04e73ba8acb8579eb2b9465209785Chris Lattner 58479b48b8bc07170656e7e2d7500f7fcbf69ccc923Devang Patelvoid DominatorTreeBase::dump() { 5857ed54a0ece41faeaac4eec1a1e39789a64c1876eChris Lattner print(llvm::cerr); 58679b48b8bc07170656e7e2d7500f7fcbf69ccc923Devang Patel} 58779b48b8bc07170656e7e2d7500f7fcbf69ccc923Devang Patel 5883dc6776b338f81e2d47daa42cc12c9f91053043dOwen Andersonbool DominatorTree::runOnFunction(Function &F) { 5893dc6776b338f81e2d47daa42cc12c9f91053043dOwen Anderson reset(); // Reset from the last time we were run... 590e934fefd6b6c83816e81bc86389cd593fb930773Owen Anderson Roots.push_back(&F.getEntryBlock()); 5913dc6776b338f81e2d47daa42cc12c9f91053043dOwen Anderson calculate(F); 5923dc6776b338f81e2d47daa42cc12c9f91053043dOwen Anderson return false; 5933dc6776b338f81e2d47daa42cc12c9f91053043dOwen Anderson} 5941715229db9c04e73ba8acb8579eb2b9465209785Chris Lattner 5951715229db9c04e73ba8acb8579eb2b9465209785Chris Lattner//===----------------------------------------------------------------------===// 5961715229db9c04e73ba8acb8579eb2b9465209785Chris Lattner// DominanceFrontier Implementation 5971715229db9c04e73ba8acb8579eb2b9465209785Chris Lattner//===----------------------------------------------------------------------===// 5981715229db9c04e73ba8acb8579eb2b9465209785Chris Lattner 5991997473cf72957d0e70322e2fe6fe2ab141c58a6Devang Patelchar DominanceFrontier::ID = 0; 6005d8925c7c506a54ebdfb0bc93437ec9f602eaaa0Chris Lattnerstatic RegisterPass<DominanceFrontier> 60117689dfe241702cbbbd29cf1e4e4229444f3e9f3Chris LattnerG("domfrontier", "Dominance Frontier Construction", true); 60293193f806378e06092820c099e437886c7309b94Chris Lattner 6030e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel// NewBB is split and now it has one successor. Update dominace frontier to 6040e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel// reflect this change. 6050e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patelvoid DominanceFrontier::splitBlock(BasicBlock *NewBB) { 6060e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel assert(NewBB->getTerminator()->getNumSuccessors() == 1 6070e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel && "NewBB should have a single successor!"); 6080e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel BasicBlock *NewBBSucc = NewBB->getTerminator()->getSuccessor(0); 6090e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel 6100e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel std::vector<BasicBlock*> PredBlocks; 6110e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel for (pred_iterator PI = pred_begin(NewBB), PE = pred_end(NewBB); 6120e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel PI != PE; ++PI) 6130e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel PredBlocks.push_back(*PI); 6140e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel 615c61ce1ad091ad1faaca8d73447f53d43020ddffaDevang Patel if (PredBlocks.empty()) 616c61ce1ad091ad1faaca8d73447f53d43020ddffaDevang Patel // If NewBB does not have any predecessors then it is a entry block. 617c61ce1ad091ad1faaca8d73447f53d43020ddffaDevang Patel // In this case, NewBB and its successor NewBBSucc dominates all 618c61ce1ad091ad1faaca8d73447f53d43020ddffaDevang Patel // other blocks. 619c61ce1ad091ad1faaca8d73447f53d43020ddffaDevang Patel return; 6200e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel 6217ed54a0ece41faeaac4eec1a1e39789a64c1876eChris Lattner // NewBBSucc inherits original NewBB frontier. 6221ff61385c8feb655a1e70cc67999680cc93f0f67Devang Patel DominanceFrontier::iterator NewBBI = find(NewBB); 6231ff61385c8feb655a1e70cc67999680cc93f0f67Devang Patel if (NewBBI != end()) { 6241ff61385c8feb655a1e70cc67999680cc93f0f67Devang Patel DominanceFrontier::DomSetType NewBBSet = NewBBI->second; 6251ff61385c8feb655a1e70cc67999680cc93f0f67Devang Patel DominanceFrontier::DomSetType NewBBSuccSet; 6261ff61385c8feb655a1e70cc67999680cc93f0f67Devang Patel NewBBSuccSet.insert(NewBBSet.begin(), NewBBSet.end()); 6271ff61385c8feb655a1e70cc67999680cc93f0f67Devang Patel addBasicBlock(NewBBSucc, NewBBSuccSet); 6281ff61385c8feb655a1e70cc67999680cc93f0f67Devang Patel } 6291ff61385c8feb655a1e70cc67999680cc93f0f67Devang Patel 6300e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel // If NewBB dominates NewBBSucc, then DF(NewBB) is now going to be the 6310e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel // DF(PredBlocks[0]) without the stuff that the new block does not dominate 6320e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel // a predecessor of. 6337ed54a0ece41faeaac4eec1a1e39789a64c1876eChris Lattner DominatorTree &DT = getAnalysis<DominatorTree>(); 6347ed54a0ece41faeaac4eec1a1e39789a64c1876eChris Lattner if (DT.dominates(NewBB, NewBBSucc)) { 6350e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel DominanceFrontier::iterator DFI = find(PredBlocks[0]); 6360e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel if (DFI != end()) { 6370e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel DominanceFrontier::DomSetType Set = DFI->second; 6380e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel // Filter out stuff in Set that we do not dominate a predecessor of. 6390e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel for (DominanceFrontier::DomSetType::iterator SetI = Set.begin(), 6400e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel E = Set.end(); SetI != E;) { 6410e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel bool DominatesPred = false; 6420e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel for (pred_iterator PI = pred_begin(*SetI), E = pred_end(*SetI); 6430e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel PI != E; ++PI) 6440e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel if (DT.dominates(NewBB, *PI)) 6450e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel DominatesPred = true; 6460e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel if (!DominatesPred) 6470e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel Set.erase(SetI++); 6480e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel else 6490e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel ++SetI; 6500e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel } 651c61ce1ad091ad1faaca8d73447f53d43020ddffaDevang Patel 652c61ce1ad091ad1faaca8d73447f53d43020ddffaDevang Patel if (NewBBI != end()) { 653c61ce1ad091ad1faaca8d73447f53d43020ddffaDevang Patel DominanceFrontier::DomSetType NewBBSet = NewBBI->second; 654c61ce1ad091ad1faaca8d73447f53d43020ddffaDevang Patel NewBBSet.insert(Set.begin(), Set.end()); 655c61ce1ad091ad1faaca8d73447f53d43020ddffaDevang Patel } else 656c61ce1ad091ad1faaca8d73447f53d43020ddffaDevang Patel addBasicBlock(NewBB, Set); 6570e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel } 6580e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel 6590e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel } else { 6600e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel // DF(NewBB) is {NewBBSucc} because NewBB does not strictly dominate 6610e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel // NewBBSucc, but it does dominate itself (and there is an edge (NewBB -> 6620e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel // NewBBSucc)). NewBBSucc is the single successor of NewBB. 6630e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel DominanceFrontier::DomSetType NewDFSet; 6640e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel NewDFSet.insert(NewBBSucc); 6650e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel addBasicBlock(NewBB, NewDFSet); 6660e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel } 6670e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel 6680e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel // Now we must loop over all of the dominance frontiers in the function, 6690e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel // replacing occurrences of NewBBSucc with NewBB in some cases. All 6700e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel // blocks that dominate a block in PredBlocks and contained NewBBSucc in 6710e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel // their dominance frontier must be updated to contain NewBB instead. 6720e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel // 6730e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel for (Function::iterator FI = NewBB->getParent()->begin(), 6740e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel FE = NewBB->getParent()->end(); FI != FE; ++FI) { 6750e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel DominanceFrontier::iterator DFI = find(FI); 6760e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel if (DFI == end()) continue; // unreachable block. 6770e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel 6787ed54a0ece41faeaac4eec1a1e39789a64c1876eChris Lattner // Only consider nodes that have NewBBSucc in their dominator frontier. 6790e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel if (!DFI->second.count(NewBBSucc)) continue; 6800e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel 6817ed54a0ece41faeaac4eec1a1e39789a64c1876eChris Lattner // Verify whether this block dominates a block in predblocks. If not, do 6827ed54a0ece41faeaac4eec1a1e39789a64c1876eChris Lattner // not update it. 6830e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel bool BlockDominatesAny = false; 6840e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel for (std::vector<BasicBlock*>::const_iterator BI = PredBlocks.begin(), 6850e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel BE = PredBlocks.end(); BI != BE; ++BI) { 6860e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel if (DT.dominates(FI, *BI)) { 6870e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel BlockDominatesAny = true; 6880e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel break; 6890e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel } 6900e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel } 6910e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel 6927ed54a0ece41faeaac4eec1a1e39789a64c1876eChris Lattner if (!BlockDominatesAny) 6937ed54a0ece41faeaac4eec1a1e39789a64c1876eChris Lattner continue; 6947ed54a0ece41faeaac4eec1a1e39789a64c1876eChris Lattner 6957ed54a0ece41faeaac4eec1a1e39789a64c1876eChris Lattner // If NewBBSucc should not stay in our dominator frontier, remove it. 6967ed54a0ece41faeaac4eec1a1e39789a64c1876eChris Lattner // We remove it unless there is a predecessor of NewBBSucc that we 6977ed54a0ece41faeaac4eec1a1e39789a64c1876eChris Lattner // dominate, but we don't strictly dominate NewBBSucc. 6987ed54a0ece41faeaac4eec1a1e39789a64c1876eChris Lattner bool ShouldRemove = true; 6997ed54a0ece41faeaac4eec1a1e39789a64c1876eChris Lattner if ((BasicBlock*)FI == NewBBSucc || !DT.dominates(FI, NewBBSucc)) { 7007ed54a0ece41faeaac4eec1a1e39789a64c1876eChris Lattner // Okay, we know that PredDom does not strictly dominate NewBBSucc. 7017ed54a0ece41faeaac4eec1a1e39789a64c1876eChris Lattner // Check to see if it dominates any predecessors of NewBBSucc. 7027ed54a0ece41faeaac4eec1a1e39789a64c1876eChris Lattner for (pred_iterator PI = pred_begin(NewBBSucc), 7037ed54a0ece41faeaac4eec1a1e39789a64c1876eChris Lattner E = pred_end(NewBBSucc); PI != E; ++PI) 7047ed54a0ece41faeaac4eec1a1e39789a64c1876eChris Lattner if (DT.dominates(FI, *PI)) { 7057ed54a0ece41faeaac4eec1a1e39789a64c1876eChris Lattner ShouldRemove = false; 7067ed54a0ece41faeaac4eec1a1e39789a64c1876eChris Lattner break; 7077ed54a0ece41faeaac4eec1a1e39789a64c1876eChris Lattner } 7080e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel } 7097ed54a0ece41faeaac4eec1a1e39789a64c1876eChris Lattner 7107ed54a0ece41faeaac4eec1a1e39789a64c1876eChris Lattner if (ShouldRemove) 7117ed54a0ece41faeaac4eec1a1e39789a64c1876eChris Lattner removeFromFrontier(DFI, NewBBSucc); 7127ed54a0ece41faeaac4eec1a1e39789a64c1876eChris Lattner addToFrontier(DFI, NewBB); 7130e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel } 7140e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel} 7150e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel 7168645fb95243d0c5b23aa10c48226c84c7fc20f17Chris Lattnernamespace { 7178645fb95243d0c5b23aa10c48226c84c7fc20f17Chris Lattner class DFCalculateWorkObject { 7188645fb95243d0c5b23aa10c48226c84c7fc20f17Chris Lattner public: 7198645fb95243d0c5b23aa10c48226c84c7fc20f17Chris Lattner DFCalculateWorkObject(BasicBlock *B, BasicBlock *P, 72026042420d642e810f5cdfb2da6156b74aaf80945Devang Patel const DomTreeNode *N, 72126042420d642e810f5cdfb2da6156b74aaf80945Devang Patel const DomTreeNode *PN) 72226042420d642e810f5cdfb2da6156b74aaf80945Devang Patel : currentBB(B), parentBB(P), Node(N), parentNode(PN) {} 7238645fb95243d0c5b23aa10c48226c84c7fc20f17Chris Lattner BasicBlock *currentBB; 7248645fb95243d0c5b23aa10c48226c84c7fc20f17Chris Lattner BasicBlock *parentBB; 72526042420d642e810f5cdfb2da6156b74aaf80945Devang Patel const DomTreeNode *Node; 72626042420d642e810f5cdfb2da6156b74aaf80945Devang Patel const DomTreeNode *parentNode; 7278645fb95243d0c5b23aa10c48226c84c7fc20f17Chris Lattner }; 7288645fb95243d0c5b23aa10c48226c84c7fc20f17Chris Lattner} 7298645fb95243d0c5b23aa10c48226c84c7fc20f17Chris Lattner 7301b7f7dc4b45a900fae2e9b062d588a995935727aChris Lattnerconst DominanceFrontier::DomSetType & 731fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha BrukmanDominanceFrontier::calculate(const DominatorTree &DT, 73226042420d642e810f5cdfb2da6156b74aaf80945Devang Patel const DomTreeNode *Node) { 733c444a4228f31656f854d15eac671b450df557346Chris Lattner BasicBlock *BB = Node->getBlock(); 734cbdfb8a9d5e9159f8bbd9b20c9b979e45a4d943cDevang Patel DomSetType *Result = NULL; 735cbdfb8a9d5e9159f8bbd9b20c9b979e45a4d943cDevang Patel 7369be98dd9c01e41c126fa3da0d794bdbeb5665c11Devang Patel std::vector<DFCalculateWorkObject> workList; 7372ad28e6c486f91d83b2d5bcd30612049a686ad64Devang Patel SmallPtrSet<BasicBlock *, 32> visited; 738cbdfb8a9d5e9159f8bbd9b20c9b979e45a4d943cDevang Patel 7399be98dd9c01e41c126fa3da0d794bdbeb5665c11Devang Patel workList.push_back(DFCalculateWorkObject(BB, NULL, Node, NULL)); 740cbdfb8a9d5e9159f8bbd9b20c9b979e45a4d943cDevang Patel do { 7419be98dd9c01e41c126fa3da0d794bdbeb5665c11Devang Patel DFCalculateWorkObject *currentW = &workList.back(); 742cbdfb8a9d5e9159f8bbd9b20c9b979e45a4d943cDevang Patel assert (currentW && "Missing work object."); 743cbdfb8a9d5e9159f8bbd9b20c9b979e45a4d943cDevang Patel 744cbdfb8a9d5e9159f8bbd9b20c9b979e45a4d943cDevang Patel BasicBlock *currentBB = currentW->currentBB; 745cbdfb8a9d5e9159f8bbd9b20c9b979e45a4d943cDevang Patel BasicBlock *parentBB = currentW->parentBB; 74626042420d642e810f5cdfb2da6156b74aaf80945Devang Patel const DomTreeNode *currentNode = currentW->Node; 74726042420d642e810f5cdfb2da6156b74aaf80945Devang Patel const DomTreeNode *parentNode = currentW->parentNode; 748cbdfb8a9d5e9159f8bbd9b20c9b979e45a4d943cDevang Patel assert (currentBB && "Invalid work object. Missing current Basic Block"); 749cbdfb8a9d5e9159f8bbd9b20c9b979e45a4d943cDevang Patel assert (currentNode && "Invalid work object. Missing current Node"); 750cbdfb8a9d5e9159f8bbd9b20c9b979e45a4d943cDevang Patel DomSetType &S = Frontiers[currentBB]; 751cbdfb8a9d5e9159f8bbd9b20c9b979e45a4d943cDevang Patel 752cbdfb8a9d5e9159f8bbd9b20c9b979e45a4d943cDevang Patel // Visit each block only once. 753cbdfb8a9d5e9159f8bbd9b20c9b979e45a4d943cDevang Patel if (visited.count(currentBB) == 0) { 754cbdfb8a9d5e9159f8bbd9b20c9b979e45a4d943cDevang Patel visited.insert(currentBB); 755cbdfb8a9d5e9159f8bbd9b20c9b979e45a4d943cDevang Patel 756cbdfb8a9d5e9159f8bbd9b20c9b979e45a4d943cDevang Patel // Loop over CFG successors to calculate DFlocal[currentNode] 757cbdfb8a9d5e9159f8bbd9b20c9b979e45a4d943cDevang Patel for (succ_iterator SI = succ_begin(currentBB), SE = succ_end(currentBB); 758cbdfb8a9d5e9159f8bbd9b20c9b979e45a4d943cDevang Patel SI != SE; ++SI) { 759cbdfb8a9d5e9159f8bbd9b20c9b979e45a4d943cDevang Patel // Does Node immediately dominate this successor? 760cbdfb8a9d5e9159f8bbd9b20c9b979e45a4d943cDevang Patel if (DT[*SI]->getIDom() != currentNode) 761cbdfb8a9d5e9159f8bbd9b20c9b979e45a4d943cDevang Patel S.insert(*SI); 762cbdfb8a9d5e9159f8bbd9b20c9b979e45a4d943cDevang Patel } 763cbdfb8a9d5e9159f8bbd9b20c9b979e45a4d943cDevang Patel } 7641715229db9c04e73ba8acb8579eb2b9465209785Chris Lattner 765cbdfb8a9d5e9159f8bbd9b20c9b979e45a4d943cDevang Patel // At this point, S is DFlocal. Now we union in DFup's of our children... 766cbdfb8a9d5e9159f8bbd9b20c9b979e45a4d943cDevang Patel // Loop through and visit the nodes that Node immediately dominates (Node's 767cbdfb8a9d5e9159f8bbd9b20c9b979e45a4d943cDevang Patel // children in the IDomTree) 768cbdfb8a9d5e9159f8bbd9b20c9b979e45a4d943cDevang Patel bool visitChild = false; 76926042420d642e810f5cdfb2da6156b74aaf80945Devang Patel for (DomTreeNode::const_iterator NI = currentNode->begin(), 770cbdfb8a9d5e9159f8bbd9b20c9b979e45a4d943cDevang Patel NE = currentNode->end(); NI != NE; ++NI) { 77126042420d642e810f5cdfb2da6156b74aaf80945Devang Patel DomTreeNode *IDominee = *NI; 772cbdfb8a9d5e9159f8bbd9b20c9b979e45a4d943cDevang Patel BasicBlock *childBB = IDominee->getBlock(); 773cbdfb8a9d5e9159f8bbd9b20c9b979e45a4d943cDevang Patel if (visited.count(childBB) == 0) { 7748645fb95243d0c5b23aa10c48226c84c7fc20f17Chris Lattner workList.push_back(DFCalculateWorkObject(childBB, currentBB, 7758645fb95243d0c5b23aa10c48226c84c7fc20f17Chris Lattner IDominee, currentNode)); 776cbdfb8a9d5e9159f8bbd9b20c9b979e45a4d943cDevang Patel visitChild = true; 777cbdfb8a9d5e9159f8bbd9b20c9b979e45a4d943cDevang Patel } 778cbdfb8a9d5e9159f8bbd9b20c9b979e45a4d943cDevang Patel } 7791715229db9c04e73ba8acb8579eb2b9465209785Chris Lattner 780cbdfb8a9d5e9159f8bbd9b20c9b979e45a4d943cDevang Patel // If all children are visited or there is any child then pop this block 781cbdfb8a9d5e9159f8bbd9b20c9b979e45a4d943cDevang Patel // from the workList. 782cbdfb8a9d5e9159f8bbd9b20c9b979e45a4d943cDevang Patel if (!visitChild) { 783cbdfb8a9d5e9159f8bbd9b20c9b979e45a4d943cDevang Patel 784cbdfb8a9d5e9159f8bbd9b20c9b979e45a4d943cDevang Patel if (!parentBB) { 785cbdfb8a9d5e9159f8bbd9b20c9b979e45a4d943cDevang Patel Result = &S; 786cbdfb8a9d5e9159f8bbd9b20c9b979e45a4d943cDevang Patel break; 787cbdfb8a9d5e9159f8bbd9b20c9b979e45a4d943cDevang Patel } 788cbdfb8a9d5e9159f8bbd9b20c9b979e45a4d943cDevang Patel 789cbdfb8a9d5e9159f8bbd9b20c9b979e45a4d943cDevang Patel DomSetType::const_iterator CDFI = S.begin(), CDFE = S.end(); 790cbdfb8a9d5e9159f8bbd9b20c9b979e45a4d943cDevang Patel DomSetType &parentSet = Frontiers[parentBB]; 791cbdfb8a9d5e9159f8bbd9b20c9b979e45a4d943cDevang Patel for (; CDFI != CDFE; ++CDFI) { 7929a51157db555395f7a6ad89faec40b3afa121091Devang Patel if (!DT.properlyDominates(parentNode, DT[*CDFI])) 793cbdfb8a9d5e9159f8bbd9b20c9b979e45a4d943cDevang Patel parentSet.insert(*CDFI); 794cbdfb8a9d5e9159f8bbd9b20c9b979e45a4d943cDevang Patel } 795cbdfb8a9d5e9159f8bbd9b20c9b979e45a4d943cDevang Patel workList.pop_back(); 7961715229db9c04e73ba8acb8579eb2b9465209785Chris Lattner } 7971715229db9c04e73ba8acb8579eb2b9465209785Chris Lattner 798cbdfb8a9d5e9159f8bbd9b20c9b979e45a4d943cDevang Patel } while (!workList.empty()); 799cbdfb8a9d5e9159f8bbd9b20c9b979e45a4d943cDevang Patel 800cbdfb8a9d5e9159f8bbd9b20c9b979e45a4d943cDevang Patel return *Result; 8011715229db9c04e73ba8acb8579eb2b9465209785Chris Lattner} 80294108ab8a36806d5c7fb56bed4ddffda064f5c5dChris Lattner 803ce9653ce449f1409815547e1bf60abcd1332d2c9Reid Spencervoid DominanceFrontierBase::print(std::ostream &o, const Module* ) const { 804a59cbb2043c08f3cfb8fb379f0d336e21e070be8Chris Lattner for (const_iterator I = begin(), E = end(); I != E; ++I) { 805b884f597d62e8596df0b3856e9ca1b2496f81361Chris Lattner o << " DomFrontier for BB"; 806b884f597d62e8596df0b3856e9ca1b2496f81361Chris Lattner if (I->first) 807b884f597d62e8596df0b3856e9ca1b2496f81361Chris Lattner WriteAsOperand(o, I->first, false); 808b884f597d62e8596df0b3856e9ca1b2496f81361Chris Lattner else 809b884f597d62e8596df0b3856e9ca1b2496f81361Chris Lattner o << " <<exit node>>"; 810b884f597d62e8596df0b3856e9ca1b2496f81361Chris Lattner o << " is:\t" << I->second << "\n"; 811a59cbb2043c08f3cfb8fb379f0d336e21e070be8Chris Lattner } 812a59cbb2043c08f3cfb8fb379f0d336e21e070be8Chris Lattner} 813d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 81479b48b8bc07170656e7e2d7500f7fcbf69ccc923Devang Patelvoid DominanceFrontierBase::dump() { 81579b48b8bc07170656e7e2d7500f7fcbf69ccc923Devang Patel print (llvm::cerr); 81679b48b8bc07170656e7e2d7500f7fcbf69ccc923Devang Patel} 817