[NFC] Add a unit test exposing lack of SCEV invalidation in LICM during code hoisting

[DaniilSuchkov]

Summary

This unit test exposes a bug in LICM: when it hoists instructions it doesn't invalidate SCEV accordingly.
Similar test exposing lack of SCEV invalidation during code sinking will be submitted as a follow-up change.

[reames]

I think you can write this test better as an lit test with strict validation. I assume SCEV has an expensive asserts mode - if not, we should add one - and thus this can be written as a lit test with an extra flag to opt.

[DaniilSuchkov]

In D69369#1723838, @reames wrote:

I think you can write this test better as an lit test with strict validation. I assume SCEV has an expensive asserts mode - if not, we should add one - and thus this can be written as a lit test with an extra flag to opt.

There is such a mode in SCEV, but it is explicitly limited to backedge taken count verification (and even there some questionable cases are explicitly ignored). I'm not sure it will be easy to convince folks to extend it.
And you suggest to use extra SCEV validation to force SCEV to cache query results before LICM invocation, right? (to have the effect of line 70 from this test)

[asbirlea]

I think this is a great example of a unit test actually.
Getting to the scenario of forcing ScEv to cache the Load, so we can verify it is no longer properly cached after the Load is hoisted is harder to do in a lit test such that it's so easy to understand, like it is in this unit test.

I think @reames makes great point that we should have a more extensive validation for ScEv and be able to use that in lit tests. If you can take that on, I would be happy to look at the patch.
I don't think we should block the fix that depends on this patch on it though.

llvm/unittests/Transforms/Scalar/CMakeLists.txt

 set(LLVM_LINK_COMPONENTS
   Analysis
   AsmParser
   Core
+  Passes
   Support
   ScalarOpts
   TransformUtils
   )
 
 add_llvm_unittest(ScalarTests
+  LICMTest.cpp
   LoopPassManagerTest.cpp
   )
 
+target_link_libraries(ScalarTests PRIVATE LLVMTestingSupport)
+
 # Workaround for the gcc 6.1 bug https://gcc.gnu.org/bugzilla/show_bug.cgi?id=80916.
 if (CMAKE_COMPILER_IS_GNUCXX AND CMAKE_CXX_COMPILER_VERSION VERSION_GREATER 6.0 AND CMAKE_CXX_COMPILER_VERSION VERSION_LESS 9.0)
   set_source_files_properties(LoopPassManagerTest.cpp PROPERTIES COMPILE_FLAGS -Wno-unused-function)
 endif()

llvm/unittests/Transforms/Scalar/LICMTest.cpp

+//===- LICMTest.cpp - LICM unit tests -------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Analysis/ScalarEvolution.h"
+#include "llvm/AsmParser/Parser.h"
+#include "llvm/IR/Module.h"
+#include "llvm/Passes/PassBuilder.h"
+#include "llvm/Support/SourceMgr.h"
+#include "llvm/Testing/Support/Error.h"
+#include "llvm/Transforms/Scalar/LICM.h"
+#include "gtest/gtest.h"
+
+namespace llvm {
+
+TEST(LICMTest, TestSCEVInvalidationOnHoisting) {
+  LLVMContext Ctx;
+  ModulePassManager MPM;
+  PassBuilder PB;
+  LoopAnalysisManager LAM;
+  FunctionAnalysisManager FAM;
+  CGSCCAnalysisManager CGAM;
+  ModuleAnalysisManager MAM;
+
+  PB.registerModuleAnalyses(MAM);
+  PB.registerCGSCCAnalyses(CGAM);
+  PB.registerFunctionAnalyses(FAM);
+  PB.registerLoopAnalyses(LAM);
+  PB.crossRegisterProxies(LAM, FAM, CGAM, MAM);
+
+  StringRef PipelineStr = "require<opt-remark-emit>,loop(licm)";
+  ASSERT_THAT_ERROR(PB.parsePassPipeline(MPM, PipelineStr), Succeeded());
+
+  SMDiagnostic Error;
+  StringRef Text = R"(
+    define void @foo(i64* %ptr) {
+    entry:
+      br label %loop
+
+    loop:
+      %iv = phi i64 [ 0, %entry ], [ %iv.inc, %loop ]
+      %n = load i64, i64* %ptr, !invariant.load !0
+      %iv.inc = add i64 %iv, 1
+      %cmp = icmp ult i64 %iv.inc, %n
+      br i1 %cmp, label %loop, label %exit
+
+    exit:
+      ret void
+    }
+
+    !0 = !{}
+  )";
+
+  std::unique_ptr<Module> M = parseAssemblyString(Text, Error, Ctx);
+  ASSERT_TRUE(M);
+  Function *F = M->getFunction("foo");
+  ScalarEvolution &SE = FAM.getResult<ScalarEvolutionAnalysis>(*F);
+  BasicBlock &EntryBB = F->getEntryBlock();
+  BasicBlock *LoopBB = EntryBB.getUniqueSuccessor();
+
+  // Select `load i64, i64* %ptr`.
+  Instruction *IBefore = LoopBB->getFirstNonPHI();
+  // Make sure the right instruction was selected.
+  ASSERT_TRUE(isa<LoadInst>(IBefore));
+  // Upon this query SCEV caches disposition of <load i64, i64* %ptr> SCEV.
+  ASSERT_EQ(SE.getBlockDisposition(SE.getSCEV(IBefore), LoopBB),
+            ScalarEvolution::BlockDisposition::DominatesBlock);
+
+  MPM.run(*M, MAM);
+
+  // Select `load i64, i64* %ptr` after it was hoisted.
+  Instruction *IAfter = EntryBB.getFirstNonPHI();
+  // Make sure the right instruction was selected.
+  ASSERT_TRUE(isa<LoadInst>(IAfter));
+
+  ScalarEvolution::BlockDisposition DispositionBeforeInvalidation =
+      SE.getBlockDisposition(SE.getSCEV(IAfter), LoopBB);
+  SE.forgetValue(IAfter);
+  ScalarEvolution::BlockDisposition DispositionAfterInvalidation =
+      SE.getBlockDisposition(SE.getSCEV(IAfter), LoopBB);
+
+  // If LICM have properly invalidated SCEV,
+  //   1. SCEV of <load i64, i64* %ptr> should properly dominate the "loop" BB,
+  //   2. extra invalidation shouldn't change result of the query.
+  // FIXME: these values should be equal!
+  EXPECT_NE(DispositionBeforeInvalidation,
+            ScalarEvolution::BlockDisposition::ProperlyDominatesBlock);
+  // FIXME: these values should be equal!
+  EXPECT_NE(DispositionBeforeInvalidation, DispositionAfterInvalidation);
+}
+}