Support CFI for WebAssembly target

[ddcc]

Summary

This patch implements CFI for WebAssembly. It modifies the LowerTypeTest pass to pre-assign table indexes to functions that are called indirectly, and lowers type checks to test against the appropriate table indexes. It also modifies the WebAssembly backend to support a special ".indidx" assembly directive that propagates the table index assignments out to the linker.

[jfb]

I'd like to see a few .ll tests as well.

Could you also update the patch description to explain what it's doing?

lib/CodeGen/AsmPrinter/DbgValueHistoryCalculator.cpp

167 ↗

(On Diff #62011)

Would you have a stand-alone test that triggers this separately? I think you should do the changes in the file in a separate patch (it's similar to @dschuff's PEI patch to handle virtual registers).

lib/CodeGen/LiveIntervalAnalysis.cpp

1326 ↗

(On Diff #62011)

Same here, do you have a bitcode file that demonstrates the issue? I'd fix separately (separate from DbgValue*.cpp above as well).

lib/Transforms/IPO/LowerTypeTests.cpp

690

Weird format here, you should run clang-format on the parts that you change.

837

static here is a bad idea. Is it just used once to fill GlobalLayout, or is the function called multiple times?

[ddcc]

Yeah, I should move the commit that modifies debug information and virtual register checking out of this patch. It's a gist by Yury Delendik (https://gist.github.com/yurydelendik/a37b786dae40736ed7a1b04770f9c9ed) that I picked up on this branch while debugging compilation crashes with debug information enabled.

[ddcc]

lib/Transforms/IPO/LowerTypeTests.cpp

837

This function is called once for each disjoint equivalence set. I'll move it out to the class level.

[ddcc]

Fix formatting, drop gist

[jfb]

lib/Target/WebAssembly/WebAssemblyAsmPrinter.cpp

189

You can fold the above lines into one:

if (MDNode *Idx = F.getMetadata("wasm.index")) {

LLVM usually uses that idiom.

lib/Transforms/IPO/LowerTypeTests.cpp

224

A more descriptive name would be better: what is this counting?

640

This shouldn't get deleted since this is x86-specific?

653

Same, still x86-specific.

680

Same.

844

Why nullptr here?

[ddcc]

Rename counter, add more comments

[ddcc]

lib/Transforms/IPO/LowerTypeTests.cpp

640

I moved the check higher up in buildBitSetsFromFunctions() and eliminated the duplicates.

844

Added a comment.

[ddcc]

Add tests

[ddcc]

Fix some test bugs

[jfb]

test/Transforms/LowerTypeTests/function-disjoint.ll

3

I'm not sure this will work because the wasm backend is still experimental (IIUC lit will exclude the backend-specific folders, but these files will be executed unconditionally). Is that the case?

[pcc]

Is there any documentation for this ".indidx" directive?

[ddcc]

As far as I know, the assembler format for WebAssembly is relatively undocumented. The pull request adding support for the ".indidx" directive in the WebAssembly linker is https://github.com/WebAssembly/binaryen/pull/616, and there is documentation for the overall CFI approach at https://github.com/ddcc/design/blob/cfi/Security.md#control-flow-integrity.

[pcc]

Thanks, but that only raises more questions.

What is an "index"? Is it something that can be called, like a function pointer?

If that's the case, and indexes start from zero, how do you resolve conflicts between indexes in dynamically loaded modules? Or does your design assume no dynamic loading?

(Also, how do you represent null function pointers if indexes start at zero?)

[ddcc]

Yes, in WebAssembly, most uses of memory addresses (pointers) are replaced with indexes into the appropriate section. As part of this, all functions and their types must be explicitly declared, and functions which can be called indirectly must be explicitly listed in a "table" section. The only remaining use of memory addresses is to an isolated linear memory region (for emulating a stack, etc), but this can only be used for storing data. Replacing function pointers with indexes is handled in s2wasm (compile/run process: c/c++ -> emscripten (clang -> opt -> llc -> s2wasm) -> browser) , which looks for functions that have their address taken, generates a table entry for each, and uses the table entry index as the "address". Additionally, s2wasm includes the expected type of the indirect function with the indirect function call. At runtime, two checks are performed at each indirect function call: (1) the specified index is a valid entry in the "table" section, and (2) the type signature specified at the call site matches the call site of the selected function (NULL "function pointers" would presumably fail this). If either of these is violated, then a runtime trap is generated.

However, this current approach has some downsides: it doesn't protect against code reuse attacks, and the signature check is fairly coarse grained, since it is performed at the WebAssembly type level (which only has four unique types: int/float, 32/64-bit). This patch adds support for Clang/LLVM's CFI implementation in WebAssembly programs, by pre-assigning continuous indexes in LLVM for each disjoint set, and introducing a new primitive (.indidx) to tell the linker that a function must be given an index. The corresponding patch to the linker first preallocates entries for functions with a preassigned index, then falls back to the normal behavior of generating new entries for each remaining function called indirectly. Unfortunately, this approach corrects the two drawbacks, but adds some runtime overhead. A future patch will use support for multiple tables with homogeneous type in WebAssembly to eliminate the runtime CFI overhead.

Dynamic linking support (https://github.com/WebAssembly/design/blob/master/DynamicLinking.md) has only recently been introduced into WebAssembly as of approx. two weeks ago, and the interaction between CFI and dynamic linking hasn't been decided yet. Currently, calling dlsym finds the imported function, copies it to the function and table sections of the host, and returns its index for use in an indirect call. Clearly, this doesn't work well with CFI; different implementations include requiring a forward declaration of dynamically-linked functions for placeholder entries, fixing table offsets and set boundaries at runtime, etc. Alternatively, if tables with homogeneous type are used for CFI, then the tables from two modules could just be joined directly: two tables with the same type are merged, otherwise new tables are created and table references are updated.

[pcc]

Thanks for that writeup, it helped me understand what's going on here more clearly. Please also include those details in your commit message.

Also, how do you represent null function pointers if indexes start at zero?

I'm still a little unclear about this. Suppose I have some code that looks like this:

void f() {}

bool foo(void (*fp)()) {
  return fp != nullptr;
}

What result will foo(f) yield if this pass happens to assign index 0 to the function f, and why?

Currently, calling dlsym finds the imported function, copies it to the function and table sections of the host, and returns its index for use in an indirect call. Clearly, this doesn't work well with CFI; different implementations include requiring a forward declaration of dynamically-linked functions for placeholder entries, fixing table offsets and set boundaries at runtime, etc. Alternatively, if tables with homogeneous type are used for CFI, then the tables from two modules could just be joined directly: two tables with the same type are merged, otherwise new tables are created and table references are updated.

Okay, I'm happy for the design here to match the current wasm design, and for it to evolve as wasm does.

lib/Target/WebAssembly/WebAssemblyAsmPrinter.cpp

191

clang-format this line.

lib/Transforms/IPO/LowerTypeTests.cpp

683–685

This comment belongs on buildBitSetsFromFunctionsX86.

688–694

Remove all braces here.

841

You could set the function metadata here instead of in the loop below.

843

Please explain *why* you are passing a null pointer here (i.e. because wasm does not use jump tables directly...)

test/Transforms/LowerTypeTests/function-disjoint.ll

4

I think this should be fine because we aren't using the backend here.

[ddcc]

Cleanup formatting, update comments, skip metadata for unused functions

[ddcc]

Hmm, good question. Currently, if I compile that example with optimizations enabled, it simply gets optimized out to always return true. However, if I compile it without optimizations, it actually returns false. This is because f() gets assigned to table index 0 by s2wasm, and the check fails. Note that this is true regardless of whether the CFI pass is enabled; there are no indirect function calls being executed, so it doesn't affect the IR at all.

Now, suppose that I execute the following example code. Without CFI, it will trigger a runtime type check failure, because the indirect call table has the entries (0: f, 1: g), and fp2 is assigned index 0, but this doesn't match the expected type at the call site. Now, the behavior is different with CFI, because the indirect call table has the entries (0: g, 1: main, 2: f), and fp2 is assigned index 0, which executes successfully. This is because {g, main} are in the same type set and are assigned indexes {0, 1}, respectively, whereas f is skipped by the CFI pass because the type of f is never referenced by llvm.type.test() (since it is never explicitly called), but it is automatically assigned index 2 in s2wasm (since it has its address taken). However, this behavior is suboptimal and actually increases the attack surface by adding more indirect call targets, so I've modified this patch to skip index assignments for functions that are not used anywhere. With the new version of this patch, the indirect call table has the entries (0: g, 1: f), and fp2 is assigned index 0, which executes successfully. If NULL + 1 is assigned to fp2, then a CFI trap is triggered, as expected.

In general, the rationale for undefined behavior is discussed in the documentation; essentially undefined behavior in C or C++ (e.g. dereferencing a NULL pointer) is still a bug when compiling for WebAssembly, even when the corresponding behavior in WebAssembly itself is defined.

void f() {
}

int g() {
  return 2;
}

int main() __attribute__((optnone)) {
  int i = 0;
  void (*fp1)() = f;
  int (*fp2)() = i ? g : NULL;
  return fp2();
}

[pcc]

This is because f() gets assigned to table index 0 by s2wasm, and the check fails. Note that this is true regardless of whether the CFI pass is enabled; there are no indirect function calls being executed, so it doesn't affect the IR at all.

So it sounds like maybe s2wasm and this pass should both be assigning indexes starting at 1? Although calls to null function pointers are undefined, null comparisons are well-defined in C++. Feel free to ignore this though with regard to this patch, as it seems like a pre-existing design issue.

lib/Transforms/IPO/LowerTypeTests.cpp

843

You may want to use Function::hasAddressTaken to exclude direct function calls here.

Please also document how this interacts with dynamic loading (i.e. not at all at the moment, right?)

[ddcc]

Revise comments, use hasAddressTaken()

[ddcc]

The issue with null pointer comparisons is definitely something that should be addressed in WebAssembly. I've filed a design bug for this at https://github.com/WebAssembly/spec/issues/312 .

[dschuff]

This looks ready to go to me, unless @pcc has remaining questions or issues?

[ddcc]

Rebase

lib/Target/WebAssembly/MCTargetDesc/WebAssemblyMCTargetDesc.h

 
 /// WebAssembly-specific directive identifiers.
 enum Directive {
   // FIXME: This is not the real binary encoding.
   DotParam = UINT64_MAX - 0,   ///< .param
   DotResult = UINT64_MAX - 1,  ///< .result
   DotLocal = UINT64_MAX - 2,   ///< .local
   DotEndFunc = UINT64_MAX - 3, ///< .endfunc
+  DotIndIdx = UINT64_MAX - 4,  /// < .indidx
 };
 
 } // end namespace WebAssembly
 
 namespace WebAssemblyII {
 enum {
   // For variadic instructions, this flag indicates whether an operand
   // in the variable_ops range is an immediate value.
inline unsigned GetDefaultP2Align(unsigned Opcode) {
   case WebAssembly::LOAD32_U_I64:
   case WebAssembly::STORE32_I64:
     return 2;
   case WebAssembly::LOAD_I64:
   case WebAssembly::LOAD_F64:
   case WebAssembly::STORE_I64:
   case WebAssembly::STORE_F64:
     return 3;
-  default: llvm_unreachable("Only loads and stores have p2align values");
+  default:
+    llvm_unreachable("Only loads and stores have p2align values");
   }
 }
 
 /// The operand number of the load or store address in load/store instructions.
 static const unsigned MemOpAddressOperandNo = 2;
 /// The operand number of the stored value in a store instruction.
 static const unsigned StoreValueOperandNo = 4;
 
 } // end namespace WebAssembly
 } // end namespace llvm
 
 #endif

lib/Target/WebAssembly/MCTargetDesc/WebAssemblyTargetStreamer.h

public:
   /// .endfunc
   virtual void emitEndFunc() = 0;
   /// .functype
   virtual void emitIndirectFunctionType(StringRef name,
                                         SmallVectorImpl<MVT> &SignatureVTs,
                                         size_t NumResults) {
     llvm_unreachable("emitIndirectFunctionType not implemented");
   }
+  /// .indidx
+  virtual void emitIndIdx(const MCExpr *Value) = 0;
 };
 
 /// This part is for ascii assembly output
 class WebAssemblyTargetAsmStreamer final : public WebAssemblyTargetStreamer {
   formatted_raw_ostream &OS;
 
 public:
   WebAssemblyTargetAsmStreamer(MCStreamer &S, formatted_raw_ostream &OS);
 
   void emitParam(ArrayRef<MVT> Types) override;
   void emitResult(ArrayRef<MVT> Types) override;
   void emitLocal(ArrayRef<MVT> Types) override;
   void emitEndFunc() override;
   void emitIndirectFunctionType(StringRef name,
                                 SmallVectorImpl<MVT> &SignatureVTs,
                                 size_t NumResults) override;
+  void emitIndIdx(const MCExpr *Value) override;
 };
 
 /// This part is for ELF object output
 class WebAssemblyTargetELFStreamer final : public WebAssemblyTargetStreamer {
 public:
   explicit WebAssemblyTargetELFStreamer(MCStreamer &S);
 
   void emitParam(ArrayRef<MVT> Types) override;
   void emitResult(ArrayRef<MVT> Types) override;
   void emitLocal(ArrayRef<MVT> Types) override;
   void emitEndFunc() override;
+  void emitIndIdx(const MCExpr *Value) override;
 };
 
 } // end namespace llvm
 
 #endif

lib/Target/WebAssembly/MCTargetDesc/WebAssemblyTargetStreamer.cpp

void WebAssemblyTargetAsmStreamer::emitLocal(ArrayRef<MVT> Types) {
   PrintTypes(OS, Types);
 }
 
 void WebAssemblyTargetAsmStreamer::emitEndFunc() { OS << "\t.endfunc\n"; }
 
 void WebAssemblyTargetAsmStreamer::emitIndirectFunctionType(
     StringRef name, SmallVectorImpl<MVT> &SignatureVTs, size_t NumResults) {
   OS << "\t.functype\t" << name;
-  if (NumResults == 0) OS << ", void";
+  if (NumResults == 0)
+    OS << ", void";
   for (auto Ty : SignatureVTs) {
     OS << ", " << WebAssembly::TypeToString(Ty);
   }
   OS << "\n";
 }
 
+void WebAssemblyTargetAsmStreamer::emitIndIdx(const MCExpr *Value) {
+  OS << "\t.indidx  \t" << *Value << '\n';
+}
+
 // FIXME: What follows is not the real binary encoding.
 
 static void EncodeTypes(MCStreamer &Streamer, ArrayRef<MVT> Types) {
   Streamer.EmitIntValue(Types.size(), sizeof(uint64_t));
   for (MVT Type : Types)
     Streamer.EmitIntValue(Type.SimpleTy, sizeof(uint64_t));
 }
 

 void WebAssemblyTargetELFStreamer::emitLocal(ArrayRef<MVT> Types) {
   Streamer.EmitIntValue(WebAssembly::DotLocal, sizeof(uint64_t));
   EncodeTypes(Streamer, Types);
 }
 
 void WebAssemblyTargetELFStreamer::emitEndFunc() {
   Streamer.EmitIntValue(WebAssembly::DotEndFunc, sizeof(uint64_t));
 }
+
+void WebAssemblyTargetELFStreamer::emitIndIdx(const MCExpr *Value) {
+  Streamer.EmitIntValue(WebAssembly::DotIndIdx, sizeof(uint64_t));
+  Streamer.EmitValue(Value, sizeof(uint64_t));
+}

lib/Target/WebAssembly/WebAssemblyAsmPrinter.cpp

 //===-- WebAssemblyAsmPrinter.cpp - WebAssembly LLVM assembly writer ------===//
 //
 //                     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 contains a printer that converts from our internal
 /// representation of machine-dependent LLVM code to the WebAssembly assembly
 /// language.
 ///
 //===----------------------------------------------------------------------===//
 
-#include "WebAssembly.h"
 #include "InstPrinter/WebAssemblyInstPrinter.h"
 #include "MCTargetDesc/WebAssemblyMCTargetDesc.h"
 #include "MCTargetDesc/WebAssemblyTargetStreamer.h"
+#include "WebAssembly.h"
 #include "WebAssemblyMCInstLower.h"
 #include "WebAssemblyMachineFunctionInfo.h"
 #include "WebAssemblyRegisterInfo.h"
 #include "WebAssemblySubtarget.h"
 #include "llvm/ADT/StringExtras.h"
 #include "llvm/CodeGen/Analysis.h"
 #include "llvm/CodeGen/AsmPrinter.h"
 #include "llvm/CodeGen/MachineConstantPool.h"

 }
 
 void WebAssemblyAsmPrinter::EmitFunctionBodyStart() {
   if (!MFI->getParams().empty())
     getTargetStreamer()->emitParam(MFI->getParams());
 
   SmallVector<MVT, 4> ResultVTs;
   const Function &F(*MF->getFunction());
+
+  // Emit the function index.
+  if (MDNode *Idx = F.getMetadata("wasm.index")) {
+    assert(Idx->getNumOperands() == 1);
+
+    getTargetStreamer()->emitIndIdx(AsmPrinter::lowerConstant(
+        cast<ConstantAsMetadata>(Idx->getOperand(0))->getValue()));
+  }
+
   ComputeLegalValueVTs(F, TM, F.getReturnType(), ResultVTs);
 
   // If the return type needs to be legalized it will get converted into
   // passing a pointer.
   if (ResultVTs.size() == 1)
     getTargetStreamer()->emitResult(ResultVTs);
 
   bool AnyWARegs = false;

lib/Transforms/IPO/LowerTypeTests.cpp

 //===-- LowerTypeTests.cpp - type metadata lowering pass ------------------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 // This pass lowers type metadata and calls to the llvm.type.test intrinsic.
 // See http://llvm.org/docs/TypeMetadata.html for more information.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Transforms/IPO/LowerTypeTests.h"
-#include "llvm/Transforms/IPO.h"
 #include "llvm/ADT/EquivalenceClasses.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/ADT/Triple.h"
 #include "llvm/IR/Constant.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/GlobalObject.h"
 #include "llvm/IR/GlobalVariable.h"
 #include "llvm/IR/IRBuilder.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/Intrinsics.h"
 #include "llvm/IR/Module.h"
 #include "llvm/IR/Operator.h"
 #include "llvm/Pass.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/raw_ostream.h"
+#include "llvm/Transforms/IPO.h"
 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
 
 using namespace llvm;
 using namespace lowertypetests;
 
 #define DEBUG_TYPE "lowertypetests"
 
 STATISTIC(ByteArraySizeBits, "Byte array size in bits");
bool BitSetInfo::containsValue(
   }
 
   if (auto GEP = dyn_cast<GEPOperator>(V)) {
     APInt APOffset(DL.getPointerSizeInBits(0), 0);
     bool Result = GEP->accumulateConstantOffset(DL, APOffset);
     if (!Result)
       return false;
     COffset += APOffset.getZExtValue();
-    return containsValue(DL, GlobalLayout, GEP->getPointerOperand(),
-                         COffset);
+    return containsValue(DL, GlobalLayout, GEP->getPointerOperand(), COffset);
   }
 
   if (auto Op = dyn_cast<Operator>(V)) {
     if (Op->getOpcode() == Instruction::BitCast)
       return containsValue(DL, GlobalLayout, Op->getOperand(0), COffset);
 
     if (Op->getOpcode() == Instruction::Select)
       return containsValue(DL, GlobalLayout, Op->getOperand(1), COffset) &&
struct LowerTypeTests : public ModulePass {
   Triple::ObjectFormatType ObjectFormat;
   IntegerType *Int1Ty;
   IntegerType *Int8Ty;
   IntegerType *Int32Ty;
   Type *Int32PtrTy;
   IntegerType *Int64Ty;
   IntegerType *IntPtrTy;
 
+  // Indirect function call index assignment counter for WebAssembly
+  uint64_t IndirectIndex;
+
   // Mapping from type identifiers to the call sites that test them.
   DenseMap<Metadata *, std::vector<CallInst *>> TypeTestCallSites;
 
   std::vector<ByteArrayInfo> ByteArrayInfos;
 
   BitSetInfo
   buildBitSet(Metadata *TypeId,
               const DenseMap<GlobalObject *, uint64_t> &GlobalLayout);
void buildBitSetsFromGlobalVariables(ArrayRef<Metadata *> TypeIds,
                                        ArrayRef<GlobalVariable *> Globals);
   unsigned getJumpTableEntrySize();
   Type *getJumpTableEntryType();
   Constant *createJumpTableEntry(GlobalObject *Src, Function *Dest,
                                  unsigned Distance);
   void verifyTypeMDNode(GlobalObject *GO, MDNode *Type);
   void buildBitSetsFromFunctions(ArrayRef<Metadata *> TypeIds,
                                  ArrayRef<Function *> Functions);
+  void buildBitSetsFromFunctionsX86(ArrayRef<Metadata *> TypeIds,
+                                    ArrayRef<Function *> Functions);
+  void buildBitSetsFromFunctionsWASM(ArrayRef<Metadata *> TypeIds,
+                                     ArrayRef<Function *> Functions);
   void buildBitSetsFromDisjointSet(ArrayRef<Metadata *> TypeIds,
                                    ArrayRef<GlobalObject *> Globals);
   bool lower();
 
   bool doInitialization(Module &M) override;
   bool runOnModule(Module &M) override;
 };
 
bool LowerTypeTests::doInitialization(Module &Mod) {
 
   Int1Ty = Type::getInt1Ty(M->getContext());
   Int8Ty = Type::getInt8Ty(M->getContext());
   Int32Ty = Type::getInt32Ty(M->getContext());
   Int32PtrTy = PointerType::getUnqual(Int32Ty);
   Int64Ty = Type::getInt64Ty(M->getContext());
   IntPtrTy = DL.getIntPtrType(M->getContext(), 0);
 
+  IndirectIndex = 0;
+
   TypeTestCallSites.clear();
 
   return false;
 }
 
 /// Build a bit set for TypeId using the object layouts in
 /// GlobalLayout.
 BitSetInfo LowerTypeTests::buildBitSet(
-    Metadata *TypeId,
-    const DenseMap<GlobalObject *, uint64_t> &GlobalLayout) {
+    Metadata *TypeId, const DenseMap<GlobalObject *, uint64_t> &GlobalLayout) {
   BitSetBuilder BSB;
 
   // Compute the byte offset of each address associated with this type
   // identifier.
   SmallVector<MDNode *, 2> Types;
   for (auto &GlobalAndOffset : GlobalLayout) {
     Types.clear();
     GlobalAndOffset.first->getMetadata(LLVMContext::MD_type, Types);
     for (MDNode *Type : Types) {
       if (Type->getOperand(1) != TypeId)
         continue;
       uint64_t Offset =
-          cast<ConstantInt>(cast<ConstantAsMetadata>(Type->getOperand(0))
-                                ->getValue())->getZExtValue();
+          cast<ConstantInt>(
+              cast<ConstantAsMetadata>(Type->getOperand(0))->getValue())
+              ->getZExtValue();
       BSB.addOffset(GlobalAndOffset.second + Offset);
     }
   }
 
   return BSB.build();
 }
 
 /// Build a test that bit BitOffset mod sizeof(Bits)*8 is set in

 }
 
 ByteArrayInfo *LowerTypeTests::createByteArray(BitSetInfo &BSI) {
   // Create globals to stand in for byte arrays and masks. These never actually
   // get initialized, we RAUW and erase them later in allocateByteArrays() once
   // we know the offset and mask to use.
   auto ByteArrayGlobal = new GlobalVariable(
       *M, Int8Ty, /*isConstant=*/true, GlobalValue::PrivateLinkage, nullptr);
-  auto MaskGlobal = new GlobalVariable(
-      *M, Int8Ty, /*isConstant=*/true, GlobalValue::PrivateLinkage, nullptr);
+  auto MaskGlobal = new GlobalVariable(*M, Int8Ty, /*isConstant=*/true,
+                                       GlobalValue::PrivateLinkage, nullptr);
 
   ByteArrayInfos.emplace_back();
   ByteArrayInfo *BAI = &ByteArrayInfos.back();
 
   BAI->Bits = BSI.Bits;
   BAI->BitSize = BSI.BitSize;
   BAI->ByteArray = ByteArrayGlobal;
   BAI->Mask = ConstantExpr::getPtrToInt(MaskGlobal, Int8Ty);
for (CallInst *CI : TypeTestCallSites[TypeId]) {
       CI->replaceAllUsesWith(Lowered);
       CI->eraseFromParent();
     }
   }
 }
 
 void LowerTypeTests::verifyTypeMDNode(GlobalObject *GO, MDNode *Type) {
   if (Type->getNumOperands() != 2)
-    report_fatal_error(
-        "All operands of type metadata must have 2 elements");
+    report_fatal_error("All operands of type metadata must have 2 elements");
 
   if (GO->isThreadLocal())
     report_fatal_error("Bit set element may not be thread-local");
   if (isa<GlobalVariable>(GO) && GO->hasSection())
     report_fatal_error(
         "A member of a type identifier may not have an explicit section");
 
   if (isa<GlobalVariable>(GO) && GO->isDeclarationForLinker())
     report_fatal_error(
         "A global var member of a type identifier must be a definition");
 
   auto OffsetConstMD = dyn_cast<ConstantAsMetadata>(Type->getOperand(0));
   if (!OffsetConstMD)
     report_fatal_error("Type offset must be a constant");
   auto OffsetInt = dyn_cast<ConstantInt>(OffsetConstMD->getValue());
   if (!OffsetInt)
     report_fatal_error("Type offset must be an integer constant");
 }
 
 static const unsigned kX86JumpTableEntrySize = 8;
 
 unsigned LowerTypeTests::getJumpTableEntrySize() {
-  if (Arch != Triple::x86 && Arch != Triple::x86_64)
-    report_fatal_error("Unsupported architecture for jump tables");
-
   return kX86JumpTableEntrySize;
 }
 
 // Create a constant representing a jump table entry for the target. This
 // consists of an instruction sequence containing a relative branch to Dest. The
 // constant will be laid out at address Src+(Len*Distance) where Len is the
 // target-specific jump table entry size.
 Constant *LowerTypeTests::createJumpTableEntry(GlobalObject *Src,
                                                Function *Dest,
                                                unsigned Distance) {
-  if (Arch != Triple::x86 && Arch != Triple::x86_64)
-    report_fatal_error("Unsupported architecture for jump tables");
-
   const unsigned kJmpPCRel32Code = 0xe9;
   const unsigned kInt3Code = 0xcc;
 
   ConstantInt *Jmp = ConstantInt::get(Int8Ty, kJmpPCRel32Code);
 
   // Build a constant representing the displacement between the constant's
   // address and Dest. This will resolve to a PC32 relocation referring to Dest.
   Constant *DestInt = ConstantExpr::getPtrToInt(Dest, IntPtrTy);
   Constant *SrcInt = ConstantExpr::getPtrToInt(Src, IntPtrTy);
   Constant *Disp = ConstantExpr::getSub(DestInt, SrcInt);
   ConstantInt *DispOffset =
       ConstantInt::get(IntPtrTy, Distance * kX86JumpTableEntrySize + 5);
   Constant *OffsetedDisp = ConstantExpr::getSub(Disp, DispOffset);
   OffsetedDisp = ConstantExpr::getTruncOrBitCast(OffsetedDisp, Int32Ty);
 
   ConstantInt *Int3 = ConstantInt::get(Int8Ty, kInt3Code);
 
   Constant *Fields[] = {
       Jmp, OffsetedDisp, Int3, Int3, Int3,
   };
   return ConstantStruct::getAnon(Fields, /*Packed=*/true);
 }
 
 Type *LowerTypeTests::getJumpTableEntryType() {
-  if (Arch != Triple::x86 && Arch != Triple::x86_64)
-    report_fatal_error("Unsupported architecture for jump tables");
-
   return StructType::get(M->getContext(),
                          {Int8Ty, Int32Ty, Int8Ty, Int8Ty, Int8Ty},
                          /*Packed=*/true);
 }
 
-/// Given a disjoint set of type identifiers and functions, build a jump table
-/// for the functions, build the bit sets and lower the llvm.type.test calls.
+/// Given a disjoint set of type identifiers and functions, build the bit sets
+/// and lower the llvm.type.test calls, architecture dependently.
 void LowerTypeTests::buildBitSetsFromFunctions(ArrayRef<Metadata *> TypeIds,
                                                ArrayRef<Function *> Functions) {
+  if (Arch == Triple::x86 || Arch == Triple::x86_64)
+    buildBitSetsFromFunctionsX86(TypeIds, Functions);
+  else if (Arch == Triple::wasm32 || Arch == Triple::wasm64)
+    buildBitSetsFromFunctionsWASM(TypeIds, Functions);
+  else
+    report_fatal_error("Unsupported architecture for jump tables");
+}
+
+/// Given a disjoint set of type identifiers and functions, build a jump table
+/// for the functions, build the bit sets and lower the llvm.type.test calls.
+void LowerTypeTests::buildBitSetsFromFunctionsX86(
+    ArrayRef<Metadata *> TypeIds, ArrayRef<Function *> Functions) {
   // Unlike the global bitset builder, the function bitset builder cannot
   // re-arrange functions in a particular order and base its calculations on the
   // layout of the functions' entry points, as we have no idea how large a
   // particular function will end up being (the size could even depend on what
   // this pass does!) Instead, we build a jump table, which is a block of code
   // consisting of one branch instruction for each of the functions in the bit
   // set that branches to the target function, and redirect any taken function
   // addresses to the corresponding jump table entry. In the object file's
void LowerTypeTests::buildBitSetsFromFunctionsX86(
   std::vector<Constant *> JumpTableEntries;
   for (unsigned I = 0; I != Functions.size(); ++I)
     JumpTableEntries.push_back(
         createJumpTableEntry(JumpTable, Functions[I], I));
   JumpTable->setInitializer(
       ConstantArray::get(JumpTableType, JumpTableEntries));
 }
 
+// Assign a dummy layout based using an incrementing counter, and store this as
+// metadata. During generation of the indexed indirect function call table, the
+// backend will ensure that the appropriate indexes are used.
+void LowerTypeTests::buildBitSetsFromFunctionsWASM(
+    ArrayRef<Metadata *> TypeIds, ArrayRef<Function *> Functions) {
+  assert(!Functions.empty());
+
+  // Build a dummy layout, and generate metadata for indirect function indexes.
+  DenseMap<GlobalObject *, uint64_t> GlobalLayout;
+  for (Function *F : Functions) {
+    // Skip functions which are not actually used, to avoid placing extra
+    // entries in the indirect function table.
+    if (!F->getNumUses())
+      continue;
+
+    MDNode *MD = MDNode::get(F->getContext(),
+                             ArrayRef<Metadata *>(ConstantAsMetadata::get(
+                                 ConstantInt::get(Int64Ty, IndirectIndex))));
+    F->setMetadata("wasm.index", MD);
+
+    GlobalLayout[F] = IndirectIndex++;
+  }
+
+  // The indirect function table index space starts at zero, so pass a NULL
+  // pointer as the subtracted "jump table" offset.
+  lowerTypeTestCalls(TypeIds,
+                     ConstantPointerNull::get(cast<PointerType>(Int32PtrTy)),
+                     GlobalLayout);
+}
+
 void LowerTypeTests::buildBitSetsFromDisjointSet(
     ArrayRef<Metadata *> TypeIds, ArrayRef<GlobalObject *> Globals) {
   llvm::DenseMap<Metadata *, uint64_t> TypeIdIndices;
   for (unsigned I = 0; I != TypeIds.size(); ++I)
     TypeIdIndices[TypeIds[I]] = I;
 
   // For each type identifier, build a set of indices that refer to members of
   // the type identifier.
for (GlobalObject &GO : M->global_objects()) {
     }
   }
 
   for (const Use &U : TypeTestFunc->uses()) {
     auto CI = cast<CallInst>(U.getUser());
 
     auto BitSetMDVal = dyn_cast<MetadataAsValue>(CI->getArgOperand(1));
     if (!BitSetMDVal)
-      report_fatal_error(
-          "Second argument of llvm.type.test must be metadata");
+      report_fatal_error("Second argument of llvm.type.test must be metadata");
     auto BitSet = BitSetMDVal->getMetadata();
 
     // Add the call site to the list of call sites for this type identifier. We
     // also use TypeTestCallSites to keep track of whether we have seen this
     // type identifier before. If we have, we don't need to re-add the
     // referenced globals to the equivalence class.
     std::pair<DenseMap<Metadata *, std::vector<CallInst *>>::iterator, bool>
         Ins = TypeTestCallSites.insert(
if (GlobalClasses.empty())
     return false;
 
   // Build a list of disjoint sets ordered by their maximum global index for
   // determinism.
   std::vector<std::pair<GlobalClassesTy::iterator, unsigned>> Sets;
   for (GlobalClassesTy::iterator I = GlobalClasses.begin(),
                                  E = GlobalClasses.end();
        I != E; ++I) {
-    if (!I->isLeader()) continue;
+    if (!I->isLeader())
+      continue;
     ++NumTypeIdDisjointSets;
 
     unsigned MaxIndex = 0;
     for (GlobalClassesTy::member_iterator MI = GlobalClasses.member_begin(I);
          MI != GlobalClasses.member_end(); ++MI) {
       if ((*MI).is<Metadata *>())
         MaxIndex = std::max(MaxIndex, TypeIdIndices[MI->get<Metadata *>()]);
     }

test/CodeGen/WebAssembly/cfi.ll

+; RUN: opt -S -lowertypetests < %s | llc -asm-verbose=false -disable-wasm-fallthrough-return-opt | FileCheck %s
+
+; Tests that we correctly assign indexes for control flow integrity.
+
+target datalayout = "e-m:e-p:32:32-i64:64-n32:64-S128"
+target triple = "wasm32-unknown-unknown"
+
+; CHECK-LABEL: h:
+; CHECK-NOT: .indidx
+define void @h() !type !0 {
+  ret void
+}
+
+; CHECK-LABEL: f:
+; CHECK: .indidx 0
+define void @f() !type !0 {
+  ret void
+}
+
+; CHECK-LABEL: g:
+; CHECK: .indidx 1
+define void @g() !type !1 {
+  ret void
+}
+
+!0 = !{i32 0, !"typeid1"}
+!1 = !{i32 0, !"typeid2"}
+
+declare i1 @llvm.type.test(i8* %ptr, metadata %bitset) nounwind readnone
+declare void @llvm.trap() nounwind noreturn
+
+; CHECK-LABEL: foo:
+; CHECK: br_if
+; CHECK: br_if
+; CHECK: unreachable
+define i1 @foo(i8* %p) {
+  call void @f()
+  call void @g()
+  %x = call i1 @llvm.type.test(i8* %p, metadata !"typeid1")
+  br i1 %x, label %contx, label %trap
+
+trap:
+  tail call void @llvm.trap() #1
+  unreachable
+
+contx:
+  %y = call i1 @llvm.type.test(i8* %p, metadata !"typeid2")
+  br i1 %y, label %conty, label %trap
+
+conty:
+  %z = add i1 %x, %y
+  ret i1 %z
+}

test/Transforms/LowerTypeTests/function-disjoint.ll

+; RUN: opt -S -lowertypetests -mtriple=x86_64-unknown-linux-gnu < %s | FileCheck --check-prefix=X64 %s
+; RUN: opt -S -lowertypetests -mtriple=wasm32-unknown-unknown < %s | FileCheck --check-prefix=WASM32 %s
+
+; Tests that we correctly handle bitsets with disjoint call target sets.
+
+target datalayout = "e-p:64:64"
+
+; X64: @[[JT0:.*]] = private constant [1 x <{ i8, i32, i8, i8, i8 }>] [<{ i8, i32, i8, i8, i8 }> <{ i8 -23, i32 trunc (i64 sub (i64 sub (i64 ptrtoint (void ()* @[[FNAME:.*]] to i64), i64 ptrtoint ([1 x <{ i8, i32, i8, i8, i8 }>]* @[[JT0]] to i64)), i64 5) to i32), i8 -52, i8 -52, i8 -52 }>], section ".text"
+; X64: @[[JT1:.*]] = private constant [1 x <{ i8, i32, i8, i8, i8 }>] [<{ i8, i32, i8, i8, i8 }> <{ i8 -23, i32 trunc (i64 sub (i64 sub (i64 ptrtoint (void ()* @[[GNAME:.*]] to i64), i64 ptrtoint ([1 x <{ i8, i32, i8, i8, i8 }>]* @[[JT1]] to i64)), i64 5) to i32), i8 -52, i8 -52, i8 -52 }>], section ".text"
+; WASM32: private constant [0 x i8] zeroinitializer
+
+; X64: @f = alias void (), bitcast ([1 x <{ i8, i32, i8, i8, i8 }>]* @[[JT0]] to void ()*)
+; X64: @g = alias void (), bitcast ([1 x <{ i8, i32, i8, i8, i8 }>]* @[[JT1]] to void ()*)
+
+; X64: define private void @[[FNAME]]()
+; WASM32: define void @f() !type !{{[0-9]+}} !wasm.index ![[I0:[0-9]+]]
+define void @f() !type !0 {
+  ret void
+}
+
+; X64: define private void @[[GNAME]]()
+; WASM32: define void @g() !type !{{[0-9]+}} !wasm.index ![[I1:[0-9]+]]
+define void @g() !type !1 {
+  ret void
+}
+
+!0 = !{i32 0, !"typeid1"}
+!1 = !{i32 0, !"typeid2"}
+
+declare i1 @llvm.type.test(i8* %ptr, metadata %bitset) nounwind readnone
+
+define i1 @foo(i8* %p) {
+  call void @f()
+  call void @g()
+  ; X64: icmp eq i64 {{.*}}, ptrtoint ([1 x <{ i8, i32, i8, i8, i8 }>]* @[[JT0]] to i64)
+  ; WASM32: icmp eq i64 {{.*}}, 0
+  %x = call i1 @llvm.type.test(i8* %p, metadata !"typeid1")
+  ; X64: icmp eq i64 {{.*}}, ptrtoint ([1 x <{ i8, i32, i8, i8, i8 }>]* @[[JT1]] to i64)
+  ; WASM32: icmp eq i64 {{.*}}, 1
+  %y = call i1 @llvm.type.test(i8* %p, metadata !"typeid2")
+  %z = add i1 %x, %y
+  ret i1 %z
+}
+
+; WASM32: ![[I0]] = !{i64 0}
+; WASM32: ![[I1]] = !{i64 1}

test/Transforms/LowerTypeTests/function-ext.ll

-; RUN: opt -S -lowertypetests < %s | FileCheck %s
+; RUN: opt -S -lowertypetests -mtriple=x86_64-unknown-linux-gnu < %s | FileCheck --check-prefix=X64 %s
+; RUN: opt -S -lowertypetests -mtriple=wasm32-unknown-unknown < %s | FileCheck --check-prefix=WASM32 %s
 
 ; Tests that we correctly handle external references, including the case where
 ; all functions in a bitset are external references.
 
-target triple = "x86_64-unknown-linux-gnu"
+; X64: @[[JT:.*]] = private constant [1 x <{ i8, i32, i8, i8, i8 }>] [<{ i8, i32, i8, i8, i8 }> <{ i8 -23, i32 trunc (i64 sub (i64 sub (i64 ptrtoint (void ()* @foo to i64), i64 ptrtoint ([1 x <{ i8, i32, i8, i8, i8 }>]* @[[JT]] to i64)), i64 5) to i32), i8 -52, i8 -52, i8 -52 }>], section ".text"
+; WASM32: private constant [0 x i8] zeroinitializer
 
+; WASM32: declare !type !{{[0-9]+}} void @foo()
 declare !type !0 void @foo()
 
-; CHECK: @[[JT:.*]] = private constant [1 x <{ i8, i32, i8, i8, i8 }>] [<{ i8, i32, i8, i8, i8 }> <{ i8 -23, i32 trunc (i64 sub (i64 sub (i64 ptrtoint (void ()* @foo to i64), i64 ptrtoint ([1 x <{ i8, i32, i8, i8, i8 }>]* @[[JT]] to i64)), i64 5) to i32), i8 -52, i8 -52, i8 -52 }>], section ".text"
-
 define i1 @bar(i8* %ptr) {
-  ; CHECK: icmp eq i64 {{.*}}, ptrtoint ([1 x <{ i8, i32, i8, i8, i8 }>]* @[[JT]] to i64)
+  ; X64: icmp eq i64 {{.*}}, ptrtoint ([1 x <{ i8, i32, i8, i8, i8 }>]* @[[JT]] to i64)
+  ; WASM32: sub i64 {{.*}}, 0
+  ; WASM32: icmp ult i64 {{.*}}, 1
   %p = call i1 @llvm.type.test(i8* %ptr, metadata !"void")
   ret i1 %p
 }
 
 declare i1 @llvm.type.test(i8* %ptr, metadata %bitset) nounwind readnone
 
 !0 = !{i64 0, !"void"}
+; WASM-NOT: !{i64 0}

test/Transforms/LowerTypeTests/function.ll

-; RUN: opt -S -lowertypetests < %s | FileCheck %s
+; RUN: opt -S -lowertypetests -mtriple=x86_64-unknown-linux-gnu < %s | FileCheck --check-prefix=X64 %s
+; RUN: opt -S -lowertypetests -mtriple=wasm32-unknown-unknown < %s | FileCheck --check-prefix=WASM32 %s
 
-; Tests that we correctly create a jump table for bitsets containing 2 or more
-; functions.
+; Tests that we correctly handle bitsets containing 2 or more functions.
 
-target triple = "x86_64-unknown-linux-gnu"
 target datalayout = "e-p:64:64"
 
-; CHECK: @[[JT:.*]] = private constant [2 x <{ i8, i32, i8, i8, i8 }>] [<{ i8, i32, i8, i8, i8 }> <{ i8 -23, i32 trunc (i64 sub (i64 sub (i64 ptrtoint (void ()* @[[FNAME:.*]] to i64), i64 ptrtoint ([2 x <{ i8, i32, i8, i8, i8 }>]* @[[JT]] to i64)), i64 5) to i32), i8 -52, i8 -52, i8 -52 }>, <{ i8, i32, i8, i8, i8 }> <{ i8 -23, i32 trunc (i64 sub (i64 sub (i64 ptrtoint (void ()* @[[GNAME:.*]] to i64), i64 ptrtoint ([2 x <{ i8, i32, i8, i8, i8 }>]* @[[JT]] to i64)), i64 13) to i32), i8 -52, i8 -52, i8 -52 }>], section ".text"
+; X64: @[[JT:.*]] = private constant [2 x <{ i8, i32, i8, i8, i8 }>] [<{ i8, i32, i8, i8, i8 }> <{ i8 -23, i32 trunc (i64 sub (i64 sub (i64 ptrtoint (void ()* @[[FNAME:.*]] to i64), i64 ptrtoint ([2 x <{ i8, i32, i8, i8, i8 }>]* @[[JT]] to i64)), i64 5) to i32), i8 -52, i8 -52, i8 -52 }>, <{ i8, i32, i8, i8, i8 }> <{ i8 -23, i32 trunc (i64 sub (i64 sub (i64 ptrtoint (void ()* @[[GNAME:.*]] to i64), i64 ptrtoint ([2 x <{ i8, i32, i8, i8, i8 }>]* @[[JT]] to i64)), i64 13) to i32), i8 -52, i8 -52, i8 -52 }>], section ".text"
+; WASM32: private constant [0 x i8] zeroinitializer
 
-; CHECK: @f = alias void (), bitcast ([2 x <{ i8, i32, i8, i8, i8 }>]* @[[JT]] to void ()*)
-; CHECK: @g = alias void (), bitcast (<{ i8, i32, i8, i8, i8 }>* getelementptr inbounds ([2 x <{ i8, i32, i8, i8, i8 }>], [2 x <{ i8, i32, i8, i8, i8 }>]* @[[JT]], i64 0, i64 1) to void ()*)
+; X64: @f = alias void (), bitcast ([2 x <{ i8, i32, i8, i8, i8 }>]* @[[JT]] to void ()*)
+; X64: @g = alias void (), bitcast (<{ i8, i32, i8, i8, i8 }>* getelementptr inbounds ([2 x <{ i8, i32, i8, i8, i8 }>], [2 x <{ i8, i32, i8, i8, i8 }>]* @[[JT]], i64 0, i64 1) to void ()*)
 
-; CHECK: define private void @[[FNAME]]()
+; X64: define private void @[[FNAME]]()
+; WASM32: define void @f() !type !{{[0-9]+}} !wasm.index ![[I0:[0-9]+]]
 define void @f() !type !0 {
   ret void
 }
 
-; CHECK: define private void @[[GNAME]]()
+; X64: define private void @[[GNAME]]()
+; WASM32: define void @g() !type !{{[0-9]+}} !wasm.index ![[I1:[0-9]+]]
 define void @g() !type !0 {
   ret void
 }
 
 !0 = !{i32 0, !"typeid1"}
 
 declare i1 @llvm.type.test(i8* %ptr, metadata %bitset) nounwind readnone
 
 define i1 @foo(i8* %p) {
-  ; CHECK: sub i64 {{.*}}, ptrtoint ([2 x <{ i8, i32, i8, i8, i8 }>]* @[[JT]] to i64)
+  call void @f()
+  call void @g()
+  ; X64: sub i64 {{.*}}, ptrtoint ([2 x <{ i8, i32, i8, i8, i8 }>]* @[[JT]] to i64)
+  ; WASM32: sub i64 {{.*}}, 0
+  ; WASM32: icmp ult i64 {{.*}}, 2
   %x = call i1 @llvm.type.test(i8* %p, metadata !"typeid1")
   ret i1 %x
 }
+
+; WASM32: ![[I0]] = !{i64 0}
+; WASM32: ![[I1]] = !{i64 1}