llvm/lib/Analysis/ValueLattice.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-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