[PartialInlining] Fix incorrect costing when IR has unreachable BBs

[vedant-amd]

Summary

Partial Inlining identifies basic blocks that can be outlined into a
function. It is possible that an unreachable basic block is marked for
outlining. During costing of the outlined region, such unreachable basic
blocks are included as well. However, the CodeExtractor eliminates such
unreachable basic blocks and emits outlined function without them.

Thus, during costing of the outlined function, it is possible that the
cost of the outlined function comes out to be lesser than the cost of
outlined region, which triggers an assert.

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

This patch adds code to eliminate unreachable blocks from the function
body before passing it on to be inlined. It also adds a test that checks
for behaviour of costing in case of unreachable basic blocks.

Discussion: https://discourse.llvm.org/t/incorrect-costing-in-partialinliner-if-ir-has-unreachable-basic-blocks/70163

[jdoerfert]

Generally, I don't believe we should run elimination in all passes.
Instead, use the dominance tree to walk the blocks of a function, or walk it by manually following the control edges.

[fhahn]

If the block is unreachable, how come it is even considered for outlining?

[vedant-amd]

In D149130#4296535, @fhahn wrote:

If the block is unreachable, how come it is even considered for outlining?

This behaviour is triggered even if there are regions of unreachable basic blocks.

no predecessors -> A -> B -> C -> while.end

[vedant-amd]

In D149130#4296268, @jdoerfert wrote:

Generally, I don't believe we should run elimination in all passes.
Instead, use the dominance tree to walk the blocks of a function, or walk it by manually following the control edges.

In D149130#4296268, @jdoerfert wrote:

Generally, I don't believe we should run elimination in all passes.
Instead, use the dominance tree to walk the blocks of a function, or walk it by manually following the control edges.

Adding a check here to see if the given basic block (or region of basic blocks) has a pred makes sense: https://github.com/llvm/llvm-project/blob/8fc1764ef3d18b65b52f82ca4a6bf56ac024e589/llvm/lib/Transforms/IPO/PartialInlining.cpp#L1182

Should I try to implement that using DT ?

[vedant-amd]

In D149130#4296535, @fhahn wrote:

If the block is unreachable, how come it is even considered for outlining?

I think there's simply no check in place, https://github.com/llvm/llvm-project/blob/8fc1764ef3d18b65b52f82ca4a6bf56ac024e589/llvm/lib/Transforms/IPO/PartialInlining.cpp#L1182

It just checks if the BB can be inlined, if not it marks it for outlining.

[fhahn]

In D149130#4297719, @vedant-amd wrote:

In D149130#4296535, @fhahn wrote:

If the block is unreachable, how come it is even considered for outlining?

I think there's simply no check in place, https://github.com/llvm/llvm-project/blob/8fc1764ef3d18b65b52f82ca4a6bf56ac024e589/llvm/lib/Transforms/IPO/PartialInlining.cpp#L1182

It just checks if the BB can be inlined, if not it marks it for outlining.

Yeah that looks like the right place. Instead of iterating over all blocks in the function, it should probably iterate over all blocks reachable from the entry node (e.g. something like depth_first(Cloned->getEntryBlock()).

[vedant-amd]

Removed pass wide unreachable block elimination added a depth_first approach to iterate over basic blocks

[vedant-amd]

Hey @fhahn @jdoerfert Sorry for the delay, but I have updated the patch to reflect your requested changes. Please let me know if it looks okay ?

[fhahn]

It looks like clang-format failed in the pre-commit tests. Could you please make sure the diff is properly formatted by running clang-format-diff?

[vedant-amd]

Run clang-format-diff on the code

[vedant-amd]

In D149130#4327201, @fhahn wrote:

It looks like clang-format failed in the pre-commit tests. Could you please make sure the diff is properly formatted by running clang-format-diff?

Sure, I have updated the patch, it passes the clang check. Does the patch look good ?

[fhahn]

LGTM, thanks!

[vedant-amd]

In D149130#4329307, @fhahn wrote:

LGTM, thanks!

I pushed using arc patch D<code>, but it seems to have not worked or something

The patch doesn't reflect in the llvm-project repo yet, did I mess up something ?

Edit: It seems github is down: https://www.githubstatus.com/

llvm/lib/Transforms/IPO/PartialInlining.cpp

 //===- PartialInlining.cpp - Inline parts of functions --------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
 // This pass performs partial inlining, typically by inlining an if statement
 // that surrounds the body of the function.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Transforms/IPO/PartialInlining.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/DenseSet.h"
+#include "llvm/ADT/DepthFirstIterator.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/BlockFrequencyInfo.h"
 #include "llvm/Analysis/BranchProbabilityInfo.h"
 #include "llvm/Analysis/InlineCost.h"
 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/Analysis/OptimizationRemarkEmitter.h"
PartialInlinerImpl::FunctionCloner::doSingleRegionFunctionOutlining() {
   ClonedFuncBFI.reset(new BlockFrequencyInfo(*ClonedFunc, BPI, LI));
 
   // Gather up the blocks that we're going to extract.
   std::vector<BasicBlock *> ToExtract;
   auto *ClonedFuncTTI = &GetTTI(*ClonedFunc);
   ToExtract.push_back(ClonedOI->NonReturnBlock);
   OutlinedRegionCost += PartialInlinerImpl::computeBBInlineCost(
       ClonedOI->NonReturnBlock, ClonedFuncTTI);
-  for (BasicBlock &BB : *ClonedFunc)
-    if (!ToBeInlined(&BB) && &BB != ClonedOI->NonReturnBlock) {
-      ToExtract.push_back(&BB);
+  for (BasicBlock *BB : depth_first(&ClonedFunc->getEntryBlock()))
+    if (!ToBeInlined(BB) && BB != ClonedOI->NonReturnBlock) {
+      ToExtract.push_back(BB);
       // 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);
+      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)

llvm/test/Transforms/PartialInlining/unreachable_basic_block.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt -passes=partial-inliner -S < %s | FileCheck %s
+declare i1 @llvm.public.type.test(ptr, metadata)
+
+define void @dummy() {
+; CHECK-LABEL: @dummy(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br i1 false, label [[WHILE_END:%.*]], label [[WHILE_BODY:%.*]]
+; CHECK:       while.body:
+; CHECK-NEXT:    call void @dummy.1.while.body()
+; CHECK-NEXT:    br label [[WHILE_END]]
+; CHECK:       while.end:
+; CHECK-NEXT:    ret void
+;
+entry:
+  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
+}