[X86] Improvement in CodeGen instruction selection for LEAs.

[jbhateja]

Summary

1/ Operand folding during complex pattern matching for LEAs has been extended, such that it promotes Scale to

 accommodate similar operand appearing in the DAG  e.g.
             T1 = A + B
             T2 = T1 + 10
             T3 = T2 + A
For above DAG rooted at T3, X86AddressMode will now look like
            Base = B , Index = A , Scale = 2 , Disp = 10

2/ During OptimizeLEAPass down the pipeline factorization is now performed over LEAs so that if there is an opportunity

then complex LEAs (having 3 operands) could be factored out  e.g.
            leal 1(%rax,%rcx,1), %rdx
            leal 1(%rax,%rcx,2), %rcx
will be factored as following
            leal 1(%rax,%rcx,1), %rdx
            leal (%rdx,%rcx)   , %edx

3/ Aggressive operand folding for AM based selection for LEAs is sensitive to loops, thus avoiding creation of any complex LEAs within a loop.

4/ Simplify LEA converts (lea (BASE,1,INDEX,0) --> add (BASE, INDEX) which offers better through put.

PR32755 will be taken care of by this pathc.

Previous patch revisions : r313343 , r314886

[lsaba]

Please add test cases for the optimization added in OptimizeLEAPass

[lsaba]

lib/Target/X86/X86OptimizeLEAs.cpp

85–86

This comment is only valid for the else statement, please change it to explain the different cases between Identical and Similar Disp

291

Please add a comment explaining what this function does

[jbhateja]

Changes for review comments for patch.

[jbhateja]

Reviewers,

Have posted an RFC for wider fix at following link

Kindly review the same and add your comments

https://groups.google.com/forum/#!topic/llvm-dev/x2LDXpON500

Thanks.

[jbhateja]

Missed one change to be submitted, build is running will upload the change post lit. Thanks

[jbhateja]

Review comments changes cont..

[lsaba]

lib/Target/X86/X86OptimizeLEAs.cpp

737

should it also be erased from the LEAs list?

[jbhateja]

lib/Target/X86/X86OptimizeLEAs.cpp

737

Why do you think so ?

LEAs is a Map where

Key = F ( BASE , INDEX , DISP , SEGMENT)
Value = Vector of MI (LEA Instr).
This MAP is populated per BasicBlock basis.

Outer Loop traverse over Map entries

Sort Vector in decresing order of Scale.
Inner Loop traverses over Sorted vector of LEA for a given Key
LI1 insturction will be traversed only once.

Map will be delted once we leave this function.

Machine CSE which is value number based is already run before this pass so if there are multiple identical LEAs (i.e same BASE/INDEX/SCALE/DISP/SEGMENT) in a BasicBlock they will be factored out before we land up here..

[lsaba]

lib/Target/X86/X86OptimizeLEAs.cpp

737

just making sure:)
by the way, can't this algorithm work cross a function's basic blocks?

[jbhateja]

Performing LEA factorization/CSE across bacis blocks.

[jbhateja]

ping @reviewers

[lsaba]

lib/Target/X86/X86OptimizeLEAs.cpp

340

it is unclear what this function does, can you explain?

[jbhateja]

lib/Target/X86/X86OptimizeLEAs.cpp

340

In a nutshell we are implementing a scoped hash map. Which is LEAs.
Every time we enter a new scope and encounter an LEA we first record the length of list of MIs corresponding to MemOpKey of new LEA. After that we insert the new LEA in the beginning of the list which is a value field of the hash map.

When we leave a scope we remove the LEA instructions from the LEAs hash map. Since we recorded the original length of list of MIs when we entered the scope at exit we keep on removing elements from the beginning of list till the size becomes same as what was recorded at the entry.

[lsaba]

lib/Target/X86/X86OptimizeLEAs.cpp

341

already initialized at the beginning of the function

test/CodeGen/X86/lea-opt-csebb.ll

1 ↗

(On Diff #106796)

can you please add a test case that covers scale >1 cases

test/CodeGen/X86/umul-with-overflow.ll

6

why did this test change?

[jbhateja]

test/CodeGen/X86/lea-opt-csebb.ll

1 ↗

(On Diff #106796)

This commit if you see has two parts
1/ pattern matching based on addressing mode (which is limited currently).
2/ factoring of LEAs which is generic.

Checking in incremental changes should be fine I guess.

Generic pattern will need to be brought out of addessing mode based selection as I described in following link
https://groups.google.com/forum/#!topic/llvm-dev/x2LDXpON500

Please comment in the thread.

test/CodeGen/X86/umul-with-overflow.ll

6

Beecause I generated its output with script utils/update_llc_test_checks.py which adds
an assertion for each instruction. I think it sould be fine.

[jbhateja]

lib/Target/X86/X86OptimizeLEAs.cpp

341

Yes.

[jbhateja]

ping @ reviewers. can we do an incremental checkin for this.

Thanks

[lsaba]

test/CodeGen/X86/lea-opt-csebb.ll

1 ↗

(On Diff #106796)

I am not sure i understand what you mean by "Generic pattern will need to be brought out of addessing mode" , as far as i understand, for the following C code:

int foo(int a, int b) {

int x = a + 2*b + 4; 
int y = a + 4*b + 4; 
int c = x*y ;
return c;

}

the currently generated IR:
define i32 @foo(i32 %a, i32 %b) local_unnamed_addr #0 {
entry:

%mul = shl i32 %b, 1
%add = add i32 %a, 4
%add1 = add i32 %add, %mul
%mul2 = shl i32 %b, 2
%add4 = add i32 %add, %mul2
%mul5 = mul nsw i32 %add1, %add4
ret i32 %mul5

}

the currently generated asm:

leal 4(%rdi,%rsi,2), %ecx
leal 4(%rdi,%rsi,4), %eax
imull %ecx, %eax
retq

this will be refactored by this optimization in this current commit (not a future commit) to:
leal 4(%rdi,%rsi,2), %ecx
leal (%ecx,%rsi,2), %eax
imull %ecx, %eax
retq

please correct me if im wrong

test/CodeGen/X86/lea-opt-cst.ll

4

please generate the test with the original checks before your changes and commit it first in a separate commit

test/CodeGen/X86/umul-with-overflow.ll

6

This needs to be in a separate pre commit. please commit and rebase

[RKSimon]

lib/Target/X86/X86OptimizeLEAs.cpp

188

Can we avoid the static?

239

Comment describing the purpose of the class

262

(style) cleanup the positions of the * - check what clang-format does

262

comment

277

comment

297

(style) remove braces

test/CodeGen/X86/lea-opt-csebb.ll

1 ↗

(On Diff #106796)

Please can you commit this test file to trunk with current codegen and update the patch to show the diff

test/CodeGen/X86/lea-opt-cst.ll

4

Please can you commit this test file to trunk with current codegen and update the patch to show the diff

test/CodeGen/X86/umul-with-overflow.ll

6

I regenerated this recently - please rebase

utils/TableGen/DAGISelMatcherGen.cpp

308

This is still here

[jbhateja]

test/CodeGen/X86/lea-opt-csebb.ll

1 ↗

(On Diff #106796)

Hi Lama,

By generic patten handling I meant LEA folding into complex LEAs which is currently restrictive.

Consider following case

%struct.SA = type { i32 , i32 , i32 , i32 , i32};

define void @foo(%struct.SA* nocapture %ctx, i32 %n) local_unnamed_addr #0 {
entry:

%h0 = getelementptr inbounds %struct.SA, %struct.SA* %ctx, i64 0, i32 0
%0 = load i32, i32* %h0, align 8
%h3 = getelementptr inbounds %struct.SA, %struct.SA* %ctx, i64 0, i32 3
%h4 = getelementptr inbounds %struct.SA, %struct.SA* %ctx, i64 0, i32 4
%1 = load i32, i32* %h4, align 8
%add = add i32 %0, 1
%add4 = add i32 %add, %1
%add5 = add i32 %add4, %1
store i32 %add5, i32* %h3, align 4
%add10 = add i32 %add5, %1
%add29 = add i32 %add10, %1
store i32 %add29, i32* %h4, align 8
ret void

}

ASM :

foo: # @foo
.cfi_startproc

BB#0: # %entry

movl (%rdi), %eax
movl 16(%rdi), %ecx
leal (%rax,%rcx,2), %edx
leal 1(%rax,%rcx,2), %eax
movl %eax, 12(%rdi)
leal 1(%rdx,%rcx,2), %eax
movl %eax, 16(%rdi)

It could be further optimized to following:

movl (%rdi), %eax
movl 16(%rdi), %ecx
leal 1(%rax,%rcx,2), %edx
movl %eax, 12(%rdi)
leal (%rdx,%rcx,2), %eax
movl %eax, 16(%rdi)

Folding is currently being done as a part of addressing mode matcher, I feel that efficient
folding can only be done as a separate MI pass, that is what I explained in the proposal (http://lists.llvm.org/pipermail/llvm-dev/2017-July/115182.html).

Thanks for your example I will add it to the test cases , it demonstrates generic ness of Factorization.

[lsaba]

test/CodeGen/X86/lea-opt-csebb.ll

1 ↗

(On Diff #106796)

Hi,

Thanks, I understand the need for a more generic pattern matching and I agree.
This is unrelated to my comment which refers solely to the Factorize LEA optimization which needs more testing, for example covering different Scale values (like the example i provided) and testing factorizing LEAs cross Basic Blocks.

[lsaba]

lib/Target/X86/X86OptimizeLEAs.cpp

724

This could end up in an assertion failure if LI1 is at the beginning of the BB, need to handle it separately, for example in this reproducer :

; ModuleID = 'bugpoint-reduced-simplified.bc'
source_filename = "bugpoint-output-2ef2e5d.bc"
target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
target triple = "x86_64-unknown-linux-gnu"

; Function Attrs: norecurse nounwind readnone uwtable
define i32 @foo(i32 %a, i32 %b, i32 %d, i32 %y, i32 %x) local_unnamed_addr #0 {
entry:

%mul1 = shl i32 %b, 1
%add2 = add i32 %a, 4
%add3 = add i32 %add2, %mul1
%mul4 = shl i32 %b, 2
%add6 = add i32 %add2, %mul4
br label %for.body

for.cond.cleanup: ; preds = %for.body

ret i32 %add

for.body: ; preds = %for.body, %entry

%x.addr.015 = phi i32 [ %x, %entry ], [ %add3, %for.body ]
%y.addr.014 = phi i32 [ %y, %entry ], [ %add6, %for.body ]
%mul = mul nsw i32 %x.addr.015, %y.addr.014
%add = add nsw i32 0, %mul
%exitcond = icmp eq i32 undef, %d
br i1 %exitcond, label %for.cond.cleanup, label %for.body, !llvm.loop !1

}

attributes #0 = { norecurse nounwind readnone uwtable "correctly-rounded-divide-sqrt-fp-math"="false" "disable-tail-calls"="false" "less-precise-fpmad"="false" "no-frame-pointer-elim"="false" "no-infs-fp- math"="false" "no-jump-tables"="false" "no-nans-fp-math"="false" "no-signed-zeros-fp-math"="false" "no-trapping-math"="false" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+fxsr,+ mmx,+sse,+sse2,+x87" "unsafe-fp-math"="false" "use-soft-float"="false" }

!llvm.ident = !{!0}

!0 = !{!"clang version 6.0.0 (cfe/trunk 309511)"}
!1 = distinct !{!1, !2}
!2 = !{!"llvm.loop.unroll.disable"}

[RKSimon]

lib/Target/X86/X86OptimizeLEAs.cpp

29

(style) Insert the include in alphabetical order (so before MachineFunctionPass.h)

[jbhateja]

1/ Changes to cover review comments.
2/ Handling for patterns involving SUBREG_TO_REG as LEA operands.
3/ Formatting changes.

[RKSimon]

lib/Target/X86/X86OptimizeLEAs.cpp

130

(style)

for (unsigned i = 1, e = MI->getNumOperands(); i <e ; i++)

215

(style)

for (unsigned i = 1, e = MI1->getNumOperands(); i < e; ++i)

test/CodeGen/X86/umul-with-overflow.ll

6

Still needs to be rebased - you've lost the x86_64 tests

[jbhateja]

• Merge branch 'master' of https://github.com/llvm-mirror/llvm
• Formatting changes

[jbhateja]

Pinging reviewers. Kindly pour your comments.
Thanks

[lsaba]

In D35014#831745, @jbhateja wrote:

Pinging reviewers. Kindly pour your comments.
Thanks

Please address my last comment (Line 920)

[jbhateja]

In D35014#833192, @lsaba wrote:

In D35014#831745, @jbhateja wrote:

Pinging reviewers. Kindly pour your comments.
Thanks

Please address my last comment (Line 920)

The test case you provided is giving correct results with currently checked in changes.

[lsaba]

lib/Target/X86/X86OptimizeLEAs.cpp

208

need to check MO2.isReg()

[jbhateja]

lib/Target/X86/X86OptimizeLEAs.cpp

208

Yes, I shall take care of this.

Kindly let me know if there are any other comments apart from this.

It shall save iterations.

[jbhateja]

@ reviewers , kindly let me know if there are any more comments apart from last comment from lsaba.
Thanks.

[lsaba]

In D35014#835240, @jbhateja wrote:

@ reviewers , kindly let me know if there are any more comments apart from last comment from lsaba.
Thanks.

Hi,
I ran the patch on several benchmarks to check performance, overall the changes look good, but there is a regression in one of the benchmarks (EEMBC/coremark-pro) caused by creating an undesired lea instruction instead of the previously created add instruction, I am working on creating a simple reproducer for the problem and would appreciate your patience.

Thanks

[lsaba]

In D35014#835498, @lsaba wrote:

In D35014#835240, @jbhateja wrote:

@ reviewers , kindly let me know if there are any more comments apart from last comment from lsaba.
Thanks.

Hi,
I ran the patch on several benchmarks to check performance, overall the changes look good, but there is a regression in one of the benchmarks (EEMBC/coremark-pro) caused by creating an undesired lea instruction instead of the previously created add instruction, I am working on creating a simple reproducer for the problem and would appreciate your patience.

Thanks

The change in X86DAGToDAGISel::matchAddressBase is good when it allows us to git rid of extra lea/add instructions, or replace slow lea with fast lea, but in some cases it only replaces an add instruction with a lea instruction and since the throughput of add instruction is higher, we would prefer to keep the add instruction, for example, for the following IR:

target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
target triple = "x86_64-unknown-linux-gnu"
; Function Attrs: norecurse nounwind uwtable
define void @foo() local_unnamed_addr #0 {
entry:
  br i1 undef, label %BB2, label %BB1
BB1:                                  ; preds = %entry
  %rem.us.1 = srem i32 undef, 65536
  br label %BB2
BB2:      ; preds = %BB1, %entry
  %s = phi i32 [ undef, %entry ], [ %rem.us.1, %BB1 ]
  %a = phi i32 [ 1, %entry ], [ 0, %BB1 ]
  %mul1 = mul nsw i32 %s, %a
  %rem1 = srem i32 %mul1, 65536
  %add1 = add nsw i32 %rem1, %a
  %conv1 = trunc i32 %add1 to i16
  store i16 %conv1, i16* undef, align 2, !tbaa !1
  %add2 = add i32 %add1, %a
  %0 = trunc i32 %add2 to i16
  %conv2 = and i16 %0, 255
  store i16 %conv2, i16* undef, align 2, !tbaa !1
  ret void
}
attributes #0 = { norecurse nounwind uwtable "correctly-rounded-divide-sqrt-fp-math"="false" "disable-tail-calls"="false" "less-precise-fpmad"="false" "no-frame-pointer-elim"="false" "no-infs-fp-math"="true" "no-jump-tables"="false" "no-nans-fp-math"="true" "no-signed-zeros-fp-
math"="true" "no-trapping-math"="true" "stack-protector-buffer-size"="8" "target-cpu"="core-avx2" "target-
features"="+aes,+avx,+avx2,+bmi,+bmi2,+cx16,+f16c,+fma,+fsgsbase,+fxsr,+lzcnt,+mmx,+movbe,+pclmul,+popcnt,+rdrnd,+sse,+sse2,+sse3,+sse4.1,+sse4.2,+ssse3,+x87,+xsave,+xsaveopt" "unsafe-fp-math"="true" "use-soft-float"="false" }
!llvm.ident = !{!0}
!0 = !{!"clang version 6.0.0 (cfe/trunk 310239)"}
!1 = !{!2, !2, i64 0}
!2 = !{!"short", !3, i64 0}
!3 = !{!"omnipotent char", !4, i64 0}
!4 = !{!"Simple C/C++ TBAA"}

the originally generated code was:

.LBB0_2:                                # %for.cond11.for.inc35_crit_edge.us.unr-lcssa
   movl	%eax, %ecx
   imull	%eax, %ecx
   movl	%ecx, %edx
   sarl	$31, %edx
   shrl	$16, %edx
   addl	%ecx, %edx
   andl	$-65536, %edx           # imm = 0xFFFF0000
   subl	%edx, %ecx
   addl	%eax, %ecx
   movw	%cx, (%rax)
   addl	%eax, %ecx
   movzbl	%cl, %eax
   movw	%ax, (%rax)
   retq

while the generated code now is

movl	%eax, %ecx
imull	%eax, %ecx
movl	%ecx, %edx
sarl	$31, %edx
shrl	$16, %edx
addl	%ecx, %edx
andl	$-65536, %edx           # imm = 0xFFFF0000
subl	%edx, %ecx
leal	(%rcx,%rax), %edx
movw	%dx, (%rax)
leal	(%rcx,%rax,2), %eax
movzbl	%al, %eax
movw	%ax, (%rax)
retq

Need to refine this optimization further to avoid such cases since the impact can be substantial if the code is in a hot loop for example

[qcolombet]

include/llvm/CodeGen/MachineInstr.h

1291 ↗

(On Diff #109147)

Genuine question.
MRI is usually accessibly via other more efficient means.
Do we really need to rely on this one?

[jbhateja]

• Changes to avoid creating costly complex LEAs having scale less than equal to 2 in loops.
• Strength reduction for simple LEAs with unit scale for better throughput.
• Pattern matching for DAG folding has been improved to make it generic.
• Incorporating other review comments.

[jbhateja]

include/llvm/CodeGen/MachineInstr.h

1291 ↗

(On Diff #109147)

It seems making it public will be useful as one can directly use the function which internally
calls getParent() twice to get to MachineFunction which contains Reg Info.

[jbhateja]

ping @ Reviewers, I guess I have addressed all comments.

[lsaba]

It seems like there are still correctness issues in the patch, I ran the llvm-test-suite and got a couple of runfails :
multisource_applications_alac_encode_alacconvert_encode
multisource_applications_jm_lencod_lencod

please debug those failures.

In general, please consider running execution tests on the patches to discover runtime failures.

[jbhateja]

• Limiting the scope of DAG operands folding while AM based instruction selection to LEAs.
• Formatting changes , rebase and lnt failure fix.

[jbhateja]

Ping @ reviewers. I think all the comments have been resolved.
Do let me know if any other comments.

[jbhateja]

• Extending aggressive AM based folding for LEAs to cover more cases.
• Merge branch 'master' of https://github.com/llvm-mirror/llvm

[jbhateja]

@lamas, @reviewers, comments have been taken care. Let me know if anything else.

[lsaba]

In D35014#859838, @jbhateja wrote:

@lamas, @reviewers, comments have been taken care. Let me know if anything else.

There are still functionality issues with the pass, please allow some time to create a reproducer

[lsaba]

In D35014#859838, @jbhateja wrote:

@lamas, @reviewers, comments have been taken care. Let me know if anything else.

The following ll code fails in CodeGen selection, please debug the issue:

target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
target triple = "x86_64-unknown-linux-gnu"
%struct.S1 = type { i32, i32 }
; Function Attrs: nounwind uwtable
define fastcc void @func(i32 %end) unnamed_addr #0 {
entry:
 br label %while.body
while.body:                                       ; preds = %if.end, %entry
 %a = phi i32 [ %end, %entry ], [ undef, %if.end ]
 br i1 undef, label %if.then, label %if.else
if.then:                                          ; preds = %while.body
 %dec = add nsw i32 %a, -1
 %idx1 = sext i32 %dec to i64
 %idx2 = getelementptr inbounds %struct.S1, %struct.S1* null, i64 %idx1
 %0 = bitcast %struct.S1* %idx2 to i64*
 store i64 0, i64* %0, align 4
 %1 = load [3 x float]*, [3 x float]** undef, align 8 
 %idx3 = getelementptr inbounds [3 x float], [3 x float]* %1, i64 %idx1, i64 0
 %2 = bitcast float* %idx3 to i32*
 %3 = load i32, i32* %2, align 4
 store i32 %3, i32* undef, align 4
 br label %if.end
if.else:                                          ; preds = %while.body
 br label %if.end
if.end:                                           ; preds = %if.else, %if.then
 br label %while.body
}
attributes #0 = { nounwind uwtable "target-cpu"="x86-64" "target-features"="+fxsr,+mmx,+sse,+sse2,+x87" }
!llvm.module.flags = !{!0}
!0 = !{i32 1, !"wchar_size", i32 4}

[RKSimon]

Some style comments, but @lsaba 's comments need to be dealt with first.

include/llvm/CodeGen/MachineInstr.h

1296 ↗

(On Diff #113356)

(style) newline before private

include/llvm/CodeGen/SelectionDAG.h

305 ↗

(On Diff #113356)

(style) newline before private

lib/Target/X86/X86ISelDAGToDAG.cpp

165

(style) newline

1115

clang-format? If so, commit it as an NFC change

1124

Two hard coded depths like this is weird - better to have a getMaxOperandFoldingDepth() helper?

lib/Target/X86/X86OptimizeLEAs.cpp

173

NFC change - just commit it if you want, but don't pollute a patch with it

316

NFC change

357

clang-format? If so, commit it as an NFC change

650

clang-format? If so, commit it as an NFC change

764

(style) Remove braces

[jbhateja]

• Fine tuning pattern matching condition.
• Formatting changes.

[lsaba]

3-Ops LEA are costly starting target SandyBridge , is there a limitation in the code for the targets this transformation works on? If not I think there should be.
you can check the Slow3OpsLEA feature for the full list of targets.

[jbhateja]

In D35014#861853, @lsaba wrote:

3-Ops LEA are costly starting target SandyBridge , is there a limitation in the code for the targets this transformation works on? If not I think there should be.
you can check the Slow3OpsLEA feature for the full list of targets.

Yes, this check could be added in pattern matching where i'm avoiding creation of complex LEA with scale less than equal to 2.

Please let me know if anything else you see to save iteration.
Thanks

[jbhateja]

• Rebasing again.
• Adding a check for subtarget feature Slow3OpLEA in pattern matching.

[jbhateja]

ping @ reviewers.

[jbhateja]

@lsaba, @reviewers , waiting for your LGTM or any remaining comments on this.
Thanks

[jbhateja]

• Few synthetic changes.

[RKSimon]

Reverted in rL313376 due to PR34629 and PR34634

[RKSimon]

PR34629 and PR34634 need to be addressed

[jbhateja]

• Undefining result operand of factored statement to preserve SSA nature of Machine IR.
• This fixes reperted PR 34634 and PR 34629 and build-bot failures reported.

[jbhateja]

@RKSimon, @Reviewers, revision was in accepted state earlier and fix to counter reported issues post commit to trunk has been fixed. Please do let me know if another acceptance is needed to land this again.

[jbhateja]

• Updating tests for reported PRs for initial patch.

[jmolloy]

lib/Target/X86/X86OptimizeLEAs.cpp

823

This can cause recursion deep enough to cause stack overflows. Please could you refactor this to not use direct recursion? The domtree may be hundreds of nodes deep in degenerate cases.

[jbhateja]

• Merge branch 'master' of https://github.com/llvm-mirror/llvm
• Making Factorization algorithm iterative.

[jbhateja]

@reviewers, required revision change are through, let me know if this can land back.

[jbhateja]

@jmolloy , @RKSimon , this patch has been reviewd and due to regression was opened again for review, required changes have
been made, can this land now in trunk if there are no more observations from any reviewers.

Thanks

[jbhateja]

@reviewers, if no more comment I shall be landing this into trunk since required revision changes post acceptance are through.

[jbhateja]

• Operands of factored LEA must belong to same register class as per Intel's Architecture Manual.
• Some code reorganization + rebase.

[jbhateja]

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

[jbhateja]

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

[jbhateja]

Patch has been regressed through chrome test sweet.
No issues reported. Thanks to Hans Wennborg ([e-mail]) for validating it.

[RKSimon]

lib/Target/X86/X86ISelDAGToDAG.cpp

100

bool isLegalScale() const {

187

Is a default argument for a setter a good idea? Especially one that is the inverse of what the setter says it is.

1124

My comment still stands - try to avoid hard coded values embedded in the source - add a getMaxOperandFoldingDepth() helper.

1422

These AM.Scale increments are scary - better to set it with AM.Scale = 2?

lib/Target/X86/X86OptimizeLEAs.cpp

29

Include ordering still broken

237

Do you mean:

bool isInstrErased = !(Opr.isReg() && Opr.getParent()->getParent());

724

Has @lsaba test been added to the patch? I couldn't see it.

770

Really don't like this - write a helper instead like you did in X86ISelDAGToDAG.cpp

auto IsLegalScale = [](int S) {
  return S == 1 || S == 2 || S == 4 || S == 8;
};

776

return Arg1->getOperand(2).getImm() >= Arg2->getOperand(2).getImm();

831

DL is only used here - just use LI1.getDebugLoc() directly?

test/CodeGen/X86/lea-opt-cse2.ll

3 ↗

(On Diff #119011)

Why have you changed these tests?

test/CodeGen/X86/lea-opt-cse4.ll

3 ↗

(On Diff #119011)

Why have you changed these tests?

[jbhateja]

lib/Target/X86/X86ISelDAGToDAG.cpp

100

Fixed.

187

Fixed. We do not need a default argument here, both the calls to this routines is passing an explicit argument.

1124

Helper added.

1422

Increments are triggered only in aggressive folding mode and can fold upto 8 operands (which is a max legal scale). This was intentionally done, initial change was only working for AM.scale = 2 and was very restrictive. Aggressive operand folding is done only for LEAs currently and is enabled instantiating and RAII object of X86AggressiveOperandFolding class.

lib/Target/X86/X86OptimizeLEAs.cpp

237

fixed.

724

We have a similare test case for loop lea-opt-cse2.ll. We are not doing any factorization inside loops, only simplifyLEA can kick in.

724

We have a test case for loops lea-opt-cse2.ll, so not added this.
We are not doing any factorization inside loops, only simplifyLEA can kick in.

770

Fixed

776

Fixed

test/CodeGen/X86/lea-opt-cse4.ll

3 ↗

(On Diff #119011)

FixupLEAPass down the pipeline transforms some complex LEA ptterns to simple with add. Optimization, with changes in the patch we will have following

leal 1(%rax,%rcx,4), %eax

which after FixupLEAPass will get converted to

leal (%rax,%rcx,4), %eax
addl $1, %eax

[jbhateja]

• Rebasing
• Review comments resolution.

[jbhateja]

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

[jbhateja]

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.

[jbhateja]

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

[RKSimon]

A few minor comments @lsaba @craig.topper any final comments?

lib/Target/X86/X86ISelDAGToDAG.cpp

191

Make this a const method

1124

I meant make this a class method, but if you don't want to you can leave it here as lambda

lib/Target/X86/X86OptimizeLEAs.cpp

85

CopyLike

188

Again, can we avoid the static?

[lsaba]

@RKSimon No more comments from my side

[craig.topper]

I haven't been following this much so I have no comments either.

[RKSimon]

LGTM

[RKSimon]

LGTM - with those final few minors I mentioned

[jbhateja]

• Reivew comment resolution.
• Rebasing patch.

[jbhateja]

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

[jbhateja]

lib/Target/X86/X86OptimizeLEAs.cpp

188

Its used bacause we want MemOpKey for LEA factorization to be indipendent of Scale, keeping it as static avoids recreation of dummy scale.

[jbhateja]

• Register name case changes due to rebase.

[RKSimon]

rL319543 was reverted at rL319591 due to asan bot breakage

[xbolva00]

Please rebase. Thanks.

lib/Target/X86/X86ISelDAGToDAG.cpp

struct X86ISelAddressMode {
     bool isRIPRelative() const {
       if (BaseType != RegBase) return false;
       if (RegisterSDNode *RegNode =
             dyn_cast_or_null<RegisterSDNode>(Base_Reg.getNode()))
         return RegNode->getReg() == X86::RIP;
       return false;
     }
 
     void setBaseReg(SDValue Reg) {
       BaseType = RegBase;
       Base_Reg = Reg;
     }
 
 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
     void dump() {
       dbgs() << "X86ISelAddressMode " << this << '\n';
       dbgs() << "Base_Reg ";
class X86DAGToDAGISel final : public SelectionDAGISel {
 
     /// If true, selector should try to optimize for code size instead of
     /// performance.
     bool OptForSize;
 
     /// If true, selector should try to optimize for minimum code size.
     bool OptForMinSize;
 
   public:
     explicit X86DAGToDAGISel(X86TargetMachine &tm, CodeGenOpt::Level OptLevel)
         : SelectionDAGISel(tm, OptLevel), OptForSize(false),
           OptForMinSize(false) {}
 
     StringRef getPassName() const override {
       return "X86 DAG->DAG Instruction Selection";
     }
 
     bool runOnMachineFunction(MachineFunction &MF) override {
       // Reset the subtarget each time through.
       Subtarget = &MF.getSubtarget<X86Subtarget>();
       SelectionDAGISel::runOnMachineFunction(MF);
       return true;
     }
 
     void EmitFunctionEntryCode() override;
 
     bool IsProfitableToFold(SDValue N, SDNode *U, SDNode *Root) const override;
 
     void PreprocessISelDAG() override;
 
 // Include the pieces autogenerated from the target description.
 #include "X86GenDAGISel.inc"
 
   private:
     void Select(SDNode *N) override;
 
     bool foldOffsetIntoAddress(uint64_t Offset, X86ISelAddressMode &AM);
     bool matchLoadInAddress(LoadSDNode *N, X86ISelAddressMode &AM);
     bool matchWrapper(SDValue N, X86ISelAddressMode &AM);
     bool matchAddress(SDValue N, X86ISelAddressMode &AM);
     bool matchAdd(SDValue N, X86ISelAddressMode &AM, unsigned Depth);
     bool matchAddressRecursively(SDValue N, X86ISelAddressMode &AM,
                                  unsigned Depth);
static bool foldMaskAndShiftToScale(SelectionDAG &DAG, SDValue N,
   DAG.ReplaceAllUsesWith(N, NewSHL);
 
   AM.Scale = 1 << AMShiftAmt;
   AM.IndexReg = NewSRL;
   return false;
 }
 
 bool X86DAGToDAGISel::matchAddressRecursively(SDValue N, X86ISelAddressMode &AM,
                                               unsigned Depth) {
   SDLoc dl(N);
   DEBUG({
       dbgs() << "MatchAddress: ";
       AM.dump();
     });
   // Limit recursion.
   if (Depth > 5)
     return matchAddressBase(N, AM);
 
   // If this is already a %rip relative address, we can only merge immediates
   // into it.  Instead of handling this in every case, we handle it here.
   // RIP relative addressing: %rip + 32-bit displacement!
   if (AM.isRIPRelative()) {
     // FIXME: JumpTable and ExternalSymbol address currently don't like
     // displacements.  It isn't very important, but this should be fixed for
     // consistency.
     if (!(AM.ES || AM.MCSym) && AM.JT != -1)
bool X86DAGToDAGISel::matchAddressBase(SDValue N, X86ISelAddressMode &AM) {
   if (AM.BaseType != X86ISelAddressMode::RegBase || AM.Base_Reg.getNode()) {
     // If so, check to see if the scale index register is set.
     if (!AM.IndexReg.getNode()) {
       AM.IndexReg = N;
       AM.Scale = 1;
       return false;
     }
 
+    if (AM.BaseType == X86ISelAddressMode::RegBase && AM.Scale == 1) {
+      if (AM.Base_Reg == N) {
+         SDValue Base_Reg = AM.Base_Reg;
+         AM.Base_Reg = AM.IndexReg;
+         AM.IndexReg = Base_Reg;
+         AM.Scale = 2;
+         return false;
+      } else if (AM.IndexReg == N) {
+         AM.Scale = 2;
+         return false;
+      }
+    }
+
     // Otherwise, we cannot select it.
     return true;
   }
 
   // Default, generate it as a register.
   AM.BaseType = X86ISelAddressMode::RegBase;
   AM.Base_Reg = N;
   return false;

lib/Target/X86/X86OptimizeLEAs.cpp

 #include "X86InstrInfo.h"
 #include "X86Subtarget.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/CodeGen/LiveVariables.h"
 #include "llvm/CodeGen/MachineFunctionPass.h"
 #include "llvm/CodeGen/MachineInstrBuilder.h"
 #include "llvm/CodeGen/MachineOperand.h"
 #include "llvm/CodeGen/MachineRegisterInfo.h"
+#include "llvm/CodeGen/MachineDominators.h"
 #include "llvm/CodeGen/Passes.h"
 #include "llvm/IR/DIBuilder.h"
 #include "llvm/IR/DebugInfoMetadata.h"
 #include "llvm/IR/Function.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/raw_ostream.h"
 #include "llvm/Target/TargetInstrInfo.h"
 

 static inline bool isLEA(const MachineInstr &MI);
 
 namespace {
 /// A key based on instruction's memory operands.
 class MemOpKey {
 public:
   MemOpKey(const MachineOperand *Base, const MachineOperand *Scale,
            const MachineOperand *Index, const MachineOperand *Segment,
-           const MachineOperand *Disp)
-      : Disp(Disp) {
+           const MachineOperand *Disp, bool DispCheck = false)
+      : Disp(Disp), HardDispCheck(DispCheck) {
     Operands[0] = Base;
     Operands[1] = Scale;
     Operands[2] = Index;
     Operands[3] = Segment;
   }
 
   bool operator==(const MemOpKey &Other) const {
     // Addresses' bases, scales, indices and segments must be identical.
     for (int i = 0; i < 4; ++i)
       if (!isIdenticalOp(*Operands[i], *Other.Operands[i]))
         return false;
 
     // Addresses' displacements don't have to be exactly the same. It only
     // matters that they use the same symbol/index/address. Immediates' or
     // offsets' differences will be taken care of during instruction
-    // substitution.
+    // substitution. If HardDispCheck is true then Disp must be identical.
+    if (!HardDispCheck)
        return isSimilarDispOp(*Disp, *Other.Disp);
+    return isIdenticalOp(*Disp,*Other.Disp);
   }
 
   // Address' base, scale, index and segment operands.
   const MachineOperand *Operands[4];
 
   // Address' displacement operand.
   const MachineOperand *Disp;
+
+  // Forces absolute displacement check.
+  bool HardDispCheck;
 };
 } // end anonymous namespace
 
 /// Provide DenseMapInfo for MemOpKey.
 namespace llvm {
 template <> struct DenseMapInfo<MemOpKey> {
   typedef DenseMapInfo<const MachineOperand *> PtrInfo;
 
static unsigned getHashValue(const MemOpKey &Val) {
     // empty or tombstone.
     assert(Val.Disp != PtrInfo::getEmptyKey() && "Cannot hash the empty key");
     assert(Val.Disp != PtrInfo::getTombstoneKey() &&
            "Cannot hash the tombstone key");
 
     hash_code Hash = hash_combine(*Val.Operands[0], *Val.Operands[1],
                                   *Val.Operands[2], *Val.Operands[3]);
 
     // If the address displacement is an immediate, it should not affect the
     // hash so that memory operands which differ only be immediate displacement
     // would have the same hash. If the address displacement is something else,
     // we should reflect symbol/index/address in the hash.
     switch (Val.Disp->getType()) {
     case MachineOperand::MO_Immediate:
       break;
     case MachineOperand::MO_ConstantPoolIndex:
     case MachineOperand::MO_JumpTableIndex:
static bool isEqual(const MemOpKey &LHS, const MemOpKey &RHS) {
     // empty or tombstone.
     if (RHS.Disp == PtrInfo::getEmptyKey())
       return LHS.Disp == PtrInfo::getEmptyKey();
     if (RHS.Disp == PtrInfo::getTombstoneKey())
       return LHS.Disp == PtrInfo::getTombstoneKey();
     return LHS == RHS;
   }
 };
 }
 
 /// \brief Returns a hash table key based on memory operands of \p MI. The
 /// number of the first memory operand of \p MI is specified through \p N.
 static inline MemOpKey getMemOpKey(const MachineInstr &MI, unsigned N) {
   assert((isLEA(MI) || MI.mayLoadOrStore()) &&
          "The instruction must be a LEA, a load or a store");
   return MemOpKey(&MI.getOperand(N + X86::AddrBaseReg),
                   &MI.getOperand(N + X86::AddrScaleAmt),
                   &MI.getOperand(N + X86::AddrIndexReg),
                   &MI.getOperand(N + X86::AddrSegmentReg),
                   &MI.getOperand(N + X86::AddrDisp));
 }
 
+static inline MemOpKey getMemOpCSEKey(const MachineInstr &MI, unsigned N) {
+  static MachineOperand DummyScale = MachineOperand::CreateImm(1);
+  assert((isLEA(MI) || MI.mayLoadOrStore()) &&
+         "The instruction must be a LEA, a load or a store");
+  return MemOpKey(&MI.getOperand(N + X86::AddrBaseReg),
+                  &DummyScale,
+                  &MI.getOperand(N + X86::AddrIndexReg),
+                  &MI.getOperand(N + X86::AddrSegmentReg),
+                  &MI.getOperand(N + X86::AddrDisp), true);
+}
+
 static inline bool isIdenticalOp(const MachineOperand &MO1,
                                  const MachineOperand &MO2) {
   return MO1.isIdenticalTo(MO2) &&
          (!MO1.isReg() ||
           !TargetRegisterInfo::isPhysicalRegister(MO1.getReg()));
 }
 
 #ifndef NDEBUG
 static bool isValidDispOp(const MachineOperand &MO) {
   return MO.isImm() || MO.isCPI() || MO.isJTI() || MO.isSymbol() ||
          MO.isGlobal() || MO.isBlockAddress() || MO.isMCSymbol() || MO.isMBB();
 }
 #endif
 
 static bool isSimilarDispOp(const MachineOperand &MO1,
                             const MachineOperand &MO2) {
   assert(isValidDispOp(MO1) && isValidDispOp(MO2) &&
          "Address displacement operand is not valid");
   return (MO1.isImm() && MO2.isImm()) ||
          (MO1.isCPI() && MO2.isCPI() && MO1.getIndex() == MO2.getIndex()) ||
          (MO1.isJTI() && MO2.isJTI() && MO1.getIndex() == MO2.getIndex()) ||
          (MO1.isSymbol() && MO2.isSymbol() &&
           MO1.getSymbolName() == MO2.getSymbolName()) ||
          (MO1.isGlobal() && MO2.isGlobal() &&
           MO1.getGlobal() == MO2.getGlobal()) ||
          (MO1.isBlockAddress() && MO2.isBlockAddress() &&
           MO1.getBlockAddress() == MO2.getBlockAddress()) ||
          (MO1.isMCSymbol() && MO2.isMCSymbol() &&
           MO1.getMCSymbol() == MO2.getMCSymbol()) ||
          (MO1.isMBB() && MO2.isMBB() && MO1.getMBB() == MO2.getMBB());
 }
 
 static inline bool isLEA(const MachineInstr &MI) {
   unsigned Opcode = MI.getOpcode();
   return Opcode == X86::LEA16r || Opcode == X86::LEA32r ||
          Opcode == X86::LEA64r || Opcode == X86::LEA64_32r;
 }
 
 namespace {
 class OptimizeLEAPass : public MachineFunctionPass {
 public:
   OptimizeLEAPass() : MachineFunctionPass(ID) {}
 
   StringRef getPassName() const override { return "X86 LEA Optimize"; }
 
   /// \brief Loop over all of the basic blocks, replacing address
   /// calculations in load and store instructions, if it's already
   /// been calculated by LEA. Also, remove redundant LEAs.
   bool runOnMachineFunction(MachineFunction &MF) override;
 
+  void getAnalysisUsage(AnalysisUsage &AU) const override {
+     AU.setPreservesCFG();
+     MachineFunctionPass::getAnalysisUsage(AU);
+     AU.addRequired<MachineDominatorTree>();
+  }
+
 private:
   typedef DenseMap<MemOpKey, SmallVector<MachineInstr *, 16>> MemOpMap;
 
   /// \brief Returns a distance between two instructions inside one basic block.
   /// Negative result means, that instructions occur in reverse order.
   int calcInstrDist(const MachineInstr &First, const MachineInstr &Last);
 
   /// \brief Choose the best \p LEA instruction from the \p List to replace
   /// address calculation in \p MI instruction. Return the address displacement
   /// and the distance between \p MI and the chosen \p BestLEA in
   /// \p AddrDispShift and \p Dist.
   bool chooseBestLEA(const SmallVectorImpl<MachineInstr *> &List,
                      const MachineInstr &MI, MachineInstr *&BestLEA,
                      int64_t &AddrDispShift, int &Dist);
 
   /// \brief Returns the difference between addresses' displacements of \p MI1
   /// and \p MI2. The numbers of the first memory operands for the instructions
   /// are specified through \p N1 and \p N2.
   int64_t getAddrDispShift(const MachineInstr &MI1, unsigned N1,
                            const MachineInstr &MI2, unsigned N2) const;
 
   /// \brief Returns true if the \p Last LEA instruction can be replaced by the
   /// \p First. The difference between displacements of the addresses calculated
   /// by these LEAs is returned in \p AddrDispShift. It'll be used for proper
   /// replacement of the \p Last LEA's uses with the \p First's def register.
   bool isReplaceable(const MachineInstr &First, const MachineInstr &Last,
                      int64_t &AddrDispShift) const;
 
   /// \brief Find all LEA instructions in the basic block. Also, assign position
   /// numbers to all instructions in the basic block to speed up calculation of
   /// distance between them.
   void findLEAs(const MachineBasicBlock &MBB, MemOpMap &LEAs);
 
+  /// \brief Find all LEA instructions in the basic block that have same
+  /// Base, Index, Disp and Segment.
+  void populateCSEMap(const MachineBasicBlock &MBB, MemOpMap &LEAs);
+
+  /// \brief Factor out LEAs which share Base,Index,Offset and Segment.
+  bool cseLEAs(const MachineBasicBlock &MBB);
+
   /// \brief Removes redundant address calculations.
   bool removeRedundantAddrCalc(MemOpMap &LEAs);
 
   /// Replace debug value MI with a new debug value instruction using register
   /// VReg with an appropriate offset and DIExpression to incorporate the
   /// address displacement AddrDispShift. Return new debug value instruction.
   MachineInstr *replaceDebugValue(MachineInstr &MI, unsigned VReg,
                                   int64_t AddrDispShift);
 
   /// \brief Removes LEAs which calculate similar addresses.
   bool removeRedundantLEAs(MemOpMap &LEAs);
 
   DenseMap<const MachineInstr *, unsigned> InstrPos;
 
+  MachineDominatorTree *DT;
   MachineRegisterInfo *MRI;
   const X86InstrInfo *TII;
   const X86RegisterInfo *TRI;
 
   static char ID;
 };
 char OptimizeLEAPass::ID = 0;
 }
 
 FunctionPass *llvm::createX86OptimizeLEAs() { return new OptimizeLEAPass(); }
 
+void OptimizeLEAPass::populateCSEMap(const MachineBasicBlock &MBB, MemOpMap &LEAs) {
+  for (auto &MI : MBB) {
+    if (isLEA(MI))
+      LEAs[getMemOpCSEKey(MI, 1)].push_back(const_cast<MachineInstr *>(&MI));
+  }
+}
+
 int OptimizeLEAPass::calcInstrDist(const MachineInstr &First,
                                    const MachineInstr &Last) {
   // Both instructions must be in the same basic block and they must be
   // presented in InstrPos.
   assert(Last.getParent() == First.getParent() &&
          "Instructions are in different basic blocks");
   assert(InstrPos.find(&First) != InstrPos.end() &&
          InstrPos.find(&Last) != InstrPos.end() &&
          "Instructions' positions are undefined");
 
   return InstrPos[&Last] - InstrPos[&First];
 }
 
 // Find the best LEA instruction in the List to replace address recalculation in
 // MI. Such LEA must meet these requirements:
 // 1) The address calculated by the LEA differs only by the displacement from
 //    the address used in MI.
 // 2) The register class of the definition of the LEA is compatible with the
 //    register class of the address base register of MI.
 // 3) Displacement of the new memory operand should fit in 1 byte if possible.
 // 4) The LEA should be as close to MI as possible, and prior to it if
 //    possible.
 bool OptimizeLEAPass::chooseBestLEA(const SmallVectorImpl<MachineInstr *> &List,
                                     const MachineInstr &MI,
                                     MachineInstr *&BestLEA,
                                     int64_t &AddrDispShift, int &Dist) {
   const MachineFunction *MF = MI.getParent()->getParent();
   const MCInstrDesc &Desc = MI.getDesc();
   int MemOpNo = X86II::getMemoryOperandNo(Desc.TSFlags) +
                 X86II::getOperandBias(Desc);
 
   BestLEA = nullptr;
 
   // Loop over all LEA instructions.
   for (auto DefMI : List) {
     // Get new address displacement.
     int64_t AddrDispShiftTemp = getAddrDispShift(MI, MemOpNo, *DefMI, 1);
 
     // Make sure address displacement fits 4 bytes.
while (I1 != List.end()) {
             replaceDebugValue(MI, FirstVReg, AddrDispShift);
             continue;
           }
 
           // Get the number of the first memory operand.
           const MCInstrDesc &Desc = MI.getDesc();
           int MemOpNo =
               X86II::getMemoryOperandNo(Desc.TSFlags) +
               X86II::getOperandBias(Desc);
 
           // Update address base.
           MO.setReg(FirstVReg);
 
           // Update address disp.
           MachineOperand &Op = MI.getOperand(MemOpNo + X86::AddrDisp);
           if (Op.isImm())
             Op.setImm(Op.getImm() + AddrDispShift);
while (I1 != List.end()) {
       }
       ++I1;
     }
   }
 
   return Changed;
 }
 
+bool OptimizeLEAPass::cseLEAs(const MachineBasicBlock &MBB) {
+   MemOpMap LEAs;
+   bool cseDone = false;
+
+   // Legal scale value (1,2,4 & 8) vector.
+   int LegalScale[9] = {0,1,1,0,1,0,0,0,1};
+
+   populateCSEMap(MBB,LEAs);
+
+   auto CompareFn = 
+     [] (const MachineInstr *Arg1,const MachineInstr *Arg2) -> bool {
+        if(Arg1->getOperand(2).getImm() < Arg2->getOperand(2).getImm())
+           return false;
+        return true;  
+     };
+
+   // Loop over all entries in the table.
+   for (auto &E : LEAs) {
+     auto &List = E.second;
+     if(List.size() > 1) {
+        std::sort(List.begin(),List.end(),CompareFn);
+     }
+     // Loop over all LEA pairs.
+     for(auto LII = List.begin(); LII != List.end(); LII++) {
+        MachineInstr &LI1 = **LII;
+        auto LINext = std::next(LII);
+        if(LINext == List.end()) 
+           break;
+        MachineInstr &LI2 = **LINext;
+        if (!DT->dominates(&LI2,&LI1))
+           continue;
+        
+        int Scale1 = LI1.getOperand(2).getImm(); 
+        int Scale2 = LI2.getOperand(2).getImm(); 
+        assert(LI2.getOperand(0).isReg() && "Result is a VirtualReg");
+        DebugLoc DL = LI1.getDebugLoc();
+
+        int Factor = Scale1 - Scale2;
+        if (Factor > 0 && LegalScale[Factor]) {
+            DEBUG(dbgs() << "CSE LEAs: Candidate to replace: "; LI1.dump(););
+            MachineInstr *NewMI = 
+            BuildMI(*(const_cast<MachineBasicBlock *>(&MBB)),
+                &LI1,DL,TII->get(LI1.getOpcode()))
+              .addDef(LI1.getOperand(0).getReg())  // Dst   = Dst of LI1. 
+              .addUse(LI2.getOperand(0).getReg())  // Base  = Dst of LI2.
+              .addImm(Factor)                      // Scale = Diff b/w scales.
+              .addUse(LI1.getOperand(3).getReg())  // Index = Index of LI1.
+              .addImm(0)                           // Disp  = 0 
+              .addUse(LI1.getOperand(5).getReg()); // Segment = Segmant of LI1.  
+
+            LI1.eraseFromParent();
+            cseDone = NewMI != nullptr;
+            DEBUG(dbgs() << "CSE LEAs: Replaced by: "; NewMI->dump(););
+        }
+     }
+   } 
+   return cseDone;
+}
+
+
 bool OptimizeLEAPass::runOnMachineFunction(MachineFunction &MF) {
   bool Changed = false;
 
   if (DisableX86LEAOpt || skipFunction(*MF.getFunction()))
     return false;
 
   MRI = &MF.getRegInfo();
   TII = MF.getSubtarget<X86Subtarget>().getInstrInfo();
   TRI = MF.getSubtarget<X86Subtarget>().getRegisterInfo();
+  DT  = &getAnalysis<MachineDominatorTree>();
 
   // Process all basic blocks.
   for (auto &MBB : MF) {
     MemOpMap LEAs;
     InstrPos.clear();
 
+    // Attempt CSE over LEAs.
+    Changed |= cseLEAs(MBB);
+
     // Find all LEA instructions in basic block.
     findLEAs(MBB, LEAs);
 
     // If current basic block has no LEAs, move on to the next one.
     if (LEAs.empty())
       continue;
 
     // Remove redundant LEA instructions.
     Changed |= removeRedundantLEAs(LEAs);
 
     // Remove redundant address calculations. Do it only for -Os/-Oz since only
     // a code size gain is expected from this part of the pass.
     if (MF.getFunction()->optForSize())
       Changed |= removeRedundantAddrCalc(LEAs);
   }
 
   return Changed;
 }

test/CodeGen/X86/lea-opt-cst.ll

+; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
+; RUN: llc < %s -mtriple=x86_64-unknown | FileCheck %s -check-prefix=X64
+; RUN: llc < %s -mtriple=i686-unknown   | FileCheck %s -check-prefix=X86
+
+%struct.SA = type { i32 , i32  , i32 , i32 ,i32 }
+
+define void @test_func(%struct.SA* nocapture %ctx, i32 %n) local_unnamed_addr {
+; X64-LABEL: test_func:
+; X64:       # BB#0: # %entry
+; X64-NEXT:    movl (%rdi), %eax
+; X64-NEXT:    movl 16(%rdi), %ecx
+; X64-NEXT:    leal 1(%rax,%rcx), %eax
+; X64-NEXT:    movl %eax, 12(%rdi)
+; X64-NEXT:    leal (%eax,%rcx), %eax
+; X64-NEXT:    movl %eax, 16(%rdi)
+; X64-NEXT:    retq
+;
+; X86-LABEL: test_func:
+; X86:       # BB#0: # %entry
+; X86-NEXT:    movl {{[0-9]+}}(%esp), %eax
+; X86-NEXT:    movl (%eax), %ecx
+; X86-NEXT:    movl 16(%eax), %edx
+; X86-NEXT:    leal 1(%ecx,%edx), %ecx
+; X86-NEXT:    movl %ecx, 12(%eax)
+; X86-NEXT:    leal (%ecx,%edx), %ecx
+; X86-NEXT:    movl %ecx, 16(%eax)
+; X86-NEXT:    retl
+ entry:
+   %h0 = getelementptr inbounds %struct.SA, %struct.SA* %ctx, i64 0, i32 0
+   %0 = load i32, i32* %h0, align 8
+   %h3 = getelementptr inbounds %struct.SA, %struct.SA* %ctx, i64 0, i32 3
+   %h4 = getelementptr inbounds %struct.SA, %struct.SA* %ctx, i64 0, i32 4
+   %1 = load i32, i32* %h4, align 8
+   %add = add i32 %0, 1
+   %add4 = add i32 %add, %1
+   store i32 %add4, i32* %h3, align 4
+   %add29 = add i32 %add4 , %1
+   store i32 %add29, i32* %h4, align 8
+   ret void
+}

test/CodeGen/X86/mul-constant-i16.ll

 ; X64-NEXT:    retq
   %mul = mul nsw i16 %x, 28
   ret i16 %mul
 }
 
 define i16 @test_mul_by_29(i16 %x) {
 ; X86-LABEL: test_mul_by_29:
 ; X86:       # BB#0:
-; X86-NEXT:    movzwl {{[0-9]+}}(%esp), %ecx
-; X86-NEXT:    leal (%ecx,%ecx,8), %eax
-; X86-NEXT:    leal (%eax,%eax,2), %eax
-; X86-NEXT:    addl %ecx, %eax
-; X86-NEXT:    addl %ecx, %eax
+; X86-NEXT:    movzwl {{[0-9]+}}(%esp), %eax
+; X86-NEXT:    leal (%eax,%eax,8), %ecx
+; X86-NEXT:    leal (%ecx,%ecx,2), %ecx
+; X86-NEXT:    leal (%ecx,%eax,2), %eax
 ; X86-NEXT:    # kill: %AX<def> %AX<kill> %EAX<kill>
 ; X86-NEXT:    retl
 ;
 ; X64-LABEL: test_mul_by_29:
 ; X64:       # BB#0:
 ; X64-NEXT:    # kill: %EDI<def> %EDI<kill> %RDI<def>
 ; X64-NEXT:    leal (%rdi,%rdi,8), %eax
 ; X64-NEXT:    leal (%rax,%rax,2), %eax
-; X64-NEXT:    addl %edi, %eax
-; X64-NEXT:    addl %edi, %eax
+; X64-NEXT:    leal (%rax,%rdi,2), %eax
 ; X64-NEXT:    # kill: %AX<def> %AX<kill> %EAX<kill>
 ; X64-NEXT:    retq
   %mul = mul nsw i16 %x, 29
   ret i16 %mul
 }
 
 define i16 @test_mul_by_30(i16 %x) {
 ; X86-LABEL: test_mul_by_30:

test/CodeGen/X86/mul-constant-i32.ll

 ; SLM-NOOPT-NEXT:    retq # sched: [4:1.00]
   %mul = mul nsw i32 %x, 28
   ret i32 %mul
 }
 
 define i32 @test_mul_by_29(i32 %x) {
 ; X86-LABEL: test_mul_by_29:
 ; X86:       # BB#0:
-; X86-NEXT:    movl {{[0-9]+}}(%esp), %ecx
-; X86-NEXT:    leal (%ecx,%ecx,8), %eax
-; X86-NEXT:    leal (%eax,%eax,2), %eax
-; X86-NEXT:    addl %ecx, %eax
-; X86-NEXT:    addl %ecx, %eax
+; X86-NEXT:    movl {{[0-9]+}}(%esp), %eax
+; X86-NEXT:    leal (%eax,%eax,8), %ecx
+; X86-NEXT:    leal (%ecx,%ecx,2), %ecx
+; X86-NEXT:    leal (%ecx,%eax,2), %eax
 ; X86-NEXT:    retl
 ;
 ; X64-HSW-LABEL: test_mul_by_29:
 ; X64-HSW:       # BB#0:
 ; X64-HSW-NEXT:    # kill: %EDI<def> %EDI<kill> %RDI<def>
 ; X64-HSW-NEXT:    leal (%rdi,%rdi,8), %eax # sched: [1:0.50]
 ; X64-HSW-NEXT:    leal (%rax,%rax,2), %eax # sched: [1:0.50]
-; X64-HSW-NEXT:    addl %edi, %eax # sched: [1:0.25]
-; X64-HSW-NEXT:    addl %edi, %eax # sched: [1:0.25]
+; X64-HSW-NEXT:    leal (%rax,%rdi,2), %eax # sched: [1:0.50]
 ; X64-HSW-NEXT:    retq # sched: [1:1.00]
 ;
 ; X64-JAG-LABEL: test_mul_by_29:
 ; X64-JAG:       # BB#0:
 ; X64-JAG-NEXT:    # kill: %EDI<def> %EDI<kill> %RDI<def>
 ; X64-JAG-NEXT:    leal (%rdi,%rdi,8), %eax # sched: [1:0.50]
 ; X64-JAG-NEXT:    leal (%rax,%rax,2), %eax # sched: [1:0.50]
-; X64-JAG-NEXT:    addl %edi, %eax # sched: [1:0.50]
-; X64-JAG-NEXT:    addl %edi, %eax # sched: [1:0.50]
+; X64-JAG-NEXT:    leal (%rax,%rdi,2), %eax # sched: [1:0.50]
 ; X64-JAG-NEXT:    retq # sched: [4:1.00]
 ;
 ; X86-NOOPT-LABEL: test_mul_by_29:
 ; X86-NOOPT:       # BB#0:
 ; X86-NOOPT-NEXT:    imull $29, {{[0-9]+}}(%esp), %eax
 ; X86-NOOPT-NEXT:    retl
 ;
 ; HSW-NOOPT-LABEL: test_mul_by_29:

test/CodeGen/X86/mul-constant-i64.ll

 }
 
 define i64 @test_mul_by_29(i64 %x) {
 ; X86-LABEL: test_mul_by_29:
 ; X86:       # BB#0:
 ; X86-NEXT:    movl {{[0-9]+}}(%esp), %eax
 ; X86-NEXT:    leal (%eax,%eax,8), %ecx
 ; X86-NEXT:    leal (%ecx,%ecx,2), %ecx
-; X86-NEXT:    addl %eax, %ecx
-; X86-NEXT:    addl %eax, %ecx
+; X86-NEXT:    leal (%ecx,%eax,2), %ecx
 ; X86-NEXT:    movl $29, %eax
 ; X86-NEXT:    mull {{[0-9]+}}(%esp)
 ; X86-NEXT:    addl %ecx, %edx
 ; X86-NEXT:    retl
 ;
 ; X64-HSW-LABEL: test_mul_by_29:
 ; X64-HSW:       # BB#0:
 ; X64-HSW-NEXT:    leaq (%rdi,%rdi,8), %rax # sched: [1:0.50]
 ; X64-HSW-NEXT:    leaq (%rax,%rax,2), %rax # sched: [1:0.50]
-; X64-HSW-NEXT:    addq %rdi, %rax # sched: [1:0.25]
-; X64-HSW-NEXT:    addq %rdi, %rax # sched: [1:0.25]
+; X64-HSW-NEXT:    leaq (%rax,%rdi,2), %rax # sched: [1:0.50]
 ; X64-HSW-NEXT:    retq # sched: [1:1.00]
 ;
 ; X64-JAG-LABEL: test_mul_by_29:
 ; X64-JAG:       # BB#0:
 ; X64-JAG-NEXT:    leaq (%rdi,%rdi,8), %rax # sched: [1:0.50]
 ; X64-JAG-NEXT:    leaq (%rax,%rax,2), %rax # sched: [1:0.50]
-; X64-JAG-NEXT:    addq %rdi, %rax # sched: [1:0.50]
-; X64-JAG-NEXT:    addq %rdi, %rax # sched: [1:0.50]
+; X64-JAG-NEXT:    leaq (%rax,%rdi,2), %rax # sched: [1:0.50]
 ; X64-JAG-NEXT:    retq # sched: [4:1.00]
 ;
 ; X86-NOOPT-LABEL: test_mul_by_29:
 ; X86-NOOPT:       # BB#0:
 ; X86-NOOPT-NEXT:    movl $29, %eax
 ; X86-NOOPT-NEXT:    mull {{[0-9]+}}(%esp)
 ; X86-NOOPT-NEXT:    imull $29, {{[0-9]+}}(%esp), %ecx
 ; X86-NOOPT-NEXT:    addl %ecx, %edx

test/CodeGen/X86/mul-constant-result.ll

 ; X86-NEXT:    leal (%eax,%eax,8), %ecx
 ; X86-NEXT:    leal (%ecx,%ecx,2), %ecx
 ; X86-NEXT:    addl %ecx, %eax
 ; X86-NEXT:    popl %esi
 ; X86-NEXT:    retl
 ; X86-NEXT:  .LBB0_35:
 ; X86-NEXT:    leal (%eax,%eax,8), %ecx
 ; X86-NEXT:    leal (%ecx,%ecx,2), %ecx
-; X86-NEXT:    addl %eax, %ecx
-; X86-NEXT:    addl %ecx, %eax
+; X86-NEXT:    leal (%ecx,%eax,2), %eax
 ; X86-NEXT:    popl %esi
 ; X86-NEXT:    retl
 ; X86-NEXT:  .LBB0_36:
 ; X86-NEXT:    movl %eax, %ecx
 ; X86-NEXT:    shll $5, %ecx
 ; X86-NEXT:    subl %eax, %ecx
 ; X86-NEXT:    jmp .LBB0_12
 ; X86-NEXT:  .LBB0_37:

 ; X64-HSW-NEXT:  .LBB0_30:
 ; X64-HSW-NEXT:    leal (%rax,%rax,8), %eax
 ; X64-HSW-NEXT:    leal (%rax,%rax,2), %eax
 ; X64-HSW-NEXT:    # kill: %EAX<def> %EAX<kill> %RAX<kill>
 ; X64-HSW-NEXT:    retq
 ; X64-HSW-NEXT:  .LBB0_31:
 ; X64-HSW-NEXT:    leal (%rax,%rax,8), %ecx
 ; X64-HSW-NEXT:    leal (%rcx,%rcx,2), %ecx
-; X64-HSW-NEXT:    jmp .LBB0_17
-; X64-HSW-NEXT:  .LBB0_32:
-; X64-HSW-NEXT:    leal (%rax,%rax,8), %ecx
-; X64-HSW-NEXT:    leal (%rcx,%rcx,2), %ecx
-; X64-HSW-NEXT:    addl %eax, %ecx
 ; X64-HSW-NEXT:  .LBB0_17:
 ; X64-HSW-NEXT:    addl %eax, %ecx
 ; X64-HSW-NEXT:    movl %ecx, %eax
 ; X64-HSW-NEXT:    # kill: %EAX<def> %EAX<kill> %RAX<kill>
 ; X64-HSW-NEXT:    retq
+; X64-HSW-NEXT:  .LBB0_32:
+; X64-HSW-NEXT:    leal (%rax,%rax,8), %ecx
+; X64-HSW-NEXT:    leal (%rcx,%rcx,2), %ecx
+; X64-HSW-NEXT:    leal (%rcx,%rax,2), %eax
+; X64-HSW-NEXT:    # kill: %EAX<def> %EAX<kill> %RAX<kill>
+; X64-HSW-NEXT:    retq
 ; X64-HSW-NEXT:  .LBB0_33:
 ; X64-HSW-NEXT:    movl %eax, %ecx
 ; X64-HSW-NEXT:    shll $5, %ecx
 ; X64-HSW-NEXT:    subl %eax, %ecx
 ; X64-HSW-NEXT:    jmp .LBB0_8
 ; X64-HSW-NEXT:  .LBB0_34:
 ; X64-HSW-NEXT:    movl %eax, %ecx
 ; X64-HSW-NEXT:    shll $5, %ecx

test/CodeGen/X86/umul-with-overflow.ll

+; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
 ; RUN: llc < %s -mtriple=i686-unknown-linux-gnu | FileCheck %s
 
 declare {i32, i1} @llvm.umul.with.overflow.i32(i32 %a, i32 %b)
 define zeroext i1 @a(i32 %x)  nounwind {
+; CHECK-LABEL: a:
+; CHECK:       # BB#0:
+; CHECK-NEXT:    movl {{[0-9]+}}(%esp), %eax
+; CHECK-NEXT:    movl $3, %ecx
+; CHECK-NEXT:    mull %ecx
+; CHECK-NEXT:    seto %al
+; CHECK-NEXT:    retl
   %res = call {i32, i1} @llvm.umul.with.overflow.i32(i32 %x, i32 3)
   %obil = extractvalue {i32, i1} %res, 1
   ret i1 %obil
-  
-; CHECK-LABEL: a:
-; CHECK: mull
-; CHECK: seto %al
-; CHECK: ret
 }
 
 define i32 @test2(i32 %a, i32 %b) nounwind readnone {
+; CHECK-LABEL: test2:
+; CHECK:       # BB#0: # %entry
+; CHECK-NEXT:    movl {{[0-9]+}}(%esp), %eax
+; CHECK-NEXT:    addl {{[0-9]+}}(%esp), %eax
+; CHECK-NEXT:    addl %eax, %eax
+; CHECK-NEXT:    retl
 entry:
   %tmp0 = add i32 %b, %a
   %tmp1 = call { i32, i1 } @llvm.umul.with.overflow.i32(i32 %tmp0, i32 2)
   %tmp2 = extractvalue { i32, i1 } %tmp1, 0
   ret i32 %tmp2
-; CHECK-LABEL: test2:
-; CHECK: addl
-; CHECK-NEXT: addl
-; CHECK-NEXT: ret
 }
 
 define i32 @test3(i32 %a, i32 %b) nounwind readnone {
+; CHECK-LABEL: test3:
+; CHECK:       # BB#0: # %entry
+; CHECK-NEXT:    movl {{[0-9]+}}(%esp), %eax
+; CHECK-NEXT:    addl {{[0-9]+}}(%esp), %eax
+; CHECK-NEXT:    movl $4, %ecx
+; CHECK-NEXT:    mull %ecx
+; CHECK-NEXT:    retl
 entry:
   %tmp0 = add i32 %b, %a
   %tmp1 = call { i32, i1 } @llvm.umul.with.overflow.i32(i32 %tmp0, i32 4)
   %tmp2 = extractvalue { i32, i1 } %tmp1, 0
   ret i32 %tmp2
-; CHECK-LABEL: test3:
-; CHECK: addl
-; CHECK: mull
-; CHECK-NEXT: ret
 }

test/Transforms/LoopStrengthReduce/X86/ivchain-X86.ll

 ; RUN: llc < %s -O3 -march=x86-64 -mcpu=core2 | FileCheck %s -check-prefix=X64
 ; RUN: llc < %s -O3 -march=x86 -mcpu=core2 | FileCheck %s -check-prefix=X32
 
 ; @simple is the most basic chain of address induction variables. Chaining
 ; saves at least one register and avoids complex addressing and setup
 ; code.
 ;
 ; X64: @simple
 ; %x * 4
 ; X64: shlq $2
 ; no other address computation in the preheader
 ; X64-NEXT: xorl
 ; X64-NEXT: .p2align
 ; X64: %loop
 ; no complex address modes
-; X64-NOT: (%{{[^)]+}},%{{[^)]+}},
+; X64-NOT: [1-9]+(%{{[^)]+}},%{{[^)]+}},
 ;
 ; X32: @simple
 ; no expensive address computation in the preheader
 ; X32-NOT: imul
 ; X32: %loop
 ; no complex address modes
-; X32-NOT: (%{{[^)]+}},%{{[^)]+}},
+; X32-NOT: [1-9]+(%{{[^)]+}},%{{[^)]+}},
 define i32 @simple(i32* %a, i32* %b, i32 %x) nounwind {
 entry:
   br label %loop
 loop:
   %iv = phi i32* [ %a, %entry ], [ %iv4, %loop ]
   %s = phi i32 [ 0, %entry ], [ %s4, %loop ]
   %v = load i32, i32* %iv
   %iv1 = getelementptr inbounds i32, i32* %iv, i32 %x

 ; strange increment expressions like this:
 ; IV + ((sext i32 (2 * %s) to i64) + (-1 * (sext i32 %s to i64)))
 ;
 ; X32: extrastride:
 ; no spills in the preheader
 ; X32-NOT: mov{{.*}}(%esp){{$}}
 ; X32: %for.body{{$}}
 ; no complex address modes
-; X32-NOT: (%{{[^)]+}},%{{[^)]+}},
+; X32-NOT: [1-9]+(%{{[^)]+}},%{{[^)]+}},
 ; no reloads
 ; X32-NOT: (%esp)
 define void @extrastride(i8* nocapture %main, i32 %main_stride, i32* nocapture %res, i32 %x, i32 %y, i32 %z) nounwind {
 entry:
   %cmp8 = icmp eq i32 %z, 0
   br i1 %cmp8, label %for.end, label %for.body.lr.ph
 
 for.body.lr.ph:                                   ; preds = %entry

utils/TableGen/DAGISelMatcherGen.cpp

if (N->getOperator()->isSubClassOf("ComplexPattern")) {
     }
 
     return;
   }
 
   const SDNodeInfo &CInfo = CGP.getSDNodeInfo(N->getOperator());
 
   // If this is an 'and R, 1234' where the operation is AND/OR and the RHS is
-  // a constant without a predicate fn that has more that one bit set, handle
+  // a constant without a predicate fn that has more than one bit set, handle
   // this as a special case.  This is usually for targets that have special
   // handling of certain large constants (e.g. alpha with it's 8/16/32-bit
   // handling stuff).  Using these instructions is often far more efficient
   // than materializing the constant.  Unfortunately, both the instcombiner
   // and the dag combiner can often infer that bits are dead, and thus drop
   // them from the mask in the dag.  For example, it might turn 'AND X, 255'
   // into 'AND X, 254' if it knows the low bit is set.  Emit code that checks
   // to handle this.