This is an archive of the discontinued LLVM Phabricator instance.

[SCEV] Generalize folding of trunc(x)+n*trunc(y) into folding m*trunc(x)+n*trunc(y)
ClosedPublic

Authored by dneilson on Sep 14 2017, 9:06 PM.

Details

Summary

A SCEV such as:
{%v2,+,((-1 * (trunc i64 (-1 * %v1) to i32)) + (-1 * (trunc i64 %v1 to i32)))}<%loop>

can be folded into, simply, {%v2,+,0}. However, the current code in ::getAddExpr()
will not try to apply the simplification m*trunc(x)+n*trunc(y) -> trunc(trunc(m)*x+trunc(n)*y)
because it only keys off having a non-multiplied trunc as the first term in the simplification.

This patch generalizes this code to try to do a more generic fold of these trunc
expressions.

Event Timeline

dneilson created this revision.Sep 14 2017, 9:06 PM
sanjoy requested changes to this revision.Sep 15 2017, 4:35 PM
sanjoy added inline comments.
lib/Analysis/ScalarEvolution.cpp
2346

This is doing a bit more work than it needs to -- if the first element after a constant isn't a trunc, then none of them are.

2365

Instead of searching from a trunc operation and going from there, how about phrasing this logic as:

  1. First figure out the SrcType, if possible (by looking at truncates and multiplies)
  2. If (1) was successful, re-traverse the operands and try to do the trunc extraction

This makes it clear that the second part is only using SrcType and not the whole truncate.

This revision now requires changes to proceed.Sep 15 2017, 4:35 PM
dneilson updated this revision to Diff 116013.Sep 20 2017, 9:27 AM
dneilson edited edge metadata.

Minor rearrangement of the patch to get srctype from the lambda instead of a trunc.
( Sorry for the delay; I was out of town & away from computers. )

sanjoy added inline comments.Sep 20 2017, 10:29 AM
lib/Analysis/ScalarEvolution.cpp
2351

I think we can rewrite this inner loop as:

auto *LastOp = Mul->getOperand(Mul->getNumOperands() - 1);
if (auto *T = dyn_cast<SCEVTruncateExpr>(LastOp))
  return T->getOperand()->getType();
if (!isa<SCEVConstant>(LastOp))
  break;

I think we can use this trick in the outer loop as well. If we just look at the last operand to the add then we'll miss (say) zero extend expressions etc. but that's fine because the loop that actually does the work will catch it. Here we just need to provide a quick "estimate".

What do you think?

dneilson added inline comments.Sep 20 2017, 10:48 AM
lib/Analysis/ScalarEvolution.cpp
2351

Sounds like a good idea to me. I wasn't aware that the operands of all SCEV expressions are sorted.

Should be able to apply this trick down below as well.

dneilson updated this revision to Diff 116050.Sep 20 2017, 12:06 PM

Rewrite lambda to exploit SCEV operand ordering.

sanjoy added inline comments.Sep 20 2017, 4:40 PM
lib/Analysis/ScalarEvolution.cpp
2350

I think this can just be:

if (auto *Mul = dyn_cast<SCEVMulExpr>(Ops[Idx]))
  if (auto *Trunc = dyn_cast<SCEVTruncateExpr>(Mul->getOperand(Mul->getNumOperands() - 1)))
    return Trunc->getOperand()->getType();
return nullptr;

The reasoning being we don't need to worry about mul expressions with the last operand as a constant -- these should have been folded away.

dneilson updated this revision to Diff 116243.Sep 21 2017, 12:08 PM

Remove the loop from the lambda.

sanjoy accepted this revision.Sep 21 2017, 11:00 PM

LGTM!

This revision is now accepted and ready to land.Sep 21 2017, 11:00 PM
This revision was automatically updated to reflect the committed changes.