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