Page MenuHomePhabricator

Handle resolvable branches in complete loop unroll heuristic.
ClosedPublic

Authored by mzolotukhin on Jun 2 2015, 6:23 PM.

Details

Summary

Resolving a branch allows us to ignore blocks that won't be executed, and thus make our estimate more accurate.
This patch is intended to be applied after D10205 (though it could be applied independently).

Diff Detail

Repository
rL LLVM

Event Timeline

mzolotukhin updated this revision to Diff 27021.Jun 2 2015, 6:23 PM
mzolotukhin retitled this revision from to Handle resolvable branches in complete loop unroll heuristic..
mzolotukhin updated this object.
mzolotukhin edited the test plan for this revision. (Show Details)
mzolotukhin added a reviewer: chandlerc.
mzolotukhin added a subscriber: Unknown Object (MLST).
mzolotukhin updated this revision to Diff 27090.Jun 3 2015, 9:53 PM
  • In two-operand instructions use simplified values only if both operands have the same base pointer (or don't have it at all).
chandlerc requested changes to this revision.Jun 4 2015, 5:19 PM
chandlerc edited edge metadata.

Totally the right direction, just some quick comments here. This patch will likely change some based on my comments in D10205 but these are independent issues.

lib/Transforms/Scalar/LoopUnrollPass.cpp
558–559 ↗(On Diff #27090)

I don't think the 'Cond' variable is buying you much.

I would also write the condition differently as the only null case is where we have no simplified value. The type must always be an int. So:

if (Constant *SimpleCond = SimplifiedValues.lookup(BI->getCondition())) {
  BBWorklist.insert(BI->getSuccessor(cast<ConstantInt>(SimpleCond)->isZero() ? 1 : 0));
565–568 ↗(On Diff #27090)

Same comment as above.

This revision now requires changes to proceed.Jun 4 2015, 5:19 PM
mzolotukhin updated this revision to Diff 27260.Jun 5 2015, 9:08 PM
mzolotukhin edited edge metadata.
  • Rebase.
  • Rename SCEVSimplify to simplifyInstWithSCEV in visitCmpInst.
  • Fallback to Base visitor if failed to constant fold (and only then call simplifyInstWithSCEV).
  • Rewrite conditional expression for adding successors.
mzolotukhin edited edge metadata.
  • Rebase on master.
chandlerc requested changes to this revision.Jul 14 2015, 2:59 PM
chandlerc edited edge metadata.

Looks really close, just need to sort out the offset simplification.

lib/Transforms/Scalar/LoopUnrollPass.cpp
387–389 ↗(On Diff #27479)

This doesn't really seem correct to me...

For example, multiplication such as "(B + X) * (B + Y)" does not simplify to "X * Y". Even addition doesn't simplify that way.

I think it would be more clear (and correct) to explicitly handle the math that simplifies here rather than trying to share a routine. Test for subtraction and that LHS and RHS are in the simplified addresses mapping. If they are, you can write a comment about how the base addresses cancel and the result is the CaonstantExpr difference of the offsets.

I don't think you really need to even think about falling through to the fancy InstSimplify logic here because you only can do anything when you have boring constant offsets.

456 ↗(On Diff #27479)

If you take my advice above, I would also inline the logic here. I'm not sure there is really going to be that much shared between the two when you're done. You can really *only* handle subtraction above, but here you can handle any comparison and really want to just fall back on the same logic.

597 ↗(On Diff #27479)

I would leave a hint in this comment that this is the fallback if we can't directly fold the successor above.

This revision now requires changes to proceed.Jul 14 2015, 2:59 PM
mzolotukhin edited edge metadata.

Address review remarks:

  • Add tests.
  • Remove simplifyUsingOffsets routine.
  • .. and rebase on the trunk.

Hi Chandler,

I updated the patch - does it look good now?

I decided not to handle operands in (Base+Offset) form in visitBinaryOperator for now, because I think we could get into troubles even if we only look at SUB (I'm concerned about possible overflow errors here). I think it's possible to do, but we can do it later if we ever need it.

Tests are also added to the patch now (mostly they are from D10208).

Thanks,
Michael

chandlerc accepted this revision.Jul 23 2015, 5:33 PM
chandlerc edited edge metadata.

This looks fantastic. Nit-picky indenting and layout below. Feel free to commit with that addressed.

lib/Transforms/Scalar/LoopUnrollPass.cpp
467–475 ↗(On Diff #29863)

I actually think its better to nest these. Because we're using fall-through to "continue trying", the early-exit is hard to spot here. It also will save some map lookups:

auto SimplifiedLHS = SimplifiedAddresses.find(LHS)
if (SimplifiedLHS != SimplifiedAddresses.end()) {
  auto SimplifiedRHS = SimplifiedAddresses.find(RHS);
  if (SimplifiedRHS != SimplifiedAddresses.end()) {
    SimplifiedAddress &LHSAddr = SimplifiedLHS->second;
    SimplifiedAddress &RHSAddr = SimplifiedRHS->second;
    if (LHSAddr.Base == RHSAddr.Base) {
      LHS = LHSAddr.Offset;
      ...
478–480 ↗(On Diff #29863)

If you're going to skip the middle {}s (which I'm fine with) skip the outer ones as well.

This revision is now accepted and ready to land.Jul 23 2015, 5:33 PM
This revision was automatically updated to reflect the committed changes.

Thanks, Chandler! It's committed.

Michael