LLVM 20.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"
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
41namespace llvm {
42class AssumptionCache;
43class DataLayout;
44class DominatorTree;
45class Function;
46class Instruction;
47class TargetLibraryInfo;
48class TruncInst;
49class Type;
50class Value;
51
55 const DataLayout &DL;
56 const DominatorTree &DT;
57
58 /// List of all TruncInst instructions to be processed.
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.
78
79public:
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 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
109 KnownBits computeKnownBits(const Value *V) const {
110 return llvm::computeKnownBits(V, DL, /*Depth=*/0, &AC,
111 /*CtxI=*/cast<Instruction>(CurrentTruncInst),
112 &DT);
113 }
114
115 unsigned ComputeNumSignBits(const Value *V) const {
117 V, DL, /*Depth=*/0, &AC, /*CtxI=*/cast<Instruction>(CurrentTruncInst),
118 &DT);
119 }
120
121 /// Given a \p V value and a \p SclTy scalar type return the generated reduced
122 /// value of \p V based on the type \p SclTy.
123 ///
124 /// \param V value to be reduced.
125 /// \param SclTy scalar version of new type to reduce to.
126 /// \return the new reduced value.
127 Value *getReducedOperand(Value *V, Type *SclTy);
128
129 /// Create a new expression graph using the reduced /p SclTy type and replace
130 /// the old expression graph with it. Also erase all instructions in the old
131 /// graph, except those that are still needed outside the graph.
132 ///
133 /// \param SclTy scalar version of new type to reduce expression graph into.
134 void ReduceExpressionGraph(Type *SclTy);
135};
136} // end namespace llvm.
137
138#endif // LLVM_LIB_TRANSFORMS_AGGRESSIVEINSTCOMBINE_COMBINEINTERNAL_H
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
RelocType Type
Definition: COFFYAML.cpp:391
Analysis containing CSE Info
Definition: CSEInfo.cpp:27
#define F(x, y, z)
Definition: MD5.cpp:55
This file implements a map that provides insertion order iteration.
This file defines the SmallVector class.
A cache of @llvm.assume calls within a function.
A parsed version of the target data layout string in and methods for querying it.
Definition: DataLayout.h:63
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:162
This class implements a map that also provides access to all stored values in a deterministic order.
Definition: MapVector.h:36
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1209
Provides information about what library functions are available for the current target.
TruncInstCombine(AssumptionCache &AC, TargetLibraryInfo &TLI, const DataLayout &DL, const DominatorTree &DT)
bool run(Function &F)
Perform TruncInst pattern optimization on given function.
This class represents a truncation of integer types.
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:45
LLVM Value Representation.
Definition: Value.h:74
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
void computeKnownBits(const Value *V, KnownBits &Known, const DataLayout &DL, unsigned Depth=0, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, bool UseInstrInfo=true)
Determine which bits of V are known to be either zero or one and return them in the KnownZero/KnownOn...
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.