contrib/llvm/lib/Transforms/AggressiveInstCombine/AggressiveInstCombineInternal.h

   1 //===- AggressiveInstCombineInternal.h --------------------------*- 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 file implements the instruction pattern combiner classes.
  11 // Currently, it handles pattern expressions for:
  12 //  * Truncate instruction
  13 //
  14 //===----------------------------------------------------------------------===//
  15
  16 #include "llvm/ADT/MapVector.h"
  17 #include "llvm/ADT/STLExtras.h"
  18 #include "llvm/Analysis/AliasAnalysis.h"
  19 #include "llvm/Analysis/BasicAliasAnalysis.h"
  20 #include "llvm/Analysis/ConstantFolding.h"
  21 #include "llvm/Analysis/GlobalsModRef.h"
  22 #include "llvm/Analysis/TargetLibraryInfo.h"
  23 #include "llvm/IR/DataLayout.h"
  24 #include "llvm/Pass.h"
  25 using namespace llvm;
  26
  27 //===----------------------------------------------------------------------===//
  28 // TruncInstCombine - looks for expression dags dominated by trunc instructions
  29 // and for each eligible dag, it will create a reduced bit-width expression and
  30 // replace the old expression with this new one and remove the old one.
  31 // Eligible expression dag is such that:
  32 //   1. Contains only supported instructions.
  33 //   2. Supported leaves: ZExtInst, SExtInst, TruncInst and Constant value.
  34 //   3. Can be evaluated into type with reduced legal bit-width (or Trunc type).
  35 //   4. All instructions in the dag must not have users outside the dag.
  36 //      Only exception is for {ZExt, SExt}Inst with operand type equal to the
  37 //      new reduced type chosen in (3).
  38 //
  39 // The motivation for this optimization is that evaluating and expression using
  40 // smaller bit-width is preferable, especially for vectorization where we can
  41 // fit more values in one vectorized instruction. In addition, this optimization
  42 // may decrease the number of cast instructions, but will not increase it.
  43 //===----------------------------------------------------------------------===//
  44
  45 namespace llvm {
  46   class DataLayout;
  47   class DominatorTree;
  48   class TargetLibraryInfo;
  49
  50 class TruncInstCombine {
  51   TargetLibraryInfo &TLI;
  52   const DataLayout &DL;
  53   const DominatorTree &DT;
  54
  55   /// List of all TruncInst instructions to be processed.
  56   SmallVector<TruncInst *, 4> Worklist;
  57
  58   /// Current processed TruncInst instruction.
  59   TruncInst *CurrentTruncInst;
  60
  61   /// Information per each instruction in the expression dag.
  62   struct Info {
  63     /// Number of LSBs that are needed to generate a valid expression.
  64     unsigned ValidBitWidth = 0;
  65     /// Minimum number of LSBs needed to generate the ValidBitWidth.
  66     unsigned MinBitWidth = 0;
  67     /// The reduced value generated to replace the old instruction.
  68     Value *NewValue = nullptr;
  69   };
  70   /// An ordered map representing expression dag post-dominated by current
  71   /// processed TruncInst. It maps each instruction in the dag to its Info
  72   /// structure. The map is ordered such that each instruction appears before
  73   /// all other instructions in the dag that uses it.
  74   MapVector<Instruction *, Info> InstInfoMap;
  75
  76 public:
  77   TruncInstCombine(TargetLibraryInfo &TLI, const DataLayout &DL,
  78                    const DominatorTree &DT)
  79       : TLI(TLI), DL(DL), DT(DT), CurrentTruncInst(nullptr) {}
  80
  81   /// Perform TruncInst pattern optimization on given function.
  82   bool run(Function &F);
  83
  84 private:
  85   /// Build expression dag dominated by the /p CurrentTruncInst and append it to
  86   /// the InstInfoMap container.
  87   ///
  88   /// \return true only if succeed to generate an eligible sub expression dag.
  89   bool buildTruncExpressionDag();
  90
  91   /// Calculate the minimal allowed bit-width of the chain ending with the
  92   /// currently visited truncate's operand.
  93   ///
  94   /// \return minimum number of bits to which the chain ending with the
  95   /// truncate's operand can be shrunk to.
  96   unsigned getMinBitWidth();
  97
  98   /// Build an expression dag dominated by the current processed TruncInst and
  99   /// Check if it is eligible to be reduced to a smaller type.
 100   ///
 101   /// \return the scalar version of the new type to be used for the reduced
 102   ///         expression dag, or nullptr if the expression dag is not eligible
 103   ///         to be reduced.
 104   Type *getBestTruncatedType();
 105
 106   /// Given a \p V value and a \p SclTy scalar type return the generated reduced
 107   /// value of \p V based on the type \p SclTy.
 108   ///
 109   /// \param V value to be reduced.
 110   /// \param SclTy scalar version of new type to reduce to.
 111   /// \return the new reduced value.
 112   Value *getReducedOperand(Value *V, Type *SclTy);
 113
 114   /// Create a new expression dag using the reduced /p SclTy type and replace
 115   /// the old expression dag with it. Also erase all instructions in the old
 116   /// dag, except those that are still needed outside the dag.
 117   ///
 118   /// \param SclTy scalar version of new type to reduce expression dag into.
 119   void ReduceExpressionDag(Type *SclTy);
 120 };
 121 } // end namespace llvm.