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