LLVM  6.0.0svn
ConstantHoisting.h
Go to the documentation of this file.
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 {
67  unsigned OpndIdx;
68 
69  ConstantUser(Instruction *Inst, unsigned Idx) : Inst(Inst), OpndIdx(Idx) {}
70 };
71 
73 
74 /// \brief Keeps track of a constant candidate and its uses.
78  unsigned CumulativeCost = 0;
79 
80  ConstantCandidate(ConstantInt *ConstInt) : ConstInt(ConstInt) {}
81 
82  /// \brief Add the user to the use list and update the cost.
83  void addUser(Instruction *Inst, unsigned Idx, unsigned Cost) {
84  CumulativeCost += Cost;
85  Uses.push_back(ConstantUser(Inst, Idx));
86  }
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.
94 
96  : Uses(std::move(Uses)), Offset(Offset) {}
97 };
98 
100 
101 /// \brief A base constant and all its rebased constants.
102 struct ConstantInfo {
105 };
106 
107 } // end namespace consthoist
108 
109 class ConstantHoistingPass : public PassInfoMixin<ConstantHoistingPass> {
110 public:
112 
113  // Glue for old PM.
116 
117  void releaseMemory() {
118  ConstantVec.clear();
119  ClonedCastMap.clear();
120  ConstCandVec.clear();
121  }
122 
123 private:
125  using ConstCandVecType = std::vector<consthoist::ConstantCandidate>;
126 
127  const TargetTransformInfo *TTI;
128  DominatorTree *DT;
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.
137 
138  /// These are the final constants we decided to hoist.
140 
141  Instruction *findMatInsertPt(Instruction *Inst, unsigned Idx = ~0U) const;
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
void push_back(const T &Elt)
Definition: SmallVector.h:212
A base constant and all its rebased constants.
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
Various leaf nodes.
Definition: ISDOpcodes.h:60
Keeps track of a constant candidate and its uses.
void addUser(Instruction *Inst, unsigned Idx, unsigned Cost)
Add the user to the use list and update the cost.
F(f)
This represents a constant that has been rebased with respect to a base constant. ...
Definition: BitVector.h:920
static bool runImpl(CallGraphSCC &SCC, AARGetterT AARGetter)
RebasedConstantInfo(ConstantUseListType &&Uses, Constant *Offset)
A CRTP mix-in to automatically provide informational APIs needed for passes.
Definition: PassManager.h:365
ConstantCandidate(ConstantInt *ConstInt)
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree...
Definition: Dominators.h:140
BlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to estimate IR basic block frequen...
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:153
LLVM Basic Block Representation.
Definition: BasicBlock.h:59
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
This is an important base class in LLVM.
Definition: Constant.h:42
Keeps track of the user of a constant and the operand index where the constant is used...
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements...
Definition: SmallPtrSet.h:418
This is the shared class of boolean and integer constants.
Definition: Constants.h:84
This pass provides access to the codegen interfaces that are needed for IR-level transformations.
ConstantUser(Instruction *Inst, unsigned Idx)
A container for analyses that lazily runs them and caches their results.
RebasedConstantListType RebasedConstants
This header defines various interfaces for pass management in LLVM.