Home | History | Annotate | Download | only in CodeGen 
      1 //===- MachineDominators.cpp - Machine Dominator Calculation --------------===//
      2 //
      3 //                     The LLVM Compiler Infrastructure
      4 //
      5 // This file is distributed under the University of Illinois Open Source
      6 // License. See LICENSE.TXT for details.
      7 //
      8 //===----------------------------------------------------------------------===//
      9 //
     10 // This file implements simple dominator construction algorithms for finding
     11 // forward dominators on machine functions.
     12 //
     13 //===----------------------------------------------------------------------===//
     14 
     15 #include "llvm/CodeGen/MachineDominators.h"
     16 #include "llvm/CodeGen/Passes.h"
     17 #include "llvm/ADT/SmallBitVector.h"
     18 
     19 using namespace llvm;
     20 
     21 namespace llvm {
     22 template class DomTreeNodeBase<MachineBasicBlock>;
     23 template class DominatorTreeBase<MachineBasicBlock>;
     24 }
     25 
     26 char MachineDominatorTree::ID = 0;
     27 
     28 INITIALIZE_PASS(MachineDominatorTree, "machinedomtree",
     29                 "MachineDominator Tree Construction", true, true)
     30 
     31 char &llvm::MachineDominatorsID = MachineDominatorTree::ID;
     32 
     33 void MachineDominatorTree::getAnalysisUsage(AnalysisUsage &AU) const {
     34   AU.setPreservesAll();
     35   MachineFunctionPass::getAnalysisUsage(AU);
     36 }
     37 
     38 bool MachineDominatorTree::runOnMachineFunction(MachineFunction &F) {
     39   CriticalEdgesToSplit.clear();
     40   NewBBs.clear();
     41   DT->recalculate(F);
     42 
     43   return false;
     44 }
     45 
     46 MachineDominatorTree::MachineDominatorTree()
     47     : MachineFunctionPass(ID) {
     48   initializeMachineDominatorTreePass(*PassRegistry::getPassRegistry());
     49   DT = new DominatorTreeBase<MachineBasicBlock>(false);
     50 }
     51 
     52 MachineDominatorTree::~MachineDominatorTree() {
     53   delete DT;
     54 }
     55 
     56 void MachineDominatorTree::releaseMemory() {
     57   DT->releaseMemory();
     58 }
     59 
     60 void MachineDominatorTree::print(raw_ostream &OS, const Module*) const {
     61   DT->print(OS);
     62 }
     63 
     64 void MachineDominatorTree::applySplitCriticalEdges() const {
     65   // Bail out early if there is nothing to do.
     66   if (CriticalEdgesToSplit.empty())
     67     return;
     68 
     69   // For each element in CriticalEdgesToSplit, remember whether or not element
     70   // is the new immediate domminator of its successor. The mapping is done by
     71   // index, i.e., the information for the ith element of CriticalEdgesToSplit is
     72   // the ith element of IsNewIDom.
     73   SmallBitVector IsNewIDom(CriticalEdgesToSplit.size(), true);
     74   size_t Idx = 0;
     75 
     76   // Collect all the dominance properties info, before invalidating
     77   // the underlying DT.
     78   for (CriticalEdge &Edge : CriticalEdgesToSplit) {
     79     // Update dominator information.
     80     MachineBasicBlock *Succ = Edge.ToBB;
     81     MachineDomTreeNode *SuccDTNode = DT->getNode(Succ);
     82 
     83     for (MachineBasicBlock *PredBB : Succ->predecessors()) {
     84       if (PredBB == Edge.NewBB)
     85         continue;
     86       // If we are in this situation:
     87       // FromBB1        FromBB2
     88       //    +              +
     89       //   + +            + +
     90       //  +   +          +   +
     91       // ...  Split1  Split2 ...
     92       //           +   +
     93       //            + +
     94       //             +
     95       //            Succ
     96       // Instead of checking the domiance property with Split2, we check it with
     97       // FromBB2 since Split2 is still unknown of the underlying DT structure.
     98       if (NewBBs.count(PredBB)) {
     99         assert(PredBB->pred_size() == 1 && "A basic block resulting from a "
    100                                            "critical edge split has more "
    101                                            "than one predecessor!");
    102         PredBB = *PredBB->pred_begin();
    103       }
    104       if (!DT->dominates(SuccDTNode, DT->getNode(PredBB))) {
    105         IsNewIDom[Idx] = false;
    106         break;
    107       }
    108     }
    109     ++Idx;
    110   }
    111 
    112   // Now, update DT with the collected dominance properties info.
    113   Idx = 0;
    114   for (CriticalEdge &Edge : CriticalEdgesToSplit) {
    115     // We know FromBB dominates NewBB.
    116     MachineDomTreeNode *NewDTNode = DT->addNewBlock(Edge.NewBB, Edge.FromBB);
    117 
    118     // If all the other predecessors of "Succ" are dominated by "Succ" itself
    119     // then the new block is the new immediate dominator of "Succ". Otherwise,
    120     // the new block doesn't dominate anything.
    121     if (IsNewIDom[Idx])
    122       DT->changeImmediateDominator(DT->getNode(Edge.ToBB), NewDTNode);
    123     ++Idx;
    124   }
    125   NewBBs.clear();
    126   CriticalEdgesToSplit.clear();
    127 }
    128