Home | History | Annotate | Download | only in Scalar 
      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 /// \brief 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 /// \brief 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   /// \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.
     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 /// \brief 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
    168