Line data    Source code

       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       70497 :   DemandedBits(Function &F, AssumptionCache &AC, DominatorTree &DT) :
      44      141516 :     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             :   /// Provide the result type for this analysis pass.
     100             :   using Result = DemandedBits;
     101             : 
     102             :   /// Run the analysis pass over a function and produce demanded bits
     103             :   /// information.
     104             :   DemandedBits run(Function &F, FunctionAnalysisManager &AM);
     105             : };
     106             : 
     107             : /// Printer pass for DemandedBits
     108             : class DemandedBitsPrinterPass : public PassInfoMixin<DemandedBitsPrinterPass> {
     109             :   raw_ostream &OS;
     110             : 
     111             : public:
     112           2 :   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