[llvm-bugs] [Bug 43678] New: [LSR] LSR creates use-before-def case

[via llvm-bugs]

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

            Bug ID: 43678
           Summary: [LSR] LSR creates use-before-def case
           Product: libraries
           Version: trunk
          Hardware: PC
                OS: Linux
            Status: NEW
          Severity: normal
          Priority: P
         Component: Scalar Optimizations
          Assignee: unassignedbugs at nondot.org
          Reporter: evgueni.brevnov at gmail.com
                CC: llvm-bugs at lists.llvm.org

Created attachment 22670
  --> https://bugs.llvm.org/attachment.cgi?id=22670&action=edit
test case

You will get an error if you try to compile attached test case with the
following command 

> opt manual.nm.ll -passes=strength-reduce -S

Instruction does not dominate all uses!
  %0 = add i32 %local.osr.1, %local_5_49.us
  %tmp2 = add i32 %0, 1
LLVM ERROR: Broken module found, compilation aborted!

I root caused the issue but don't know what would be a proper fix. The problem
is that hoist a user instruction to another block while expanding code for one
of its uses. As a result the user ends up placed before its uses.

During code expansion/rewriting for tmp1 in "%tmp2 = add i32 %tmp1, 1" we hoist
%tmp1 & %tmp2 from the second to the first block.

Here is the code in responsible for this:

      // Check whether we can reuse this PHI node.
      if (LSRMode) {
        if (!isExpandedAddRecExprPHI(&PN, TempIncV, L))
          continue;
        if (L == IVIncInsertLoop && !hoistIVInc(TempIncV, IVIncInsertPos))
          continue;
      } else {
        if (!isNormalAddRecExprPHI(&PN, TempIncV, L))
          continue;
      }

Note the call to hoistIVInc, where IVIncInsertPos is set once for entire
expansion. Since there is another post-inc use in the first block,
IVIncInsertPos points to an instruction there.

But actual IP determined at the beginning of LSRInstance::Expand ('IP =
AdjustInsertPositionForExpand(IP, LF, LU, Rewriter);') belongs to the second
block.

As a result we end up placing use in the first block while def in the second.


I verified that the following workaround helps to this case but it's definitely
not a solution:

index 7f119175c4a..660b49e70bc 100644
--- a/llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp
+++ b/llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp
@@ -5221,6 +5221,8 @@ Value *LSRInstance::Expand(const LSRUse &LU, const
LSRFixup &LF,
   // Flush the operand list to suppress SCEVExpander hoisting of both folded
and
   // unfolded offsets. LSR assumes they both live next to their uses.
   if (!Ops.empty()) {
+    IP = AdjustInsertPositionForExpand(LF.UserInst->getIterator(), LF, LU,
Rewriter);
+    Rewriter.setInsertPoint(&*IP);
     Value *FullV = Rewriter.expandCodeFor(SE.getAddExpr(Ops), Ty);
     Ops.clear();
     Ops.push_back(SE.getUnknown(FullV));



Any thoughts?

Thanks
Evgeniy

-- 
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/20191015/8dfc6089/attachment.html>