[SimplifyCFG] Prevent SimplifyCFG from sinking indirect calls.

[jhuber6]

Summary

This patch prevents the CFG simplification pass from sinking indirect
calls. Currently, the indirect calls will be combined into a single
indirect call after the arguments have been selected. This prevents the
indirect calls from being replaced with direct ones once the callee is
known through other optimizations.

An example of this is shown in https://godbolt.org/z/jTcfYnvYx where the
indirect calls cannot be replaced with direct calls once they are
inlined and the calls are known. This is generally more costly than
calling the function directly.

[lebedev.ri]

It looks like what we need is a invoke of select between functions --> if-then-else

[jhuber6]

In D110901#3035809, @lebedev.ri wrote:

It looks like what we need is a invoke of select between functions --> if-then-else

So this should be a separate optimization run afterwards? Where do you think that optimization should live?

[jdoerfert]

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

2065–2066

CB has an isindirectcall member, IIRC.

[jhuber6]

In D110901#3035809, @lebedev.ri wrote:

It looks like what we need is a invoke of select between functions --> if-then-else

Looked at this problem again. There's already a way to promote indirect calls by versioning the call site, we could just add a pass that fully versions indirect calls that have callee metadata. If we do that for the code in the summary we'll get something like this https://godbolt.org/z/EP6n75far, then the versioning should be optimized out in cases like this with InstCombine, SimplifyCFG, and DCE leaving only conditional direct calls. Even in cases where this can't be optimized out, fully versioning out an indirect call whose callees are all known seems reasonable to me, maybe there's a reason we don't do this already that I'm not aware of. The downside is that fixing the code in the summary requires running the callee analysis after inlining, and then doing the versioning early enough that the other simplification passes will clean it up. I could make a patch for that if you think it's reasonable, but I'm not sure if it's worth the extra runtime in LLVM. The alternative is this patch which prevents this specific problem from showing up. What do you think @lebedev.ri?

[lebedev.ri]

This review seems to be stuck/dead, consider abandoning if no longer relevant.

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

 #include "llvm/Analysis/ConstantFolding.h"
 #include "llvm/Analysis/EHPersonalities.h"
 #include "llvm/Analysis/GuardUtils.h"
 #include "llvm/Analysis/InstructionSimplify.h"
 #include "llvm/Analysis/MemorySSA.h"
 #include "llvm/Analysis/MemorySSAUpdater.h"
 #include "llvm/Analysis/TargetTransformInfo.h"
 #include "llvm/Analysis/ValueTracking.h"
+#include "llvm/IR/AbstractCallSite.h"
 #include "llvm/IR/Attributes.h"
 #include "llvm/IR/BasicBlock.h"
 #include "llvm/IR/CFG.h"
 #include "llvm/IR/Constant.h"
 #include "llvm/IR/ConstantRange.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/DerivedTypes.h"
static bool SinkCommonCodeFromPredecessors(BasicBlock *BB,
   // If no instructions can be sunk, early-return.
   if (ScanIdx == 0)
     return false;
 
   // Okay, we *could* sink last ScanIdx instructions. But how many can we
   // actually sink before encountering instruction that is unprofitable to sink?
   auto ProfitableToSinkInstruction = [&](LockstepReverseIterator &LRI) {
     unsigned NumPHIdValues = 0;
-    for (auto *I : *LRI)
+    for (auto *I : *LRI) {
+      // Sinking indirect calls prevents us from replacing the indirect call
+      // with a direct call once the callee is known.
+      if (auto *CB = dyn_cast<CallBase>(I))
+        if (AbstractCallSite ACS = &CB->getCalledOperandUse())
+          if (ACS.isIndirectCall())
+            return false;
       for (auto *V : PHIOperands[I]) {
         if (InstructionsToSink.count(V) == 0)
           ++NumPHIdValues;
         // FIXME: this check is overly optimistic. We may end up not sinking
         // said instruction, due to the very same profitability check.
         // See @creating_too_many_phis in sink-common-code.ll.
       }
+    }
     LLVM_DEBUG(dbgs() << "SINK: #phid values: " << NumPHIdValues << "\n");
     unsigned NumPHIInsts = NumPHIdValues / UnconditionalPreds.size();
     if ((NumPHIdValues % UnconditionalPreds.size()) != 0)
         NumPHIInsts++;
 
     return NumPHIInsts <= 1;
   };
 

llvm/test/Transforms/SimplifyCFG/X86/sink-common-code.ll

call_bar:
   br label %end
 
 end:
   ret void
 }
 
 define void @indirect_caller(i1 %c, i32 %v, void (i32)* %foo, void (i32)* %bar) {
 ; CHECK-LABEL: @indirect_caller(
-; CHECK-NEXT:  end:
-; CHECK-NEXT:    [[FOO_BAR:%.*]] = select i1 [[C:%.*]], void (i32)* [[FOO:%.*]], void (i32)* [[BAR:%.*]]
-; CHECK-NEXT:    tail call void [[FOO_BAR]](i32 [[V:%.*]])
+; CHECK-NEXT:    br i1 [[C:%.*]], label [[CALL_FOO:%.*]], label [[CALL_BAR:%.*]]
+; CHECK:       call_foo:
+; CHECK-NEXT:    tail call void [[FOO:%.*]](i32 [[V:%.*]])
+; CHECK-NEXT:    br label [[END:%.*]]
+; CHECK:       call_bar:
+; CHECK-NEXT:    tail call void [[BAR:%.*]](i32 [[V]])
+; CHECK-NEXT:    br label [[END]]
+; CHECK:       end:
 ; CHECK-NEXT:    ret void
 ;
   br i1 %c, label %call_foo, label %call_bar
 
 call_foo:
   tail call void %foo(i32 %v)
   br label %end