projects / platform / upstream / llvm.git / commit
? search:
summary | shortlog | log | commit | commitdiff | tree
(parent: 257cb4e) | patch
Remove all allocation and divisions from GreatestCommonDivisor
authorRichard Smith <richard-llvm@metafoo.co.uk>
Thu, 13 Apr 2017 20:29:59 +0000 (20:29 +0000)
committerRichard Smith <richard-llvm@metafoo.co.uk>
Thu, 13 Apr 2017 20:29:59 +0000 (20:29 +0000)
commit55bd375b69c6ae16727333303ea582ed3b1b3500
tree3b3b748bb1d93a405a7fbc10dd0d6c2658c91699tree | snapshot
parent257cb4e099cd739b13ac40ef7b7412a34ecafe59commit | diff
Remove all allocation and divisions from GreatestCommonDivisor

Switch from Euclid's algorithm to Stein's algorithm for computing GCD. This
avoids the (expensive) APInt division operation in favour of bit operations.
Remove all memory allocation from within the GCD loop by tweaking our `lshr`
implementation so it can operate in-place.

Differential Revision: https://reviews.llvm.org/D31968

llvm-svn: 300252
llvm/include/llvm/ADT/APInt.h diff | blob | history
llvm/lib/Support/APInt.cpp diff | blob | history
llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp diff | blob | history
llvm/test/Transforms/InstCombine/divisibility.ll [new file with mode: 0644] blob
llvm/unittests/ADT/APIntTest.cpp diff | blob | history
Domain: System / Toolchain;