1 //===- ValueLattice.cpp - Value constraint analysis -------------*- 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 #include "llvm/Analysis/ValueLattice.h" 10 #include "llvm/Analysis/ConstantFolding.h" 11 #include "llvm/IR/Instructions.h" 12 13 namespace llvm { 14 Constant * 15 ValueLatticeElement::getCompare(CmpInst::Predicate Pred, Type *Ty, 16 const ValueLatticeElement &Other, 17 const DataLayout &DL) const { 18 // Not yet resolved. 19 if (isUnknown() || Other.isUnknown()) 20 return nullptr; 21 22 // TODO: Can be made more precise, but always returning undef would be 23 // incorrect. 24 if (isUndef() || Other.isUndef()) 25 return nullptr; 26 27 if (isConstant() && Other.isConstant()) 28 return ConstantFoldCompareInstOperands(Pred, getConstant(), 29 Other.getConstant(), DL); 30 31 if (ICmpInst::isEquality(Pred)) { 32 // not(C) != C => true, not(C) == C => false. 33 if ((isNotConstant() && Other.isConstant() && 34 getNotConstant() == Other.getConstant()) || 35 (isConstant() && Other.isNotConstant() && 36 getConstant() == Other.getNotConstant())) 37 return Pred == ICmpInst::ICMP_NE ? ConstantInt::getTrue(Ty) 38 : ConstantInt::getFalse(Ty); 39 } 40 41 // Integer constants are represented as ConstantRanges with single 42 // elements. 43 if (!isConstantRange() || !Other.isConstantRange()) 44 return nullptr; 45 46 const auto &CR = getConstantRange(); 47 const auto &OtherCR = Other.getConstantRange(); 48 if (CR.icmp(Pred, OtherCR)) 49 return ConstantInt::getTrue(Ty); 50 if (CR.icmp(CmpInst::getInversePredicate(Pred), OtherCR)) 51 return ConstantInt::getFalse(Ty); 52 53 return nullptr; 54 } 55 56 static bool hasSingleValue(const ValueLatticeElement &Val) { 57 if (Val.isConstantRange() && Val.getConstantRange().isSingleElement()) 58 // Integer constants are single element ranges 59 return true; 60 return Val.isConstant(); 61 } 62 63 /// Combine two sets of facts about the same value into a single set of 64 /// facts. Note that this method is not suitable for merging facts along 65 /// different paths in a CFG; that's what the mergeIn function is for. This 66 /// is for merging facts gathered about the same value at the same location 67 /// through two independent means. 68 /// Notes: 69 /// * This method does not promise to return the most precise possible lattice 70 /// value implied by A and B. It is allowed to return any lattice element 71 /// which is at least as strong as *either* A or B (unless our facts 72 /// conflict, see below). 73 /// * Due to unreachable code, the intersection of two lattice values could be 74 /// contradictory. If this happens, we return some valid lattice value so as 75 /// not confuse the rest of LVI. Ideally, we'd always return Undefined, but 76 /// we do not make this guarantee. TODO: This would be a useful enhancement. 77 ValueLatticeElement 78 ValueLatticeElement::intersect(const ValueLatticeElement &Other) const { 79 if (isUnknown()) 80 return *this; 81 if (Other.isUnknown()) 82 return Other; 83 84 // If we gave up for one, but got a useable fact from the other, use it. 85 if (isOverdefined()) 86 return Other; 87 if (Other.isOverdefined()) 88 return *this; 89 90 // Can't get any more precise than constants. 91 if (hasSingleValue(*this)) 92 return *this; 93 if (hasSingleValue(Other)) 94 return Other; 95 96 // Could be either constant range or not constant here. 97 if (!isConstantRange() || !Other.isConstantRange()) { 98 // TODO: Arbitrary choice, could be improved 99 return *this; 100 } 101 102 // Intersect two constant ranges 103 ConstantRange Range = 104 getConstantRange().intersectWith(Other.getConstantRange()); 105 // Note: An empty range is implicitly converted to unknown or undef depending 106 // on MayIncludeUndef internally. 107 return ValueLatticeElement::getRange( 108 std::move(Range), /*MayIncludeUndef=*/isConstantRangeIncludingUndef() || 109 Other.isConstantRangeIncludingUndef()); 110 } 111 112 raw_ostream &operator<<(raw_ostream &OS, const ValueLatticeElement &Val) { 113 if (Val.isUnknown()) 114 return OS << "unknown"; 115 if (Val.isUndef()) 116 return OS << "undef"; 117 if (Val.isOverdefined()) 118 return OS << "overdefined"; 119 120 if (Val.isNotConstant()) 121 return OS << "notconstant<" << *Val.getNotConstant() << ">"; 122 123 if (Val.isConstantRangeIncludingUndef()) 124 return OS << "constantrange incl. undef <" 125 << Val.getConstantRange(true).getLower() << ", " 126 << Val.getConstantRange(true).getUpper() << ">"; 127 128 if (Val.isConstantRange()) 129 return OS << "constantrange<" << Val.getConstantRange().getLower() << ", " 130 << Val.getConstantRange().getUpper() << ">"; 131 return OS << "constant<" << *Val.getConstant() << ">"; 132 } 133 } // end namespace llvm 134