LCOV - code coverage report
Current view: top level - include/llvm/Transforms/Scalar - ConstantHoisting.h (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 13 13 100.0 %
Date: 2018-06-17 00:07:59 Functions: 3 3 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/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        2099 :   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        5836 : struct ConstantCandidate {
      76             :   ConstantUseListType Uses;
      77             :   ConstantInt *ConstInt;
      78             :   unsigned CumulativeCost = 0;
      79             : 
      80        2800 :   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        2099 :     CumulativeCost += Cost;
      85        4198 :     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        2358 : struct RebasedConstantInfo {
      92             :   ConstantUseListType Uses;
      93             :   Constant *Offset;
      94             : 
      95             :   RebasedConstantInfo(ConstantUseListType &&Uses, Constant *Offset)
      96         786 :     : 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        1002 : struct ConstantInfo {
     103             :   ConstantInt *BaseConstant;
     104             :   RebasedConstantListType RebasedConstants;
     105             : };
     106             : 
     107             : } // end namespace consthoist
     108             : 
     109       57226 : 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      181673 :   void releaseMemory() {
     118             :     ConstantVec.clear();
     119      181673 :     ClonedCastMap.clear();
     120      181673 :     ConstCandVec.clear();
     121      181673 :   }
     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

Generated by: LCOV version 1.13