contrib/llvm/include/llvm/Transforms/Scalar/ConstantHoisting.h

   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 /// Keeps track of the user of a constant and the operand index where the
  64 /// constant is used.
  65 struct ConstantUser {
  66   Instruction *Inst;
  67   unsigned OpndIdx;
  68
  69   ConstantUser(Instruction *Inst, unsigned Idx) : Inst(Inst), OpndIdx(Idx) {}
  70 };
  71
  72 using ConstantUseListType = SmallVector<ConstantUser, 8>;
  73
  74 /// Keeps track of a constant candidate and its uses.
  75 struct ConstantCandidate {
  76   ConstantUseListType Uses;
  77   ConstantInt *ConstInt;
  78   unsigned CumulativeCost = 0;
  79
  80   ConstantCandidate(ConstantInt *ConstInt) : ConstInt(ConstInt) {}
  81
  82   /// 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 /// 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.
  91 struct RebasedConstantInfo {
  92   ConstantUseListType Uses;
  93   Constant *Offset;
  94
  95   RebasedConstantInfo(ConstantUseListType &&Uses, Constant *Offset)
  96     : Uses(std::move(Uses)), Offset(Offset) {}
  97 };
  98
  99 using RebasedConstantListType = SmallVector<RebasedConstantInfo, 4>;
 100
 101 /// A base constant and all its rebased constants.
 102 struct ConstantInfo {
 103   ConstantInt *BaseConstant;
 104   RebasedConstantListType RebasedConstants;
 105 };
 106
 107 } // end namespace consthoist
 108
 109 class ConstantHoistingPass : public PassInfoMixin<ConstantHoistingPass> {
 110 public:
 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
 123 private:
 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