PostDominators.cpp revision d20cc14dbf6d54d896e67b9920cd9bccdc14c41a
14c9df7c619ba827729490757dae6dc35bb068a9fChris Lattner//===- PostDominators.cpp - Post-Dominator Calculation --------------------===// 22b37d7cf28b1382420b5e4007042feeb66d21ac8Misha 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. 72b37d7cf28b1382420b5e4007042feeb66d21ac8Misha Brukman// 8b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell//===----------------------------------------------------------------------===// 91715229db9c04e73ba8acb8579eb2b9465209785Chris Lattner// 104c9df7c619ba827729490757dae6dc35bb068a9fChris Lattner// This file implements the post-dominator construction algorithms. 111715229db9c04e73ba8acb8579eb2b9465209785Chris Lattner// 121715229db9c04e73ba8acb8579eb2b9465209785Chris Lattner//===----------------------------------------------------------------------===// 131715229db9c04e73ba8acb8579eb2b9465209785Chris Lattner 14a69fd903585a665c031d5aa3fdfb8dc919b44befChris Lattner#include "llvm/Analysis/PostDominators.h" 1547b14a4a6a455c7be169cfd312fcbe796f0ad426Misha Brukman#include "llvm/Instructions.h" 16221d688a5ef21a22c2368c9fff0e92d7966c95e5Chris Lattner#include "llvm/Support/CFG.h" 17551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/ADT/DepthFirstIterator.h" 18551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/ADT/SetOperations.h" 199cb7f49ee9d8c77f5ae82e36befde2b3094fdd02Owen Anderson#include "llvm/Analysis/DominatorInternals.h" 20cd7c2877307bc82fdda978dc6f97d4c608e77a80Chris Lattnerusing namespace llvm; 21d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 2294108ab8a36806d5c7fb56bed4ddffda064f5c5dChris Lattner//===----------------------------------------------------------------------===// 233dc6776b338f81e2d47daa42cc12c9f91053043dOwen Anderson// PostDominatorTree Implementation 24442b32b5c5f690bc9b49d67b3ec76008879bc4d9Nate Begeman//===----------------------------------------------------------------------===// 25442b32b5c5f690bc9b49d67b3ec76008879bc4d9Nate Begeman 261997473cf72957d0e70322e2fe6fe2ab141c58a6Devang Patelchar PostDominatorTree::ID = 0; 271997473cf72957d0e70322e2fe6fe2ab141c58a6Devang Patelchar PostDominanceFrontier::ID = 0; 283dc6776b338f81e2d47daa42cc12c9f91053043dOwen Andersonstatic RegisterPass<PostDominatorTree> 293dc6776b338f81e2d47daa42cc12c9f91053043dOwen AndersonF("postdomtree", "Post-Dominator Tree Construction", true); 30442b32b5c5f690bc9b49d67b3ec76008879bc4d9Nate Begeman 31471ab54df756f2f48c9146ad897672662c3f25f9Owen Andersonbool PostDominatorTree::runOnFunction(Function &F) { 32d20cc14dbf6d54d896e67b9920cd9bccdc14c41aOwen Anderson DT->recalculate(F); 33471ab54df756f2f48c9146ad897672662c3f25f9Owen Anderson return false; 34471ab54df756f2f48c9146ad897672662c3f25f9Owen Anderson} 35471ab54df756f2f48c9146ad897672662c3f25f9Owen Anderson 36ccacd3ccc2a4a2336085a1d8d58cedb947b2eb52Chris Lattner//===----------------------------------------------------------------------===// 374c9df7c619ba827729490757dae6dc35bb068a9fChris Lattner// PostDominanceFrontier Implementation 381715229db9c04e73ba8acb8579eb2b9465209785Chris Lattner//===----------------------------------------------------------------------===// 391715229db9c04e73ba8acb8579eb2b9465209785Chris Lattner 405d8925c7c506a54ebdfb0bc93437ec9f602eaaa0Chris Lattnerstatic RegisterPass<PostDominanceFrontier> 4117689dfe241702cbbbd29cf1e4e4229444f3e9f3Chris LattnerH("postdomfrontier", "Post-Dominance Frontier Construction", true); 4293193f806378e06092820c099e437886c7309b94Chris Lattner 431b7f7dc4b45a900fae2e9b062d588a995935727aChris Lattnerconst DominanceFrontier::DomSetType & 442b37d7cf28b1382420b5e4007042feeb66d21ac8Misha BrukmanPostDominanceFrontier::calculate(const PostDominatorTree &DT, 4526042420d642e810f5cdfb2da6156b74aaf80945Devang Patel const DomTreeNode *Node) { 4694108ab8a36806d5c7fb56bed4ddffda064f5c5dChris Lattner // Loop over CFG successors to calculate DFlocal[Node] 47c444a4228f31656f854d15eac671b450df557346Chris Lattner BasicBlock *BB = Node->getBlock(); 4894108ab8a36806d5c7fb56bed4ddffda064f5c5dChris Lattner DomSetType &S = Frontiers[BB]; // The new set to fill in... 49706e61ead9b7913098ff3fbf729263a36e01f1b9Chris Lattner if (getRoots().empty()) return S; 50706e61ead9b7913098ff3fbf729263a36e01f1b9Chris Lattner 51706e61ead9b7913098ff3fbf729263a36e01f1b9Chris Lattner if (BB) 52706e61ead9b7913098ff3fbf729263a36e01f1b9Chris Lattner for (pred_iterator SI = pred_begin(BB), SE = pred_end(BB); 535a713cc72fd56c81e4cccc582f5eb0c731ad7c9fDevang Patel SI != SE; ++SI) { 542f2d06506c9167dada05b11debe717334de972d4Misha Brukman // Does Node immediately dominate this predecessor? 5526042420d642e810f5cdfb2da6156b74aaf80945Devang Patel DomTreeNode *SINode = DT[*SI]; 565a713cc72fd56c81e4cccc582f5eb0c731ad7c9fDevang Patel if (SINode && SINode->getIDom() != Node) 57706e61ead9b7913098ff3fbf729263a36e01f1b9Chris Lattner S.insert(*SI); 585a713cc72fd56c81e4cccc582f5eb0c731ad7c9fDevang Patel } 5994108ab8a36806d5c7fb56bed4ddffda064f5c5dChris Lattner 6094108ab8a36806d5c7fb56bed4ddffda064f5c5dChris Lattner // At this point, S is DFlocal. Now we union in DFup's of our children... 6194108ab8a36806d5c7fb56bed4ddffda064f5c5dChris Lattner // Loop through and visit the nodes that Node immediately dominates (Node's 6294108ab8a36806d5c7fb56bed4ddffda064f5c5dChris Lattner // children in the IDomTree) 6394108ab8a36806d5c7fb56bed4ddffda064f5c5dChris Lattner // 6426042420d642e810f5cdfb2da6156b74aaf80945Devang Patel for (DomTreeNode::const_iterator 65ce6ef112c4abb1f7fd64738c5760f48cddc9a4a5Chris Lattner NI = Node->begin(), NE = Node->end(); NI != NE; ++NI) { 6626042420d642e810f5cdfb2da6156b74aaf80945Devang Patel DomTreeNode *IDominee = *NI; 67ce6ef112c4abb1f7fd64738c5760f48cddc9a4a5Chris Lattner const DomSetType &ChildDF = calculate(DT, IDominee); 6894108ab8a36806d5c7fb56bed4ddffda064f5c5dChris Lattner 6994108ab8a36806d5c7fb56bed4ddffda064f5c5dChris Lattner DomSetType::const_iterator CDFI = ChildDF.begin(), CDFE = ChildDF.end(); 7094108ab8a36806d5c7fb56bed4ddffda064f5c5dChris Lattner for (; CDFI != CDFE; ++CDFI) { 719a51157db555395f7a6ad89faec40b3afa121091Devang Patel if (!DT.properlyDominates(Node, DT[*CDFI])) 72dedf2bd5a34dac25e4245f58bb902ced6b64edd9Misha Brukman S.insert(*CDFI); 7394108ab8a36806d5c7fb56bed4ddffda064f5c5dChris Lattner } 7494108ab8a36806d5c7fb56bed4ddffda064f5c5dChris Lattner } 7594108ab8a36806d5c7fb56bed4ddffda064f5c5dChris Lattner 7694108ab8a36806d5c7fb56bed4ddffda064f5c5dChris Lattner return S; 7794108ab8a36806d5c7fb56bed4ddffda064f5c5dChris Lattner} 78a69fd903585a665c031d5aa3fdfb8dc919b44befChris Lattner 794f1bd9e9963239c119db70070db1d68286b3de7eReid Spencer// Ensure that this .cpp file gets linked when PostDominators.h is used. 804f1bd9e9963239c119db70070db1d68286b3de7eReid SpencerDEFINING_FILE_FOR(PostDominanceFrontier) 81