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/MapVector.h"
  41 #include "llvm/ADT/PointerUnion.h"
  42 #include "llvm/ADT/SetVector.h"
  43 #include "llvm/ADT/SmallPtrSet.h"
  44 #include "llvm/ADT/SmallVector.h"
  45 #include "llvm/IR/PassManager.h"
  46 #include <algorithm>
  47 #include <vector>
  48
  49 namespace llvm {
  50
  51 class BasicBlock;
  52 class BlockFrequencyInfo;
  53 class Constant;
  54 class ConstantInt;
  55 class ConstantExpr;
  56 class DominatorTree;
  57 class Function;
  58 class GlobalVariable;
  59 class Instruction;
  60 class ProfileSummaryInfo;
  61 class TargetTransformInfo;
  62
  63 /// A private "module" namespace for types and utilities used by
  64 /// ConstantHoisting. These are implementation details and should not be used by
  65 /// clients.
  66 namespace consthoist {
  67
  68 /// Keeps track of the user of a constant and the operand index where the
  69 /// constant is used.
  70 struct ConstantUser {
  71   Instruction *Inst;
  72   unsigned OpndIdx;
  73
  74   ConstantUser(Instruction *Inst, unsigned Idx) : Inst(Inst), OpndIdx(Idx) {}
  75 };
  76
  77 using ConstantUseListType = SmallVector<ConstantUser, 8>;
  78
  79 /// Keeps track of a constant candidate and its uses.
  80 struct ConstantCandidate {
  81   ConstantUseListType Uses;
  82   // If the candidate is a ConstantExpr (currely only constant GEP expressions
  83   // whose base pointers are GlobalVariables are supported), ConstInt records
  84   // its offset from the base GV, ConstExpr tracks the candidate GEP expr.
  85   ConstantInt *ConstInt;
  86   ConstantExpr *ConstExpr;
  87   unsigned CumulativeCost = 0;
  88
  89   ConstantCandidate(ConstantInt *ConstInt, ConstantExpr *ConstExpr=nullptr) :
  90       ConstInt(ConstInt), ConstExpr(ConstExpr) {}
  91
  92   /// Add the user to the use list and update the cost.
  93   void addUser(Instruction *Inst, unsigned Idx, unsigned Cost) {
  94     CumulativeCost += Cost;
  95     Uses.push_back(ConstantUser(Inst, Idx));
  96   }
  97 };
  98
  99 /// This represents a constant that has been rebased with respect to a
 100 /// base constant. The difference to the base constant is recorded in Offset.
 101 struct RebasedConstantInfo {
 102   ConstantUseListType Uses;
 103   Constant *Offset;
 104   Type *Ty;
 105
 106   RebasedConstantInfo(ConstantUseListType &&Uses, Constant *Offset,
 107       Type *Ty=nullptr) : Uses(std::move(Uses)), Offset(Offset), Ty(Ty) {}
 108 };
 109
 110 using RebasedConstantListType = SmallVector<RebasedConstantInfo, 4>;
 111
 112 /// A base constant and all its rebased constants.
 113 struct ConstantInfo {
 114   // If the candidate is a ConstantExpr (currely only constant GEP expressions
 115   // whose base pointers are GlobalVariables are supported), ConstInt records
 116   // its offset from the base GV, ConstExpr tracks the candidate GEP expr.
 117   ConstantInt *BaseInt;
 118   ConstantExpr *BaseExpr;
 119   RebasedConstantListType RebasedConstants;
 120 };
 121
 122 } // end namespace consthoist
 123
 124 class ConstantHoistingPass : public PassInfoMixin<ConstantHoistingPass> {
 125 public:
 126   PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
 127
 128   // Glue for old PM.
 129   bool runImpl(Function &F, TargetTransformInfo &TTI, DominatorTree &DT,
 130                BlockFrequencyInfo *BFI, BasicBlock &Entry,
 131                ProfileSummaryInfo *PSI);
 132
 133   void cleanup() {
 134     ClonedCastMap.clear();
 135     ConstIntCandVec.clear();
 136     for (auto MapEntry : ConstGEPCandMap)
 137       MapEntry.second.clear();
 138     ConstGEPCandMap.clear();
 139     ConstIntInfoVec.clear();
 140     for (auto MapEntry : ConstGEPInfoMap)
 141       MapEntry.second.clear();
 142     ConstGEPInfoMap.clear();
 143   }
 144
 145 private:
 146   using ConstPtrUnionType = PointerUnion<ConstantInt *, ConstantExpr *>;
 147   using ConstCandMapType = DenseMap<ConstPtrUnionType, unsigned>;
 148
 149   const TargetTransformInfo *TTI;
 150   DominatorTree *DT;
 151   BlockFrequencyInfo *BFI;
 152   LLVMContext *Ctx;
 153   const DataLayout *DL;
 154   BasicBlock *Entry;
 155   ProfileSummaryInfo *PSI;
 156
 157   /// Keeps track of constant candidates found in the function.
 158   using ConstCandVecType = std::vector<consthoist::ConstantCandidate>;
 159   using GVCandVecMapType = MapVector<GlobalVariable *, ConstCandVecType>;
 160   ConstCandVecType ConstIntCandVec;
 161   GVCandVecMapType ConstGEPCandMap;
 162
 163   /// These are the final constants we decided to hoist.
 164   using ConstInfoVecType = SmallVector<consthoist::ConstantInfo, 8>;
 165   using GVInfoVecMapType = MapVector<GlobalVariable *, ConstInfoVecType>;
 166   ConstInfoVecType ConstIntInfoVec;
 167   GVInfoVecMapType ConstGEPInfoMap;
 168
 169   /// Keep track of cast instructions we already cloned.
 170   MapVector<Instruction *, Instruction *> ClonedCastMap;
 171
 172   Instruction *findMatInsertPt(Instruction *Inst, unsigned Idx = ~0U) const;
 173   SetVector<Instruction *>
 174   findConstantInsertionPoint(const consthoist::ConstantInfo &ConstInfo) const;
 175   void collectConstantCandidates(ConstCandMapType &ConstCandMap,
 176                                  Instruction *Inst, unsigned Idx,
 177                                  ConstantInt *ConstInt);
 178   void collectConstantCandidates(ConstCandMapType &ConstCandMap,
 179                                  Instruction *Inst, unsigned Idx,
 180                                  ConstantExpr *ConstExpr);
 181   void collectConstantCandidates(ConstCandMapType &ConstCandMap,
 182                                  Instruction *Inst, unsigned Idx);
 183   void collectConstantCandidates(ConstCandMapType &ConstCandMap,
 184                                  Instruction *Inst);
 185   void collectConstantCandidates(Function &Fn);
 186   void findAndMakeBaseConstant(ConstCandVecType::iterator S,
 187                                ConstCandVecType::iterator E,
 188       SmallVectorImpl<consthoist::ConstantInfo> &ConstInfoVec);
 189   unsigned maximizeConstantsInRange(ConstCandVecType::iterator S,
 190                                     ConstCandVecType::iterator E,
 191                                     ConstCandVecType::iterator &MaxCostItr);
 192   // If BaseGV is nullptr, find base among Constant Integer candidates;
 193   // otherwise find base among constant GEPs sharing BaseGV as base pointer.
 194   void findBaseConstants(GlobalVariable *BaseGV);
 195   void emitBaseConstants(Instruction *Base, Constant *Offset, Type *Ty,
 196                          const consthoist::ConstantUser &ConstUser);
 197   // If BaseGV is nullptr, emit Constant Integer base; otherwise emit
 198   // constant GEP base.
 199   bool emitBaseConstants(GlobalVariable *BaseGV);
 200   void deleteDeadCastInst() const;
 201   bool optimizeConstants(Function &Fn);
 202 };
 203
 204 } // end namespace llvm
 205
 206 #endif // LLVM_TRANSFORMS_SCALAR_CONSTANTHOISTING_H