[llvm-bugs] [Bug 41445] New: [LSR] Rewrite misses some fixup locations if it splits critical edge

[via llvm-bugs]

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

            Bug ID: 41445
           Summary: [LSR] Rewrite misses some fixup locations if it splits
                    critical edge
           Product: libraries
           Version: trunk
          Hardware: PC
                OS: All
            Status: NEW
          Severity: normal
          Priority: P
         Component: Scalar Optimizations
          Assignee: unassignedbugs at nondot.org
          Reporter: denis.bakhvalov at intel.com
                CC: llvm-bugs at lists.llvm.org

Created attachment 21760
  --> https://bugs.llvm.org/attachment.cgi?id=21760&action=edit
Reproducing behavior

If LSR split critical edge during rewriting operand in a phi node which has
other pending fixup locations, those pending locations will not be rewritten.
Because not all locations were rewritten formulae was not implemented
completely and some instructions are not eliminated.

Reproducer attached.
$ opt repro.ll -loop-reduce -S -o -
If you compare IR it's visible that LSR does something non-profitable. For
example, shl instruction was not eliminated, but it's possible to eliminate it.

We have this phi node where all input operands (%1, %2, %3, %4) need to be
rewritten:
%indvars.iv.lcssa.ph = phi i64 [ %1, %then.34 ], [ %2, %ifmerge.34 ], [ %3,
%ifmerge.38 ], [ %4, %ifmerge.42 ]

Then, when we try to rewrite %1, we first split the critical edge. All the
other PHI inputs besides %1 go to a new phi node. Like this:

loop.exit.loopexitsplit:                          ; preds = %ifmerge.42,
%ifmerge.38, %ifmerge.34
  %indvars.iv.lcssa.ph.ph = phi i64 [ %4, %ifmerge.42 ], [ %3, %ifmerge.38 ], [
%2, %ifmerge.34 ]
  br label %loop.exit.loopexit

%indvars.iv.lcssa.ph = phi i64 [ %0, %then.34.loop.exit.loopexit_crit_edge ], [
%indvars.iv.lcssa.ph.ph, %loop.exit.loopexitsplit ]

After that when we try to fix other operands (%2, %3, %4) in the original phi
node (%indvars.iv.lcssa.ph), there are no such operands. And algorithm just
skips those fixup sites, because it can't find them.

At the moment I'm considering 4 possible ways to fix this:
1. Forbid splitting critical edge if there are pending fixup sites in current
PHI.
2. Delay splitting critical edge if there are pending fixup sites in current
PHI, until there will be only one operand to fixup.
3. After splitting critical edge, update all the fixup sites with pointer to
the new PHI node.
4. While searching for operand to rewrite, go down through the PHI chain.

-- 
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/20190409/f52915aa/attachment.html>