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 //===----------------------------------------------------------------------===// 24 // TruncInstCombine - looks for expression graphs dominated by trunc 25 // instructions and for each eligible graph, it will create a reduced bit-width 26 // expression and replace the old expression with this new one and remove the 27 // old one. Eligible expression graph 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 graph must not have users outside the graph. 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 AssumptionCache; 43 class DataLayout; 44 class DominatorTree; 45 class Function; 46 class Instruction; 47 class TargetLibraryInfo; 48 class TruncInst; 49 class Type; 50 class Value; 51 52 class TruncInstCombine { 53 AssumptionCache &AC; 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 = nullptr; 63 64 /// Information per each instruction in the expression graph. 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 graph post-dominated by current 74 /// processed TruncInst. It maps each instruction in the graph to its Info 75 /// structure. The map is ordered such that each instruction appears before 76 /// all other instructions in the graph that uses it. 77 MapVector<Instruction *, Info> InstInfoMap; 78 79 public: TruncInstCombine(AssumptionCache & AC,TargetLibraryInfo & TLI,const DataLayout & DL,const DominatorTree & DT)80 TruncInstCombine(AssumptionCache &AC, TargetLibraryInfo &TLI, 81 const DataLayout &DL, const DominatorTree &DT) 82 : AC(AC), TLI(TLI), DL(DL), DT(DT) {} 83 84 /// Perform TruncInst pattern optimization on given function. 85 bool run(Function &F); 86 87 private: 88 /// Build expression graph dominated by the /p CurrentTruncInst and append it 89 /// to the InstInfoMap container. 90 /// 91 /// \return true only if succeed to generate an eligible sub expression graph. 92 bool buildTruncExpressionGraph(); 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 graph 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 graph, or nullptr if the expression graph is not 106 /// eligible to be reduced. 107 Type *getBestTruncatedType(); 108 computeKnownBits(const Value * V)109 KnownBits computeKnownBits(const Value *V) const { 110 return llvm::computeKnownBits(V, DL, &AC, 111 /*CtxI=*/cast<Instruction>(CurrentTruncInst), 112 &DT); 113 } 114 ComputeNumSignBits(const Value * V)115 unsigned ComputeNumSignBits(const Value *V) const { 116 return llvm::ComputeNumSignBits( 117 V, DL, &AC, /*CtxI=*/cast<Instruction>(CurrentTruncInst), &DT); 118 } 119 120 /// Given a \p V value and a \p SclTy scalar type return the generated reduced 121 /// value of \p V based on the type \p SclTy. 122 /// 123 /// \param V value to be reduced. 124 /// \param SclTy scalar version of new type to reduce to. 125 /// \return the new reduced value. 126 Value *getReducedOperand(Value *V, Type *SclTy); 127 128 /// Create a new expression graph using the reduced /p SclTy type and replace 129 /// the old expression graph with it. Also erase all instructions in the old 130 /// graph, except those that are still needed outside the graph. 131 /// 132 /// \param SclTy scalar version of new type to reduce expression graph into. 133 void ReduceExpressionGraph(Type *SclTy); 134 }; 135 } // end namespace llvm. 136 137 #endif // LLVM_LIB_TRANSFORMS_AGGRESSIVEINSTCOMBINE_COMBINEINTERNAL_H 138