This is an archive of the discontinued LLVM Phabricator instance.

[IndVars] Turn isValidRewrite into an assertion
AbandonedPublic

Authored by mkazantsev on Sep 3 2018, 1:42 AM.

Details

Summary

Function rewriteLoopExitValues contains a check on isValidRewrite which
is needed to make sure that SCEV does not convert the pattern
gep Base, (&p[n] - &p[0]) into gep &p[n], Base - &p[0]. This problem
has been fixed in SCEV long ago, so this check is just obsolete.

This patch converts it into an assertion to make sure that the SCEV will
not mess up this case in the future.

Diff Detail

Event Timeline

mkazantsev created this revision.Sep 3 2018, 1:42 AM
atrick added a comment.Sep 4 2018, 9:49 AM

isValidRewrite is a hack that wasn't supposed to live this long.

At the IR level, the problem is simply that we don't want to rewrite

gep Base, (&p[n] - &p[0])

as

gep &p[n], Base - &p[0]

SCEV no longer does the kind of reassociation. I'm not sure when it was fixed, but the original test case definitely no longer requires the isValidRewrite check.

atrick added a comment.Sep 4 2018, 9:52 AM

@sanjoy may have some insight as to why SCEV is now safe. If we know this why can't happen, you can completely remove isValidRewrite and don't need to assert.

If you want to keep the logic under an assert, then you could add a more understandable comment:

"Avoid converting gep Base, (&p[n] - &p[0]) into gep &p[n], Base - &p[0]"

I think this particular problem was fixed a long time ago, likely
before I started working on SCEV. I think the relevant bit is here:
https://github.com/llvm-mirror/llvm/blob/master/lib/Analysis/ScalarEvolution.cpp#L6451

It's tempting to handle inttoptr and ptrtoint as no-ops, however this can
lead to pointer expressions which cannot safely be expanded to GEPs,
because ScalarEvolution doesn't respect the GEP aliasing rules when
simplifying integer expressions.

because we don't handle ptrtoint (&p[n] - &p[0]) will be a SCEVUnknown
and SCEV should not reassociate through this expression.

  • Sanjoy
atrick added a comment.Sep 4 2018, 1:48 PM

The bitcast bailout (implemented in 2009) (https://github.com/llvm-mirror/llvm/blob/master/lib/Analysis/ScalarEvolution.cpp#L6451)

wasn't catching this case (fixed in 2011). The problem had to do with LCSSA preventing normal SCEV simplification...

Before:

define i8* @stdimpl_itoa(i32 %v, i8* %string, i32 %r) nounwind {
entry:
  %buf.i = alloca [34 x i8], align 4
...
bb4.i12.preheader:                                ; preds = %bb.i4                                                                                                                                      
  %.lcssa20 = phi i8* [ %21, %bb.i4 ]
  br label %bb4.i12

bb4.i12:                                          ; preds = %bb4.i12, %bb4.i12.preheader                                                                                                                
  %start.0.i10 = phi i8* [ %26, %bb4.i12 ], [ %string, %bb4.i12.preheader ]
  %p.1.i11 = phi i8* [ %24, %bb4.i12 ], [ %.lcssa20, %bb4.i12.preheader ]
...
  store i8 %25, i8* %start.0.i10, align 1
  %26 = getelementptr inbounds i8* %start.0.i10, i32 1
  %27 = icmp eq i8* %16, %24
  br i1 %27, label %_ZL5_xtoamPcii.exit14, label %bb4.i12

_ZL5_xtoamPcii.exit14:                            ; preds = %bb4.i12                                                                                                                                    
  %.lcssa19 = phi i8* [ %26, %bb4.i12 ]
  store i8 0, i8* %.lcssa19, align 1
  ret i8* %string

Notice the definition of %26, the phi in the exit block and the store address.

After:

bb4.i12.preheader:                                ; preds = %bb.i4                                                                                                                                      
  %.lcssa20 = phi i8* [ %scevgep31, %bb.i4 ]
...
_ZL5_xtoamPcii.exit14:                            ; preds = %bb4.i12                                                                                                                                    
  %scevgep18 = getelementptr i8* %.lcssa20, i32 %scevgep1617
  store i8 0, i8* %scevgep18, align 1
  ret i8* %string

The address is effectively %scevgep31 which is defined in bb.i4:
%scevgep31 = getelementptr [34 x i8]* %buf.i, i32 0, i32 %tmp30

%buf.i is an alloca so DSE will end up deleting the store.


So, maybe it's best to leave the assertion.

mkazantsev updated this revision to Diff 163963.Sep 4 2018, 7:16 PM
mkazantsev edited the summary of this revision. (Show Details)

Added clarification comment, updated commit message to describe what is going on.

isValidRewrite is a hack that wasn't supposed to live this long.

At the IR level, the problem is simply that we don't want to rewrite

gep Base, (&p[n] - &p[0])

as

gep &p[n], Base - &p[0]

SCEV no longer does the kind of reassociation. I'm not sure when it was fixed, but the original test case definitely no longer requires the isValidRewrite check.

Thanks for explanation! Is the "original test case" you are mentioning present somewhere in the unit tests? If no, I'd appreciate if you could check it in.

Do you guys feel OK if we check in this patch (leaving this as assertion) with the comment update I've just made?

atrick accepted this revision.Sep 5 2018, 8:35 AM

Is the "original test case" you are mentioning present somewhere in the unit tests? If no, I'd appreciate if you could check it in.

It looks like there was some proprietary C code that exposed this but never a reduced .ll test sadly. I'm positive that the original .c test no longer hits this assert, and think it's very unlikely that the current LLVM pipeline could still expose the issue. I'm just not sure exactly how SCEV itself guards against it.

I think it's fine for you to checkin this PR as-is, with the assert as a measure of safety.

This revision is now accepted and ready to land.Sep 5 2018, 8:35 AM
This revision was automatically updated to reflect the committed changes.

It seems we were wrong: http://lab.llvm.org:8011/builders/clang-ppc64be-linux-multistage/builds/11583/steps/build%20stage%202/logs/stdio

Patch reverted as rL341517. It seems that this situation is still possible. I'll try to make a reduced test example on that and commit it separately.

mkazantsev reopened this revision.Sep 5 2018, 10:56 PM

This patch has been reverted, the situation it protects against seems still possible. It means that the initial theory was true and we need a unit test on that.

This revision is now accepted and ready to land.Sep 5 2018, 10:56 PM
mkazantsev planned changes to this revision.Sep 5 2018, 10:56 PM
atrick added a comment.Sep 6 2018, 9:00 AM

It's great that you have a reproducer. Sad that SCEV still hasn't been fixed. As I mentioned, I wasn't able to easily reproduce the problem from source. I know that, back in 2011, the issue was only exposed because LCSSA form was blocking some obvious SCEV optimization.

mkazantsev abandoned this revision.Nov 7 2018, 2:36 AM

I don't think I'll ever have time for this.