This is an archive of the discontinued LLVM Phabricator instance.

[X86] Reduce complexity of the LEA optimization pass
ClosedPublic

Authored by aturetsk on Dec 21 2015, 8:35 AM.

Details

Summary

In the OptimizeLEA pass keep instructions' positions in the basic block saved and use them for calculation of the distance between two instructions instead of std::distance. This reduces complexity of the pass from O(n^3) to O(n^2) and thus the compile time.

Diff Detail

Event Timeline

aturetsk updated this revision to Diff 43377.Dec 21 2015, 8:35 AM
aturetsk retitled this revision from to [X86] Reduce complexity of the LEA optimization pass.
aturetsk updated this object.
aturetsk added reviewers: qcolombet, dberlin.
aturetsk added a subscriber: llvm-commits.

Here are the results.

Just -Os (LEA pass is disabled):

$ time ./bin/clang++ -std=c++11 -S a.ll -Os

real    0m8.328s
user    0m8.282s
sys     0m0.041s

-Os with the old LEA pass:

$ time ./bin/clang++ -std=c++11 -S a.ll -Os -mllvm -enable-x86-lea-opt

real    0m11.653s
user    0m11.591s
sys     0m0.059s

-Os with the new LEA pass:

$ time ./bin/clang++ -std=c++11 -S a.ll -Os -mllvm -enable-x86-lea-opt

real    0m8.446s
user    0m8.380s
sys     0m0.064s

a.ll is taken from the example from https://llvm.org/bugs/show_bug.cgi?id=25843 and was generated this way:

$ python a.py 5000 > a.cc
$ ./bin/clang++ -std=c++11 -S -emit-llvm -Os a.cc
(this took about 1.5 hours)

Thanks for this! Just one tiny nit.

lib/Target/X86/X86OptimizeLEAs.cpp
93

Is there a reason that we can't use DenseMap here instead?

aturetsk updated this revision to Diff 43437.Dec 22 2015, 3:20 AM

Replaced unordered_map with DenseMap.

Hello George,
Thanks for the review.

lib/Target/X86/X86OptimizeLEAs.cpp
93

Fixed.

qcolombet accepted this revision.Jan 6 2016, 11:26 AM
qcolombet edited edge metadata.
This revision is now accepted and ready to land.Jan 6 2016, 11:26 AM
This revision was automatically updated to reflect the committed changes.