[LVI] Remove an assert on case which could happen in LazyValueInfo.

[trentxintong]

Summary

If an instruction is defined in a block not the the one we try to get
the value in. We will keep chasing up the predecessors till we figure
out a value for the Val*.

This, however, can take us up to the entry block even though we are
not looking at a function argment.

[reames]

The assertion is checking the a value is not live-in to the entry block unless it is a global. That assert is correct. From your test case, it looks like you've actually found a place where we recurse on a non-local search we shouldn't have. (i.e. a local add with two constant operands should never trigger the backwards walk.)

p.s. You can probably write your test as an IR test.

[• dberlin]

unittests/Analysis/LazyValueInfoTest.cpp

78

FWIW: This is almost certainly easier to just do with Builder rather than parsing assembly strings :)

[• dberlin]

In D46279#1084112, @reames wrote:

The assertion is checking the a value is not live-in to the entry block unless it is a global. That assert is correct. From your test case, it looks like you've actually found a place where we recurse on a non-local search we shouldn't have. (i.e. a local add with two constant operands should never trigger the backwards walk.)

Dunno if you noticed this, but this is because they are specifically asking about the local value at the end of a block that comes before it (IE a block not dominated by the definition of that value).

The add is in block "last", and they are asking for the value of that add in block "lhs".

This is a nonsensical query in the first place, there is no value for the add in block "last".

LVI should, i believe, simply return null here, because the specific value is not known to be constant at the end of the specific block:

"

/// Determine whether the specified value is known to be a
/// constant at the end of the specified block.  Return null if not.
Constant *getConstant(Value *V, BasicBlock *BB, Instruction *CxtI = nullptr);

"

If you ask LVI the query LVI->getConstant(I, Last), it correctly gives the value "20".

The other possibility is to declare this query invalid, since it requires this interface dominance check that V->getParent() dominates BB on every call and return nullptr if false.
Then we just add an assert about it and fix any bugs.
IMHO, unclear that it's worth paying the cost at all, even constant time, for making this query return nullptr. I'm also surethat most calls trying to ask this question are bugs.
While I can think of asking LVI this kind of question in PRE or something where it wants to know what the value would be in a previous block, IMHO it would be better to have a different API where that kind of query is valid and does something sensible (AFAICT, it will not do anything sensible here, like phi translate the operands).

unittests/Analysis/LazyValueInfoTest.cpp

87

This is not guaranteed to return the LHS block, fwiw :)

[trentxintong]

@dberlin @reames I completely agree with the diagnosis and the proposed solution. Let me fix this.

[trentxintong]

And I think adding an assert to check against queries w.r.t. dominance makes sense.

lib/Analysis/LazyValueInfo.cpp

for (Instruction &I : *BB)
         return true;
   return false;
 }
 
 bool LazyValueInfoImpl::solveBlockValueNonLocal(ValueLatticeElement &BBLV,
                                                  Value *Val, BasicBlock *BB) {
   ValueLatticeElement Result;  // Start Undefined.
 
-  // If this is the entry block, we must be asking about an argument.  The
-  // value is overdefined.
-  if (BB == &BB->getParent()->getEntryBlock()) {
-    assert(isa<Argument>(Val) && "Unknown live-in to the entry block");
-    // Before giving up, see if we can prove the pointer non-null local to
-    // this particular block.
+  // If this is the entry block, try to figure out what it is.
+  if (BB == &BB->getParent()->getEntryBlock()) {
     if (Val->getType()->isPointerTy() &&
         (isKnownNonZero(Val, DL) || isObjectDereferencedInBlock(Val, BB))) {
       PointerType *PTy = cast<PointerType>(Val->getType());
       Result = ValueLatticeElement::getNot(ConstantPointerNull::get(PTy));
     } else {
       Result = ValueLatticeElement::getOverdefined();
     }
     BBLV = Result;

unittests/Analysis/CMakeLists.txt

add_llvm_unittest(AnalysisTests
   BlockFrequencyInfoTest.cpp
   BranchProbabilityInfoTest.cpp
   CallGraphTest.cpp
   CFGTest.cpp
   CGSCCPassManagerTest.cpp
   GlobalsModRefTest.cpp
   ValueLatticeTest.cpp
   LazyCallGraphTest.cpp
+  LazyValueInfoTest.cpp
   LoopInfoTest.cpp
   MemoryBuiltinsTest.cpp
   MemorySSA.cpp
   OrderedBasicBlockTest.cpp
   ProfileSummaryInfoTest.cpp
   ScalarEvolutionTest.cpp
   SparsePropagation.cpp
   TargetLibraryInfoTest.cpp
   TBAATest.cpp
   UnrollAnalyzer.cpp
   ValueTrackingTest.cpp
   )

unittests/Analysis/LazyValueInfoTest.cpp

+//===- LazyValueInfoTest.cpp - Lazy Value Info tests ----------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Analysis/LazyValueInfo.h"
+#include "llvm/Analysis/AssumptionCache.h"
+#include "llvm/Analysis/TargetLibraryInfo.h"
+#include "llvm/AsmParser/Parser.h"
+#include "llvm/IR/Dominators.h"
+#include "llvm/IR/Function.h"
+#include "llvm/IR/LLVMContext.h"
+#include "llvm/IR/Module.h"
+#include "llvm/Support/ErrorHandling.h"
+#include "llvm/Support/SourceMgr.h"
+#include "gtest/gtest.h"
+
+namespace llvm {
+namespace {
+
+std::unique_ptr<Module> parseAssembly(LLVMContext &Context,
+                                      const char *Assembly) {
+  SMDiagnostic Error;
+  std::unique_ptr<Module> M = parseAssemblyString(Assembly, Error, Context);
+
+  std::string ErrMsg;
+  raw_string_ostream OS(ErrMsg);
+  Error.print("", OS);
+
+  // A failure here means that the test itself is buggy.
+  if (!M)
+    report_fatal_error(OS.str().c_str());
+
+  return M;
+}
+
+// We use this fixture to ensure that we clean up ScalarEvolution before
+// deleting the PassManager.
+class LazyValueInfoTest : public testing::Test {
+protected:
+  std::unique_ptr<AssumptionCache> AC;
+  std::unique_ptr<DominatorTree> DT;
+  TargetLibraryInfoImpl TLII;
+  TargetLibraryInfo TLI;
+
+  LazyValueInfoTest() : TLI(TLII) {}
+
+  LazyValueInfo buildSE(Function &F) {
+    AC.reset(new AssumptionCache(F));
+    DT.reset(new DominatorTree(F));
+    return LazyValueInfo(&*AC, &(F.getParent()->getDataLayout()), &TLI, &*DT);
+  }
+};
+
+TEST_F(LazyValueInfoTest, PhiValueTracking) {
+  LLVMContext Context;
+  SMDiagnostic Error;
+  auto M = parseAssemblyString(
+      "target datalayout = \"e-m:e-p:32:32-f64:32:64-f80:32-n8:16:32-S128\" "
+      "define void @caller(i1 %c) {"
+      "entry:"
+      "  br i1 %c, label %lhs, label %rhs "
+      " "
+      "lhs: "
+      "  br label %last "
+      " "
+      "rhs: "
+      "  br label %last "
+      " "
+      "last: "
+      "  %x = add i32 10, 10"
+      "  ret void "
+      "}",
+      Error, Context);
+  assert(M && "Bad assembly?");
+  auto *F = (*M).getFunction("caller");
+
+  // Create the lazy value info object.
+  LazyValueInfo LVI = buildSE(*F);
+
+  // Get the add instruction.
+  pred_iterator i = pred_begin(last);
+  BasicBlock *LHS = *i++;
+  BasicBlock *last = &*(--F->end());
+  Instruction *I = &*last->begin();
+
+  // Try to figure out the constants on the edges.
+  Constant *LHSV = LVI.getConstant(I, LHS);
+  assert(!LHSV && "Succeeded to derive a constant ?");
+}
+
+} // namespace
+} // namespace llvm