• Updating comment

Ping reviewers, can put this under Size oriented optimization.

• [X86] Limiting optimization to i32 and i64 types

• [X86] Review comments resolution for patch D49966
• Patch rebase.

• [X86] Review comments incorporation for patch D49966

• [X86] Review comment resolutions for patch D49966

• [X86] Correcting a comment in patch D49966

• [X86] Review comments incorporation for patch D49966

• Register name case changes due to rebase.

• Rebasing to resolve incorrect overrideing of register names in kill statements.

• Reivew comment resolution.
• Rebasing patch.

Few more minor changes , mostly NFCs.

• Formatting change.
• Rebasing for commit.

ping @reviewers

• Merge branch 'master' of https://github.com/llvm-mirror/llvm
• Review commentes resolution.

@RKSimon, @lsaba , @jmolly , all your comments have been addressed. Kindly verify so that I can land this into trunk.

• Adding a test for signext of function arguments.

1/ Making the factorization alog iterative. This was earlier commited with

Diff : https://reviews.llvm.org/D35014?id=116144
but some how got removed in successive commits.

2/ Rebasing again. All comments are resolved.

ConstantExpr are not handled by FastISel.

In D38494#911550, @junryoungju wrote:

In D38494#911512, @jbhateja wrote:

In D38494#911501, @junryoungju wrote:

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.

In D38494#908808, @junryoungju wrote:

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."

In D38494#911501, @junryoungju wrote:

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.

In D38494#908808, @junryoungju wrote:

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.

• Review comments resolution.

In D38494#911259, @junryoungju wrote:

In D38494#910903, @sanjoy wrote:

In D38494#910421, @junryoungju wrote:

:( 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.

In D38494#908808, @junryoungju wrote:

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.

@RKSimon, requested revision changes have been made as per your comments. Can you please validate.

• Review comments resolution.

• Rebasing
• Review comments resolution.

• Review comment resolutions.

• Review comments resolutions.

In D38494#904754, @junryoungju wrote:

In D38494#903575, @jbhateja wrote:

@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.

Few general concerns.

1/  Always submit patch with few test cases (valid for any patch).
2/  Patch https://reviews.llvm.org/D38494 is taking care of this problem. I don't see what is your point in duplicating the efforts.

You are on the review list also.

• Adding a visitor to generalize ICmp evalauation while computing SCEV for PHIs.
• Merge branch 'master' of https://github.com/llvm-mirror/llvm

[llvm] r316129 - Revert "[ScalarEvolution] Handling for ICmp occuring in the evolution chain."

Patch has been regressed through chrome test sweet.
No issues reported. Thanks to Hans Wennborg (hans@chromium.org) for validating it.

In D37660#900408, @junryoungju wrote:

@jbhateja

If a compare instruction is same or inverse of the compare in the
branch of the loop latch, then return a constant evolution node.
Currently scope of evaluation is limited to SCEV computation for
PHI nodes.

Formatting changes.
Test case extension from .txt to .ll

In D38494#899577, @junryoungju wrote:

Go to diff history, and download diff. and re upload it.

Removing unrelated changes uploaded by mistake in previous diff.

In D38494#899561, @junryoungju wrote:

I don't understand why is there are CG commits here....

• Updating for a review comment.

Hi Jun Ryoung Ju,

In D38494#888590, @sanjoy wrote:

With this IR:

define void @f() {
entry:
  br label %loop

loop:
  %iv = phi i32 [ 0, %entry ], [ %iv.inc, %loop ]
  %iv.inc = add i32 %iv, 1
  %cmp = icmp ne i32 %iv.inc, 10
  %cmp.zext = zext i1 %cmp to i32
  br i1 %cmp, label %loop, label %leave

leave:
  ret void
}

and opt -analyze -scalar-evolution , on master:

Printing analysis 'Scalar Evolution Analysis' for function 'f':
Classifying expressions for: @f
  %iv = phi i32 [ 0, %entry ], [ %iv.inc, %loop ]
  -->  {0,+,1}<%loop> U: [0,10) S: [0,10)               Exits: 9                LoopDispositions: { %loop: Computable }
  %iv.inc = add i32 %iv, 1
  -->  {1,+,1}<%loop> U: [1,11) S: [1,11)               Exits: 10               LoopDispositions: { %loop: Computable }
  %cmp.zext = zext i1 %cmp to i32
  -->  (zext i1 %cmp to i32) U: [0,2) S: [0,2)          Exits: 0                LoopDispositions: { %loop: Variant }
Determining loop execution counts for: @f
Loop %loop: backedge-taken count is 9
Loop %loop: max backedge-taken count is 9
Loop %loop: Predicated backedge-taken count is 9
 Predicates:

Loop %loop: Trip multiple is 10

and with your patch:

Printing analysis 'Scalar Evolution Analysis' for function 'f':
Classifying expressions for: @f
  %iv = phi i32 [ 0, %entry ], [ %iv.inc, %loop ]
  -->  {0,+,1}<%loop> U: [0,10) S: [0,10)               Exits: 9                LoopDispositions: { %loop: Computable }
  %iv.inc = add i32 %iv, 1
  -->  {1,+,1}<%loop> U: [1,11) S: [1,11)               Exits: 10               LoopDispositions: { %loop: Computable }
  %cmp.zext = zext i1 %cmp to i32
  -->  1 U: [1,2) S: [1,2)              Exits: 1                LoopDispositions: { %loop: Invariant }
Determining loop execution counts for: @f
Loop %loop: backedge-taken count is 9
Loop %loop: max backedge-taken count is 9
Loop %loop: Predicated backedge-taken count is 9
 Predicates:

Loop %loop: Trip multiple is 10

Note that the SCEV for %cmp.zext is different. I'm not sure how you got a
different answer on your end, since this should basically be the same as the IR
from Hal's example. Perhaps in the example you tried the icmp feeding in to the
latch was a different llvm::Instruction than the icmp feeding into the zext? If
so, that's a missing-CSE bug.

• Limiting the evaluation of ICmp to computation of SCEV of PHI nodes.

• Operands of LEA must be of same register class, this constraint is as per Intel's architecture manual.
• Remove map entry from LEAs map if value list becomes empty.
• Rebase.

• D35014 : Review comments resolution
• Removing 2 tests, pulled their latest renamed versions from trunk.
• [X86] : Factorize LEA, handling for patterns involing SUBREG_TO_REG as LEA operands.
• Few more changes for LEA factorization.
• Updating test lea-opt-cse3.ll
• Formatting changes.
• Formatting changes
• Changes to avoid creating costly LEAs in loops, strength reduction for simple LEAs with unit scale
• Updating test.
• [X86] Limiting the scope of DAG operands folding while AM based instruction selection to LEAs.
• Merge from trunk.
• Extending aggressive AM based folding for LEAs to cover more cases.
• Updating test post rebase.
• Formatting changes + fine tuning pattern matching condition.
• Adding a check for subtarget feature Slow3OpLEA in pattern matching.
• Few synthetic changes.
• Undefining result operand of factored statement to preserve SSA nature of Machine IR.
• Merge branch 'master' of https://github.com/llvm-mirror/llvm
• Merge branch 'master' of https://github.com/llvm-mirror/llvm
• Updating tests for reported PRs for initial patch.
• Merge branch 'master' of https://github.com/llvm-mirror/llvm
• Pull from trunk.
• Operands of LEAs must be of same register class.
• Revert "Operands of LEAs must be of same register class."