/Users/buildslave/jenkins/sharedspace/clang-stage2-coverage-R@2/llvm/include/llvm/Transforms/Scalar/ConstantHoisting.h
Line | Count | Source |
1 | | //==- ConstantHoisting.h - Prepare code for expensive constants --*- 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 pass identifies expensive constants to hoist and coalesces them to |
11 | | // better prepare it for SelectionDAG-based code generation. This works around |
12 | | // the limitations of the basic-block-at-a-time approach. |
13 | | // |
14 | | // First it scans all instructions for integer constants and calculates its |
15 | | // cost. If the constant can be folded into the instruction (the cost is |
16 | | // TCC_Free) or the cost is just a simple operation (TCC_BASIC), then we don't |
17 | | // consider it expensive and leave it alone. This is the default behavior and |
18 | | // the default implementation of getIntImmCost will always return TCC_Free. |
19 | | // |
20 | | // If the cost is more than TCC_BASIC, then the integer constant can't be folded |
21 | | // into the instruction and it might be beneficial to hoist the constant. |
22 | | // Similar constants are coalesced to reduce register pressure and |
23 | | // materialization code. |
24 | | // |
25 | | // When a constant is hoisted, it is also hidden behind a bitcast to force it to |
26 | | // be live-out of the basic block. Otherwise the constant would be just |
27 | | // duplicated and each basic block would have its own copy in the SelectionDAG. |
28 | | // The SelectionDAG recognizes such constants as opaque and doesn't perform |
29 | | // certain transformations on them, which would create a new expensive constant. |
30 | | // |
31 | | // This optimization is only applied to integer constants in instructions and |
32 | | // simple (this means not nested) constant cast expressions. For example: |
33 | | // %0 = load i64* inttoptr (i64 big_constant to i64*) |
34 | | // |
35 | | //===----------------------------------------------------------------------===// |
36 | | |
37 | | #ifndef LLVM_TRANSFORMS_SCALAR_CONSTANTHOISTING_H |
38 | | #define LLVM_TRANSFORMS_SCALAR_CONSTANTHOISTING_H |
39 | | |
40 | | #include "llvm/ADT/DenseMap.h" |
41 | | #include "llvm/ADT/SmallPtrSet.h" |
42 | | #include "llvm/ADT/SmallVector.h" |
43 | | #include "llvm/IR/PassManager.h" |
44 | | #include <algorithm> |
45 | | #include <vector> |
46 | | |
47 | | namespace llvm { |
48 | | |
49 | | class BasicBlock; |
50 | | class BlockFrequencyInfo; |
51 | | class Constant; |
52 | | class ConstantInt; |
53 | | class DominatorTree; |
54 | | class Function; |
55 | | class Instruction; |
56 | | class TargetTransformInfo; |
57 | | |
58 | | /// A private "module" namespace for types and utilities used by |
59 | | /// ConstantHoisting. These are implementation details and should not be used by |
60 | | /// clients. |
61 | | namespace consthoist { |
62 | | |
63 | | /// \brief Keeps track of the user of a constant and the operand index where the |
64 | | /// constant is used. |
65 | | struct ConstantUser { |
66 | | Instruction *Inst; |
67 | | unsigned OpndIdx; |
68 | | |
69 | 58.0k | ConstantUser(Instruction *Inst, unsigned Idx) : Inst(Inst), OpndIdx(Idx) {} |
70 | | }; |
71 | | |
72 | | using ConstantUseListType = SmallVector<ConstantUser, 8>; |
73 | | |
74 | | /// \brief Keeps track of a constant candidate and its uses. |
75 | | struct ConstantCandidate { |
76 | | ConstantUseListType Uses; |
77 | | ConstantInt *ConstInt; |
78 | | unsigned CumulativeCost = 0; |
79 | | |
80 | 29.1k | ConstantCandidate(ConstantInt *ConstInt) : ConstInt(ConstInt) {} |
81 | | |
82 | | /// \brief Add the user to the use list and update the cost. |
83 | 58.0k | void addUser(Instruction *Inst, unsigned Idx, unsigned Cost) { |
84 | 58.0k | CumulativeCost += Cost; |
85 | 58.0k | Uses.push_back(ConstantUser(Inst, Idx)); |
86 | 58.0k | } |
87 | | }; |
88 | | |
89 | | /// \brief This represents a constant that has been rebased with respect to a |
90 | | /// base constant. The difference to the base constant is recorded in Offset. |
91 | | struct RebasedConstantInfo { |
92 | | ConstantUseListType Uses; |
93 | | Constant *Offset; |
94 | | |
95 | | RebasedConstantInfo(ConstantUseListType &&Uses, Constant *Offset) |
96 | 12.3k | : Uses(std::move(Uses)), Offset(Offset) {} |
97 | | }; |
98 | | |
99 | | using RebasedConstantListType = SmallVector<RebasedConstantInfo, 4>; |
100 | | |
101 | | /// \brief A base constant and all its rebased constants. |
102 | | struct ConstantInfo { |
103 | | ConstantInt *BaseConstant; |
104 | | RebasedConstantListType RebasedConstants; |
105 | | }; |
106 | | |
107 | | } // end namespace consthoist |
108 | | |
109 | | class ConstantHoistingPass : public PassInfoMixin<ConstantHoistingPass> { |
110 | | public: |
111 | | PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); |
112 | | |
113 | | // Glue for old PM. |
114 | | bool runImpl(Function &F, TargetTransformInfo &TTI, DominatorTree &DT, |
115 | | BlockFrequencyInfo *BFI, BasicBlock &Entry); |
116 | | |
117 | 588k | void releaseMemory() { |
118 | 588k | ConstantVec.clear(); |
119 | 588k | ClonedCastMap.clear(); |
120 | 588k | ConstCandVec.clear(); |
121 | 588k | } |
122 | | |
123 | | private: |
124 | | using ConstCandMapType = DenseMap<ConstantInt *, unsigned>; |
125 | | using ConstCandVecType = std::vector<consthoist::ConstantCandidate>; |
126 | | |
127 | | const TargetTransformInfo *TTI; |
128 | | DominatorTree *DT; |
129 | | BlockFrequencyInfo *BFI; |
130 | | BasicBlock *Entry; |
131 | | |
132 | | /// Keeps track of constant candidates found in the function. |
133 | | ConstCandVecType ConstCandVec; |
134 | | |
135 | | /// Keep track of cast instructions we already cloned. |
136 | | SmallDenseMap<Instruction *, Instruction *> ClonedCastMap; |
137 | | |
138 | | /// These are the final constants we decided to hoist. |
139 | | SmallVector<consthoist::ConstantInfo, 8> ConstantVec; |
140 | | |
141 | | Instruction *findMatInsertPt(Instruction *Inst, unsigned Idx = ~0U) const; |
142 | | SmallPtrSet<Instruction *, 8> |
143 | | findConstantInsertionPoint(const consthoist::ConstantInfo &ConstInfo) const; |
144 | | void collectConstantCandidates(ConstCandMapType &ConstCandMap, |
145 | | Instruction *Inst, unsigned Idx, |
146 | | ConstantInt *ConstInt); |
147 | | void collectConstantCandidates(ConstCandMapType &ConstCandMap, |
148 | | Instruction *Inst, unsigned Idx); |
149 | | void collectConstantCandidates(ConstCandMapType &ConstCandMap, |
150 | | Instruction *Inst); |
151 | | void collectConstantCandidates(Function &Fn); |
152 | | void findAndMakeBaseConstant(ConstCandVecType::iterator S, |
153 | | ConstCandVecType::iterator E); |
154 | | unsigned maximizeConstantsInRange(ConstCandVecType::iterator S, |
155 | | ConstCandVecType::iterator E, |
156 | | ConstCandVecType::iterator &MaxCostItr); |
157 | | void findBaseConstants(); |
158 | | void emitBaseConstants(Instruction *Base, Constant *Offset, |
159 | | const consthoist::ConstantUser &ConstUser); |
160 | | bool emitBaseConstants(); |
161 | | void deleteDeadCastInst() const; |
162 | | bool optimizeConstants(Function &Fn); |
163 | | }; |
164 | | |
165 | | } // end namespace llvm |
166 | | |
167 | | #endif // LLVM_TRANSFORMS_SCALAR_CONSTANTHOISTING_H |