]> granicus.if.org Git - llvm/commit
projects / llvm / commit
? search:
summary | shortlog | log | commit | commitdiff | tree
(parent: caf5bed) | 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)
commit74413b926ab5eef6b03d15e90cdbb164b89622de
tree1df83ffd7270a04341d5255d647a04bdef51b70btree | snapshot
parentcaf5bedd42fbd1457239fded7e355f1e6314daa9commit | 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

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@300252 91177308-0d34-0410-b5e6-96231b3b80d8
include/llvm/ADT/APInt.h diff | blob | history
lib/Support/APInt.cpp diff | blob | history
lib/Transforms/InstCombine/InstCombineCompares.cpp diff | blob | history
test/Transforms/InstCombine/divisibility.ll [new file with mode: 0644] blob
unittests/ADT/APIntTest.cpp diff | blob | history
Unnamed repository; edit this file 'description' to name the repository.