← Back to branch summary

~pali/+junk/llvm-toolchain-3.7

« back to all changes in this revision

Viewing changes to include/llvm/CodeGen/MachineDominators.h

  • Committer: Package Import Robot
  • Author(s): Sylvestre Ledru
  • Date: 2015-07-15 17:51:08 UTC
  • Revision ID: package-import@ubuntu.com-20150715175108-l8mynwovkx4zx697
Tags: upstream-3.7~+rc2
Import upstream version 3.7~+rc2

Show diffs side-by-side

added added

removed removed

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