Home | History | Annotate | Line # | Download | only in AggressiveInstCombine 
      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
    125