[Directize] Add a flag to consider initial table contents immutable (#4942)

In LLVM output and probably others, the initial table contents are never
changed. We may append later, but we don't trample the initial table
entries. As a result, with this new flag we can turn indirect calls on those
offsets into direct ones:

--directize-initial-tables-immutable

3 files changed, 721 insertions, 70 deletions

diff --git a/CHANGELOG.md b/CHANGELOG.md
index f4a008bd2..ab28fd56d 100644
--- a/CHANGELOG.md
+++ b/CHANGELOG.md
@@ -14,6 +14,10 @@ full changeset diff at the end of each section.
 
 Current Trunk
 -------------
+- Add a new flag to Directize, `--pass-arg=directize-initial-contents-immutable`
+  which indicates the initial table contents are immutable. That is the case for
+  LLVM, for example, and it allows us to optimize more indirect calls to direct
+  ones. (#4942)
 - Change constant values of some reference types in the C and JS APIs. This is
   only observable if you hardcode specific values instead of calling the
   relevant methods (like `BinaryenTypeDataref()`). (#4755)
diff --git a/src/passes/Directize.cpp b/src/passes/Directize.cpp
index 5ef870476..ba5280d65 100644
--- a/src/passes/Directize.cpp
+++ b/src/passes/Directize.cpp
@@ -19,6 +19,16 @@
 // the table cannot change, and if we see a constant argument for the
 // indirect call's index.
 //
+// If called with
+//
+//   --pass-arg=directize-initial-contents-immutable
+//
+// then the initial tables' contents are assumed to be immutable. That is, if
+// a table looks like [a, b, c] in the wasm, and we see a call to index 1, we
+// will assume it must call b. It is possible that the table is appended to, but
+// in this mode we assume the initial contents are not overwritten. This is the
+// case for output from LLVM, for example.
+//
 
 #include <unordered_map>
 
@@ -35,28 +45,45 @@ namespace wasm {
 
 namespace {
 
+struct TableInfo {
+  // Whether the table may be modifed at runtime, either because it is imported
+  // or exported, or table.set operations exist for it in the code.
+  bool mayBeModified = false;
+
+  // Whether we can assume that the initial contents are immutable. See the
+  // toplevel comment.
+  bool initialContentsImmutable = false;
+
+  std::unique_ptr<TableUtils::FlatTable> flatTable;
+
+  bool canOptimize() const {
+    // We can optimize if:
+    //  * Either the table can't be modified at all, or it can be modified but
+    //    the initial contents are immutable (so we can optimize them).
+    //  * The table is flat.
+    return (!mayBeModified || initialContentsImmutable) && flatTable->valid;
+  }
+};
+
+using TableInfoMap = std::unordered_map<Name, TableInfo>;
+
 struct FunctionDirectizer : public WalkerPass<PostWalker<FunctionDirectizer>> {
   bool isFunctionParallel() override { return true; }
 
   Pass* create() override { return new FunctionDirectizer(tables); }
 
-  FunctionDirectizer(
-    const std::unordered_map<Name, TableUtils::FlatTable>& tables)
-    : tables(tables) {}
+  FunctionDirectizer(const TableInfoMap& tables) : tables(tables) {}
 
   void visitCallIndirect(CallIndirect* curr) {
-    auto it = tables.find(curr->table);
-    if (it == tables.end()) {
+    auto& table = tables.at(curr->table);
+    if (!table.canOptimize()) {
       return;
     }
-
-    auto& flatTable = it->second;
-
     // If the target is constant, we can emit a direct call.
     if (curr->target->is<Const>()) {
       std::vector<Expression*> operands(curr->operands.begin(),
                                         curr->operands.end());
-      replaceCurrent(makeDirectCall(operands, curr->target, flatTable, curr));
+      makeDirectCall(operands, curr->target, table, curr);
       return;
     }
 
@@ -64,7 +91,7 @@ struct FunctionDirectizer : public WalkerPass<PostWalker<FunctionDirectizer>> {
     if (auto* calls = CallUtils::convertToDirectCalls(
           curr,
           [&](Expression* target) {
-            return getTargetInfo(target, flatTable, curr);
+            return getTargetInfo(target, table, curr);
           },
           *getFunction(),
           *getModule())) {
@@ -85,7 +112,7 @@ struct FunctionDirectizer : public WalkerPass<PostWalker<FunctionDirectizer>> {
   }
 
 private:
-  const std::unordered_map<Name, TableUtils::FlatTable>& tables;
+  const TableInfoMap& tables;
 
   bool changedTypes = false;
 
@@ -93,10 +120,9 @@ private:
   // analyze it and return one of the results of CallUtils::IndirectCallInfo,
   // that is, whether we know a direct call target, or we know it will trap, or
   // if we know nothing.
-  CallUtils::IndirectCallInfo
-  getTargetInfo(Expression* target,
-                const TableUtils::FlatTable& flatTable,
-                CallIndirect* original) {
+  CallUtils::IndirectCallInfo getTargetInfo(Expression* target,
+                                            const TableInfo& table,
+                                            CallIndirect* original) {
     auto* c = target->dynCast<Const>();
     if (!c) {
       return CallUtils::Unknown{};
@@ -104,9 +130,21 @@ private:
 
     Index index = c->value.geti32();
 
-    // If the index is invalid, or the type is wrong, then this will trap.
+    // Check if index is invalid, or the type is wrong.
+    auto& flatTable = *table.flatTable;
     if (index >= flatTable.names.size()) {
-      return CallUtils::Trap{};
+      // The index is out of bounds for the initial table's content. This may
+      // trap, but it may also not trap if the table is modified later (if a
+      // function is appended to it).
+      if (!table.mayBeModified) {
+        return CallUtils::Trap{};
+      } else {
+        // The table may be modified, so it might be appended to. We should only
+        // get here in the case that the initial contents are immutable, as
+        // otherwise we have nothing to optimize at all.
+        assert(table.initialContentsImmutable);
+        return CallUtils::Unknown{};
+      }
     }
     auto name = flatTable.names[index];
     if (!name.is()) {
@@ -121,26 +159,31 @@ private:
 
   // Create a direct call for a given list of operands, an expression which is
   // known to contain a constant indicating the table offset, and the relevant
-  // table. If we can see that the call will trap, instead return an
-  // unreachable.
-  Expression* makeDirectCall(const std::vector<Expression*>& operands,
-                             Expression* c,
-                             const TableUtils::FlatTable& flatTable,
-                             CallIndirect* original) {
+  // table, if we can. If we can see that the call will trap, instead replace
+  // with an unreachable.
+  void makeDirectCall(const std::vector<Expression*>& operands,
+                      Expression* c,
+                      const TableInfo& table,
+                      CallIndirect* original) {
+    auto info = getTargetInfo(c, table, original);
+    if (std::get_if<CallUtils::Unknown>(&info)) {
+      // We don't know anything here.
+      return;
+    }
     // If the index is invalid, or the type is wrong, we can
     // emit an unreachable here, since in Binaryen it is ok to
     // reorder/replace traps when optimizing (but never to
     // remove them, at least not by default).
-    auto info = getTargetInfo(c, flatTable, original);
     if (std::get_if<CallUtils::Trap>(&info)) {
-      return replaceWithUnreachable(operands);
+      replaceCurrent(replaceWithUnreachable(operands));
+      return;
     }
-    assert(std::get_if<CallUtils::Known>(&info));
-    auto name = std::get_if<CallUtils::Known>(&info)->target;
 
     // Everything looks good!
-    return Builder(*getModule())
-      .makeCall(name, operands, original->type, original->isReturn);
+    auto name = std::get<CallUtils::Known>(info).target;
+    replaceCurrent(
+      Builder(*getModule())
+        .makeCall(name, operands, original->type, original->isReturn));
   }
 
   Expression* replaceWithUnreachable(const std::vector<Expression*>& operands) {
@@ -163,11 +206,50 @@ struct Directize : public Pass {
       return;
     }
 
-    // Find which tables are valid to optimize on. They must not be imported nor
-    // exported (so the outside cannot modify them), and must have no sets in
-    // any part of the module.
+    // TODO: consider a per-table option here
+    auto initialContentsImmutable =
+      runner->options.getArgumentOrDefault(
+        "directize-initial-contents-immutable", "") != "";
+
+    // Set up the initial info.
+    TableInfoMap tables;
+    for (auto& table : module->tables) {
+      tables[table->name].initialContentsImmutable = initialContentsImmutable;
+      tables[table->name].flatTable =
+        std::make_unique<TableUtils::FlatTable>(*module, *table);
+    }
+
+    // Next, look at the imports and exports.
+
+    for (auto& table : module->tables) {
+      if (table->imported()) {
+        tables[table->name].mayBeModified = true;
+      }
+    }
+
+    for (auto& ex : module->exports) {
+      if (ex->kind == ExternalKind::Table) {
+        tables[ex->value].mayBeModified = true;
+      }
+    }
+
+    // This may already be enough information to know that we can't optimize
+    // anything. If so, skip scanning all the module contents.
+    auto canOptimize = [&]() {
+      for (auto& [_, info] : tables) {
+        if (info.canOptimize()) {
+          return true;
+        }
+      }
+      return false;
+    };
+
+    if (!canOptimize()) {
+      return;
+    }
+
+    // Find which tables have sets.
 
-    // First, find which tables have sets.
     using TablesWithSet = std::unordered_set<Name>;
 
     ModuleUtils::ParallelFunctionAnalysis<TablesWithSet> analysis(
@@ -180,47 +262,20 @@ struct Directize : public Pass {
         }
       });
 
-    TablesWithSet tablesWithSet;
     for (auto& [_, names] : analysis.map) {
       for (auto name : names) {
-        tablesWithSet.insert(name);
-      }
-    }
-
-    std::unordered_map<Name, TableUtils::FlatTable> validTables;
-
-    for (auto& table : module->tables) {
-      if (table->imported()) {
-        continue;
-      }
-
-      if (tablesWithSet.count(table->name)) {
-        continue;
-      }
-
-      bool canOptimizeCallIndirect = true;
-      for (auto& ex : module->exports) {
-        if (ex->kind == ExternalKind::Table && ex->value == table->name) {
-          canOptimizeCallIndirect = false;
-          break;
-        }
-      }
-      if (!canOptimizeCallIndirect) {
-        continue;
-      }
-
-      // All conditions are valid, this is optimizable.
-      TableUtils::FlatTable flatTable(*module, *table);
-      if (flatTable.valid) {
-        validTables.emplace(table->name, flatTable);
+        tables[name].mayBeModified = true;
       }
     }
 
-    if (validTables.empty()) {
+    // Perhaps the new information about tables with sets shows we cannot
+    // optimize.
+    if (!canOptimize()) {
       return;
     }
 
-    FunctionDirectizer(validTables).run(runner, module);
+    // We can optimize!
+    FunctionDirectizer(tables).run(runner, module);
   }
 };
 
diff --git a/test/lit/passes/directize_all-features.wast b/test/lit/passes/directize_all-features.wast
index 696b43ebf..10bcfc60f 100644
--- a/test/lit/passes/directize_all-features.wast
+++ b/test/lit/passes/directize_all-features.wast
@@ -1,13 +1,16 @@
 ;; NOTE: Assertions have been generated by update_lit_checks.py --all-items and should not be edited.
 ;; NOTE: This test was ported using port_passes_tests_to_lit.py and could be cleaned up.
 
-;; RUN: foreach %s %t wasm-opt --directize --all-features -S -o - | filecheck %s
+;; RUN: foreach %s %t wasm-opt --directize                                                 --all-features -S -o - | filecheck %s --check-prefix=CHECK
+;; RUN: foreach %s %t wasm-opt --directize --pass-arg=directize-initial-contents-immutable --all-features -S -o - | filecheck %s --check-prefix=IMMUT
 
 (module
  ;; CHECK:      (type $ii (func (param i32 i32)))
+ ;; IMMUT:      (type $ii (func (param i32 i32)))
  (type $ii (func (param i32 i32)))
 
  ;; CHECK:      (table $0 5 5 funcref)
+ ;; IMMUT:      (table $0 5 5 funcref)
  (table $0 5 5 funcref)
  (elem (i32.const 1) $foo)
 
@@ -16,6 +19,11 @@
  ;; CHECK:      (func $foo (param $0 i32) (param $1 i32)
  ;; CHECK-NEXT:  (unreachable)
  ;; CHECK-NEXT: )
+ ;; IMMUT:      (elem (i32.const 1) $foo)
+
+ ;; IMMUT:      (func $foo (param $0 i32) (param $1 i32)
+ ;; IMMUT-NEXT:  (unreachable)
+ ;; IMMUT-NEXT: )
  (func $foo (param i32) (param i32)
   ;; helper function
   (unreachable)
@@ -27,6 +35,12 @@
  ;; CHECK-NEXT:   (local.get $y)
  ;; CHECK-NEXT:  )
  ;; CHECK-NEXT: )
+ ;; IMMUT:      (func $bar (param $x i32) (param $y i32)
+ ;; IMMUT-NEXT:  (call $foo
+ ;; IMMUT-NEXT:   (local.get $x)
+ ;; IMMUT-NEXT:   (local.get $y)
+ ;; IMMUT-NEXT:  )
+ ;; IMMUT-NEXT: )
  (func $bar (param $x i32) (param $y i32)
   (call_indirect (type $ii)
    (local.get $x)
@@ -38,12 +52,17 @@
 
 (module
  ;; CHECK:      (type $ii (func (param i32 i32)))
+ ;; IMMUT:      (type $ii (func (param i32 i32)))
  (type $ii (func (param i32 i32)))
  ;; CHECK:      (type $i32_=>_i32 (func (param i32) (result i32)))
 
  ;; CHECK:      (table $0 5 5 funcref)
+ ;; IMMUT:      (type $i32_=>_i32 (func (param i32) (result i32)))
+
+ ;; IMMUT:      (table $0 5 5 funcref)
  (table $0 5 5 funcref)
  ;; CHECK:      (table $1 5 5 funcref)
+ ;; IMMUT:      (table $1 5 5 funcref)
  (table $1 5 5 funcref)
  (elem (table $0) (i32.const 1) func $dummy)
  (elem (table $1) (i32.const 1) func $f)
@@ -54,12 +73,22 @@
  ;; CHECK:      (func $dummy (param $0 i32) (result i32)
  ;; CHECK-NEXT:  (local.get $0)
  ;; CHECK-NEXT: )
+ ;; IMMUT:      (elem $0 (table $0) (i32.const 1) func $dummy)
+
+ ;; IMMUT:      (elem $1 (table $1) (i32.const 1) func $f)
+
+ ;; IMMUT:      (func $dummy (param $0 i32) (result i32)
+ ;; IMMUT-NEXT:  (local.get $0)
+ ;; IMMUT-NEXT: )
  (func $dummy (param i32) (result i32)
   (local.get 0)
  )
  ;; CHECK:      (func $f (param $0 i32) (param $1 i32)
  ;; CHECK-NEXT:  (unreachable)
  ;; CHECK-NEXT: )
+ ;; IMMUT:      (func $f (param $0 i32) (param $1 i32)
+ ;; IMMUT-NEXT:  (unreachable)
+ ;; IMMUT-NEXT: )
  (func $f (param i32) (param i32)
   (unreachable)
  )
@@ -69,6 +98,12 @@
  ;; CHECK-NEXT:   (local.get $y)
  ;; CHECK-NEXT:  )
  ;; CHECK-NEXT: )
+ ;; IMMUT:      (func $g (param $x i32) (param $y i32)
+ ;; IMMUT-NEXT:  (call $f
+ ;; IMMUT-NEXT:   (local.get $x)
+ ;; IMMUT-NEXT:   (local.get $y)
+ ;; IMMUT-NEXT:  )
+ ;; IMMUT-NEXT: )
  (func $g (param $x i32) (param $y i32)
   (call_indirect $1 (type $ii)
    (local.get $x)
@@ -81,10 +116,13 @@
 ;; at table edges
 (module
  ;; CHECK:      (type $ii (func (param i32 i32)))
+ ;; IMMUT:      (type $ii (func (param i32 i32)))
  (type $ii (func (param i32 i32)))
  ;; CHECK:      (table $0 5 5 funcref)
+ ;; IMMUT:      (table $0 5 5 funcref)
  (table $0 5 5 funcref)
  ;; CHECK:      (table $1 5 5 funcref)
+ ;; IMMUT:      (table $1 5 5 funcref)
  (table $1 5 5 funcref)
  (elem (table $1) (i32.const 4) func $foo)
  ;; CHECK:      (elem (table $1) (i32.const 4) func $foo)
@@ -92,6 +130,11 @@
  ;; CHECK:      (func $foo (param $0 i32) (param $1 i32)
  ;; CHECK-NEXT:  (unreachable)
  ;; CHECK-NEXT: )
+ ;; IMMUT:      (elem (table $1) (i32.const 4) func $foo)
+
+ ;; IMMUT:      (func $foo (param $0 i32) (param $1 i32)
+ ;; IMMUT-NEXT:  (unreachable)
+ ;; IMMUT-NEXT: )
  (func $foo (param i32) (param i32)
   (unreachable)
  )
@@ -101,6 +144,12 @@
  ;; CHECK-NEXT:   (local.get $y)
  ;; CHECK-NEXT:  )
  ;; CHECK-NEXT: )
+ ;; IMMUT:      (func $bar (param $x i32) (param $y i32)
+ ;; IMMUT-NEXT:  (call $foo
+ ;; IMMUT-NEXT:   (local.get $x)
+ ;; IMMUT-NEXT:   (local.get $y)
+ ;; IMMUT-NEXT:  )
+ ;; IMMUT-NEXT: )
  (func $bar (param $x i32) (param $y i32)
   (call_indirect $1 (type $ii)
    (local.get $x)
@@ -112,8 +161,10 @@
 
 (module
  ;; CHECK:      (type $ii (func (param i32 i32)))
+ ;; IMMUT:      (type $ii (func (param i32 i32)))
  (type $ii (func (param i32 i32)))
  ;; CHECK:      (table $0 5 5 funcref)
+ ;; IMMUT:      (table $0 5 5 funcref)
  (table $0 5 5 funcref)
  (elem (i32.const 0) $foo)
  ;; CHECK:      (elem (i32.const 0) $foo)
@@ -121,6 +172,11 @@
  ;; CHECK:      (func $foo (param $0 i32) (param $1 i32)
  ;; CHECK-NEXT:  (unreachable)
  ;; CHECK-NEXT: )
+ ;; IMMUT:      (elem (i32.const 0) $foo)
+
+ ;; IMMUT:      (func $foo (param $0 i32) (param $1 i32)
+ ;; IMMUT-NEXT:  (unreachable)
+ ;; IMMUT-NEXT: )
  (func $foo (param i32) (param i32)
   (unreachable)
  )
@@ -130,6 +186,12 @@
  ;; CHECK-NEXT:   (local.get $y)
  ;; CHECK-NEXT:  )
  ;; CHECK-NEXT: )
+ ;; IMMUT:      (func $bar (param $x i32) (param $y i32)
+ ;; IMMUT-NEXT:  (call $foo
+ ;; IMMUT-NEXT:   (local.get $x)
+ ;; IMMUT-NEXT:   (local.get $y)
+ ;; IMMUT-NEXT:  )
+ ;; IMMUT-NEXT: )
  (func $bar (param $x i32) (param $y i32)
   (call_indirect (type $ii)
    (local.get $x)
@@ -141,10 +203,13 @@
 
 (module
  ;; CHECK:      (type $ii (func (param i32 i32)))
+ ;; IMMUT:      (type $ii (func (param i32 i32)))
  (type $ii (func (param i32 i32)))
  ;; CHECK:      (table $0 5 5 funcref)
+ ;; IMMUT:      (table $0 5 5 funcref)
  (table $0 5 5 funcref)
  ;; CHECK:      (table $1 5 5 funcref)
+ ;; IMMUT:      (table $1 5 5 funcref)
  (table $1 5 5 funcref)
  (elem (i32.const 0) $foo $foo $foo $foo $foo)
  (elem (table $1) (i32.const 0) func $foo $foo $foo $foo $foo)
@@ -155,6 +220,13 @@
  ;; CHECK:      (func $foo (param $0 i32) (param $1 i32)
  ;; CHECK-NEXT:  (unreachable)
  ;; CHECK-NEXT: )
+ ;; IMMUT:      (elem $0 (table $0) (i32.const 0) func $foo $foo $foo $foo $foo)
+
+ ;; IMMUT:      (elem $1 (table $1) (i32.const 0) func $foo $foo $foo $foo $foo)
+
+ ;; IMMUT:      (func $foo (param $0 i32) (param $1 i32)
+ ;; IMMUT-NEXT:  (unreachable)
+ ;; IMMUT-NEXT: )
  (func $foo (param i32) (param i32)
   (unreachable)
  )
@@ -164,6 +236,12 @@
  ;; CHECK-NEXT:   (local.get $y)
  ;; CHECK-NEXT:  )
  ;; CHECK-NEXT: )
+ ;; IMMUT:      (func $bar (param $x i32) (param $y i32)
+ ;; IMMUT-NEXT:  (call $foo
+ ;; IMMUT-NEXT:   (local.get $x)
+ ;; IMMUT-NEXT:   (local.get $y)
+ ;; IMMUT-NEXT:  )
+ ;; IMMUT-NEXT: )
  (func $bar (param $x i32) (param $y i32)
   (call_indirect $1 (type $ii)
    (local.get $x)
@@ -173,11 +251,13 @@
  )
 )
 
-;; imported table
+;; imported table. only optimizable in the immutable case.
 (module
  ;; CHECK:      (type $ii (func (param i32 i32)))
+ ;; IMMUT:      (type $ii (func (param i32 i32)))
  (type $ii (func (param i32 i32)))
  ;; CHECK:      (import "env" "table" (table $table 5 5 funcref))
+ ;; IMMUT:      (import "env" "table" (table $table 5 5 funcref))
  (import "env" "table" (table $table 5 5 funcref))
  (elem (i32.const 1) $foo)
  ;; CHECK:      (elem (i32.const 1) $foo)
@@ -185,6 +265,11 @@
  ;; CHECK:      (func $foo (param $0 i32) (param $1 i32)
  ;; CHECK-NEXT:  (unreachable)
  ;; CHECK-NEXT: )
+ ;; IMMUT:      (elem (i32.const 1) $foo)
+
+ ;; IMMUT:      (func $foo (param $0 i32) (param $1 i32)
+ ;; IMMUT-NEXT:  (unreachable)
+ ;; IMMUT-NEXT: )
  (func $foo (param i32) (param i32)
   (unreachable)
  )
@@ -195,6 +280,12 @@
  ;; CHECK-NEXT:   (i32.const 1)
  ;; CHECK-NEXT:  )
  ;; CHECK-NEXT: )
+ ;; IMMUT:      (func $bar (param $x i32) (param $y i32)
+ ;; IMMUT-NEXT:  (call $foo
+ ;; IMMUT-NEXT:   (local.get $x)
+ ;; IMMUT-NEXT:   (local.get $y)
+ ;; IMMUT-NEXT:  )
+ ;; IMMUT-NEXT: )
  (func $bar (param $x i32) (param $y i32)
   (call_indirect (type $ii)
    (local.get $x)
@@ -202,22 +293,55 @@
    (i32.const 1)
   )
  )
+
+ ;; CHECK:      (func $out-of-bounds (param $x i32) (param $y i32)
+ ;; CHECK-NEXT:  (call_indirect $table (type $ii)
+ ;; CHECK-NEXT:   (local.get $x)
+ ;; CHECK-NEXT:   (local.get $y)
+ ;; CHECK-NEXT:   (i32.const 999)
+ ;; CHECK-NEXT:  )
+ ;; CHECK-NEXT: )
+ ;; IMMUT:      (func $out-of-bounds (param $x i32) (param $y i32)
+ ;; IMMUT-NEXT:  (call_indirect $table (type $ii)
+ ;; IMMUT-NEXT:   (local.get $x)
+ ;; IMMUT-NEXT:   (local.get $y)
+ ;; IMMUT-NEXT:   (i32.const 999)
+ ;; IMMUT-NEXT:  )
+ ;; IMMUT-NEXT: )
+ (func $out-of-bounds (param $x i32) (param $y i32)
+  ;; The index here, 999, is out of bounds. We can't optimize that even in the
+  ;; immutable case, since we only assume the initial contents in the table are
+  ;; immutable, and so something might be written to offset 999 later.
+  (call_indirect (type $ii)
+   (local.get $x)
+   (local.get $y)
+   (i32.const 999)
+  )
+ )
 )
 
-;; exported table
+;; exported table. only optimizable in the immutable case.
 (module
  ;; CHECK:      (type $ii (func (param i32 i32)))
+ ;; IMMUT:      (type $ii (func (param i32 i32)))
  (type $ii (func (param i32 i32)))
  ;; CHECK:      (table $0 5 5 funcref)
+ ;; IMMUT:      (table $0 5 5 funcref)
  (table $0 5 5 funcref)
  ;; CHECK:      (elem (i32.const 1) $foo)
 
  ;; CHECK:      (export "tab" (table $0))
+ ;; IMMUT:      (elem (i32.const 1) $foo)
+
+ ;; IMMUT:      (export "tab" (table $0))
  (export "tab" (table $0))
  (elem (i32.const 1) $foo)
  ;; CHECK:      (func $foo (param $0 i32) (param $1 i32)
  ;; CHECK-NEXT:  (unreachable)
  ;; CHECK-NEXT: )
+ ;; IMMUT:      (func $foo (param $0 i32) (param $1 i32)
+ ;; IMMUT-NEXT:  (unreachable)
+ ;; IMMUT-NEXT: )
  (func $foo (param i32) (param i32)
   (unreachable)
  )
@@ -228,6 +352,12 @@
  ;; CHECK-NEXT:   (i32.const 1)
  ;; CHECK-NEXT:  )
  ;; CHECK-NEXT: )
+ ;; IMMUT:      (func $bar (param $x i32) (param $y i32)
+ ;; IMMUT-NEXT:  (call $foo
+ ;; IMMUT-NEXT:   (local.get $x)
+ ;; IMMUT-NEXT:   (local.get $y)
+ ;; IMMUT-NEXT:  )
+ ;; IMMUT-NEXT: )
  (func $bar (param $x i32) (param $y i32)
   (call_indirect (type $ii)
    (local.get $x)
@@ -240,10 +370,14 @@
 ;; non-constant table offset
 (module
  ;; CHECK:      (type $ii (func (param i32 i32)))
+ ;; IMMUT:      (type $ii (func (param i32 i32)))
  (type $ii (func (param i32 i32)))
  ;; CHECK:      (global $g (mut i32) (i32.const 1))
 
  ;; CHECK:      (table $0 5 5 funcref)
+ ;; IMMUT:      (global $g (mut i32) (i32.const 1))
+
+ ;; IMMUT:      (table $0 5 5 funcref)
  (table $0 5 5 funcref)
  (global $g (mut i32) (i32.const 1))
  (elem (global.get $g) $foo)
@@ -252,6 +386,11 @@
  ;; CHECK:      (func $foo (param $0 i32) (param $1 i32)
  ;; CHECK-NEXT:  (unreachable)
  ;; CHECK-NEXT: )
+ ;; IMMUT:      (elem (global.get $g) $foo)
+
+ ;; IMMUT:      (func $foo (param $0 i32) (param $1 i32)
+ ;; IMMUT-NEXT:  (unreachable)
+ ;; IMMUT-NEXT: )
  (func $foo (param i32) (param i32)
   (unreachable)
  )
@@ -262,6 +401,13 @@
  ;; CHECK-NEXT:   (i32.const 1)
  ;; CHECK-NEXT:  )
  ;; CHECK-NEXT: )
+ ;; IMMUT:      (func $bar (param $x i32) (param $y i32)
+ ;; IMMUT-NEXT:  (call_indirect $0 (type $ii)
+ ;; IMMUT-NEXT:   (local.get $x)
+ ;; IMMUT-NEXT:   (local.get $y)
+ ;; IMMUT-NEXT:   (i32.const 1)
+ ;; IMMUT-NEXT:  )
+ ;; IMMUT-NEXT: )
  (func $bar (param $x i32) (param $y i32)
   (call_indirect (type $ii)
    (local.get $x)
@@ -273,12 +419,17 @@
 
 (module
  ;; CHECK:      (type $ii (func (param i32 i32)))
+ ;; IMMUT:      (type $ii (func (param i32 i32)))
  (type $ii (func (param i32 i32)))
  ;; CHECK:      (global $g (mut i32) (i32.const 1))
 
  ;; CHECK:      (table $0 5 5 funcref)
+ ;; IMMUT:      (global $g (mut i32) (i32.const 1))
+
+ ;; IMMUT:      (table $0 5 5 funcref)
  (table $0 5 5 funcref)
  ;; CHECK:      (table $1 5 5 funcref)
+ ;; IMMUT:      (table $1 5 5 funcref)
  (table $1 5 5 funcref)
  (global $g (mut i32) (i32.const 1))
  (elem (table $1) (global.get $g) func $foo)
@@ -287,6 +438,11 @@
  ;; CHECK:      (func $foo (param $0 i32) (param $1 i32)
  ;; CHECK-NEXT:  (unreachable)
  ;; CHECK-NEXT: )
+ ;; IMMUT:      (elem (table $1) (global.get $g) func $foo)
+
+ ;; IMMUT:      (func $foo (param $0 i32) (param $1 i32)
+ ;; IMMUT-NEXT:  (unreachable)
+ ;; IMMUT-NEXT: )
  (func $foo (param i32) (param i32)
   (unreachable)
  )
@@ -297,6 +453,13 @@
  ;; CHECK-NEXT:   (i32.const 1)
  ;; CHECK-NEXT:  )
  ;; CHECK-NEXT: )
+ ;; IMMUT:      (func $bar (param $x i32) (param $y i32)
+ ;; IMMUT-NEXT:  (call_indirect $1 (type $ii)
+ ;; IMMUT-NEXT:   (local.get $x)
+ ;; IMMUT-NEXT:   (local.get $y)
+ ;; IMMUT-NEXT:   (i32.const 1)
+ ;; IMMUT-NEXT:  )
+ ;; IMMUT-NEXT: )
  (func $bar (param $x i32) (param $y i32)
   (call_indirect $1 (type $ii)
    (local.get $x)
@@ -309,10 +472,14 @@
 ;; non-constant call index
 (module
  ;; CHECK:      (type $ii (func (param i32 i32)))
+ ;; IMMUT:      (type $ii (func (param i32 i32)))
  (type $ii (func (param i32 i32)))
  ;; CHECK:      (type $i32_i32_i32_=>_none (func (param i32 i32 i32)))
 
  ;; CHECK:      (table $0 5 5 funcref)
+ ;; IMMUT:      (type $i32_i32_i32_=>_none (func (param i32 i32 i32)))
+
+ ;; IMMUT:      (table $0 5 5 funcref)
  (table $0 5 5 funcref)
  (elem (i32.const 1) $foo)
  ;; CHECK:      (elem (i32.const 1) $foo)
@@ -320,6 +487,11 @@
  ;; CHECK:      (func $foo (param $0 i32) (param $1 i32)
  ;; CHECK-NEXT:  (unreachable)
  ;; CHECK-NEXT: )
+ ;; IMMUT:      (elem (i32.const 1) $foo)
+
+ ;; IMMUT:      (func $foo (param $0 i32) (param $1 i32)
+ ;; IMMUT-NEXT:  (unreachable)
+ ;; IMMUT-NEXT: )
  (func $foo (param i32) (param i32)
   (unreachable)
  )
@@ -330,6 +502,13 @@
  ;; CHECK-NEXT:   (local.get $z)
  ;; CHECK-NEXT:  )
  ;; CHECK-NEXT: )
+ ;; IMMUT:      (func $bar (param $x i32) (param $y i32) (param $z i32)
+ ;; IMMUT-NEXT:  (call_indirect $0 (type $ii)
+ ;; IMMUT-NEXT:   (local.get $x)
+ ;; IMMUT-NEXT:   (local.get $y)
+ ;; IMMUT-NEXT:   (local.get $z)
+ ;; IMMUT-NEXT:  )
+ ;; IMMUT-NEXT: )
  (func $bar (param $x i32) (param $y i32) (param $z i32)
   (call_indirect (type $ii)
    (local.get $x)
@@ -342,8 +521,10 @@
 ;; bad index
 (module
  ;; CHECK:      (type $ii (func (param i32 i32)))
+ ;; IMMUT:      (type $ii (func (param i32 i32)))
  (type $ii (func (param i32 i32)))
  ;; CHECK:      (table $0 5 5 funcref)
+ ;; IMMUT:      (table $0 5 5 funcref)
  (table $0 5 5 funcref)
  (elem (i32.const 1) $foo)
  ;; CHECK:      (elem (i32.const 1) $foo)
@@ -351,6 +532,11 @@
  ;; CHECK:      (func $foo (param $0 i32) (param $1 i32)
  ;; CHECK-NEXT:  (unreachable)
  ;; CHECK-NEXT: )
+ ;; IMMUT:      (elem (i32.const 1) $foo)
+
+ ;; IMMUT:      (func $foo (param $0 i32) (param $1 i32)
+ ;; IMMUT-NEXT:  (unreachable)
+ ;; IMMUT-NEXT: )
  (func $foo (param i32) (param i32)
   (unreachable)
  )
@@ -365,6 +551,17 @@
  ;; CHECK-NEXT:  )
  ;; CHECK-NEXT:  (unreachable)
  ;; CHECK-NEXT: )
+ ;; IMMUT:      (func $bar (param $x i32) (param $y i32)
+ ;; IMMUT-NEXT:  (block
+ ;; IMMUT-NEXT:   (drop
+ ;; IMMUT-NEXT:    (local.get $x)
+ ;; IMMUT-NEXT:   )
+ ;; IMMUT-NEXT:   (drop
+ ;; IMMUT-NEXT:    (local.get $y)
+ ;; IMMUT-NEXT:   )
+ ;; IMMUT-NEXT:  )
+ ;; IMMUT-NEXT:  (unreachable)
+ ;; IMMUT-NEXT: )
  (func $bar (param $x i32) (param $y i32)
   (call_indirect (type $ii)
    (local.get $x)
@@ -377,8 +574,10 @@
 ;; missing index
 (module
  ;; CHECK:      (type $ii (func (param i32 i32)))
+ ;; IMMUT:      (type $ii (func (param i32 i32)))
  (type $ii (func (param i32 i32)))
  ;; CHECK:      (table $0 5 5 funcref)
+ ;; IMMUT:      (table $0 5 5 funcref)
  (table $0 5 5 funcref)
  (elem (i32.const 1) $foo)
  ;; CHECK:      (elem (i32.const 1) $foo)
@@ -386,6 +585,11 @@
  ;; CHECK:      (func $foo (param $0 i32) (param $1 i32)
  ;; CHECK-NEXT:  (unreachable)
  ;; CHECK-NEXT: )
+ ;; IMMUT:      (elem (i32.const 1) $foo)
+
+ ;; IMMUT:      (func $foo (param $0 i32) (param $1 i32)
+ ;; IMMUT-NEXT:  (unreachable)
+ ;; IMMUT-NEXT: )
  (func $foo (param i32) (param i32)
   (unreachable)
  )
@@ -400,6 +604,17 @@
  ;; CHECK-NEXT:  )
  ;; CHECK-NEXT:  (unreachable)
  ;; CHECK-NEXT: )
+ ;; IMMUT:      (func $bar (param $x i32) (param $y i32)
+ ;; IMMUT-NEXT:  (block
+ ;; IMMUT-NEXT:   (drop
+ ;; IMMUT-NEXT:    (local.get $x)
+ ;; IMMUT-NEXT:   )
+ ;; IMMUT-NEXT:   (drop
+ ;; IMMUT-NEXT:    (local.get $y)
+ ;; IMMUT-NEXT:   )
+ ;; IMMUT-NEXT:  )
+ ;; IMMUT-NEXT:  (unreachable)
+ ;; IMMUT-NEXT: )
  (func $bar (param $x i32) (param $y i32)
   (call_indirect (type $ii)
    (local.get $x)
@@ -414,8 +629,12 @@
  ;; CHECK:      (type $i32_=>_none (func (param i32)))
 
  ;; CHECK:      (type $ii (func (param i32 i32)))
+ ;; IMMUT:      (type $i32_=>_none (func (param i32)))
+
+ ;; IMMUT:      (type $ii (func (param i32 i32)))
  (type $ii (func (param i32 i32)))
  ;; CHECK:      (table $0 5 5 funcref)
+ ;; IMMUT:      (table $0 5 5 funcref)
  (table $0 5 5 funcref)
  (elem (i32.const 1) $foo)
  ;; CHECK:      (elem (i32.const 1) $foo)
@@ -423,6 +642,11 @@
  ;; CHECK:      (func $foo (param $0 i32)
  ;; CHECK-NEXT:  (unreachable)
  ;; CHECK-NEXT: )
+ ;; IMMUT:      (elem (i32.const 1) $foo)
+
+ ;; IMMUT:      (func $foo (param $0 i32)
+ ;; IMMUT-NEXT:  (unreachable)
+ ;; IMMUT-NEXT: )
  (func $foo (param i32)
   (unreachable)
  )
@@ -437,6 +661,17 @@
  ;; CHECK-NEXT:  )
  ;; CHECK-NEXT:  (unreachable)
  ;; CHECK-NEXT: )
+ ;; IMMUT:      (func $bar (param $x i32) (param $y i32)
+ ;; IMMUT-NEXT:  (block
+ ;; IMMUT-NEXT:   (drop
+ ;; IMMUT-NEXT:    (local.get $x)
+ ;; IMMUT-NEXT:   )
+ ;; IMMUT-NEXT:   (drop
+ ;; IMMUT-NEXT:    (local.get $y)
+ ;; IMMUT-NEXT:   )
+ ;; IMMUT-NEXT:  )
+ ;; IMMUT-NEXT:  (unreachable)
+ ;; IMMUT-NEXT: )
  (func $bar (param $x i32) (param $y i32)
   (call_indirect (type $ii)
    (local.get $x)
@@ -453,6 +688,11 @@
  ;; CHECK:      (func $foo (param $0 i32)
  ;; CHECK-NEXT:  (unreachable)
  ;; CHECK-NEXT: )
+ ;; IMMUT:      (type $i32_=>_none (func (param i32)))
+
+ ;; IMMUT:      (func $foo (param $0 i32)
+ ;; IMMUT-NEXT:  (unreachable)
+ ;; IMMUT-NEXT: )
  (func $foo (param i32)
   (unreachable)
  )
@@ -464,6 +704,9 @@
  ;; CHECK:      (type $none_=>_none (func))
 
  ;; CHECK:      (table $0 8 8 funcref)
+ ;; IMMUT:      (type $none_=>_none (func))
+
+ ;; IMMUT:      (table $0 8 8 funcref)
  (table $0 8 8 funcref)
  ;; CHECK:      (func $0
  ;; CHECK-NEXT:  (block $block
@@ -475,6 +718,16 @@
  ;; CHECK-NEXT:   )
  ;; CHECK-NEXT:  )
  ;; CHECK-NEXT: )
+ ;; IMMUT:      (func $0
+ ;; IMMUT-NEXT:  (block $block
+ ;; IMMUT-NEXT:   (nop)
+ ;; IMMUT-NEXT:   (block
+ ;; IMMUT-NEXT:    (block
+ ;; IMMUT-NEXT:    )
+ ;; IMMUT-NEXT:    (unreachable)
+ ;; IMMUT-NEXT:   )
+ ;; IMMUT-NEXT:  )
+ ;; IMMUT-NEXT: )
  (func $0
   (block ;; the type of this block will change
    (nop)
@@ -487,8 +740,10 @@
 
 (module ;; indirect tail call
  ;; CHECK:      (type $ii (func (param i32 i32)))
+ ;; IMMUT:      (type $ii (func (param i32 i32)))
  (type $ii (func (param i32 i32)))
  ;; CHECK:      (table $0 5 5 funcref)
+ ;; IMMUT:      (table $0 5 5 funcref)
  (table $0 5 5 funcref)
  (elem (i32.const 1) $foo)
  ;; CHECK:      (elem (i32.const 1) $foo)
@@ -496,6 +751,11 @@
  ;; CHECK:      (func $foo (param $0 i32) (param $1 i32)
  ;; CHECK-NEXT:  (unreachable)
  ;; CHECK-NEXT: )
+ ;; IMMUT:      (elem (i32.const 1) $foo)
+
+ ;; IMMUT:      (func $foo (param $0 i32) (param $1 i32)
+ ;; IMMUT-NEXT:  (unreachable)
+ ;; IMMUT-NEXT: )
  (func $foo (param i32) (param i32)
   (unreachable)
  )
@@ -505,6 +765,12 @@
  ;; CHECK-NEXT:   (local.get $y)
  ;; CHECK-NEXT:  )
  ;; CHECK-NEXT: )
+ ;; IMMUT:      (func $bar (param $x i32) (param $y i32)
+ ;; IMMUT-NEXT:  (return_call $foo
+ ;; IMMUT-NEXT:   (local.get $x)
+ ;; IMMUT-NEXT:   (local.get $y)
+ ;; IMMUT-NEXT:  )
+ ;; IMMUT-NEXT: )
  (func $bar (param $x i32) (param $y i32)
   (return_call_indirect (type $ii)
    (local.get $x)
@@ -518,6 +784,9 @@
  ;; CHECK:      (type $i32_i32_i32_=>_none (func (param i32 i32 i32)))
 
  ;; CHECK:      (type $ii (func (param i32 i32)))
+ ;; IMMUT:      (type $i32_i32_i32_=>_none (func (param i32 i32 i32)))
+
+ ;; IMMUT:      (type $ii (func (param i32 i32)))
  (type $ii (func (param i32 i32)))
 
  (type $none (func))
@@ -525,6 +794,9 @@
  ;; CHECK:      (type $i32_=>_none (func (param i32)))
 
  ;; CHECK:      (table $0 5 5 funcref)
+ ;; IMMUT:      (type $i32_=>_none (func (param i32)))
+
+ ;; IMMUT:      (table $0 5 5 funcref)
  (table $0 5 5 funcref)
  (elem (i32.const 1) $foo1 $foo2)
  ;; CHECK:      (elem (i32.const 1) $foo1 $foo2)
@@ -532,12 +804,20 @@
  ;; CHECK:      (func $foo1 (param $0 i32) (param $1 i32)
  ;; CHECK-NEXT:  (unreachable)
  ;; CHECK-NEXT: )
+ ;; IMMUT:      (elem (i32.const 1) $foo1 $foo2)
+
+ ;; IMMUT:      (func $foo1 (param $0 i32) (param $1 i32)
+ ;; IMMUT-NEXT:  (unreachable)
+ ;; IMMUT-NEXT: )
  (func $foo1 (param i32) (param i32)
   (unreachable)
  )
  ;; CHECK:      (func $foo2 (param $0 i32) (param $1 i32)
  ;; CHECK-NEXT:  (unreachable)
  ;; CHECK-NEXT: )
+ ;; IMMUT:      (func $foo2 (param $0 i32) (param $1 i32)
+ ;; IMMUT-NEXT:  (unreachable)
+ ;; IMMUT-NEXT: )
  (func $foo2 (param i32) (param i32)
   (unreachable)
  )
@@ -562,6 +842,27 @@
  ;; CHECK-NEXT:   )
  ;; CHECK-NEXT:  )
  ;; CHECK-NEXT: )
+ ;; IMMUT:      (func $select (param $x i32) (param $y i32) (param $z i32)
+ ;; IMMUT-NEXT:  (local $3 i32)
+ ;; IMMUT-NEXT:  (local $4 i32)
+ ;; IMMUT-NEXT:  (local.set $3
+ ;; IMMUT-NEXT:   (local.get $x)
+ ;; IMMUT-NEXT:  )
+ ;; IMMUT-NEXT:  (local.set $4
+ ;; IMMUT-NEXT:   (local.get $y)
+ ;; IMMUT-NEXT:  )
+ ;; IMMUT-NEXT:  (if
+ ;; IMMUT-NEXT:   (local.get $z)
+ ;; IMMUT-NEXT:   (call $foo1
+ ;; IMMUT-NEXT:    (local.get $3)
+ ;; IMMUT-NEXT:    (local.get $4)
+ ;; IMMUT-NEXT:   )
+ ;; IMMUT-NEXT:   (call $foo2
+ ;; IMMUT-NEXT:    (local.get $3)
+ ;; IMMUT-NEXT:    (local.get $4)
+ ;; IMMUT-NEXT:   )
+ ;; IMMUT-NEXT:  )
+ ;; IMMUT-NEXT: )
  (func $select (param $x i32) (param $y i32) (param $z i32)
   ;; Test we can optimize a call_indirect whose index is a select between two
   ;; constants. We can emit an if and two direct calls for that.
@@ -586,6 +887,17 @@
  ;; CHECK-NEXT:   )
  ;; CHECK-NEXT:  )
  ;; CHECK-NEXT: )
+ ;; IMMUT:      (func $select-bad-1 (param $x i32) (param $y i32) (param $z i32)
+ ;; IMMUT-NEXT:  (call_indirect $0 (type $ii)
+ ;; IMMUT-NEXT:   (local.get $x)
+ ;; IMMUT-NEXT:   (local.get $y)
+ ;; IMMUT-NEXT:   (select
+ ;; IMMUT-NEXT:    (local.get $z)
+ ;; IMMUT-NEXT:    (i32.const 2)
+ ;; IMMUT-NEXT:    (local.get $z)
+ ;; IMMUT-NEXT:   )
+ ;; IMMUT-NEXT:  )
+ ;; IMMUT-NEXT: )
  (func $select-bad-1 (param $x i32) (param $y i32) (param $z i32)
   ;; As above but one select arm is not constant.
   (call_indirect (type $ii)
@@ -609,6 +921,17 @@
  ;; CHECK-NEXT:   )
  ;; CHECK-NEXT:  )
  ;; CHECK-NEXT: )
+ ;; IMMUT:      (func $select-bad-2 (param $x i32) (param $y i32) (param $z i32)
+ ;; IMMUT-NEXT:  (call_indirect $0 (type $ii)
+ ;; IMMUT-NEXT:   (local.get $x)
+ ;; IMMUT-NEXT:   (local.get $y)
+ ;; IMMUT-NEXT:   (select
+ ;; IMMUT-NEXT:    (i32.const 2)
+ ;; IMMUT-NEXT:    (local.get $z)
+ ;; IMMUT-NEXT:    (local.get $z)
+ ;; IMMUT-NEXT:   )
+ ;; IMMUT-NEXT:  )
+ ;; IMMUT-NEXT: )
  (func $select-bad-2 (param $x i32) (param $y i32) (param $z i32)
   ;; As above but the other select arm is not constant.
   (call_indirect (type $ii)
@@ -639,6 +962,24 @@
  ;; CHECK-NEXT:   )
  ;; CHECK-NEXT:  )
  ;; CHECK-NEXT: )
+ ;; IMMUT:      (func $select-out-of-range (param $x i32) (param $y i32) (param $z i32)
+ ;; IMMUT-NEXT:  (local $3 i32)
+ ;; IMMUT-NEXT:  (local $4 i32)
+ ;; IMMUT-NEXT:  (local.set $3
+ ;; IMMUT-NEXT:   (local.get $x)
+ ;; IMMUT-NEXT:  )
+ ;; IMMUT-NEXT:  (local.set $4
+ ;; IMMUT-NEXT:   (local.get $y)
+ ;; IMMUT-NEXT:  )
+ ;; IMMUT-NEXT:  (if
+ ;; IMMUT-NEXT:   (local.get $z)
+ ;; IMMUT-NEXT:   (unreachable)
+ ;; IMMUT-NEXT:   (call $foo2
+ ;; IMMUT-NEXT:    (local.get $3)
+ ;; IMMUT-NEXT:    (local.get $4)
+ ;; IMMUT-NEXT:   )
+ ;; IMMUT-NEXT:  )
+ ;; IMMUT-NEXT: )
  (func $select-out-of-range (param $x i32) (param $y i32) (param $z i32)
   ;; Both are constants, but one is out of range for the table, and there is no
   ;; valid function to call there; emit an unreachable.
@@ -667,6 +1008,21 @@
  ;; CHECK-NEXT:   (unreachable)
  ;; CHECK-NEXT:  )
  ;; CHECK-NEXT: )
+ ;; IMMUT:      (func $select-both-out-of-range (param $x i32) (param $y i32) (param $z i32)
+ ;; IMMUT-NEXT:  (local $3 i32)
+ ;; IMMUT-NEXT:  (local $4 i32)
+ ;; IMMUT-NEXT:  (local.set $3
+ ;; IMMUT-NEXT:   (local.get $x)
+ ;; IMMUT-NEXT:  )
+ ;; IMMUT-NEXT:  (local.set $4
+ ;; IMMUT-NEXT:   (local.get $y)
+ ;; IMMUT-NEXT:  )
+ ;; IMMUT-NEXT:  (if
+ ;; IMMUT-NEXT:   (local.get $z)
+ ;; IMMUT-NEXT:   (unreachable)
+ ;; IMMUT-NEXT:   (unreachable)
+ ;; IMMUT-NEXT:  )
+ ;; IMMUT-NEXT: )
  (func $select-both-out-of-range (param $x i32) (param $y i32) (param $z i32)
   ;; Both are constants, and both are out of range for the table.
   (call_indirect (type $ii)
@@ -690,6 +1046,17 @@
  ;; CHECK-NEXT:   )
  ;; CHECK-NEXT:  )
  ;; CHECK-NEXT: )
+ ;; IMMUT:      (func $select-unreachable-operand (param $x i32) (param $y i32) (param $z i32)
+ ;; IMMUT-NEXT:  (call_indirect $0 (type $ii)
+ ;; IMMUT-NEXT:   (local.get $x)
+ ;; IMMUT-NEXT:   (local.get $y)
+ ;; IMMUT-NEXT:   (select
+ ;; IMMUT-NEXT:    (unreachable)
+ ;; IMMUT-NEXT:    (i32.const 2)
+ ;; IMMUT-NEXT:    (local.get $z)
+ ;; IMMUT-NEXT:   )
+ ;; IMMUT-NEXT:  )
+ ;; IMMUT-NEXT: )
  (func $select-unreachable-operand (param $x i32) (param $y i32) (param $z i32)
   ;; One operand is unreachable.
   (call_indirect (type $ii)
@@ -713,6 +1080,17 @@
  ;; CHECK-NEXT:   )
  ;; CHECK-NEXT:  )
  ;; CHECK-NEXT: )
+ ;; IMMUT:      (func $select-unreachable-condition (param $x i32) (param $y i32) (param $z i32)
+ ;; IMMUT-NEXT:  (call_indirect $0 (type $ii)
+ ;; IMMUT-NEXT:   (local.get $x)
+ ;; IMMUT-NEXT:   (local.get $y)
+ ;; IMMUT-NEXT:   (select
+ ;; IMMUT-NEXT:    (i32.const 1)
+ ;; IMMUT-NEXT:    (i32.const 2)
+ ;; IMMUT-NEXT:    (unreachable)
+ ;; IMMUT-NEXT:   )
+ ;; IMMUT-NEXT:  )
+ ;; IMMUT-NEXT: )
  (func $select-unreachable-condition (param $x i32) (param $y i32) (param $z i32)
   ;; The condition is unreachable. We should not even create any vars here, and
   ;; just not do anything.
@@ -733,6 +1111,13 @@
  ;; CHECK-NEXT:   (unreachable)
  ;; CHECK-NEXT:  )
  ;; CHECK-NEXT: )
+ ;; IMMUT:      (func $select-bad-type (param $z i32)
+ ;; IMMUT-NEXT:  (if
+ ;; IMMUT-NEXT:   (local.get $z)
+ ;; IMMUT-NEXT:   (unreachable)
+ ;; IMMUT-NEXT:   (unreachable)
+ ;; IMMUT-NEXT:  )
+ ;; IMMUT-NEXT: )
  (func $select-bad-type (param $z i32)
   ;; The type here is $none, which does not match the functions at indexes 1 and
   ;; 2, so we know they will trap and can emit unreachables.
@@ -754,6 +1139,13 @@
  ;; CHECK:      (type $none_=>_none (func))
 
  ;; CHECK:      (table $0 15 15 funcref)
+ ;; IMMUT:      (type $F (func (param (ref func))))
+
+ ;; IMMUT:      (type $i32_=>_none (func (param i32)))
+
+ ;; IMMUT:      (type $none_=>_none (func))
+
+ ;; IMMUT:      (table $0 15 15 funcref)
  (table $0 15 15 funcref)
  (type $F (func (param (ref func))))
  (elem (i32.const 10) $foo-ref $foo-ref)
@@ -765,6 +1157,13 @@
  ;; CHECK:      (func $foo-ref (param $0 (ref func))
  ;; CHECK-NEXT:  (unreachable)
  ;; CHECK-NEXT: )
+ ;; IMMUT:      (elem (i32.const 10) $foo-ref $foo-ref)
+
+ ;; IMMUT:      (elem declare func $select-non-nullable)
+
+ ;; IMMUT:      (func $foo-ref (param $0 (ref func))
+ ;; IMMUT-NEXT:  (unreachable)
+ ;; IMMUT-NEXT: )
  (func $foo-ref (param (ref func))
   ;; helper function
   (unreachable)
@@ -789,6 +1188,25 @@
  ;; CHECK-NEXT:   )
  ;; CHECK-NEXT:  )
  ;; CHECK-NEXT: )
+ ;; IMMUT:      (func $select-non-nullable (param $x i32)
+ ;; IMMUT-NEXT:  (local $1 (ref null $i32_=>_none))
+ ;; IMMUT-NEXT:  (local.set $1
+ ;; IMMUT-NEXT:   (ref.func $select-non-nullable)
+ ;; IMMUT-NEXT:  )
+ ;; IMMUT-NEXT:  (if
+ ;; IMMUT-NEXT:   (local.get $x)
+ ;; IMMUT-NEXT:   (call $foo-ref
+ ;; IMMUT-NEXT:    (ref.as_non_null
+ ;; IMMUT-NEXT:     (local.get $1)
+ ;; IMMUT-NEXT:    )
+ ;; IMMUT-NEXT:   )
+ ;; IMMUT-NEXT:   (call $foo-ref
+ ;; IMMUT-NEXT:    (ref.as_non_null
+ ;; IMMUT-NEXT:     (local.get $1)
+ ;; IMMUT-NEXT:    )
+ ;; IMMUT-NEXT:   )
+ ;; IMMUT-NEXT:  )
+ ;; IMMUT-NEXT: )
  (func $select-non-nullable (param $x i32)
   ;; Test we can handle a non-nullable value when optimizing a select, during
   ;; which we place values in locals.
@@ -812,6 +1230,16 @@
  ;; CHECK-NEXT:   )
  ;; CHECK-NEXT:  )
  ;; CHECK-NEXT: )
+ ;; IMMUT:      (func $select-non-nullable-unreachable-condition
+ ;; IMMUT-NEXT:  (call_indirect $0 (type $F)
+ ;; IMMUT-NEXT:   (ref.func $select-non-nullable)
+ ;; IMMUT-NEXT:   (select
+ ;; IMMUT-NEXT:    (i32.const 10)
+ ;; IMMUT-NEXT:    (i32.const 11)
+ ;; IMMUT-NEXT:    (unreachable)
+ ;; IMMUT-NEXT:   )
+ ;; IMMUT-NEXT:  )
+ ;; IMMUT-NEXT: )
  (func $select-non-nullable-unreachable-condition
   ;; Test we ignore an unreachable condition and don't make any changes at all
   ;; to the code (in particular, we shouldn't add any vars).
@@ -835,6 +1263,16 @@
  ;; CHECK-NEXT:   )
  ;; CHECK-NEXT:  )
  ;; CHECK-NEXT: )
+ ;; IMMUT:      (func $select-non-nullable-unreachable-arg (param $x i32)
+ ;; IMMUT-NEXT:  (call_indirect $0 (type $F)
+ ;; IMMUT-NEXT:   (unreachable)
+ ;; IMMUT-NEXT:   (select
+ ;; IMMUT-NEXT:    (i32.const 10)
+ ;; IMMUT-NEXT:    (i32.const 11)
+ ;; IMMUT-NEXT:    (local.get $x)
+ ;; IMMUT-NEXT:   )
+ ;; IMMUT-NEXT:  )
+ ;; IMMUT-NEXT: )
  (func $select-non-nullable-unreachable-arg (param $x i32)
   ;; Test we ignore an unreachable argument and don't make any changes at all
   ;; to the code (in particular, we shouldn't add any vars).
@@ -852,18 +1290,23 @@
 ;; A table.set prevents optimization.
 (module
  ;; CHECK:      (type $v (func))
+ ;; IMMUT:      (type $v (func))
  (type $v (func))
 
  ;; CHECK:      (table $has-set 5 5 funcref)
+ ;; IMMUT:      (table $has-set 5 5 funcref)
  (table $has-set 5 5 funcref)
 
  ;; CHECK:      (table $no-set 5 5 funcref)
+ ;; IMMUT:      (table $no-set 5 5 funcref)
  (table $no-set 5 5 funcref)
 
  ;; CHECK:      (elem $0 (table $has-set) (i32.const 1) func $foo)
+ ;; IMMUT:      (elem $0 (table $has-set) (i32.const 1) func $foo)
  (elem $0 (table $has-set) (i32.const 1) $foo)
 
  ;; CHECK:      (elem $1 (table $no-set) (i32.const 1) func $foo)
+ ;; IMMUT:      (elem $1 (table $no-set) (i32.const 1) func $foo)
  (elem $1 (table $no-set) (i32.const 1) $foo)
 
  ;; CHECK:      (func $foo
@@ -872,6 +1315,12 @@
  ;; CHECK-NEXT:   (ref.func $foo)
  ;; CHECK-NEXT:  )
  ;; CHECK-NEXT: )
+ ;; IMMUT:      (func $foo
+ ;; IMMUT-NEXT:  (table.set $has-set
+ ;; IMMUT-NEXT:   (i32.const 1)
+ ;; IMMUT-NEXT:   (ref.func $foo)
+ ;; IMMUT-NEXT:  )
+ ;; IMMUT-NEXT: )
  (func $foo
   ;; Technically this set writes the same value as is already there, but the
   ;; analysis will give up on optimizing when it sees any set to a table.
@@ -887,8 +1336,13 @@
  ;; CHECK-NEXT:  )
  ;; CHECK-NEXT:  (call $foo)
  ;; CHECK-NEXT: )
+ ;; IMMUT:      (func $bar
+ ;; IMMUT-NEXT:  (call $foo)
+ ;; IMMUT-NEXT:  (call $foo)
+ ;; IMMUT-NEXT: )
  (func $bar
-  ;; We can't optimize this one, but we can the one after it.
+  ;; We can't optimize this one, but we can the one after it. (But we can
+  ;; optimize both in the immutable case.)
   (call_indirect $has-set (type $v)
    (i32.const 1)
   )
@@ -897,3 +1351,141 @@
   )
  )
 )
+
+;; An imported table with a non-contiguous range in the initial contents.
+(module
+ ;; CHECK:      (type $ii (func (param i32 i32)))
+ ;; IMMUT:      (type $ii (func (param i32 i32)))
+ (type $ii (func (param i32 i32)))
+
+ ;; CHECK:      (import "env" "table" (table $table 5 5 funcref))
+ ;; IMMUT:      (import "env" "table" (table $table 5 5 funcref))
+ (import "env" "table" (table $table 5 5 funcref))
+ (elem (i32.const 1) $foo1)
+ (elem (i32.const 3) $foo2)
+
+ ;; CHECK:      (elem $0 (i32.const 1) $foo1)
+
+ ;; CHECK:      (elem $1 (i32.const 3) $foo2)
+
+ ;; CHECK:      (func $foo1 (param $0 i32) (param $1 i32)
+ ;; CHECK-NEXT:  (unreachable)
+ ;; CHECK-NEXT: )
+ ;; IMMUT:      (elem $0 (i32.const 1) $foo1)
+
+ ;; IMMUT:      (elem $1 (i32.const 3) $foo2)
+
+ ;; IMMUT:      (func $foo1 (param $0 i32) (param $1 i32)
+ ;; IMMUT-NEXT:  (unreachable)
+ ;; IMMUT-NEXT: )
+ (func $foo1 (param i32) (param i32)
+  (unreachable)
+ )
+ ;; CHECK:      (func $foo2 (param $0 i32) (param $1 i32)
+ ;; CHECK-NEXT:  (unreachable)
+ ;; CHECK-NEXT: )
+ ;; IMMUT:      (func $foo2 (param $0 i32) (param $1 i32)
+ ;; IMMUT-NEXT:  (unreachable)
+ ;; IMMUT-NEXT: )
+ (func $foo2 (param i32) (param i32)
+  (unreachable)
+ )
+
+ ;; CHECK:      (func $bar (param $x i32) (param $y i32)
+ ;; CHECK-NEXT:  (call_indirect $table (type $ii)
+ ;; CHECK-NEXT:   (local.get $x)
+ ;; CHECK-NEXT:   (local.get $y)
+ ;; CHECK-NEXT:   (i32.const 0)
+ ;; CHECK-NEXT:  )
+ ;; CHECK-NEXT:  (call_indirect $table (type $ii)
+ ;; CHECK-NEXT:   (local.get $x)
+ ;; CHECK-NEXT:   (local.get $y)
+ ;; CHECK-NEXT:   (i32.const 1)
+ ;; CHECK-NEXT:  )
+ ;; CHECK-NEXT:  (call_indirect $table (type $ii)
+ ;; CHECK-NEXT:   (local.get $x)
+ ;; CHECK-NEXT:   (local.get $y)
+ ;; CHECK-NEXT:   (i32.const 2)
+ ;; CHECK-NEXT:  )
+ ;; CHECK-NEXT:  (call_indirect $table (type $ii)
+ ;; CHECK-NEXT:   (local.get $x)
+ ;; CHECK-NEXT:   (local.get $y)
+ ;; CHECK-NEXT:   (i32.const 3)
+ ;; CHECK-NEXT:  )
+ ;; CHECK-NEXT:  (call_indirect $table (type $ii)
+ ;; CHECK-NEXT:   (local.get $x)
+ ;; CHECK-NEXT:   (local.get $y)
+ ;; CHECK-NEXT:   (i32.const 4)
+ ;; CHECK-NEXT:  )
+ ;; CHECK-NEXT: )
+ ;; IMMUT:      (func $bar (param $x i32) (param $y i32)
+ ;; IMMUT-NEXT:  (block
+ ;; IMMUT-NEXT:   (block
+ ;; IMMUT-NEXT:    (drop
+ ;; IMMUT-NEXT:     (local.get $x)
+ ;; IMMUT-NEXT:    )
+ ;; IMMUT-NEXT:    (drop
+ ;; IMMUT-NEXT:     (local.get $y)
+ ;; IMMUT-NEXT:    )
+ ;; IMMUT-NEXT:   )
+ ;; IMMUT-NEXT:   (unreachable)
+ ;; IMMUT-NEXT:  )
+ ;; IMMUT-NEXT:  (call $foo1
+ ;; IMMUT-NEXT:   (local.get $x)
+ ;; IMMUT-NEXT:   (local.get $y)
+ ;; IMMUT-NEXT:  )
+ ;; IMMUT-NEXT:  (block
+ ;; IMMUT-NEXT:   (block
+ ;; IMMUT-NEXT:    (drop
+ ;; IMMUT-NEXT:     (local.get $x)
+ ;; IMMUT-NEXT:    )
+ ;; IMMUT-NEXT:    (drop
+ ;; IMMUT-NEXT:     (local.get $y)
+ ;; IMMUT-NEXT:    )
+ ;; IMMUT-NEXT:   )
+ ;; IMMUT-NEXT:   (unreachable)
+ ;; IMMUT-NEXT:  )
+ ;; IMMUT-NEXT:  (call $foo2
+ ;; IMMUT-NEXT:   (local.get $x)
+ ;; IMMUT-NEXT:   (local.get $y)
+ ;; IMMUT-NEXT:  )
+ ;; IMMUT-NEXT:  (call_indirect $table (type $ii)
+ ;; IMMUT-NEXT:   (local.get $x)
+ ;; IMMUT-NEXT:   (local.get $y)
+ ;; IMMUT-NEXT:   (i32.const 4)
+ ;; IMMUT-NEXT:  )
+ ;; IMMUT-NEXT: )
+ (func $bar (param $x i32) (param $y i32)
+  ;; When assuming the initial contents are immutable, we can optimize some
+  ;; of these cases. 0 and 2 are offsets that are known to contain a null, so
+  ;; they will trap, and 1 and 3 contain known contents we can do a direct call
+  ;; to. 4 is out of bounds so we cannot optimize there. (And in all of these,
+  ;; we cannot optimize anything in the non-immutable case, since the table is
+  ;; imported.)
+  (call_indirect (type $ii)
+   (local.get $x)
+   (local.get $y)
+   (i32.const 0)
+  )
+  (call_indirect (type $ii)
+   (local.get $x)
+   (local.get $y)
+   (i32.const 1)
+  )
+  (call_indirect (type $ii)
+   (local.get $x)
+   (local.get $y)
+   (i32.const 2)
+  )
+  (call_indirect (type $ii)
+   (local.get $x)
+   (local.get $y)
+   (i32.const 3)
+  )
+  (call_indirect (type $ii)
+   (local.get $x)
+   (local.get $y)
+   (i32.const 4)
+  )
+ )
+)