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/SmallPtrSet.h" 27 #include "llvm/IR/PassManager.h" 28 #include "llvm/Support/Compiler.h" 29 30 namespace llvm { 31 32 class AssumptionCache; 33 class DominatorTree; 34 class Function; 35 class Instruction; 36 struct KnownBits; 37 class raw_ostream; 38 class Use; 39 class Value; 40 41 class DemandedBits { 42 public: DemandedBits(Function & F,AssumptionCache & AC,DominatorTree & DT)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 /// 48 /// For vector instructions individual vector elements are not distinguished: 49 /// A bit is demanded if it is demanded for any of the vector elements. The 50 /// size of the return value corresponds to the type size in bits of the 51 /// scalar type. 52 /// 53 /// Instructions that do not have integer or vector of integer type are 54 /// accepted, but will always produce a mask with all bits set. 55 LLVM_ABI APInt getDemandedBits(Instruction *I); 56 57 /// Return the bits demanded from use U. 58 LLVM_ABI APInt getDemandedBits(Use *U); 59 60 /// Return true if, during analysis, I could not be reached. 61 LLVM_ABI bool isInstructionDead(Instruction *I); 62 63 /// Return whether this use is dead by means of not having any demanded bits. 64 LLVM_ABI bool isUseDead(Use *U); 65 66 LLVM_ABI void print(raw_ostream &OS); 67 68 /// Compute alive bits of one addition operand from alive output and known 69 /// operand bits 70 LLVM_ABI static APInt determineLiveOperandBitsAdd(unsigned OperandNo, 71 const APInt &AOut, 72 const KnownBits &LHS, 73 const KnownBits &RHS); 74 75 /// Compute alive bits of one subtraction operand from alive output and known 76 /// operand bits 77 LLVM_ABI static APInt determineLiveOperandBitsSub(unsigned OperandNo, 78 const APInt &AOut, 79 const KnownBits &LHS, 80 const KnownBits &RHS); 81 82 private: 83 void performAnalysis(); 84 void determineLiveOperandBits(const Instruction *UserI, 85 const Value *Val, unsigned OperandNo, 86 const APInt &AOut, APInt &AB, 87 KnownBits &Known, KnownBits &Known2, bool &KnownBitsComputed); 88 89 Function &F; 90 AssumptionCache &AC; 91 DominatorTree &DT; 92 93 bool Analyzed = false; 94 95 // The set of visited instructions (non-integer-typed only). 96 SmallPtrSet<Instruction*, 32> Visited; 97 DenseMap<Instruction *, APInt> AliveBits; 98 // Uses with no demanded bits. If the user also has no demanded bits, the use 99 // might not be stored explicitly in this map, to save memory during analysis. 100 SmallPtrSet<Use *, 16> DeadUses; 101 }; 102 103 /// An analysis that produces \c DemandedBits for a function. 104 class DemandedBitsAnalysis : public AnalysisInfoMixin<DemandedBitsAnalysis> { 105 friend AnalysisInfoMixin<DemandedBitsAnalysis>; 106 107 LLVM_ABI static AnalysisKey Key; 108 109 public: 110 /// Provide the result type for this analysis pass. 111 using Result = DemandedBits; 112 113 /// Run the analysis pass over a function and produce demanded bits 114 /// information. 115 LLVM_ABI DemandedBits run(Function &F, FunctionAnalysisManager &AM); 116 }; 117 118 /// Printer pass for DemandedBits 119 class DemandedBitsPrinterPass : public PassInfoMixin<DemandedBitsPrinterPass> { 120 raw_ostream &OS; 121 122 public: DemandedBitsPrinterPass(raw_ostream & OS)123 explicit DemandedBitsPrinterPass(raw_ostream &OS) : OS(OS) {} 124 125 LLVM_ABI PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); 126 isRequired()127 static bool isRequired() { return true; } 128 }; 129 130 } // end namespace llvm 131 132 #endif // LLVM_ANALYSIS_DEMANDEDBITS_H 133