Incorrect costing in PartialInliner if IR has unreachable basic blocks

opt -passes=partial-inliner temp.ll

; RUN: opt -passes=partial-inliner -S < %s | FileCheck %s
declare i1 @llvm.public.type.test(ptr, metadata)

define void @dummy() {
  br i1 false, label %while.end, label %while.body

while.body:                                       ; preds = %entry
  call void @dummy()
  br label %while.end

unreachable.block:               ; No predecessors!
  %0 = tail call i1 @llvm.public.type.test(ptr null, metadata !"test-function")
  %result = getelementptr ptr, ptr null, i64 1
  br label %while.end

while.end:                                        ; preds = %unreachable.block, %while.body, %entry
  ret void

If we consider the following test-case, here unreachable.block is an unreachable basic block. But, while computing the cost of outlining region it is considered in the costing and marked as a basic block to be extracted. But when the ToExtract vector is passed on to the CodeExtractor, this unreachable block is removed and the outlining function doesn’t contain this block. As a result, when the costing of outlining function is performed it comes out to be lesser than the cost of outline region and triggers an assert as follows:

Assertion `OutlinedFunctionCost >= Cloner.OutlinedRegionCost && “Outlined function cost should be no less than the outlined region”’ failed.

Explaining the flow that causes this bug

  1. Outlined region costing is performed in the for loop. The following two basic blocks are the ones that are to be extracted = [while.body, unreachable.block] and the costs of them come out to be as follows, (I manually computed and then verified with step execution in gdb)

    Cost of Outline Region = [30 + 5, 1 + 5 + 5] = [35, 11] = 46

// llvm/lib/Transforms/IPO/PartialInlining.cpp: 1157
Function *
PartialInlinerImpl::FunctionCloner::doSingleRegionFunctionOutlining() {
  OutlinedRegionCost += PartialInlinerImpl::computeBBInlineCost(
      ClonedOI->NonReturnBlock, ClonedFuncTTI);
  for (BasicBlock &BB : *ClonedFunc)
    if (!ToBeInlined(&BB) && &BB != ClonedOI->NonReturnBlock) {
      // FIXME: the code extractor may hoist/sink more code
      // into the outlined function which may make the outlining
      // overhead (the difference of the outlined function cost
      // and OutliningRegionCost) look larger.
      OutlinedRegionCost += computeBBInlineCost(&BB, ClonedFuncTTI);

  // Extract the body of the if.
  CodeExtractorAnalysisCache CEAC(*ClonedFunc);
  Function *OutlinedFunc =
      CodeExtractor(ToExtract, &DT, /*AggregateArgs*/ false,
                    ClonedFuncBFI.get(), &BPI, LookupAC(*ClonedFunc),
                    /* AllowVarargs */ true)
  1. Outlining function costing is calculated here, the outlined function has only the while.body from the ToExtract vector, because the other BB is unreachable and was removed by the CodeExtractor, but it was still accounted in the loop that calculated OutlinedRegionCost. The cost of the outlined function including the added entry and exit blocks is:

    OutlinedFunctionCost = 5 + 30 + 5 = 35

// // llvm/lib/Transforms/IPO/PartialInlining.cpp: 864
std::tuple<InstructionCost, InstructionCost>
PartialInlinerImpl::computeOutliningCosts(FunctionCloner &Cloner) const {
  InstructionCost OutliningFuncCallCost = 0, OutlinedFunctionCost = 0;
  for (auto FuncBBPair : Cloner.OutlinedFunctions) {
    Function *OutlinedFunc = FuncBBPair.first;
    BasicBlock* OutliningCallBB = FuncBBPair.second;
    // Now compute the cost of the call sequence to the outlined function
    // 'OutlinedFunction' in BB 'OutliningCallBB':
    auto *OutlinedFuncTTI = &GetTTI(*OutlinedFunc);
    OutliningFuncCallCost +=
        computeBBInlineCost(OutliningCallBB, OutlinedFuncTTI);

    // Now compute the cost of the extracted/outlined function itself:
    for (BasicBlock &BB : *OutlinedFunc)
      OutlinedFunctionCost += computeBBInlineCost(&BB, OutlinedFuncTTI);
  assert(OutlinedFunctionCost >= Cloner.OutlinedRegionCost &&
         "Outlined function cost should be no less than the outlined region");

Reason for assertion
OutlinedFunctionCost >= Cloner.OutlinedRegionCost this given condition fails and turns out to be false as:
OutlinedFunctionCost = 45
Cloner.OutlinedRegionCost = 46
and thus OutlinedFunctionCost < Cloner.OutlinedRegionCost and it triggers the assert.

Solution if the bug is valid
Somehow, it feels incorrect that the unreachable basic block is still used in computing outlining region costs. But, the same is removed from the outlining function.

I tried to solve this bug by adding a EliminateUnreachableBlocks(*CurrFunc) in PartialInlinerImpl::run before call to unswitchFunction(). This solution worked for me. If it seems fine, I have a patch ready to be posted on Phabricator.

Another way to do it, might be to prevent a unreachable basic block to be considered for outlining, but this will be a more complex solution.

(This is not a hand-crafted test case, rather a complex case was exposed in a test application through the same assert. It was then reduced to this form using llvm-reduce)

I have posted a patch on Phabricator for review:

@fhahn @mehdi_amini who might be the right person to review this patch ? Thanks !