[MSSA] Extending IsGuaranteedLoopInvariant to support an instruction defined in the entry block

[fvrmatteo]

Summary

As mentioned in D96979, I'm extending the IsGuaranteedLoopInvariant check also to the MemorySSA.cpp file.

@fhahn For now I didn't unify the function into MemorySSA.h because, as you mentioned, it's not directly MSSA related. I'm open to suggestions to find a better place so we can improve the unification process.

I was also wondering if it would make sense to have a utility function called isEntryBlockInstruction (part of llvm::Instruction) to avoid the ugly check used in this (and the mentioned) patch.

I didn't provide a test yet, because it's not clear to me how to create one that is showing the improvement in the MemorySSA case.

[fhahn]

I didn't provide a test yet, because it's not clear to me how to create one that is showing the improvement in the MemorySSA case.

Could you add a variant of the test added in a0017c2bc258690146f18491317144e487ddb101 ?

[fvrmatteo]

In D97155#2579921, @fhahn wrote:

I didn't provide a test yet, because it's not clear to me how to create one that is showing the improvement in the MemorySSA case.

Could you add a variant of the test added in a0017c2bc258690146f18491317144e487ddb101 ?

I tried, but even though I see the new code being triggered and successfully returning true when expected to do so, I can't seem to notice any difference when printing the MemorySSA information (with -aa-pipeline=basic-aa -passes='print<memoryssa>,verify<memoryssa>'). So I'm still clueless on what should be the expected testable behaviour.

[fvrmatteo]

Added a unit test to verify that the modification to IsGuaranteeLoopInvariant leads to retaining the location information associated to a MemoryAccess (in this case a MemoryPhi) when handling a pointer defined in the entry block.

[fhahn]

In D97155#2606949, @fvrmatteo wrote:

Added a unit test to verify that the modification to IsGuaranteeLoopInvariant leads to retaining the location information associated to a MemoryAccess (in this case a MemoryPhi) when handling a pointer defined in the entry block.

Thanks for adding the test!

Is it possible to have a .ll test instead of the unit test? If we need a unit test, can we at least parse the IR from a string, to make it a bit easier to see what we are working with (e.g. like in https://github.com/llvm/llvm-project/blob/main/llvm/unittests/Analysis/ValueTrackingTest.cpp#L115)

[fvrmatteo]

I couldn't manage to craft a test based on an .ll file, so I kept the unit test, but I'm now parsing the IR from a string.

[fhahn]

LGTM thanks. As mentioned at an earlier review, it would be good to unify the implementation with the one DSE uses.

[fhahn]

I forgot to commit this for you. Let me do that now.

llvm/lib/Analysis/MemorySSA.cpp

bool upward_defs_iterator::IsGuaranteedLoopInvariant(Value *Ptr) const {
   auto IsGuaranteedLoopInvariantBase = [](Value *Ptr) {
     Ptr = Ptr->stripPointerCasts();
     if (!isa<Instruction>(Ptr))
       return true;
     return isa<AllocaInst>(Ptr);
   };
 
   Ptr = Ptr->stripPointerCasts();
+  if (auto *I = dyn_cast<Instruction>(Ptr)) {
+    if (I->getParent() == &I->getFunction()->getEntryBlock()) {
+      return true;
+    }
+  }
   if (auto *GEP = dyn_cast<GEPOperator>(Ptr)) {
     return IsGuaranteedLoopInvariantBase(GEP->getPointerOperand()) &&
            GEP->hasAllConstantIndices();
   }
   return IsGuaranteedLoopInvariantBase(Ptr);
 }

llvm/unittests/Analysis/MemorySSATest.cpp

 //===- MemorySSA.cpp - Unit tests for MemorySSA ---------------------------===//
 //
 // 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/MemorySSA.h"
 #include "llvm/Analysis/AliasAnalysis.h"
 #include "llvm/Analysis/AssumptionCache.h"
 #include "llvm/Analysis/BasicAliasAnalysis.h"
 #include "llvm/Analysis/MemorySSAUpdater.h"
 #include "llvm/Analysis/TargetLibraryInfo.h"
+#include "llvm/AsmParser/Parser.h"
 #include "llvm/IR/BasicBlock.h"
 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/IRBuilder.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/LLVMContext.h"
+#include "llvm/Support/SourceMgr.h"
 #include "gtest/gtest.h"
 
 using namespace llvm;
 
 const static char DLString[] = "e-i64:64-f80:128-n8:16:32:64-S128";
 
 /// There's a lot of common setup between these tests. This fixture helps reduce
 /// that. Tests should mock up a function, store it in F, and then call
TEST_F(MemorySSATest, TestLoadClobber) {
 
   MemoryAccess *Pointer2Clobber = Walker->getClobberingMemoryAccess(
       Load2Access, MemoryLocation(Pointer2, LocationSize::precise(1)));
   EXPECT_TRUE(MSSA.isLiveOnEntryDef(Pointer2Clobber));
 
   MemoryAccess *Load2Clobber = Walker->getClobberingMemoryAccess(Load2Access);
   EXPECT_EQ(Load2Clobber, Load1Access);
 }
+
+// We want to test if the location information are retained
+// when the IsGuaranteedLoopInvariant function handles a
+// memory access referring to a pointer defined in the entry
+// block, hence automatically guaranteed to be loop invariant.
+TEST_F(MemorySSATest, TestLoopInvariantEntryBlockPointer) {
+  SMDiagnostic E;
+  auto LocalM =
+      parseAssemblyString("define void @test(i64 %a0, i8* %a1, i1* %a2) {\n"
+                          "entry:\n"
+                          "%v0 = getelementptr i8, i8* %a1, i64 %a0\n"
+                          "%v1 = bitcast i8* %v0 to i64*\n"
+                          "%v2 = bitcast i8* %v0 to i32*\n"
+                          "%v3 = load i1, i1* %a2\n"
+                          "br i1 %v3, label %body, label %exit\n"
+                          "body:\n"
+                          "store i32 1, i32* %v2\n"
+                          "br label %exit\n"
+                          "exit:\n"
+                          "store i64 0, i64* %v1\n"
+                          "ret void\n"
+                          "}",
+                          E, C);
+  ASSERT_TRUE(LocalM);
+  F = LocalM->getFunction("test");
+  ASSERT_TRUE(F);
+  // Setup the analysis
+  setupAnalyses();
+  MemorySSA &MSSA = *Analyses->MSSA;
+  // Find the exit block
+  for (auto &BB : *F) {
+    if (BB.getName() == "exit") {
+      // Get the store instruction
+      auto *SI = BB.getFirstNonPHI();
+      // Get the memory access and location
+      MemoryAccess *MA = MSSA.getMemoryAccess(SI);
+      MemoryLocation ML = MemoryLocation::get(SI);
+      // Use the 'upward_defs_iterator' which internally calls
+      // IsGuaranteedLoopInvariant
+      auto ItA = upward_defs_begin({MA, ML}, MSSA.getDomTree());
+      auto ItB =
+          upward_defs_begin({ItA->first, ItA->second}, MSSA.getDomTree());
+      // Check if the location information have been retained
+      EXPECT_TRUE(ItB->second.Size.isPrecise());
+      EXPECT_TRUE(ItB->second.Size.hasValue());
+      EXPECT_TRUE(ItB->second.Size.getValue() == 8);
+    }
+  }
+}
 No newline at end of file