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