Home | History | Annotate | Line # | Download | only in Analysis 
      1 //===- llvm/Analysis/DemandedBits.h - Determine demanded bits ---*- C++ -*-===//
      2 //
      3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
      4 // See https://llvm.org/LICENSE.txt for license information.
      5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
      6 //
      7 //===----------------------------------------------------------------------===//
      8 //
      9 // This pass implements a demanded bits analysis. A demanded bit is one that
     10 // contributes to a result; bits that are not demanded can be either zero or
     11 // one without affecting control or data flow. For example in this sequence:
     12 //
     13 //   %1 = add i32 %x, %y
     14 //   %2 = trunc i32 %1 to i16
     15 //
     16 // Only the lowest 16 bits of %1 are demanded; the rest are removed by the
     17 // trunc.
     18 //
     19 //===----------------------------------------------------------------------===//
     20 
     21 #ifndef LLVM_ANALYSIS_DEMANDEDBITS_H
     22 #define LLVM_ANALYSIS_DEMANDEDBITS_H
     23 
     24 #include "llvm/ADT/APInt.h"
     25 #include "llvm/ADT/DenseMap.h"
     26 #include "llvm/ADT/Optional.h"
     27 #include "llvm/ADT/SmallPtrSet.h"
     28 #include "llvm/IR/PassManager.h"
     29 #include "llvm/Pass.h"
     30 
     31 namespace llvm {
     32 
     33 class AssumptionCache;
     34 class DominatorTree;
     35 class Function;
     36 class Instruction;
     37 struct KnownBits;
     38 class raw_ostream;
     39 
     40 class DemandedBits {
     41 public:
     42   DemandedBits(Function &F, AssumptionCache &AC, DominatorTree &DT) :
     43     F(F), AC(AC), DT(DT) {}
     44 
     45   /// Return the bits demanded from instruction I.
     46   ///
     47   /// For vector instructions individual vector elements are not distinguished:
     48   /// A bit is demanded if it is demanded for any of the vector elements. The
     49   /// size of the return value corresponds to the type size in bits of the
     50   /// scalar type.
     51   ///
     52   /// Instructions that do not have integer or vector of integer type are
     53   /// accepted, but will always produce a mask with all bits set.
     54   APInt getDemandedBits(Instruction *I);
     55 
     56   /// Return true if, during analysis, I could not be reached.
     57   bool isInstructionDead(Instruction *I);
     58 
     59   /// Return whether this use is dead by means of not having any demanded bits.
     60   bool isUseDead(Use *U);
     61 
     62   void print(raw_ostream &OS);
     63 
     64   /// Compute alive bits of one addition operand from alive output and known
     65   /// operand bits
     66   static APInt determineLiveOperandBitsAdd(unsigned OperandNo,
     67                                            const APInt &AOut,
     68                                            const KnownBits &LHS,
     69                                            const KnownBits &RHS);
     70 
     71   /// Compute alive bits of one subtraction operand from alive output and known
     72   /// operand bits
     73   static APInt determineLiveOperandBitsSub(unsigned OperandNo,
     74                                            const APInt &AOut,
     75                                            const KnownBits &LHS,
     76                                            const KnownBits &RHS);
     77 
     78 private:
     79   void performAnalysis();
     80   void determineLiveOperandBits(const Instruction *UserI,
     81     const Value *Val, unsigned OperandNo,
     82     const APInt &AOut, APInt &AB,
     83     KnownBits &Known, KnownBits &Known2, bool &KnownBitsComputed);
     84 
     85   Function &F;
     86   AssumptionCache ∾
     87   DominatorTree &DT;
     88 
     89   bool Analyzed = false;
     90 
     91   // The set of visited instructions (non-integer-typed only).
     92   SmallPtrSet<Instruction*, 32> Visited;
     93   DenseMap<Instruction *, APInt> AliveBits;
     94   // Uses with no demanded bits. If the user also has no demanded bits, the use
     95   // might not be stored explicitly in this map, to save memory during analysis.
     96   SmallPtrSet<Use *, 16> DeadUses;
     97 };
     98 
     99 class DemandedBitsWrapperPass : public FunctionPass {
    100 private:
    101   mutable Optional<DemandedBits> DB;
    102 
    103 public:
    104   static char ID; // Pass identification, replacement for typeid
    105 
    106   DemandedBitsWrapperPass();
    107 
    108   bool runOnFunction(Function &F) override;
    109   void getAnalysisUsage(AnalysisUsage &AU) const override;
    110 
    111   /// Clean up memory in between runs
    112   void releaseMemory() override;
    113 
    114   DemandedBits &getDemandedBits() { return *DB; }
    115 
    116   void print(raw_ostream &OS, const Module *M) const override;
    117 };
    118 
    119 /// An analysis that produces \c DemandedBits for a function.
    120 class DemandedBitsAnalysis : public AnalysisInfoMixin<DemandedBitsAnalysis> {
    121   friend AnalysisInfoMixin<DemandedBitsAnalysis>;
    122 
    123   static AnalysisKey Key;
    124 
    125 public:
    126   /// Provide the result type for this analysis pass.
    127   using Result = DemandedBits;
    128 
    129   /// Run the analysis pass over a function and produce demanded bits
    130   /// information.
    131   DemandedBits run(Function &F, FunctionAnalysisManager &AM);
    132 };
    133 
    134 /// Printer pass for DemandedBits
    135 class DemandedBitsPrinterPass : public PassInfoMixin<DemandedBitsPrinterPass> {
    136   raw_ostream &OS;
    137 
    138 public:
    139   explicit DemandedBitsPrinterPass(raw_ostream &OS) : OS(OS) {}
    140 
    141   PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
    142 };
    143 
    144 /// Create a demanded bits analysis pass.
    145 FunctionPass *createDemandedBitsWrapperPass();
    146 
    147 } // end namespace llvm
    148 
    149 #endif // LLVM_ANALYSIS_DEMANDEDBITS_H
    150