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
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 be
23 // incorrect.
24 if (isUndef() || Other.isUndef())
25 return nullptr;
26
27 if (isConstant() && Other.isConstant())
28 return ConstantFoldCompareInstOperands(Predicate: Pred, LHS: getConstant(),
29 RHS: Other.getConstant(), DL);
30
31 if (ICmpInst::isEquality(P: 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, Other: OtherCR))
49 return ConstantInt::getTrue(Ty);
50 if (CR.icmp(Pred: CmpInst::getInversePredicate(pred: Pred), Other: 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 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.
77ValueLatticeElement
78ValueLatticeElement::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(Val: *this))
92 return *this;
93 if (hasSingleValue(Val: 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(CR: Other.getConstantRange());
105 // Note: An empty range is implicitly converted to unknown or undef depending
106 // on MayIncludeUndef internally.
107 return ValueLatticeElement::getRange(
108 CR: 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(UndefAllowed: true).getLower() << ", "
126 << Val.getConstantRange(UndefAllowed: 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