This is an archive of the discontinued LLVM Phabricator instance.

[SCEV] Generate AddRec for trivial and LCSSA phis outside of loop header (WIP)
AbandonedPublic

Authored by bmahjour on Dec 13 2019, 2:22 PM.

Details

Summary

The current implementation of createAddRecFromPHI() returns immediately if the phi is not in the loop header. This causes some trivial phi nodes to be represented as SCEVUnknown instead of a proper recurrence. This patch improves the result of SCEV for such cases.
For example consider:

define i64 @test1(i32 signext %n, float* %A) {
entry:
  %0 = sext i32 %n to i64
  br label %do.body

do.body:                                          ; preds = %do.body, %entry
  %indvars.iv = phi i64 [ %indvars.iv.next, %do.body ], [ 0, %entry ]
  %arrayidx = getelementptr inbounds float, float* %A, i64 %indvars.iv
  store float 1.000000e+00, float* %arrayidx, align 4
  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
  %cmp = icmp slt i64 %indvars.iv.next, %0
  br i1 %cmp, label %do.body, label %do.end

do.end:                                           ; preds = %do.body
  %add.lcssa.wide = phi i64 [ %indvars.iv.next, %do.body ]
  ret i64 %add.lcssa.wide
}

The SCEV for %add.lcssa.wide is:

--> %add.lcssa.wide U: [1,2147483648) S: [1,2147483648)

This patch makes it generate the following instead:

--> {1,+,1}<nuw><nsw><%do.body> U: [1,2147483648) S: [1,2147483648) --> (1 smax (sext i32 %n to i64)) U: [1,2147483648) S: [1,2147483648)

Diff Detail

Event Timeline

bmahjour created this revision.Dec 13 2019, 2:22 PM

[suggestion] The scope of the lcssa PHI node and the definition of its value are in different loops, hence calling getSCEVAtScope at the lcssa's scope may simplify the expression. This might even be mandatory since SCEV should be canonical.

[serious] createAddRecFromPHI might be directly called be called getSCEV such that %indvars.iv.next isn't in the cache yet. Therefore the result changes depending on the order in which getSCEV is called.

llvm/lib/Analysis/ScalarEvolution.cpp
5017

Did you consider using getExistingSCEV to check whether it already has been computed?

5335

Why insering this into createAddRecFromPHI and not createNodeForPHI, its only caller?

5341–5344

[serious] Shouldn't this code handle the case? It explicitly mentions the risk of breaking LCSSA, why isn't this the case for your code?

fhahn added inline comments.Dec 16 2019, 4:09 AM
llvm/lib/Analysis/ScalarEvolution.cpp
5341–5344

I think the problem here is that SCEVExpander does not preserve LCSSA at the moment while expanding expressions and looking through LCSSA would break LCSSA form while expanding SCEVs that would refer to a LCSSA instruction without looking through them.

Getting rid of that restriction was discussed in D68194 as well and I have been working on set of follow up patches that make SCEVExpander preserve LCSSA while expanding. I've put up the WIP patches at D71538 and D71539. There are still a few problems/refactors pending before they are ready though.

bmahjour updated this revision to Diff 234615.Dec 18 2019, 2:00 PM
bmahjour marked 5 inline comments as done.

Address Michael's comments.

[suggestion] The scope of the lcssa PHI node and the definition of its value are in different loops, hence calling getSCEVAtScope at the lcssa's scope may simplify the expression. This might even be mandatory since SCEV should be canonical.

If by "lcssa`s scope" you mean the scope at which the lcssa phi instruction appears, then it's not going to help in this case. The scope is the function (outside of any loop). If you pass nullptr to getSCEVAtScope it continues to produce SCEVUnknown.

[serious] createAddRecFromPHI might be directly called be called getSCEV such that %indvars.iv.next isn't in the cache yet. Therefore the result changes depending on the order in which getSCEV is called.

Yes, I was originally concerned that calling getSCEV could cause an infinite loop for cyclic phis, but I gave it more thought and I couldn't come up with a valid IR that can cause the infinite loop. I've changed it to use getSCEV and documented my reasoning for why I don't think a cycle is possible.

llvm/lib/Analysis/ScalarEvolution.cpp
5017

I've replaced this with a call to getSCEV(). Please also see my comment above.

5335

ok, I'll put it at the start of createNodeForPHI.

5341–5344

@fhahn are you considering the other types of non-trivial phis in your patches? eg. %tmp24 = phi i64 [ %tmp14, %bb22 ], [ %tmp14, %bb13 ] in the LIT test bellow.

I think this patch can complement D71539 assuming preservation of LCSSA by SCEVExpander goes in first. For now I can mark this as a child of your patch, unless you'd like to fit this change into yours to handle non-LCSSA trivial phis too.

bmahjour retitled this revision from [SCEV] Generate AddRec for trivial and LCSSA phis outside of loop header. to [SCEV] Generate AddRec for trivial and LCSSA phis outside of loop header (WIP).Dec 18 2019, 2:09 PM
fhahn added inline comments.Dec 19 2019, 9:11 AM
llvm/lib/Analysis/ScalarEvolution.cpp
5341–5344

@fhahn are you considering the other types of non-trivial phis in your patches? eg. %tmp24 = phi i64 [ %tmp14, %bb22 ], [ %tmp14, %bb13 ] in the LIT test bellow.

I *think* that should be handled by my patches automatically, as it just lifts the LI.replacementPreservesLCSSAForm restriction below and the PHI you mentioned should be simplified to %tmp14 by SimplifyInstruction.

What is the status of this? Does it depend on D71538?

If D71538 goes in, are this patch and D71539 equivalent?

What is the status of this? Does it depend on D71538?

If D71538 goes in, are this patch and D71539 equivalent?

I need to find some time to update the linked patches. But I plan to make some progress over the next week

bmahjour abandoned this revision.Apr 20 2022, 9:14 AM

This has been superseded by https://reviews.llvm.org/D71539

Herald added a project: Restricted Project. · View Herald TranscriptApr 20 2022, 9:14 AM