[PartialInliner] Make PHIs free in cost computation.

[fhahn]

Summary

InlineCost also treats them as free and the current implementation
can cause assertion failures if PHI nodes are moved outside the region
from entry BBs to the region.

It also updates the code to use the instructionsWithoutDebug iterator.

[fhahn]

ping

[davidxl]

lib/Transforms/IPO/PartialInlining.cpp

334

Can you add documentation of IsEntryBB parameter (though it seems obvious)?

856

Since you are here, i think it is better to skip all 'nop' operations including (regardless wether it is in entry or not).

1. debugintrinsic (already skipped)
2. phi node
3. nop casting
4. functions calls that does not lower to actual calls (TTI.isLoweredToCall())

[fhahn]

Thanks for having a look! Updated to treat PHI nodes as free.

[fhahn]

lib/Transforms/IPO/PartialInlining.cpp

856

Since you are here, i think it is better to skip all 'nop' operations including (regardless wether it is in entry or not).

debugintrinsic (already skipped)

updated to use iterator.

phi node
nop casting

Done by the switch now.

functions calls that does not lower to actual calls (TTI.isLoweredToCall())

We are using getCallsiteCost from InlineCost.cpp to get the cost of function calls. Do you think it is worth the special case this in PartialInliner.cpp? If so, I think it would be better as a separate commit.

[davidxl]

There are more rooms to improve, but can be done independently.

LGTM

lib/Transforms/IPO/PartialInlining.cpp

private:
   //    outlined function itself;
   // - The second value is the estimated size of the new call sequence in
   //   basic block Cloner.OutliningCallBB;
   std::tuple<int, int> computeOutliningCosts(FunctionCloner &Cloner);
 
   // Compute the 'InlineCost' of block BB. InlineCost is a proxy used to
   // approximate both the size and runtime cost (Note that in the current
   // inline cost analysis, there is no clear distinction there either).
   static int computeBBInlineCost(BasicBlock *BB);
 
   std::unique_ptr<FunctionOutliningInfo> computeOutliningInfo(Function *F);
   std::unique_ptr<FunctionOutliningMultiRegionInfo>
   computeOutliningColdRegionsInfo(Function *F, OptimizationRemarkEmitter &ORE);
 };
 
 struct PartialInlinerLegacyPass : public ModulePass {
   static char ID; // Pass identification, replacement for typeid

 }
 
 // TODO: Ideally  we should share Inliner's InlineCost Analysis code.
 // For now use a simplified version. The returned 'InlineCost' will be used
 // to esimate the size cost as well as runtime cost of the BB.
 int PartialInlinerImpl::computeBBInlineCost(BasicBlock *BB) {
   int InlineCost = 0;
   const DataLayout &DL = BB->getParent()->getParent()->getDataLayout();
-  for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) {
-    if (isa<DbgInfoIntrinsic>(I))
-      continue;
-
-    switch (I->getOpcode()) {
+  for (Instruction &I : BB->instructionsWithoutDebug()) {
+    // Skip free instructions.
+    switch (I.getOpcode()) {
     case Instruction::BitCast:
     case Instruction::PtrToInt:
     case Instruction::IntToPtr:
     case Instruction::Alloca:
+    case Instruction::PHI:
       continue;
     case Instruction::GetElementPtr:
-      if (cast<GetElementPtrInst>(I)->hasAllZeroIndices())
+      if (cast<GetElementPtrInst>(&I)->hasAllZeroIndices())
         continue;
       break;
     default:
       break;
     }
 
-    IntrinsicInst *IntrInst = dyn_cast<IntrinsicInst>(I);
+    IntrinsicInst *IntrInst = dyn_cast<IntrinsicInst>(&I);
     if (IntrInst) {
       if (IntrInst->getIntrinsicID() == Intrinsic::lifetime_start ||
           IntrInst->getIntrinsicID() == Intrinsic::lifetime_end)
         continue;
     }
 
-    if (CallInst *CI = dyn_cast<CallInst>(I)) {
+    if (CallInst *CI = dyn_cast<CallInst>(&I)) {
       InlineCost += getCallsiteCost(CallSite(CI), DL);
       continue;
     }
 
-    if (InvokeInst *II = dyn_cast<InvokeInst>(I)) {
+    if (InvokeInst *II = dyn_cast<InvokeInst>(&I)) {
       InlineCost += getCallsiteCost(CallSite(II), DL);
       continue;
     }
 
-    if (SwitchInst *SI = dyn_cast<SwitchInst>(I)) {
+    if (SwitchInst *SI = dyn_cast<SwitchInst>(&I)) {
       InlineCost += (SI->getNumCases() + 1) * InlineConstants::InstrCost;
       continue;
     }
     InlineCost += InlineConstants::InstrCost;
   }
   return InlineCost;
 }
 

test/Transforms/CodeExtractor/PartialInlineEntryPHICost.ll

+; RUN: opt < %s -partial-inliner -S | FileCheck %s
+; RUN: opt < %s -passes=partial-inliner -S | FileCheck %s
+
+; Check that we do not overcompute the outlined region cost, where the PHIs in
+; the outlined region entry (BB4) are moved outside the region by CodeExtractor.
+
+define i32 @bar(i32 %arg) {
+bb:
+  %tmp = icmp slt i32 %arg, 0
+  br i1 %tmp, label %bb1, label %bb2
+
+bb1:
+  br i1 undef, label %bb4, label %bb2
+
+bb2:                                              ; preds = %bb, %bb1
+  br i1 undef, label %bb4, label %bb5
+
+bb4:                                              ; preds = %bb1, %bb2
+  %xx1 = phi i32 [ 1, %bb1 ], [ 9, %bb2 ]
+  %xx2 = phi i32 [ 1, %bb1 ], [ 9, %bb2 ]
+  %xx3 = phi i32 [ 1, %bb1 ], [ 9, %bb2 ]
+  tail call void (...) @foo() #2
+  br label %bb5
+
+bb5:                                              ; preds = %bb4, %bb2
+  %tmp6 = phi i32 [ 1, %bb2 ], [ 9, %bb4 ]
+  ret i32 %tmp6
+}
+
+declare void @foo(...)
+
+define i32 @dummy_caller(i32 %arg) {
+bb:
+; CHECK-LABEL: @dummy_caller
+; CHECK: br i1
+; CHECK: br i1
+; CHECK: call void @bar.1.
+  %tmp = tail call i32 @bar(i32 %arg)
+  ret i32 %tmp
+}