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