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
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
|
#pragma once
#ifdef __GNUC__
#pragma GCC diagnostic push
#pragma GCC diagnostic ignored "-Wunused-parameter"
#endif
//===- llvm/Analysis/DemandedBits.h - Determine demanded bits ---*- 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 pass implements a demanded bits analysis. A demanded bit is one that
// contributes to a result; bits that are not demanded can be either zero or
// one without affecting control or data flow. For example in this sequence:
//
// %1 = add i32 %x, %y
// %2 = trunc i32 %1 to i16
//
// Only the lowest 16 bits of %1 are demanded; the rest are removed by the
// trunc.
//
//===----------------------------------------------------------------------===//
#ifndef LLVM_ANALYSIS_DEMANDEDBITS_H
#define LLVM_ANALYSIS_DEMANDEDBITS_H
#include "llvm/ADT/APInt.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/IR/PassManager.h"
#include "llvm/Pass.h"
#include <optional>
namespace llvm {
class AssumptionCache;
class DominatorTree;
class Function;
class Instruction;
struct KnownBits;
class raw_ostream;
class DemandedBits {
public:
DemandedBits(Function &F, AssumptionCache &AC, DominatorTree &DT) :
F(F), AC(AC), DT(DT) {}
/// Return the bits demanded from instruction I.
///
/// For vector instructions individual vector elements are not distinguished:
/// A bit is demanded if it is demanded for any of the vector elements. The
/// size of the return value corresponds to the type size in bits of the
/// scalar type.
///
/// Instructions that do not have integer or vector of integer type are
/// accepted, but will always produce a mask with all bits set.
APInt getDemandedBits(Instruction *I);
/// Return the bits demanded from use U.
APInt getDemandedBits(Use *U);
/// Return true if, during analysis, I could not be reached.
bool isInstructionDead(Instruction *I);
/// Return whether this use is dead by means of not having any demanded bits.
bool isUseDead(Use *U);
void print(raw_ostream &OS);
/// Compute alive bits of one addition operand from alive output and known
/// operand bits
static APInt determineLiveOperandBitsAdd(unsigned OperandNo,
const APInt &AOut,
const KnownBits &LHS,
const KnownBits &RHS);
/// Compute alive bits of one subtraction operand from alive output and known
/// operand bits
static APInt determineLiveOperandBitsSub(unsigned OperandNo,
const APInt &AOut,
const KnownBits &LHS,
const KnownBits &RHS);
private:
void performAnalysis();
void determineLiveOperandBits(const Instruction *UserI,
const Value *Val, unsigned OperandNo,
const APInt &AOut, APInt &AB,
KnownBits &Known, KnownBits &Known2, bool &KnownBitsComputed);
Function &F;
AssumptionCache &AC;
DominatorTree &DT;
bool Analyzed = false;
// The set of visited instructions (non-integer-typed only).
SmallPtrSet<Instruction*, 32> Visited;
DenseMap<Instruction *, APInt> AliveBits;
// Uses with no demanded bits. If the user also has no demanded bits, the use
// might not be stored explicitly in this map, to save memory during analysis.
SmallPtrSet<Use *, 16> DeadUses;
};
class DemandedBitsWrapperPass : public FunctionPass {
private:
mutable std::optional<DemandedBits> DB;
public:
static char ID; // Pass identification, replacement for typeid
DemandedBitsWrapperPass();
bool runOnFunction(Function &F) override;
void getAnalysisUsage(AnalysisUsage &AU) const override;
/// Clean up memory in between runs
void releaseMemory() override;
DemandedBits &getDemandedBits() { return *DB; }
void print(raw_ostream &OS, const Module *M) const override;
};
/// An analysis that produces \c DemandedBits for a function.
class DemandedBitsAnalysis : public AnalysisInfoMixin<DemandedBitsAnalysis> {
friend AnalysisInfoMixin<DemandedBitsAnalysis>;
static AnalysisKey Key;
public:
/// Provide the result type for this analysis pass.
using Result = DemandedBits;
/// Run the analysis pass over a function and produce demanded bits
/// information.
DemandedBits run(Function &F, FunctionAnalysisManager &AM);
};
/// Printer pass for DemandedBits
class DemandedBitsPrinterPass : public PassInfoMixin<DemandedBitsPrinterPass> {
raw_ostream &OS;
public:
explicit DemandedBitsPrinterPass(raw_ostream &OS) : OS(OS) {}
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
};
/// Create a demanded bits analysis pass.
FunctionPass *createDemandedBitsWrapperPass();
} // end namespace llvm
#endif // LLVM_ANALYSIS_DEMANDEDBITS_H
#ifdef __GNUC__
#pragma GCC diagnostic pop
#endif
|
