1327952Sdim//==- ConstantHoisting.h - Prepare code for expensive constants --*- C++ -*-==// 2303231Sdim// 3353358Sdim// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4353358Sdim// See https://llvm.org/LICENSE.txt for license information. 5353358Sdim// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6303231Sdim// 7303231Sdim//===----------------------------------------------------------------------===// 8303231Sdim// 9303231Sdim// This pass identifies expensive constants to hoist and coalesces them to 10303231Sdim// better prepare it for SelectionDAG-based code generation. This works around 11303231Sdim// the limitations of the basic-block-at-a-time approach. 12303231Sdim// 13303231Sdim// First it scans all instructions for integer constants and calculates its 14303231Sdim// cost. If the constant can be folded into the instruction (the cost is 15303231Sdim// TCC_Free) or the cost is just a simple operation (TCC_BASIC), then we don't 16303231Sdim// consider it expensive and leave it alone. This is the default behavior and 17360784Sdim// the default implementation of getIntImmCostInst will always return TCC_Free. 18303231Sdim// 19303231Sdim// If the cost is more than TCC_BASIC, then the integer constant can't be folded 20303231Sdim// into the instruction and it might be beneficial to hoist the constant. 21303231Sdim// Similar constants are coalesced to reduce register pressure and 22303231Sdim// materialization code. 23303231Sdim// 24303231Sdim// When a constant is hoisted, it is also hidden behind a bitcast to force it to 25303231Sdim// be live-out of the basic block. Otherwise the constant would be just 26303231Sdim// duplicated and each basic block would have its own copy in the SelectionDAG. 27303231Sdim// The SelectionDAG recognizes such constants as opaque and doesn't perform 28303231Sdim// certain transformations on them, which would create a new expensive constant. 29303231Sdim// 30303231Sdim// This optimization is only applied to integer constants in instructions and 31303231Sdim// simple (this means not nested) constant cast expressions. For example: 32303231Sdim// %0 = load i64* inttoptr (i64 big_constant to i64*) 33327952Sdim// 34303231Sdim//===----------------------------------------------------------------------===// 35303231Sdim 36303231Sdim#ifndef LLVM_TRANSFORMS_SCALAR_CONSTANTHOISTING_H 37303231Sdim#define LLVM_TRANSFORMS_SCALAR_CONSTANTHOISTING_H 38303231Sdim 39327952Sdim#include "llvm/ADT/DenseMap.h" 40360784Sdim#include "llvm/ADT/MapVector.h" 41344779Sdim#include "llvm/ADT/PointerUnion.h" 42360784Sdim#include "llvm/ADT/SetVector.h" 43327952Sdim#include "llvm/ADT/SmallPtrSet.h" 44327952Sdim#include "llvm/ADT/SmallVector.h" 45303231Sdim#include "llvm/IR/PassManager.h" 46327952Sdim#include <algorithm> 47327952Sdim#include <vector> 48303231Sdim 49303231Sdimnamespace llvm { 50303231Sdim 51327952Sdimclass BasicBlock; 52327952Sdimclass BlockFrequencyInfo; 53327952Sdimclass Constant; 54327952Sdimclass ConstantInt; 55344779Sdimclass ConstantExpr; 56327952Sdimclass DominatorTree; 57327952Sdimclass Function; 58344779Sdimclass GlobalVariable; 59327952Sdimclass Instruction; 60353358Sdimclass ProfileSummaryInfo; 61327952Sdimclass TargetTransformInfo; 62327952Sdim 63303231Sdim/// A private "module" namespace for types and utilities used by 64303231Sdim/// ConstantHoisting. These are implementation details and should not be used by 65303231Sdim/// clients. 66303231Sdimnamespace consthoist { 67327952Sdim 68341825Sdim/// Keeps track of the user of a constant and the operand index where the 69303231Sdim/// constant is used. 70303231Sdimstruct ConstantUser { 71303231Sdim Instruction *Inst; 72303231Sdim unsigned OpndIdx; 73303231Sdim 74327952Sdim ConstantUser(Instruction *Inst, unsigned Idx) : Inst(Inst), OpndIdx(Idx) {} 75303231Sdim}; 76303231Sdim 77327952Sdimusing ConstantUseListType = SmallVector<ConstantUser, 8>; 78303231Sdim 79341825Sdim/// Keeps track of a constant candidate and its uses. 80303231Sdimstruct ConstantCandidate { 81303231Sdim ConstantUseListType Uses; 82344779Sdim // If the candidate is a ConstantExpr (currely only constant GEP expressions 83344779Sdim // whose base pointers are GlobalVariables are supported), ConstInt records 84344779Sdim // its offset from the base GV, ConstExpr tracks the candidate GEP expr. 85303231Sdim ConstantInt *ConstInt; 86344779Sdim ConstantExpr *ConstExpr; 87327952Sdim unsigned CumulativeCost = 0; 88303231Sdim 89344779Sdim ConstantCandidate(ConstantInt *ConstInt, ConstantExpr *ConstExpr=nullptr) : 90344779Sdim ConstInt(ConstInt), ConstExpr(ConstExpr) {} 91303231Sdim 92341825Sdim /// Add the user to the use list and update the cost. 93303231Sdim void addUser(Instruction *Inst, unsigned Idx, unsigned Cost) { 94303231Sdim CumulativeCost += Cost; 95303231Sdim Uses.push_back(ConstantUser(Inst, Idx)); 96303231Sdim } 97303231Sdim}; 98303231Sdim 99341825Sdim/// This represents a constant that has been rebased with respect to a 100303231Sdim/// base constant. The difference to the base constant is recorded in Offset. 101303231Sdimstruct RebasedConstantInfo { 102303231Sdim ConstantUseListType Uses; 103303231Sdim Constant *Offset; 104344779Sdim Type *Ty; 105303231Sdim 106344779Sdim RebasedConstantInfo(ConstantUseListType &&Uses, Constant *Offset, 107344779Sdim Type *Ty=nullptr) : Uses(std::move(Uses)), Offset(Offset), Ty(Ty) {} 108303231Sdim}; 109303231Sdim 110327952Sdimusing RebasedConstantListType = SmallVector<RebasedConstantInfo, 4>; 111303231Sdim 112341825Sdim/// A base constant and all its rebased constants. 113303231Sdimstruct ConstantInfo { 114344779Sdim // If the candidate is a ConstantExpr (currely only constant GEP expressions 115344779Sdim // whose base pointers are GlobalVariables are supported), ConstInt records 116344779Sdim // its offset from the base GV, ConstExpr tracks the candidate GEP expr. 117344779Sdim ConstantInt *BaseInt; 118344779Sdim ConstantExpr *BaseExpr; 119303231Sdim RebasedConstantListType RebasedConstants; 120303231Sdim}; 121303231Sdim 122327952Sdim} // end namespace consthoist 123327952Sdim 124303231Sdimclass ConstantHoistingPass : public PassInfoMixin<ConstantHoistingPass> { 125303231Sdimpublic: 126303231Sdim PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); 127303231Sdim 128303231Sdim // Glue for old PM. 129303231Sdim bool runImpl(Function &F, TargetTransformInfo &TTI, DominatorTree &DT, 130353358Sdim BlockFrequencyInfo *BFI, BasicBlock &Entry, 131353358Sdim ProfileSummaryInfo *PSI); 132303231Sdim 133353358Sdim void cleanup() { 134303231Sdim ClonedCastMap.clear(); 135344779Sdim ConstIntCandVec.clear(); 136344779Sdim for (auto MapEntry : ConstGEPCandMap) 137344779Sdim MapEntry.second.clear(); 138344779Sdim ConstGEPCandMap.clear(); 139344779Sdim ConstIntInfoVec.clear(); 140344779Sdim for (auto MapEntry : ConstGEPInfoMap) 141344779Sdim MapEntry.second.clear(); 142344779Sdim ConstGEPInfoMap.clear(); 143303231Sdim } 144303231Sdim 145303231Sdimprivate: 146344779Sdim using ConstPtrUnionType = PointerUnion<ConstantInt *, ConstantExpr *>; 147344779Sdim using ConstCandMapType = DenseMap<ConstPtrUnionType, unsigned>; 148303231Sdim 149303231Sdim const TargetTransformInfo *TTI; 150303231Sdim DominatorTree *DT; 151321369Sdim BlockFrequencyInfo *BFI; 152344779Sdim LLVMContext *Ctx; 153344779Sdim const DataLayout *DL; 154303231Sdim BasicBlock *Entry; 155353358Sdim ProfileSummaryInfo *PSI; 156303231Sdim 157303231Sdim /// Keeps track of constant candidates found in the function. 158344779Sdim using ConstCandVecType = std::vector<consthoist::ConstantCandidate>; 159360784Sdim using GVCandVecMapType = MapVector<GlobalVariable *, ConstCandVecType>; 160344779Sdim ConstCandVecType ConstIntCandVec; 161344779Sdim GVCandVecMapType ConstGEPCandMap; 162303231Sdim 163344779Sdim /// These are the final constants we decided to hoist. 164344779Sdim using ConstInfoVecType = SmallVector<consthoist::ConstantInfo, 8>; 165360784Sdim using GVInfoVecMapType = MapVector<GlobalVariable *, ConstInfoVecType>; 166344779Sdim ConstInfoVecType ConstIntInfoVec; 167344779Sdim GVInfoVecMapType ConstGEPInfoMap; 168344779Sdim 169303231Sdim /// Keep track of cast instructions we already cloned. 170360784Sdim MapVector<Instruction *, Instruction *> ClonedCastMap; 171303231Sdim 172303231Sdim Instruction *findMatInsertPt(Instruction *Inst, unsigned Idx = ~0U) const; 173360784Sdim SetVector<Instruction *> 174321369Sdim findConstantInsertionPoint(const consthoist::ConstantInfo &ConstInfo) const; 175303231Sdim void collectConstantCandidates(ConstCandMapType &ConstCandMap, 176303231Sdim Instruction *Inst, unsigned Idx, 177303231Sdim ConstantInt *ConstInt); 178303231Sdim void collectConstantCandidates(ConstCandMapType &ConstCandMap, 179344779Sdim Instruction *Inst, unsigned Idx, 180344779Sdim ConstantExpr *ConstExpr); 181344779Sdim void collectConstantCandidates(ConstCandMapType &ConstCandMap, 182321369Sdim Instruction *Inst, unsigned Idx); 183321369Sdim void collectConstantCandidates(ConstCandMapType &ConstCandMap, 184303231Sdim Instruction *Inst); 185303231Sdim void collectConstantCandidates(Function &Fn); 186303231Sdim void findAndMakeBaseConstant(ConstCandVecType::iterator S, 187344779Sdim ConstCandVecType::iterator E, 188344779Sdim SmallVectorImpl<consthoist::ConstantInfo> &ConstInfoVec); 189303231Sdim unsigned maximizeConstantsInRange(ConstCandVecType::iterator S, 190303231Sdim ConstCandVecType::iterator E, 191303231Sdim ConstCandVecType::iterator &MaxCostItr); 192344779Sdim // If BaseGV is nullptr, find base among Constant Integer candidates; 193344779Sdim // otherwise find base among constant GEPs sharing BaseGV as base pointer. 194344779Sdim void findBaseConstants(GlobalVariable *BaseGV); 195344779Sdim void emitBaseConstants(Instruction *Base, Constant *Offset, Type *Ty, 196303231Sdim const consthoist::ConstantUser &ConstUser); 197344779Sdim // If BaseGV is nullptr, emit Constant Integer base; otherwise emit 198344779Sdim // constant GEP base. 199344779Sdim bool emitBaseConstants(GlobalVariable *BaseGV); 200303231Sdim void deleteDeadCastInst() const; 201303231Sdim bool optimizeConstants(Function &Fn); 202303231Sdim}; 203303231Sdim 204327952Sdim} // end namespace llvm 205327952Sdim 206303231Sdim#endif // LLVM_TRANSFORMS_SCALAR_CONSTANTHOISTING_H 207