This is an archive of the discontinued LLVM Phabricator instance.

[InstCombine] Extending InstructionSimplify
Needs ReviewPublic

Authored by opaparo on Dec 18 2017, 7:59 AM.

Details

Summary
  1. So far, InstructionSimplify would not approach OverflowingBinaryOperators and PossiblyExactOperators. If it have encountered one of these, it would simply give up, aborting the transformation. However, in some cases, these operators can be proven to be safe, and the transformation can carry on. I've added a function for each of the two types, determining whether they are safe or not. In this patch I've added support for all types of shifts.
  2. Added support for CastInst for specific cases.

Diff Detail

Repository
rL LLVM

Event Timeline

hfinkel added inline comments.Dec 19 2017, 1:22 AM
lib/Analysis/InstructionSimplify.cpp
3432

I'd prefer not to have these kinds of TODO comment. If you have specific ideas, that's good to mention, but comments that are essentially "TODO: Think about this more.", don't add much value.

Comments should also end with a period.

In any case, with a bit of refactoring, I think that you could handle this in a more-general way. There definitely are other cases that could be handled. Note that the implementation in ValueTracking of known bits for an add/sub is essentially:

unsigned BitWidth = KnownOut.getBitWidth();
KnownBits LHSKnown(BitWidth);
computeKnownBits(Op0, LHSKnown, Depth + 1, Q);
computeKnownBits(Op1, Known2, Depth + 1, Q);
KnownOut = KnownBits::computeForAddSub(Add, NSW, LHSKnown, Known2);

where the actual logic has been put in KnownBits::computeForAddSub (in lib/Support/KnownBits.cpp). To detect whether we can prove non-overflow, you could get the known bits of the operands, make the APInts larger, call KnownBits::computeForAddSub, and then see if the extended bits of the result are all known zero.

KnownBits::computeForAddSub is currently the only part of ValueTracking split out like that, but the same could be done for the code in computeKnownBitsMul and computeKnownBitsFromShiftOperator (or, more specifically, the relevant code in its caller) to handle mul and shifts.

opaparo updated this revision to Diff 127889.Dec 21 2017, 8:03 AM
  1. Generalized InstructionSimplify's IsSafeOverflowingBinaryOperator to handle 'add', 'sub' and 'mul' in addition to 'shl'. This was done by refactoring existing behavior out of InstCombine's internals into ValueTracking, so now both InstCombine and InstructionSimplify use it.
  2. Added tests to cover possible cases. For each OverflowingBinaryOperator ('shl', 'add', 'sub' and 'mul') I've created tests according to the Cartesian product of four factors: the op has the nuw flag, the op has the nsw flag, there actually is an unsigned overflow, there actually is a signed overflow. The key idea is to check that optimizations occur if and only if the overflow flag is absent or no overflow is guaranteed. also note that the file name had changed from select-bitext-bitwise-ops.ll to select-obo-peo-ops.ll to better reflect the nature of the tests it contains.
opaparo marked an inline comment as done.Dec 21 2017, 8:04 AM
sanjoy resigned from this revision.Jan 29 2022, 5:32 PM