Page MenuHomePhabricator

[SCEV] Handling for ICmp occuring in the evolution chain.
ClosedPublic

Authored by jbhateja on Oct 3 2017, 12:36 AM.

Details

Summary

If a compare instruction is same or inverse of the compare in the
branch of the loop latch, then return a constant evolution node.
This shall facilitate computations of loop exit counts in cases
where compare appears in the evolution chain of induction variables.

Will fix PR 34538

Event Timeline

There are a very large number of changes, so older changes are hidden. Show Older Changes
jbhateja added a comment.EditedOct 23 2017, 7:55 AM

@reviewers, kindly let me know if any other comments.

lib/Analysis/ScalarEvolution.cpp
4092

Could not compute SCEV is returned when visitor could not compute ICmp. This is checked at client side for validating results returned by visitor. Hope I am able to put across my point.

6508

Well in a way we are actually evaluating ICmp by matching it against the latch condition. Shall rename to make it more intuitive to resolve your comment.

junryoungju added a comment.EditedOct 24 2017, 12:34 AM

@reviewers, kindly let me know if any other comments.

I hope just understand that I can be rude a bit, please understand I'm not really good at english. ( I'm just a korean highschool student. )

@reviewers, kindly let me know if any other comments.

I hope just understand that I can be rude a bit, please understand I'm not really good at english. ( I'm just a korean highschool student. )

No issues with your english @junryoungju.
@sanjoy let me know if your concerns have been addressed.

jbhateja retitled this revision from [ScalarEvolution] Handling for ICmp occuring in the evolution chain. to [SCEV] Handling for ICmp occuring in the evolution chain..Oct 24 2017, 1:58 AM
jbhateja updated this revision to Diff 120193.Oct 24 2017, 11:54 PM
  • Review comments resolutions.
This comment was removed by junryoungju.
sanjoy requested changes to this revision.Oct 26 2017, 2:20 PM
sanjoy added inline comments.
lib/Analysis/ScalarEvolution.cpp
4083

I think a better name would be BackedgeConditionFolder. Please also add a one-liner describing what it does.

4100

You can just use a cast<> since you've already checked isa<Instruction>.

4103

Not all select condition operands are icmp instructions.

I also don't think you need the condition to be an icmp instruction -- if the condition is the latch condition, then on increment expression it is going to be true.

4817

I think it would be simpler if you changed SCEVCmpEvaluator::rewrite to not return CouldNotCompute and always just return the rewritten value; and here did:

Ops.push_back(SCEVCmpEvaluator::rewrite(Add->getOperand(i)));
6512

I'd suggest putting this method in SCEVCmpEvaluator; having it on ScalarEvolution will be prone to misuse. Once you do that, you can probably make the convention a bit simpler and have it return a SCEVConstant * which may be null to indicate failure to fold.

6514

This comment needs to be more specific on why the transform is correct -- it isn't that the latch condition is always true, but we know it is true if the backedge is taken.

lib/Transforms/Scalar/LoopStrengthReduce.cpp
2974

Why do you need this change?

This revision now requires changes to proceed.Oct 26 2017, 2:20 PM
junryoungju added a comment.EditedOct 26 2017, 7:04 PM

Okay, just we need to make sure we are evoluting conditional instructions or just checking that instructions are true or false for now.

first one.
If we are "actaully" evoluting a conditional instructions. better creating SCEVConditonal, checking that is true or false when is computing backedge taken count on each AddRec step.
I think this is a correct way for handling conditional instructions.
but, this will cause SCEV jobs MUUUUCHHH SLOWER.

second one.
If we are just checking that instructions are true or false. we do not need to rewrite it, rewriting value means that we handle that value as that "actual" SCEV. (register SCEV on SCEVCallbackVH)
this mean, this is same to write this chain on to createSCEV that we did at first.
so we have to handle it as a "except" of SCEV chain. better inlining code into createAddRecFromPHI.

jbhateja updated this revision to Diff 120731.Oct 28 2017, 4:19 AM
jbhateja edited edge metadata.
  • Review comment resolutions.
sanjoy requested changes to this revision.Oct 30 2017, 12:03 AM

This is looking close to ready, just a few minor things inline.

lib/Analysis/ScalarEvolution.cpp
4092

Doesn't look like L can be nullptr - ScalarEvolution::createAddRecFromPHI bails out early if L is nullptr.

I think you can rewrite this to be:

if (BasicBlock *Latch = ...) {
  ...
}
4115

Calling getSCEV + visit seems a bit overkill -- can't you just compare I->getOperand(0) with LoopBackOnPosCond here?

How about adding an Optional<bool> isValueKnown(Value *Cond) function that returns true or false if Cond is equal to LoopBackOnPosCond else returns None, and using that function in both the cases?

4122

Typically LLVM style is would be putting the break; inside the curly brace block.

4137

A more idiomatic name for this is BackedgeTakenOnTrue.

6506–6530

Whitespace damange?

test/Analysis/ScalarEvolution/pr34538.ll
14

I'd put these two test cases in the same file with a somewhat more descriptive file name. Perhaps you can put the PR number as the function name instead?

This revision now requires changes to proceed.Oct 30 2017, 12:03 AM

:( that I commented didn't reviewed. this is why I wanted to make other reversion.

:( that I commented didn't reviewed. this is why I wanted to make other reversion.

Are you saying that you had made the same comments as I did above? If so, that wasn't clear from what you wrote. You can help authors by:

  • Adding inline comments instead of a top level comment, knowing which part of the patch you're referring to helps comprehension
  • Being specific; instead of saying "this is very general" say "use cast instead of switch"
jbhateja updated this revision to Diff 120877.Oct 30 2017, 1:09 PM
jbhateja edited edge metadata.
  • Review comments resolution.
sanjoy requested changes to this revision.Oct 30 2017, 2:18 PM
sanjoy added inline comments.
lib/Analysis/ScalarEvolution.cpp
4085

I'd emphasize that this replacement is valid only in some specific cases (the backedge increment of an add recurrence).

4089

This can be private. Please also make it explicit.

4095

I think you also need to check that the false edge actually leaves the loop. If both the edges out of the conditional branch branch to the header then this rewrite is not valid.

(Please also add a test case for the above situation ^).

4102

You can bail out early if BackedgeCond is nullptr.

4115

This comment needs to be addressed -- I don't think we should be creating SCEVUnknown unnecessarily as you're doing here.

4118

Use getTrueValue() and getFalseValue() instead of hard-coding the operand indices.

6506–6530

Wasn't fixed.

This revision now requires changes to proceed.Oct 30 2017, 2:18 PM
junryoungju added a comment.EditedOct 30 2017, 4:18 PM

:( that I commented didn't reviewed. this is why I wanted to make other reversion.

Are you saying that you had made the same comments as I did above? If so, that wasn't clear from what you wrote. You can help authors by:

  • Adding inline comments instead of a top level comment, knowing which part of the patch you're referring to helps comprehension
  • Being specific; instead of saying "this is very general" say "use cast instead of switch"

No, I wanted to say all that we are missing a very important point.

Okay, just we need to make sure we are evoluting conditional instructions or just checking that instructions are true or false for now.

first one.
If we are "actaully" evoluting a conditional instructions. better creating SCEVConditonal, checking that is true or false when is computing backedge taken count on each AddRec step.
I think this is a correct way for handling conditional instructions.
but, this will cause SCEV jobs MUUUUCHHH SLOWER.

second one.
If we are just checking that instructions are true or false. we do not need to rewrite it, rewriting value means that we handle that value as that "actual" SCEV. (register SCEV on SCEVCallbackVH)
this mean, this is same to write this chain on to createSCEV that we did at first.
so we have to handle it as a "except" of SCEV chain. better inlining code into createAddRecFromPHI.

This is the actual point. not only fixing a ICmp, this will not fix a "point" that bug reported.
and this will cause same bug, but from littlely different code.
It just fixing only that "specific" IR assembles in a very narrow range.

:( that I commented didn't reviewed. this is why I wanted to make other reversion.

Are you saying that you had made the same comments as I did above? If so, that wasn't clear from what you wrote. You can help authors by:

  • Adding inline comments instead of a top level comment, knowing which part of the patch you're referring to helps comprehension
  • Being specific; instead of saying "this is very general" say "use cast instead of switch"

No, I wanted to say all that we are missing a very important point.

Okay, just we need to make sure we are evoluting conditional instructions or just checking that instructions are true or false for now.

first one.
If we are "actaully" evoluting a conditional instructions. better creating SCEVConditonal, checking that is true or false when is computing backedge taken count on each AddRec step.
I think this is a correct way for handling conditional instructions.
but, this will cause SCEV jobs MUUUUCHHH SLOWER.

second one.
If we are just checking that instructions are true or false. we do not need to rewrite it, rewriting value means that we handle that value as that "actual" SCEV. (register SCEV on SCEVCallbackVH)
this mean, this is same to write this chain on to createSCEV that we did at first.
so we have to handle it as a "except" of SCEV chain. better inlining code into createAddRecFromPHI.

This is the actual point. not only fixing a ICmp, this will not fix a "point" that bug reported.
and this will cause same bug, but from littlely different code.
It just fixing only that "specific" IR assembles in a very narrow range.

@junryoungju, it will be good if you append to the bug report with other Patterns, I had made changes in my last revision to cover other case[s]too (I guess you added one another pattern in the mirror revision which you created from this patch) , we can generalise this or incremental addition can also be made.

The problem is, if under ICmp's operand node has a ICmp can evolutable? (or any other conditional expressions).
This only can be solved by registering this chain into getSCEV.

; RUN: opt -analyze -scalar-evolution < %s | FileCheck %s --check-prefix=CHECK-ANALYSIS

define i32 @foo() {
  br label %do_start

do_start:
  %inc = phi i32 [ 0, %0 ], [ %add, %do_start ]
  %cmp = icmp slt i32 %inc, 10000
  %add_cond = add nsw i32 %inc, 2
  %sel = select i1 %cmp, i32 %add_cond, i32 %inc
  %add = add nsw i32 %sel, 1
  br i1 %cmp, label %do_start, label %do_end

; CHECK-ANALYSIS: Loop %do_start: backedge-taken count is 3334
; CHECK-ANALYSIS: Loop %do_start: max backedge-taken count is 3334
; CHECK-ANALYSIS: Loop %do_start: Predicated backedge-taken count is 3334

do_end:
  ret i32 0
}

This case is "actaully" generated from Clang executable using -O3 -S -emit-llvm option.
that mean this case can be "always" appear.

To fix this case, we need to create SCEVConditional. that I commented here.

Okay, just we need to make sure we are evoluting conditional instructions or just checking that instructions are true or false for now.

first one.
If we are "actaully" evoluting a conditional instructions. better creating SCEVConditonal, checking that is true or false when is computing backedge taken count on each AddRec step.
I think this is a correct way for handling conditional instructions.
but, this will cause SCEV jobs MUUUUCHHH SLOWER.

second one.
If we are just checking that instructions are true or false. we do not need to rewrite it, rewriting value means that we handle that value as that "actual" SCEV. (register SCEV on SCEVCallbackVH)
this mean, this is same to write this chain on to createSCEV that we did at first.
so we have to handle it as a "except" of SCEV chain. better inlining code into createAddRecFromPHI.

and just note this issue CANNOT be solved just by checking ICmp has conditional instruction.

jbhateja updated this revision to Diff 120936.Oct 30 2017, 10:32 PM
jbhateja edited edge metadata.
  • Review comments resolution.
lib/Analysis/ScalarEvolution.cpp
4085

Returning a SCEV for a true or false value by checking backedge condition of the loop latch is generic theme, which is what comment states.

4089

Yes, infact other visitor SCEVShiftRewriter is having same problem. Will be fixed as NFCI.

4095

Can you give a scenario where this can happen ? A latch where both the branches have same desitination header ?

4102

Done

4118

Done.

junryoungju added inline comments.Oct 30 2017, 10:37 PM
lib/Analysis/ScalarEvolution.cpp
4788

This still didn't fixed.
You should try clang output to this patch emits correct optimized assemblies that commented on original bug report.

The problem is, if under ICmp's operand node has a ICmp can evolutable? (or any other conditional expressions).
This only can be solved by registering this chain into getSCEV.

; RUN: opt -analyze -scalar-evolution < %s | FileCheck %s --check-prefix=CHECK-ANALYSIS

define i32 @foo() {
  br label %do_start

do_start:
  %inc = phi i32 [ 0, %0 ], [ %add, %do_start ]
  %cmp = icmp slt i32 %inc, 10000
  %add_cond = add nsw i32 %inc, 2
  %sel = select i1 %cmp, i32 %add_cond, i32 %inc
  %add = add nsw i32 %sel, 1
  br i1 %cmp, label %do_start, label %do_end

; CHECK-ANALYSIS: Loop %do_start: backedge-taken count is 3334
; CHECK-ANALYSIS: Loop %do_start: max backedge-taken count is 3334
; CHECK-ANALYSIS: Loop %do_start: Predicated backedge-taken count is 3334

do_end:
  ret i32 0
}

This case is "actaully" generated from Clang executable using -O3 -S -emit-llvm option.
that mean this case can be "always" appear.

To fix this case, we need to create SCEVConditional. that I commented here.

Okay, just we need to make sure we are evoluting conditional instructions or just checking that instructions are true or false for now.

first one.
If we are "actaully" evoluting a conditional instructions. better creating SCEVConditonal, checking that is true or false when is computing backedge taken count on each AddRec step.
I think this is a correct way for handling conditional instructions.
but, this will cause SCEV jobs MUUUUCHHH SLOWER.

second one.
If we are just checking that instructions are true or false. we do not need to rewrite it, rewriting value means that we handle that value as that "actual" SCEV. (register SCEV on SCEVCallbackVH)
this mean, this is same to write this chain on to createSCEV that we did at first.
so we have to handle it as a "except" of SCEV chain. better inlining code into createAddRecFromPHI.

and just note this issue CANNOT be solved just by checking ICmp has conditional instruction.

Just try pulling out earlier diff : https://reviews.llvm.org/D38494?id=120193 , this was fixing your new case.
You shuld attempt an incremental fix once this patch goes through.

junryoungju added a comment.EditedOct 31 2017, 1:43 AM

The problem is, if under ICmp's operand node has a ICmp can evolutable? (or any other conditional expressions).
This only can be solved by registering this chain into getSCEV.

; RUN: opt -analyze -scalar-evolution < %s | FileCheck %s --check-prefix=CHECK-ANALYSIS

define i32 @foo() {
  br label %do_start

do_start:
  %inc = phi i32 [ 0, %0 ], [ %add, %do_start ]
  %cmp = icmp slt i32 %inc, 10000
  %add_cond = add nsw i32 %inc, 2
  %sel = select i1 %cmp, i32 %add_cond, i32 %inc
  %add = add nsw i32 %sel, 1
  br i1 %cmp, label %do_start, label %do_end

; CHECK-ANALYSIS: Loop %do_start: backedge-taken count is 3334
; CHECK-ANALYSIS: Loop %do_start: max backedge-taken count is 3334
; CHECK-ANALYSIS: Loop %do_start: Predicated backedge-taken count is 3334

do_end:
  ret i32 0
}

This case is "actaully" generated from Clang executable using -O3 -S -emit-llvm option.
that mean this case can be "always" appear.

To fix this case, we need to create SCEVConditional. that I commented here.

Okay, just we need to make sure we are evoluting conditional instructions or just checking that instructions are true or false for now.

first one.
If we are "actaully" evoluting a conditional instructions. better creating SCEVConditonal, checking that is true or false when is computing backedge taken count on each AddRec step.
I think this is a correct way for handling conditional instructions.
but, this will cause SCEV jobs MUUUUCHHH SLOWER.

second one.
If we are just checking that instructions are true or false. we do not need to rewrite it, rewriting value means that we handle that value as that "actual" SCEV. (register SCEV on SCEVCallbackVH)
this mean, this is same to write this chain on to createSCEV that we did at first.
so we have to handle it as a "except" of SCEV chain. better inlining code into createAddRecFromPHI.

and just note this issue CANNOT be solved just by checking ICmp has conditional instruction.

Just try pulling out earlier diff : https://reviews.llvm.org/D38494?id=120193 , this was fixing your new case.
You shuld attempt an incremental fix once this patch goes through.

That isn't a POINT, Please read the point that I commented.
Only that handling each test case dosn't means fixing a "point" of problem.

Is the point of this problem is handling the problem just by CHECKING that ICmp is true, or false?
OR are we REALLY wants to handle condtional instructions.
The point of problem is, current SCEV chain cannot handle conditonal expressions.
NOT only a clang, clang emits PHI node when its conditional, LLVM is a toolchain that we can create a compiler.

so I wanted to listen the opinion that "how about handling condtional variables by just creating SCEVCondtional, and comparing at computing backedge-count by visiting each step."

The problem is, if under ICmp's operand node has a ICmp can evolutable? (or any other conditional expressions).
This only can be solved by registering this chain into getSCEV.

; RUN: opt -analyze -scalar-evolution < %s | FileCheck %s --check-prefix=CHECK-ANALYSIS

define i32 @foo() {
  br label %do_start

do_start:
  %inc = phi i32 [ 0, %0 ], [ %add, %do_start ]
  %cmp = icmp slt i32 %inc, 10000
  %add_cond = add nsw i32 %inc, 2
  %sel = select i1 %cmp, i32 %add_cond, i32 %inc
  %add = add nsw i32 %sel, 1
  br i1 %cmp, label %do_start, label %do_end

; CHECK-ANALYSIS: Loop %do_start: backedge-taken count is 3334
; CHECK-ANALYSIS: Loop %do_start: max backedge-taken count is 3334
; CHECK-ANALYSIS: Loop %do_start: Predicated backedge-taken count is 3334

do_end:
  ret i32 0
}

This case is "actaully" generated from Clang executable using -O3 -S -emit-llvm option.
that mean this case can be "always" appear.

To fix this case, we need to create SCEVConditional. that I commented here.

Okay, just we need to make sure we are evoluting conditional instructions or just checking that instructions are true or false for now.

first one.
If we are "actaully" evoluting a conditional instructions. better creating SCEVConditonal, checking that is true or false when is computing backedge taken count on each AddRec step.
I think this is a correct way for handling conditional instructions.
but, this will cause SCEV jobs MUUUUCHHH SLOWER.

second one.
If we are just checking that instructions are true or false. we do not need to rewrite it, rewriting value means that we handle that value as that "actual" SCEV. (register SCEV on SCEVCallbackVH)
this mean, this is same to write this chain on to createSCEV that we did at first.
so we have to handle it as a "except" of SCEV chain. better inlining code into createAddRecFromPHI.

and just note this issue CANNOT be solved just by checking ICmp has conditional instruction.

Just try pulling out earlier diff : https://reviews.llvm.org/D38494?id=120193 , this was fixing your new case.
You shuld attempt an incremental fix once this patch goes through.

That isn't a POINT, Please read the point that I commented.
Only that handling each test case dosn't means fixing a "point" of problem.

Is the point of this problem is handling the problem just by CHECKING that ICmp is true, or false?
OR are we REALLY wants to handle condtional instructions.
The point of problem is, current SCEV chain cannot handle conditonal expressions.
NOT only a clang, clang emits PHI node when its conditional, LLVM is a toolchain that we can create a compiler.

so I wanted to listen the opinion that "how about handling condtional variables by just creating SCEVCondtional, and comparing at computing backedge-count by visiting each step."

@junryoungju, I would suggest we can do this discussion over llvm-dev mailing list. This patch is not claiming to fix all the patterns and we can incrementally add over it.

@sanjoy, all your comments have been resolved.

sanjoy requested changes to this revision.Nov 5 2017, 1:23 PM

Mostly minor stuff remains + the one correctness issue with a conditional latch branching to the header in both the true and false cases.

lib/Analysis/ScalarEvolution.cpp
4095

Yes

4115

The cast isa seems redundant here -- can't you return a value of type SCEVConstant (that may or may not be null)?

Though I'd still prefer Optional<bool> since that's more specific -- reading SCEVConstant you can't immediately tell that CondSE is either 1 or 0; but with Optional<bool> that fact will be obvious from the type system.

4124

The ICmp prefix to ICmpSE is misleading, since the condition does not need to be an icmp.

This revision now requires changes to proceed.Nov 5 2017, 1:23 PM
jbhateja added inline comments.Nov 5 2017, 8:28 PM
lib/Analysis/ScalarEvolution.cpp
4095

Yes ? @sanjoy, Can you provide a scenario/test in HLL where such situation is possible.

sanjoy added inline comments.Nov 5 2017, 8:57 PM
lib/Analysis/ScalarEvolution.cpp
4095

I answered "yes" to your second question -- since that's precisely the situation I'm talking about:

define void @foo(i1 %c) {
entry:
  br label %loop

loop:
  br i1 %c, label %loop, label %loop
}
jbhateja added inline comments.Nov 8 2017, 10:53 AM
lib/Analysis/ScalarEvolution.cpp
4095

Well, what I was checking was how can such an IR be generated ? Are we making any such check for both outgoing branches from a latch any where else in the code, because conditional branch instruction should become an unconditional branch in this scenario.

Shall revise this patch with your other comments, do add any thing else to save iteration ;-)

sanjoy added inline comments.Nov 8 2017, 11:08 AM
lib/Analysis/ScalarEvolution.cpp
4095

instruction should become an unconditional branch in this scenario.

Correctness of transformations cannot rely on a specific optimization having happened -- you're right that in most cases the trivial conditional branch will be folded to an unconditional one, but we can't miscompile code if that optimization didn't happen for some reason or the other.

jbhateja updated this revision to Diff 122314.Nov 9 2017, 12:56 PM
jbhateja edited edge metadata.

ping @reviewers

sanjoy accepted this revision.Nov 12 2017, 12:46 PM

Mostly minor stuff; please check in directly after addressing these.

lib/Analysis/ScalarEvolution.cpp
4099

It is usually customary to to put the else block in braces if the if is in braces.

4108

No need to change it in this patch, but this constraint isn't necessary, is it?

4149

I think it is better to return Optional<bool> here, and instead call getOne and getZero in the default: case in the switch on I->getOpcode() which is the only place that needs it. It will also make the case Instruction::Select: code a bit simpler.

test/Analysis/ScalarEvolution/pr34538.ll
33

Please also add a test case where both the latch branches branch to the loop header.

This revision is now accepted and ready to land.Nov 12 2017, 12:46 PM
jbhateja added inline comments.Nov 13 2017, 8:13 AM
lib/Analysis/ScalarEvolution.cpp
4099

Actually I purpusfully wrote it this way based on comments received on other patches reviewed. Shall change here following the file convention.

4108

Not sure, why this constraint not necssary, why do we want to cross loop boundary to explore evolution expression. If Expression is loop invariant either its a constant or its def lies outside the loop.

test/Analysis/ScalarEvolution/pr34538.ll
33

This will break the latch detection at header as getLoopLatch() looks at all the incoming branches and if sees more than one incoming branch from a block within loop then it returns null. Though two disjoint natural-loops can have same headers and two loop latches are possible. Adding a test will be futile here.

jbhateja updated this revision to Diff 122660.Nov 13 2017, 8:31 AM
  • Formatting change.
  • Rebasing for commit.
This revision was automatically updated to reflect the committed changes.
sanjoy added inline comments.Nov 13 2017, 9:30 AM
lib/Analysis/ScalarEvolution.cpp
4108

Yes, it does not help ver much if the increment amount is already a constant. But it can help e.g. change an addrec from {0,+,%arg} (%arg being a value whose def is outside the loop) to {0,+,1} which is useful.

4149

This wasn't addressed?

test/Analysis/ScalarEvolution/pr34538.ll
33

I see, that's a very good point. That means the BI->getSuccessor(0) != BI->getSuccessor(1) can be an assert instead?

jbhateja added inline comments.Nov 13 2017, 9:53 AM
lib/Analysis/ScalarEvolution.cpp
4149

My bad I missed it,
BTW I'm not clear how you want this and if current code is not clean.

test/Analysis/ScalarEvolution/pr34538.ll
33

Exaclty, Is post commit NFC for this and your proposed code ok here.

sanjoy added inline comments.Nov 23 2017, 12:32 PM
lib/Analysis/ScalarEvolution.cpp
4149

I was suggesting:

Optional<bool> compareWithBackedgeCondition(Value *IC) {
  return BackedgeCond == IC ? IsPositiveBECond : None;
}

and then putting the getZero() vs. getOne() in the default: case. In the Select case you would not have to call getZero() and getOne()

test/Analysis/ScalarEvolution/pr34538.ll
33

Yes, a post-commit NFC fixup is fine (feel free to push without review).