include/llvm/Analysis/DemandedBits.h

   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_DEMANDED_BITS_H
  22 #define LLVM_ANALYSIS_DEMANDED_BITS_H
  23
  24 #include "llvm/ADT/APInt.h"
  25 #include "llvm/ADT/DenseMap.h"
  26 #include "llvm/ADT/Optional.h"
  27 #include "llvm/ADT/SmallPtrSet.h"
  28 #include "llvm/IR/PassManager.h"
  29 #include "llvm/Pass.h"
  30
  31 namespace llvm {
  32
  33 class AssumptionCache;
  34 class DominatorTree;
  35 class Function;
  36 class Instruction;
  37 struct KnownBits;
  38 class raw_ostream;
  39
  40 class DemandedBits {
  41 public:
  42   DemandedBits(Function &F, AssumptionCache &AC, DominatorTree &DT) :
  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.
  54   APInt getDemandedBits(Instruction *I);
  55
  56   /// Return true if, during analysis, I could not be reached.
  57   bool isInstructionDead(Instruction *I);
  58
  59   /// Return whether this use is dead by means of not having any demanded bits.
  60   bool isUseDead(Use *U);
  61
  62   void print(raw_ostream &OS);
  63
  64 private:
  65   void performAnalysis();
  66   void determineLiveOperandBits(const Instruction *UserI,
  67     const Value *Val, unsigned OperandNo,
  68     const APInt &AOut, APInt &AB,
  69     KnownBits &Known, KnownBits &Known2, bool &KnownBitsComputed);
  70
  71   Function &F;
  72   AssumptionCache &AC;
  73   DominatorTree &DT;
  74
  75   bool Analyzed = false;
  76
  77   // The set of visited instructions (non-integer-typed only).
  78   SmallPtrSet<Instruction*, 32> Visited;
  79   DenseMap<Instruction *, APInt> AliveBits;
  80   // Uses with no demanded bits. If the user also has no demanded bits, the use
  81   // might not be stored explicitly in this map, to save memory during analysis.
  82   SmallPtrSet<Use *, 16> DeadUses;
  83 };
  84
  85 class DemandedBitsWrapperPass : public FunctionPass {
  86 private:
  87   mutable Optional<DemandedBits> DB;
  88
  89 public:
  90   static char ID; // Pass identification, replacement for typeid
  91
  92   DemandedBitsWrapperPass();
  93
  94   bool runOnFunction(Function &F) override;
  95   void getAnalysisUsage(AnalysisUsage &AU) const override;
  96
  97   /// Clean up memory in between runs
  98   void releaseMemory() override;
  99
 100   DemandedBits &getDemandedBits() { return *DB; }
 101
 102   void print(raw_ostream &OS, const Module *M) const override;
 103 };
 104
 105 /// An analysis that produces \c DemandedBits for a function.
 106 class DemandedBitsAnalysis : public AnalysisInfoMixin<DemandedBitsAnalysis> {
 107   friend AnalysisInfoMixin<DemandedBitsAnalysis>;
 108
 109   static AnalysisKey Key;
 110
 111 public:
 112   /// Provide the result type for this analysis pass.
 113   using Result = DemandedBits;
 114
 115   /// Run the analysis pass over a function and produce demanded bits
 116   /// information.
 117   DemandedBits run(Function &F, FunctionAnalysisManager &AM);
 118 };
 119
 120 /// Printer pass for DemandedBits
 121 class DemandedBitsPrinterPass : public PassInfoMixin<DemandedBitsPrinterPass> {
 122   raw_ostream &OS;
 123
 124 public:
 125   explicit DemandedBitsPrinterPass(raw_ostream &OS) : OS(OS) {}
 126
 127   PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
 128 };
 129
 130 /// Create a demanded bits analysis pass.
 131 FunctionPass *createDemandedBitsWrapperPass();
 132
 133 } // end namespace llvm
 134
 135 #endif // LLVM_ANALYSIS_DEMANDED_BITS_H