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