PNaCl: Implement computed gotos (indirectbr) by expanding out to switches

lib/Transforms/NaCl/ExpandIndirectBr.cpp

Index: lib/Transforms/NaCl/ExpandIndirectBr.cpp
diff --git a/lib/Transforms/NaCl/ExpandIndirectBr.cpp b/lib/Transforms/NaCl/ExpandIndirectBr.cpp
new file mode 100644
index 0000000000000000000000000000000000000000..63e44d5567c69b77e25b5f470da5a70e4a6aa44a
--- /dev/null
+++ b/lib/Transforms/NaCl/ExpandIndirectBr.cpp
@@ -0,0 +1,152 @@
+//===- ExpandIndirectBr.cpp - Expand out indirectbr and blockaddress-------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This pass expands out indirectbr instructions and blockaddress
+// ConstantExprs, which are not currently supported in PNaCl's stable
+// ABI.  indirectbr is used to implement computed gotos (a GNU
+// extension to C).  This pass replaces indirectbr instructions with
+// switch instructions.
+//
+// The resulting use of switches might not be as fast as the original
+// indirectbrs.  If you are compiling a program that has a
+// compile-time option for using computed gotos, it's possible that
+// the program will run faster with the option turned off than with
+// using computed gotos + ExpandIndirectBr (for example, if the
+// program does extra work to take advantage of computed gotos).
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/DenseSet.h"
+#include "llvm/IR/Constants.h"
+#include "llvm/IR/Instructions.h"
+#include "llvm/IR/Module.h"
+#include "llvm/Pass.h"
+#include "llvm/Transforms/NaCl.h"
+
+using namespace llvm;
+
+namespace {
+  // This is a ModulePass so that it can expand out blockaddress
+  // ConstantExprs inside global variable initializers.
+  class ExpandIndirectBr : public ModulePass {
+  public:
+    static char ID; // Pass identification, replacement for typeid
+    ExpandIndirectBr() : ModulePass(ID) {
+      initializeExpandIndirectBrPass(*PassRegistry::getPassRegistry());
+    }
+
+    virtual bool runOnModule(Module &M);
+  };
+}
+
+char ExpandIndirectBr::ID = 0;
+INITIALIZE_PASS(ExpandIndirectBr, "expand-indirectbr",
+                "Expand out indirectbr and blockaddress (computed gotos)",
+                false, false)
+
+static bool convertFunction(Function *Func) {
+  bool Changed = false;
+  IntegerType *I32 = Type::getInt32Ty(Func->getContext());
+
+  // Skip zero in case programs treat a null pointer as special.
+  uint32_t NextNum = 1;
+  DenseMap<BasicBlock *, ConstantInt *> LabelNums;
+  BasicBlock *DefaultBB = NULL;
+
+  // Replace each indirectbr with a switch.
+  //
+  // If there are multiple indirectbr instructions in the function,
+  // this could be expensive.  While an indirectbr is usually
+  // converted to O(1) machine instructions, the switch we generate
+  // here will be O(n) in the number of target labels.
+  //
+  // However, Clang usually generates just a single indirectbr per
+  // function anyway when compiling C computed gotos.
+  //
+  // We could try to generate one switch to handle all the indirectbr
+  // instructions in the function, but that would be complicated to
+  // implement given that variables that are live at one indirectbr
+  // might not be live at others.
+  for (llvm::Function::iterator BB = Func->begin(), E = Func->end();
+       BB != E; ++BB) {
+    if (IndirectBrInst *Br = dyn_cast<IndirectBrInst>(BB->getTerminator())) {
+      Changed = true;
+
+      if (!DefaultBB) {
+        DefaultBB = BasicBlock::Create(Func->getContext(),
+                                       "indirectbr_default", Func);
+        new UnreachableInst(Func->getContext(), DefaultBB);
+      }
+
+      // An indirectbr can list the same target block multiple times.
+      // Keep track of the basic blocks we've handled to avoid adding
+      // the same case multiple times.
+      DenseSet<BasicBlock *> BlocksSeen;
+
+      Value *Cast = new PtrToIntInst(Br->getAddress(), I32,
+                                     "indirectbr_cast", Br);
+      unsigned Count = Br->getNumSuccessors();
+      SwitchInst *Switch = SwitchInst::Create(Cast, DefaultBB, Count, Br);
+      for (unsigned I = 0; I < Count; ++I) {
+        BasicBlock *Dest = Br->getSuccessor(I);
+        if (!BlocksSeen.insert(Dest).second) {
+          // Remove duplicated entries from phi nodes.
+          for (BasicBlock::iterator Inst = Dest->begin(); ; ++Inst) {
+            PHINode *Phi = dyn_cast<PHINode>(Inst);
+            if (!Phi)
+              break;
+            Phi->removeIncomingValue(Br->getParent());
+          }
+          continue;
+        }
+        ConstantInt *Val;
+        if (LabelNums.count(Dest) == 0) {
+          Val = ConstantInt::get(I32, NextNum++);
+          LabelNums[Dest] = Val;
+
+          BlockAddress *BA = BlockAddress::get(Func, Dest);
+          Value *ValAsPtr = ConstantExpr::getIntToPtr(Val, BA->getType());
+          BA->replaceAllUsesWith(ValAsPtr);
+          BA->destroyConstant();
+        } else {
+          Val = LabelNums[Dest];
+        }
+        Switch->addCase(Val, Br->getSuccessor(I));
+      }
+      Br->eraseFromParent();
+    }
+  }
+
+  // If there are any blockaddresses that are never used by an
+  // indirectbr, replace them with dummy values.

[Derek Schuff, 2014/01/06 22:30:22]

Why do this rather than just destroying them?

[Mark Seaborn, 2014/01/06 22:36:02]

Because they might be used, so you can't just destroy them.  The blockaddress
has to evaluate to something.

e.g.
void *foo() {
  return &&label;
label:
  return 0;
}

This might happen in less silly code if the indirectbrs are deleted by dead code
elimination.

[Derek Schuff, 2014/01/07 00:35:01]

Ah, i didn't think there about legitimate uses other than indirectbr

+  for (Value::use_iterator UI = Func->use_begin(), E = Func->use_end();
+       UI != E; ++UI) {
+    if (BlockAddress *BA = dyn_cast<BlockAddress>(*UI)) {
+      Changed = true;
+      Value *DummyVal = ConstantExpr::getIntToPtr(ConstantInt::get(I32, ~0L),
+                                                  BA->getType());
+      BA->replaceAllUsesWith(DummyVal);
+      BA->destroyConstant();
+    }
+  }
+  return Changed;
+}
+
+bool ExpandIndirectBr::runOnModule(Module &M) {
+  bool Changed = false;
+  for (Module::iterator Func = M.begin(), E = M.end(); Func != E; ++Func) {
+    Changed |= convertFunction(Func);
+  }
+  return Changed;
+}
+
+ModulePass *llvm::createExpandIndirectBrPass() {
+  return new ExpandIndirectBr();
+}