LLVM 17.0.0git
DemandedBits.h
Go to the documentation of this file.
1//===- llvm/Analysis/DemandedBits.h - Determine demanded bits ---*- 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 pass implements a demanded bits analysis. A demanded bit is one that
10// contributes to a result; bits that are not demanded can be either zero or
11// one without affecting control or data flow. For example in this sequence:
12//
13// %1 = add i32 %x, %y
14// %2 = trunc i32 %1 to i16
15//
16// Only the lowest 16 bits of %1 are demanded; the rest are removed by the
17// trunc.
18//
19//===----------------------------------------------------------------------===//
20
21#ifndef LLVM_ANALYSIS_DEMANDEDBITS_H
22#define LLVM_ANALYSIS_DEMANDEDBITS_H
23
24#include "llvm/ADT/APInt.h"
25#include "llvm/ADT/DenseMap.h"
27#include "llvm/IR/PassManager.h"
28#include <optional>
29
30namespace llvm {
31
32class AssumptionCache;
33class DominatorTree;
34class Function;
35class Instruction;
36struct KnownBits;
37class raw_ostream;
38
40public:
42 F(F), AC(AC), DT(DT) {}
43
44 /// Return the bits demanded from instruction I.
45 ///
46 /// For vector instructions individual vector elements are not distinguished:
47 /// A bit is demanded if it is demanded for any of the vector elements. The
48 /// size of the return value corresponds to the type size in bits of the
49 /// scalar type.
50 ///
51 /// Instructions that do not have integer or vector of integer type are
52 /// accepted, but will always produce a mask with all bits set.
54
55 /// Return the bits demanded from use U.
57
58 /// Return true if, during analysis, I could not be reached.
60
61 /// Return whether this use is dead by means of not having any demanded bits.
62 bool isUseDead(Use *U);
63
64 void print(raw_ostream &OS);
65
66 /// Compute alive bits of one addition operand from alive output and known
67 /// operand bits
68 static APInt determineLiveOperandBitsAdd(unsigned OperandNo,
69 const APInt &AOut,
70 const KnownBits &LHS,
71 const KnownBits &RHS);
72
73 /// Compute alive bits of one subtraction operand from alive output and known
74 /// operand bits
75 static APInt determineLiveOperandBitsSub(unsigned OperandNo,
76 const APInt &AOut,
77 const KnownBits &LHS,
78 const KnownBits &RHS);
79
80private:
81 void performAnalysis();
82 void determineLiveOperandBits(const Instruction *UserI,
83 const Value *Val, unsigned OperandNo,
84 const APInt &AOut, APInt &AB,
85 KnownBits &Known, KnownBits &Known2, bool &KnownBitsComputed);
86
87 Function &F;
89 DominatorTree &DT;
90
91 bool Analyzed = false;
92
93 // The set of visited instructions (non-integer-typed only).
96 // Uses with no demanded bits. If the user also has no demanded bits, the use
97 // might not be stored explicitly in this map, to save memory during analysis.
99};
100
101/// An analysis that produces \c DemandedBits for a function.
102class DemandedBitsAnalysis : public AnalysisInfoMixin<DemandedBitsAnalysis> {
104
105 static AnalysisKey Key;
106
107public:
108 /// Provide the result type for this analysis pass.
110
111 /// Run the analysis pass over a function and produce demanded bits
112 /// information.
114};
115
116/// Printer pass for DemandedBits
117class DemandedBitsPrinterPass : public PassInfoMixin<DemandedBitsPrinterPass> {
118 raw_ostream &OS;
119
120public:
122
124};
125
126} // end namespace llvm
127
128#endif // LLVM_ANALYSIS_DEMANDEDBITS_H
This file implements a class to represent arbitrary precision integral constant values and operations...
This file defines the DenseMap class.
#define F(x, y, z)
Definition: MD5.cpp:55
#define I(x, y, z)
Definition: MD5.cpp:58
This header defines various interfaces for pass management in LLVM.
raw_pwrite_stream & OS
This file defines the SmallPtrSet class.
Value * RHS
Value * LHS
Class for arbitrary precision integers.
Definition: APInt.h:75
A container for analyses that lazily runs them and caches their results.
Definition: PassManager.h:620
A cache of @llvm.assume calls within a function.
An analysis that produces DemandedBits for a function.
Definition: DemandedBits.h:102
DemandedBits run(Function &F, FunctionAnalysisManager &AM)
Run the analysis pass over a function and produce demanded bits information.
Printer pass for DemandedBits.
Definition: DemandedBits.h:117
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
DemandedBitsPrinterPass(raw_ostream &OS)
Definition: DemandedBits.h:121
void print(raw_ostream &OS)
APInt getDemandedBits(Instruction *I)
Return the bits demanded from instruction I.
static APInt determineLiveOperandBitsAdd(unsigned OperandNo, const APInt &AOut, const KnownBits &LHS, const KnownBits &RHS)
Compute alive bits of one addition operand from alive output and known operand bits.
DemandedBits(Function &F, AssumptionCache &AC, DominatorTree &DT)
Definition: DemandedBits.h:41
bool isInstructionDead(Instruction *I)
Return true if, during analysis, I could not be reached.
static APInt determineLiveOperandBitsSub(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.
bool isUseDead(Use *U)
Return whether this use is dead by means of not having any demanded bits.
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:166
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:152
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:450
A Use represents the edge between a Value definition and its users.
Definition: Use.h:43
LLVM Value Representation.
Definition: Value.h:74
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:52
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
A CRTP mix-in that provides informational APIs needed for analysis passes.
Definition: PassManager.h:394
A special type used by analysis passes to provide an address that identifies that particular analysis...
Definition: PassManager.h:69
A CRTP mix-in to automatically provide informational APIs needed for passes.
Definition: PassManager.h:371