1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
|
//===- 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 dags dominated by trunc instructions
// and for each eligible dag, it will create a reduced bit-width expression and
// replace the old expression with this new one and remove the old one.
// Eligible expression dag 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 dag must not have users outside the dag.
// 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;
/// Information per each instruction in the expression dag.
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 dag post-dominated by current
/// processed TruncInst. It maps each instruction in the dag to its Info
/// structure. The map is ordered such that each instruction appears before
/// all other instructions in the dag 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), CurrentTruncInst(nullptr) {}
/// Perform TruncInst pattern optimization on given function.
bool run(Function &F);
private:
/// Build expression dag dominated by the /p CurrentTruncInst and append it to
/// the InstInfoMap container.
///
/// \return true only if succeed to generate an eligible sub expression dag.
bool buildTruncExpressionDag();
/// 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 dag 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 dag, or nullptr if the expression dag 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 dag using the reduced /p SclTy type and replace
/// the old expression dag with it. Also erase all instructions in the old
/// dag, except those that are still needed outside the dag.
///
/// \param SclTy scalar version of new type to reduce expression dag into.
void ReduceExpressionDag(Type *SclTy);
};
} // end namespace llvm.
#endif
|
