[IRSim][IROutliner] Ignore outlined sections that include musttail calls

[AndrewLitteken]

Summary

Musttail calls require extra handling to properly propagate the calling convention information and tail call information. The outliner does not currently do this, so we ignore call instructions that utilize the swifttailcc and tailcc calling convention as well as functions marked with the attribute musttail.

[AndrewLitteken]

llvm/include/llvm/Transforms/IPO/IROutliner.h

384

Could be removed from this version, is needed in the patch that handles outlining musttail calls.

llvm/lib/Analysis/IRSimilarityIdentifier.cpp

1203

Needs Comment to denote the argument name.

1222

Needs Comment to denote the argument name.

[paquette]

llvm/include/llvm/Analysis/IRSimilarityIdentifier.h

563

Can you add comments here explaining why this is currently disabled? In the future, we may want to handle this, or someone may be interested in why it's disabled.

[AndrewLitteken]

Adding comments explaining reasoning for skipping for now.

[paquette]

LGTM

llvm/include/llvm/Analysis/IRSimilarityIdentifier.h

struct InstructionClassification
     // is not an indirect call.
     InstrType visitCallInst(CallInst &CI) {
       Function *F = CI.getCalledFunction();
       bool IsIndirectCall = CI.isIndirectCall();
       if (IsIndirectCall && !EnableIndirectCalls)
         return Illegal;
       if (!F && !IsIndirectCall)
         return Illegal;
+      // Functions marked with the swifttailcc and tailcc calling conventions
+      // require special handling when outlining musttail functions.  The
+      // calling convention must be passed down to the outlined function as
+      // well. Further, there is special handling for musttail calls as well,
+      // requiring a return call directly after.  For now, the outliner does not
+      // support this, so we do not handle matching this case either.
+      if ((CI.getCallingConv() == CallingConv::SwiftTail ||
+           CI.getCallingConv() == CallingConv::Tail) &&
+          !EnableMustTailCalls)
+        return Illegal;
+      if (CI.isMustTailCall() && !EnableMustTailCalls)
+        return Illegal;
       return Legal;
     }
     // TODO: We do not current handle similarity that changes the control flow.
     InstrType visitInvokeInst(InvokeInst &II) { return Illegal; }
     // TODO: We do not current handle similarity that changes the control flow.
     InstrType visitCallBrInst(CallBrInst &CBI) { return Illegal; }
     // TODO: Handle interblock similarity.
     InstrType visitTerminator(Instruction &I) { return Illegal; }
     InstrType visitInstruction(Instruction &I) { return Legal; }
 
     // The flag variable that lets the classifier know whether we should
     // allow branches to be checked for similarity.
     bool EnableBranches = false;
 
     // The flag variable that lets the classifier know whether we should
     // allow indirect calls to be considered legal instructions.
     bool EnableIndirectCalls = false;
 
     // Flag that lets the classifier know whether we should allow intrinsics to
     // be checked for similarity.
     bool EnableIntrinsics = false;
+  
+    // Flag that lets the classifier know whether we should allow tail calls to
+    // be checked for similarity.
+    bool EnableMustTailCalls = false;
   };
 
   /// Maps an Instruction to a member of InstrType.
   InstructionClassification InstClassifier;
 };
 
 /// This is a class that wraps a range of IRInstructionData from one point to
 /// another in the vector of IRInstructionData, which is a region of the

 ///
 /// A list of the different similarity groups is then returned after
 /// analyzing the module.
 class IRSimilarityIdentifier {
 public:
   IRSimilarityIdentifier(bool MatchBranches = true,
                          bool MatchIndirectCalls = true,
                          bool MatchCallsWithName = false,
-                         bool MatchIntrinsics = true)
+                         bool MatchIntrinsics = true,
+                         bool MatchMustTailCalls = true)
       : Mapper(&InstDataAllocator, &InstDataListAllocator),
         EnableBranches(MatchBranches), EnableIndirectCalls(MatchIndirectCalls),
         EnableMatchingCallsByName(MatchCallsWithName),
-        EnableIntrinsics(MatchIntrinsics) {}
+        EnableIntrinsics(MatchIntrinsics),
+        EnableMustTailCalls(MatchMustTailCalls) {}
 
 private:
   /// Map the instructions in the module to unsigned integers, using mapping
   /// already present in the Mapper if possible.
   ///
   /// \param [in] M Module - To map to integers.
   /// \param [in,out] InstrList - The vector to append IRInstructionData to.
   /// \param [in,out] IntegerMapping - The vector to append integers to.
private:
   /// similar if they do not have the same name, only the same calling
   /// convention, attributes and type signature.
   bool EnableMatchingCallsByName = true;
 
   /// The flag variable that marks whether we should check intrinsics for
   /// similarity.
   bool EnableIntrinsics = true;
 
+  // The flag variable that marks whether we should allow tailcalls
+  // to be checked for similarity.
+  bool EnableMustTailCalls = false;
+
   /// The SimilarityGroups found with the most recent run of \ref
   /// findSimilarity. None if there is no recent run.
   Optional<SimilarityGroupList> SimilarityCandidates;
 };
 
 } // end namespace IRSimilarity
 
 /// An analysis pass based on legacy pass manager that runs and returns

llvm/include/llvm/Transforms/IPO/IROutliner.h

 #include "llvm/IR/ValueMap.h"
 #include "llvm/Support/InstructionCost.h"
 #include "llvm/Transforms/Utils/CodeExtractor.h"
 #include <set>
 
 struct OutlinableGroup;
 
 namespace llvm {
+using namespace CallingConv;
 using namespace IRSimilarity;
 
 class Module;
 class TargetTransformInfo;
 class OptimizationRemarkEmitter;
 
 /// The OutlinableRegion holds all the information for a specific region, or
 /// sequence of instructions. This includes what values need to be hoisted to
bool visitCallInst(CallInst &CI) {
         return false;
       if (!F && !IsIndirectCall)
         return false;
       // Returning twice can cause issues with the state of the function call
       // that were not expected when the function was used, so we do not include
       // the call in outlined functions.
       if (CI.canReturnTwice())
         return false;
+      // TODO: Update the outliner to capture whether the outlined function
+      // needs these extra attributes.
+
+      // Functions marked with the swifttailcc and tailcc calling conventions
+      // require special handling when outlining musttail functions.  The
+      // calling convention must be passed down to the outlined function as
+      // well. Further, there is special handling for musttail calls as well,
+      // requiring a return call directly after.  For now, the outliner does not
+      // support this.
+      bool IsTailCC = CI.getCallingConv() == CallingConv::SwiftTail ||
+                      CI.getCallingConv() == CallingConv::Tail;
+      if (IsTailCC && !EnableMustTailCalls)
+        return false;
+      if (CI.isMustTailCall() && !EnableMustTailCalls)
+        return false;
+      // The outliner can only handle musttail items if it is also accompanied
+      // by the tailcc or swifttailcc calling convention.
+      if (CI.isMustTailCall() && !IsTailCC)
+        return false;
       return true;
     }
     // TODO: Handle FreezeInsts.  Since a frozen value could be frozen inside
     // the outlined region, and then returned as an output, this will have to be
     // handled differently.
     bool visitFreezeInst(FreezeInst &CI) { return false; }
     // TODO: We do not current handle similarity that changes the control flow.
     bool visitInvokeInst(InvokeInst &II) { return false; }
struct InstructionAllowed : public InstVisitor<InstructionAllowed, bool> {
 
     // The flag variable that marks whether we should allow indirect calls
     // to be outlined.
     bool EnableIndirectCalls = true;
 
     // The flag variable that marks whether we should allow intrinsics
     // instructions to be outlined.
     bool EnableIntrinsics = false;
+
+    // The flag variable that marks whether we should allow musttail calls.
+    bool EnableMustTailCalls = false;
   };
 
   /// A InstVisitor used to exclude certain instructions from being outlined.
   InstructionAllowed InstructionClassifier;
 };
 
 /// Pass to outline similar regions.
 class IROutlinerPass : public PassInfoMixin<IROutlinerPass> {
 public:
   PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM);
 };
 
 } // end namespace llvm
 
 #endif // LLVM_TRANSFORMS_IPO_IROUTLINER_H

llvm/lib/Analysis/IRSimilarityIdentifier.cpp

SimilarityGroupList &IRSimilarityIdentifier::findSimilarity(
   resetSimilarityCandidates();
 
   std::vector<IRInstructionData *> InstrList;
   std::vector<unsigned> IntegerMapping;
   Mapper.InstClassifier.EnableBranches = this->EnableBranches;
   Mapper.InstClassifier.EnableIndirectCalls = EnableIndirectCalls;
   Mapper.EnableMatchCallsByName = EnableMatchingCallsByName;
   Mapper.InstClassifier.EnableIntrinsics = EnableIntrinsics;
+  Mapper.InstClassifier.EnableMustTailCalls = EnableMustTailCalls;
 
   populateMapper(Modules, InstrList, IntegerMapping);
   findCandidates(InstrList, IntegerMapping);
 
   return SimilarityCandidates.getValue();
 }
 
 SimilarityGroupList &IRSimilarityIdentifier::findSimilarity(Module &M) {
   resetSimilarityCandidates();
   Mapper.InstClassifier.EnableBranches = this->EnableBranches;
   Mapper.InstClassifier.EnableIndirectCalls = EnableIndirectCalls;
   Mapper.EnableMatchCallsByName = EnableMatchingCallsByName;
   Mapper.InstClassifier.EnableIntrinsics = EnableIntrinsics;
+  Mapper.InstClassifier.EnableMustTailCalls = EnableMustTailCalls;
 
   std::vector<IRInstructionData *> InstrList;
   std::vector<unsigned> IntegerMapping;
 
   populateMapper(M, InstrList, IntegerMapping);
   findCandidates(InstrList, IntegerMapping);
 
   return SimilarityCandidates.getValue();
 }
 
 INITIALIZE_PASS(IRSimilarityIdentifierWrapperPass, "ir-similarity-identifier",
                 "ir-similarity-identifier", false, true)
 
 IRSimilarityIdentifierWrapperPass::IRSimilarityIdentifierWrapperPass()
     : ModulePass(ID) {
   initializeIRSimilarityIdentifierWrapperPassPass(
       *PassRegistry::getPassRegistry());
 }
 
 bool IRSimilarityIdentifierWrapperPass::doInitialization(Module &M) {
   IRSI.reset(new IRSimilarityIdentifier(!DisableBranches, !DisableIndirectCalls,
-                                        MatchCallsByName, !DisableIntrinsics));
+                                        MatchCallsByName, !DisableIntrinsics,
+                                        false));
   return false;
 }
 
 bool IRSimilarityIdentifierWrapperPass::doFinalization(Module &M) {
   IRSI.reset();
   return false;
 }
 
 bool IRSimilarityIdentifierWrapperPass::runOnModule(Module &M) {
   IRSI->findSimilarity(M);
   return false;
 }
 
 AnalysisKey IRSimilarityAnalysis::Key;
 IRSimilarityIdentifier IRSimilarityAnalysis::run(Module &M,
                                                  ModuleAnalysisManager &) {
   auto IRSI = IRSimilarityIdentifier(!DisableBranches, !DisableIndirectCalls,
-                                     MatchCallsByName, !DisableIntrinsics);
+                                     MatchCallsByName, !DisableIntrinsics,
+                                     false);
   IRSI.findSimilarity(M);
   return IRSI;
 }
 
 PreservedAnalyses
 IRSimilarityAnalysisPrinterPass::run(Module &M, ModuleAnalysisManager &AM) {
   IRSimilarityIdentifier &IRSI = AM.getResult<IRSimilarityAnalysis>(M);
   Optional<SimilarityGroupList> &SimilarityCandidatesOpt = IRSI.getSimilarity();

llvm/test/Transforms/IROutliner/outlining-musttail.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py UTC_ARGS: --include-generated-funcs
+; RUN: opt -S -verify -iroutliner -ir-outlining-no-cost < %s | FileCheck %s
+
+; Check that we do not outline musttail when swifttaill cc or tailcc
+; is not present.
+
+declare void @musttail()
+
+define void @f1() {
+  %a = alloca i32, align 4
+  store i32 2, i32* %a, align 4
+  musttail call void @musttail()
+  ret void
+}
+
+define void @f2() {
+  %a = alloca i32, align 4
+  store i32 2, i32* %a, align 4
+  musttail call void @musttail()
+  ret void
+}
+; CHECK-LABEL: @f1(
+; CHECK-NEXT:    [[A:%.*]] = alloca i32, align 4
+; CHECK-NEXT:    store i32 2, i32* [[A]], align 4
+; CHECK-NEXT:    musttail call void @musttail()
+; CHECK-NEXT:    ret void
+;
+;
+; CHECK-LABEL: @f2(
+; CHECK-NEXT:    [[A:%.*]] = alloca i32, align 4
+; CHECK-NEXT:    store i32 2, i32* [[A]], align 4
+; CHECK-NEXT:    musttail call void @musttail()
+; CHECK-NEXT:    ret void
+;

llvm/test/Transforms/IROutliner/outlining-swifttailcc.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py UTC_ARGS: --include-generated-funcs
+; RUN: opt -S -verify -iroutliner -ir-outlining-no-cost < %s | FileCheck %s
+
+; Check that we do not outline musttail calls when swifttailcc is present.
+
+declare swifttailcc void @musttail()
+
+define swifttailcc void @f1() {
+  %a = alloca i32, align 4
+  store i32 2, i32* %a, align 4
+  musttail call swifttailcc void @musttail()
+  ret void
+}
+
+define swifttailcc void @f2() {
+  %a = alloca i32, align 4
+  store i32 2, i32* %a, align 4
+  musttail call swifttailcc void @musttail()
+  ret void
+}
+; CHECK-LABEL: @f1(
+; CHECK-NEXT:    [[A:%.*]] = alloca i32, align 4
+; CHECK-NEXT:    store i32 2, i32* [[A]], align 4
+; CHECK-NEXT:    musttail call swifttailcc void @musttail()
+; CHECK-NEXT:    ret void
+;
+;
+; CHECK-LABEL: @f2(
+; CHECK-NEXT:    [[A:%.*]] = alloca i32, align 4
+; CHECK-NEXT:    store i32 2, i32* [[A]], align 4
+; CHECK-NEXT:    musttail call swifttailcc void @musttail()
+; CHECK-NEXT:    ret void
+;

llvm/test/Transforms/IROutliner/outlining-tailcc.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py UTC_ARGS: --include-generated-funcs
+; RUN: opt -S -verify -iroutliner -ir-outlining-no-cost < %s | FileCheck %s
+
+; Check that we not do outline musttail calls when tailcc is present.
+
+declare tailcc void @musttail()
+
+define tailcc void @f1() {
+  %a = alloca i32, align 4
+  store i32 2, i32* %a, align 4
+  musttail call tailcc void @musttail()
+  ret void
+}
+
+define tailcc void @f2() {
+  %a = alloca i32, align 4
+  store i32 2, i32* %a, align 4
+  musttail call tailcc void @musttail()
+  ret void
+}
+; CHECK-LABEL: @f1(
+; CHECK-NEXT:    [[A:%.*]] = alloca i32, align 4
+; CHECK-NEXT:    store i32 2, i32* [[A]], align 4
+; CHECK-NEXT:    musttail call tailcc void @musttail()
+; CHECK-NEXT:    ret void
+;
+;
+; CHECK-LABEL: @f2(
+; CHECK-NEXT:    [[A:%.*]] = alloca i32, align 4
+; CHECK-NEXT:    store i32 2, i32* [[A]], align 4
+; CHECK-NEXT:    musttail call tailcc void @musttail()
+; CHECK-NEXT:    ret void
+;