134 lines · cpp
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-exception6//7//===----------------------------------------------------------------------===//8 9#include "llvm/Analysis/ValueLattice.h"10#include "llvm/Analysis/ConstantFolding.h"11#include "llvm/IR/Instructions.h"12 13namespace llvm {14Constant *15ValueLatticeElement::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 be23 // 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 single42 // 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 56static bool hasSingleValue(const ValueLatticeElement &Val) {57 if (Val.isConstantRange() && Val.getConstantRange().isSingleElement())58 // Integer constants are single element ranges59 return true;60 return Val.isConstant();61}62 63/// Combine two sets of facts about the same value into a single set of64/// facts. Note that this method is not suitable for merging facts along65/// different paths in a CFG; that's what the mergeIn function is for. This66/// is for merging facts gathered about the same value at the same location67/// through two independent means.68/// Notes:69/// * This method does not promise to return the most precise possible lattice70/// value implied by A and B. It is allowed to return any lattice element71/// which is at least as strong as *either* A or B (unless our facts72/// conflict, see below).73/// * Due to unreachable code, the intersection of two lattice values could be74/// contradictory. If this happens, we return some valid lattice value so as75/// not confuse the rest of LVI. Ideally, we'd always return Undefined, but76/// we do not make this guarantee. TODO: This would be a useful enhancement.77ValueLatticeElement78ValueLatticeElement::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 improved99 return *this;100 }101 102 // Intersect two constant ranges103 ConstantRange Range =104 getConstantRange().intersectWith(Other.getConstantRange());105 // Note: An empty range is implicitly converted to unknown or undef depending106 // on MayIncludeUndef internally.107 return ValueLatticeElement::getRange(108 std::move(Range), /*MayIncludeUndef=*/isConstantRangeIncludingUndef() ||109 Other.isConstantRangeIncludingUndef());110}111 112raw_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 llvm134