LLVM 19.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
29namespace llvm {
30
31class AssumptionCache;
32class DominatorTree;
33class Function;
34class Instruction;
35struct KnownBits;
36class raw_ostream;
37
39public:
41 F(F), AC(AC), DT(DT) {}
42
43 /// Return the bits demanded from instruction I.
44 ///
45 /// For vector instructions individual vector elements are not distinguished:
46 /// A bit is demanded if it is demanded for any of the vector elements. The
47 /// size of the return value corresponds to the type size in bits of the
48 /// scalar type.
49 ///
50 /// Instructions that do not have integer or vector of integer type are
51 /// accepted, but will always produce a mask with all bits set.
53
54 /// Return the bits demanded from use U.
56
57 /// Return true if, during analysis, I could not be reached.
59
60 /// Return whether this use is dead by means of not having any demanded bits.
61 bool isUseDead(Use *U);
62
63 void print(raw_ostream &OS);
64
65 /// Compute alive bits of one addition operand from alive output and known
66 /// operand bits
67 static APInt determineLiveOperandBitsAdd(unsigned OperandNo,
68 const APInt &AOut,
69 const KnownBits &LHS,
70 const KnownBits &RHS);
71
72 /// Compute alive bits of one subtraction operand from alive output and known
73 /// operand bits
74 static APInt determineLiveOperandBitsSub(unsigned OperandNo,
75 const APInt &AOut,
76 const KnownBits &LHS,
77 const KnownBits &RHS);
78
79private:
80 void performAnalysis();
81 void determineLiveOperandBits(const Instruction *UserI,
82 const Value *Val, unsigned OperandNo,
83 const APInt &AOut, APInt &AB,
84 KnownBits &Known, KnownBits &Known2, bool &KnownBitsComputed);
85
86 Function &F;
88 DominatorTree &DT;
89
90 bool Analyzed = false;
91
92 // The set of visited instructions (non-integer-typed only).
95 // Uses with no demanded bits. If the user also has no demanded bits, the use
96 // might not be stored explicitly in this map, to save memory during analysis.
98};
99
100/// An analysis that produces \c DemandedBits for a function.
101class DemandedBitsAnalysis : public AnalysisInfoMixin<DemandedBitsAnalysis> {
103
104 static AnalysisKey Key;
105
106public:
107 /// Provide the result type for this analysis pass.
109
110 /// Run the analysis pass over a function and produce demanded bits
111 /// information.
113};
114
115/// Printer pass for DemandedBits
116class DemandedBitsPrinterPass : public PassInfoMixin<DemandedBitsPrinterPass> {
117 raw_ostream &OS;
118
119public:
121
123
124 static bool isRequired() { return true; }
125};
126
127} // end namespace llvm
128
129#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:77
A container for analyses that lazily runs them and caches their results.
Definition: PassManager.h:321
A cache of @llvm.assume calls within a function.
An analysis that produces DemandedBits for a function.
Definition: DemandedBits.h:101
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:116
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
DemandedBitsPrinterPass(raw_ostream &OS)
Definition: DemandedBits.h:120
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:40
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:162
A set of analyses that are preserved following a run of a transformation pass.
Definition: Analysis.h:109
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:427
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:97
A special type used by analysis passes to provide an address that identifies that particular analysis...
Definition: Analysis.h:26
A CRTP mix-in to automatically provide informational APIs needed for passes.
Definition: PassManager.h:74