[WebAssembly] Fix for 0xc call_indirect changes

[jgravelle-google]

Summary

Need to reorder the operands to have the callee as the last argument.
Adds a pseudo-instruction, and a pass to lower it into a real
call_indirect.

This is the first of two options for how to fix the problem.

[jgravelle-google]

In particular these two reviews are more "should we go with A or B". I don't think either are ready to land just yet, but feedback as to which direction to commit to would be helpful.

[sunfish]

Hrm, I see. My preference would be for the approach in this patch, rather than the other. It has the advantage that we handle it in one place, and don't require as much special-casing elsewhere.

As one minor nit, the CallIndirectFixup pass should be registered outside the getOptLevel() != CodeGenOpt::None test, since it's needed for correctness.

[jgravelle-google]

I also vote for this one, so it looks like we all agree.
I'll make this a bit more production-ready and update this review.

In particular:

• Add a more complete test to validate that stackification errors are gone
• Actually add a description of the WebAssemblyCallIndirectFixup pass
• Make sure this runs regardless of opt level

Thanks!

[jgravelle-google]

More polished implementation of call_indirect lowering

• added register stackification test
• added description to new pass
• made sure to run psuedo fixup on -O0
• removed most autos

[sunfish]

Looks good!

lib/Target/WebAssembly/WebAssemblyInstrCall.td

32 ↗

(On Diff #75347)

We can add "let isCodeGenOnly = 1 in" before this instruction to let various parts of LLVM know that this instruction isn't ever encoded or parsed.

45 ↗

(On Diff #75347)

Ditto about isCodeGenOnly.

69 ↗

(On Diff #75347)

Ditto here too :-).

[jgravelle-google]

Mark pseudo call_indirects as isCodeGenOnly

llvm/trunk/lib/Target/WebAssembly/CMakeLists.txt

 set(LLVM_TARGET_DEFINITIONS WebAssembly.td)
 
 tablegen(LLVM WebAssemblyGenAsmWriter.inc -gen-asm-writer)
 tablegen(LLVM WebAssemblyGenDAGISel.inc -gen-dag-isel)
 tablegen(LLVM WebAssemblyGenFastISel.inc -gen-fast-isel)
 tablegen(LLVM WebAssemblyGenInstrInfo.inc -gen-instr-info)
 tablegen(LLVM WebAssemblyGenMCCodeEmitter.inc -gen-emitter)
 tablegen(LLVM WebAssemblyGenRegisterInfo.inc -gen-register-info)
 tablegen(LLVM WebAssemblyGenSubtargetInfo.inc -gen-subtarget)
 add_public_tablegen_target(WebAssemblyCommonTableGen)
 
 add_llvm_target(WebAssemblyCodeGen
   WebAssemblyArgumentMove.cpp
   WebAssemblyAsmPrinter.cpp
+  WebAssemblyCallIndirectFixup.cpp
   WebAssemblyCFGStackify.cpp
   WebAssemblyFastISel.cpp
   WebAssemblyFixIrreducibleControlFlow.cpp
   WebAssemblyFrameLowering.cpp
   WebAssemblyISelDAGToDAG.cpp
   WebAssemblyISelLowering.cpp
   WebAssemblyInstrInfo.cpp
   WebAssemblyLowerBrUnless.cpp

llvm/trunk/lib/Target/WebAssembly/WebAssembly.h

 FunctionPass *createWebAssemblyStoreResults();
 FunctionPass *createWebAssemblyRegStackify();
 FunctionPass *createWebAssemblyRegColoring();
 FunctionPass *createWebAssemblyFixIrreducibleControlFlow();
 FunctionPass *createWebAssemblyCFGStackify();
 FunctionPass *createWebAssemblyLowerBrUnless();
 FunctionPass *createWebAssemblyRegNumbering();
 FunctionPass *createWebAssemblyPeephole();
+FunctionPass *createWebAssemblyCallIndirectFixup();
 
 } // end namespace llvm
 
 #endif

llvm/trunk/lib/Target/WebAssembly/WebAssemblyCallIndirectFixup.cpp

+//===-- WebAssemblyCallIndirectFixup.cpp - Fix call_indirects -------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+///
+/// \file
+/// \brief This file converts pseudo call_indirect instructions into real
+/// call_indirects.
+///
+/// The order of arguments for a call_indirect is the arguments to the function
+/// call, followed by the function pointer. There's no natural way to express
+/// a machineinstr with varargs followed by one more arg, so we express it as
+/// the function pointer followed by varargs, then rewrite it here.
+///
+/// We need to rewrite the order of the arguments on the machineinstrs
+/// themselves so that register stackification knows the order they'll be
+/// executed in.
+///
+//===----------------------------------------------------------------------===//
+
+#include "WebAssembly.h"
+#include "MCTargetDesc/WebAssemblyMCTargetDesc.h" // for WebAssembly::ARGUMENT_*
+#include "WebAssemblyMachineFunctionInfo.h"
+#include "WebAssemblySubtarget.h"
+#include "llvm/Analysis/AliasAnalysis.h"
+#include "llvm/CodeGen/LiveIntervalAnalysis.h"
+#include "llvm/CodeGen/MachineBlockFrequencyInfo.h"
+#include "llvm/CodeGen/MachineDominators.h"
+#include "llvm/CodeGen/MachineInstrBuilder.h"
+#include "llvm/CodeGen/MachineRegisterInfo.h"
+#include "llvm/CodeGen/Passes.h"
+#include "llvm/Support/Debug.h"
+#include "llvm/Support/raw_ostream.h"
+using namespace llvm;
+
+#define DEBUG_TYPE "wasm-call-indirect-fixup"
+
+namespace {
+class WebAssemblyCallIndirectFixup final : public MachineFunctionPass {
+  StringRef getPassName() const override {
+    return "WebAssembly CallIndirect Fixup";
+  }
+
+  bool runOnMachineFunction(MachineFunction &MF) override;
+
+public:
+  static char ID; // Pass identification, replacement for typeid
+  WebAssemblyCallIndirectFixup() : MachineFunctionPass(ID) {}
+};
+} // end anonymous namespace
+
+char WebAssemblyCallIndirectFixup::ID = 0;
+FunctionPass *llvm::createWebAssemblyCallIndirectFixup() {
+  return new WebAssemblyCallIndirectFixup();
+}
+
+static unsigned GetNonPseudoCallIndirectOpcode(const MachineInstr &MI) {
+  switch (MI.getOpcode()) {
+    using namespace WebAssembly;
+  case PCALL_INDIRECT_VOID: return CALL_INDIRECT_VOID;
+  case PCALL_INDIRECT_I32: return CALL_INDIRECT_I32;
+  case PCALL_INDIRECT_I64: return CALL_INDIRECT_I64;
+  case PCALL_INDIRECT_F32: return CALL_INDIRECT_F32;
+  case PCALL_INDIRECT_F64: return CALL_INDIRECT_F64;
+  case PCALL_INDIRECT_v16i8: return CALL_INDIRECT_v16i8;
+  case PCALL_INDIRECT_v8i16: return CALL_INDIRECT_v8i16;
+  case PCALL_INDIRECT_v4i32: return CALL_INDIRECT_v4i32;
+  case PCALL_INDIRECT_v4f32: return CALL_INDIRECT_v4f32;
+  default: return INSTRUCTION_LIST_END;
+  }
+}
+
+static bool IsPseudoCallIndirect(const MachineInstr &MI) {
+  return GetNonPseudoCallIndirectOpcode(MI) !=
+         WebAssembly::INSTRUCTION_LIST_END;
+}
+
+bool WebAssemblyCallIndirectFixup::runOnMachineFunction(MachineFunction &MF) {
+  DEBUG(dbgs() << "********** Fixing up CALL_INDIRECTs **********\n"
+               << MF.getName() << '\n');
+
+  bool Changed = false;
+  const WebAssemblyInstrInfo *TII =
+      MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo();
+
+  for (MachineBasicBlock &MBB : MF) {
+    for (MachineInstr &MI : MBB) {
+      if (IsPseudoCallIndirect(MI)) {
+        DEBUG(dbgs() << "Found call_indirect: " << MI << '\n');
+
+        // Rewrite pseudo to non-pseudo
+        const MCInstrDesc &Desc = TII->get(GetNonPseudoCallIndirectOpcode(MI));
+        MI.setDesc(Desc);
+
+        // Rewrite argument order
+        auto Uses = MI.explicit_uses();
+        MachineInstr::mop_iterator it = Uses.begin();
+        const MachineOperand MO = *it;
+        unsigned num = MI.getOperandNo(it);
+        MI.RemoveOperand(num);
+        MI.addOperand(MF, MO);
+
+        DEBUG(dbgs() << "  After transform: " << MI);
+        Changed = true;
+      }
+    }
+  }
+
+  DEBUG(dbgs() << "\nDone fixing up CALL_INDIRECTs\n\n");
+
+  return Changed;
+}
+

llvm/trunk/lib/Target/WebAssembly/WebAssemblyFastISel.cpp

if (Func && Func->isIntrinsic())
     return false;
 
   FunctionType *FuncTy = Call->getFunctionType();
   unsigned Opc;
   bool IsDirect = Func != nullptr;
   bool IsVoid = FuncTy->getReturnType()->isVoidTy();
   unsigned ResultReg;
   if (IsVoid) {
-    Opc = IsDirect ? WebAssembly::CALL_VOID : WebAssembly::CALL_INDIRECT_VOID;
+    Opc = IsDirect ? WebAssembly::CALL_VOID : WebAssembly::PCALL_INDIRECT_VOID;
   } else {
     if (!Subtarget->hasSIMD128() && Call->getType()->isVectorTy())
       return false;
 
     MVT::SimpleValueType RetTy = getSimpleType(Call->getType());
     switch (RetTy) {
     case MVT::i1:
     case MVT::i8:
     case MVT::i16:
     case MVT::i32:
-      Opc = IsDirect ? WebAssembly::CALL_I32 : WebAssembly::CALL_INDIRECT_I32;
+      Opc = IsDirect ? WebAssembly::CALL_I32 : WebAssembly::PCALL_INDIRECT_I32;
       ResultReg = createResultReg(&WebAssembly::I32RegClass);
       break;
     case MVT::i64:
-      Opc = IsDirect ? WebAssembly::CALL_I64 : WebAssembly::CALL_INDIRECT_I64;
+      Opc = IsDirect ? WebAssembly::CALL_I64 : WebAssembly::PCALL_INDIRECT_I64;
       ResultReg = createResultReg(&WebAssembly::I64RegClass);
       break;
     case MVT::f32:
-      Opc = IsDirect ? WebAssembly::CALL_F32 : WebAssembly::CALL_INDIRECT_F32;
+      Opc = IsDirect ? WebAssembly::CALL_F32 : WebAssembly::PCALL_INDIRECT_F32;
       ResultReg = createResultReg(&WebAssembly::F32RegClass);
       break;
     case MVT::f64:
-      Opc = IsDirect ? WebAssembly::CALL_F64 : WebAssembly::CALL_INDIRECT_F64;
+      Opc = IsDirect ? WebAssembly::CALL_F64 : WebAssembly::PCALL_INDIRECT_F64;
       ResultReg = createResultReg(&WebAssembly::F64RegClass);
       break;
     case MVT::v16i8:
       Opc =
-          IsDirect ? WebAssembly::CALL_v16i8 : WebAssembly::CALL_INDIRECT_v16i8;
+          IsDirect ? WebAssembly::CALL_v16i8 : WebAssembly::PCALL_INDIRECT_v16i8;
       ResultReg = createResultReg(&WebAssembly::V128RegClass);
       break;
     case MVT::v8i16:
       Opc =
-          IsDirect ? WebAssembly::CALL_v8i16 : WebAssembly::CALL_INDIRECT_v8i16;
+          IsDirect ? WebAssembly::CALL_v8i16 : WebAssembly::PCALL_INDIRECT_v8i16;
       ResultReg = createResultReg(&WebAssembly::V128RegClass);
       break;
     case MVT::v4i32:
       Opc =
-          IsDirect ? WebAssembly::CALL_v4i32 : WebAssembly::CALL_INDIRECT_v4i32;
+          IsDirect ? WebAssembly::CALL_v4i32 : WebAssembly::PCALL_INDIRECT_v4i32;
       ResultReg = createResultReg(&WebAssembly::V128RegClass);
       break;
     case MVT::v4f32:
       Opc =
-          IsDirect ? WebAssembly::CALL_v4f32 : WebAssembly::CALL_INDIRECT_v4f32;
+          IsDirect ? WebAssembly::CALL_v4f32 : WebAssembly::PCALL_INDIRECT_v4f32;
       ResultReg = createResultReg(&WebAssembly::V128RegClass);
       break;
     default:
       return false;
     }
   }
 
   SmallVector<unsigned, 8> Args;

llvm/trunk/lib/Target/WebAssembly/WebAssemblyInstrCall.td

 def ADJCALLSTACKUP : I<(outs), (ins i32imm:$amt, i32imm:$amt2),
                        [(WebAssemblycallseq_end timm:$amt, timm:$amt2)]>;
 } // isCodeGenOnly = 1
 
 multiclass CALL<WebAssemblyRegClass vt, string prefix> {
   def CALL_#vt : I<(outs vt:$dst), (ins i32imm:$callee, variable_ops),
                    [(set vt:$dst, (WebAssemblycall1 (i32 imm:$callee)))],
                    !strconcat(prefix, "call\t$dst, $callee")>;
-  def CALL_INDIRECT_#vt : I<(outs vt:$dst), (ins I32:$callee, variable_ops),
+  let isCodeGenOnly = 1 in {
+    def PCALL_INDIRECT_#vt : I<(outs vt:$dst), (ins I32:$callee, variable_ops),
                               [(set vt:$dst, (WebAssemblycall1 I32:$callee))],
-                            !strconcat(prefix, "call_indirect\t$dst, $callee")>;
+                              "PSEUDO CALL INDIRECT\t$callee">;
+  } // isCodeGenOnly = 1
+  def CALL_INDIRECT_#vt : I<(outs vt:$dst), (ins variable_ops),
+                            [],
+                            !strconcat(prefix, "call_indirect\t$dst")>;
 }
 
 multiclass SIMD_CALL<ValueType vt, string prefix> {
   def CALL_#vt : SIMD_I<(outs V128:$dst), (ins i32imm:$callee, variable_ops),
                          [(set (vt V128:$dst),
                                (WebAssemblycall1 (i32 imm:$callee)))],
                          !strconcat(prefix, "call\t$dst, $callee")>;
-  def CALL_INDIRECT_#vt : SIMD_I<(outs V128:$dst),
+  let isCodeGenOnly = 1 in {
+    def PCALL_INDIRECT_#vt : SIMD_I<(outs V128:$dst),
                                     (ins I32:$callee, variable_ops),
                                     [(set (vt V128:$dst),
                                           (WebAssemblycall1 I32:$callee))],
-                                  !strconcat(prefix,
-                                             "call_indirect\t$dst, $callee")>;
+                                    "PSEUDO CALL INDIRECT\t$callee">;
+  } // isCodeGenOnly = 1
+  def CALL_INDIRECT_#vt : SIMD_I<(outs V128:$dst),
+                                  (ins variable_ops),
+                                  [],
+                                  !strconcat(prefix, "call_indirect\t$dst")>;
 }
 
 let Uses = [SP32, SP64], isCall = 1 in {
   defm : CALL<I32, "i32.">;
   defm : CALL<I64, "i64.">;
   defm : CALL<F32, "f32.">;
   defm : CALL<F64, "f64.">;
   defm : SIMD_CALL<v16i8, "i8x16.">;
   defm : SIMD_CALL<v8i16, "i16x8.">;
   defm : SIMD_CALL<v4i32, "i32x4.">;
   defm : SIMD_CALL<v4f32, "f32x4.">;
 
   def CALL_VOID : I<(outs), (ins i32imm:$callee, variable_ops),
                     [(WebAssemblycall0 (i32 imm:$callee))],
                     "call    \t$callee">;
-  def CALL_INDIRECT_VOID : I<(outs), (ins I32:$callee, variable_ops),
-                             [(WebAssemblycall0 I32:$callee)],
-                             "call_indirect\t$callee">;
+  let isCodeGenOnly = 1 in {
+    def PCALL_INDIRECT_VOID : I<(outs), (ins I32:$callee, variable_ops),
+                      "PSEUDO CALL INDIRECT\t$callee">;
+  } // isCodeGenOnly = 1
+  def CALL_INDIRECT_VOID : I<(outs), (ins variable_ops),
+                             [],
+                             "call_indirect\t">;
 } // Uses = [SP32,SP64], isCall = 1
 
 } // Defs = [ARGUMENTS]
 
 // Patterns for matching a direct call to a global address.
 def : Pat<(i32 (WebAssemblycall1 (WebAssemblywrapper tglobaladdr:$callee))),
           (CALL_I32 tglobaladdr:$callee)>;
 def : Pat<(i64 (WebAssemblycall1 (WebAssemblywrapper tglobaladdr:$callee))),

llvm/trunk/lib/Target/WebAssembly/WebAssemblyTargetMachine.cpp

 void WebAssemblyPassConfig::addPreEmitPass() {
   TargetPassConfig::addPreEmitPass();
 
   // Now that we have a prologue and epilogue and all frame indices are
   // rewritten, eliminate SP and FP. This allows them to be stackified,
   // colored, and numbered with the rest of the registers.
   addPass(createWebAssemblyReplacePhysRegs());
 
+  // Rewrite pseudo call_indirect instructions as real instructions.
+  // This needs to run before register stackification, because we change the
+  // order of the arguments.
+  addPass(createWebAssemblyCallIndirectFixup());
+
   if (getOptLevel() != CodeGenOpt::None) {
     // LiveIntervals isn't commonly run this late. Re-establish preconditions.
     addPass(createWebAssemblyPrepareForLiveIntervals());
 
     // Depend on LiveIntervals and perform some optimizations on it.
     addPass(createWebAssemblyOptimizeLiveIntervals());
 
     // Prepare store instructions for register stackifying.

llvm/trunk/test/CodeGen/WebAssembly/call.ll

 ; CHECK-NEXT: .result i32{{$}}
 ; CHECK-NEXT: {{^}} i32.call_indirect $push[[NUM:[0-9]+]]=, $0{{$}}
 ; CHECK-NEXT: return $pop[[NUM]]{{$}}
 define i32 @call_indirect_i32(i32 ()* %callee) {
   %t = call i32 %callee()
   ret i32 %t
 }
 
+; CHECK-LABEL: call_indirect_arg:
+; CHECK-NEXT: .param i32, i32{{$}}
+; CHECK-NEXT: {{^}} call_indirect $1, $0{{$}}
+; CHECK-NEXT: return{{$}}
+define void @call_indirect_arg(void (i32)* %callee, i32 %arg) {
+  call void %callee(i32 %arg)
+  ret void
+}
+
+; CHECK-LABEL: call_indirect_arg_2:
+; CHECK-NEXT: .param i32, i32, i32{{$}}
+; CHECK-NEXT: {{^}} i32.call_indirect $drop=, $1, $2, $0{{$}}
+; CHECK-NEXT: return{{$}}
+define void @call_indirect_arg_2(i32 (i32, i32)* %callee, i32 %arg, i32 %arg2) {
+  call i32 %callee(i32 %arg, i32 %arg2)
+  ret void
+}
+
 ; CHECK-LABEL: tail_call_void_nullary:
 ; CHECK-NEXT: {{^}} call void_nullary@FUNCTION{{$}}
 ; CHECK-NEXT: return{{$}}
 define void @tail_call_void_nullary() {
   tail call void @void_nullary()
   ret void
 }
 

llvm/trunk/test/CodeGen/WebAssembly/reg-stackify.ll

 declare i32 @stackpointer_callee(i8* readnone, i8* readnone)
 declare i8* @llvm.frameaddress(i32)
 define i32 @stackpointer_dependency(i8* readnone) {
   %2 = tail call i8* @llvm.frameaddress(i32 0)
   %3 = tail call i32 @stackpointer_callee(i8* %0, i8* %2)
   ret i32 %3
 }
 
+; Stackify a call_indirect with respect to its ordering
+
+; CHECK-LABEL: call_indirect_stackify:
+; CHECK: i32.load  $push[[L4:.+]]=, 0($0)
+; CHECK-NEXT: tee_local $push[[L3:.+]]=, $0=, $pop[[L4]]
+; CHECK-NEXT: i32.load  $push[[L0:.+]]=, 0($0)
+; CHECK-NEXT: i32.load  $push[[L1:.+]]=, 0($pop[[L0]])
+; CHECK-NEXT: i32.call_indirect $push{{.+}}=, $pop[[L3]], $1, $pop[[L1]]
+%class.call_indirect = type { i32 (...)** }
+define i32 @call_indirect_stackify(%class.call_indirect** %objptr, i32 %arg) {
+  %obj = load %class.call_indirect*, %class.call_indirect** %objptr
+  %addr = bitcast %class.call_indirect* %obj to i32(%class.call_indirect*, i32)***
+  %vtable = load i32(%class.call_indirect*, i32)**, i32(%class.call_indirect*, i32)*** %addr
+  %vfn = getelementptr inbounds i32(%class.call_indirect*, i32)*, i32(%class.call_indirect*, i32)** %vtable, i32 0
+  %f = load i32(%class.call_indirect*, i32)*, i32(%class.call_indirect*, i32)** %vfn
+  %ret = call i32 %f(%class.call_indirect* %obj, i32 %arg)
+  ret i32 %ret
+}
+
 !llvm.module.flags = !{!0}
 !llvm.dbg.cu = !{!1}
 
 !0 = !{i32 2, !"Debug Info Version", i32 3}
 !1 = distinct !DICompileUnit(language: DW_LANG_C99, file: !2, producer: "clang version 3.9.0 (trunk 266005) (llvm/trunk 266105)", isOptimized: false, runtimeVersion: 0, emissionKind: FullDebug, enums: !3)
 !2 = !DIFile(filename: "test.c", directory: "/")
 !3 = !{}
 !5 = distinct !DISubprogram(name: "test", scope: !2, file: !2, line: 10, type: !6, isLocal: false, isDefinition: true, scopeLine: 11, flags: DIFlagPrototyped, isOptimized: true, unit: !1, variables: !3)
 !6 = !DISubroutineType(types: !3)
 !7 = !DILocalVariable(name: "nzcnt", scope: !5, file: !2, line: 15, type: !8)
 !8 = !DIBasicType(name: "int", size: 32, align: 32, encoding: DW_ATE_signed)
 !9 = !DIExpression()
 !10 = !DILocation(line: 15, column: 6, scope: !5)