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