Skip to content

Commit f2e60fc

Browse files
committedJun 14, 2019
[SimpligyCFG] NFC intended, remove GCD that was only used for powers of two
and replace with an equilivent countTrailingZeros. GCD is much more expensive than this, with repeated division. This depends on D60823 Differential Revision: https://reviews.llvm.org/D61151 llvm-svn: 363422
1 parent bea1286 commit f2e60fc

File tree

1 file changed

+11
-13
lines changed

1 file changed

+11
-13
lines changed
 

‎llvm/lib/Transforms/Utils/SimplifyCFG.cpp

+11-13
Original file line numberDiff line numberDiff line change
@@ -5559,25 +5559,23 @@ static bool ReduceSwitchRange(SwitchInst *SI, IRBuilder<> &Builder,
55595559
// Now we have signed numbers that have been shifted so that, given enough
55605560
// precision, there are no negative values. Since the rest of the transform
55615561
// is bitwise only, we switch now to an unsigned representation.
5562-
uint64_t GCD = 0;
5563-
for (auto &V : Values)
5564-
GCD = GreatestCommonDivisor64(GCD, (uint64_t)V);
55655562

5566-
// This transform can be done speculatively because it is so cheap - it results
5567-
// in a single rotate operation being inserted. This can only happen if the
5568-
// factor extracted is a power of 2.
5569-
// FIXME: If the GCD is an odd number we can multiply by the multiplicative
5570-
// inverse of GCD and then perform this transform.
5563+
// This transform can be done speculatively because it is so cheap - it
5564+
// results in a single rotate operation being inserted.
55715565
// FIXME: It's possible that optimizing a switch on powers of two might also
55725566
// be beneficial - flag values are often powers of two and we could use a CLZ
55735567
// as the key function.
5574-
if (GCD <= 1 || !isPowerOf2_64(GCD))
5575-
// No common divisor found or too expensive to compute key function.
5576-
return false;
55775568

5578-
unsigned Shift = Log2_64(GCD);
5569+
// countTrailingZeros(0) returns 64. As Values is guaranteed to have more than
5570+
// one element and LLVM disallows duplicate cases, Shift is guaranteed to be
5571+
// less than 64.
5572+
unsigned Shift = 64;
55795573
for (auto &V : Values)
5580-
V = (int64_t)((uint64_t)V >> Shift);
5574+
Shift = std::min(Shift, countTrailingZeros((uint64_t)V));
5575+
assert(Shift < 64);
5576+
if (Shift > 0)
5577+
for (auto &V : Values)
5578+
V = (int64_t)((uint64_t)V >> Shift);
55815579

55825580
if (!isSwitchDense(Values))
55835581
// Transform didn't create a dense switch.

0 commit comments

Comments
 (0)