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 76