Don't generate unnecessary signed ConstantRange during multiply

[pete]

Summary

Hi James

In r231483 you taught ConstantRange::multiply to be clever about signed vs unsigned ranges. For example, an unsigned range could be full-set while the signed range is more specific than that.

In looking at the allocations trace for LTO'ing verify-uselistorder, I see millions of allocations from APInt, many of which come from ConstantRange's.

This change tries to avoid some (3.2 million) allocations by returning the unsigned range if its suitable. The checks here are that it should not be a wrapping range, and should be positive. That should be enough to check for ranges such as [1, 10) which the signed range will be equal to, if we were to calculate it.

Thanks,
Pete

[jmolloy]

Hi Pete,

This makes sense to me!

James

[pete]

Thanks for the quick review! r271020.

Cheers,
Pete

[craig.topper]

Sorry to dredge this back up. But isn't that only ensuring the lower bound is positive? It doesn't guarantee anything about the upper bound. So I think we are returning full set for [-2, -2] * [0, 1] through the unsigned code and not even checking the signed range.

lib/IR/ConstantRange.cpp

                                             this_max * Other_max + 1);
   ConstantRange UR = Result_zext.truncate(getBitWidth());
 
+  // If the unsigned range doesn't wrap, and isn't negative then it's a range
+  // from one positive number to another which is as good as we can generate.
+  // In this case, skip the extra work of generating signed ranges which aren't
+  // going to be better than this range.
+  if (!UR.isWrappedSet() && UR.getLower().isNonNegative())
+    return UR;
+
   // Now the signed range. Because we could be dealing with negative numbers
   // here, the lower bound is the smallest of the cartesian product of the
   // lower and upper ranges; for example: