This is an archive of the discontinued LLVM Phabricator instance.

Enable ExitValue rewrite only when expansion cost is low.
ClosedPublic

Authored by wmi on May 15 2015, 1:56 PM.

Details

Summary

The patch is to enable ExitValue rewrite (In IndVarSimplify pass) only when the cost of expansion is low, just like LinearFunctionTestReplace does right now. The problem is described in https://llvm.org/bugs/show_bug.cgi?id=23538.

It includes these changes:

  1. Add an option. -replexitval=cheap is the default. -replexitval - Choose the strategy to replace exit value in IndVarSimplify =never - never replace exit value =cheap - only replace exit value when the cost is cheap =always - always replace exit value whenever possible
  1. The existing logic of SCEVExpander::isHighCostExpansionHelper is problematic. It cannot find out the udiv operator inside SCEVNAryExpr other than SCEVAddExpr. It doesn't check the sub SCEV inside SCEVTruncateExpr/SCEVZeroExtendExpr/SCEVSignExtendExpr. Like the SCEV: (-12 + (-12 * ((-12 + %len) /u 12)) + %len), SCEVExpander::isHighCostExpansionHelper will return false for it now. Fix the logic.

The patch improved an internal benchmark by 10%. It improved bzip2 in spec2000 by 1%.

Diff Detail

Repository
rL LLVM

Event Timeline

wmi updated this revision to Diff 25880.May 15 2015, 1:56 PM
wmi retitled this revision from to Enable ExitValue rewrite only when expansion cost is low..
wmi updated this object.
wmi edited the test plan for this revision. (Show Details)
wmi added reviewers: qcolombet, hfinkel, atrick.
wmi set the repository for this revision to rL LLVM.
wmi added subscribers: Unknown Object (MLST), davidxl.
hfinkel edited edge metadata.May 20 2015, 2:32 PM

Does this only apply when the loop otherwise has side effects? If the loop can be removed once the exit value is unused, maybe we should do it anyway?

lib/Transforms/Scalar/IndVarSimplify.cpp
633

No { } needed here.

wmi added a comment.May 20 2015, 3:38 PM

Does this only apply when the loop otherwise has side effects? If the loop can be removed once the exit value is unused, maybe we should do it anyway?

Yes, it makes sense, although it will increase the code complexity a little bit. I think it can be done like this: The loop can be removed only when all the phi nodes in exitBB with incoming values from the loop can be rewritten. We need to hold the transformations of all the phi in every ExitBB of the loop, get the information whether the loop can be removed, then do the transformation for all the phi in the end.

I will get a new patch to implement it.

In D9800#175987, @wmi wrote:

Does this only apply when the loop otherwise has side effects? If the loop can be removed once the exit value is unused, maybe we should do it anyway?

Yes, it makes sense, although it will increase the code complexity a little bit. I think it can be done like this: The loop can be removed only when all the phi nodes in exitBB with incoming values from the loop can be rewritten. We need to hold the transformations of all the phi in every ExitBB of the loop, get the information whether the loop can be removed, then do the transformation for all the phi in the end.

I will get a new patch to implement it.

Great! Do you also need to check the loops for instructions with side effects?

wmi added a comment.May 20 2015, 4:09 PM
In D9800#175987, @wmi wrote:

Does this only apply when the loop otherwise has side effects? If the loop can be removed once the exit value is unused, maybe we should do it anyway?

Yes, it makes sense, although it will increase the code complexity a little bit. I think it can be done like this: The loop can be removed only when all the phi nodes in exitBB with incoming values from the loop can be rewritten. We need to hold the transformations of all the phi in every ExitBB of the loop, get the information whether the loop can be removed, then do the transformation for all the phi in the end.

I will get a new patch to implement it.

Great! Do you also need to check the loops for instructions with side effects?

Yes, it is needed. Thanks for reminding. I will check the existing legality check logic to remove a loop when it is dead.

wmi updated this revision to Diff 26625.May 27 2015, 12:36 PM
wmi edited edge metadata.

I updated the patch to enable aggressive exit value rewriting if the loop can be deleted after the rewrite.

Thanks,
Wei.

Thanks for continuing to work on this. A few comments below, and I'd like Andy to look at this.

lib/Transforms/Scalar/IndVarSimplify.cpp
718

Once LoopCanBeDel is false, it will never become true again. Please remove this variable and just 'return false' in all places where you set LoopCanBeDel to false.

740

incoming -> Incoming

atrick requested changes to this revision.May 27 2015, 9:16 PM
atrick edited edge metadata.

Nice work.

Please update you patch for trunk. You probably don't need LastPN.

IsLoopCanBeDel should be phrased "CanLoopBeDeleted". However, it's not just a query; it at least needs a very clear comment that it may hoist instructions into the preheader to facilitate the query.

As Hal pointed out, it's very important to return early from CanLoopBeDeleted. We should only scan all instructions in the loop if we know the loop can otherwise be deleted.

I'm curious why you needed to enable aggressive exit value replacement in four unit tests. Can your logic determine that the loops can be deleted in those cases?

This revision now requires changes to proceed.May 27 2015, 9:16 PM
wmi updated this revision to Diff 26704.May 28 2015, 10:44 AM
wmi edited edge metadata.

Hal and Andy, thanks for the helpful comments.

Once LoopCanBeDel is false, it will never become true again. Please remove this variable and just 'return false' in all places where you set LoopCanBeDel to false.

Done.

incoming -> Incoming

Done.

Please update you patch for trunk. You probably don't need LastPN.

Done.

IsLoopCanBeDel should be phrased "CanLoopBeDeleted". However, it's not just a query; it at least needs a very clear comment that it may hoist instructions into the preheader to facilitate the query.

I think it is fine to let later phase to do the LICM so I changed Loop::makeLoopInvariant to Loop::hasLoopInvariantOperands. CanLoopBeDeleted is a query only func now.

As Hal pointed out, it's very important to return early from CanLoopBeDeleted. We should only scan all instructions in the loop if we know the loop can otherwise be deleted.

Done.

I'm curious why you needed to enable aggressive exit value replacement in four unit tests. Can your logic determine that the loops can be deleted in those cases?

I changed the tests. Now aggressive exit value replacement is only enabled in test/Transforms/IndVarSimplify/lcssa-preservation.ll. That test is used to check IndVars preserves LCSSA form. I preserve the original test behavior by enabling aggressive exit value replacement. For other three tests, loops can be deleted.

Thanks,
Wei.

atrick accepted this revision.May 28 2015, 11:13 AM
atrick edited edge metadata.

LGTM

This revision is now accepted and ready to land.May 28 2015, 11:13 AM
This revision was automatically updated to reflect the committed changes.