[SimpligyCFG] NFC, remove GCD that was only used for powers of two

[shawnl]

Summary

This is patch 2 is a series beginning with D61150

and replace with an equilivent countTrailingZeros.

GCD is much more expensive than this, with repeated division.

And actually using the full GCD would require multiplication in the generated code.

This depends on D60823

[jmolloy]

Thanks for splitting these up! They're really much easier to read.

Some comments, but none of them fatal.

Cheers!

lib/Transforms/Utils/SimplifyCFG.cpp

5543

It feels to me like this comment still has value - perhaps it should be kept?

5550

I personally would rewrite this whole thing as:

unsigned Shift = 64;
for (auto &V : Values)
  Shift = std::min(Shift, countTrailingZeros((uint64_t)V);

I don't see the need for the zero bailout.

5551

This comment could be clearer. I've tried to understand it a couple of times and only vaguely do. Could you please rewrite it so that it clearly states *which* edge condition you're referring to (I presume ctz(0)?)

5561

Shift is an integer, not a pointer or boolean, so please use if (Shift != 0).

5563

Nit: I'd use:

V >>= Shift;

Just to make it ultra-clear that we're updating V in-place (updating a mutable reference iterator is fine in this case, but it's something readers normally expect so it'd be good to make this very clear).

[nikic]

lib/Transforms/Utils/SimplifyCFG.cpp

5563

It's rather hidden due to overzealous auto use, but this is going to perform an arithmetic shift. This doesn't seem correct to me, as the used rotate operation degenerates to a logical shift for valid values (with low bits unset).

[shawnl]

lib/Transforms/Utils/SimplifyCFG.cpp

5563

Yeah, that happened when I split the patches up. (and the style issue because I just simplified the old code, but I was using unsigned then)

[shawnl]

This now depends on D60823

[jmolloy]

lib/Transforms/Utils/SimplifyCFG.cpp

5553

I completely misinterpreted this comment and this code. I thought your comment referred to *runtime behaviour* of generated cttz instructions. Actually it's just referring to the return value of llvm::countTrailingZeros().

I'd recommend making this comment less scary. My suggestion would be:

countTrailingZeros(0) returns 64. As Values is guaranteed to have more than one element and LLVM disallows duplicate cases, Shift is guaranteed to be less than 64.

... and then add an assert(Shift < 64) afterwards to prove it.

5563

I'd recommend just switching to using APInt. That's what it's for after all - making things like this self-explaining.

[shawnl]

lib/Transforms/Utils/SimplifyCFG.cpp

5563

I remove your signed interpretation in a later patch.

[jmolloy]

LGTM.

[shawnl]

applied 361726

lib/Transforms/Utils/SimplifyCFG.cpp

   if (isSwitchDense(Values))
     return false;
 
   // First, transform the values such that they start at zero and ascend.
   int64_t Base = Values[0];
   for (auto &V : Values)
     V -= (uint64_t)(Base);
 
-  // Now we have signed numbers that have been shifted so that, given enough
-  // precision, there are no negative values. Since the rest of the transform
-  // is bitwise only, we switch now to an unsigned representation.
-  uint64_t GCD = 0;
-  for (auto &V : Values)
-    GCD = GreatestCommonDivisor64(GCD, (uint64_t)V);
-
   // This transform can be done speculatively because it is so cheap - it results
-  // in a single rotate operation being inserted. This can only happen if the
-  // factor extracted is a power of 2.
-  // FIXME: If the GCD is an odd number we can multiply by the multiplicative
-  // inverse of GCD and then perform this transform.
+  // in a single rotate operation being inserted.
   // FIXME: It's possible that optimizing a switch on powers of two might also
   // be beneficial - flag values are often powers of two and we could use a CLZ
   // as the key function.
-  if (GCD <= 1 || !isPowerOf2_64(GCD))
-    // No common divisor found or too expensive to compute key function.
-    return false;
 
-  unsigned Shift = Log2_64(GCD);
-  for (auto &V : Values)
-    V = (int64_t)((uint64_t)V >> Shift);
+  unsigned Shift = 64;
+  for (auto &V : Values) {
+    // There is no edge condition when the BitWidth is less than 64, because if
+    // 0 is the only value then a shift does nothing, and LLVM requires
+    // well-formed IR to not have duplicate cases.
+    unsigned TZ = countTrailingZeros((uint64_t)V);
+    if (TZ < Shift) {
+      Shift = TZ;
+      if (Shift == 0)
+        break;
+    }
+  }
+  if (Shift) {
+    for (auto &V : Values)
+      V = V >> Shift;
+  }
 
   if (!isSwitchDense(Values))
     // Transform didn't create a dense switch.
     return false;
 
   // The obvious transform is to shift the switch condition right and emit a
   // check that the condition actually cleanly divided by GCD, i.e.
   //   C & (1 << Shift - 1) == 0