LLVM  14.0.0git
AggressiveInstCombineInternal.h
Go to the documentation of this file.
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"
21 #include "llvm/Support/KnownBits.h"
22 
23 using namespace llvm;
24 
25 //===----------------------------------------------------------------------===//
26 // TruncInstCombine - looks for expression dags dominated by trunc instructions
27 // and for each eligible dag, it will create a reduced bit-width expression and
28 // replace the old expression with this new one and remove the old one.
29 // Eligible expression dag is such that:
30 // 1. Contains only supported instructions.
31 // 2. Supported leaves: ZExtInst, SExtInst, TruncInst and Constant value.
32 // 3. Can be evaluated into type with reduced legal bit-width (or Trunc type).
33 // 4. All instructions in the dag must not have users outside the dag.
34 // Only exception is for {ZExt, SExt}Inst with operand type equal to the
35 // new reduced type chosen in (3).
36 //
37 // The motivation for this optimization is that evaluating and expression using
38 // smaller bit-width is preferable, especially for vectorization where we can
39 // fit more values in one vectorized instruction. In addition, this optimization
40 // may decrease the number of cast instructions, but will not increase it.
41 //===----------------------------------------------------------------------===//
42 
43 namespace llvm {
44 class AssumptionCache;
45 class DataLayout;
46 class DominatorTree;
47 class Function;
48 class Instruction;
49 class TargetLibraryInfo;
50 class TruncInst;
51 class Type;
52 class Value;
53 
55  AssumptionCache ∾
56  TargetLibraryInfo &TLI;
57  const DataLayout &DL;
58  const DominatorTree &DT;
59 
60  /// List of all TruncInst instructions to be processed.
62 
63  /// Current processed TruncInst instruction.
64  TruncInst *CurrentTruncInst;
65 
66  /// Information per each instruction in the expression dag.
67  struct Info {
68  /// Number of LSBs that are needed to generate a valid expression.
69  unsigned ValidBitWidth = 0;
70  /// Minimum number of LSBs needed to generate the ValidBitWidth.
71  unsigned MinBitWidth = 0;
72  /// The reduced value generated to replace the old instruction.
73  Value *NewValue = nullptr;
74  };
75  /// An ordered map representing expression dag post-dominated by current
76  /// processed TruncInst. It maps each instruction in the dag to its Info
77  /// structure. The map is ordered such that each instruction appears before
78  /// all other instructions in the dag that uses it.
80 
81 public:
83  const DataLayout &DL, const DominatorTree &DT)
84  : AC(AC), TLI(TLI), DL(DL), DT(DT), CurrentTruncInst(nullptr) {}
85 
86  /// Perform TruncInst pattern optimization on given function.
87  bool run(Function &F);
88 
89 private:
90  /// Build expression dag dominated by the /p CurrentTruncInst and append it to
91  /// the InstInfoMap container.
92  ///
93  /// \return true only if succeed to generate an eligible sub expression dag.
94  bool buildTruncExpressionDag();
95 
96  /// Calculate the minimal allowed bit-width of the chain ending with the
97  /// currently visited truncate's operand.
98  ///
99  /// \return minimum number of bits to which the chain ending with the
100  /// truncate's operand can be shrunk to.
101  unsigned getMinBitWidth();
102 
103  /// Build an expression dag dominated by the current processed TruncInst and
104  /// Check if it is eligible to be reduced to a smaller type.
105  ///
106  /// \return the scalar version of the new type to be used for the reduced
107  /// expression dag, or nullptr if the expression dag is not eligible
108  /// to be reduced.
109  Type *getBestTruncatedType();
110 
111  KnownBits computeKnownBits(const Value *V) const {
112  return llvm::computeKnownBits(V, DL, /*Depth=*/0, &AC,
113  /*CtxI=*/cast<Instruction>(CurrentTruncInst),
114  &DT);
115  }
116 
117  unsigned ComputeNumSignBits(const Value *V) const {
119  V, DL, /*Depth=*/0, &AC, /*CtxI=*/cast<Instruction>(CurrentTruncInst),
120  &DT);
121  }
122 
123  /// Given a \p V value and a \p SclTy scalar type return the generated reduced
124  /// value of \p V based on the type \p SclTy.
125  ///
126  /// \param V value to be reduced.
127  /// \param SclTy scalar version of new type to reduce to.
128  /// \return the new reduced value.
129  Value *getReducedOperand(Value *V, Type *SclTy);
130 
131  /// Create a new expression dag using the reduced /p SclTy type and replace
132  /// the old expression dag with it. Also erase all instructions in the old
133  /// dag, except those that are still needed outside the dag.
134  ///
135  /// \param SclTy scalar version of new type to reduce expression dag into.
136  void ReduceExpressionDag(Type *SclTy);
137 };
138 } // end namespace llvm.
139 
140 #endif
llvm
This file implements support for optimizing divisions by a constant.
Definition: AllocatorList.h:23
llvm::DataLayout
A parsed version of the target data layout string in and methods for querying it.
Definition: DataLayout.h:113
llvm::TruncInstCombine::TruncInstCombine
TruncInstCombine(AssumptionCache &AC, TargetLibraryInfo &TLI, const DataLayout &DL, const DominatorTree &DT)
Definition: AggressiveInstCombineInternal.h:82
llvm::Function
Definition: Function.h:62
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1168
MapVector.h
ValueTracking.h
llvm::DominatorTree
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:151
llvm::Type
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:45
llvm::MapVector
This class implements a map that also provides access to all stored values in a deterministic order.
Definition: MapVector.h:37
llvm::ComputeNumSignBits
unsigned ComputeNumSignBits(const Value *Op, const DataLayout &DL, unsigned Depth=0, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, bool UseInstrInfo=true)
Return the number of times the sign bit of the register is replicated into the other bits.
Definition: ValueTracking.cpp:380
F
#define F(x, y, z)
Definition: MD5.cpp:56
llvm::TruncInstCombine::run
bool run(Function &F)
Perform TruncInst pattern optimization on given function.
Definition: TruncInstCombine.cpp:487
KnownBits.h
llvm::TruncInstCombine
Definition: AggressiveInstCombineInternal.h:54
llvm::Instruction
Definition: Instruction.h:45
Info
Analysis containing CSE Info
Definition: CSEInfo.cpp:27
llvm::TruncInst
This class represents a truncation of integer types.
Definition: Instructions.h:4753
llvm::computeKnownBits
void computeKnownBits(const Value *V, KnownBits &Known, const DataLayout &DL, unsigned Depth=0, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, OptimizationRemarkEmitter *ORE=nullptr, bool UseInstrInfo=true)
Determine which bits of V are known to be either zero or one and return them in the KnownZero/KnownOn...
Definition: ValueTracking.cpp:213
llvm::AssumptionCache
A cache of @llvm.assume calls within a function.
Definition: AssumptionCache.h:41
DL
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
Definition: AArch64SLSHardening.cpp:76
llvm::KnownBits
Definition: KnownBits.h:23
llvm::TargetLibraryInfo
Provides information about what library functions are available for the current target.
Definition: TargetLibraryInfo.h:221
SmallVector.h
llvm::Value
LLVM Value Representation.
Definition: Value.h:74