[PartialInlining] : Partial inlining Overhead reduction: eliminate unnecessary live-out(s)

[davidxl]

Summary

When there are multiple outgoing edges from outlined region to the return block, a new return block is created and the original return block becomes the 'pre-return block' to factor all incoming values from the outlined region to the new return. The original return block will be part of the outlined region. The original phi in the pre-return block is pruned so that it only takes incoming values from the outlined region.

There are cases when the old phi becomes trivial (all operands have the same value) -- for instance with the same constant or same live across value (from outside the region). In such cases, leaving the phi node will make the code-extractor decide that the phi's def is a live out value defined inside the outlined region -- this leads to additional runtime overhead: stack space to store the live out value, passing the address, in addition to load/store around the outlined calls.

This patch cleans it up.

[wmi]

LGTM. Only a minor comment.

lib/Transforms/IPO/PartialInlining.cpp

660–670

Maybe a little bit simpler to use find_if, but I am not sure.

if (find_if(PN->incoming_values(), std::bind2nd(std::not_equal_to<Value *>(), PN->getIncomingValue(0)))
        != PN->incoming_values().end())
  return (Value *)nullptr;
return PN->getIncomingValue(0);

[davide]

lib/Transforms/IPO/PartialInlining.cpp

660–670

I don't think the find_if version is more readable, but that's just my opinion.

[davide]

An alternative, which I find slightly more readable is using llvm::all_of to make sure all the operands are the same of the first, and in that case return the first and nullptr otherwise.
That would remove the need for the loop.

[davidxl]

Use all_of idiom.

[davide]

Just a comment explaining why we introduce useless PHIs (and therefore the need to remove them).
Wit that, LGTM.

[davide]

thanks for your patience!

lib/Transforms/IPO/PartialInlining.cpp

   // Special hackery is needed with PHI nodes that have inputs from more than
   // one extracted block.  For simplicity, just split the PHIs into a two-level
   // sequence of PHIs, some of which will go in the extracted region, and some
   // of which will go outside.
   BasicBlock *PreReturn = NewReturnBlock;
   // only split block when necessary:
   PHINode *FirstPhi = getFirstPHI(PreReturn);
   unsigned NumPredsFromEntries = OI->ReturnBlockPreds.size();
+  auto IsTrivialPhi = [](PHINode *PN) {
+    Value *CommonValue = nullptr;
+    for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
+      Value *PhiOpnd = PN->getIncomingValue(i);
+      if (!CommonValue)
+        CommonValue = PhiOpnd;
+      else if (CommonValue != PhiOpnd) {
+        CommonValue = nullptr;
+        break;
+      }
+    }
+    return CommonValue;
+  };
+
   if (FirstPhi && FirstPhi->getNumIncomingValues() > NumPredsFromEntries + 1) {
 
     NewReturnBlock = NewReturnBlock->splitBasicBlock(
         NewReturnBlock->getFirstNonPHI()->getIterator());
     BasicBlock::iterator I = PreReturn->begin();
     Instruction *Ins = &NewReturnBlock->front();
+    SmallVector<Instruction *, 4> DeadPhis;
     while (I != PreReturn->end()) {
       PHINode *OldPhi = dyn_cast<PHINode>(I);
       if (!OldPhi)
         break;
 
       PHINode *RetPhi =
           PHINode::Create(OldPhi->getType(), NumPredsFromEntries + 1, "", Ins);
       OldPhi->replaceAllUsesWith(RetPhi);
       Ins = NewReturnBlock->getFirstNonPHI();
 
       RetPhi->addIncoming(&*I, PreReturn);
       for (BasicBlock *E : OI->ReturnBlockPreds) {
         BasicBlock *NewE = cast<BasicBlock>(VMap[E]);
         RetPhi->addIncoming(OldPhi->getIncomingValueForBlock(NewE), NewE);
         OldPhi->removeIncomingValue(NewE);
       }
+
+      if (auto *OldPhiVal = IsTrivialPhi(OldPhi)) {
+        OldPhi->replaceAllUsesWith(OldPhiVal);
+        DeadPhis.push_back(OldPhi);
+      }
+
       ++I;
     }
+
+    for (auto *DP : DeadPhis)
+      DP->eraseFromParent();
+
     for (auto E : OI->ReturnBlockPreds) {
       BasicBlock *NewE = cast<BasicBlock>(VMap[E]);
       NewE->getTerminator()->replaceUsesOfWith(PreReturn, NewReturnBlock);
     }
   }
 
   // Returns true if the block is to be partial inlined into the caller
   // (i.e. not to be extracted to the out of line function)

test/Transforms/CodeExtractor/PartialInlineLiveAcross.ll

+; RUN: opt -S  -partial-inliner -max-num-inline-blocks=2 -skip-partial-inlining-cost-analysis < %s  | FileCheck %s
+; RUN: opt -S -passes=partial-inliner -max-num-inline-blocks=2 -skip-partial-inlining-cost-analysis < %s  | FileCheck %s
+define i32 @test(i32 %arg) local_unnamed_addr #0 {
+bb:
+  %tmp = tail call i32 (...) @bar() #1
+  %tmp1 = icmp slt i32 %arg, 0
+  br i1 %tmp1, label %bb6, label %bb2
+
+bb2:                                              ; preds = %bb
+  tail call void (...) @foo() #1
+  tail call void (...) @foo() #1
+  tail call void (...) @foo() #1
+  tail call void (...) @foo() #1
+  tail call void (...) @foo() #1
+  %tmp3 = tail call i32 (...) @bar() #1
+  %tmp4 = icmp eq i32 %tmp3, 10
+  br i1 %tmp4, label %bb6, label %bb5
+
+bb5:                                              ; preds = %bb2
+  tail call void (...) @foo() #1
+  tail call void (...) @foo() #1
+  tail call void (...) @foo() #1
+  tail call void (...) @foo() #1
+  br label %bb6
+
+bb6:                                              ; preds = %bb5, %bb2, %bb
+  %tmp7 = phi i32 [ %tmp, %bb5 ], [ 0, %bb ], [ %tmp, %bb2 ]
+  ret i32 %tmp7
+}
+
+declare i32 @bar(...) local_unnamed_addr #1
+
+declare void @foo(...) local_unnamed_addr #1
+
+; Function Attrs: nounwind uwtable
+define i32 @dummy_caller(i32 %arg) local_unnamed_addr #0 {
+; CHECK-LABEL: @dummy_caller
+; CHECK: codeRepl.i:
+; CHECK:  call void @test.1_bb2()
+; CHECK-NOT: load
+; CHECK  br
+
+bb:
+  %tmp = tail call i32 @test(i32 %arg)
+  ret i32 %tmp
+}
+
+; CHECK-LABEL: define internal void @test.1_bb2()
+; CHECK: .exitStub:
+; CHECK-NOT:  store i32 %tmp7, i32* %tmp7.out
+; CHECK: ret
+
+
+attributes #0 = { nounwind uwtable }
+attributes #1 = { nounwind uwtable }
+
+!llvm.module.flags = !{!0}
+!llvm.ident = !{!1}
+
+!0 = !{i32 1, !"wchar_size", i32 4}
+!1 = !{!"clang version 5.0.0 (trunk 303574)"}

test/Transforms/CodeExtractor/PartialInlineNoLiveOut.ll

+; RUN: opt -S -partial-inliner -max-num-inline-blocks=2 -skip-partial-inlining-cost-analysis  < %s  | FileCheck %s
+; RUN: opt -S -passes=partial-inliner -max-num-inline-blocks=2  -skip-partial-inlining-cost-analysis < %s  | FileCheck %s
+
+define i32 @test(i32 %arg) local_unnamed_addr #0 {
+bb:
+  %tmp = tail call i32 (...) @bar() #1
+  %tmp1 = icmp slt i32 %arg, 0
+  br i1 %tmp1, label %bb6, label %bb2
+
+bb2:                                              ; preds = %bb
+  tail call void (...) @foo() #1
+  tail call void (...) @foo() #1
+  tail call void (...) @foo() #1
+  tail call void (...) @foo() #1
+  tail call void (...) @foo() #1
+  %tmp3 = tail call i32 (...) @bar() #1
+  %tmp4 = icmp eq i32 %tmp3, 10
+  br i1 %tmp4, label %bb6, label %bb5
+
+bb5:                                              ; preds = %bb2
+  tail call void (...) @foo() #1
+  tail call void (...) @foo() #1
+  tail call void (...) @foo() #1
+  tail call void (...) @foo() #1
+  br label %bb6
+
+bb6:                                              ; preds = %bb5, %bb2, %bb
+  %tmp7 = phi i32 [ 1, %bb5 ], [ 0, %bb ], [ 1, %bb2 ]
+  ret i32 %tmp7
+}
+
+; Function Attrs: nounwind uwtable
+declare i32 @bar(...) local_unnamed_addr #0
+
+; Function Attrs: nounwind uwtable
+declare void @foo(...) local_unnamed_addr #0
+
+; Function Attrs: nounwind uwtable
+define i32 @dummy_caller(i32 %arg) local_unnamed_addr #0 {
+; CHECK-LABEL: @dummy_caller
+; CHECK: codeRepl.i:
+; CHECK:  call void @test.1_bb2()
+; CHECK-NOT: load
+; CHECK  br
+bb:
+  %tmp = tail call i32 @test(i32 %arg)
+  ret i32 %tmp
+}
+
+; CHECK-LABEL: define internal void @test.1_bb2()
+; CHECK: .exitStub:
+; CHECK-NOT:  store i32 %tmp7, i32* %tmp7.out
+; CHECK: ret
+
+attributes #0 = { nounwind uwtable }
+attributes #1 = { nounwind }
+
+!llvm.module.flags = !{!0}
+!llvm.ident = !{!1}
+
+!0 = !{i32 1, !"wchar_size", i32 4}
+!1 = !{!"clang version 5.0.0 (trunk 303574)"}