Transforms/Scalar/ConstantHoisting.h

0001 //==- ConstantHoisting.h - Prepare code for expensive constants --*- C++ -*-==//
0002 //
0003 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
0004 // See https://llvm.org/LICENSE.txt for license information.
0005 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
0006 //
0007 //===----------------------------------------------------------------------===//
0008 //
0009 // This pass identifies expensive constants to hoist and coalesces them to
0010 // better prepare it for SelectionDAG-based code generation. This works around
0011 // the limitations of the basic-block-at-a-time approach.
0012 //
0013 // First it scans all instructions for integer constants and calculates its
0014 // cost. If the constant can be folded into the instruction (the cost is
0015 // TCC_Free) or the cost is just a simple operation (TCC_BASIC), then we don't
0016 // consider it expensive and leave it alone. This is the default behavior and
0017 // the default implementation of getIntImmCostInst will always return TCC_Free.
0018 //
0019 // If the cost is more than TCC_BASIC, then the integer constant can't be folded
0020 // into the instruction and it might be beneficial to hoist the constant.
0021 // Similar constants are coalesced to reduce register pressure and
0022 // materialization code.
0023 //
0024 // When a constant is hoisted, it is also hidden behind a bitcast to force it to
0025 // be live-out of the basic block. Otherwise the constant would be just
0026 // duplicated and each basic block would have its own copy in the SelectionDAG.
0027 // The SelectionDAG recognizes such constants as opaque and doesn't perform
0028 // certain transformations on them, which would create a new expensive constant.
0029 //
0030 // This optimization is only applied to integer constants in instructions and
0031 // simple (this means not nested) constant cast expressions. For example:
0032 // %0 = load i64* inttoptr (i64 big_constant to i64*)
0033 //
0034 //===----------------------------------------------------------------------===//
0035
0036 #ifndef LLVM_TRANSFORMS_SCALAR_CONSTANTHOISTING_H
0037 #define LLVM_TRANSFORMS_SCALAR_CONSTANTHOISTING_H
0038
0039 #include "llvm/ADT/ArrayRef.h"
0040 #include "llvm/ADT/DenseMap.h"
0041 #include "llvm/ADT/MapVector.h"
0042 #include "llvm/ADT/PointerUnion.h"
0043 #include "llvm/ADT/SetVector.h"
0044 #include "llvm/ADT/SmallVector.h"
0045 #include "llvm/IR/BasicBlock.h"
0046 #include "llvm/IR/PassManager.h"
0047 #include <algorithm>
0048 #include <vector>
0049
0050 namespace llvm {
0051
0052 class BasicBlock;
0053 class BlockFrequencyInfo;
0054 class Constant;
0055 class ConstantInt;
0056 class ConstantExpr;
0057 class DominatorTree;
0058 class Function;
0059 class GlobalVariable;
0060 class Instruction;
0061 class ProfileSummaryInfo;
0062 class TargetTransformInfo;
0063 class TargetTransformInfo;
0064
0065 /// A private "module" namespace for types and utilities used by
0066 /// ConstantHoisting. These are implementation details and should not be used by
0067 /// clients.
0068 namespace consthoist {
0069
0070 /// Keeps track of the user of a constant and the operand index where the
0071 /// constant is used.
0072 struct ConstantUser {
0073   Instruction *Inst;
0074   unsigned OpndIdx;
0075
0076   ConstantUser(Instruction *Inst, unsigned Idx) : Inst(Inst), OpndIdx(Idx) {}
0077 };
0078
0079 using ConstantUseListType = SmallVector<ConstantUser, 8>;
0080
0081 /// Keeps track of a constant candidate and its uses.
0082 struct ConstantCandidate {
0083   ConstantUseListType Uses;
0084   // If the candidate is a ConstantExpr (currely only constant GEP expressions
0085   // whose base pointers are GlobalVariables are supported), ConstInt records
0086   // its offset from the base GV, ConstExpr tracks the candidate GEP expr.
0087   ConstantInt *ConstInt;
0088   ConstantExpr *ConstExpr;
0089   unsigned CumulativeCost = 0;
0090
0091   ConstantCandidate(ConstantInt *ConstInt, ConstantExpr *ConstExpr=nullptr) :
0092       ConstInt(ConstInt), ConstExpr(ConstExpr) {}
0093
0094   /// Add the user to the use list and update the cost.
0095   void addUser(Instruction *Inst, unsigned Idx, unsigned Cost) {
0096     CumulativeCost += Cost;
0097     Uses.push_back(ConstantUser(Inst, Idx));
0098   }
0099 };
0100
0101 /// This represents a constant that has been rebased with respect to a
0102 /// base constant. The difference to the base constant is recorded in Offset.
0103 struct RebasedConstantInfo {
0104   ConstantUseListType Uses;
0105   Constant *Offset;
0106   Type *Ty;
0107
0108   RebasedConstantInfo(ConstantUseListType &&Uses, Constant *Offset,
0109       Type *Ty=nullptr) : Uses(std::move(Uses)), Offset(Offset), Ty(Ty) {}
0110 };
0111
0112 using RebasedConstantListType = SmallVector<RebasedConstantInfo, 4>;
0113
0114 /// A base constant and all its rebased constants.
0115 struct ConstantInfo {
0116   // If the candidate is a ConstantExpr (currely only constant GEP expressions
0117   // whose base pointers are GlobalVariables are supported), ConstInt records
0118   // its offset from the base GV, ConstExpr tracks the candidate GEP expr.
0119   ConstantInt *BaseInt;
0120   ConstantExpr *BaseExpr;
0121   RebasedConstantListType RebasedConstants;
0122 };
0123
0124 } // end namespace consthoist
0125
0126 class ConstantHoistingPass : public PassInfoMixin<ConstantHoistingPass> {
0127 public:
0128   PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
0129
0130   // Glue for old PM.
0131   bool runImpl(Function &F, TargetTransformInfo &TTI, DominatorTree &DT,
0132                BlockFrequencyInfo *BFI, BasicBlock &Entry,
0133                ProfileSummaryInfo *PSI);
0134
0135   void cleanup() {
0136     ClonedCastMap.clear();
0137     ConstIntCandVec.clear();
0138     for (auto MapEntry : ConstGEPCandMap)
0139       MapEntry.second.clear();
0140     ConstGEPCandMap.clear();
0141     ConstIntInfoVec.clear();
0142     for (auto MapEntry : ConstGEPInfoMap)
0143       MapEntry.second.clear();
0144     ConstGEPInfoMap.clear();
0145   }
0146
0147 private:
0148   using ConstPtrUnionType = PointerUnion<ConstantInt *, ConstantExpr *>;
0149   using ConstCandMapType = DenseMap<ConstPtrUnionType, unsigned>;
0150
0151   const TargetTransformInfo *TTI;
0152   DominatorTree *DT;
0153   BlockFrequencyInfo *BFI;
0154   LLVMContext *Ctx;
0155   const DataLayout *DL;
0156   BasicBlock *Entry;
0157   ProfileSummaryInfo *PSI;
0158   bool OptForSize;
0159
0160   /// Keeps track of constant candidates found in the function.
0161   using ConstCandVecType = std::vector<consthoist::ConstantCandidate>;
0162   using GVCandVecMapType = MapVector<GlobalVariable *, ConstCandVecType>;
0163   ConstCandVecType ConstIntCandVec;
0164   GVCandVecMapType ConstGEPCandMap;
0165
0166   /// These are the final constants we decided to hoist.
0167   using ConstInfoVecType = SmallVector<consthoist::ConstantInfo, 8>;
0168   using GVInfoVecMapType = MapVector<GlobalVariable *, ConstInfoVecType>;
0169   ConstInfoVecType ConstIntInfoVec;
0170   GVInfoVecMapType ConstGEPInfoMap;
0171
0172   /// Keep track of cast instructions we already cloned.
0173   MapVector<Instruction *, Instruction *> ClonedCastMap;
0174
0175   void collectMatInsertPts(
0176       const consthoist::RebasedConstantListType &RebasedConstants,
0177       SmallVectorImpl<BasicBlock::iterator> &MatInsertPts) const;
0178   BasicBlock::iterator findMatInsertPt(Instruction *Inst,
0179                                        unsigned Idx = ~0U) const;
0180   SetVector<BasicBlock::iterator> findConstantInsertionPoint(
0181       const consthoist::ConstantInfo &ConstInfo,
0182       const ArrayRef<BasicBlock::iterator> MatInsertPts) const;
0183   void collectConstantCandidates(ConstCandMapType &ConstCandMap,
0184                                  Instruction *Inst, unsigned Idx,
0185                                  ConstantInt *ConstInt);
0186   void collectConstantCandidates(ConstCandMapType &ConstCandMap,
0187                                  Instruction *Inst, unsigned Idx,
0188                                  ConstantExpr *ConstExpr);
0189   void collectConstantCandidates(ConstCandMapType &ConstCandMap,
0190                                  Instruction *Inst, unsigned Idx);
0191   void collectConstantCandidates(ConstCandMapType &ConstCandMap,
0192                                  Instruction *Inst);
0193   void collectConstantCandidates(Function &Fn);
0194   void findAndMakeBaseConstant(ConstCandVecType::iterator S,
0195                                ConstCandVecType::iterator E,
0196       SmallVectorImpl<consthoist::ConstantInfo> &ConstInfoVec);
0197   unsigned maximizeConstantsInRange(ConstCandVecType::iterator S,
0198                                     ConstCandVecType::iterator E,
0199                                     ConstCandVecType::iterator &MaxCostItr);
0200   // If BaseGV is nullptr, find base among Constant Integer candidates;
0201   // otherwise find base among constant GEPs sharing BaseGV as base pointer.
0202   void findBaseConstants(GlobalVariable *BaseGV);
0203
0204   /// A ConstantUser grouped with the Type and Constant adjustment. The user
0205   /// will be adjusted by Offset.
0206   struct UserAdjustment {
0207     Constant *Offset;
0208     Type *Ty;
0209     BasicBlock::iterator MatInsertPt;
0210     const consthoist::ConstantUser User;
0211     UserAdjustment(Constant *O, Type *T, BasicBlock::iterator I,
0212                    consthoist::ConstantUser U)
0213         : Offset(O), Ty(T), MatInsertPt(I), User(U) {}
0214   };
0215   void emitBaseConstants(Instruction *Base, UserAdjustment *Adj);
0216   // If BaseGV is nullptr, emit Constant Integer base; otherwise emit
0217   // constant GEP base.
0218   bool emitBaseConstants(GlobalVariable *BaseGV);
0219   void deleteDeadCastInst() const;
0220 };
0221
0222 } // end namespace llvm
0223
0224 #endif // LLVM_TRANSFORMS_SCALAR_CONSTANTHOISTING_H