contrib/llvm/include/llvm/Analysis/DemandedBits.h

   1 //===- llvm/Analysis/DemandedBits.h - Determine demanded bits ---*- C++ -*-===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This pass implements a demanded bits analysis. A demanded bit is one that
  11 // contributes to a result; bits that are not demanded can be either zero or
  12 // one without affecting control or data flow. For example in this sequence:
  13 //
  14 //   %1 = add i32 %x, %y
  15 //   %2 = trunc i32 %1 to i16
  16 //
  17 // Only the lowest 16 bits of %1 are demanded; the rest are removed by the
  18 // trunc.
  19 //
  20 //===----------------------------------------------------------------------===//
  21
  22 #ifndef LLVM_ANALYSIS_DEMANDED_BITS_H
  23 #define LLVM_ANALYSIS_DEMANDED_BITS_H
  24
  25 #include "llvm/ADT/APInt.h"
  26 #include "llvm/ADT/DenseMap.h"
  27 #include "llvm/ADT/Optional.h"
  28 #include "llvm/ADT/SmallPtrSet.h"
  29 #include "llvm/IR/PassManager.h"
  30 #include "llvm/Pass.h"
  31
  32 namespace llvm {
  33
  34 class AssumptionCache;
  35 class DominatorTree;
  36 class Function;
  37 class Instruction;
  38 struct KnownBits;
  39 class raw_ostream;
  40
  41 class DemandedBits {
  42 public:
  43   DemandedBits(Function &F, AssumptionCache &AC, DominatorTree &DT) :
  44     F(F), AC(AC), DT(DT) {}
  45
  46   /// Return the bits demanded from instruction I.
  47   APInt getDemandedBits(Instruction *I);
  48
  49   /// Return true if, during analysis, I could not be reached.
  50   bool isInstructionDead(Instruction *I);
  51
  52   void print(raw_ostream &OS);
  53
  54 private:
  55   void performAnalysis();
  56   void determineLiveOperandBits(const Instruction *UserI,
  57     const Instruction *I, unsigned OperandNo,
  58     const APInt &AOut, APInt &AB,
  59     KnownBits &Known, KnownBits &Known2);
  60
  61   Function &F;
  62   AssumptionCache &AC;
  63   DominatorTree &DT;
  64
  65   bool Analyzed = false;
  66
  67   // The set of visited instructions (non-integer-typed only).
  68   SmallPtrSet<Instruction*, 32> Visited;
  69   DenseMap<Instruction *, APInt> AliveBits;
  70 };
  71
  72 class DemandedBitsWrapperPass : public FunctionPass {
  73 private:
  74   mutable Optional<DemandedBits> DB;
  75
  76 public:
  77   static char ID; // Pass identification, replacement for typeid
  78
  79   DemandedBitsWrapperPass();
  80
  81   bool runOnFunction(Function &F) override;
  82   void getAnalysisUsage(AnalysisUsage &AU) const override;
  83
  84   /// Clean up memory in between runs
  85   void releaseMemory() override;
  86
  87   DemandedBits &getDemandedBits() { return *DB; }
  88
  89   void print(raw_ostream &OS, const Module *M) const override;
  90 };
  91
  92 /// An analysis that produces \c DemandedBits for a function.
  93 class DemandedBitsAnalysis : public AnalysisInfoMixin<DemandedBitsAnalysis> {
  94   friend AnalysisInfoMixin<DemandedBitsAnalysis>;
  95
  96   static AnalysisKey Key;
  97
  98 public:
  99   /// \brief Provide the result type for this analysis pass.
 100   using Result = DemandedBits;
 101
 102   /// \brief Run the analysis pass over a function and produce demanded bits
 103   /// information.
 104   DemandedBits run(Function &F, FunctionAnalysisManager &AM);
 105 };
 106
 107 /// \brief Printer pass for DemandedBits
 108 class DemandedBitsPrinterPass : public PassInfoMixin<DemandedBitsPrinterPass> {
 109   raw_ostream &OS;
 110
 111 public:
 112   explicit DemandedBitsPrinterPass(raw_ostream &OS) : OS(OS) {}
 113
 114   PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
 115 };
 116
 117 /// Create a demanded bits analysis pass.
 118 FunctionPass *createDemandedBitsWrapperPass();
 119
 120 } // end namespace llvm
 121
 122 #endif // LLVM_ANALYSIS_DEMANDED_BITS_H