This is an archive of the discontinued LLVM Phabricator instance.

[LSR] Allow already invariant operand for ICmpZero matching [try 2]
ClosedPublic

Authored by reames on Jul 14 2022, 11:48 AM.

Details

Summary

Changes since initial commit:

  • Wrapping a pointer in an SCEV unknown hides the base, and SCEV is only able to compute a subtraction when the bases are known to be equal. This results in a SCEVCouldNotCompute flowing forward and triggering asserts. Test case added in d767b392.
  • isLoopInvariant returns true for instructions outside the loop, but necessarily *above* the loop. Since this code is allowed to visit uses of an IV outside of a loop, we have to make sure the operands of the compare are both invariant and dominating the header. Test case added in 2aed3cdb.

Original commit message follows...

The ICmpZero matching is checking to see if the expression is loop invariant per SCEV and expandable. This allows expressions inside the loop which can be made loop invariant to be seamlessly expanded, but is overly conservative for expressions which already *are* loop invariant.

As a simple justification for why this is correct, consider a loop invariant urem as RHS vs an alternate function with that same urem wrapped inside a helper call. Why would it be legal to match the later, but not the former?

Diff Detail

Event Timeline

reames created this revision.Jul 14 2022, 11:48 AM
reames requested review of this revision.Jul 14 2022, 11:48 AM
Herald added a project: Restricted Project. · View Herald TranscriptJul 14 2022, 11:48 AM
nikic accepted this revision.Jul 15 2022, 12:39 AM

LGTM

This revision is now accepted and ready to land.Jul 15 2022, 12:39 AM
This revision was landed with ongoing or failed builds.Jul 15 2022, 9:51 AM
This revision was automatically updated to reflect the committed changes.

It looks like this may cause crashes on some bots, e.g. https://lab.llvm.org/buildbot#builders/168/builds/7520

It looks like this may cause crashes on some bots, e.g. https://lab.llvm.org/buildbot#builders/168/builds/7520

Agreed, that does look related. Reverted while I investigate.

It looks like this may cause crashes on some bots, e.g. https://lab.llvm.org/buildbot#builders/168/builds/7520

Agreed, that does look related. Reverted while I investigate.

was just looking at this, here's a reduced test case if it's helpful

target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
target triple = "x86_64-unknown-linux-gnu"

define void @f() {
  br label %1

1:                                                ; preds = %1, %0
  %2 = phi i64 [ %3, %1 ], [ 0, %0 ]
  %3 = add nuw i64 %2, 1
  br i1 true, label %4, label %1

4:                                                ; preds = %1
  %5 = trunc i64 %2 to i32
  br label %6

6:                                                ; preds = %4
  %7 = add i32 %5, 1
  br label %8

8:                                                ; preds = %6
  %9 = icmp eq i32 %5, %7
  ret void
}
$ ./build/rel/bin/opt -loop-reduce
Instruction does not dominate all uses!
  %8 = add i32 %5, 1
  %6 = add i32 %8, 1
craig.topper added inline comments.
llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp
3354

unknwon -> unknown

Interestingly, we appear to have at least two distinct bugs here.

One is a straight forward bug in the patch where I didn't account for pointer subtraction properly.

The second - which Artur reported - appears to be something else. Working on identifying that now, my tentative guess is that's a latent bug in LSR simply being exposed by this change.

reames updated this revision to Diff 445082.Jul 15 2022, 11:46 AM

Version with fix for pointer difference bug.

I think I now understand Arthur's case. This is visit uses outside of loop L, and L->isLoopInvariant returns true for instructions outside the loop even if that instruction does not dominate L. Going to reduce a minimal test case (to confirm theory), and then update with the second fix.

reames reopened this revision.Jul 15 2022, 11:46 AM
This revision is now accepted and ready to land.Jul 15 2022, 11:46 AM
reames updated this revision to Diff 445096.Jul 15 2022, 12:21 PM
reames retitled this revision from [LSR] Allow already invariant operand for ICmpZero matching to [LSR] Allow already invariant operand for ICmpZero matching [try 2].
reames edited the summary of this revision. (Show Details)

Version with both bugs fixed

reames requested review of this revision.Jul 15 2022, 12:22 PM

Requesting re-review since this changed pretty majorly from the approved version.

nikic accepted this revision.Jul 15 2022, 1:20 PM

LG

llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp
3346

I was going to say the check for instructions is unnecessary, but this is the one dominates() API where it is needed: https://github.com/llvm/llvm-project/blob/09531ede6d5622da68941902072dbca517d31318/llvm/include/llvm/IR/Dominators.h#L199-L201

This revision is now accepted and ready to land.Jul 15 2022, 1:20 PM
This revision was landed with ongoing or failed builds.Jul 15 2022, 1:30 PM
This revision was automatically updated to reflect the committed changes.