| //===- AggressiveInstCombineInternal.h --------------------------*- C++ -*-===// |
| // |
| // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |
| // See https://llvm.org/LICENSE.txt for license information. |
| // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
| // |
| //===----------------------------------------------------------------------===// |
| // |
| // This file implements the instruction pattern combiner classes. |
| // Currently, it handles pattern expressions for: |
| // * Truncate instruction |
| // |
| //===----------------------------------------------------------------------===// |
| |
| #ifndef LLVM_LIB_TRANSFORMS_AGGRESSIVEINSTCOMBINE_COMBINEINTERNAL_H |
| #define LLVM_LIB_TRANSFORMS_AGGRESSIVEINSTCOMBINE_COMBINEINTERNAL_H |
| |
| #include "llvm/ADT/MapVector.h" |
| #include "llvm/ADT/SmallVector.h" |
| #include "llvm/Analysis/ValueTracking.h" |
| #include "llvm/Support/KnownBits.h" |
| |
| using namespace llvm; |
| |
| //===----------------------------------------------------------------------===// |
| // TruncInstCombine - looks for expression graphs dominated by trunc |
| // instructions and for each eligible graph, it will create a reduced bit-width |
| // expression and replace the old expression with this new one and remove the |
| // old one. Eligible expression graph is such that: |
| // 1. Contains only supported instructions. |
| // 2. Supported leaves: ZExtInst, SExtInst, TruncInst and Constant value. |
| // 3. Can be evaluated into type with reduced legal bit-width (or Trunc type). |
| // 4. All instructions in the graph must not have users outside the graph. |
| // Only exception is for {ZExt, SExt}Inst with operand type equal to the |
| // new reduced type chosen in (3). |
| // |
| // The motivation for this optimization is that evaluating and expression using |
| // smaller bit-width is preferable, especially for vectorization where we can |
| // fit more values in one vectorized instruction. In addition, this optimization |
| // may decrease the number of cast instructions, but will not increase it. |
| //===----------------------------------------------------------------------===// |
| |
| namespace llvm { |
| class AssumptionCache; |
| class DataLayout; |
| class DominatorTree; |
| class Function; |
| class Instruction; |
| class TargetLibraryInfo; |
| class TruncInst; |
| class Type; |
| class Value; |
| |
| class TruncInstCombine { |
| AssumptionCache ∾ |
| TargetLibraryInfo &TLI; |
| const DataLayout &DL; |
| const DominatorTree &DT; |
| |
| /// List of all TruncInst instructions to be processed. |
| SmallVector<TruncInst *, 4> Worklist; |
| |
| /// Current processed TruncInst instruction. |
| TruncInst *CurrentTruncInst = nullptr; |
| |
| /// Information per each instruction in the expression graph. |
| struct Info { |
| /// Number of LSBs that are needed to generate a valid expression. |
| unsigned ValidBitWidth = 0; |
| /// Minimum number of LSBs needed to generate the ValidBitWidth. |
| unsigned MinBitWidth = 0; |
| /// The reduced value generated to replace the old instruction. |
| Value *NewValue = nullptr; |
| }; |
| /// An ordered map representing expression graph post-dominated by current |
| /// processed TruncInst. It maps each instruction in the graph to its Info |
| /// structure. The map is ordered such that each instruction appears before |
| /// all other instructions in the graph that uses it. |
| MapVector<Instruction *, Info> InstInfoMap; |
| |
| public: |
| TruncInstCombine(AssumptionCache &AC, TargetLibraryInfo &TLI, |
| const DataLayout &DL, const DominatorTree &DT) |
| : AC(AC), TLI(TLI), DL(DL), DT(DT) {} |
| |
| /// Perform TruncInst pattern optimization on given function. |
| bool run(Function &F); |
| |
| private: |
| /// Build expression graph dominated by the /p CurrentTruncInst and append it |
| /// to the InstInfoMap container. |
| /// |
| /// \return true only if succeed to generate an eligible sub expression graph. |
| bool buildTruncExpressionGraph(); |
| |
| /// Calculate the minimal allowed bit-width of the chain ending with the |
| /// currently visited truncate's operand. |
| /// |
| /// \return minimum number of bits to which the chain ending with the |
| /// truncate's operand can be shrunk to. |
| unsigned getMinBitWidth(); |
| |
| /// Build an expression graph dominated by the current processed TruncInst and |
| /// Check if it is eligible to be reduced to a smaller type. |
| /// |
| /// \return the scalar version of the new type to be used for the reduced |
| /// expression graph, or nullptr if the expression graph is not |
| /// eligible to be reduced. |
| Type *getBestTruncatedType(); |
| |
| KnownBits computeKnownBits(const Value *V) const { |
| return llvm::computeKnownBits(V, DL, /*Depth=*/0, &AC, |
| /*CtxI=*/cast<Instruction>(CurrentTruncInst), |
| &DT); |
| } |
| |
| unsigned ComputeNumSignBits(const Value *V) const { |
| return llvm::ComputeNumSignBits( |
| V, DL, /*Depth=*/0, &AC, /*CtxI=*/cast<Instruction>(CurrentTruncInst), |
| &DT); |
| } |
| |
| /// Given a \p V value and a \p SclTy scalar type return the generated reduced |
| /// value of \p V based on the type \p SclTy. |
| /// |
| /// \param V value to be reduced. |
| /// \param SclTy scalar version of new type to reduce to. |
| /// \return the new reduced value. |
| Value *getReducedOperand(Value *V, Type *SclTy); |
| |
| /// Create a new expression graph using the reduced /p SclTy type and replace |
| /// the old expression graph with it. Also erase all instructions in the old |
| /// graph, except those that are still needed outside the graph. |
| /// |
| /// \param SclTy scalar version of new type to reduce expression graph into. |
| void ReduceExpressionGraph(Type *SclTy); |
| }; |
| } // end namespace llvm. |
| |
| #endif |