[DSE] Relax constraint on isGuaranteedLoopInvariant

[StephenFan]

Summary

If the location ptr to be killed is in no loop and the Function does not
have irreducible loops, then we can regard it as loop invariant.

[nikic]

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

1202

Spurious newline? This should either be one line higher or not exist.

1218–1221

I wonder whether we should retain the entry block check as well. That would make sure that even with irreducible cycles we will at least handle the important case of (constant geps of) allocas.

[StephenFan]

1. Add a testcase
2. Check isEntryBlock no matter if contains irreducible loops

[nikic]

LGTM

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

bool isGuaranteedLoopIndependent(const Instruction *Current,
                                    const MemoryLocation &CurrentLoc) {
     // If the dependency is within the same block or loop level (being careful
     // of irreducible loops), we know that AA will return a valid result for the
     // memory dependency. (Both at the function level, outside of any loop,
     // would also be valid but we currently disable that to limit compile time).
     if (Current->getParent() == KillingDef->getParent())
       return true;
     const Loop *CurrentLI = LI.getLoopFor(Current->getParent());
     if (!ContainsIrreducibleLoops && CurrentLI &&
         CurrentLI == LI.getLoopFor(KillingDef->getParent()))
       return true;
     // Otherwise check the memory location is invariant to any loops.
     return isGuaranteedLoopInvariant(CurrentLoc.Ptr);
   }
 
   /// Returns true if \p Ptr is guaranteed to be loop invariant for any possible
   /// loop. In particular, this guarantees that it only references a single
   /// MemoryLocation during execution of the containing function.
   bool isGuaranteedLoopInvariant(const Value *Ptr) {
     Ptr = Ptr->stripPointerCasts();
     if (auto *GEP = dyn_cast<GEPOperator>(Ptr))
       if (GEP->hasAllConstantIndices())
         Ptr = GEP->getPointerOperand()->stripPointerCasts();
 
-    if (auto *I = dyn_cast<Instruction>(Ptr))
-      return I->getParent()->isEntryBlock();
+    if (auto *I = dyn_cast<Instruction>(Ptr)) {
+      return I->getParent()->isEntryBlock() ||
+             (!ContainsIrreducibleLoops && !LI.getLoopFor(I->getParent()));
+    }
     return true;
   }
 
   // Find a MemoryDef writing to \p KillingLoc and dominating \p StartAccess,
   // with no read access between them or on any other path to a function exit
   // block if \p KillingLoc is not accessible after the function returns. If
   // there is no such MemoryDef, return None. The returned value may not
   // (completely) overwrite \p KillingLoc. Currently we bail out when we

llvm/test/Transforms/DeadStoreElimination/multiblock-loops.ll

B:
   %exitcond = icmp eq i16 %j.0, 4
   br i1 %exitcond, label %exit, label %A
 
 exit:
   store i16 1, ptr %arrayidx, align 1
   ret i16 0
 }
 
+define i16 @irreducible_entryblock_def(i1 %c) {
+; CHECK-LABEL: @irreducible_entryblock_def(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br i1 [[C:%.*]], label [[A:%.*]], label [[B:%.*]]
+; CHECK:       A:
+; CHECK-NEXT:    br label [[B]]
+; CHECK:       B:
+; CHECK-NEXT:    br i1 [[C]], label [[EXIT:%.*]], label [[A]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret i16 0
+;
+entry:
+  %obj = alloca i32, align 4
+  br i1 %c, label %A, label %B
+
+A:
+  store i32 1, ptr %obj, align 4
+  br label %B
+
+B:
+  br i1 %c, label %exit, label %A
+
+exit:
+  ret i16 0
+}
+
 ; An irreducible loop inside another loop.
 define i16 @irreducible_nested() {
 ; CHECK-LABEL: @irreducible_nested(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br label [[OUTER:%.*]]
 ; CHECK:       outer:
 ; CHECK-NEXT:    [[X:%.*]] = phi i16 [ 0, [[ENTRY:%.*]] ], [ [[INCX:%.*]], [[OUTERL:%.*]] ]
 ; CHECK-NEXT:    [[C:%.*]] = icmp sgt i16 [[X]], 2

 
 
 define i16 @partial_override_overloop(i1 %c, i32 %i) {
 ; CHECK-LABEL: @partial_override_overloop(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br label [[FIRST:%.*]]
 ; CHECK:       first:
 ; CHECK-NEXT:    [[ARRAYIDX:%.*]] = getelementptr inbounds [10 x i16], ptr @x, i16 0, i32 [[I:%.*]]
-; CHECK-NEXT:    store i16 1, ptr [[ARRAYIDX]], align 1
 ; CHECK-NEXT:    br label [[DO_BODY:%.*]]
 ; CHECK:       do.body:
 ; CHECK-NEXT:    [[I_0:%.*]] = phi i16 [ 0, [[FIRST]] ], [ [[INC:%.*]], [[DO_BODY]] ]
 ; CHECK-NEXT:    [[ARRAYIDX2:%.*]] = getelementptr inbounds [10 x i16], ptr @x, i16 0, i16 [[I_0]]
 ; CHECK-NEXT:    store i16 2, ptr [[ARRAYIDX2]], align 1
 ; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp eq i16 [[I_0]], 4
 ; CHECK-NEXT:    [[INC]] = add nuw nsw i16 [[I_0]], 1
 ; CHECK-NEXT:    br i1 [[EXITCOND]], label [[EXIT:%.*]], label [[DO_BODY]]

llvm/test/Transforms/DeadStoreElimination/multiblock-malloc-free.ll

 
 
 define void @test27() {
 ; CHECK-LABEL: @test27(
 ; CHECK-NEXT:  bb1:
 ; CHECK-NEXT:    br i1 true, label [[BB2:%.*]], label [[BB3:%.*]]
 ; CHECK:       bb2:
 ; CHECK-NEXT:    [[M:%.*]] = call noalias ptr @malloc(i64 10)
-; CHECK-NEXT:    store i8 1, ptr [[M]], align 1
 ; CHECK-NEXT:    br label [[BB3]]
 ; CHECK:       bb3:
 ; CHECK-NEXT:    [[R:%.*]] = phi ptr [ null, [[BB1:%.*]] ], [ [[M]], [[BB2]] ]
 ; CHECK-NEXT:    ret void
 ;
 bb1:
   br i1 true, label %bb2, label %bb3
 bb2: