Page MenuHomePhabricator

Limit the number of phis in intptr/ptrint folding
ClosedPublic

Authored by davidxl on May 17 2018, 12:05 PM.

Details

Summary

In rare cases when there are thousands of single use phis in a BB, the phi folding simplification can take excessive amount of time. Add an option to control the limit. Mostly NFC.

Diff Detail

Repository
rL LLVM

Event Timeline

davidxl created this revision.May 17 2018, 12:05 PM
mzolotukhin accepted this revision.May 17 2018, 12:13 PM

Do you mind adding a TODO note describing the problem and another way to fix it? Otherwise, LGTM.

Thanks,
Michael

This revision is now accepted and ready to land.May 17 2018, 12:13 PM

Done. Added comment.

This revision was automatically updated to reflect the committed changes.

Hi David,

Unfortunately, this change doesn't help the testcase we have, so there should be more issues with this. Do you have other ideas how it can be fixed (the script I sent earlier still exposes an issue)? Instruments show that the most time is currently spent in Use::getUser().

Thanks,
Michael

My profile shows that with the 20000 phi case, the cycles are cut in half
with the limit.

The remaining problem is in : [.] llvm::BasicBlock::getFirstNonPHI

I guess a short fix would be to have a customized version of getFirstNonPhi
which returns an 'end' if the limit is reached. You can try if that works
for you.

thanks,

David

I thought about this transformation more, and I no longer think that we even need to move it to aggressive-instcombine (or another FunctionPass). What we need is to just change it from top-down to bottom-up: i.e. to start looking not from phi-nodes, but rather from inttoptr instructions. That is, the algorithm would look like:

visitIntToPtr(Instruction &I) {
  Value *Def = I.getOperand()
  if (!Def.hasSingleUse())
     return;
  if (isa<PtrToInt>(Def)) {   // Simple case without phi - it's probably already handled somewhere else, but I'm putting it here for completeness
     I.replaceAllUsesWith(Def.getOperand());
  }
  if (isa<PHINode>(Def)) {    // Interesting case where we have a phi-node
     if (all operands are PtrToInt with a single use) {
       NewPHI = RewritePHI();
       I.replaceAllUsesWith(NewPHI);
    }
  }
}

What do you think? Would it work?

PS: Internally we worked around the slowdown, so it's not pressing on us anymore.

Michael

This might work and existing test cases should be able to make sure the
behavior is not regressed.

David