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"
26#include "llvm/ADT/SmallPtrSet.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
38class DemandedBits {
39public:
40 DemandedBits(Function &F, AssumptionCache &AC, DominatorTree &DT) :
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.
52 APInt getDemandedBits(Instruction *I);
53
54 /// Return the bits demanded from use U.
55 APInt getDemandedBits(Use *U);
56
57 /// Return true if, during analysis, I could not be reached.
58 bool isInstructionDead(Instruction *I);
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;
87 AssumptionCache ∾
88 DominatorTree &DT;
89
90 bool Analyzed = false;
91
92 // The set of visited instructions (non-integer-typed only).
93 SmallPtrSet<Instruction*, 32> Visited;
94 DenseMap<Instruction *, APInt> AliveBits;
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.
97 SmallPtrSet<Use *, 16> DeadUses;
98};
99
100/// An analysis that produces \c DemandedBits for a function.
101class DemandedBitsAnalysis : public AnalysisInfoMixin<DemandedBitsAnalysis> {
102 friend AnalysisInfoMixin<DemandedBitsAnalysis>;
103
104 static AnalysisKey Key;
105
106public:
107 /// Provide the result type for this analysis pass.
108 using Result = DemandedBits;
109
110 /// Run the analysis pass over a function and produce demanded bits
111 /// information.
112 DemandedBits run(Function &F, FunctionAnalysisManager &AM);
113};
114
115/// Printer pass for DemandedBits
116class DemandedBitsPrinterPass : public PassInfoMixin<DemandedBitsPrinterPass> {
117 raw_ostream &OS;
118
119public:
120 explicit DemandedBitsPrinterPass(raw_ostream &OS) : OS(OS) {}
121
122 PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
123
124 static bool isRequired() { return true; }
125};
126
127} // end namespace llvm
128
129#endif // LLVM_ANALYSIS_DEMANDEDBITS_H
130

source code of llvm/include/llvm/Analysis/DemandedBits.h