[llvm-bugs] [Bug 30818] New: Infinite loop in Reassociate

[via llvm-bugs]

https://llvm.org/bugs/show_bug.cgi?id=30818

            Bug ID: 30818
           Summary: Infinite loop in Reassociate
           Product: new-bugs
           Version: trunk
          Hardware: PC
                OS: Linux
            Status: NEW
          Severity: normal
          Priority: P
         Component: new bugs
          Assignee: unassignedbugs at nondot.org
          Reporter: bjorn.a.pettersson at ericsson.com
                CC: llvm-bugs at lists.llvm.org
    Classification: Unclassified

Created attachment 17507
  --> https://llvm.org/bugs/attachment.cgi?id=17507&action=edit
Hangs in reassociate

When running "opt -reassociate" on the following program (also included as
attachment) we end up in an infinite loop:

define void @xor_deadloop() {
  br label %endlabel

deadloop:
  %1 = xor i32 %2, 7
  %2 = xor i32 %1, 8
  br label %deadloop

endlabel:
  ret void
}


Problem was detected when doing randomized tests using csmith.
A dead loop similar to the example below was created by -jump-threading.
According to -verify the code is valid. However, the SSA form of the dead loop
is quite interesting.

------------------

One solution (to avoid hanging in Reassociate) is to simply avoid analysis of
dead basic blocks.
For example like this patch:

diff --git a/lib/Transforms/Scalar/Reassociate.cpp
b/lib/Transforms/Scalar/Reassociate.cpp
index 1ec7fce..6fc8dc8 100644
--- a/lib/Transforms/Scalar/Reassociate.cpp
+++ b/lib/Transforms/Scalar/Reassociate.cpp
@@ -2177,8 +2177,19 @@ PreservedAnalyses ReassociatePass::run(Function &F,
FunctionAnalysisManager &) {
   // Calculate the rank map for F.
   BuildRankMap(F);

+  // Mark all reachable blocks.
+  df_iterator_default_set<BasicBlock*> Reachable;
+  for (BasicBlock *BB : depth_first_ext(&F, Reachable))
+    (void)BB/* Mark all reachable blocks */;
+
   MadeChange = false;
   for (Function::iterator BI = F.begin(), BE = F.end(); BI != BE; ++BI) {
+    // Skip dead basic blocks
+    if (!Reachable.count(&*BI)) {
+      DEBUG(dbgs() << "Skipping dead BB:"; BI->dump(););
+      continue;
+    }
+
     // Optimize every instruction in the basic block.
     for (BasicBlock::iterator II = BI->begin(), IE = BI->end(); II != IE;)
       if (isInstructionTriviallyDead(&*II)) {

------------------

I noticed that this problem started to appear after this commit
(so it could be an old problem that appeared again after that revert):

commit a537a2bbfe75a0f15deb93efa5dd9f8ad96971e8
Author: Chad Rosier <mcrosier at codeaurora.org>
Date:   Wed Aug 17 15:54:39 2016 +0000

    Revert "Reassociate: Reprocess RedoInsts after each inst".

    This reverts commit r258830, which introduced a bug described in PR28367.

    PR28367

    git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@278938
91177308-0d34-0410-b5e6-96231b3b80d8

-- 
You are receiving this mail because:
You are on the CC list for the bug.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-bugs/attachments/20161028/e054a54e/attachment.html>