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
  30 namespace llvm {
  31
  32 class FunctionPass;
  33 class Function;
  34 class Instruction;
  35 class DominatorTree;
  36 class AssumptionCache;
  37
  38 struct DemandedBits : public FunctionPass {
  39   static char ID; // Pass identification, replacement for typeid
  40   DemandedBits();
  41
  42   bool runOnFunction(Function& F) override;
  43   void getAnalysisUsage(AnalysisUsage& AU) const override;
  44   void print(raw_ostream &OS, const Module *M) const override;
  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 private:
  53   void performAnalysis();
  54   void determineLiveOperandBits(const Instruction *UserI,
  55                                 const Instruction *I, unsigned OperandNo,
  56                                 const APInt &AOut, APInt &AB,
  57                                 APInt &KnownZero, APInt &KnownOne,
  58                                 APInt &KnownZero2, APInt &KnownOne2);
  59
  60   AssumptionCache *AC;
  61   DominatorTree *DT;
  62   Function *F;
  63   bool Analyzed;
  64
  65   // The set of visited instructions (non-integer-typed only).
  66   SmallPtrSet<Instruction*, 128> Visited;
  67   DenseMap<Instruction *, APInt> AliveBits;
  68 };
  69
  70 /// Create a demanded bits analysis pass.
  71 FunctionPass *createDemandedBitsPass();
  72
  73 } // End llvm namespace
  74
  75 #endif