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