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/Pass.h"
  26 #include "llvm/ADT/APInt.h"
  27 #include "llvm/ADT/DenseMap.h"
  28 #include "llvm/ADT/SmallPtrSet.h"
  29 #include "llvm/IR/PassManager.h"
  30
  31 namespace llvm {
  32
  33 class FunctionPass;
  34 class Function;
  35 class Instruction;
  36 class DominatorTree;
  37 class AssumptionCache;
  38 struct KnownBits;
  39
  40 class DemandedBits {
  41 public:
  42   DemandedBits(Function &F, AssumptionCache &AC, DominatorTree &DT) :
  43     F(F), AC(AC), DT(DT), Analyzed(false) {}
  44
  45   /// Return the bits demanded from instruction I.
  46   APInt getDemandedBits(Instruction *I);
  47
  48   /// Return true if, during analysis, I could not be reached.
  49   bool isInstructionDead(Instruction *I);
  50
  51   void print(raw_ostream &OS);
  52
  53 private:
  54   Function &F;
  55   AssumptionCache &AC;
  56   DominatorTree &DT;
  57
  58   void performAnalysis();
  59   void determineLiveOperandBits(const Instruction *UserI,
  60     const Instruction *I, unsigned OperandNo,
  61     const APInt &AOut, APInt &AB,
  62     KnownBits &Known, KnownBits &Known2);
  63
  64   bool Analyzed;
  65
  66   // The set of visited instructions (non-integer-typed only).
  67   SmallPtrSet<Instruction*, 32> Visited;
  68   DenseMap<Instruction *, APInt> AliveBits;
  69 };
  70
  71 class DemandedBitsWrapperPass : public FunctionPass {
  72 private:
  73   mutable Optional<DemandedBits> DB;
  74 public:
  75   static char ID; // Pass identification, replacement for typeid
  76   DemandedBitsWrapperPass();
  77
  78   bool runOnFunction(Function &F) override;
  79   void getAnalysisUsage(AnalysisUsage &AU) const override;
  80
  81   /// Clean up memory in between runs
  82   void releaseMemory() override;
  83
  84   DemandedBits &getDemandedBits() { return *DB; }
  85
  86   void print(raw_ostream &OS, const Module *M) const override;
  87 };
  88
  89 /// An analysis that produces \c DemandedBits for a function.
  90 class DemandedBitsAnalysis : public AnalysisInfoMixin<DemandedBitsAnalysis> {
  91   friend AnalysisInfoMixin<DemandedBitsAnalysis>;
  92   static AnalysisKey Key;
  93
  94 public:
  95   /// \brief Provide the result typedef for this analysis pass.
  96   typedef DemandedBits Result;
  97
  98   /// \brief Run the analysis pass over a function and produce demanded bits
  99   /// information.
 100   DemandedBits run(Function &F, FunctionAnalysisManager &AM);
 101 };
 102
 103 /// \brief Printer pass for DemandedBits
 104 class DemandedBitsPrinterPass : public PassInfoMixin<DemandedBitsPrinterPass> {
 105   raw_ostream &OS;
 106
 107 public:
 108   explicit DemandedBitsPrinterPass(raw_ostream &OS) : OS(OS) {}
 109   PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
 110 };
 111
 112 /// Create a demanded bits analysis pass.
 113 FunctionPass *createDemandedBitsWrapperPass();
 114
 115 } // End llvm namespace
 116
 117 #endif