[llvm] boilerplate for new callbrprepare codegen IR pass

[nickdesaulniers]

Summary

Because this pass is to be a codegen pass, it must use the legacy pass
manager.

Link: https://discourse.llvm.org/t/rfc-syncing-asm-goto-with-outputs-with-gcc/65453/8

[aeubanks]

llvm/test/CodeGen/PowerPC/O3-pipeline.ll

87 ↗

(On Diff #482187)

to prevent this you'll want to make sure the pass preserves the domtree, and add
something like this

but if you're not using the domtree right now, you should actually say setPreservesAll and later change that to only preserve analyses that you're actually preserving when the pass actually does something

llvm/tools/opt/opt.cpp

363–398

sorry for this, I'm trying to make it so this isn't necessary

[nickdesaulniers]

• preserve all analyses, for now

[aeubanks]

I wouldn't add the pass to the pipeline just yet if it's not even doing anything, but the pass boilerplate looks fine

[nickdesaulniers]

• drop pass from pipelines for now

[aeubanks]

lg, assuming we're actually going this direction

llvm/include/llvm/CodeGen/CodeGenPassBuilder.h

717

oh this is the att

[void]

Why add a stub for the pass? I think people normally just wait until they have a full implementation ready.

[nickdesaulniers]

In D139861#4011835, @void wrote:

Why add a stub for the pass? I think people normally just wait until they have a full implementation ready.

Commit early commit often. I figured it might be easier to review more bite-sized chunks.

This commit is the stub. The next 4 patches incrementally build off it. The 5th patch then wires in the pass to actually run as part of the default pipelines.

[nickdesaulniers]

• rebase, format

[nickdesaulniers]

• rebase

[void]

A couple nits, but overall okay.

llvm/include/llvm/CodeGen/CodeGenPassBuilder.h

721

nit: Probably don't need to reformat this comment.

llvm/lib/CodeGen/CallBrPrepare.cpp

10

s/closer//

[jyknight]

llvm/include/llvm/InitializePasses.h

86–87

Odd artifact here.

llvm/lib/CodeGen/CallBrPrepare.cpp

10–18

I think this description needs to be substantially edited for clarity.

A few points on substance:

• the problem is not unique to physical register outputs, so mentioning that here is just misleading.
• Worth noting that this is primarily to make things easy for SelectionDAG, and in GlobalISel we may be able to lower directly without the IR pass.

[nickdesaulniers]

• fix both nits in comments, as per @void

[nickdesaulniers]

• rebase

[jyknight]

llvm/lib/CodeGen/CallBrPrepare.cpp

10–18

[...] GlobalISel we may be able to lower directly [...]

Or, maybe not...since we probably still need to split critical edges, just not insert a new intrinsic? Dunno.

[nickdesaulniers]

llvm/lib/CodeGen/CallBrPrepare.cpp

10–18

I don't really have any experience with GlobalISel to provide colorful commentary on what it can or cannot do. For instance, I don't think it can even select inline asm, so callbrprepare is kind of a non-starter until it has at least that support.

What are your thoughts on how I can reword this for clarity? I agree I can drop "physical" from descriptions about "physical registers." Anything else? I'm happy to replace the entire thing outright, if you have suggestions?

[nickdesaulniers]

• drop cruft from mis-rebase-merge-conflict-resolution as per @jyknight
• update comment block as per @jyknight

[nickdesaulniers]

llvm/lib/CodeGen/CallBrPrepare.cpp

10–18

Updated to remove mention of specific physical registers in favor of just registers. If you have further thoughts on how best to reword this, please reopen the thread with proposed wording. Marking as done for now.

[jyknight]

llvm/lib/CodeGen/CallBrPrepare.cpp

9–20

Suggestion:

This pass lowers callbrs in LLVM IR in order to to assist SelectionDAG's codegen.

In particular, this pass assists in inserting register copies for the output values of a callbr along the edges leading to the indirect target blocks. Though the output SSA value is defined by the callbr instruction itself in the IR representation, the value cannot be copied to the appropriate virtual registers prior to jumping to an indirect label, since the jump occurs within the user-provided assembly blob.

Instead, those copies must occur separately at the beginning of each indirect target. That requires that we create a separate SSA definition in each of them (via llvm.callbr.landingpad), and may require splitting critical edges so we have a location to place the intrinsic. Finally, we remap users of the original callbr output SSA value to instead point to the appropriate llvm.callbr.landingpad value.

Ideally, this could be done inside SelectionDAG, or in the MachineInstruction representation, without the use of an IR-level intrinsic. But, within the current framework, it’s simpler to implement as an IR pass. (If support for callbr in GlobalISel is implemented, it’s worth considering whether this is still required.)

[nickdesaulniers]

• use @jyknight's lucid description for the comment block describing callbr-prepare pass

[nickdesaulniers]

• rebase

[nickdesaulniers]

• final rebase

llvm/include/llvm/CodeGen/CodeGenPassBuilder.h

 }
 
 /// Add common passes that perform LLVM IR to IR transforms in preparation for
 /// instruction selection.
 template <typename Derived>
 void CodeGenPassBuilder<Derived>::addISelPrepare(AddIRPass &addPass) const {
   derived().addPreISel(addPass);
 
+  // addPass(CallBrPrepare()); // TODO(ndesaulniers): impl pass
   // Add both the safe stack and the stack protection passes: each of them will
   // only protect functions that have corresponding attributes.
   addPass(SafeStackPass());
   addPass(StackProtectorPass());
 
   if (Opt.PrintISelInput)
     addPass(PrintFunctionPass(dbgs(),
                               "\n\n*** Final LLVM Code input to ISel ***\n"));
 
   // All passes which modify the LLVM IR are now complete; run the verifier
   // to ensure that the IR is valid.
   if (!Opt.DisableVerify)

llvm/include/llvm/CodeGen/MachinePassRegistry.def

 DUMMY_FUNCTION_PASS("stack-protector", StackProtectorPass, ())
 DUMMY_FUNCTION_PASS("atomic-expand", AtomicExpandPass, ())
 DUMMY_FUNCTION_PASS("interleaved-access", InterleavedAccessPass, ())
 DUMMY_FUNCTION_PASS("indirectbr-expand", IndirectBrExpandPass, ())
 DUMMY_FUNCTION_PASS("cfguard-dispatch", CFGuardDispatchPass, ())
 DUMMY_FUNCTION_PASS("cfguard-check", CFGuardCheckPass, ())
 DUMMY_FUNCTION_PASS("gc-info-printer", GCInfoPrinterPass, ())
 DUMMY_FUNCTION_PASS("select-optimize", SelectOptimizePass, ())
+DUMMY_FUNCTION_PASS("callbrprepare", CallBrPrepare, ())
 #undef DUMMY_FUNCTION_PASS
 
 #ifndef DUMMY_MODULE_PASS
 #define DUMMY_MODULE_PASS(NAME, PASS_NAME, CONSTRUCTOR)
 #endif
 DUMMY_MODULE_PASS("lower-emutls", LowerEmuTLSPass, ())
 #undef DUMMY_MODULE_PASS
 

llvm/include/llvm/CodeGen/Passes.h

namespace llvm {
   /// otherwise this does nothing
   FunctionPass *createRegAllocScoringPass();
 
   /// JMC instrument pass.
   ModulePass *createJMCInstrumenterPass();
 
   /// This pass converts conditional moves to conditional jumps when profitable.
   FunctionPass *createSelectOptimizePass();
+
+  FunctionPass *createCallBrPass();
 } // End llvm namespace
 
 #endif

llvm/include/llvm/InitializePasses.h

 void initializeCFGOnlyViewerLegacyPassPass(PassRegistry&);
 void initializeCFGPrinterLegacyPassPass(PassRegistry&);
 void initializeCFGSimplifyPassPass(PassRegistry&);
 void initializeCFGuardPass(PassRegistry&);
 void initializeCFGuardLongjmpPass(PassRegistry&);
 void initializeCFGViewerLegacyPassPass(PassRegistry&);
 void initializeCFIFixupPass(PassRegistry&);
 void initializeCFIInstrInserterPass(PassRegistry&);
+void initializeCallBrPreparePass(PassRegistry &);
 void initializeCallGraphDOTPrinterPass(PassRegistry&);
 void initializeCallGraphPrinterLegacyPassPass(PassRegistry&);
 void initializeCallGraphViewerPass(PassRegistry&);
 void initializeCallGraphWrapperPassPass(PassRegistry&);
 void initializeCallSiteSplittingLegacyPassPass(PassRegistry&);
 void initializeCalledValuePropagationLegacyPassPass(PassRegistry &);
 void initializeCheckDebugMachineModulePass(PassRegistry &);
 void initializeCodeGenPreparePass(PassRegistry&);
 void initializeComplexDeinterleavingLegacyPassPass(PassRegistry&);

llvm/lib/CodeGen/CMakeLists.txt

add_llvm_component_library(LLVMCodeGen
   AtomicExpandPass.cpp
   BasicTargetTransformInfo.cpp
   BranchFolding.cpp
   BranchRelaxation.cpp
   BreakFalseDeps.cpp
   BasicBlockSections.cpp
   BasicBlockSectionsProfileReader.cpp
   CalcSpillWeights.cpp
+  CallBrPrepare.cpp
   CallingConvLower.cpp
   CFGuardLongjmp.cpp
   CFIFixup.cpp
   CFIInstrInserter.cpp
   CodeGen.cpp
   CodeGenCommonISel.cpp
   CodeGenPassBuilder.cpp
   CodeGenPrepare.cpp

llvm/lib/CodeGen/CallBrPrepare.cpp

+//===-- CallBrPrepare - Prepare callbr for code generation ----------------===//
+//
+// 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 lowers callbrs in LLVM IR to something that the backend can
+// perform correct instruction selection for.  In particular, callbr may have
+// inline asm with output constraints that require registers.  These registers
+// will need to be copied back to virtual registers somewhere. If we have
+// critical edges, we may need to split them. Regardless of critical edges, we
+// create distinct new SSA values for each indirect destination of the callbr,
+// then remap users of the direct destinations value which aren't dominated by
+// the direct destination, but are by the indirect destination.
+//
+// This enables us to keep the use of the callbr's Value simple in IR, and
+// expand control flow when necessary at the last minute before instruction
+// selection.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/CodeGen/Passes.h"
+#include "llvm/IR/BasicBlock.h"
+#include "llvm/IR/Function.h"
+#include "llvm/IR/Instructions.h"
+#include "llvm/InitializePasses.h"
+#include "llvm/Pass.h"
+
+using namespace llvm;
+
+#define DEBUG_TYPE "callbrprepare"
+
+namespace {
+
+class CallBrPrepare : public FunctionPass {
+public:
+  CallBrPrepare() : FunctionPass(ID) {}
+  static char ID;
+  void getAnalysisUsage(AnalysisUsage &AU) const override;
+  bool runOnFunction(Function &Fn) override;
+};
+
+} // end anonymous namespace
+
+char CallBrPrepare::ID = 0;
+INITIALIZE_PASS(CallBrPrepare, DEBUG_TYPE, "Prepare callbr", false, false)
+
+FunctionPass *llvm::createCallBrPass() { return new CallBrPrepare(); }
+
+void CallBrPrepare::getAnalysisUsage(AnalysisUsage &AU) const {
+  AU.setPreservesAll();
+}
+
+bool CallBrPrepare::runOnFunction(Function &Fn) {
+  for (BasicBlock &BB : Fn) {
+    auto *CBR = dyn_cast<CallBrInst>(BB.getTerminator());
+    if (!CBR)
+      continue;
+    // TODO: something interesting.
+    // https://discourse.llvm.org/t/rfc-syncing-asm-goto-with-outputs-with-gcc/65453/8
+  }
+  return false;
+}

llvm/lib/CodeGen/CodeGen.cpp

 
 /// initializeCodeGen - Initialize all passes linked into the CodeGen library.
 void llvm::initializeCodeGen(PassRegistry &Registry) {
   initializeAssignmentTrackingAnalysisPass(Registry);
   initializeAtomicExpandPass(Registry);
   initializeBasicBlockSectionsPass(Registry);
   initializeBranchFolderPassPass(Registry);
   initializeBranchRelaxationPass(Registry);
+  initializeCallBrPreparePass(Registry);
   initializeCFGuardLongjmpPass(Registry);
   initializeCFIFixupPass(Registry);
   initializeCFIInstrInserterPass(Registry);
   initializeCheckDebugMachineModulePass(Registry);
   initializeCodeGenPreparePass(Registry);
   initializeDeadMachineInstructionElimPass(Registry);
   initializeDebugifyMachineModulePass(Registry);
   initializeDetectDeadLanesPass(Registry);

llvm/lib/CodeGen/TargetPassConfig.cpp

 /// instruction selection.
 void TargetPassConfig::addISelPrepare() {
   addPreISel();
 
   // Force codegen to run according to the callgraph.
   if (requiresCodeGenSCCOrder())
     addPass(new DummyCGSCCPass);
 
+  // addPass(createCallBrPass()); // TODO(ndesaulniers): impl pass
+
   // Add both the safe stack and the stack protection passes: each of them will
   // only protect functions that have corresponding attributes.
   addPass(createSafeStackPass());
   addPass(createStackProtectorPass());
 
   if (PrintISelInput)
     addPass(createPrintFunctionPass(
         dbgs(), "\n\n*** Final LLVM Code input to ISel ***\n"));

llvm/test/CodeGen/AArch64/callbr-prepare.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt %s -callbrprepare -S -o - | FileCheck %s
+
+; TODO: update this test to split critical edges.
+define i32 @test0() {
+; CHECK-LABEL: @test0(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[OUT:%.*]] = callbr i32 asm "# $0", "=r,!i"()
+; CHECK-NEXT:    to label [[DIRECT:%.*]] [label %indirect]
+; CHECK:       direct:
+; CHECK-NEXT:    [[OUT2:%.*]] = callbr i32 asm "# $0", "=r,!i"()
+; CHECK-NEXT:    to label [[DIRECT2:%.*]] [label %indirect]
+; CHECK:       direct2:
+; CHECK-NEXT:    ret i32 0
+; CHECK:       indirect:
+; CHECK-NEXT:    [[OUT3:%.*]] = phi i32 [ [[OUT]], [[ENTRY:%.*]] ], [ [[OUT2]], [[DIRECT]] ]
+; CHECK-NEXT:    ret i32 [[OUT3]]
+;
+entry:
+  %out = callbr i32 asm "# $0", "=r,!i"()
+  to label %direct [label %indirect]
+direct:
+  %out2 = callbr i32 asm "# $0", "=r,!i"()
+  to label %direct2 [label %indirect]
+direct2:
+  ret i32 0
+indirect:
+  %out3 = phi i32 [%out, %entry], [%out2, %direct]
+  ret i32 %out3
+}

llvm/tools/opt/opt.cpp

static bool shouldPinPassToLegacyPM(StringRef Pass) {
 
   std::vector<StringRef> PassNamePrefix = {
       "x86-",    "xcore-", "wasm-",  "systemz-", "ppc-",    "nvvm-",
       "nvptx-",  "mips-",  "lanai-", "hexagon-", "bpf-",    "avr-",
       "thumb2-", "arm-",   "si-",    "gcn-",     "amdgpu-", "aarch64-",
       "amdgcn-", "polly-", "riscv-", "dxil-"};
   std::vector<StringRef> PassNameContain = {"ehprepare"};
   std::vector<StringRef> PassNameExact = {
       "safe-stack",
       "cost-model",
       "codegenprepare",
       "interleaved-load-combine",
       "unreachableblockelim",
       "verify-safepoint-ir",
       "atomic-expand",
       "expandvp",
       "hardware-loops",
       "mve-tail-predication",
       "interleaved-access",
       "global-merge",
       "pre-isel-intrinsic-lowering",
       "expand-reductions",
       "indirectbr-expand",
       "generic-to-nvvm",
       "expandmemcmp",
       "loop-reduce",
       "lower-amx-type",
       "pre-amx-config",
       "lower-amx-intrinsics",
       "polyhedral-info",
       "print-polyhedral-info",
       "replace-with-veclib",
       "jmc-instrument",
       "dot-regions",
       "dot-regions-only",
       "view-regions",
       "view-regions-only",
       "select-optimize",
       "expand-large-div-rem",
       "structurizecfg",
       "fix-irreducible",
-      "expand-large-fp-convert"
+      "expand-large-fp-convert",
+      "callbrprepare",
   };
   for (const auto &P : PassNamePrefix)
     if (Pass.startswith(P))
       return true;
   for (const auto &P : PassNameContain)
     if (Pass.contains(P))
       return true;
   return llvm::is_contained(PassNameExact, Pass);
 }
int main(int argc, char **argv) {
   initializeTarget(Registry);
   // For codegen passes, only passes that do IR to IR transformation are
   // supported.
   initializeExpandLargeDivRemLegacyPassPass(Registry);
   initializeExpandLargeFpConvertLegacyPassPass(Registry);
   initializeExpandMemCmpPassPass(Registry);
   initializeScalarizeMaskedMemIntrinLegacyPassPass(Registry);
   initializeSelectOptimizePass(Registry);
+  initializeCallBrPreparePass(Registry);
   initializeCodeGenPreparePass(Registry);
   initializeAtomicExpandPass(Registry);
   initializeRewriteSymbolsLegacyPassPass(Registry);
   initializeWinEHPreparePass(Registry);
   initializeDwarfEHPrepareLegacyPassPass(Registry);
   initializeSafeStackLegacyPassPass(Registry);
   initializeSjLjEHPreparePass(Registry);
   initializePreISelIntrinsicLoweringLegacyPassPass(Registry);

llvm/utils/gn/secondary/llvm/lib/CodeGen/BUILD.gn

sources = [
     "BasicTargetTransformInfo.cpp",
     "BranchFolding.cpp",
     "BranchRelaxation.cpp",
     "BreakFalseDeps.cpp",
     "CFGuardLongjmp.cpp",
     "CFIFixup.cpp",
     "CFIInstrInserter.cpp",
     "CalcSpillWeights.cpp",
+    "CallBrPrepare.cpp",
     "CallingConvLower.cpp",
     "CodeGen.cpp",
     "CodeGenCommonISel.cpp",
     "CodeGenPassBuilder.cpp",
     "CodeGenPrepare.cpp",
     "CommandFlags.cpp",
     "ComplexDeinterleavingPass.cpp",
     "CriticalAntiDepBreaker.cpp",