[LoopDeletion] Handle users in unreachable block

[skatkov]

Summary

This is a fix for PR35884.

When we want to delete dead loop we must clean uses in unreachable blocks
otherwise we'll get an assert during deletion of instructions from the loop.

[lebedev.ri]

lib/Transforms/Utils/LoopUtils.cpp

1370

I think this can be simplified down to

for (Use &U : I.uses())

[skatkov]

lib/Transforms/Utils/LoopUtils.cpp

1370

I'm not sure I can do it due to I modify Use in a loop.
I implemented it in this way to be similar to how Value::replace** routines do it.

[lebedev.ri]

lib/Transforms/Utils/LoopUtils.cpp

1370

So if it is an invalid simplification, either this won't compile, or the testcase will fail, right?

[anna]

LGTM w/ comments.

lib/Transforms/Utils/LoopUtils.cpp

1359

I think this is more clearer: "Given LCSSA form is satisfied, we should not have users of instructions within the dead loop outside of the loop. However, LCSSA doesn't take unreachable uses into account. We handle them here".

1364

Nit: only valid operation after dropping references, is deletion.

test/Transforms/LoopDeletion/use-in-unreachable.ll

10

really, this isn't a badloop :)
It's an invariant loop that can be deleted. Perhaps rename to just loop?

lib/Transforms/Utils/LoopUtils.cpp

void llvm::deleteDeadLoop(Loop *L, DominatorTree *DT = nullptr,
   if (DT) {
     // Update the dominator tree by informing it about the new edge from the
     // preheader to the exit.
     DT->insertEdge(Preheader, ExitBlock);
     // Inform the dominator tree about the removed edge.
     DT->deleteEdge(Preheader, L->getHeader());
   }
 
+  // Strongly speaking any instruction in the loop at this moment should not
+  // have a user outside of this loop. However it is possible that there are
+  // some users in unreachable blocks and we want to remove these users here.
+  // We could do it after drop all references (in this case all users in the
+  // loop will be already eliminated and we have less work to do but according
+  // to API doc of User::dropAllReferences no one operation after dropping all
+  // references is valid except deletion. So let's substitute all usages of
+  // instruction from the loop with undef value of corresponding type first.
+  for (auto *Block : L->blocks())
+    for (Instruction &I : *Block) {
+      auto *Undef = UndefValue::get(I.getType());
+      for (Value::use_iterator UI = I.use_begin(), E = I.use_end(); UI != E;) {
+        Use &U = *UI;
+        ++UI;
+        if (auto *Usr = dyn_cast<Instruction>(U.getUser()))
+          if (L->contains(Usr->getParent()))
+            continue;
+        // If we have a DT then we can check that uses outside a loop only in
+        // unreachable block.
+        if (DT)
+          assert(!DT->isReachableFromEntry(U) &&
+                 "Unexpected user in reachable block");
+        U.set(Undef);
+      }
+    }
+
   // Remove the block from the reference counting scheme, so that we can
   // delete it freely later.
   for (auto *Block : L->blocks())
     Block->dropAllReferences();
 
   if (LI) {
     // Erase the instructions and the blocks without having to worry
     // about ordering because we already dropped the references.

test/Transforms/LoopDeletion/use-in-unreachable.ll

+; RUN: opt < %s -loop-deletion -S | FileCheck %s
+
+; Checking that possible users of instruction from the loop in
+; unreachable blocks are handled.
+
+define i64 @foo() {
+entry:
+  br label %badloop
+; CHECK-LABEL-NOT: badloop
+badloop:
+  %indvar1 = phi i64 [ 3, %entry ], [ %indvar2, %badloop_iter ]
+  %check = icmp ult i64 %indvar1, 400
+  br i1 %check, label %badloop_iter, label %loopexit
+badloop_iter:
+  %indvar2 = add i64 %indvar1, 1
+  %baddef = add i64 0, 0
+  br label %badloop
+loopexit:
+  ret i64 0
+deadcode:
+; CHECK-LABEL: deadcode
+; CHECK: ret i64 undef
+  ret i64 %baddef
+}
 No newline at end of file