LCOV - code coverage report
Current view: top level - include/llvm/Transforms/Scalar - ConstantHoisting.h (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 16 16 100.0 %
Date: 2018-09-23 13:06:45 Functions: 1 1 100.0 %
Legend: Lines: hit not hit

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

Generated by: LCOV version 1.13