10b57cec5SDimitry Andric //===- AggressiveInstCombineInternal.h --------------------------*- C++ -*-===// 20b57cec5SDimitry Andric // 30b57cec5SDimitry Andric // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 40b57cec5SDimitry Andric // See https://llvm.org/LICENSE.txt for license information. 50b57cec5SDimitry Andric // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 60b57cec5SDimitry Andric // 70b57cec5SDimitry Andric //===----------------------------------------------------------------------===// 80b57cec5SDimitry Andric // 90b57cec5SDimitry Andric // This file implements the instruction pattern combiner classes. 100b57cec5SDimitry Andric // Currently, it handles pattern expressions for: 110b57cec5SDimitry Andric // * Truncate instruction 120b57cec5SDimitry Andric // 130b57cec5SDimitry Andric //===----------------------------------------------------------------------===// 140b57cec5SDimitry Andric 150b57cec5SDimitry Andric #ifndef LLVM_LIB_TRANSFORMS_AGGRESSIVEINSTCOMBINE_COMBINEINTERNAL_H 160b57cec5SDimitry Andric #define LLVM_LIB_TRANSFORMS_AGGRESSIVEINSTCOMBINE_COMBINEINTERNAL_H 170b57cec5SDimitry Andric 180b57cec5SDimitry Andric #include "llvm/ADT/MapVector.h" 195ffd83dbSDimitry Andric #include "llvm/ADT/SmallVector.h" 20349cc55cSDimitry Andric #include "llvm/Analysis/ValueTracking.h" 21349cc55cSDimitry Andric #include "llvm/Support/KnownBits.h" 225ffd83dbSDimitry Andric 230b57cec5SDimitry Andric using namespace llvm; 240b57cec5SDimitry Andric 250b57cec5SDimitry Andric //===----------------------------------------------------------------------===// 2681ad6265SDimitry Andric // TruncInstCombine - looks for expression graphs dominated by trunc 2781ad6265SDimitry Andric // instructions and for each eligible graph, it will create a reduced bit-width 2881ad6265SDimitry Andric // expression and replace the old expression with this new one and remove the 2981ad6265SDimitry Andric // old one. Eligible expression graph is such that: 300b57cec5SDimitry Andric // 1. Contains only supported instructions. 310b57cec5SDimitry Andric // 2. Supported leaves: ZExtInst, SExtInst, TruncInst and Constant value. 320b57cec5SDimitry Andric // 3. Can be evaluated into type with reduced legal bit-width (or Trunc type). 3381ad6265SDimitry Andric // 4. All instructions in the graph must not have users outside the graph. 340b57cec5SDimitry Andric // Only exception is for {ZExt, SExt}Inst with operand type equal to the 350b57cec5SDimitry Andric // new reduced type chosen in (3). 360b57cec5SDimitry Andric // 370b57cec5SDimitry Andric // The motivation for this optimization is that evaluating and expression using 380b57cec5SDimitry Andric // smaller bit-width is preferable, especially for vectorization where we can 390b57cec5SDimitry Andric // fit more values in one vectorized instruction. In addition, this optimization 400b57cec5SDimitry Andric // may decrease the number of cast instructions, but will not increase it. 410b57cec5SDimitry Andric //===----------------------------------------------------------------------===// 420b57cec5SDimitry Andric 430b57cec5SDimitry Andric namespace llvm { 44349cc55cSDimitry Andric class AssumptionCache; 450b57cec5SDimitry Andric class DataLayout; 460b57cec5SDimitry Andric class DominatorTree; 475ffd83dbSDimitry Andric class Function; 485ffd83dbSDimitry Andric class Instruction; 490b57cec5SDimitry Andric class TargetLibraryInfo; 505ffd83dbSDimitry Andric class TruncInst; 515ffd83dbSDimitry Andric class Type; 525ffd83dbSDimitry Andric class Value; 530b57cec5SDimitry Andric 540b57cec5SDimitry Andric class TruncInstCombine { 55349cc55cSDimitry Andric AssumptionCache &AC; 560b57cec5SDimitry Andric TargetLibraryInfo &TLI; 570b57cec5SDimitry Andric const DataLayout &DL; 580b57cec5SDimitry Andric const DominatorTree &DT; 590b57cec5SDimitry Andric 600b57cec5SDimitry Andric /// List of all TruncInst instructions to be processed. 610b57cec5SDimitry Andric SmallVector<TruncInst *, 4> Worklist; 620b57cec5SDimitry Andric 630b57cec5SDimitry Andric /// Current processed TruncInst instruction. 6481ad6265SDimitry Andric TruncInst *CurrentTruncInst = nullptr; 650b57cec5SDimitry Andric 6681ad6265SDimitry Andric /// Information per each instruction in the expression graph. 670b57cec5SDimitry Andric struct Info { 680b57cec5SDimitry Andric /// Number of LSBs that are needed to generate a valid expression. 690b57cec5SDimitry Andric unsigned ValidBitWidth = 0; 700b57cec5SDimitry Andric /// Minimum number of LSBs needed to generate the ValidBitWidth. 710b57cec5SDimitry Andric unsigned MinBitWidth = 0; 720b57cec5SDimitry Andric /// The reduced value generated to replace the old instruction. 730b57cec5SDimitry Andric Value *NewValue = nullptr; 740b57cec5SDimitry Andric }; 7581ad6265SDimitry Andric /// An ordered map representing expression graph post-dominated by current 7681ad6265SDimitry Andric /// processed TruncInst. It maps each instruction in the graph to its Info 770b57cec5SDimitry Andric /// structure. The map is ordered such that each instruction appears before 7881ad6265SDimitry Andric /// all other instructions in the graph that uses it. 790b57cec5SDimitry Andric MapVector<Instruction *, Info> InstInfoMap; 800b57cec5SDimitry Andric 810b57cec5SDimitry Andric public: TruncInstCombine(AssumptionCache & AC,TargetLibraryInfo & TLI,const DataLayout & DL,const DominatorTree & DT)82349cc55cSDimitry Andric TruncInstCombine(AssumptionCache &AC, TargetLibraryInfo &TLI, 83349cc55cSDimitry Andric const DataLayout &DL, const DominatorTree &DT) 8481ad6265SDimitry Andric : AC(AC), TLI(TLI), DL(DL), DT(DT) {} 850b57cec5SDimitry Andric 860b57cec5SDimitry Andric /// Perform TruncInst pattern optimization on given function. 870b57cec5SDimitry Andric bool run(Function &F); 880b57cec5SDimitry Andric 890b57cec5SDimitry Andric private: 9081ad6265SDimitry Andric /// Build expression graph dominated by the /p CurrentTruncInst and append it 9181ad6265SDimitry Andric /// to the InstInfoMap container. 920b57cec5SDimitry Andric /// 9381ad6265SDimitry Andric /// \return true only if succeed to generate an eligible sub expression graph. 9481ad6265SDimitry Andric bool buildTruncExpressionGraph(); 950b57cec5SDimitry Andric 960b57cec5SDimitry Andric /// Calculate the minimal allowed bit-width of the chain ending with the 970b57cec5SDimitry Andric /// currently visited truncate's operand. 980b57cec5SDimitry Andric /// 990b57cec5SDimitry Andric /// \return minimum number of bits to which the chain ending with the 1000b57cec5SDimitry Andric /// truncate's operand can be shrunk to. 1010b57cec5SDimitry Andric unsigned getMinBitWidth(); 1020b57cec5SDimitry Andric 10381ad6265SDimitry Andric /// Build an expression graph dominated by the current processed TruncInst and 1040b57cec5SDimitry Andric /// Check if it is eligible to be reduced to a smaller type. 1050b57cec5SDimitry Andric /// 1060b57cec5SDimitry Andric /// \return the scalar version of the new type to be used for the reduced 10781ad6265SDimitry Andric /// expression graph, or nullptr if the expression graph is not 10881ad6265SDimitry Andric /// eligible to be reduced. 1090b57cec5SDimitry Andric Type *getBestTruncatedType(); 1100b57cec5SDimitry Andric computeKnownBits(const Value * V)111349cc55cSDimitry Andric KnownBits computeKnownBits(const Value *V) const { 112349cc55cSDimitry Andric return llvm::computeKnownBits(V, DL, /*Depth=*/0, &AC, 113349cc55cSDimitry Andric /*CtxI=*/cast<Instruction>(CurrentTruncInst), 114349cc55cSDimitry Andric &DT); 115349cc55cSDimitry Andric } 116349cc55cSDimitry Andric ComputeNumSignBits(const Value * V)117349cc55cSDimitry Andric unsigned ComputeNumSignBits(const Value *V) const { 118349cc55cSDimitry Andric return llvm::ComputeNumSignBits( 119349cc55cSDimitry Andric V, DL, /*Depth=*/0, &AC, /*CtxI=*/cast<Instruction>(CurrentTruncInst), 120349cc55cSDimitry Andric &DT); 121349cc55cSDimitry Andric } 122349cc55cSDimitry Andric 1230b57cec5SDimitry Andric /// Given a \p V value and a \p SclTy scalar type return the generated reduced 1240b57cec5SDimitry Andric /// value of \p V based on the type \p SclTy. 1250b57cec5SDimitry Andric /// 1260b57cec5SDimitry Andric /// \param V value to be reduced. 1270b57cec5SDimitry Andric /// \param SclTy scalar version of new type to reduce to. 1280b57cec5SDimitry Andric /// \return the new reduced value. 1290b57cec5SDimitry Andric Value *getReducedOperand(Value *V, Type *SclTy); 1300b57cec5SDimitry Andric 13181ad6265SDimitry Andric /// Create a new expression graph using the reduced /p SclTy type and replace 13281ad6265SDimitry Andric /// the old expression graph with it. Also erase all instructions in the old 13381ad6265SDimitry Andric /// graph, except those that are still needed outside the graph. 1340b57cec5SDimitry Andric /// 13581ad6265SDimitry Andric /// \param SclTy scalar version of new type to reduce expression graph into. 13681ad6265SDimitry Andric void ReduceExpressionGraph(Type *SclTy); 1370b57cec5SDimitry Andric }; 1380b57cec5SDimitry Andric } // end namespace llvm. 1390b57cec5SDimitry Andric 1400b57cec5SDimitry Andric #endif 141