llvm/lib/Transforms/AggressiveInstCombine/AggressiveInstCombineInternal.h

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