include/llvm/Transforms/Scalar/ConstantHoisting.h

   1 //==- ConstantHoisting.h - Prepare code for expensive constants --*- C++ -*-==//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 //
   9 // This pass identifies expensive constants to hoist and coalesces them to
  10 // better prepare it for SelectionDAG-based code generation. This works around
  11 // the limitations of the basic-block-at-a-time approach.
  12 //
  13 // First it scans all instructions for integer constants and calculates its
  14 // cost. If the constant can be folded into the instruction (the cost is
  15 // TCC_Free) or the cost is just a simple operation (TCC_BASIC), then we don't
  16 // consider it expensive and leave it alone. This is the default behavior and
  17 // the default implementation of getIntImmCost will always return TCC_Free.
  18 //
  19 // If the cost is more than TCC_BASIC, then the integer constant can't be folded
  20 // into the instruction and it might be beneficial to hoist the constant.
  21 // Similar constants are coalesced to reduce register pressure and
  22 // materialization code.
  23 //
  24 // When a constant is hoisted, it is also hidden behind a bitcast to force it to
  25 // be live-out of the basic block. Otherwise the constant would be just
  26 // duplicated and each basic block would have its own copy in the SelectionDAG.
  27 // The SelectionDAG recognizes such constants as opaque and doesn't perform
  28 // certain transformations on them, which would create a new expensive constant.
  29 //
  30 // This optimization is only applied to integer constants in instructions and
  31 // simple (this means not nested) constant cast expressions. For example:
  32 // %0 = load i64* inttoptr (i64 big_constant to i64*)
  33 //
  34 //===----------------------------------------------------------------------===//
  35
  36 #ifndef LLVM_TRANSFORMS_SCALAR_CONSTANTHOISTING_H
  37 #define LLVM_TRANSFORMS_SCALAR_CONSTANTHOISTING_H
  38
  39 #include "llvm/ADT/DenseMap.h"
  40 #include "llvm/ADT/PointerUnion.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 ConstantExpr;
  54 class DominatorTree;
  55 class Function;
  56 class GlobalVariable;
  57 class Instruction;
  58 class ProfileSummaryInfo;
  59 class TargetTransformInfo;
  60
  61 /// A private "module" namespace for types and utilities used by
  62 /// ConstantHoisting. These are implementation details and should not be used by
  63 /// clients.
  64 namespace consthoist {
  65
  66 /// Keeps track of the user of a constant and the operand index where the
  67 /// constant is used.
  68 struct ConstantUser {
  69   Instruction *Inst;
  70   unsigned OpndIdx;
  71
  72   ConstantUser(Instruction *Inst, unsigned Idx) : Inst(Inst), OpndIdx(Idx) {}
  73 };
  74
  75 using ConstantUseListType = SmallVector<ConstantUser, 8>;
  76
  77 /// Keeps track of a constant candidate and its uses.
  78 struct ConstantCandidate {
  79   ConstantUseListType Uses;
  80   // If the candidate is a ConstantExpr (currely only constant GEP expressions
  81   // whose base pointers are GlobalVariables are supported), ConstInt records
  82   // its offset from the base GV, ConstExpr tracks the candidate GEP expr.
  83   ConstantInt *ConstInt;
  84   ConstantExpr *ConstExpr;
  85   unsigned CumulativeCost = 0;
  86
  87   ConstantCandidate(ConstantInt *ConstInt, ConstantExpr *ConstExpr=nullptr) :
  88       ConstInt(ConstInt), ConstExpr(ConstExpr) {}
  89
  90   /// Add the user to the use list and update the cost.
  91   void addUser(Instruction *Inst, unsigned Idx, unsigned Cost) {
  92     CumulativeCost += Cost;
  93     Uses.push_back(ConstantUser(Inst, Idx));
  94   }
  95 };
  96
  97 /// This represents a constant that has been rebased with respect to a
  98 /// base constant. The difference to the base constant is recorded in Offset.
  99 struct RebasedConstantInfo {
 100   ConstantUseListType Uses;
 101   Constant *Offset;
 102   Type *Ty;
 103
 104   RebasedConstantInfo(ConstantUseListType &&Uses, Constant *Offset,
 105       Type *Ty=nullptr) : Uses(std::move(Uses)), Offset(Offset), Ty(Ty) {}
 106 };
 107
 108 using RebasedConstantListType = SmallVector<RebasedConstantInfo, 4>;
 109
 110 /// A base constant and all its rebased constants.
 111 struct ConstantInfo {
 112   // If the candidate is a ConstantExpr (currely only constant GEP expressions
 113   // whose base pointers are GlobalVariables are supported), ConstInt records
 114   // its offset from the base GV, ConstExpr tracks the candidate GEP expr.
 115   ConstantInt *BaseInt;
 116   ConstantExpr *BaseExpr;
 117   RebasedConstantListType RebasedConstants;
 118 };
 119
 120 } // end namespace consthoist
 121
 122 class ConstantHoistingPass : public PassInfoMixin<ConstantHoistingPass> {
 123 public:
 124   PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
 125
 126   // Glue for old PM.
 127   bool runImpl(Function &F, TargetTransformInfo &TTI, DominatorTree &DT,
 128                BlockFrequencyInfo *BFI, BasicBlock &Entry,
 129                ProfileSummaryInfo *PSI);
 130
 131   void cleanup() {
 132     ClonedCastMap.clear();
 133     ConstIntCandVec.clear();
 134     for (auto MapEntry : ConstGEPCandMap)
 135       MapEntry.second.clear();
 136     ConstGEPCandMap.clear();
 137     ConstIntInfoVec.clear();
 138     for (auto MapEntry : ConstGEPInfoMap)
 139       MapEntry.second.clear();
 140     ConstGEPInfoMap.clear();
 141   }
 142
 143 private:
 144   using ConstPtrUnionType = PointerUnion<ConstantInt *, ConstantExpr *>;
 145   using ConstCandMapType = DenseMap<ConstPtrUnionType, unsigned>;
 146
 147   const TargetTransformInfo *TTI;
 148   DominatorTree *DT;
 149   BlockFrequencyInfo *BFI;
 150   LLVMContext *Ctx;
 151   const DataLayout *DL;
 152   BasicBlock *Entry;
 153   ProfileSummaryInfo *PSI;
 154
 155   /// Keeps track of constant candidates found in the function.
 156   using ConstCandVecType = std::vector<consthoist::ConstantCandidate>;
 157   using GVCandVecMapType = DenseMap<GlobalVariable *, ConstCandVecType>;
 158   ConstCandVecType ConstIntCandVec;
 159   GVCandVecMapType ConstGEPCandMap;
 160
 161   /// These are the final constants we decided to hoist.
 162   using ConstInfoVecType = SmallVector<consthoist::ConstantInfo, 8>;
 163   using GVInfoVecMapType = DenseMap<GlobalVariable *, ConstInfoVecType>;
 164   ConstInfoVecType ConstIntInfoVec;
 165   GVInfoVecMapType ConstGEPInfoMap;
 166
 167   /// Keep track of cast instructions we already cloned.
 168   SmallDenseMap<Instruction *, Instruction *> ClonedCastMap;
 169
 170   Instruction *findMatInsertPt(Instruction *Inst, unsigned Idx = ~0U) const;
 171   SmallPtrSet<Instruction *, 8>
 172   findConstantInsertionPoint(const consthoist::ConstantInfo &ConstInfo) const;
 173   void collectConstantCandidates(ConstCandMapType &ConstCandMap,
 174                                  Instruction *Inst, unsigned Idx,
 175                                  ConstantInt *ConstInt);
 176   void collectConstantCandidates(ConstCandMapType &ConstCandMap,
 177                                  Instruction *Inst, unsigned Idx,
 178                                  ConstantExpr *ConstExpr);
 179   void collectConstantCandidates(ConstCandMapType &ConstCandMap,
 180                                  Instruction *Inst, unsigned Idx);
 181   void collectConstantCandidates(ConstCandMapType &ConstCandMap,
 182                                  Instruction *Inst);
 183   void collectConstantCandidates(Function &Fn);
 184   void findAndMakeBaseConstant(ConstCandVecType::iterator S,
 185                                ConstCandVecType::iterator E,
 186       SmallVectorImpl<consthoist::ConstantInfo> &ConstInfoVec);
 187   unsigned maximizeConstantsInRange(ConstCandVecType::iterator S,
 188                                     ConstCandVecType::iterator E,
 189                                     ConstCandVecType::iterator &MaxCostItr);
 190   // If BaseGV is nullptr, find base among Constant Integer candidates;
 191   // otherwise find base among constant GEPs sharing BaseGV as base pointer.
 192   void findBaseConstants(GlobalVariable *BaseGV);
 193   void emitBaseConstants(Instruction *Base, Constant *Offset, Type *Ty,
 194                          const consthoist::ConstantUser &ConstUser);
 195   // If BaseGV is nullptr, emit Constant Integer base; otherwise emit
 196   // constant GEP base.
 197   bool emitBaseConstants(GlobalVariable *BaseGV);
 198   void deleteDeadCastInst() const;
 199   bool optimizeConstants(Function &Fn);
 200 };
 201
 202 } // end namespace llvm
 203
 204 #endif // LLVM_TRANSFORMS_SCALAR_CONSTANTHOISTING_H