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
47namespace llvm {
48
49class BasicBlock;
50class BlockFrequencyInfo;
51class Constant;
52class ConstantInt;
53class DominatorTree;
54class Function;
55class Instruction;
56class 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.
61namespace consthoist {
62
63/// \brief Keeps track of the user of a constant and the operand index where the
64/// constant is used.
65struct ConstantUser {
66  Instruction *Inst;
67  unsigned OpndIdx;
68
69  ConstantUser(Instruction *Inst, unsigned Idx) : Inst(Inst), OpndIdx(Idx) {}
70};
71
72using ConstantUseListType = SmallVector<ConstantUser, 8>;
73
74/// \brief Keeps track of a constant candidate and its uses.
75struct ConstantCandidate {
76  ConstantUseListType Uses;
77  ConstantInt *ConstInt;
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.
91struct RebasedConstantInfo {
92  ConstantUseListType Uses;
93  Constant *Offset;
94
95  RebasedConstantInfo(ConstantUseListType &&Uses, Constant *Offset)
96    : Uses(std::move(Uses)), Offset(Offset) {}
97};
98
99using RebasedConstantListType = SmallVector<RebasedConstantInfo, 4>;
100
101/// \brief A base constant and all its rebased constants.
102struct ConstantInfo {
103  ConstantInt *BaseConstant;
104  RebasedConstantListType RebasedConstants;
105};
106
107} // end namespace consthoist
108
109class ConstantHoistingPass : public PassInfoMixin<ConstantHoistingPass> {
110public:
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  void releaseMemory() {
118    ConstantVec.clear();
119    ClonedCastMap.clear();
120    ConstCandVec.clear();
121  }
122
123private:
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
168