Andrew Scull | 5e1ddfa | 2018-08-14 10:06:54 +0100 | [diff] [blame] | 1 | //==- llvm/CodeGen/MachineDominators.h - Machine Dom Calculation -*- C++ -*-==// |
| 2 | // |
Andrew Walbran | 16937d0 | 2019-10-22 13:54:20 +0100 | [diff] [blame] | 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 |
Andrew Scull | 5e1ddfa | 2018-08-14 10:06:54 +0100 | [diff] [blame] | 6 | // |
| 7 | //===----------------------------------------------------------------------===// |
| 8 | // |
| 9 | // This file defines classes mirroring those in llvm/Analysis/Dominators.h, |
| 10 | // but for target-specific code rather than target-independent IR. |
| 11 | // |
| 12 | //===----------------------------------------------------------------------===// |
| 13 | |
| 14 | #ifndef LLVM_CODEGEN_MACHINEDOMINATORS_H |
| 15 | #define LLVM_CODEGEN_MACHINEDOMINATORS_H |
| 16 | |
| 17 | #include "llvm/ADT/SmallSet.h" |
| 18 | #include "llvm/ADT/SmallVector.h" |
| 19 | #include "llvm/CodeGen/MachineBasicBlock.h" |
| 20 | #include "llvm/CodeGen/MachineFunctionPass.h" |
| 21 | #include "llvm/CodeGen/MachineInstr.h" |
| 22 | #include "llvm/Support/GenericDomTree.h" |
| 23 | #include "llvm/Support/GenericDomTreeConstruction.h" |
| 24 | #include <cassert> |
| 25 | #include <memory> |
| 26 | #include <vector> |
| 27 | |
| 28 | namespace llvm { |
| 29 | |
| 30 | template <> |
| 31 | inline void DominatorTreeBase<MachineBasicBlock, false>::addRoot( |
| 32 | MachineBasicBlock *MBB) { |
| 33 | this->Roots.push_back(MBB); |
| 34 | } |
| 35 | |
| 36 | extern template class DomTreeNodeBase<MachineBasicBlock>; |
| 37 | extern template class DominatorTreeBase<MachineBasicBlock, false>; // DomTree |
| 38 | extern template class DominatorTreeBase<MachineBasicBlock, true>; // PostDomTree |
| 39 | |
| 40 | using MachineDomTreeNode = DomTreeNodeBase<MachineBasicBlock>; |
| 41 | |
| 42 | //===------------------------------------- |
| 43 | /// DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to |
| 44 | /// compute a normal dominator tree. |
| 45 | /// |
| 46 | class MachineDominatorTree : public MachineFunctionPass { |
Andrew Scull | cdfcccc | 2018-10-05 20:58:37 +0100 | [diff] [blame] | 47 | /// Helper structure used to hold all the basic blocks |
Andrew Scull | 5e1ddfa | 2018-08-14 10:06:54 +0100 | [diff] [blame] | 48 | /// involved in the split of a critical edge. |
| 49 | struct CriticalEdge { |
| 50 | MachineBasicBlock *FromBB; |
| 51 | MachineBasicBlock *ToBB; |
| 52 | MachineBasicBlock *NewBB; |
| 53 | }; |
| 54 | |
Andrew Scull | cdfcccc | 2018-10-05 20:58:37 +0100 | [diff] [blame] | 55 | /// Pile up all the critical edges to be split. |
Andrew Scull | 5e1ddfa | 2018-08-14 10:06:54 +0100 | [diff] [blame] | 56 | /// The splitting of a critical edge is local and thus, it is possible |
| 57 | /// to apply several of those changes at the same time. |
| 58 | mutable SmallVector<CriticalEdge, 32> CriticalEdgesToSplit; |
| 59 | |
Andrew Scull | cdfcccc | 2018-10-05 20:58:37 +0100 | [diff] [blame] | 60 | /// Remember all the basic blocks that are inserted during |
Andrew Scull | 5e1ddfa | 2018-08-14 10:06:54 +0100 | [diff] [blame] | 61 | /// edge splitting. |
| 62 | /// Invariant: NewBBs == all the basic blocks contained in the NewBB |
| 63 | /// field of all the elements of CriticalEdgesToSplit. |
| 64 | /// I.e., forall elt in CriticalEdgesToSplit, it exists BB in NewBBs |
| 65 | /// such as BB == elt.NewBB. |
| 66 | mutable SmallSet<MachineBasicBlock *, 32> NewBBs; |
| 67 | |
| 68 | /// The DominatorTreeBase that is used to compute a normal dominator tree |
| 69 | std::unique_ptr<DomTreeBase<MachineBasicBlock>> DT; |
| 70 | |
Andrew Scull | cdfcccc | 2018-10-05 20:58:37 +0100 | [diff] [blame] | 71 | /// Apply all the recorded critical edges to the DT. |
Andrew Scull | 5e1ddfa | 2018-08-14 10:06:54 +0100 | [diff] [blame] | 72 | /// This updates the underlying DT information in a way that uses |
| 73 | /// the fast query path of DT as much as possible. |
| 74 | /// |
| 75 | /// \post CriticalEdgesToSplit.empty(). |
| 76 | void applySplitCriticalEdges() const; |
| 77 | |
| 78 | public: |
| 79 | static char ID; // Pass ID, replacement for typeid |
| 80 | |
| 81 | MachineDominatorTree(); |
| 82 | |
| 83 | DomTreeBase<MachineBasicBlock> &getBase() { |
| 84 | if (!DT) DT.reset(new DomTreeBase<MachineBasicBlock>()); |
| 85 | applySplitCriticalEdges(); |
| 86 | return *DT; |
| 87 | } |
| 88 | |
| 89 | void getAnalysisUsage(AnalysisUsage &AU) const override; |
| 90 | |
| 91 | /// getRoots - Return the root blocks of the current CFG. This may include |
| 92 | /// multiple blocks if we are computing post dominators. For forward |
| 93 | /// dominators, this will always be a single block (the entry node). |
| 94 | /// |
| 95 | inline const SmallVectorImpl<MachineBasicBlock*> &getRoots() const { |
| 96 | applySplitCriticalEdges(); |
| 97 | return DT->getRoots(); |
| 98 | } |
| 99 | |
| 100 | inline MachineBasicBlock *getRoot() const { |
| 101 | applySplitCriticalEdges(); |
| 102 | return DT->getRoot(); |
| 103 | } |
| 104 | |
| 105 | inline MachineDomTreeNode *getRootNode() const { |
| 106 | applySplitCriticalEdges(); |
| 107 | return DT->getRootNode(); |
| 108 | } |
| 109 | |
| 110 | bool runOnMachineFunction(MachineFunction &F) override; |
| 111 | |
| 112 | inline bool dominates(const MachineDomTreeNode* A, |
| 113 | const MachineDomTreeNode* B) const { |
| 114 | applySplitCriticalEdges(); |
| 115 | return DT->dominates(A, B); |
| 116 | } |
| 117 | |
| 118 | inline bool dominates(const MachineBasicBlock* A, |
| 119 | const MachineBasicBlock* B) const { |
| 120 | applySplitCriticalEdges(); |
| 121 | return DT->dominates(A, B); |
| 122 | } |
| 123 | |
| 124 | // dominates - Return true if A dominates B. This performs the |
| 125 | // special checks necessary if A and B are in the same basic block. |
| 126 | bool dominates(const MachineInstr *A, const MachineInstr *B) const { |
| 127 | applySplitCriticalEdges(); |
| 128 | const MachineBasicBlock *BBA = A->getParent(), *BBB = B->getParent(); |
| 129 | if (BBA != BBB) return DT->dominates(BBA, BBB); |
| 130 | |
| 131 | // Loop through the basic block until we find A or B. |
| 132 | MachineBasicBlock::const_iterator I = BBA->begin(); |
| 133 | for (; &*I != A && &*I != B; ++I) |
| 134 | /*empty*/ ; |
| 135 | |
| 136 | //if(!DT.IsPostDominators) { |
| 137 | // A dominates B if it is found first in the basic block. |
| 138 | return &*I == A; |
| 139 | //} else { |
| 140 | // // A post-dominates B if B is found first in the basic block. |
| 141 | // return &*I == B; |
| 142 | //} |
| 143 | } |
| 144 | |
| 145 | inline bool properlyDominates(const MachineDomTreeNode* A, |
| 146 | const MachineDomTreeNode* B) const { |
| 147 | applySplitCriticalEdges(); |
| 148 | return DT->properlyDominates(A, B); |
| 149 | } |
| 150 | |
| 151 | inline bool properlyDominates(const MachineBasicBlock* A, |
| 152 | const MachineBasicBlock* B) const { |
| 153 | applySplitCriticalEdges(); |
| 154 | return DT->properlyDominates(A, B); |
| 155 | } |
| 156 | |
| 157 | /// findNearestCommonDominator - Find nearest common dominator basic block |
| 158 | /// for basic block A and B. If there is no such block then return NULL. |
| 159 | inline MachineBasicBlock *findNearestCommonDominator(MachineBasicBlock *A, |
| 160 | MachineBasicBlock *B) { |
| 161 | applySplitCriticalEdges(); |
| 162 | return DT->findNearestCommonDominator(A, B); |
| 163 | } |
| 164 | |
| 165 | inline MachineDomTreeNode *operator[](MachineBasicBlock *BB) const { |
| 166 | applySplitCriticalEdges(); |
| 167 | return DT->getNode(BB); |
| 168 | } |
| 169 | |
| 170 | /// getNode - return the (Post)DominatorTree node for the specified basic |
| 171 | /// block. This is the same as using operator[] on this class. |
| 172 | /// |
| 173 | inline MachineDomTreeNode *getNode(MachineBasicBlock *BB) const { |
| 174 | applySplitCriticalEdges(); |
| 175 | return DT->getNode(BB); |
| 176 | } |
| 177 | |
| 178 | /// addNewBlock - Add a new node to the dominator tree information. This |
| 179 | /// creates a new node as a child of DomBB dominator node,linking it into |
| 180 | /// the children list of the immediate dominator. |
| 181 | inline MachineDomTreeNode *addNewBlock(MachineBasicBlock *BB, |
| 182 | MachineBasicBlock *DomBB) { |
| 183 | applySplitCriticalEdges(); |
| 184 | return DT->addNewBlock(BB, DomBB); |
| 185 | } |
| 186 | |
| 187 | /// changeImmediateDominator - This method is used to update the dominator |
| 188 | /// tree information when a node's immediate dominator changes. |
| 189 | /// |
| 190 | inline void changeImmediateDominator(MachineBasicBlock *N, |
| 191 | MachineBasicBlock* NewIDom) { |
| 192 | applySplitCriticalEdges(); |
| 193 | DT->changeImmediateDominator(N, NewIDom); |
| 194 | } |
| 195 | |
| 196 | inline void changeImmediateDominator(MachineDomTreeNode *N, |
| 197 | MachineDomTreeNode* NewIDom) { |
| 198 | applySplitCriticalEdges(); |
| 199 | DT->changeImmediateDominator(N, NewIDom); |
| 200 | } |
| 201 | |
| 202 | /// eraseNode - Removes a node from the dominator tree. Block must not |
| 203 | /// dominate any other blocks. Removes node from its immediate dominator's |
| 204 | /// children list. Deletes dominator node associated with basic block BB. |
| 205 | inline void eraseNode(MachineBasicBlock *BB) { |
| 206 | applySplitCriticalEdges(); |
| 207 | DT->eraseNode(BB); |
| 208 | } |
| 209 | |
| 210 | /// splitBlock - BB is split and now it has one successor. Update dominator |
| 211 | /// tree to reflect this change. |
| 212 | inline void splitBlock(MachineBasicBlock* NewBB) { |
| 213 | applySplitCriticalEdges(); |
| 214 | DT->splitBlock(NewBB); |
| 215 | } |
| 216 | |
| 217 | /// isReachableFromEntry - Return true if A is dominated by the entry |
| 218 | /// block of the function containing it. |
| 219 | bool isReachableFromEntry(const MachineBasicBlock *A) { |
| 220 | applySplitCriticalEdges(); |
| 221 | return DT->isReachableFromEntry(A); |
| 222 | } |
| 223 | |
| 224 | void releaseMemory() override; |
| 225 | |
| 226 | void verifyAnalysis() const override; |
| 227 | |
| 228 | void print(raw_ostream &OS, const Module*) const override; |
| 229 | |
Andrew Scull | cdfcccc | 2018-10-05 20:58:37 +0100 | [diff] [blame] | 230 | /// Record that the critical edge (FromBB, ToBB) has been |
Andrew Scull | 5e1ddfa | 2018-08-14 10:06:54 +0100 | [diff] [blame] | 231 | /// split with NewBB. |
| 232 | /// This is best to use this method instead of directly update the |
| 233 | /// underlying information, because this helps mitigating the |
| 234 | /// number of time the DT information is invalidated. |
| 235 | /// |
| 236 | /// \note Do not use this method with regular edges. |
| 237 | /// |
| 238 | /// \note To benefit from the compile time improvement incurred by this |
| 239 | /// method, the users of this method have to limit the queries to the DT |
| 240 | /// interface between two edges splitting. In other words, they have to |
| 241 | /// pack the splitting of critical edges as much as possible. |
| 242 | void recordSplitCriticalEdge(MachineBasicBlock *FromBB, |
| 243 | MachineBasicBlock *ToBB, |
| 244 | MachineBasicBlock *NewBB) { |
| 245 | bool Inserted = NewBBs.insert(NewBB).second; |
| 246 | (void)Inserted; |
| 247 | assert(Inserted && |
| 248 | "A basic block inserted via edge splitting cannot appear twice"); |
| 249 | CriticalEdgesToSplit.push_back({FromBB, ToBB, NewBB}); |
| 250 | } |
| 251 | }; |
| 252 | |
| 253 | //===------------------------------------- |
| 254 | /// DominatorTree GraphTraits specialization so the DominatorTree can be |
| 255 | /// iterable by generic graph iterators. |
| 256 | /// |
| 257 | |
| 258 | template <class Node, class ChildIterator> |
| 259 | struct MachineDomTreeGraphTraitsBase { |
| 260 | using NodeRef = Node *; |
| 261 | using ChildIteratorType = ChildIterator; |
| 262 | |
| 263 | static NodeRef getEntryNode(NodeRef N) { return N; } |
| 264 | static ChildIteratorType child_begin(NodeRef N) { return N->begin(); } |
| 265 | static ChildIteratorType child_end(NodeRef N) { return N->end(); } |
| 266 | }; |
| 267 | |
| 268 | template <class T> struct GraphTraits; |
| 269 | |
| 270 | template <> |
| 271 | struct GraphTraits<MachineDomTreeNode *> |
| 272 | : public MachineDomTreeGraphTraitsBase<MachineDomTreeNode, |
| 273 | MachineDomTreeNode::iterator> {}; |
| 274 | |
| 275 | template <> |
| 276 | struct GraphTraits<const MachineDomTreeNode *> |
| 277 | : public MachineDomTreeGraphTraitsBase<const MachineDomTreeNode, |
| 278 | MachineDomTreeNode::const_iterator> { |
| 279 | }; |
| 280 | |
| 281 | template <> struct GraphTraits<MachineDominatorTree*> |
| 282 | : public GraphTraits<MachineDomTreeNode *> { |
| 283 | static NodeRef getEntryNode(MachineDominatorTree *DT) { |
| 284 | return DT->getRootNode(); |
| 285 | } |
| 286 | }; |
| 287 | |
| 288 | } // end namespace llvm |
| 289 | |
| 290 | #endif // LLVM_CODEGEN_MACHINEDOMINATORS_H |