llvm/Analysis/ValueLattice.h

0001 //===- ValueLattice.h - Value constraint analysis ---------------*- C++ -*-===//
0002 //
0003 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
0004 // See https://llvm.org/LICENSE.txt for license information.
0005 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
0006 //
0007 //===----------------------------------------------------------------------===//
0008
0009 #ifndef LLVM_ANALYSIS_VALUELATTICE_H
0010 #define LLVM_ANALYSIS_VALUELATTICE_H
0011
0012 #include "llvm/IR/ConstantRange.h"
0013 #include "llvm/IR/Constants.h"
0014
0015 //===----------------------------------------------------------------------===//
0016 //                               ValueLatticeElement
0017 //===----------------------------------------------------------------------===//
0018
0019 namespace llvm {
0020
0021 /// This class represents lattice values for constants.
0022 ///
0023 /// FIXME: This is basically just for bringup, this can be made a lot more rich
0024 /// in the future.
0025 ///
0026 class ValueLatticeElement {
0027   enum ValueLatticeElementTy {
0028     /// This Value has no known value yet.  As a result, this implies the
0029     /// producing instruction is dead.  Caution: We use this as the starting
0030     /// state in our local meet rules.  In this usage, it's taken to mean
0031     /// "nothing known yet".
0032     /// Transition to any other state allowed.
0033     unknown,
0034
0035     /// This Value is an UndefValue constant or produces undef. Undefined values
0036     /// can be merged with constants (or single element constant ranges),
0037     /// assuming all uses of the result will be replaced.
0038     /// Transition allowed to the following states:
0039     ///  constant
0040     ///  constantrange_including_undef
0041     ///  overdefined
0042     undef,
0043
0044     /// This Value has a specific constant value.  The constant cannot be undef.
0045     /// (For constant integers, constantrange is used instead. Integer typed
0046     /// constantexprs can appear as constant.) Note that the constant state
0047     /// can be reached by merging undef & constant states.
0048     /// Transition allowed to the following states:
0049     ///  overdefined
0050     constant,
0051
0052     /// This Value is known to not have the specified value. (For constant
0053     /// integers, constantrange is used instead.  As above, integer typed
0054     /// constantexprs can appear here.)
0055     /// Transition allowed to the following states:
0056     ///  overdefined
0057     notconstant,
0058
0059     /// The Value falls within this range. (Used only for integer typed values.)
0060     /// Transition allowed to the following states:
0061     ///  constantrange (new range must be a superset of the existing range)
0062     ///  constantrange_including_undef
0063     ///  overdefined
0064     constantrange,
0065
0066     /// This Value falls within this range, but also may be undef.
0067     /// Merging it with other constant ranges results in
0068     /// constantrange_including_undef.
0069     /// Transition allowed to the following states:
0070     ///  overdefined
0071     constantrange_including_undef,
0072
0073     /// We can not precisely model the dynamic values this value might take.
0074     /// No transitions are allowed after reaching overdefined.
0075     overdefined,
0076   };
0077
0078   ValueLatticeElementTy Tag : 8;
0079   /// Number of times a constant range has been extended with widening enabled.
0080   unsigned NumRangeExtensions : 8;
0081
0082   /// The union either stores a pointer to a constant or a constant range,
0083   /// associated to the lattice element. We have to ensure that Range is
0084   /// initialized or destroyed when changing state to or from constantrange.
0085   union {
0086     Constant *ConstVal;
0087     ConstantRange Range;
0088   };
0089
0090   /// Destroy contents of lattice value, without destructing the object.
0091   void destroy() {
0092     switch (Tag) {
0093     case overdefined:
0094     case unknown:
0095     case undef:
0096     case constant:
0097     case notconstant:
0098       break;
0099     case constantrange_including_undef:
0100     case constantrange:
0101       Range.~ConstantRange();
0102       break;
0103     };
0104   }
0105
0106 public:
0107   /// Struct to control some aspects related to merging constant ranges.
0108   struct MergeOptions {
0109     /// The merge value may include undef.
0110     bool MayIncludeUndef;
0111
0112     /// Handle repeatedly extending a range by going to overdefined after a
0113     /// number of steps.
0114     bool CheckWiden;
0115
0116     /// The number of allowed widening steps (including setting the range
0117     /// initially).
0118     unsigned MaxWidenSteps;
0119
0120     MergeOptions() : MergeOptions(false, false) {}
0121
0122     MergeOptions(bool MayIncludeUndef, bool CheckWiden,
0123                  unsigned MaxWidenSteps = 1)
0124         : MayIncludeUndef(MayIncludeUndef), CheckWiden(CheckWiden),
0125           MaxWidenSteps(MaxWidenSteps) {}
0126
0127     MergeOptions &setMayIncludeUndef(bool V = true) {
0128       MayIncludeUndef = V;
0129       return *this;
0130     }
0131
0132     MergeOptions &setCheckWiden(bool V = true) {
0133       CheckWiden = V;
0134       return *this;
0135     }
0136
0137     MergeOptions &setMaxWidenSteps(unsigned Steps = 1) {
0138       CheckWiden = true;
0139       MaxWidenSteps = Steps;
0140       return *this;
0141     }
0142   };
0143
0144   // ConstVal and Range are initialized on-demand.
0145   ValueLatticeElement() : Tag(unknown), NumRangeExtensions(0) {}
0146
0147   ~ValueLatticeElement() { destroy(); }
0148
0149   ValueLatticeElement(const ValueLatticeElement &Other)
0150       : Tag(Other.Tag), NumRangeExtensions(0) {
0151     switch (Other.Tag) {
0152     case constantrange:
0153     case constantrange_including_undef:
0154       new (&Range) ConstantRange(Other.Range);
0155       NumRangeExtensions = Other.NumRangeExtensions;
0156       break;
0157     case constant:
0158     case notconstant:
0159       ConstVal = Other.ConstVal;
0160       break;
0161     case overdefined:
0162     case unknown:
0163     case undef:
0164       break;
0165     }
0166   }
0167
0168   ValueLatticeElement(ValueLatticeElement &&Other)
0169       : Tag(Other.Tag), NumRangeExtensions(0) {
0170     switch (Other.Tag) {
0171     case constantrange:
0172     case constantrange_including_undef:
0173       new (&Range) ConstantRange(std::move(Other.Range));
0174       NumRangeExtensions = Other.NumRangeExtensions;
0175       break;
0176     case constant:
0177     case notconstant:
0178       ConstVal = Other.ConstVal;
0179       break;
0180     case overdefined:
0181     case unknown:
0182     case undef:
0183       break;
0184     }
0185     Other.Tag = unknown;
0186   }
0187
0188   ValueLatticeElement &operator=(const ValueLatticeElement &Other) {
0189     destroy();
0190     new (this) ValueLatticeElement(Other);
0191     return *this;
0192   }
0193
0194   ValueLatticeElement &operator=(ValueLatticeElement &&Other) {
0195     destroy();
0196     new (this) ValueLatticeElement(std::move(Other));
0197     return *this;
0198   }
0199
0200   static ValueLatticeElement get(Constant *C) {
0201     ValueLatticeElement Res;
0202     Res.markConstant(C);
0203     return Res;
0204   }
0205   static ValueLatticeElement getNot(Constant *C) {
0206     ValueLatticeElement Res;
0207     assert(!isa<UndefValue>(C) && "!= undef is not supported");
0208     Res.markNotConstant(C);
0209     return Res;
0210   }
0211   static ValueLatticeElement getRange(ConstantRange CR,
0212                                       bool MayIncludeUndef = false) {
0213     if (CR.isFullSet())
0214       return getOverdefined();
0215
0216     if (CR.isEmptySet()) {
0217       ValueLatticeElement Res;
0218       if (MayIncludeUndef)
0219         Res.markUndef();
0220       return Res;
0221     }
0222
0223     ValueLatticeElement Res;
0224     Res.markConstantRange(std::move(CR),
0225                           MergeOptions().setMayIncludeUndef(MayIncludeUndef));
0226     return Res;
0227   }
0228   static ValueLatticeElement getOverdefined() {
0229     ValueLatticeElement Res;
0230     Res.markOverdefined();
0231     return Res;
0232   }
0233
0234   bool isUndef() const { return Tag == undef; }
0235   bool isUnknown() const { return Tag == unknown; }
0236   bool isUnknownOrUndef() const { return Tag == unknown || Tag == undef; }
0237   bool isConstant() const { return Tag == constant; }
0238   bool isNotConstant() const { return Tag == notconstant; }
0239   bool isConstantRangeIncludingUndef() const {
0240     return Tag == constantrange_including_undef;
0241   }
0242   /// Returns true if this value is a constant range. Use \p UndefAllowed to
0243   /// exclude non-singleton constant ranges that may also be undef. Note that
0244   /// this function also returns true if the range may include undef, but only
0245   /// contains a single element. In that case, it can be replaced by a constant.
0246   bool isConstantRange(bool UndefAllowed = true) const {
0247     return Tag == constantrange || (Tag == constantrange_including_undef &&
0248                                     (UndefAllowed || Range.isSingleElement()));
0249   }
0250   bool isOverdefined() const { return Tag == overdefined; }
0251
0252   Constant *getConstant() const {
0253     assert(isConstant() && "Cannot get the constant of a non-constant!");
0254     return ConstVal;
0255   }
0256
0257   Constant *getNotConstant() const {
0258     assert(isNotConstant() && "Cannot get the constant of a non-notconstant!");
0259     return ConstVal;
0260   }
0261
0262   /// Returns the constant range for this value. Use \p UndefAllowed to exclude
0263   /// non-singleton constant ranges that may also be undef. Note that this
0264   /// function also returns a range if the range may include undef, but only
0265   /// contains a single element. In that case, it can be replaced by a constant.
0266   const ConstantRange &getConstantRange(bool UndefAllowed = true) const {
0267     assert(isConstantRange(UndefAllowed) &&
0268            "Cannot get the constant-range of a non-constant-range!");
0269     return Range;
0270   }
0271
0272   std::optional<APInt> asConstantInteger() const {
0273     if (isConstant() && isa<ConstantInt>(getConstant())) {
0274       return cast<ConstantInt>(getConstant())->getValue();
0275     } else if (isConstantRange() && getConstantRange().isSingleElement()) {
0276       return *getConstantRange().getSingleElement();
0277     }
0278     return std::nullopt;
0279   }
0280
0281   ConstantRange asConstantRange(unsigned BW, bool UndefAllowed = false) const {
0282     if (isConstantRange(UndefAllowed))
0283       return getConstantRange();
0284     if (isConstant())
0285       return getConstant()->toConstantRange();
0286     if (isUnknown())
0287       return ConstantRange::getEmpty(BW);
0288     return ConstantRange::getFull(BW);
0289   }
0290
0291   ConstantRange asConstantRange(Type *Ty, bool UndefAllowed = false) const {
0292     assert(Ty->isIntOrIntVectorTy() && "Must be integer type");
0293     return asConstantRange(Ty->getScalarSizeInBits(), UndefAllowed);
0294   }
0295
0296   bool markOverdefined() {
0297     if (isOverdefined())
0298       return false;
0299     destroy();
0300     Tag = overdefined;
0301     return true;
0302   }
0303
0304   bool markUndef() {
0305     if (isUndef())
0306       return false;
0307
0308     assert(isUnknown());
0309     Tag = undef;
0310     return true;
0311   }
0312
0313   bool markConstant(Constant *V, bool MayIncludeUndef = false) {
0314     if (isa<UndefValue>(V))
0315       return markUndef();
0316
0317     if (isConstant()) {
0318       assert(getConstant() == V && "Marking constant with different value");
0319       return false;
0320     }
0321
0322     if (ConstantInt *CI = dyn_cast<ConstantInt>(V))
0323       return markConstantRange(
0324           ConstantRange(CI->getValue()),
0325           MergeOptions().setMayIncludeUndef(MayIncludeUndef));
0326
0327     assert(isUnknown() || isUndef());
0328     Tag = constant;
0329     ConstVal = V;
0330     return true;
0331   }
0332
0333   bool markNotConstant(Constant *V) {
0334     assert(V && "Marking constant with NULL");
0335     if (ConstantInt *CI = dyn_cast<ConstantInt>(V))
0336       return markConstantRange(
0337           ConstantRange(CI->getValue() + 1, CI->getValue()));
0338
0339     if (isa<UndefValue>(V))
0340       return false;
0341
0342     if (isNotConstant()) {
0343       assert(getNotConstant() == V && "Marking !constant with different value");
0344       return false;
0345     }
0346
0347     assert(isUnknown());
0348     Tag = notconstant;
0349     ConstVal = V;
0350     return true;
0351   }
0352
0353   /// Mark the object as constant range with \p NewR. If the object is already a
0354   /// constant range, nothing changes if the existing range is equal to \p
0355   /// NewR and the tag. Otherwise \p NewR must be a superset of the existing
0356   /// range or the object must be undef. The tag is set to
0357   /// constant_range_including_undef if either the existing value or the new
0358   /// range may include undef.
0359   bool markConstantRange(ConstantRange NewR,
0360                          MergeOptions Opts = MergeOptions()) {
0361     assert(!NewR.isEmptySet() && "should only be called for non-empty sets");
0362
0363     if (NewR.isFullSet())
0364       return markOverdefined();
0365
0366     ValueLatticeElementTy OldTag = Tag;
0367     ValueLatticeElementTy NewTag =
0368         (isUndef() || isConstantRangeIncludingUndef() || Opts.MayIncludeUndef)
0369             ? constantrange_including_undef
0370             : constantrange;
0371     if (isConstantRange()) {
0372       Tag = NewTag;
0373       if (getConstantRange() == NewR)
0374         return Tag != OldTag;
0375
0376       // Simple form of widening. If a range is extended multiple times, go to
0377       // overdefined.
0378       if (Opts.CheckWiden && ++NumRangeExtensions > Opts.MaxWidenSteps)
0379         return markOverdefined();
0380
0381       assert(NewR.contains(getConstantRange()) &&
0382              "Existing range must be a subset of NewR");
0383       Range = std::move(NewR);
0384       return true;
0385     }
0386
0387     assert(isUnknown() || isUndef() || isConstant());
0388     assert((!isConstant() || NewR.contains(getConstant()->toConstantRange())) &&
0389            "Constant must be subset of new range");
0390
0391     NumRangeExtensions = 0;
0392     Tag = NewTag;
0393     new (&Range) ConstantRange(std::move(NewR));
0394     return true;
0395   }
0396
0397   /// Updates this object to approximate both this object and RHS. Returns
0398   /// true if this object has been changed.
0399   bool mergeIn(const ValueLatticeElement &RHS,
0400                MergeOptions Opts = MergeOptions()) {
0401     if (RHS.isUnknown() || isOverdefined())
0402       return false;
0403     if (RHS.isOverdefined()) {
0404       markOverdefined();
0405       return true;
0406     }
0407
0408     if (isUndef()) {
0409       assert(!RHS.isUnknown());
0410       if (RHS.isUndef())
0411         return false;
0412       if (RHS.isConstant())
0413         return markConstant(RHS.getConstant(), true);
0414       if (RHS.isConstantRange())
0415         return markConstantRange(RHS.getConstantRange(true),
0416                                  Opts.setMayIncludeUndef());
0417       return markOverdefined();
0418     }
0419
0420     if (isUnknown()) {
0421       assert(!RHS.isUnknown() && "Unknow RHS should be handled earlier");
0422       *this = RHS;
0423       return true;
0424     }
0425
0426     if (isConstant()) {
0427       if (RHS.isConstant() && getConstant() == RHS.getConstant())
0428         return false;
0429       if (RHS.isUndef())
0430         return false;
0431       // If the constant is a vector of integers, try to treat it as a range.
0432       if (getConstant()->getType()->isVectorTy() &&
0433           getConstant()->getType()->getScalarType()->isIntegerTy()) {
0434         ConstantRange L = getConstant()->toConstantRange();
0435         ConstantRange NewR = L.unionWith(
0436             RHS.asConstantRange(L.getBitWidth(), /*UndefAllowed=*/true));
0437         return markConstantRange(
0438             std::move(NewR),
0439             Opts.setMayIncludeUndef(RHS.isConstantRangeIncludingUndef()));
0440       }
0441       markOverdefined();
0442       return true;
0443     }
0444
0445     if (isNotConstant()) {
0446       if (RHS.isNotConstant() && getNotConstant() == RHS.getNotConstant())
0447         return false;
0448       markOverdefined();
0449       return true;
0450     }
0451
0452     auto OldTag = Tag;
0453     assert(isConstantRange() && "New ValueLattice type?");
0454     if (RHS.isUndef()) {
0455       Tag = constantrange_including_undef;
0456       return OldTag != Tag;
0457     }
0458
0459     const ConstantRange &L = getConstantRange();
0460     ConstantRange NewR = L.unionWith(
0461         RHS.asConstantRange(L.getBitWidth(), /*UndefAllowed=*/true));
0462     return markConstantRange(
0463         std::move(NewR),
0464         Opts.setMayIncludeUndef(RHS.isConstantRangeIncludingUndef()));
0465   }
0466
0467   // Compares this symbolic value with Other using Pred and returns either
0468   /// true, false or undef constants, or nullptr if the comparison cannot be
0469   /// evaluated.
0470   Constant *getCompare(CmpInst::Predicate Pred, Type *Ty,
0471                        const ValueLatticeElement &Other,
0472                        const DataLayout &DL) const;
0473
0474   /// Combine two sets of facts about the same value into a single set of
0475   /// facts.  Note that this method is not suitable for merging facts along
0476   /// different paths in a CFG; that's what the mergeIn function is for.  This
0477   /// is for merging facts gathered about the same value at the same location
0478   /// through two independent means.
0479   /// Notes:
0480   /// * This method does not promise to return the most precise possible lattice
0481   ///   value implied by A and B.  It is allowed to return any lattice element
0482   ///   which is at least as strong as *either* A or B (unless our facts
0483   ///   conflict, see below).
0484   /// * Due to unreachable code, the intersection of two lattice values could be
0485   ///   contradictory.  If this happens, we return some valid lattice value so
0486   ///   as not confuse the rest of LVI.  Ideally, we'd always return Undefined,
0487   ///   but we do not make this guarantee.  TODO: This would be a useful
0488   ///   enhancement.
0489   ValueLatticeElement intersect(const ValueLatticeElement &Other) const;
0490
0491   unsigned getNumRangeExtensions() const { return NumRangeExtensions; }
0492   void setNumRangeExtensions(unsigned N) { NumRangeExtensions = N; }
0493 };
0494
0495 static_assert(sizeof(ValueLatticeElement) <= 40,
0496               "size of ValueLatticeElement changed unexpectedly");
0497
0498 raw_ostream &operator<<(raw_ostream &OS, const ValueLatticeElement &Val);
0499 } // end namespace llvm
0500 #endif