Home | History | Annotate | Download | only in Analysis 
      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 ∾
     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
    123