Page MenuHomePhabricator

[LV] Relax assumption that LCSSA implies single entry
ClosedPublic

Authored by reames on Dec 22 2020, 12:23 PM.

Details

Summary

This relates to the ongoing effort to support vectorization of multiple exit loops (see D93317).

The previous code assumed that LCSSA phis were always single entry before the vectorizer ran. This was correct, but only because the vectorizer allowed only a single exiting edge. There's nothing in the definition of LCSSA which requires single entry phis.

A common case where this comes up is with a loop with multiple exiting blocks which all reach a common exit block. (e.g. see the test updates)

Diff Detail

Event Timeline

reames created this revision.Dec 22 2020, 12:23 PM
reames requested review of this revision.Dec 22 2020, 12:23 PM
Herald added a project: Restricted Project. · View Herald TranscriptDec 22 2020, 12:23 PM

ping now that previous patch in series has landed

fhahn added inline comments.Tue, Jan 5, 1:18 AM
llvm/lib/Transforms/Vectorize/LoopVectorize.cpp
635–636

This also needs updating now, right? The exit may have phis with multiple incoming values and it needs to fix PHIs without incoming values from the 'middle' block.

4162

This is because we run the last iteration in the scalar loop, right? I think it would be good to extend the comment. Also, the same comment also applies to the similar code in fixReduction and fixLCSSAPHIs as well?

And could you add a test case where we have LCSSA phis where some incoming values are different to the recurrence, as in

define i16 @test(i16* %p, i32 %n) {
entry:
  br label %for.cond

for.cond:
  %i = phi i32 [ 0, %entry ], [ %inc, %for.body ]
  %rec = phi i16 [0, %entry], [ %rec.next, %for.body ]
  %iprom = sext i32 %i to i64
  %b = getelementptr inbounds i16, i16* %p, i64 %iprom
  %rec.next = load i16, i16* %b
  %cmp = icmp slt i32 %i, %n
  br i1 %cmp, label %for.body, label %if.end

for.body:
  store i16 %rec , i16* %b, align 4
  %inc = add nsw i32 %i, 1
  %cmp2 = icmp slt i32 %i, 2096
  br i1 %cmp2, label %for.cond, label %if.end

if.end:
  %rec.lcssa = phi i16 [ %rec, %for.cond ], [ 10, %for.body ]
  ret i16 %rec.lcssa
}
4164

nit: personally I find using any_of slightly more explicit, like

if (any_of(LCSSAPhi.incoming_values(), [Phi](Value *V) { return V == Phi; }))
  LCSSAPhi.addIncoming(ExtractForPhiUsedOutsideLoop, LoopMiddleBlock);

but that's down to personal preference

4371

Should that be reduction and recurrence code above?

llvm/test/Transforms/LoopVectorize/loop-form.ll
349

can you also add a test with multiple unique exits & first-order recurrences/reductions?

like

define i16 @multiple_unique_exit_fof(i16* %p, i32 %n) {
entry:
  br label %for.cond

for.cond:
  %i = phi i32 [ 0, %entry ], [ %inc, %for.body ]
  %rec = phi i16 [0, %entry], [ %rec.next, %for.body ]
  %iprom = sext i32 %i to i64
  %b = getelementptr inbounds i16, i16* %p, i64 %iprom
  %rec.next = load i16, i16* %b
  %cmp = icmp slt i32 %i, %n
  br i1 %cmp, label %for.body, label %if.end

for.body:
  store i16 %rec , i16* %b, align 4
  %inc = add nsw i32 %i, 1
  %cmp2 = icmp slt i32 %i, 2096
  br i1 %cmp2, label %for.cond, label %if.end

if.end:
  ret i16 %rec
}

Not sure if loop-form.ll would be the right place, perhaps adding them to llvm/test/Transforms/LoopVectorize/first-order-recurrence.ll and llvm/test/Transforms/LoopVectorize/reduction.ll respectively would be better.

reames updated this revision to Diff 315669.Sun, Jan 10, 11:48 AM

Address stylistic updates. Test changes to be done separately in near future.

reames updated this revision to Diff 315672.Sun, Jan 10, 12:18 PM

Add requested test.

Will rebase over test additions and reformats shortly.

reames updated this revision to Diff 315674.Sun, Jan 10, 12:37 PM

rebase over landed tests

Ready for re-review.

fhahn accepted this revision.Tue, Jan 12, 3:48 AM

LGTM, thanks!

llvm/test/Transforms/LoopVectorize/loop-form.ll
938–939

nit: would be good to have a comment that this tests multi exit & reductions, perhaps also add it to the name?

This revision is now accepted and ready to land.Tue, Jan 12, 3:48 AM
This revision was automatically updated to reflect the committed changes.