[FuncSpec] Add Phi nodes to the InstCostVisitor.

[labrinea]

Summary

This patch allows constant folding of PHIs when estimating the user bonus. Phi
nodes are a special case since some of their inputs may remain unresolved until
all the specialization arguments have been processed by the InstCostVisitor.
Therefore, we keep a list of dead basic blocks and then lazily visit the Phi nodes
once the user bonus has been computed for all the specialization arguments.

[ChuanqiXu]

The motivation of the patch looks a little bit odd to me.

Given:

a:
  br label %merge

b:
  br label %merge

merge:
  %p = phi i32 [%arg0, %a], [%non_constant, %b]

Given %arg0 may be constant , I don't think the information implies (any) benefits with function specialization. Because after the transformation, %p won't be constant still.

I know there is an optimization (may be aggressive JumpThreading?) to optimize the case:

a:
  br label %merge

b:
  br label %merge

merge:
  %p = phi i32 [%constant, %a], [%non_constant, %b]
  use of %p
  goto successors

to

a:
  br label %merge.a

b:
  br label %merge

merge:
  %p = phi i32  [%non_constant, %b]
  use of %p
  goto successors

merge.a:
   %p.a = %constant
   use of %constant
   goto copy of successors

But I am not sure if this is implemented in LLVM. Also it smells not good to make FS to dependent on such optimizations.

llvm/lib/Transforms/IPO/FunctionSpecialization.cpp

127–128

What's the semantics of DeadBlocks here? Why would we add BB to DeadBlocks? It looks odd to me since it implies that estimating basic blocks will mark these blocks as dead.

275–277

Maybe it is slightly better to alert the findConstantFor .

[ChuanqiXu]

llvm/lib/Transforms/IPO/FunctionSpecialization.cpp

184–186

This smells not good. It looks dangerous that the LastVisited may be invalid.

278–280

What's the semantics for PendingPHIs here? It looks like a set of PHIs which would be constant but we don't know its values. But if it is this case, why can we insert the non-const and visited PHIs to PendingPHIs? It looks odd.

284

Also I am curious why can we treat the PHI as constant with one of its incoming value? That doesn't make sense to me.

[labrinea]

In D154852#4487493, @ChuanqiXu wrote:

The motivation of the patch looks a little bit odd to me.

Given:

a:
  br label %merge

b:
  br label %merge

merge:
  %p = phi i32 [%arg0, %a], [%non_constant, %b]

Given %arg0 may be constant , I don't think the information implies (any) benefits with function specialization. Because after the transformation, %p won't be constant still.

I know there is an optimization (may be aggressive JumpThreading?) to optimize the case:

a:
  br label %merge

b:
  br label %merge

merge:
  %p = phi i32 [%constant, %a], [%non_constant, %b]
  use of %p
  goto successors

to

a:
  br label %merge.a

b:
  br label %merge

merge:
  %p = phi i32  [%non_constant, %b]
  use of %p
  goto successors

merge.a:
   %p.a = %constant
   use of %constant
   goto copy of successors

But I am not sure if this is implemented in LLVM. Also it smells not good to make FS to dependent on such optimizations.

Apologies for the confusion, perhaps I need to add some comments explaining the intention. If not all the incoming values of a PHI node evaluate to the same constant then the PHI node cannot be folded.

llvm/lib/Transforms/IPO/FunctionSpecialization.cpp

127–128

This function is called when we constant fold switch instructions or conditional branches. It estimates the cost of instructions residing in dead blocks (unless they've already been estimated while constant folding).

184–186

The function getBonusFromPendingPHIs just above contains the only callsite to getUserBonus where nullptr is passed for the last two arguments. The key to a DenseMap cannot be nullptr. This isn't problematic as visitPHINode doesn't use LastVisited.

275–277

Ack

278–280

Pending PHIs are phi nodes we have visited once without successfully folding them to a constant value, so we want to repeat this once more after all the specialization arguments have been estimated by the InstCostVisitor. It is possible that a later argument makes a conditional branch unconditional, and consequently a basic block turns dead (if it has a unique predecessor). As a result one of the incoming values of the PHI can be disregarded for the evaluation of the PHI. I'll add a comment explaining this.

284

Const is initialized to nullptr. The first incoming value that is identified to be constant sets Const to that value. If the remaing incomign values have that same constant value then we can replace the PHI, otherwise we can't. The only exception is if the incoming value is coming from a basic block we have proved is dead, or if the incoming values is this PHI itself, in which cases we ingore (skip) that incoming value. Perhaps I need to add a comment with this explanation.

[labrinea]

llvm/lib/Transforms/IPO/FunctionSpecialization.cpp

273–274

I am wondering whether we should be checking DeadBlocks.contains(I.getIncomingBlock(Idx)). Imagine this scenario:

      x = 2
     /     \
    /    aliveBB
deadBB
    \     y = 3
     \     /
phi ( x , y )

The basic block where x is defined is alive, therefore we can't fold the PHI because x != y. Is it not a pessimization?

[labrinea]

• Fixed the bug with dead incoming basic blocks.
• Added a few comments.
• Rebased on D155177 (minor refactoring)

[labrinea]

Ping

[ChuanqiXu]

If not all the incoming values of a PHI node evaluate to the same constant then the PHI node cannot be folded.

Got it. Then it makes sense. Sorry for misreading.

llvm/lib/Transforms/IPO/FunctionSpecialization.cpp

110

Let's mention the semantics of DeadBlocks here.

127–128

I got it. The semantics is "these blocks are dead if we convert the visiting values to constant. (But we haven't decided we're going to transform them, right?)". It is still slightly odd for me. But I don't have a suggestion here.

184–186

I know it. I just feel the pattern is dangerous. For example, in all other visit* methods, we always assume the LastVisited is valid, but it won't be true after this patch. (Although it is not formally stated). The concern I had was that we broke the assumption here. And it is almost bad to broke some assumptions. I think the easy solution here may insert:

if (LastVisited == KnownConstants.end())
    return nullptr;

to many other visit* methods. And set LastVisited to KnownConstants.end() if the use and C is nullptr.

264–265

What's this insight for limitation? I don't feel the new algorithm is super time consuming.

273–274

I don't understand this. Given DeadBlocks contains deadBB and I.getIncomingBlock(Idx) for x returns deadBB, we won't consider the value from x, right? Then it doesn't matter if x != y. Do I understand correctly?

278–280

Got it. It makes sense now.

284

Oh, I got it. It makes sense.

790–796

Given getSpecializationBonus would do additional computations exposing inlining opportunities exposing inlining via indirect call promotion., (e.g., converting the call to a function ptr to a direct function call), it looks like we didn't compute these for pending PHIs.

While the current patch is self-contained, maybe we can add a TODO/FIXME here for future improvements.

[labrinea]

llvm/lib/Transforms/IPO/FunctionSpecialization.cpp

110

I'll improve the wording.

127–128

The DeadBlocks is a member of the InstCostVisitor, which by definition only estimates, does not transform itself. I'll make it clear on the description that here we are estimating the benefit to later decide whether we are going to make a transformation.

184–186

There are other visit methods which are already not using the LastVisited iterator like visitCallBase and visitGetElementPtrInst. I think the extra checks are expensive, perhaps we could do:

LastVisited = Use ? KnownConstants.insert({Use, C}).first : KnownConstants.end();

then inside the visit methods assert(LastVisited != KnownConstants.end())

264–265

There can be phi nodes with 64 incoming values or more, in which case it can be time consuming. We do need to early exit. I think 4 is a reasonable number.

273–274

Exactly. The previous revision was checking if (DeadBlocks.contains(Inst->getParent()), which was wrong.

790–796

As is, getSpecializationBonus only checks the specialization arguments (the root of the use-def chain) for inlining opportunities, not every single user of the use-def chain which might become constant. In that regard the pending PHIs are no different from the rest of the users that the InstCostVisitor is visiting through getUserBonus. Is this something we would like to change?

[ChuanqiXu]

llvm/lib/Transforms/IPO/FunctionSpecialization.cpp

184–186

Yeah, that sounds much better.

264–265

While I agree with you, it is better to make this an option. Then we reduce the magic number and have better semantics here even if we can image that there won't be so many people tuning on that.

790–796

I think at least it is a potential optimization opportunities. Then if we have a consensus on this, it looks not bad to leave a TODO/FIXME.

In that regard the pending PHIs are no different from the rest of the users that the InstCostVisitor is visiting through getUserBonus.

A difference I thought is that the PHIs are more possible to be a function pointers. (But now I don't think it is better to say "more possible" while both GEP and load instructions may get a constant too )

[labrinea]

• added an option to control the maximum number of incoming phi values
• added an assertion for the LastVisited iterator inside visit methods
• added a comment to explain the semantics of DeadBlocks

[labrinea]

llvm/lib/Transforms/IPO/FunctionSpecialization.cpp

790–796

In my opinion, I think it's better to add the FIXME under a separate commit, since it's not directly related to this patch as I've explained above.

[ChuanqiXu]

Thanks!

llvm/lib/Transforms/IPO/FunctionSpecialization.cpp

790–796

That's fine.

[raj.khem]

I am seeing a crash in libLLVM-17.so when compiling socat on aarch64 and have narrowed it down to this change. here is testcase
https://uclibc.org/~kraj/nestlex.zip

compiler cmdline is

aarch64-yoe-linux-clang -target aarch64-yoe-linux nestlex.i -c -O

results in
segmentation fault (core dumped) ../recipe-sysroot-native/usr/bin/aarch64-yoe-linux/aarch64-yoe-linux-clang

works ok on reverting this patch from 17.x release branch

here is stack trace

                Stack trace of thread 1747742:
                #0  0x00007f84b9e8eaa7 _ZN4llvm12hash_combineIJhhtNS_9hash_codeES1_PNS_4TypeEEEES1_DpRKT_ (libLLVM-17.so + 0xc8eaa7)
                #1  0x00007f84b9e9a3ae _ZN4llvm17ConstantUniqueMapINS_12ConstantExprEE11getOrCreateEPNS_4TypeENS_19ConstantExprKeyTypeE (libLLVM-17.so + 0xc9a3ae)
                #2  0x00007f84b9ea14e4 _ZN4llvm12ConstantExpr11getIntToPtrEPNS_8ConstantEPNS_4TypeEb (libLLVM-17.so + 0xca14e4)
                #3  0x00007f84bb4f3dcc _ZN12_GLOBAL__N_123SymbolicallyEvaluateGEPEPKN4llvm11GEPOperatorENS0_8ArrayRefIPNS0_8ConstantEEERKNS0_10DataLayoutEPKNS0_17TargetLibraryInfoE (libLLVM-
17.so + 0x22f3dcc)
                #4  0x00007f84bb4f44d3 _ZN12_GLOBAL__N_128ConstantFoldInstOperandsImplEPKN4llvm5ValueEjNS0_8ArrayRefIPNS0_8ConstantEEERKNS0_10DataLayoutEPKNS0_17TargetLibraryInfoE (libLLVM-1
7.so + 0x22f44d3)
                #5  0x00007f84bb1b6e37 _ZN4llvm15InstCostVisitor22visitGetElementPtrInstERNS_17GetElementPtrInstE (libLLVM-17.so + 0x1fb6e37)
                #6  0x00007f84bb1bb36b _ZN4llvm15InstCostVisitor12getUserBonusEPNS_11InstructionEPNS_5ValueEPNS_8ConstantE (libLLVM-17.so + 0x1fbb36b)
                #7  0x00007f84bb1bb711 _ZN4llvm15InstCostVisitor12getUserBonusEPNS_11InstructionEPNS_5ValueEPNS_8ConstantE (libLLVM-17.so + 0x1fbb711)
                #8  0x00007f84bb1bb711 _ZN4llvm15InstCostVisitor12getUserBonusEPNS_11InstructionEPNS_5ValueEPNS_8ConstantE (libLLVM-17.so + 0x1fbb711)
                #9  0x00007f84bb1bb711 _ZN4llvm15InstCostVisitor12getUserBonusEPNS_11InstructionEPNS_5ValueEPNS_8ConstantE (libLLVM-17.so + 0x1fbb711)
                #10 0x00007f84bb1bb711 _ZN4llvm15InstCostVisitor12getUserBonusEPNS_11InstructionEPNS_5ValueEPNS_8ConstantE (libLLVM-17.so + 0x1fbb711)
                #11 0x00007f84bb1bb711 _ZN4llvm15InstCostVisitor12getUserBonusEPNS_11InstructionEPNS_5ValueEPNS_8ConstantE (libLLVM-17.so + 0x1fbb711)
                #12 0x00007f84bb1bb711 _ZN4llvm15InstCostVisitor12getUserBonusEPNS_11InstructionEPNS_5ValueEPNS_8ConstantE (libLLVM-17.so + 0x1fbb711)
                #13 0x00007f84bb1bb711 _ZN4llvm15InstCostVisitor12getUserBonusEPNS_11InstructionEPNS_5ValueEPNS_8ConstantE (libLLVM-17.so + 0x1fbb711)
                #14 0x00007f84bb1bb711 _ZN4llvm15InstCostVisitor12getUserBonusEPNS_11InstructionEPNS_5ValueEPNS_8ConstantE (libLLVM-17.so + 0x1fbb711)
                #15 0x00007f84bb1bb711 _ZN4llvm15InstCostVisitor12getUserBonusEPNS_11InstructionEPNS_5ValueEPNS_8ConstantE (libLLVM-17.so + 0x1fbb711)

[labrinea]

Thanks. Reverted. Looks like an infinite loop.

[raj.khem]

In D154852#4534868, @labrinea wrote:

Thanks. Reverted. Looks like an infinite loop.

thank you. Can you also revert it on release/17.x branch as well please ?

[labrinea]

In D154852#4535442, @raj.khem wrote:

In D154852#4534868, @labrinea wrote:

Thanks. Reverted. Looks like an infinite loop.

thank you. Can you also revert it on release/17.x branch as well please ?

Will do.

[labrinea]

Fixes the infinite loop in getUserBonus.

[labrinea]

The assertion "Found circle" fails.

[labrinea]

Turned the "found circle" assertion in getUserBonus into early exit.

[ChuanqiXu]

Maybe it is a good idea to add a test case for the circle issue?

[dyung]

@labrinea the test you added seems to be failing on several bots. Can you take a look and revert if you need time to investigate?

https://lab.llvm.org/buildbot/#/builders/216/builds/24650
https://lab.llvm.org/buildbot/#/builders/247/builds/7037
https://lab.llvm.org/buildbot/#/builders/139/builds/46259

[vvereschaka]

Hi @labrinea

the same problem with the following builders:

• https://lab.llvm.org/buildbot/#/builders/235/builds/975
• https://lab.llvm.org/buildbot/#/builders/58/builds/42553
• https://lab.llvm.org/buildbot/#/builders/58/builds/42553

and few others ...

******************** TEST 'LLVM-Unit :: Transforms/IPO/./IPOTests/11/12' FAILED ********************
Script(shard):
--
GTEST_OUTPUT=json:/home/buildbot/as-builder-4/lld-x86_64-ubuntu-fast/build/unittests/Transforms/IPO/./IPOTests-LLVM-Unit-1080736-11-12.json GTEST_SHUFFLE=0 GTEST_TOTAL_SHARDS=12 GTEST_SHARD_INDEX=11 /home/buildbot/as-builder-4/lld-x86_64-ubuntu-fast/build/unittests/Transforms/IPO/./IPOTests
--
Script:
--
/home/buildbot/as-builder-4/lld-x86_64-ubuntu-fast/build/unittests/Transforms/IPO/./IPOTests --gtest_filter=FunctionSpecializationTest.PhiNode
--
/home/buildbot/as-builder-4/lld-x86_64-ubuntu-fast/llvm-project/llvm/unittests/Transforms/IPO/FunctionSpecializationTest.cpp:358: Failure
Expected equality of these values:
  Bonus
    Which is: 0
  Ref
    Which is: 2014
/home/buildbot/as-builder-4/lld-x86_64-ubuntu-fast/llvm-project/llvm/unittests/Transforms/IPO/FunctionSpecializationTest.cpp:359: Failure
Value of: Bonus > 0
  Actual: false
Expected: true
/home/buildbot/as-builder-4/lld-x86_64-ubuntu-fast/llvm-project/llvm/unittests/Transforms/IPO/FunctionSpecializationTest.cpp:358
Expected equality of these values:
  Bonus
    Which is: 0
  Ref
    Which is: 2014
/home/buildbot/as-builder-4/lld-x86_64-ubuntu-fast/llvm-project/llvm/unittests/Transforms/IPO/FunctionSpecializationTest.cpp:359
Value of: Bonus > 0
  Actual: false
Expected: true
********************

[phosek]

We also see the same test failure on Windows:

Script:
--
C:\b\s\w\ir\x\w\llvm_build\unittests\Transforms\IPO\.\IPOTests.exe --gtest_filter=FunctionSpecializationTest.PhiNode
--
C:\b\s\w\ir\x\w\llvm-llvm-project\llvm\unittests\Transforms\IPO\FunctionSpecializationTest.cpp:358
Expected equality of these values:
  Bonus
    Which is: 0
  Ref
    Which is: 2014
C:\b\s\w\ir\x\w\llvm-llvm-project\llvm\unittests\Transforms\IPO\FunctionSpecializationTest.cpp:359
Value of: Bonus > 0
  Actual: false
Expected: true

[labrinea]

The previous revision was sensitive to the order getSpecializationBonus was evaluated in the unittest.
Specifically I was under the assumption that the expression

Specializer.getSpecializationBonus(F->getArg(0), One, Visitor) +
Specializer.getSpecializationBonus(F->getArg(1), One, Visitor) +
Specializer.getSpecializationBonus(F->getArg(2), One, Visitor)

would evaluate in order, but it depends on the target, so it has an effect on the resulting value.

llvm/include/llvm/Transforms/IPO/FunctionSpecialization.h

 
 class InstCostVisitor : public InstVisitor<InstCostVisitor, Constant *> {
   const DataLayout &DL;
   BlockFrequencyInfo &BFI;
   TargetTransformInfo &TTI;
   SCCPSolver &Solver;
 
   ConstMap KnownConstants;
+  // Basic blocks known to be unreachable after constant propagation.
+  DenseSet<BasicBlock *> DeadBlocks;
+  // PHI nodes we have visited before.
+  DenseSet<Instruction *> VisitedPHIs;
+  // PHI nodes we have visited once without successfully constant folding them.
+  // Once the InstCostVisitor has processed all the specialization arguments,
+  // it should be possible to determine whether those PHIs can be folded
+  // (some of their incoming values may have become constant or dead).
+  SmallVector<Instruction *> PendingPHIs;
 
   ConstMap::iterator LastVisited;
 
 public:
   InstCostVisitor(const DataLayout &DL, BlockFrequencyInfo &BFI,
                   TargetTransformInfo &TTI, SCCPSolver &Solver)
       : DL(DL), BFI(BFI), TTI(TTI), Solver(Solver) {}
 
-  Cost getUserBonus(Instruction *User, Value *Use, Constant *C);
+  bool isBlockExecutable(BasicBlock *BB) {
+    return Solver.isBlockExecutable(BB) && !DeadBlocks.contains(BB);
+  }
+
+  Cost getUserBonus(Instruction *User, Value *Use = nullptr,
+                    Constant *C = nullptr);
+
+  Cost getBonusFromPendingPHIs();
 
 private:
   friend class InstVisitor<InstCostVisitor, Constant *>;
 
   Cost estimateSwitchInst(SwitchInst &I);
   Cost estimateBranchInst(BranchInst &I);
 
   Constant *visitInstruction(Instruction &I) { return nullptr; }
+  Constant *visitPHINode(PHINode &I);
   Constant *visitFreezeInst(FreezeInst &I);
   Constant *visitCallBase(CallBase &I);
   Constant *visitLoadInst(LoadInst &I);
   Constant *visitGetElementPtrInst(GetElementPtrInst &I);
   Constant *visitSelectInst(SelectInst &I);
   Constant *visitCastInst(CastInst &I);
   Constant *visitCmpInst(CmpInst &I);
   Constant *visitUnaryOperator(UnaryOperator &I);

llvm/lib/Transforms/IPO/FunctionSpecialization.cpp

static cl::opt<bool> ForceSpecialization(
     "Force function specialization for every call site with a constant "
     "argument"));
 
 static cl::opt<unsigned> MaxClones(
     "funcspec-max-clones", cl::init(3), cl::Hidden, cl::desc(
     "The maximum number of clones allowed for a single function "
     "specialization"));
 
+static cl::opt<unsigned> MaxIncomingPhiValues(
+    "funcspec-max-incoming-phi-values", cl::init(4), cl::Hidden, cl::desc(
+    "The maximum number of incoming values a PHI node can have to be "
+    "considered during the specialization bonus estimation"));
+
 static cl::opt<unsigned> MinFunctionSize(
     "funcspec-min-function-size", cl::init(100), cl::Hidden, cl::desc(
     "Don't specialize functions that have less than this number of "
     "instructions"));
 
 static cl::opt<bool> SpecializeOnAddress(
     "funcspec-on-address", cl::init(false), cl::Hidden, cl::desc(
     "Enable function specialization on the address of global values"));
 
 // Disabled by default as it can significantly increase compilation times.
 //
 // https://llvm-compile-time-tracker.com
 // https://github.com/nikic/llvm-compile-time-tracker
 static cl::opt<bool> SpecializeLiteralConstant(
     "funcspec-for-literal-constant", cl::init(false), cl::Hidden, cl::desc(
     "Enable specialization of functions that take a literal constant as an "
     "argument"));
 
 // Estimates the instruction cost of all the basic blocks in \p WorkList.
 // The successors of such blocks are added to the list as long as they are
 // executable and they have a unique predecessor. \p WorkList represents
 // the basic blocks of a specialization which become dead once we replace
 // instructions that are known to be constants. The aim here is to estimate
 // the combination of size and latency savings in comparison to the non
 // specialized version of the function.
 static Cost estimateBasicBlocks(SmallVectorImpl<BasicBlock *> &WorkList,
+                                DenseSet<BasicBlock *> &DeadBlocks,
                                 ConstMap &KnownConstants, SCCPSolver &Solver,
                                 BlockFrequencyInfo &BFI,
                                 TargetTransformInfo &TTI) {
   Cost Bonus = 0;
 
   // Accumulate the instruction cost of each basic block weighted by frequency.
   while (!WorkList.empty()) {
     BasicBlock *BB = WorkList.pop_back_val();
 
     uint64_t Weight = BFI.getBlockFreq(BB).getFrequency() /
                       BFI.getEntryFreq();
     if (!Weight)
       continue;
 
+    // These blocks are considered dead as far as the InstCostVisitor
+    // is concerned. They haven't been proven dead yet by the Solver,
+    // but may become if we propagate the specialization arguments.
+    if (!DeadBlocks.insert(BB).second)
+      continue;
+
     for (Instruction &I : *BB) {
       // Disregard SSA copies.
       if (auto *II = dyn_cast<IntrinsicInst>(&I))
         if (II->getIntrinsicID() == Intrinsic::ssa_copy)
           continue;
       // If it's a known constant we have already accounted for it.
       if (KnownConstants.contains(&I))
         continue;

 static Constant *findConstantFor(Value *V, ConstMap &KnownConstants) {
   if (auto *C = dyn_cast<Constant>(V))
     return C;
   if (auto It = KnownConstants.find(V); It != KnownConstants.end())
     return It->second;
   return nullptr;
 }
 
+Cost InstCostVisitor::getBonusFromPendingPHIs() {
+  Cost Bonus = 0;
+  while (!PendingPHIs.empty()) {
+    Instruction *Phi = PendingPHIs.pop_back_val();
+    // The pending PHIs could have been proven dead by now.
+    if (isBlockExecutable(Phi->getParent()))
+      Bonus += getUserBonus(Phi);
+  }
+  return Bonus;
+}
+
 Cost InstCostVisitor::getUserBonus(Instruction *User, Value *Use, Constant *C) {
+  // We have already propagated a constant for this user.
+  if (KnownConstants.contains(User))
+    return 0;
+
   // Cache the iterator before visiting.
-  LastVisited = KnownConstants.insert({Use, C}).first;
+  LastVisited = Use ? KnownConstants.insert({Use, C}).first
+                    : KnownConstants.end();
 
   if (auto *I = dyn_cast<SwitchInst>(User))
     return estimateSwitchInst(*I);
 
   if (auto *I = dyn_cast<BranchInst>(User))
     return estimateBranchInst(*I);
 
   C = visit(*User);
   if (!C)
Cost InstCostVisitor::getUserBonus(Instruction *User, Value *Use, Constant *C) {
   Cost Bonus = Weight *
       TTI.getInstructionCost(User, TargetTransformInfo::TCK_SizeAndLatency);
 
   LLVM_DEBUG(dbgs() << "FnSpecialization:     Bonus " << Bonus
                     << " for user " << *User << "\n");
 
   for (auto *U : User->users())
     if (auto *UI = dyn_cast<Instruction>(U))
-      if (Solver.isBlockExecutable(UI->getParent()))
+      if (UI != User && isBlockExecutable(UI->getParent()))
         Bonus += getUserBonus(UI, User, C);
 
   return Bonus;
 }
 
 Cost InstCostVisitor::estimateSwitchInst(SwitchInst &I) {
+  assert(LastVisited != KnownConstants.end() && "Invalid iterator!");
+
   if (I.getCondition() != LastVisited->first)
     return 0;
 
   auto *C = dyn_cast<ConstantInt>(LastVisited->second);
   if (!C)
     return 0;
 
   BasicBlock *Succ = I.findCaseValue(C)->getCaseSuccessor();
   // Initialize the worklist with the dead basic blocks. These are the
   // destination labels which are different from the one corresponding
   // to \p C. They should be executable and have a unique predecessor.
   SmallVector<BasicBlock *> WorkList;
   for (const auto &Case : I.cases()) {
     BasicBlock *BB = Case.getCaseSuccessor();
     if (BB == Succ || !Solver.isBlockExecutable(BB) ||
         BB->getUniquePredecessor() != I.getParent())
       continue;
     WorkList.push_back(BB);
   }
 
-  return estimateBasicBlocks(WorkList, KnownConstants, Solver, BFI, TTI);
+  return estimateBasicBlocks(WorkList, DeadBlocks, KnownConstants, Solver, BFI,
+                             TTI);
 }
 
 Cost InstCostVisitor::estimateBranchInst(BranchInst &I) {
+  assert(LastVisited != KnownConstants.end() && "Invalid iterator!");
+
   if (I.getCondition() != LastVisited->first)
     return 0;
 
   BasicBlock *Succ = I.getSuccessor(LastVisited->second->isOneValue());
   // Initialize the worklist with the dead successor as long as
   // it is executable and has a unique predecessor.
   SmallVector<BasicBlock *> WorkList;
   if (Solver.isBlockExecutable(Succ) &&
       Succ->getUniquePredecessor() == I.getParent())
     WorkList.push_back(Succ);
 
-  return estimateBasicBlocks(WorkList, KnownConstants, Solver, BFI, TTI);
+  return estimateBasicBlocks(WorkList, DeadBlocks, KnownConstants, Solver, BFI,
+                             TTI);
+}
+
+Constant *InstCostVisitor::visitPHINode(PHINode &I) {
+  if (I.getNumIncomingValues() > MaxIncomingPhiValues)
+    return nullptr;
+
+  bool Inserted = VisitedPHIs.insert(&I).second;
+  Constant *Const = nullptr;
+
+  for (unsigned Idx = 0, E = I.getNumIncomingValues(); Idx != E; ++Idx) {
+    Value *V = I.getIncomingValue(Idx);
+    if (auto *Inst = dyn_cast<Instruction>(V))
+      if (Inst == &I || DeadBlocks.contains(I.getIncomingBlock(Idx)))
+        continue;
+    Constant *C = findConstantFor(V, KnownConstants);
+    if (!C) {
+      if (Inserted)
+        PendingPHIs.push_back(&I);
+      return nullptr;
+    }
+    if (!Const)
+      Const = C;
+    else if (C != Const)
+      return nullptr;
+  }
+  return Const;
 }
 
 Constant *InstCostVisitor::visitFreezeInst(FreezeInst &I) {
+  assert(LastVisited != KnownConstants.end() && "Invalid iterator!");
+
   if (isGuaranteedNotToBeUndefOrPoison(LastVisited->second))
     return LastVisited->second;
   return nullptr;
 }
 
 Constant *InstCostVisitor::visitCallBase(CallBase &I) {
   Function *F = I.getCalledFunction();
   if (!F || !canConstantFoldCallTo(&I, F))
for (unsigned Idx = 0, E = I.getNumOperands() - 1; Idx != E; ++Idx) {
     Operands.push_back(C);
   }
 
   auto Ops = ArrayRef(Operands.begin(), Operands.end());
   return ConstantFoldCall(&I, F, Ops);
 }
 
 Constant *InstCostVisitor::visitLoadInst(LoadInst &I) {
+  assert(LastVisited != KnownConstants.end() && "Invalid iterator!");
+
   if (isa<ConstantPointerNull>(LastVisited->second))
     return nullptr;
   return ConstantFoldLoadFromConstPtr(LastVisited->second, I.getType(), DL);
 }
 
 Constant *InstCostVisitor::visitGetElementPtrInst(GetElementPtrInst &I) {
   SmallVector<Constant *, 8> Operands;
   Operands.reserve(I.getNumOperands());
 
   for (unsigned Idx = 0, E = I.getNumOperands(); Idx != E; ++Idx) {
     Value *V = I.getOperand(Idx);
     Constant *C = findConstantFor(V, KnownConstants);
     if (!C)
       return nullptr;
     Operands.push_back(C);
   }
 
   auto Ops = ArrayRef(Operands.begin(), Operands.end());
   return ConstantFoldInstOperands(&I, Ops, DL);
 }
 
 Constant *InstCostVisitor::visitSelectInst(SelectInst &I) {
+  assert(LastVisited != KnownConstants.end() && "Invalid iterator!");
+
   if (I.getCondition() != LastVisited->first)
     return nullptr;
 
   Value *V = LastVisited->second->isZeroValue() ? I.getFalseValue()
                                                 : I.getTrueValue();
   Constant *C = findConstantFor(V, KnownConstants);
   return C;
 }
 
 Constant *InstCostVisitor::visitCastInst(CastInst &I) {
   return ConstantFoldCastOperand(I.getOpcode(), LastVisited->second,
                                  I.getType(), DL);
 }
 
 Constant *InstCostVisitor::visitCmpInst(CmpInst &I) {
+  assert(LastVisited != KnownConstants.end() && "Invalid iterator!");
+
   bool Swap = I.getOperand(1) == LastVisited->first;
   Value *V = Swap ? I.getOperand(0) : I.getOperand(1);
   Constant *Other = findConstantFor(V, KnownConstants);
   if (!Other)
     return nullptr;
 
   Constant *Const = LastVisited->second;
   return Swap ?
         ConstantFoldCompareInstOperands(I.getPredicate(), Other, Const, DL)
       : ConstantFoldCompareInstOperands(I.getPredicate(), Const, Other, DL);
 }
 
 Constant *InstCostVisitor::visitUnaryOperator(UnaryOperator &I) {
+  assert(LastVisited != KnownConstants.end() && "Invalid iterator!");
+
   return ConstantFoldUnaryOpOperand(I.getOpcode(), LastVisited->second, DL);
 }
 
 Constant *InstCostVisitor::visitBinaryOperator(BinaryOperator &I) {
+  assert(LastVisited != KnownConstants.end() && "Invalid iterator!");
+
   bool Swap = I.getOperand(1) == LastVisited->first;
   Value *V = Swap ? I.getOperand(0) : I.getOperand(1);
   Constant *Other = findConstantFor(V, KnownConstants);
   if (!Other)
     return nullptr;
 
   Constant *Const = LastVisited->second;
   return dyn_cast_or_null<Constant>(Swap ?
if (auto It = UniqueSpecs.find(S); It != UniqueSpecs.end()) {
       // functions. Hence we don't rewrite the call directly, but match it with
       // the best specialisation once all specialisations are known.
       if (CS.getFunction() == F)
         continue;
       const unsigned Index = It->second;
       AllSpecs[Index].CallSites.push_back(&CS);
     } else {
       // Calculate the specialisation gain.
-      Cost Score = 0 - SpecCost;
+      Cost Score = 0;
       InstCostVisitor Visitor = getInstCostVisitorFor(F);
       for (ArgInfo &A : S.Args)
         Score += getSpecializationBonus(A.Formal, A.Actual, Visitor);
+      Score += Visitor.getBonusFromPendingPHIs();
+
+      LLVM_DEBUG(dbgs() << "FnSpecialization: Specialization score = "
+                        << Score << "\n");
 
       // Discard unprofitable specialisations.
-      if (!ForceSpecialization && Score <= 0)
+      if (!ForceSpecialization && Score <= SpecCost)
         continue;
 
       // Create a new specialisation entry.
       auto &Spec = AllSpecs.emplace_back(F, S, Score);
       if (CS.getFunction() != F)
         Spec.CallSites.push_back(&CS);
       const unsigned Index = AllSpecs.size() - 1;
       UniqueSpecs[S] = Index;

 Cost FunctionSpecializer::getSpecializationBonus(Argument *A, Constant *C,
                                                  InstCostVisitor &Visitor) {
   LLVM_DEBUG(dbgs() << "FnSpecialization: Analysing bonus for constant: "
                     << C->getNameOrAsOperand() << "\n");
 
   Cost TotalCost = 0;
   for (auto *U : A->users())
     if (auto *UI = dyn_cast<Instruction>(U))
-      if (Solver.isBlockExecutable(UI->getParent()))
+      if (Visitor.isBlockExecutable(UI->getParent()))
         TotalCost += Visitor.getUserBonus(UI, A, C);
 
   LLVM_DEBUG(dbgs() << "FnSpecialization:   Accumulated user bonus "
                     << TotalCost << " for argument " << *A << "\n");
 
   // The below heuristic is only concerned with exposing inlining
   // opportunities via indirect call promotion. If the argument is not a
   // (potentially casted) function pointer, give up.

llvm/unittests/Transforms/IPO/FunctionSpecializationTest.cpp

Ref = getInstCost(Gep) + getInstCost(Load) + getInstCost(Freeze) +
         getInstCost(Smax);
   Bonus = Specializer.getSpecializationBonus(F->getArg(2), GV, Visitor);
   EXPECT_EQ(Bonus, Ref);
   EXPECT_TRUE(Bonus > 0);
 
   Bonus = Specializer.getSpecializationBonus(F->getArg(3), Undef, Visitor);
   EXPECT_TRUE(Bonus == 0);
 }
+
+TEST_F(FunctionSpecializationTest, PhiNode) {
+  const char *ModuleString = R"(
+    define void @foo(i32 %a, i32 %b, i32 %i) {
+    entry:
+      br label %loop
+    loop:
+      %0 = phi i32 [ %a, %entry ], [ %3, %bb ]
+      switch i32 %i, label %default
+      [ i32 1, label %case1
+        i32 2, label %case2 ]
+    case1:
+      %1 = add i32 %0, 1
+      br label %bb
+    case2:
+      %2 = phi i32 [ %a, %entry ], [ %0, %loop ]
+      br label %bb
+    bb:
+      %3 = phi i32 [ %b, %case1 ], [ %2, %case2 ], [ %3, %bb ]
+      %4 = icmp eq i32 %3, 1
+      br i1 %4, label %bb, label %loop
+    default:
+      ret void
+    }
+  )";
+
+  Module &M = parseModule(ModuleString);
+  Function *F = M.getFunction("foo");
+  FunctionSpecializer Specializer = getSpecializerFor(F);
+  InstCostVisitor Visitor = Specializer.getInstCostVisitorFor(F);
+
+  Constant *One = ConstantInt::get(IntegerType::getInt32Ty(M.getContext()), 1);
+
+  auto FuncIter = F->begin();
+  BasicBlock &Loop = *++FuncIter;
+  BasicBlock &Case1 = *++FuncIter;
+  BasicBlock &Case2 = *++FuncIter;
+  BasicBlock &BB = *++FuncIter;
+
+  Instruction &PhiLoop = Loop.front();
+  Instruction &Add = Case1.front();
+  Instruction &PhiCase2 = Case2.front();
+  Instruction &BrBB = Case2.back();
+  Instruction &PhiBB = BB.front();
+  Instruction &Icmp = *++BB.begin();
+
+  Cost Bonus = Specializer.getSpecializationBonus(F->getArg(0), One, Visitor);
+  EXPECT_EQ(Bonus, 0);
+
+  Bonus = Specializer.getSpecializationBonus(F->getArg(1), One, Visitor);
+  EXPECT_EQ(Bonus, 0);
+
+  // phi + br
+  Cost Ref = getInstCost(PhiCase2) + getInstCost(BrBB);
+  Bonus = Specializer.getSpecializationBonus(F->getArg(2), One, Visitor);
+  EXPECT_EQ(Bonus, Ref);
+  EXPECT_TRUE(Bonus > 0);
+
+  // phi + phi + add + icmp
+  Ref = getInstCost(PhiBB) + getInstCost(PhiLoop) + getInstCost(Add) +
+        getInstCost(Icmp);
+  Bonus = Visitor.getBonusFromPendingPHIs();
+  EXPECT_EQ(Bonus, Ref);
+  EXPECT_TRUE(Bonus > 0);
+}
+