Limit the number of phis in intptr/ptrint folding

[davidxl]

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.

[mzolotukhin]

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

Thanks,
Michael

[davidxl]

Done. Added comment.

[mzolotukhin]

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

[davidxl]

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

[mzolotukhin]

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

[davidxl]

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

David

llvm/trunk/lib/Transforms/InstCombine/InstCombinePHI.cpp

 #include "llvm/Analysis/Utils/Local.h"
 #include "llvm/Analysis/ValueTracking.h"
 #include "llvm/IR/PatternMatch.h"
 using namespace llvm;
 using namespace llvm::PatternMatch;
 
 #define DEBUG_TYPE "instcombine"
 
+static cl::opt<unsigned>
+MaxNumPhis("instcombine-max-num-phis", cl::init(512),
+           cl::desc("Maximum number phis to handle in intptr/ptrint folding"));
+
 /// The PHI arguments will be folded into a single operation with a PHI node
 /// as input. The debug location of the single operation will be the merged
 /// locations of the original PHI node arguments.
 void InstCombiner::PHIArgMergedDebugLoc(Instruction *Inst, PHINode &PN) {
   auto *FirstInst = cast<Instruction>(PN.getIncomingValue(0));
   Inst->setDebugLoc(FirstInst->getDebugLoc());
   // We do not expect a CallInst here, otherwise, N-way merging of DebugLoc
   // will be inefficient.
for (unsigned i = 0; i != PN.getNumIncomingValues(); ++i) {
     AvailablePtrVals.emplace_back(LoadI);
   }
 
   // Now search for a matching PHI
   auto *BB = PN.getParent();
   assert(AvailablePtrVals.size() == PN.getNumIncomingValues() &&
          "Not enough available ptr typed incoming values");
   PHINode *MatchingPtrPHI = nullptr;
+  unsigned NumPhis = 0;
   for (auto II = BB->begin(), EI = BasicBlock::iterator(BB->getFirstNonPHI());
-       II != EI; II++) {
+       II != EI; II++, NumPhis++) {
+    // FIXME: consider handling this in AggressiveInstCombine
+    if (NumPhis > MaxNumPhis)
+      return nullptr;
     PHINode *PtrPHI = dyn_cast<PHINode>(II);
     if (!PtrPHI || PtrPHI == &PN || PtrPHI->getType() != IntToPtr->getType())
       continue;
     MatchingPtrPHI = PtrPHI;
     for (unsigned i = 0; i != PtrPHI->getNumIncomingValues(); ++i) {
       if (AvailablePtrVals[i] !=
           PtrPHI->getIncomingValueForBlock(PN.getIncomingBlock(i))) {
         MatchingPtrPHI = nullptr;