138 lines · c
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-exception6//7//===----------------------------------------------------------------------===//8//9// This file implements the instruction pattern combiner classes.10// Currently, it handles pattern expressions for:11// * Truncate instruction12//13//===----------------------------------------------------------------------===//14 15#ifndef LLVM_LIB_TRANSFORMS_AGGRESSIVEINSTCOMBINE_COMBINEINTERNAL_H16#define LLVM_LIB_TRANSFORMS_AGGRESSIVEINSTCOMBINE_COMBINEINTERNAL_H17 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 trunc25// instructions and for each eligible graph, it will create a reduced bit-width26// expression and replace the old expression with this new one and remove the27// 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 the33// new reduced type chosen in (3).34//35// The motivation for this optimization is that evaluating and expression using36// smaller bit-width is preferable, especially for vectorization where we can37// fit more values in one vectorized instruction. In addition, this optimization38// may decrease the number of cast instructions, but will not increase it.39//===----------------------------------------------------------------------===//40 41namespace llvm {42class AssumptionCache;43class DataLayout;44class DominatorTree;45class Function;46class Instruction;47class TargetLibraryInfo;48class TruncInst;49class Type;50class Value;51 52class 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 current74 /// processed TruncInst. It maps each instruction in the graph to its Info75 /// structure. The map is ordered such that each instruction appears before76 /// all other instructions in the graph that uses it.77 MapVector<Instruction *, Info> InstInfoMap;78 79public: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 87private:88 /// Build expression graph dominated by the /p CurrentTruncInst and append it89 /// 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 the95 /// currently visited truncate's operand.96 ///97 /// \return minimum number of bits to which the chain ending with the98 /// truncate's operand can be shrunk to.99 unsigned getMinBitWidth();100 101 /// Build an expression graph dominated by the current processed TruncInst and102 /// 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 reduced105 /// expression graph, or nullptr if the expression graph is not106 /// eligible to be reduced.107 Type *getBestTruncatedType();108 109 KnownBits computeKnownBits(const Value *V) const {110 return llvm::computeKnownBits(V, DL, &AC,111 /*CtxI=*/cast<Instruction>(CurrentTruncInst),112 &DT);113 }114 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 reduced121 /// 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 replace129 /// the old expression graph with it. Also erase all instructions in the old130 /// 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_H138