[LVI] Try to document the complexities of context instructions

[reames]

Summary

This is an attempt to document and clarify the semantics of the context instruction parameter and how it interacts with LVI's primary analysis algorithm. I've found myself having to explain this a bunch of times over and I'm pretty sure that *I* get it wrong about half the time.

I'm really curious if this explanation makes sense to others and if they think it's actually correct w.r.t. both implementation and intent. :) With that in mind, I've added both LVI old hands and a few folks who've touched it a bit recently. I'd appreciate multiple sets of eyes.

[sanjoy]

include/llvm/Analysis/LazyValueInfo.h

68

I almost hate nitpicking on this, but you have an extra ~.

69

I'd s/Block, Edge/basic block or basic block edge/ The way you've written it now, it looks like a tuple of a block and an edge.

73

s/a true/are true/

78

This is stylistic and my personal preference (so feel free to ignore), but I'd not put the stuff about IPO / guards / assumes here (maybe as a footnote, but not "inlined" here like this).

Instead, I'd say However, there are control flow facts which can become true part way through a block (for instance, once after a pointer has been dereferenced, we know it is non-null). and continue with your main point of describing CtxI.

84

Have you tried restructuring the description this way:

The LVI query predicates accept a CFG element (Block, Edge) and an optional context instruction.  When a context instruction is present ... (semantics of the context instruction).  If it isn't present, we pretend the context instruction is the beginning of the block / somewhere "inside" the edge.

91

But what if execution does not reach the context instruction?

[reames]

include/llvm/Analysis/LazyValueInfo.h

78

I really think the assume/guard bits need to be there, but otherwise someone reading has no way to connect it to the implementation. Adding a footnote with an reference might work. Would you find that cleaner?

84

Hm, you repharsing of the missing context case is interesting. In particular, we might be able to implement the semantics you suggest and get slightly more precise results than we do today. This *isn't* our semantic today, but it would be a completely reasonable one and I don't think it would break any existing users.

We'd have to pick beginning or end consistently. End seems like it's more powerful, what do you think? (i.e. for an invoke's normal edge, we'd want the context to be the first non-phi instruction in the normal block, not the invoke itself.)

91

Today, I believe the answer is "don't do that!" or "UB". This may very well be a latent bug in a couple of transforms. JumpThreading - which is the main transform which exploits this - seems okay on first read.

[anna]

include/llvm/Analysis/LazyValueInfo.h

77

s/an context/a context/

84

How is the value chosen currently when the context instruction is not specified? Is this correct:

1. in the case of single Block -- value of Y depends on all instructions in BB? One of these instructions might as well be the context instruction, but it wasnt specified.
2. for Edge (start BB, end BB) -- value of Y depends on instructions from first inst in start BB upto last inst in end BB.

lib/Analysis/LazyValueInfo.cpp

965

extra 'is' - 'This result is safe to'

[anna]

include/llvm/Analysis/LazyValueInfo.h

84

Coming back to this, since it would be better to document this clearly and clarify our assumptions :)

I think LVI info is for an entire basic block. Once we have guards and instructions that are not `guaranteedToTransferExecutionToSuccessor` in the block, the info at beginning maybe different from the end. However, this is handled correctly depending on the Context Instruction passed in. If there's no CtxtI instruction, we should conservatively chose the info as that in the beginning of the block in such cases.

include/llvm/Analysis/LazyValueInfo.h

public:
 
   /// This is used to return true/false/dunno results.
   enum Tristate {
     Unknown = -1, False = 0, True = 1
   };
 
   // Public query interface.
 
+  /// Understanding Context Instructions, Assumes, and Guards
+  /// --------------------------------------------------------
+  ///    The LVI query predicates accept a CFG element (Block, Edge) and an
+  /// optional context instruction.  Without a context specified, the return
+  /// value simply describes facts known to be true at the specified CFG
+  /// element.  That is, a value might be known constant within a block or on a
+  /// given edge.  Without a context, the facts returned a true anywhere within
+  /// the specified block.
+  ///    However, there are control flow facts which can become true part way
+  /// through a block.  The simplest example is we may encounter a function
+  /// which throws if it's argument is non-zero.  For an context before that
+  /// function call, we have to assume the value might be non-zero, but after
+  /// the function call, we know the value is zero.  In general, we don't
+  /// exploit such interprocedural reasoning today, but in principle, we
+  /// could.  Today, we do have a couple of argument attributes (e.g. nonnull)
+  /// which can summarize interprocedural facts.  We also have a couple of
+  /// special intrinsics with related semantics: assume, and guards.
+  ///    The optional context instruction provides a means to query these
+  /// facts.  We also allow context instructions which are not within the block
+  /// being queried.  This ends up being very useful for a number of transforms
+  /// (e.g. jump-threading) as it allows questions of the form "what is the
+  /// value of Y in BB if I reach CxtI?".   As such, the return value of a call
+  /// which names both a CFG element and a context instruction describes a
+  /// property of the specified Value which is true at the given CFG element if
+  /// execution also reaches the context instruction.
+  ///    TODO: We could be much more aggressive about exploiting the last point
+  /// if we thought this was profitable for transforms.
+  /// --------------------------------------------------------
+
   /// Determine whether the specified value comparison with a constant is known
-  /// to be true or false on the specified CFG edge.
-  /// Pred is a CmpInst predicate.
+  /// to be true or false on the specified CFG edge.  Pred is a CmpInst
+  /// predicate. See note above about semantics of context instructions.
   Tristate getPredicateOnEdge(unsigned Pred, Value *V, Constant *C,
                               BasicBlock *FromBB, BasicBlock *ToBB,
                               Instruction *CxtI = nullptr);
 
   /// Determine whether the specified value comparison with a constant is known
-  /// to be true or false at the specified instruction
-  /// (from an assume intrinsic). Pred is a CmpInst predicate.
+  /// to be true or false at the specified instruction. Pred is a CmpInst
+  /// predicate. 
   Tristate getPredicateAt(unsigned Pred, Value *V, Constant *C,
                           Instruction *CxtI);
 
-  /// Determine whether the specified value is known to be a
-  /// constant at the end of the specified block.  Return null if not.
+  /// Determine whether the specified value is known to be a constant within
+  /// the specified block.  Return null if not. See note above about semantics
+  /// of context instructions. 
   Constant *getConstant(Value *V, BasicBlock *BB, Instruction *CxtI = nullptr);
 
+  /// Determine whether the specified value is known to be a constant at the
+  /// the specified context instruction.  Return null if not. 
+  Constant *getConstant(Value *V, Instruction *CxtI) {
+    return getConstant(V, CxtI->getParent(), CxtI);
+  }
+
   /// Return the ConstantRange constraint that is known to hold for the
-  /// specified value at the end of the specified block. This may only be called
-  /// on integer-typed Values.
-  ConstantRange getConstantRange(Value *V, BasicBlock *BB, Instruction *CxtI = nullptr);
+  /// specified value within the specified block . This may only be called on
+  /// integer-typed Values. See note above about semantics of context
+  /// instructions. 
+  ConstantRange getConstantRange(Value *V, BasicBlock *BB,
+                                 Instruction *CxtI = nullptr);
 
-  /// Determine whether the specified value is known to be a
-  /// constant on the specified edge.  Return null if not.
+  /// Returns the ConstantRange constraint known to be true for 'V' at the
+  /// specified context.
+  ConstantRange getConstantRange(Value *V, Instruction *CxtI);
+
+  /// Determine whether the specified value is known to be a constant on the
+  /// specified edge, given execution reaches both Edge and (optionally) CxtI.
+  /// Return null if not. See note above about semantics of context
+  /// instructions.
   Constant *getConstantOnEdge(Value *V, BasicBlock *FromBB, BasicBlock *ToBB,
                               Instruction *CxtI = nullptr);
 
   /// Inform the analysis cache that we have threaded an edge from
   /// PredBB to OldSucc to be from PredBB to NewSucc instead.
   void threadEdge(BasicBlock *PredBB, BasicBlock *OldSucc, BasicBlock *NewSucc);
 
   /// Inform the analysis cache that we have erased a block.

lib/Analysis/LazyValueInfo.cpp

struct LVIValueHandle final : public CallbackVH {
     void deleted() override;
     void allUsesReplacedWith(Value *V) override {
       deleted();
     }
   };
 } // end anonymous namespace
 
 namespace {
-  /// This is the cache kept by LazyValueInfo which
-  /// maintains information about queries across the clients' queries.
+  /// This is the cache kept by LazyValueInfo which  maintains information
+  /// about queries across the clients' queries.  Note that facts stored in
+  /// this structure are true for a given Value anywhere within the given
+  /// block. This means that an unconditional assume within a block can
+  /// influence the value cached, but that an assume after a potentially
+  /// throwing call can not.    
   class LazyValueInfoCache {
     /// This is all of the cached block information for exactly one Value*.
     /// The entries are sorted by the BasicBlock* of the
     /// entries, allowing us to do a lookup with a binary search.
     /// Over-defined lattice values are recorded in OverDefinedCache to reduce
     /// memory overhead.
     struct ValueCacheEntryTy {
       ValueCacheEntryTy(Value *V, LazyValueInfoCache *P) : Handle(V, P) {}
bool LazyValueInfoImpl::solveBlockValuePHINode(LVILatticeVal &BBLV,
   BBLV = Result;
   return true;
 }
 
 static LVILatticeVal getValueFromCondition(Value *Val, Value *Cond,
                                            bool isTrueDest = true);
 
 // If we can determine a constraint on the value given conditions assumed by
-// the program, intersect those constraints with BBLV
+// the program, intersect those constraints with BBLV.
+// Note: This function is used in two related but distinct purposes.  Within
+// the solve infrastructure, it is used to find assumed facts which are true
+// about intermediate values at their point of use.  This is result is safe to
+// cache since the def-use graph/cfg is fixed for all queuries.  For an
+// individual query, we also intersect facts about the specific context
+// instruction provided with the cached result.  This produces a result which
+// is valid for a given query, but can't be cached because it is context
+// specific. 
 void LazyValueInfoImpl::intersectAssumeOrGuardBlockValueConstantRange(
         Value *Val, LVILatticeVal &BBLV, Instruction *BBI) {
   BBI = BBI ? BBI : dyn_cast<Instruction>(Val);
   if (!BBI)
     return;
 
   for (auto &AssumeVH : AC->assumptions()) {
     if (!AssumeVH)
       continue;
     auto *I = cast<CallInst>(AssumeVH);
     if (!isValidAssumeForContext(I, BBI, DT))
       continue;
 
     BBLV = intersect(BBLV, getValueFromCondition(Val, I->getArgOperand(0)));
   }
 
   // If guards are not used in the module, don't spend time looking for them
   auto *GuardDecl = BBI->getModule()->getFunction(
           Intrinsic::getName(Intrinsic::experimental_guard));
   if (!GuardDecl || GuardDecl->use_empty())
     return;
 
+  // TODO: handle guards in dominating blocks as well
   for (BasicBlock::iterator I = BBI->getIterator(),
                             E = BBI->getParent()->begin(); I != E; I--) {
     Value *Cond = nullptr;
     if (!match(&*I, m_Intrinsic<Intrinsic::experimental_guard>(m_Value(Cond))))
       continue;
     BBLV = intersect(BBLV, getValueFromCondition(Val, Cond));
   }
 }

 Constant *LazyValueInfo::getConstant(Value *V, BasicBlock *BB,
                                      Instruction *CxtI) {
   // Bail out early if V is known not to be a Constant.
   if (isKnownNonConstant(V))
     return nullptr;
 
   const DataLayout &DL = BB->getModule()->getDataLayout();
   LVILatticeVal Result =
-      getImpl(PImpl, AC, &DL, DT).getValueInBlock(V, BB, CxtI);
+      getImpl(PImpl, AC, &DL, DT).getValueInBlock(V, BB);
 
   if (Result.isConstant())
     return Result.getConstant();
   if (Result.isConstantRange()) {
     ConstantRange CR = Result.getConstantRange();
     if (const APInt *SingleVal = CR.getSingleElement())
       return ConstantInt::get(V->getContext(), *SingleVal);
   }
   return nullptr;
 }
 
 ConstantRange LazyValueInfo::getConstantRange(Value *V, BasicBlock *BB,
                                               Instruction *CxtI) {
   assert(V->getType()->isIntegerTy());
   unsigned Width = V->getType()->getIntegerBitWidth();
   const DataLayout &DL = BB->getModule()->getDataLayout();
   LVILatticeVal Result =
-      getImpl(PImpl, AC, &DL, DT).getValueInBlock(V, BB, CxtI);
+  
   if (Result.isUndefined())
     return ConstantRange(Width, /*isFullSet=*/false);
   if (Result.isConstantRange())
     return Result.getConstantRange();
   // We represent ConstantInt constants as constant ranges but other kinds
   // of integer constants, i.e. ConstantExpr will be tagged as constants
   assert(!(Result.isConstant() && isa<ConstantInt>(Result.getConstant())) &&
          "ConstantInt value must be represented as constantrange");
   return ConstantRange(Width, /*isFullSet=*/true);
 }
 
+ConstantRange LazyValueInfo::getConstantRange(Value *V, Instruction *CxtI) {
+  return getConstantRange(V, CxtI->getParent(), CxtI);
+}
+
 /// Determine whether the specified value is known to be a
 /// constant on the specified edge. Return null if not.
 Constant *LazyValueInfo::getConstantOnEdge(Value *V, BasicBlock *FromBB,
                                            BasicBlock *ToBB,
                                            Instruction *CxtI) {
   const DataLayout &DL = FromBB->getModule()->getDataLayout();
   LVILatticeVal Result =
       getImpl(PImpl, AC, &DL, DT).getValueOnEdge(V, FromBB, ToBB, CxtI);

lib/Transforms/Scalar/CorrelatedValuePropagation.cpp

 Pass *llvm::createCorrelatedValuePropagationPass() {
   return new CorrelatedValuePropagation();
 }
 
 static bool processSelect(SelectInst *S, LazyValueInfo *LVI) {
   if (S->getType()->isVectorTy()) return false;
   if (isa<Constant>(S->getOperand(0))) return false;
 
-  Constant *C = LVI->getConstant(S->getOperand(0), S->getParent(), S);
+  Constant *C = LVI->getConstant(S->getOperand(0), S);
   if (!C) return false;
 
   ConstantInt *CI = dyn_cast<ConstantInt>(C);
   if (!CI) return false;
 
   Value *ReplaceWith = S->getOperand(1);
   Value *Other = S->getOperand(2);
   if (!CI->isOne()) std::swap(ReplaceWith, Other);
static bool processMemAccess(Instruction *I, LazyValueInfo *LVI) {
   Value *Pointer = nullptr;
   if (LoadInst *L = dyn_cast<LoadInst>(I))
     Pointer = L->getPointerOperand();
   else
     Pointer = cast<StoreInst>(I)->getPointerOperand();
 
   if (isa<Constant>(Pointer)) return false;
 
-  Constant *C = LVI->getConstant(Pointer, I->getParent(), I);
+  Constant *C = LVI->getConstant(Pointer, I);
   if (!C) return false;
 
   ++NumMemAccess;
   I->replaceUsesOfWith(Pointer, C);
   return true;
 }
 
 /// See if LazyValueInfo's ability to exploit edge conditions or range
static bool processAdd(BinaryOperator *AddOp, LazyValueInfo *LVI) {
   if (AddOp->getType()->isVectorTy() || hasLocalDefs(AddOp))
     return false;
 
   bool NSW = AddOp->hasNoSignedWrap();
   bool NUW = AddOp->hasNoUnsignedWrap();
   if (NSW && NUW)
     return false;
 
-  BasicBlock *BB = AddOp->getParent();
-
   Value *LHS = AddOp->getOperand(0);
   Value *RHS = AddOp->getOperand(1);
 
-  ConstantRange LRange = LVI->getConstantRange(LHS, BB, AddOp);
+  ConstantRange LRange = LVI->getConstantRange(LHS, AddOp);
 
   // Initialize RRange only if we need it. If we know that guaranteed no wrap
   // range for the given LHS range is empty don't spend time calculating the
   // range for the RHS.
   Optional<ConstantRange> RRange;
   auto LazyRRange = [&] () {
       if (!RRange)
-        RRange = LVI->getConstantRange(RHS, BB, AddOp);
+        RRange = LVI->getConstantRange(RHS, AddOp);
       return RRange.getValue();
   };
 
   bool Changed = false;
   if (!NUW) {
     ConstantRange NUWRange =
             LRange.makeGuaranteedNoWrapRegion(BinaryOperator::Add, LRange,
                                               OBO::NoUnsignedWrap);
if (!NSWRange.isEmptySet()) {
       Changed |= NewNSW;
     }
   }
 
   return Changed;
 }
 
 static Constant *getConstantAt(Value *V, Instruction *At, LazyValueInfo *LVI) {
-  if (Constant *C = LVI->getConstant(V, At->getParent(), At))
+  if (Constant *C = LVI->getConstant(V, At))
     return C;
 
   // TODO: The following really should be sunk inside LVI's core algorithm, or
   // at least the outer shims around such.
   auto *C = dyn_cast<CmpInst>(V);
   if (!C) return nullptr;
 
   Value *Op0 = C->getOperand(0);