Page MenuHomePhabricator

Reroll loops with multiple IV and negative step part 3/3 -- support multiple induction variables

Authored by hulx2000 on Jan 25 2016, 12:17 PM.


This patch enable loop reroll for the following case:
    for(int i=0;  i<N; i += 2) {
       S += *a++;
       S += *a++;

Diff Detail


Event Timeline

hulx2000 retitled this revision from to Reroll loops with multiple IV and negative step part 3/3 -- support multiple induction variables.
hulx2000 updated this object.
hulx2000 added reviewers: jmolloy, hfinkel.
hulx2000 set the repository for this revision to rL LLVM.
hulx2000 added a subscriber: llvm-commits.
hulx2000 added inline comments.Jan 25 2016, 4:37 PM
1433 ↗(On Diff #45899)

Empty line is not needed

1531 ↗(On Diff #45899)

Empty line is not needed

jmolloy requested changes to this revision.Feb 15 2016, 7:44 AM
jmolloy edited edge metadata.


I've got a bunch of comments - I think it'll be easier to review if you address these first, then I can continue to the end of the patch.


436 ↗(On Diff #45899)

I don't see the need for the "Only" here. Simply "LoopControlIV" ? (no need for "ctrl" instead of "control" - be verbose when possible).

440 ↗(On Diff #45899)

The name should include "branch" - like "isCompareUsedByBranch" or something.

It can also be made simpler:

bool isCompareUsedByBranch(Instruction *I) {
  auto *TI = I->getParent()->getTerminator();
  if (!isa<BranchInst>(TI) || !isa<CmpInst>(I))
    return false;
  return I->hasOneUse() && TI->getOperand(0) == I;
528 ↗(On Diff #45899)

Can't you just use InductionInfo::isInduction() here? You'd be looking for an induction with a step of 1 that is used by the loop latch. It seems this could remove a lot of code.

530 ↗(On Diff #45899)

Use "unsigned" here. There's no need to fix this to a specific bitwidth and no need for it to be signed.

531 ↗(On Diff #45899)

Please fold the ! inside the brackets for readability:

if (IVUses != 2 && IVUses != 1)
  return false;
538 ↗(On Diff #45899)


538 ↗(On Diff #45899)

isCompareInst doesn't handle nullptr. This should either use cast<Instruction>() or check that dyn_cast<Instruction>() is not nullptr.

541 ↗(On Diff #45899)

Same as line 531.

546 ↗(On Diff #45899)

You can fold these two if's together.

614 ↗(On Diff #45899)

No need for brackets: &*I.

1170 ↗(On Diff #45899)

This is really nasty. Please come up with a more concise way of expressing this.

(If you used InductionDescriptor to represent LoopControlIV, this should be fairly easy I think?)

This revision now requires changes to proceed.Feb 15 2016, 7:44 AM

Thanks, James.

Caught by tight release schedule again, will address your comment after freed up.

hulx2000 marked 12 inline comments as done.Mar 30 2016, 3:10 PM
hulx2000 added inline comments.
528 ↗(On Diff #45899)

Here I am checking if an induction PHI is only used to control loop iteration, no other uses such as A[i], normally, an Induction PHI will have other uses other than controlling loop iteration, e.g. Used as an index to access array.

So InductionDescriptor::isInductionPHI is not enough here.

1170 ↗(On Diff #45899)

Here I am trying to mark the Loop Control Only IV and it's related instructions such as increment, compare and branches as used, InductionDescriptor can't help much here.

And there seems no other way around it without adding more code, may be I could add more comments instead?

hulx2000 edited edge metadata.
hulx2000 marked an inline comment as done.

Hi, James:

Patch updated, could you please continue your review?

Thanks a lot.

Lawrence Hu

Hi Lawrence,

Sorry, I'll look at this tomorrow.



Thanks, James.

Did you get time on this?

Have a nice weekend.

Lawrence Hu

Thanks James for the update, have a a nice vacation then.

Hal, could you please find some time to review it then? I have another reroll patch pending on this, and I will transfer to another team in May 21st.

Have a nice day.

Lawrence HU

Thanks a lot Hal.


Lawrence Hu

hfinkel added inline comments.Apr 18 2016, 10:30 PM
167 ↗(On Diff #52138)

// For a loop with multiple induction variables, remember the one used only to control the loop.

513 ↗(On Diff #52138)

// Check if an IV is only used to control the loop. There are two cases:

514 ↗(On Diff #52138)

// 1. It has only one use which is the loop increment, and the increment is only used by the comparison and the PHI, and the comparison is used only by the branch.

516 ↗(On Diff #52138)

// 2. It is used only by the loop increment and the comparison, the loop increment is only used by the PHI, and the comparison is used only by the branch.

534 ↗(On Diff #52138)

be the loop increment

535 ↗(On Diff #52138)

The loop increment

544 ↗(On Diff #52138)

// The users of the IV must be a binary operation or a comparison.

1152 ↗(On Diff #52138)

// Make sure we mark loop-control-only PHIs as used in all iterations. See comment above LoopReroll::isLoopControlIV for more information.

[Don't repeat the comment text from above LoopReroll::isLoopControlIV here.]

1170 ↗(On Diff #52138)

You don't need the parenthesis around UUser->user_begin() - '->' has higher precedence than '*'.

1171 ↗(On Diff #52138)

Do you need, or intend, the dyn_cast here? I think you don't, because you don't want the condition to be true if both sides are nullptr.

1435 ↗(On Diff #52138)

non-loop-control IVs

1451 ↗(On Diff #52138)

assert(COp && "Didn't find constant operand of LoopInc!");

1455 ↗(On Diff #52138)

It does not look like there are test cases covering this logic, please add some.

hulx2000 marked 13 inline comments as done.Apr 20 2016, 12:17 PM
hulx2000 edited edge metadata.

Hi, Hal.

Thanks a lot for reviewing, patch updated.

hfinkel accepted this revision.Apr 26 2016, 9:14 AM
hfinkel edited edge metadata.


166 ↗(On Diff #54400)

variable -> variables

jmolloy accepted this revision.Apr 27 2016, 11:29 PM
jmolloy edited edge metadata.

Hi Lawrence,

Hal's happy so I'm happy.



This revision is now accepted and ready to land.Apr 27 2016, 11:29 PM
This revision was automatically updated to reflect the committed changes.