JumpTable support! What this represents is working asm and jit support for

x86 and ppc for 100% dense switch statements when relocations are non-PIC.
This support will be extended and enhanced in the coming days to support
PIC, and less dense forms of jump tables.


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@27947 91177308-0d34-0410-b5e6-96231b3b80d8

40 files changed, 717 insertions, 77 deletions

diff --git a/include/llvm/CodeGen/AsmPrinter.h b/include/llvm/CodeGen/AsmPrinter.h
index bb948ebc9d..2a56543612 100644
--- a/include/llvm/CodeGen/AsmPrinter.h
+++ b/include/llvm/CodeGen/AsmPrinter.h
@@ -140,6 +140,10 @@ namespace llvm {
     /// before emitting the constant pool for a function.
     const char *ConstantPoolSection;     // Defaults to "\t.section .rodata\n"
 
+    /// JumpTableSection - This is the section that we SwitchToSection right
+    /// before emitting the jump tables for a function.
+    const char *JumpTableSection;     // Defaults to "\t.section .rodata\n"
+    
     /// StaticCtorsSection - This is the directive that is emitted to switch to
     /// a section to emit the static constructor list.
     /// Defaults to "\t.section .ctors,\"aw\",@progbits".
@@ -231,6 +235,11 @@ namespace llvm {
     ///
     void EmitConstantPool(MachineConstantPool *MCP);
 
+    /// EmitJumpTableInfo - Print assembly representations of the jump tables 
+    /// used by the current function to the current output stream.  
+    ///
+    void EmitJumpTableInfo(MachineJumpTableInfo *MJTI);
+    
     /// EmitSpecialLLVMGlobal - Check to see if the specified global is a
     /// special global used by LLVM.  If so, emit it and return true, otherwise
     /// do nothing and return false.
@@ -257,6 +266,11 @@ namespace llvm {
     /// printInlineAsm - This method formats and prints the specified machine
     /// instruction that is an inline asm.
     void printInlineAsm(const MachineInstr *MI) const;
+    
+    /// printBasicBlockLabel - This method prints the label for the specified
+    /// MachineBasicBlock
+    virtual void printBasicBlockLabel(const MachineBasicBlock *MBB) const;
+    
   private:
     void EmitXXStructorList(Constant *List);
 
diff --git a/include/llvm/CodeGen/MachineCodeEmitter.h b/include/llvm/CodeGen/MachineCodeEmitter.h
index f5ee2e6237..f4b7c2290d 100644
--- a/include/llvm/CodeGen/MachineCodeEmitter.h
+++ b/include/llvm/CodeGen/MachineCodeEmitter.h
@@ -18,11 +18,13 @@
 #define LLVM_CODEGEN_MACHINECODEEMITTER_H
 
 #include "llvm/Support/DataTypes.h"
+#include <map>
 
 namespace llvm {
 
 class MachineBasicBlock;
 class MachineConstantPool;
+class MachineJumpTableInfo;
 class MachineFunction;
 class MachineRelocation;
 class Value;
@@ -47,6 +49,17 @@ public:
   /// for the function.
   virtual void emitConstantPool(MachineConstantPool *MCP) {}
 
+  /// initJumpTableInfo - This callback is invoked by the JIT to allocate the
+  /// necessary memory to hold the jump tables.
+  virtual void initJumpTableInfo(MachineJumpTableInfo *MJTI) {}
+  
+  /// emitJumpTableInfo - This callback is invoked to output the jump tables
+  /// for the function.  In addition to a pointer to the MachineJumpTableInfo,
+  /// this function also takes a map of MBBs to addresses, so that the final
+  /// addresses of the MBBs can be written to the jump tables.
+  virtual void emitJumpTableInfo(MachineJumpTableInfo *MJTI,
+                                 std::map<MachineBasicBlock*,uint64_t> &MBBM) {}
+  
   /// startFunctionStub - This callback is invoked when the JIT needs the
   /// address of a function that has not been code generated yet.  The StubSize
   /// specifies the total size required by the stub.  Stubs are not allowed to
@@ -94,6 +107,11 @@ public:
   //
   virtual uint64_t getConstantPoolEntryAddress(unsigned Index) = 0;
 
+  // getJumpTablelEntryAddress - Return the address of the jump table with index
+  // 'Index' in the function that last called initJumpTableInfo.
+  //
+  virtual uint64_t getJumpTableEntryAddress(unsigned Index) = 0;
+  
   // allocateGlobal - Allocate some space for a global variable.
   virtual unsigned char* allocateGlobal(unsigned size, unsigned alignment) = 0;
 
diff --git a/include/llvm/CodeGen/MachineFunction.h b/include/llvm/CodeGen/MachineFunction.h
index 83f696f5d7..0f511e3d91 100644
--- a/include/llvm/CodeGen/MachineFunction.h
+++ b/include/llvm/CodeGen/MachineFunction.h
@@ -29,6 +29,7 @@ class TargetMachine;
 class SSARegMap;
 class MachineFrameInfo;
 class MachineConstantPool;
+class MachineJumpTableInfo;
 
 // ilist_traits
 template <>
@@ -93,6 +94,9 @@ class MachineFunction : private Annotation {
 
   // Keep track of constants which are spilled to memory
   MachineConstantPool *ConstantPool;
+  
+  // Keep track of jump tables for switch instructions
+  MachineJumpTableInfo *JumpTableInfo;
 
   // Function-level unique numbering for MachineBasicBlocks.  When a
   // MachineBasicBlock is inserted into a MachineFunction is it automatically
@@ -138,6 +142,12 @@ public:
   ///
   MachineFrameInfo *getFrameInfo() const { return FrameInfo; }
 
+  /// getJumpTableInfo - Return the jump table info object for the current 
+  /// function.  This object contains information about jump tables for switch
+  /// instructions in the current function.
+  ///
+  MachineJumpTableInfo *getJumpTableInfo() const { return JumpTableInfo; }
+  
   /// getConstantPool - Return the constant pool object for the current
   /// function.
   ///
diff --git a/include/llvm/CodeGen/MachineInstr.h b/include/llvm/CodeGen/MachineInstr.h
index e98caa56af..d02493bfc7 100644
--- a/include/llvm/CodeGen/MachineInstr.h
+++ b/include/llvm/CodeGen/MachineInstr.h
@@ -105,6 +105,7 @@ public:
     MO_MachineBasicBlock,       // MachineBasicBlock reference
     MO_FrameIndex,              // Abstract Stack Frame Index
     MO_ConstantPoolIndex,       // Address of indexed Constant in Constant Pool
+    MO_JumpTableIndex,          // Address of indexed Jump Table for switch
     MO_ExternalSymbol,          // Name of external global symbol
     MO_GlobalAddress            // Address of a global value
   };
@@ -242,6 +243,7 @@ public:
   }
   bool isFrameIndex() const { return opType == MO_FrameIndex; }
   bool isConstantPoolIndex() const { return opType == MO_ConstantPoolIndex; }
+  bool isJumpTableIndex() const { return opType == MO_JumpTableIndex; }
   bool isGlobalAddress() const { return opType == MO_GlobalAddress; }
   bool isExternalSymbol() const { return opType == MO_ExternalSymbol; }
 
@@ -285,6 +287,10 @@ public:
     assert(isConstantPoolIndex() && "Wrong MachineOperand accessor");
     return (unsigned)contents.immedVal;
   }
+  unsigned getJumpTableIndex() const {
+    assert(isJumpTableIndex() && "Wrong MachineOperand accessor");
+    return (unsigned)contents.immedVal;
+  }
   GlobalValue *getGlobal() const {
     assert(isGlobalAddress() && "Wrong MachineOperand accessor");
     return (GlobalValue*)contents.value;
@@ -348,7 +354,8 @@ public:
   }
 
   void setOffset(int Offset) {
-    assert((isGlobalAddress() || isExternalSymbol() || isConstantPoolIndex()) &&
+    assert((isGlobalAddress() || isExternalSymbol() || isConstantPoolIndex() ||
+            isJumpTableIndex()) &&
         "Wrong MachineOperand accessor");
     extra.offset = Offset;
   }
@@ -611,6 +618,15 @@ public:
     operands.push_back(MachineOperand(I, MachineOperand::MO_ConstantPoolIndex));
   }
 
+  /// addJumpTableIndexOperand - Add a jump table object index to the
+  /// instruction.
+  ///
+  void addJumpTableIndexOperand(unsigned I) {
+    assert(!OperandsComplete() &&
+           "Trying to add an operand to a machine instr that is already done!");
+    operands.push_back(MachineOperand(I, MachineOperand::MO_JumpTableIndex));
+  }
+  
   void addGlobalAddressOperand(GlobalValue *GV, bool isPCRelative, int Offset) {
     assert(!OperandsComplete() &&
            "Trying to add an operand to a machine instr that is already done!");
diff --git a/include/llvm/CodeGen/MachineJumpTableInfo.h b/include/llvm/CodeGen/MachineJumpTableInfo.h
new file mode 100644
index 0000000000..192fb65542
--- /dev/null
+++ b/include/llvm/CodeGen/MachineJumpTableInfo.h
@@ -0,0 +1,73 @@
+//===-- CodeGen/MachineJumpTableInfo.h - Abstract Jump Tables  --*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file was developed by Nate Begeman and is distributed under the
+// University of Illinois Open Source License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// The MachineJumpTableInfo class keeps track of jump tables referenced by
+// lowered switch instructions in the MachineFunction.
+//
+// Instructions reference the address of these jump tables through the use of 
+// MO_JumpTableIndex values.  When emitting assembly or machine code, these 
+// virtual address references are converted to refer to the address of the 
+// function jump tables.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CODEGEN_MACHINEJUMPTABLEINFO_H
+#define LLVM_CODEGEN_MACHINEJUMPTABLEINFO_H
+
+#include "llvm/Target/TargetData.h"
+#include <vector>
+#include <iosfwd>
+
+namespace llvm {
+
+class MachineBasicBlock;
+
+/// MachineJumpTableEntry - One jump table in the jump table info.
+///
+struct MachineJumpTableEntry {
+  /// MBBs - The vector of basic blocks from which to create the jump table.
+  std::vector<MachineBasicBlock*> MBBs;
+  
+  MachineJumpTableEntry(std::vector<MachineBasicBlock*> &M) : MBBs(M) {}
+};
+  
+class MachineJumpTableInfo {
+  const TargetData &TD;
+  std::vector<MachineJumpTableEntry> JumpTables;
+public:
+  MachineJumpTableInfo(const TargetData &td) : TD(td) {}
+    
+  /// getJumpTableIndex - Create a new jump table or return an existing one.
+  ///
+  unsigned getJumpTableIndex(std::vector<MachineBasicBlock*> &DestBBs);
+  
+  /// isEmpty - Return true if there are no jump tables.
+  ///
+  bool isEmpty() const { return JumpTables.empty(); }
+
+  const std::vector<MachineJumpTableEntry> &getJumpTables() const {
+    return JumpTables;
+  }
+  
+  unsigned getEntrySize() const { return TD.getPointerSize(); }
+  unsigned getAlignment() const { return TD.getPointerAlignment(); }
+  
+  /// print - Used by the MachineFunction printer to print information about
+  /// jump tables.  Implemented in MachineFunction.cpp
+  ///
+  void print(std::ostream &OS) const;
+
+  /// dump - Call print(std::cerr) to be called from the debugger.
+  ///
+  void dump() const;
+};
+
+} // End llvm namespace
+
+#endif
diff --git a/include/llvm/CodeGen/ScheduleDAG.h b/include/llvm/CodeGen/ScheduleDAG.h
index b2a2a9c9b8..f72285e0f4 100644
--- a/include/llvm/CodeGen/ScheduleDAG.h
+++ b/include/llvm/CodeGen/ScheduleDAG.h
@@ -100,6 +100,7 @@ namespace llvm {
       if (isa<BasicBlockSDNode>(Node))     return true;
       if (isa<FrameIndexSDNode>(Node))     return true;
       if (isa<ConstantPoolSDNode>(Node))   return true;
+      if (isa<JumpTableSDNode>(Node))      return true;
       if (isa<ExternalSymbolSDNode>(Node)) return true;
       return false;
     }
diff --git a/include/llvm/CodeGen/SelectionDAG.h b/include/llvm/CodeGen/SelectionDAG.h
index 01f56a9e86..f05b5b96bd 100644
--- a/include/llvm/CodeGen/SelectionDAG.h
+++ b/include/llvm/CodeGen/SelectionDAG.h
@@ -120,6 +120,8 @@ public:
                                    int offset = 0);
   SDOperand getFrameIndex(int FI, MVT::ValueType VT);
   SDOperand getTargetFrameIndex(int FI, MVT::ValueType VT);
+  SDOperand getJumpTable(int JTI, MVT::ValueType VT);
+  SDOperand getTargetJumpTable(int JTI, MVT::ValueType VT);
   SDOperand getConstantPool(Constant *C, MVT::ValueType VT,
                            unsigned Alignment=0,  int offset = 0);
   SDOperand getTargetConstantPool(Constant *C, MVT::ValueType VT,
@@ -468,7 +470,8 @@ private:
   std::map<std::pair<uint64_t, MVT::ValueType>, SDNode*> TargetConstants;
   std::map<std::pair<uint64_t, MVT::ValueType>, SDNode*> ConstantFPs;
   std::map<std::pair<uint64_t, MVT::ValueType>, SDNode*> TargetConstantFPs;
-  std::map<int, SDNode*> FrameIndices, TargetFrameIndices;
+  std::map<int, SDNode*> FrameIndices, TargetFrameIndices, JumpTableIndices,
+    TargetJumpTableIndices;
   std::map<std::pair<Constant *,
                      std::pair<int, unsigned> >, SDNode*> ConstantPoolIndices;
   std::map<std::pair<Constant *,
diff --git a/include/llvm/CodeGen/SelectionDAGISel.h b/include/llvm/CodeGen/SelectionDAGISel.h
index 2bf3407199..0e59d7b913 100644
--- a/include/llvm/CodeGen/SelectionDAGISel.h
+++ b/include/llvm/CodeGen/SelectionDAGISel.h
@@ -18,6 +18,7 @@
 #include "llvm/Pass.h"
 #include "llvm/Constant.h"
 #include "llvm/CodeGen/SelectionDAGNodes.h"
+#include <set>
 
 namespace llvm {
   class SelectionDAG;
@@ -40,7 +41,7 @@ public:
   SelectionDAG *CurDAG;
   MachineBasicBlock *BB;
 
-  SelectionDAGISel(TargetLowering &tli) : TLI(tli) {}
+  SelectionDAGISel(TargetLowering &tli) : TLI(tli), JT(0,0,0) {}
 
   virtual void getAnalysisUsage(AnalysisUsage &AU) const;
 
@@ -87,6 +88,20 @@ public:
     // ThisBB - the blcok into which to emit the code for the setcc and branches
     MachineBasicBlock *ThisBB;
   };
+  struct JumpTable {
+    JumpTable(unsigned R, unsigned J, MachineBasicBlock *me) : Reg(R), JTI(J),
+              MBB(me) {}
+    // Reg - the virtual register containing the index of the jump table entry
+    // to jump to.
+    unsigned Reg;
+    // JTI - the JumpTableIndex for this jump table in the function.
+    unsigned JTI;
+    // MBB - the MBB into which to emit the code for the indirect jump.
+    MachineBasicBlock *MBB;
+    // SuccMBBs - a vector of unique successor MBBs used for updating CFG info
+    // and PHI nodes.
+    std::set<MachineBasicBlock*> SuccMBBs;
+  };
   
 protected:
   /// Pick a safe ordering and emit instructions for each target node in the
@@ -114,6 +129,9 @@ private:
   /// SwitchCases - Vector of CaseBlock structures used to communicate
   /// SwitchInst code generation information.
   std::vector<CaseBlock> SwitchCases;
+
+  /// JT - Record which holds necessary information for emitting a jump table
+  JumpTable JT;
 };
 
 }
diff --git a/include/llvm/CodeGen/SelectionDAGNodes.h b/include/llvm/CodeGen/SelectionDAGNodes.h
index 1b7e8e659a..7f317c5e98 100644
--- a/include/llvm/CodeGen/SelectionDAGNodes.h
+++ b/include/llvm/CodeGen/SelectionDAGNodes.h
@@ -65,7 +65,7 @@ namespace ISD {
     // Various leaf nodes.
     STRING, BasicBlock, VALUETYPE, CONDCODE, Register,
     Constant, ConstantFP,
-    GlobalAddress, FrameIndex, ConstantPool, ExternalSymbol,
+    GlobalAddress, FrameIndex, JumpTable, ConstantPool, ExternalSymbol,
 
     // TargetConstant* - Like Constant*, but the DAG does not do any folding or
     // simplification of the constant.
@@ -77,6 +77,7 @@ namespace ISD {
     // dag, turning into a GlobalAddress operand.
     TargetGlobalAddress,
     TargetFrameIndex,
+    TargetJumpTable,
     TargetConstantPool,
     TargetExternalSymbol,
     
@@ -388,6 +389,11 @@ namespace ISD {
     // operand, the second is the MBB to branch to.
     BR,
 
+    // BRIND - Indirect branch.  The first operand is the chain, the second
+    // is the value to branch to, which must be of the same type as the target's
+    // pointer type.
+    BRIND,
+    
     // BRCOND - Conditional branch.  The first operand is the chain,
     // the second is the condition, the third is the block to branch
     // to if the condition is true.
@@ -1165,6 +1171,24 @@ public:
   }
 };
 
+class JumpTableSDNode : public SDNode {
+  int JTI;
+protected:
+  friend class SelectionDAG;
+  JumpTableSDNode(int jti, MVT::ValueType VT, bool isTarg)
+    : SDNode(isTarg ? ISD::TargetJumpTable : ISD::JumpTable, VT), 
+    JTI(jti) {}
+public:
+    
+    int getIndex() const { return JTI; }
+  
+  static bool classof(const JumpTableSDNode *) { return true; }
+  static bool classof(const SDNode *N) {
+    return N->getOpcode() == ISD::JumpTable ||
+           N->getOpcode() == ISD::TargetJumpTable;
+  }
+};
+
 class ConstantPoolSDNode : public SDNode {
   Constant *C;
   int Offset;
diff --git a/lib/CodeGen/AsmPrinter.cpp b/lib/CodeGen/AsmPrinter.cpp
index 11c6f231b9..48d4a20a83 100644
--- a/lib/CodeGen/AsmPrinter.cpp
+++ b/lib/CodeGen/AsmPrinter.cpp
@@ -17,6 +17,7 @@
 #include "llvm/Constants.h"
 #include "llvm/Module.h"
 #include "llvm/CodeGen/MachineConstantPool.h"
+#include "llvm/CodeGen/MachineJumpTableInfo.h"
 #include "llvm/Support/Mangler.h"
 #include "llvm/Support/MathExtras.h"
 #include "llvm/Target/TargetMachine.h"
@@ -46,6 +47,7 @@ AsmPrinter::AsmPrinter(std::ostream &o, TargetMachine &tm)
   AlignmentIsInBytes(true),
   SwitchToSectionDirective("\t.section\t"),
   ConstantPoolSection("\t.section .rodata\n"),
+  JumpTableSection("\t.section .rodata\n"),
   StaticCtorsSection("\t.section .ctors,\"aw\",@progbits"),
   StaticDtorsSection("\t.section .dtors,\"aw\",@progbits"),
   LCOMMDirective(0),
@@ -127,6 +129,33 @@ void AsmPrinter::EmitConstantPool(MachineConstantPool *MCP) {
   }
 }
 
+/// EmitJumpTableInfo - Print assembly representations of the jump tables used
+/// by the current function to the current output stream.  
+///
+void AsmPrinter::EmitJumpTableInfo(MachineJumpTableInfo *MJTI) {
+  const std::vector<MachineJumpTableEntry> &JT = MJTI->getJumpTables();
+  if (JT.empty()) return;
+  const TargetData &TD = TM.getTargetData();
+  
+  // FIXME: someday we need to handle PIC jump tables
+  assert((TM.getRelocationModel() == Reloc::Static ||
+          TM.getRelocationModel() == Reloc::DynamicNoPIC) &&
+         "Unhandled relocation model emitting jump table information!");
+  
+  SwitchSection(JumpTableSection, 0);
+  EmitAlignment(Log2_32(TD.getPointerAlignment()));
+  for (unsigned i = 0, e = JT.size(); i != e; ++i) {
+    O << PrivateGlobalPrefix << "JTI" << getFunctionNumber() << '_' << i 
+      << ":\n";
+    const std::vector<MachineBasicBlock*> &JTBBs = JT[i].MBBs;
+    for (unsigned ii = 0, ee = JTBBs.size(); ii != ee; ++ii) {
+      O << Data32bitsDirective << ' ';
+      printBasicBlockLabel(JTBBs[ii]);
+      O << '\n';
+    }
+  }
+}
+
 /// EmitSpecialLLVMGlobal - Check to see if the specified global is a
 /// special global used by LLVM.  If so, emit it and return true, otherwise
 /// do nothing and return false.
@@ -654,3 +683,12 @@ bool AsmPrinter::PrintAsmMemoryOperand(const MachineInstr *MI, unsigned OpNo,
   // Target doesn't support this yet!
   return true;
 }
+
+/// printBasicBlockLabel - This method prints the label for the specified
+/// MachineBasicBlock
+void AsmPrinter::printBasicBlockLabel(const MachineBasicBlock *MBB) const {
+  O << PrivateGlobalPrefix << "LBB" 
+    << Mang->getValueName(MBB->getParent()->getFunction())
+    << "_" << MBB->getNumber() << '\t' << CommentString
+    << MBB->getBasicBlock()->getName();
+}
diff --git a/lib/CodeGen/ELFWriter.cpp b/lib/CodeGen/ELFWriter.cpp
index c0b2cdfd2a..4be2419886 100644
--- a/lib/CodeGen/ELFWriter.cpp
+++ b/lib/CodeGen/ELFWriter.cpp
@@ -84,7 +84,10 @@ namespace llvm {
       assert(0 && "CP not implementated yet!");
       return 0;
     }
-
+    virtual uint64_t getJumpTableEntryAddress(unsigned Index) {
+      assert(0 && "JT not implementated yet!");
+      return 0;
+    }
     virtual unsigned char* allocateGlobal(unsigned size, unsigned alignment) {
       assert(0 && "Globals not implemented yet!");
       return 0;
diff --git a/lib/CodeGen/MachineCodeEmitter.cpp b/lib/CodeGen/MachineCodeEmitter.cpp
index d37fef4003..4243076d3e 100644
--- a/lib/CodeGen/MachineCodeEmitter.cpp
+++ b/lib/CodeGen/MachineCodeEmitter.cpp
@@ -56,6 +56,7 @@ namespace {
     { return 0; }
 
     uint64_t getConstantPoolEntryAddress(unsigned Num) { return 0; }
+    uint64_t getJumpTableEntryAddress(unsigned Num) { return 0; }
     uint64_t getCurrentPCValue() { return 0; }
     uint64_t getCurrentPCOffset() { return 0; }
   };
@@ -97,7 +98,14 @@ namespace {
     void emitConstantPool(MachineConstantPool *MCP) {
       MCE.emitConstantPool(MCP);
     }
-
+    void initJumpTableInfo(MachineJumpTableInfo *MJTI) {
+      MCE.initJumpTableInfo(MJTI);
+    }
+    void emitJumpTableInfo(MachineJumpTableInfo *MJTI,
+                           std::map<MachineBasicBlock*,uint64_t> &MBBM) {
+      MCE.emitJumpTableInfo(MJTI, MBBM);
+    }
+    
     void startFunctionStub(unsigned StubSize) {
       MCE.startFunctionStub(StubSize);
     }
@@ -146,7 +154,9 @@ namespace {
     uint64_t getConstantPoolEntryAddress(unsigned Num) {
       return MCE.getConstantPoolEntryAddress(Num);
     }
-
+    uint64_t getJumpTableEntryAddress(unsigned Num) {
+      return MCE.getJumpTableEntryAddress(Num);
+    }
     virtual unsigned char* allocateGlobal(unsigned size, unsigned alignment)
     { return MCE.allocateGlobal(size, alignment); }
 
diff --git a/lib/CodeGen/MachineFunction.cpp b/lib/CodeGen/MachineFunction.cpp
index 65c902fd4b..da89ea1821 100644
--- a/lib/CodeGen/MachineFunction.cpp
+++ b/lib/CodeGen/MachineFunction.cpp
@@ -18,6 +18,7 @@
 #include "llvm/CodeGen/SSARegMap.h"
 #include "llvm/CodeGen/MachineFrameInfo.h"
 #include "llvm/CodeGen/MachineConstantPool.h"
+#include "llvm/CodeGen/MachineJumpTableInfo.h"
 #include "llvm/CodeGen/Passes.h"
 #include "llvm/Target/TargetMachine.h"
 #include "llvm/Target/TargetFrameInfo.h"
@@ -113,6 +114,7 @@ MachineFunction::MachineFunction(const Function *F,
   MFInfo = 0;
   FrameInfo = new MachineFrameInfo();
   ConstantPool = new MachineConstantPool(TM.getTargetData());
+  JumpTableInfo = new MachineJumpTableInfo(TM.getTargetData());
   BasicBlocks.Parent = this;
 }
 
@@ -122,6 +124,7 @@ MachineFunction::~MachineFunction() {
   delete MFInfo;
   delete FrameInfo;
   delete ConstantPool;
+  delete JumpTableInfo;
   delete[] UsedPhysRegs;
 }
 
@@ -132,6 +135,9 @@ void MachineFunction::print(std::ostream &OS) const {
 
   // Print Frame Information
   getFrameInfo()->print(*this, OS);
+  
+  // Print JumpTable Information
+  getJumpTableInfo()->print(OS);
 
   // Print Constant Pool
   getConstantPool()->print(OS);
@@ -334,6 +340,36 @@ void MachineFrameInfo::dump(const MachineFunction &MF) const {
 
 
 //===----------------------------------------------------------------------===//
+//  MachineJumpTableInfo implementation
+//===----------------------------------------------------------------------===//
+
+/// getJumpTableIndex - Create a new jump table entry in the jump table info
+/// or return an existing one.
+///
+unsigned MachineJumpTableInfo::getJumpTableIndex(
+                                     std::vector<MachineBasicBlock*> &DestBBs) {
+  for (unsigned i = 0, e = JumpTables.size(); i != e; ++i)
+    if (JumpTables[i].MBBs == DestBBs)
+      return i;
+  
+  JumpTables.push_back(MachineJumpTableEntry(DestBBs));
+  return JumpTables.size()-1;
+}
+
+
+void MachineJumpTableInfo::print(std::ostream &OS) const {
+  // FIXME: this is lame, maybe we could print out the MBB numbers or something
+  // like {1, 2, 4, 5, 3, 0}
+  for (unsigned i = 0, e = JumpTables.size(); i != e; ++i) {
+    OS << "  <jt #" << i << "> has " << JumpTables[i].MBBs.size() 
+       << " entries\n";
+  }
+}
+
+void MachineJumpTableInfo::dump() const { print(std::cerr); }
+
+
+//===----------------------------------------------------------------------===//
 //  MachineConstantPool implementation
 //===----------------------------------------------------------------------===//
 
diff --git a/lib/CodeGen/MachineInstr.cpp b/lib/CodeGen/MachineInstr.cpp
index 973e3ec1e6..f92c0844d8 100644
--- a/lib/CodeGen/MachineInstr.cpp
+++ b/lib/CodeGen/MachineInstr.cpp
@@ -238,6 +238,9 @@ static void print(const MachineOperand &MO, std::ostream &OS,
   case MachineOperand::MO_ConstantPoolIndex:
     OS << "<cp#" << MO.getConstantPoolIndex() << ">";
     break;
+  case MachineOperand::MO_JumpTableIndex:
+    OS << "<jt#" << MO.getJumpTableIndex() << ">";
+    break;
   case MachineOperand::MO_GlobalAddress:
     OS << "<ga:" << ((Value*)MO.getGlobal())->getName();
     if (MO.getOffset()) OS << "+" << MO.getOffset();
@@ -377,6 +380,9 @@ std::ostream &operator<<(std::ostream &OS, const MachineOperand &MO) {
   case MachineOperand::MO_ConstantPoolIndex:
     OS << "<cp#" << MO.getConstantPoolIndex() << ">";
     break;
+  case MachineOperand::MO_JumpTableIndex:
+    OS << "<jt#" << MO.getJumpTableIndex() << ">";
+    break;
   case MachineOperand::MO_GlobalAddress:
     OS << "<ga:" << ((Value*)MO.getGlobal())->getName() << ">";
     break;
diff --git a/lib/CodeGen/SelectionDAG/LegalizeDAG.cpp b/lib/CodeGen/SelectionDAG/LegalizeDAG.cpp
index d635747d80..6f9e97748e 100644
--- a/lib/CodeGen/SelectionDAG/LegalizeDAG.cpp
+++ b/lib/CodeGen/SelectionDAG/LegalizeDAG.cpp
@@ -510,6 +510,7 @@ SDOperand SelectionDAGLegalize::LegalizeOp(SDOperand Op) {
   case ISD::Register:
   case ISD::BasicBlock:
   case ISD::TargetFrameIndex:
+  case ISD::TargetJumpTable:
   case ISD::TargetConstant:
   case ISD::TargetConstantFP:
   case ISD::TargetConstantPool:
@@ -552,7 +553,8 @@ SDOperand SelectionDAGLegalize::LegalizeOp(SDOperand Op) {
     abort();
   case ISD::GlobalAddress:
   case ISD::ExternalSymbol:
-  case ISD::ConstantPool:           // Nothing to do.
+  case ISD::ConstantPool:
+  case ISD::JumpTable: // Nothing to do.
     switch (TLI.getOperationAction(Node->getOpcode(), Node->getValueType(0))) {
     default: assert(0 && "This action is not supported yet!");
     case TargetLowering::Custom:
@@ -1183,7 +1185,21 @@ SDOperand SelectionDAGLegalize::LegalizeOp(SDOperand Op) {
     
     Result = DAG.UpdateNodeOperands(Result, Tmp1, Node->getOperand(1));
     break;
-
+  case ISD::BRIND:
+    Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
+    // Ensure that libcalls are emitted before a branch.
+    Tmp1 = DAG.getNode(ISD::TokenFactor, MVT::Other, Tmp1, LastCALLSEQ_END);
+    Tmp1 = LegalizeOp(Tmp1);
+    LastCALLSEQ_END = DAG.getEntryNode();
+    
+    switch (getTypeAction(Node->getOperand(1).getValueType())) {
+    default: assert(0 && "Indirect target must be legal type (pointer)!");
+    case Legal:
+      Tmp2 = LegalizeOp(Node->getOperand(1)); // Legalize the condition.
+      break;
+    }
+    Result = DAG.UpdateNodeOperands(Result, Tmp1, Tmp2);
+    break;
   case ISD::BRCOND:
     Tmp1 = LegalizeOp(Node->getOperand(0));  // Legalize the chain.
     // Ensure that libcalls are emitted before a return.
diff --git a/lib/CodeGen/SelectionDAG/ScheduleDAG.cpp b/lib/CodeGen/SelectionDAG/ScheduleDAG.cpp
index c0118aff8e..bf95a92555 100644
--- a/lib/CodeGen/SelectionDAG/ScheduleDAG.cpp
+++ b/lib/CodeGen/SelectionDAG/ScheduleDAG.cpp
@@ -117,6 +117,9 @@ void ScheduleDAG::AddOperand(MachineInstr *MI, SDOperand Op,
   } else if (FrameIndexSDNode *FI =
              dyn_cast<FrameIndexSDNode>(Op)) {
     MI->addFrameIndexOperand(FI->getIndex());
+  } else if (JumpTableSDNode *JT =
+             dyn_cast<JumpTableSDNode>(Op)) {
+    MI->addJumpTableIndexOperand(JT->getIndex());
   } else if (ConstantPoolSDNode *CP = 
              dyn_cast<ConstantPoolSDNode>(Op)) {
     int Offset = CP->getOffset();
diff --git a/lib/CodeGen/SelectionDAG/SelectionDAG.cpp b/lib/CodeGen/SelectionDAG/SelectionDAG.cpp
index ec1050fd72..c26632a41e 100644
--- a/lib/CodeGen/SelectionDAG/SelectionDAG.cpp
+++ b/lib/CodeGen/SelectionDAG/SelectionDAG.cpp
@@ -387,6 +387,13 @@ void SelectionDAG::RemoveNodeFromCSEMaps(SDNode *N) {
   case ISD::TargetFrameIndex:
     Erased = TargetFrameIndices.erase(cast<FrameIndexSDNode>(N)->getIndex());
     break;
+  case ISD::JumpTable:
+    Erased = JumpTableIndices.erase(cast<JumpTableSDNode>(N)->getIndex());
+    break;
+  case ISD::TargetJumpTable:
+    Erased = 
+      TargetJumpTableIndices.erase(cast<JumpTableSDNode>(N)->getIndex());
+    break;
   case ISD::ConstantPool:
     Erased = ConstantPoolIndices.
       erase(std::make_pair(cast<ConstantPoolSDNode>(N)->get(),
@@ -741,6 +748,22 @@ SDOperand SelectionDAG::getTargetFrameIndex(int FI, MVT::ValueType VT) {
   return SDOperand(N, 0);
 }
 
+SDOperand SelectionDAG::getJumpTable(int JTI, MVT::ValueType VT) {
+  SDNode *&N = JumpTableIndices[JTI];
+  if (N) return SDOperand(N, 0);
+  N = new JumpTableSDNode(JTI, VT, false);
+  AllNodes.push_back(N);
+  return SDOperand(N, 0);
+}
+
+SDOperand SelectionDAG::getTargetJumpTable(int JTI, MVT::ValueType VT) {
+  SDNode *&N = TargetJumpTableIndices[JTI];
+  if (N) return SDOperand(N, 0);
+  N = new JumpTableSDNode(JTI, VT, true);
+  AllNodes.push_back(N);
+  return SDOperand(N, 0);
+}
+
 SDOperand SelectionDAG::getConstantPool(Constant *C, MVT::ValueType VT,
                                         unsigned Alignment,  int Offset) {
   SDNode *&N = ConstantPoolIndices[std::make_pair(C,
@@ -2742,6 +2765,7 @@ const char *SDNode::getOperationName(const SelectionDAG *G) const {
   case ISD::ConstantFP:    return "ConstantFP";
   case ISD::GlobalAddress: return "GlobalAddress";
   case ISD::FrameIndex:    return "FrameIndex";
+  case ISD::JumpTable:     return "JumpTable";
   case ISD::ConstantPool:  return "ConstantPool";
   case ISD::ExternalSymbol: return "ExternalSymbol";
   case ISD::INTRINSIC_WO_CHAIN: {
@@ -2759,6 +2783,7 @@ const char *SDNode::getOperationName(const SelectionDAG *G) const {
   case ISD::TargetConstantFP:return "TargetConstantFP";
   case ISD::TargetGlobalAddress: return "TargetGlobalAddress";
   case ISD::TargetFrameIndex: return "TargetFrameIndex";
+  case ISD::TargetJumpTable:  return "TargetJumpTable";
   case ISD::TargetConstantPool:  return "TargetConstantPool";
   case ISD::TargetExternalSymbol: return "TargetExternalSymbol";
 
@@ -2849,6 +2874,7 @@ const char *SDNode::getOperationName(const SelectionDAG *G) const {
 
     // Control flow instructions
   case ISD::BR:      return "br";
+  case ISD::BRIND:   return "brind";
   case ISD::BRCOND:  return "brcond";
   case ISD::BR_CC:   return "br_cc";
   case ISD::RET:     return "ret";
diff --git a/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp b/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp
index 96a81e0938..7fcaaf59af 100644
--- a/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp
+++ b/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp
@@ -27,6 +27,7 @@
 #include "llvm/CodeGen/MachineDebugInfo.h"
 #include "llvm/CodeGen/MachineFunction.h"
 #include "llvm/CodeGen/MachineFrameInfo.h"
+#include "llvm/CodeGen/MachineJumpTableInfo.h"
 #include "llvm/CodeGen/MachineInstrBuilder.h"
 #include "llvm/CodeGen/SelectionDAG.h"
 #include "llvm/CodeGen/SSARegMap.h"
@@ -398,6 +399,7 @@ public:
   /// SwitchCases - Vector of CaseBlock structures used to communicate
   /// SwitchInst code generation information.
   std::vector<SelectionDAGISel::CaseBlock> SwitchCases;
+  SelectionDAGISel::JumpTable JT;
   
   /// FuncInfo - Information about the function as a whole.
   ///
@@ -406,7 +408,7 @@ public:
   SelectionDAGLowering(SelectionDAG &dag, TargetLowering &tli,
                        FunctionLoweringInfo &funcinfo)
     : TLI(tli), DAG(dag), TD(DAG.getTarget().getTargetData()),
-      FuncInfo(funcinfo) {
+      JT(0,0,0), FuncInfo(funcinfo) {
   }
 
   /// getRoot - Return the current virtual root of the Selection DAG.
@@ -474,6 +476,7 @@ public:
 
   // Helper for visitSwitch
   void visitSwitchCase(SelectionDAGISel::CaseBlock &CB);
+  void visitJumpTable(SelectionDAGISel::JumpTable &JT);
   
   // These all get lowered before this pass.
   void visitInvoke(InvokeInst &I) { assert(0 && "TODO"); }
@@ -816,6 +819,30 @@ void SelectionDAGLowering::visitSwitchCase(SelectionDAGISel::CaseBlock &CB) {
   CurMBB->addSuccessor(CB.RHSBB);
 }
 
+/// visitSwitchCase - Emits the necessary code to represent a single node in
+/// the binary search tree resulting from lowering a switch instruction.
+void SelectionDAGLowering::visitJumpTable(SelectionDAGISel::JumpTable &JT) {
+  // FIXME: Need to emit different code for PIC vs. Non-PIC, specifically,
+  // we need to add the address of the jump table to the value loaded, since
+  // the entries in the jump table will be differences rather than absolute
+  // addresses.
+  
+  // Emit the code for the jump table
+  MVT::ValueType PTy = TLI.getPointerTy();
+  unsigned PTyBytes = MVT::getSizeInBits(PTy)/8;
+  SDOperand Copy = DAG.getCopyFromReg(getRoot(), JT.Reg, PTy);
+  SDOperand IDX = DAG.getNode(ISD::MUL, PTy, Copy,
+                              DAG.getConstant(PTyBytes, PTy));
+  SDOperand ADD = DAG.getNode(ISD::ADD, PTy, IDX, DAG.getJumpTable(JT.JTI,PTy));
+  SDOperand LD  = DAG.getLoad(PTy, Copy.getValue(1), ADD, DAG.getSrcValue(0));
+  DAG.setRoot(DAG.getNode(ISD::BRIND, MVT::Other, LD.getValue(1), LD));
+
+  // Update successor info
+  for (std::set<MachineBasicBlock*>::iterator ii = JT.SuccMBBs.begin(), 
+       ee = JT.SuccMBBs.end(); ii != ee; ++ii)
+    JT.MBB->addSuccessor(*ii);
+}
+
 void SelectionDAGLowering::visitSwitch(SwitchInst &I) {
   // Figure out which block is immediately after the current one.
   MachineBasicBlock *NextBlock = 0;
@@ -850,11 +877,88 @@ void SelectionDAGLowering::visitSwitch(SwitchInst &I) {
   // search tree.
   Value *SV = I.getOperand(0);
   MachineBasicBlock *Default = FuncInfo.MBBMap[I.getDefaultDest()];
-  
-  // Get the current MachineFunction and LLVM basic block, for use in creating
-  // and inserting new MBBs during the creation of the binary search tree.
+
+  // Get the MachineFunction which holds the current MBB.  This is used during
+  // emission of jump tables, and when inserting any additional MBBs necessary
+  // to represent the switch.
   MachineFunction *CurMF = CurMBB->getParent();
   const BasicBlock *LLVMBB = CurMBB->getBasicBlock();
+  Reloc::Model Relocs = TLI.getTargetMachine().getRelocationModel();
+
+  // If the switch has more than 3 blocks, and is 100% dense, then emit a jump
+  // table rather than lowering the switch to a binary tree of conditional
+  // branches.
+  // FIXME: Make this work with 64 bit targets someday, possibly by always
+  // doing differences there so that entries stay 32 bits.
+  // FIXME: Make this work with PIC code
+  if (TLI.isOperationLegal(ISD::BRIND, TLI.getPointerTy()) &&
+      TLI.getPointerTy() == MVT::i32 &&
+      (Relocs == Reloc::Static || Relocs == Reloc::DynamicNoPIC) &&
+      Cases.size() > 3) {
+    uint64_t First = cast<ConstantIntegral>(Cases.front().first)->getRawValue();
+    uint64_t Last  = cast<ConstantIntegral>(Cases.back().first)->getRawValue();
+
+    // Determine density
+    // FIXME: support sub-100% density
+    if (((Last - First) + 1ULL) == (uint64_t)Cases.size()) {
+      // Create a new basic block to hold the code for loading the address
+      // of the jump table, and jumping to it.  Update successor information;
+      // we will either branch to the default case for the switch, or the jump
+      // table.
+      MachineBasicBlock *JumpTableBB = new MachineBasicBlock(LLVMBB);
+      CurMF->getBasicBlockList().insert(BBI, JumpTableBB);
+      CurMBB->addSuccessor(Default);
+      CurMBB->addSuccessor(JumpTableBB);
+      
+      // Subtract the lowest switch case value from the value being switched on
+      // and conditional branch to default mbb if the result is greater than the
+      // difference between smallest and largest cases.
+      SDOperand SwitchOp = getValue(SV);
+      MVT::ValueType VT = SwitchOp.getValueType();
+      SDOperand SUB = DAG.getNode(ISD::SUB, VT, SwitchOp, 
+                                  DAG.getConstant(First, VT));
+
+      // The SDNode we just created, which holds the value being switched on
+      // minus the the smallest case value, needs to be copied to a virtual
+      // register so it can be used as an index into the jump table in a 
+      // subsequent basic block.  This value may be smaller or larger than the
+      // target's pointer type, and therefore require extension or truncating.
+      if (VT > TLI.getPointerTy())
+        SwitchOp = DAG.getNode(ISD::TRUNCATE, TLI.getPointerTy(), SUB);
+      else
+        SwitchOp = DAG.getNode(ISD::ZERO_EXTEND, TLI.getPointerTy(), SUB);
+      unsigned JumpTableReg = FuncInfo.MakeReg(TLI.getPointerTy());
+      SDOperand CopyTo = DAG.getCopyToReg(getRoot(), JumpTableReg, SwitchOp);
+      
+      // Emit the range check for the jump table, and branch to the default
+      // block for the switch statement if the value being switched on exceeds
+      // the largest case in the switch.
+      SDOperand CMP = DAG.getSetCC(TLI.getSetCCResultTy(), SUB,
+                                   DAG.getConstant(Last-First,VT), ISD::SETUGT);
+      DAG.setRoot(DAG.getNode(ISD::BRCOND, MVT::Other, CopyTo, CMP, 
+                              DAG.getBasicBlock(Default)));
+
+      // Build a sorted vector of destination BBs, corresponding to each target
+      // of the switch.
+      // FIXME: need to insert DefaultMBB for each "hole" in the jump table,
+      // when we support jump tables with < 100% density.
+      std::set<MachineBasicBlock*> UniqueBBs;
+      std::vector<MachineBasicBlock*> DestBBs;
+      for (CaseItr ii = Cases.begin(), ee = Cases.end(); ii != ee; ++ii) {
+        DestBBs.push_back(ii->second);
+        UniqueBBs.insert(ii->second);
+      }
+      unsigned JTI = CurMF->getJumpTableInfo()->getJumpTableIndex(DestBBs);
+      
+      // Set the jump table information so that we can codegen it as a second
+      // MachineBasicBlock
+      JT.Reg = JumpTableReg;
+      JT.JTI = JTI;
+      JT.MBB = JumpTableBB;
+      JT.SuccMBBs = UniqueBBs;
+      return;
+    }
+  }
   
   // Push the initial CaseRec onto the worklist
   std::vector<CaseRec> CaseVec;
@@ -3022,9 +3126,10 @@ void SelectionDAGISel::BuildSelectionDAG(SelectionDAG &DAG, BasicBlock *LLVMBB,
   SDL.visit(*LLVMBB->getTerminator());
 
   // Copy over any CaseBlock records that may now exist due to SwitchInst
-  // lowering.
+  // lowering, as well as any jump table information.
   SwitchCases.clear();
   SwitchCases = SDL.SwitchCases;
+  JT = SDL.JT;
   
   // Make sure the root of the DAG is up-to-date.
   DAG.setRoot(SDL.getRoot());
@@ -3074,7 +3179,7 @@ void SelectionDAGISel::SelectBasicBlock(BasicBlock *LLVMBB, MachineFunction &MF,
   
   // Next, now that we know what the last MBB the LLVM BB expanded is, update
   // PHI nodes in successors.
-  if (SwitchCases.empty()) {
+  if (SwitchCases.empty() && JT.Reg == 0) {
     for (unsigned i = 0, e = PHINodesToUpdate.size(); i != e; ++i) {
       MachineInstr *PHI = PHINodesToUpdate[i].first;
       assert(PHI->getOpcode() == TargetInstrInfo::PHI &&
@@ -3085,6 +3190,33 @@ void SelectionDAGISel::SelectBasicBlock(BasicBlock *LLVMBB, MachineFunction &MF,
     return;
   }
   
+  // If we need to emit a jump table, 
+  if (JT.Reg) {
+    assert(SwitchCases.empty() && "Cannot have jump table and lowered switch");
+    SelectionDAG SDAG(TLI, MF, getAnalysisToUpdate<MachineDebugInfo>());
+    CurDAG = &SDAG;
+    SelectionDAGLowering SDL(SDAG, TLI, FuncInfo);
+    // Set the current basic block to the mbb we wish to insert the code into
+    BB = JT.MBB;
+    SDL.setCurrentBasicBlock(BB);
+    // Emit the code
+    SDL.visitJumpTable(JT);
+    SDAG.setRoot(SDL.getRoot());
+    CodeGenAndEmitDAG(SDAG);
+    // Update PHI Nodes
+    for (unsigned pi = 0, pe = PHINodesToUpdate.size(); pi != pe; ++pi) {
+      MachineInstr *PHI = PHINodesToUpdate[pi].first;
+      MachineBasicBlock *PHIBB = PHI->getParent();
+      assert(PHI->getOpcode() == TargetInstrInfo::PHI &&
+             "This is not a machine PHI node that we are updating!");
+      if (JT.SuccMBBs.find(PHIBB) != JT.SuccMBBs.end()) {
+        PHI->addRegOperand(PHINodesToUpdate[pi].second);
+        PHI->addMachineBasicBlockOperand(BB);
+      }
+    }
+    return;
+  }
+  
   // If we generated any switch lowering information, build and codegen any
   // additional DAGs necessary.
   for(unsigned i = 0, e = SwitchCases.size(); i != e; ++i) {
diff --git a/lib/ExecutionEngine/ExecutionEngine.cpp b/lib/ExecutionEngine/ExecutionEngine.cpp
index 5cd83ff51a..b99497fd88 100644
--- a/lib/ExecutionEngine/ExecutionEngine.cpp
+++ b/lib/ExecutionEngine/ExecutionEngine.cpp
@@ -328,7 +328,10 @@ GenericValue ExecutionEngine::getConstantValue(const Constant *C) {
   return Result;
 }
 
-/// FIXME: document
+/// StoreValueToMemory - Stores the data in Val of type Ty at address Ptr.  Ptr
+/// is the address of the memory at which to store Val, cast to GenericValue *.
+/// It is not a pointer to a GenericValue containing the address at which to
+/// store Val.
 ///
 void ExecutionEngine::StoreValueToMemory(GenericValue Val, GenericValue *Ptr,
                                          const Type *Ty) {
diff --git a/lib/ExecutionEngine/JIT/JITEmitter.cpp b/lib/ExecutionEngine/JIT/JITEmitter.cpp
index a5bb7c690a..b67dfe1953 100644
--- a/lib/ExecutionEngine/JIT/JITEmitter.cpp
+++ b/lib/ExecutionEngine/JIT/JITEmitter.cpp
@@ -20,7 +20,9 @@
 #include "llvm/CodeGen/MachineCodeEmitter.h"
 #include "llvm/CodeGen/MachineFunction.h"
 #include "llvm/CodeGen/MachineConstantPool.h"
+#include "llvm/CodeGen/MachineJumpTableInfo.h"
 #include "llvm/CodeGen/MachineRelocation.h"
+#include "llvm/ExecutionEngine/GenericValue.h"
 #include "llvm/Target/TargetData.h"
 #include "llvm/Target/TargetJITInfo.h"
 #include "llvm/Support/Debug.h"
@@ -430,7 +432,15 @@ namespace {
     /// ConstantPoolBase - A pointer to the first entry in the constant pool.
     ///
     void *ConstantPoolBase;
-  public:
+
+    /// ConstantPool - The constant pool for the current function.
+    ///
+    MachineJumpTableInfo *JumpTable;
+    
+    /// JumpTableBase - A pointer to the first entry in the jump table.
+    ///
+    void *JumpTableBase;
+public:
     JITEmitter(JIT &jit) : MemMgr(jit.getJITInfo().needsGOT()) {
       TheJIT = &jit;
       DEBUG(std::cerr <<
@@ -441,6 +451,9 @@ namespace {
     virtual void startFunction(MachineFunction &F);
     virtual void finishFunction(MachineFunction &F);
     virtual void emitConstantPool(MachineConstantPool *MCP);
+    virtual void initJumpTableInfo(MachineJumpTableInfo *MJTI);
+    virtual void emitJumpTableInfo(MachineJumpTableInfo *MJTI,
+                                   std::map<MachineBasicBlock*,uint64_t> &MBBM);
     virtual void startFunctionStub(unsigned StubSize);
     virtual void* finishFunctionStub(const Function *F);
     virtual void emitByte(unsigned char B);
@@ -454,6 +467,7 @@ namespace {
     virtual uint64_t getCurrentPCValue();
     virtual uint64_t getCurrentPCOffset();
     virtual uint64_t getConstantPoolEntryAddress(unsigned Entry);
+    virtual uint64_t getJumpTableEntryAddress(unsigned Entry);
     virtual unsigned char* allocateGlobal(unsigned size, unsigned alignment);
 
   private:
@@ -583,6 +597,57 @@ void JITEmitter::emitConstantPool(MachineConstantPool *MCP) {
   }
 }
 
+void JITEmitter::initJumpTableInfo(MachineJumpTableInfo *MJTI) {
+  const std::vector<MachineJumpTableEntry> &JT = MJTI->getJumpTables();
+  if (JT.empty()) return;
+  
+  unsigned Size = 0;
+  unsigned EntrySize = MJTI->getEntrySize();
+  for (unsigned i = 0, e = JT.size(); i != e; ++i)
+    Size += JT[i].MBBs.size() * EntrySize;
+  
+  // Just allocate space for all the jump tables now.  We will fix up the actual
+  // MBB entries in the tables after we emit the code for each block, since then
+  // we will know the final locations of the MBBs in memory.
+  JumpTable = MJTI;
+  JumpTableBase = MemMgr.allocateConstant(Size, MJTI->getAlignment());
+}
+
+void JITEmitter::emitJumpTableInfo(MachineJumpTableInfo *MJTI,
+                                   std::map<MachineBasicBlock*,uint64_t> &MBBM){
+  const std::vector<MachineJumpTableEntry> &JT = MJTI->getJumpTables();
+  if (JT.empty()) return;
+
+  unsigned Offset = 0;
+  unsigned EntrySize = MJTI->getEntrySize();
+  
+  // For each jump table, map each target in the jump table to the address of 
+  // an emitted MachineBasicBlock.
+  for (unsigned i = 0, e = JT.size(); i != e; ++i) {
+    const std::vector<MachineBasicBlock*> &MBBs = JT[i].MBBs;
+    for (unsigned mi = 0, me = MBBs.size(); mi != me; ++mi) {
+      uint64_t addr = MBBM[MBBs[mi]];
+      GenericValue addrgv;
+      const Type *Ty;
+      if (EntrySize == 4) {
+        addrgv.UIntVal = addr;
+        Ty = Type::UIntTy;
+      } else if (EntrySize == 8) {
+        addrgv.ULongVal = addr;
+        Ty = Type::ULongTy;
+      } else {
+        assert(0 && "Unhandled jump table entry size!");
+        abort();
+      }
+      // Store the address of the basic block for this jump table slot in the
+      // memory we allocated for the jump table in 'initJumpTableInfo'
+      void *ptr = (void *)((char *)JumpTableBase + Offset);
+      TheJIT->StoreValueToMemory(addrgv, (GenericValue *)ptr, Ty);
+      Offset += EntrySize;
+    }
+  }
+}
+
 void JITEmitter::startFunctionStub(unsigned StubSize) {
   SavedCurBlock = CurBlock;  SavedCurByte = CurByte;
   CurByte = CurBlock = MemMgr.allocateStub(StubSize);
@@ -621,6 +686,22 @@ uint64_t JITEmitter::getConstantPoolEntryAddress(unsigned ConstantNum) {
          ConstantPool->getConstants()[ConstantNum].Offset;
 }
 
+// getJumpTableEntryAddress - Return the address of the JumpTable with index
+// 'Index' in the jumpp table that was last initialized with 'initJumpTableInfo'
+//
+uint64_t JITEmitter::getJumpTableEntryAddress(unsigned Index) {
+  const std::vector<MachineJumpTableEntry> &JT = JumpTable->getJumpTables();
+  assert(Index < JT.size() && "Invalid jump table index!");
+  
+  unsigned Offset = 0;
+  unsigned EntrySize = JumpTable->getEntrySize();
+  
+  for (unsigned i = 0; i < Index; ++i)
+    Offset += JT[i].MBBs.size() * EntrySize;
+  
+  return (uint64_t)((char *)JumpTableBase + Offset);
+}
+
 unsigned char* JITEmitter::allocateGlobal(unsigned size, unsigned alignment)
 {
   return MemMgr.allocateGlobal(size, alignment);
diff --git a/lib/Target/Alpha/AlphaAsmPrinter.cpp b/lib/Target/Alpha/AlphaAsmPrinter.cpp
index 6f45fb5497..5d1f522ca0 100644
--- a/lib/Target/Alpha/AlphaAsmPrinter.cpp
+++ b/lib/Target/Alpha/AlphaAsmPrinter.cpp
@@ -115,14 +115,9 @@ void AlphaAsmPrinter::printOp(const MachineOperand &MO, bool IsCallOp) {
     abort();
     return;
 
-  case MachineOperand::MO_MachineBasicBlock: {
-    MachineBasicBlock *MBBOp = MO.getMachineBasicBlock();
-    O << PrivateGlobalPrefix << "LBB"
-      << Mang->getValueName(MBBOp->getParent()->getFunction())
-      << "_" << MBBOp->getNumber() << "\t" << CommentString << " "
-      << MBBOp->getBasicBlock()->getName();
+  case MachineOperand::MO_MachineBasicBlock:
+    printBasicBlockLabel(MO.getMachineBasicBlock());
     return;
-  }
 
   case MachineOperand::MO_ConstantPoolIndex:
     O << PrivateGlobalPrefix << "CPI" << getFunctionNumber() << "_"
diff --git a/lib/Target/Alpha/AlphaISelLowering.cpp b/lib/Target/Alpha/AlphaISelLowering.cpp
index fee6457d7d..3c72e7f981 100644
--- a/lib/Target/Alpha/AlphaISelLowering.cpp
+++ b/lib/Target/Alpha/AlphaISelLowering.cpp
@@ -193,6 +193,7 @@ AlphaTargetLowering::AlphaTargetLowering(TargetMachine &TM) : TargetLowering(TM)
   addRegisterClass(MVT::f64, Alpha::F8RCRegisterClass);
   addRegisterClass(MVT::f32, Alpha::F4RCRegisterClass);
   
+  setOperationAction(ISD::BRIND,        MVT::i64,   Expand);
   setOperationAction(ISD::BR_CC,        MVT::Other, Expand);
   setOperationAction(ISD::SELECT_CC,    MVT::Other, Expand);
   
diff --git a/lib/Target/IA64/IA64AsmPrinter.cpp b/lib/Target/IA64/IA64AsmPrinter.cpp
index 2cd156124a..359b644104 100644
--- a/lib/Target/IA64/IA64AsmPrinter.cpp
+++ b/lib/Target/IA64/IA64AsmPrinter.cpp
@@ -189,14 +189,9 @@ void IA64AsmPrinter::printOp(const MachineOperand &MO,
   case MachineOperand::MO_UnextendedImmed:
     O << /*(unsigned int)*/MO.getImmedValue();
     return;
-  case MachineOperand::MO_MachineBasicBlock: {
-    MachineBasicBlock *MBBOp = MO.getMachineBasicBlock();
-    O << PrivateGlobalPrefix << "LBB"
-      << Mang->getValueName(MBBOp->getParent()->getFunction())
-      << "_" << MBBOp->getNumber () << "\t// "
-      << MBBOp->getBasicBlock ()->getName ();
+  case MachineOperand::MO_MachineBasicBlock:
+    printBasicBlockLabel(MO.getMachineBasicBlock());
     return;
-  }
   case MachineOperand::MO_PCRelativeDisp:
     std::cerr << "Shouldn't use addPCDisp() when building IA64 MachineInstrs";
     abort ();
diff --git a/lib/Target/IA64/IA64ISelLowering.cpp b/lib/Target/IA64/IA64ISelLowering.cpp
index 85e6737d4b..9de54472de 100644
--- a/lib/Target/IA64/IA64ISelLowering.cpp
+++ b/lib/Target/IA64/IA64ISelLowering.cpp
@@ -35,6 +35,7 @@ IA64TargetLowering::IA64TargetLowering(TargetMachine &TM)
       // register class for predicate registers
       addRegisterClass(MVT::i1, IA64::PRRegisterClass);
 
+      setOperationAction(ISD::BRIND            , MVT::i64,   Expand);
       setOperationAction(ISD::BR_CC            , MVT::Other, Expand);
       setOperationAction(ISD::FP_ROUND_INREG   , MVT::f32  , Expand);
 
diff --git a/lib/Target/PowerPC/PPCAsmPrinter.cpp b/lib/Target/PowerPC/PPCAsmPrinter.cpp
index b34bf9a8a2..11c0ec008b 100644
--- a/lib/Target/PowerPC/PPCAsmPrinter.cpp
+++ b/lib/Target/PowerPC/PPCAsmPrinter.cpp
@@ -233,6 +233,8 @@ namespace {
       printOperand(MI, OpNo+1);
     }
     
+    virtual void printBasicBlockLabel(const MachineBasicBlock *MBB) const; 
+    
     virtual bool runOnMachineFunction(MachineFunction &F) = 0;
     virtual bool doFinalization(Module &M) = 0;
     
@@ -277,6 +279,8 @@ namespace {
       Data64bitsDirective = 0;       // we can't emit a 64-bit unit
       AlignmentIsInBytes = false;    // Alignment is by power of 2.
       ConstantPoolSection = "\t.const\t";
+      // FIXME: Conditionalize jump table section based on PIC
+      JumpTableSection = ".const";
       LCOMMDirective = "\t.lcomm\t";
       StaticCtorsSection = ".mod_init_func";
       StaticDtorsSection = ".mod_term_func";
@@ -373,13 +377,14 @@ void PPCAsmPrinter::printOp(const MachineOperand &MO) {
     abort();
     return;
 
-  case MachineOperand::MO_MachineBasicBlock: {
-    MachineBasicBlock *MBBOp = MO.getMachineBasicBlock();
-    O << PrivateGlobalPrefix << "BB" << getFunctionNumber() << "_"
-      << MBBOp->getNumber() << "\t; " << MBBOp->getBasicBlock()->getName();
+  case MachineOperand::MO_MachineBasicBlock:
+    printBasicBlockLabel(MO.getMachineBasicBlock());
+    return;
+  case MachineOperand::MO_JumpTableIndex:
+    O << PrivateGlobalPrefix << "JTI" << getFunctionNumber()
+      << '_' << MO.getJumpTableIndex();
+    // FIXME: PIC relocation model
     return;
-  }
-
   case MachineOperand::MO_ConstantPoolIndex:
     O << PrivateGlobalPrefix << "CPI" << getFunctionNumber()
       << '_' << MO.getConstantPoolIndex();
@@ -500,6 +505,11 @@ void PPCAsmPrinter::printMachineInstruction(const MachineInstr *MI) {
   return;
 }
 
+void PPCAsmPrinter::printBasicBlockLabel(const MachineBasicBlock *MBB) const {
+  O << PrivateGlobalPrefix << "BB" << getFunctionNumber() << "_"
+    << MBB->getNumber() << '\t' << CommentString
+    << MBB->getBasicBlock()->getName();
+}
 
 /// runOnMachineFunction - This uses the printMachineInstruction()
 /// method to print assembly for each instruction.
@@ -514,6 +524,9 @@ bool DarwinAsmPrinter::runOnMachineFunction(MachineFunction &MF) {
   // Print out constants referenced by the function
   EmitConstantPool(MF.getConstantPool());
 
+  // Print out jump tables referenced by the function
+  EmitJumpTableInfo(MF.getJumpTableInfo());
+
   // Print out labels for the function.
   const Function *F = MF.getFunction();
   switch (F->getLinkage()) {
diff --git a/lib/Target/PowerPC/PPCCodeEmitter.cpp b/lib/Target/PowerPC/PPCCodeEmitter.cpp
index 8d4e1b669a..c7f2acbd77 100644
--- a/lib/Target/PowerPC/PPCCodeEmitter.cpp
+++ b/lib/Target/PowerPC/PPCCodeEmitter.cpp
@@ -34,7 +34,7 @@ namespace {
     // Tracks which instruction references which BasicBlock
     std::vector<std::pair<MachineBasicBlock*, unsigned*> > BBRefs;
     // Tracks where each BasicBlock starts
-    std::map<MachineBasicBlock*, long> BBLocations;
+    std::map<MachineBasicBlock*, uint64_t> BBLocations;
 
     /// getMachineOpValue - evaluates the MachineOperand of a given MachineInstr
     ///
@@ -91,8 +91,10 @@ bool PPCCodeEmitter::runOnMachineFunction(MachineFunction &MF) {
          "JIT relocation model must be set to static or default!");
   MCE.startFunction(MF);
   MCE.emitConstantPool(MF.getConstantPool());
+  MCE.initJumpTableInfo(MF.getJumpTableInfo());
   for (MachineFunction::iterator BB = MF.begin(), E = MF.end(); BB != E; ++BB)
     emitBasicBlock(*BB);
+  MCE.emitJumpTableInfo(MF.getJumpTableInfo(), BBLocations);
   MCE.finishFunction(MF);
 
   // Resolve branches to BasicBlocks for the entire function
@@ -192,10 +194,13 @@ int PPCCodeEmitter::getMachineOpValue(MachineInstr &MI, MachineOperand &MO) {
   } else if (MO.isMachineBasicBlock()) {
     unsigned* CurrPC = (unsigned*)(intptr_t)MCE.getCurrentPCValue();
     BBRefs.push_back(std::make_pair(MO.getMachineBasicBlock(), CurrPC));
-  } else if (MO.isConstantPoolIndex()) {
-    unsigned index = MO.getConstantPoolIndex();
+  } else if (MO.isConstantPoolIndex() || MO.isJumpTableIndex()) {
+    if (MO.isConstantPoolIndex())
+      rv = MCE.getConstantPoolEntryAddress(MO.getConstantPoolIndex());
+    else
+      rv = MCE.getJumpTableEntryAddress(MO.getJumpTableIndex());
+
     unsigned Opcode = MI.getOpcode();
-    rv = MCE.getConstantPoolEntryAddress(index);
     if (Opcode == PPC::LIS || Opcode == PPC::ADDIS) {
       // lis wants hi16(addr)
       if ((short)rv < 0) rv += 1 << 16;
@@ -206,7 +211,7 @@ int PPCCodeEmitter::getMachineOpValue(MachineInstr &MI, MachineOperand &MO) {
       // These load opcodes want lo16(addr)
       rv &= 0xffff;
     } else {
-      assert(0 && "Unknown constant pool using instruction!");
+      assert(0 && "Unknown constant pool or jump table using instruction!");
     }
   } else {
     std::cerr << "ERROR: Unknown type of MachineOperand: " << MO << "\n";
diff --git a/lib/Target/PowerPC/PPCISelDAGToDAG.cpp b/lib/Target/PowerPC/PPCISelDAGToDAG.cpp
index b699b92afb..10f074f6ef 100644
--- a/lib/Target/PowerPC/PPCISelDAGToDAG.cpp
+++ b/lib/Target/PowerPC/PPCISelDAGToDAG.cpp
@@ -520,7 +520,8 @@ bool PPCDAGToDAGISel::SelectAddrImm(SDOperand N, SDOperand &Disp,
              && "Cannot handle constant offsets yet!");
       Disp = N.getOperand(1).getOperand(0);  // The global address.
       assert(Disp.getOpcode() == ISD::TargetGlobalAddress ||
-             Disp.getOpcode() == ISD::TargetConstantPool);
+             Disp.getOpcode() == ISD::TargetConstantPool ||
+             Disp.getOpcode() == ISD::TargetJumpTable);
       Base = N.getOperand(0);
       return true;  // [&g+r]
     }
@@ -661,7 +662,8 @@ bool PPCDAGToDAGISel::SelectAddrImmShift(SDOperand N, SDOperand &Disp,
              && "Cannot handle constant offsets yet!");
       Disp = N.getOperand(1).getOperand(0);  // The global address.
       assert(Disp.getOpcode() == ISD::TargetGlobalAddress ||
-             Disp.getOpcode() == ISD::TargetConstantPool);
+             Disp.getOpcode() == ISD::TargetConstantPool ||
+             Disp.getOpcode() == ISD::TargetJumpTable);
       Base = N.getOperand(0);
       return true;  // [&g+r]
     }
@@ -1241,6 +1243,15 @@ void PPCDAGToDAGISel::Select(SDOperand &Result, SDOperand Op) {
                                   N->getOperand(4), Chain);
     return;
   }
+  case ISD::BRIND: {
+    SDOperand Chain, Target;
+    Select(Chain, N->getOperand(0));
+    Select(Target,N->getOperand(1));
+    Chain = SDOperand(CurDAG->getTargetNode(PPC::MTCTR, MVT::Other, Target,
+                                            Chain), 0);
+    Result = CurDAG->SelectNodeTo(N, PPC::BCTR, MVT::Other, Chain);
+    return;
+  }
   }
   
   SelectCode(Result, Op);
diff --git a/lib/Target/PowerPC/PPCISelLowering.cpp b/lib/Target/PowerPC/PPCISelLowering.cpp
index 18404fcfef..fac2806c12 100644
--- a/lib/Target/PowerPC/PPCISelLowering.cpp
+++ b/lib/Target/PowerPC/PPCISelLowering.cpp
@@ -123,6 +123,7 @@ PPCTargetLowering::PPCTargetLowering(TargetMachine &TM)
   // appropriate instructions to materialize the address.
   setOperationAction(ISD::GlobalAddress, MVT::i32, Custom);
   setOperationAction(ISD::ConstantPool,  MVT::i32, Custom);
+  setOperationAction(ISD::JumpTable,     MVT::i32, Custom);
 
   // RET must be custom lowered, to meet ABI requirements
   setOperationAction(ISD::RET               , MVT::Other, Custom);
@@ -605,6 +606,36 @@ static SDOperand LowerConstantPool(SDOperand Op, SelectionDAG &DAG) {
   return Lo;
 }
 
+static SDOperand LowerJumpTable(SDOperand Op, SelectionDAG &DAG) {
+  JumpTableSDNode *JT = cast<JumpTableSDNode>(Op);
+  SDOperand JTI = DAG.getTargetJumpTable(JT->getIndex(), MVT::i32);
+  SDOperand Zero = DAG.getConstant(0, MVT::i32);
+  
+  const TargetMachine &TM = DAG.getTarget();
+  
+  // If this is a non-darwin platform, we don't support non-static relo models
+  // yet.
+  if (TM.getRelocationModel() == Reloc::Static ||
+      !TM.getSubtarget<PPCSubtarget>().isDarwin()) {
+    // Generate non-pic code that has direct accesses to the constant pool.
+    // The address of the global is just (hi(&g)+lo(&g)).
+    SDOperand Hi = DAG.getNode(PPCISD::Hi, MVT::i32, JTI, Zero);
+    SDOperand Lo = DAG.getNode(PPCISD::Lo, MVT::i32, JTI, Zero);
+    return DAG.getNode(ISD::ADD, MVT::i32, Hi, Lo);
+  }
+  
+  SDOperand Hi = DAG.getNode(PPCISD::Hi, MVT::i32, JTI, Zero);
+  if (TM.getRelocationModel() == Reloc::PIC) {
+    // With PIC, the first instruction is actually "GR+hi(&G)".
+    Hi = DAG.getNode(ISD::ADD, MVT::i32,
+                     DAG.getNode(PPCISD::GlobalBaseReg, MVT::i32), Hi);
+  }
+  
+  SDOperand Lo = DAG.getNode(PPCISD::Lo, MVT::i32, JTI, Zero);
+  Lo = DAG.getNode(ISD::ADD, MVT::i32, Hi, Lo);
+  return Lo;
+}
+
 static SDOperand LowerGlobalAddress(SDOperand Op, SelectionDAG &DAG) {
   GlobalAddressSDNode *GSDN = cast<GlobalAddressSDNode>(Op);
   GlobalValue *GV = GSDN->getGlobal();
@@ -1652,6 +1683,7 @@ SDOperand PPCTargetLowering::LowerOperation(SDOperand Op, SelectionDAG &DAG) {
   default: assert(0 && "Wasn't expecting to be able to lower this!"); 
   case ISD::ConstantPool:       return LowerConstantPool(Op, DAG);
   case ISD::GlobalAddress:      return LowerGlobalAddress(Op, DAG);
+  case ISD::JumpTable:          return LowerJumpTable(Op, DAG);
   case ISD::SETCC:              return LowerSETCC(Op, DAG);
   case ISD::VASTART:            return LowerVASTART(Op, DAG, VarArgsFrameIndex);
   case ISD::RET:                return LowerRET(Op, DAG);
diff --git a/lib/Target/PowerPC/PPCInstrInfo.td b/lib/Target/PowerPC/PPCInstrInfo.td
index 449c3bd9cd..8333873f08 100644
--- a/lib/Target/PowerPC/PPCInstrInfo.td
+++ b/lib/Target/PowerPC/PPCInstrInfo.td
@@ -702,7 +702,7 @@ def MTCTR : XFXForm_7_ext<31, 467, 9, (ops GPRC:$rS), "mtctr $rS", SprMTSPR>,
 
 def MTLR  : XFXForm_7_ext<31, 467, 8, (ops GPRC:$rS), "mtlr $rS", SprMTSPR>,
             PPC970_DGroup_First, PPC970_Unit_FXU;
-def MFLR  : XFXForm_1_ext<31, 339, 8, (ops GPRC:$rT), "mflr $rT",  SprMFSPR>,
+def MFLR  : XFXForm_1_ext<31, 339, 8, (ops GPRC:$rT), "mflr $rT", SprMFSPR>,
             PPC970_DGroup_First, PPC970_Unit_FXU;
 
 // Move to/from VRSAVE: despite being a SPR, the VRSAVE register is renamed like
@@ -1015,10 +1015,14 @@ def : Pat<(PPChi tglobaladdr:$in, 0), (LIS tglobaladdr:$in)>;
 def : Pat<(PPClo tglobaladdr:$in, 0), (LI tglobaladdr:$in)>;
 def : Pat<(PPChi tconstpool:$in, 0), (LIS tconstpool:$in)>;
 def : Pat<(PPClo tconstpool:$in, 0), (LI tconstpool:$in)>;
+def : Pat<(PPChi tjumptable:$in, 0), (LIS tjumptable:$in)>;
+def : Pat<(PPClo tjumptable:$in, 0), (LI tjumptable:$in)>;
 def : Pat<(add GPRC:$in, (PPChi tglobaladdr:$g, 0)),
           (ADDIS GPRC:$in, tglobaladdr:$g)>;
 def : Pat<(add GPRC:$in, (PPChi tconstpool:$g, 0)),
           (ADDIS GPRC:$in, tconstpool:$g)>;
+def : Pat<(add GPRC:$in, (PPChi tjumptable:$g, 0)),
+          (ADDIS GPRC:$in, tjumptable:$g)>;
 
 // Fused negative multiply subtract, alternate pattern
 def : Pat<(fsub F8RC:$B, (fmul F8RC:$A, F8RC:$C)),
diff --git a/lib/Target/Sparc/SparcAsmPrinter.cpp b/lib/Target/Sparc/SparcAsmPrinter.cpp
index 4565a997e2..dc1ab545d7 100644
--- a/lib/Target/Sparc/SparcAsmPrinter.cpp
+++ b/lib/Target/Sparc/SparcAsmPrinter.cpp
@@ -163,13 +163,9 @@ void SparcAsmPrinter::printOperand(const MachineInstr *MI, int opNum) {
   case MachineOperand::MO_UnextendedImmed:
     O << (int)MO.getImmedValue();
     break;
-  case MachineOperand::MO_MachineBasicBlock: {
-    MachineBasicBlock *MBBOp = MO.getMachineBasicBlock();
-    O << ".LBB" << Mang->getValueName(MBBOp->getParent()->getFunction())
-      << "_" << MBBOp->getNumber () << "\t! "
-      << MBBOp->getBasicBlock ()->getName ();
+  case MachineOperand::MO_MachineBasicBlock:
+    printBasicBlockLabel(MO.getMachineBasicBlock());
     return;
-  }
   case MachineOperand::MO_PCRelativeDisp:
     std::cerr << "Shouldn't use addPCDisp() when building Sparc MachineInstrs";
     abort ();
diff --git a/lib/Target/Sparc/SparcISelDAGToDAG.cpp b/lib/Target/Sparc/SparcISelDAGToDAG.cpp
index 03902382c4..a910b3e047 100644
--- a/lib/Target/Sparc/SparcISelDAGToDAG.cpp
+++ b/lib/Target/Sparc/SparcISelDAGToDAG.cpp
@@ -167,6 +167,7 @@ SparcTargetLowering::SparcTargetLowering(TargetMachine &TM)
   
   // Sparc doesn't have BRCOND either, it has BR_CC.
   setOperationAction(ISD::BRCOND, MVT::Other, Expand);
+  setOperationAction(ISD::BRIND, MVT::i32, Expand);
   setOperationAction(ISD::BR_CC, MVT::i32, Custom);
   setOperationAction(ISD::BR_CC, MVT::f32, Custom);
   setOperationAction(ISD::BR_CC, MVT::f64, Custom);
diff --git a/lib/Target/TargetSelectionDAG.td b/lib/Target/TargetSelectionDAG.td
index 61283ae2df..f37e53c715 100644
--- a/lib/Target/TargetSelectionDAG.td
+++ b/lib/Target/TargetSelectionDAG.td
@@ -150,6 +150,10 @@ def SDTBrcond : SDTypeProfile<0, 2, [ // brcond
   SDTCisInt<0>, SDTCisVT<1, OtherVT>
 ]>;
 
+def SDTBrind : SDTypeProfile<0, 1, [ // brind
+  SDTCisPtrTy<0>
+]>;
+
 def SDTRet : SDTypeProfile<0, 0, []>; // ret
 
 def SDTLoad : SDTypeProfile<1, 1, [ // load
@@ -217,6 +221,10 @@ def constpool   : SDNode<"ISD::ConstantPool",         SDTPtrLeaf, [],
                          "ConstantPoolSDNode">;
 def tconstpool  : SDNode<"ISD::TargetConstantPool",   SDTPtrLeaf, [],
                          "ConstantPoolSDNode">;
+def jumptable   : SDNode<"ISD::JumpTable",            SDTPtrLeaf, [],
+                         "JumpTableSDNode">;
+def tjumptable  : SDNode<"ISD::TargetJumpTable",      SDTPtrLeaf, [],
+                         "JumpTableSDNode">;
 def frameindex  : SDNode<"ISD::FrameIndex",           SDTPtrLeaf, [],
                          "FrameIndexSDNode">;
 def tframeindex : SDNode<"ISD::TargetFrameIndex",     SDTPtrLeaf, [],
@@ -293,6 +301,7 @@ def select     : SDNode<"ISD::SELECT"     , SDTSelect>;
 def selectcc   : SDNode<"ISD::SELECT_CC"  , SDTSelectCC>;
 
 def brcond     : SDNode<"ISD::BRCOND"     , SDTBrcond, [SDNPHasChain]>;
+def brind      : SDNode<"ISD::BRIND"      , SDTBrind,  [SDNPHasChain]>;
 def br         : SDNode<"ISD::BR"         , SDTBr,     [SDNPHasChain]>;
 def ret        : SDNode<"ISD::RET"        , SDTRet,    [SDNPHasChain]>;
 
diff --git a/lib/Target/X86/X86ATTAsmPrinter.cpp b/lib/Target/X86/X86ATTAsmPrinter.cpp
index 5a3490a703..e3c4818085 100755
--- a/lib/Target/X86/X86ATTAsmPrinter.cpp
+++ b/lib/Target/X86/X86ATTAsmPrinter.cpp
@@ -38,6 +38,9 @@ bool X86ATTAsmPrinter::runOnMachineFunction(MachineFunction &MF) {
   // Print out constants referenced by the function
   EmitConstantPool(MF.getConstantPool());
 
+  // Print out jump tables referenced by the function
+  EmitJumpTableInfo(MF.getJumpTableInfo());
+  
   // Print out labels for the function.
   const Function *F = MF.getFunction();
   switch (F->getLinkage()) {
@@ -120,18 +123,21 @@ void X86ATTAsmPrinter::printOperand(const MachineInstr *MI, unsigned OpNo,
       O << '$';
     O << (int)MO.getImmedValue();
     return;
-  case MachineOperand::MO_MachineBasicBlock: {
-    MachineBasicBlock *MBBOp = MO.getMachineBasicBlock();
-    O << PrivateGlobalPrefix << "BB"
-      << Mang->getValueName(MBBOp->getParent()->getFunction())
-      << "_" << MBBOp->getNumber () << "\t# "
-      << MBBOp->getBasicBlock ()->getName ();
+  case MachineOperand::MO_MachineBasicBlock:
+    printBasicBlockLabel(MO.getMachineBasicBlock());
     return;
-  }
   case MachineOperand::MO_PCRelativeDisp:
     std::cerr << "Shouldn't use addPCDisp() when building X86 MachineInstrs";
     abort ();
     return;
+  case MachineOperand::MO_JumpTableIndex: {
+    bool isMemOp  = Modifier && !strcmp(Modifier, "mem");
+    if (!isMemOp) O << '$';
+    O << PrivateGlobalPrefix << "JTI" << getFunctionNumber() << "_"
+      << MO.getJumpTableIndex();
+    // FIXME: PIC relocation model
+    return;
+  }
   case MachineOperand::MO_ConstantPoolIndex: {
     bool isMemOp  = Modifier && !strcmp(Modifier, "mem");
     if (!isMemOp) O << '$';
diff --git a/lib/Target/X86/X86AsmPrinter.cpp b/lib/Target/X86/X86AsmPrinter.cpp
index 990951ea7b..ee1383e6c2 100644
--- a/lib/Target/X86/X86AsmPrinter.cpp
+++ b/lib/Target/X86/X86AsmPrinter.cpp
@@ -54,6 +54,7 @@ bool X86SharedAsmPrinter::doInitialization(Module &M) {
     ZeroDirective = "\t.space\t";  // ".space N" emits N zeros.
     PrivateGlobalPrefix = "L";     // Marker for constant pool idxs
     ConstantPoolSection = "\t.const\n";
+    JumpTableSection = "\t.const\n"; // FIXME: depends on PIC mode
     LCOMMDirective = "\t.lcomm\t";
     COMMDirectiveTakesAlignment = false;
     HasDotTypeDotSizeDirective = false;
@@ -205,6 +206,14 @@ bool X86SharedAsmPrinter::doFinalization(Module &M) {
   return false; // success
 }
 
+void X86SharedAsmPrinter::printBasicBlockLabel(const MachineBasicBlock *MBB) 
+     const {
+  O << PrivateGlobalPrefix << "BB" 
+  << Mang->getValueName(MBB->getParent()->getFunction())
+  << "_" << MBB->getNumber() << '\t' << CommentString
+  << MBB->getBasicBlock()->getName();
+}
+
 /// createX86CodePrinterPass - Returns a pass that prints the X86 assembly code
 /// for a MachineFunction to the given output stream, using the given target
 /// machine description.
diff --git a/lib/Target/X86/X86AsmPrinter.h b/lib/Target/X86/X86AsmPrinter.h
index c4d67b6ac7..fa84c9ec13 100755
--- a/lib/Target/X86/X86AsmPrinter.h
+++ b/lib/Target/X86/X86AsmPrinter.h
@@ -88,6 +88,8 @@ struct X86SharedAsmPrinter : public AsmPrinter {
        MI->getOperand(Op+3).isGlobalAddress() ||
        MI->getOperand(Op+3).isConstantPoolIndex());
   }
+
+  virtual void printBasicBlockLabel(const MachineBasicBlock *MBB) const; 
 };
 
 } // end namespace llvm
diff --git a/lib/Target/X86/X86CodeEmitter.cpp b/lib/Target/X86/X86CodeEmitter.cpp
index 51be7b82de..bac310cd6b 100644
--- a/lib/Target/X86/X86CodeEmitter.cpp
+++ b/lib/Target/X86/X86CodeEmitter.cpp
@@ -35,8 +35,8 @@ namespace {
   class Emitter : public MachineFunctionPass {
     const X86InstrInfo  *II;
     MachineCodeEmitter  &MCE;
-    std::map<const MachineBasicBlock*, unsigned> BasicBlockAddrs;
-    std::vector<std::pair<const MachineBasicBlock *, unsigned> > BBRefs;
+    std::map<MachineBasicBlock*, uint64_t> BasicBlockAddrs;
+    std::vector<std::pair<MachineBasicBlock *, unsigned> > BBRefs;
   public:
     explicit Emitter(MachineCodeEmitter &mce) : II(0), MCE(mce) {}
     Emitter(MachineCodeEmitter &mce, const X86InstrInfo& ii)
@@ -51,9 +51,8 @@ namespace {
     void emitInstruction(const MachineInstr &MI);
 
   private:
-    void emitBasicBlock(const MachineBasicBlock &MBB);
-
-    void emitPCRelativeBlockAddress(const MachineBasicBlock *BB);
+    void emitBasicBlock(MachineBasicBlock &MBB);
+    void emitPCRelativeBlockAddress(MachineBasicBlock *MBB);
     void emitPCRelativeValue(unsigned Address);
     void emitGlobalAddressForCall(GlobalValue *GV, bool isTailCall);
     void emitGlobalAddressForPtr(GlobalValue *GV, int Disp = 0);
@@ -84,8 +83,10 @@ bool Emitter::runOnMachineFunction(MachineFunction &MF) {
 
   MCE.startFunction(MF);
   MCE.emitConstantPool(MF.getConstantPool());
+  MCE.initJumpTableInfo(MF.getJumpTableInfo());
   for (MachineFunction::iterator I = MF.begin(), E = MF.end(); I != E; ++I)
     emitBasicBlock(*I);
+  MCE.emitJumpTableInfo(MF.getJumpTableInfo(), BasicBlockAddrs);
   MCE.finishFunction(MF);
 
   // Resolve all forward branches now...
@@ -99,7 +100,7 @@ bool Emitter::runOnMachineFunction(MachineFunction &MF) {
   return false;
 }
 
-void Emitter::emitBasicBlock(const MachineBasicBlock &MBB) {
+void Emitter::emitBasicBlock(MachineBasicBlock &MBB) {
   if (uint64_t Addr = MCE.getCurrentPCValue())
     BasicBlockAddrs[&MBB] = Addr;
 
@@ -119,11 +120,10 @@ void Emitter::emitPCRelativeValue(unsigned Address) {
 /// (because this is a forward branch), it keeps track of the information
 /// necessary to resolve this address later (and emits a dummy value).
 ///
-void Emitter::emitPCRelativeBlockAddress(const MachineBasicBlock *MBB) {
+void Emitter::emitPCRelativeBlockAddress(MachineBasicBlock *MBB) {
   // If this is a backwards branch, we already know the address of the target,
   // so just emit the value.
-  std::map<const MachineBasicBlock*, unsigned>::iterator I =
-    BasicBlockAddrs.find(MBB);
+  std::map<MachineBasicBlock*,uint64_t>::iterator I = BasicBlockAddrs.find(MBB);
   if (I != BasicBlockAddrs.end()) {
     emitPCRelativeValue(I->second);
   } else {
@@ -242,6 +242,8 @@ void Emitter::emitMemModRMByte(const MachineInstr &MI,
   } else if (Op3.isConstantPoolIndex()) {
     DispVal += MCE.getConstantPoolEntryAddress(Op3.getConstantPoolIndex());
     DispVal += Op3.getOffset();
+  } else if (Op3.isJumpTableIndex()) {
+    DispVal += MCE.getJumpTableEntryAddress(Op3.getJumpTableIndex());
   } else {
     DispVal = Op3.getImmedValue();
   }
@@ -445,6 +447,10 @@ void Emitter::emitInstruction(const MachineInstr &MI) {
         assert(sizeOfImm(Desc) == 4 &&
                "Don't know how to emit non-pointer values!");
         emitExternalSymbolAddress(MO1.getSymbolName(), false, false);
+      } else if (MO1.isJumpTableIndex()) {
+        assert(sizeOfImm(Desc) == 4 &&
+               "Don't know how to emit non-pointer values!");
+        emitConstant(MCE.getJumpTableEntryAddress(MO1.getJumpTableIndex()), 4);
       } else {
         emitConstant(MO1.getImmedValue(), sizeOfImm(Desc));
       }
diff --git a/lib/Target/X86/X86ISelLowering.cpp b/lib/Target/X86/X86ISelLowering.cpp
index db2b5dd5c6..3861fc3594 100644
--- a/lib/Target/X86/X86ISelLowering.cpp
+++ b/lib/Target/X86/X86ISelLowering.cpp
@@ -169,6 +169,7 @@ X86TargetLowering::X86TargetLowering(TargetMachine &TM)
   setOperationAction(ISD::RET             , MVT::Other, Custom);
   // Darwin ABI issue.
   setOperationAction(ISD::ConstantPool    , MVT::i32  , Custom);
+  setOperationAction(ISD::JumpTable       , MVT::i32  , Custom);
   setOperationAction(ISD::GlobalAddress   , MVT::i32  , Custom);
   setOperationAction(ISD::ExternalSymbol  , MVT::i32  , Custom);
   // 64-bit addm sub, shl, sra, srl (iff 32-bit x86)
@@ -2792,8 +2793,8 @@ SDOperand X86TargetLowering::LowerOperation(SDOperand Op, SelectionDAG &DAG) {
     return Chain;
   }
 
-  // ConstantPool, GlobalAddress, and ExternalSymbol are lowered as their
-  // target countpart wrapped in the X86ISD::Wrapper node. Suppose N is
+  // ConstantPool, JumpTable, GlobalAddress, and ExternalSymbol are lowered as 
+  // their target countpart wrapped in the X86ISD::Wrapper node. Suppose N is
   // one of the above mentioned nodes. It has to be wrapped because otherwise
   // Select(N) returns N. So the raw TargetGlobalAddress nodes, etc. can only
   // be used to form addressing mode. These wrapped nodes will be selected
@@ -2812,6 +2813,20 @@ SDOperand X86TargetLowering::LowerOperation(SDOperand Op, SelectionDAG &DAG) {
 
     return Result;
   }
+  case ISD::JumpTable: {
+    JumpTableSDNode *JT = cast<JumpTableSDNode>(Op);
+    SDOperand Result = DAG.getNode(X86ISD::Wrapper, getPointerTy(),
+                                   DAG.getTargetJumpTable(JT->getIndex(),
+                                                          getPointerTy()));
+    if (Subtarget->isTargetDarwin()) {
+      // With PIC, the address is actually $g + Offset.
+      if (getTargetMachine().getRelocationModel() == Reloc::PIC)
+        Result = DAG.getNode(ISD::ADD, getPointerTy(),
+                DAG.getNode(X86ISD::GlobalBaseReg, getPointerTy()), Result);    
+    }
+
+    return Result;
+  }
   case ISD::GlobalAddress: {
     GlobalValue *GV = cast<GlobalAddressSDNode>(Op)->getGlobal();
     SDOperand Result = DAG.getNode(X86ISD::Wrapper, getPointerTy(),
diff --git a/lib/Target/X86/X86InstrInfo.td b/lib/Target/X86/X86InstrInfo.td
index 172f33e901..84d824d8a0 100644
--- a/lib/Target/X86/X86InstrInfo.td
+++ b/lib/Target/X86/X86InstrInfo.td
@@ -365,10 +365,18 @@ let isBranch = 1, isTerminator = 1, noResults = 1 in
   class IBr<bits<8> opcode, dag ops, string asm, list<dag> pattern> :
         I<opcode, RawFrm, ops, asm, pattern>;
 
-// Conditional branches
+// Indirect branches
 let isBarrier = 1 in
   def JMP : IBr<0xE9, (ops brtarget:$dst), "jmp $dst", [(br bb:$dst)]>;
 
+let isBranch = 1, isTerminator = 1, noResults = 1, isBarrier = 1 in {
+  def JMP32r     : I<0xFF, MRM4r, (ops R32:$dst), "jmp{l} {*}$dst",
+                     [(brind R32:$dst)]>;
+  def JMP32m     : I<0xFF, MRM4m, (ops i32mem:$dst), "jmp{l} {*}$dst",
+                     [(brind (loadi32 addr:$dst))]>;
+}
+
+// Conditional branches
 def JE  : IBr<0x84, (ops brtarget:$dst), "je $dst",
               [(X86brcond bb:$dst, X86_COND_E)]>, TB;
 def JNE : IBr<0x85, (ops brtarget:$dst), "jne $dst",
@@ -2302,16 +2310,20 @@ def DWARF_LABEL : I<0, Pseudo, (ops i32imm:$id),
 
 // ConstantPool GlobalAddress, ExternalSymbol
 def : Pat<(i32 (X86Wrapper tconstpool  :$dst)), (MOV32ri tconstpool  :$dst)>;
+def : Pat<(i32 (X86Wrapper tjumptable  :$dst)), (MOV32ri tjumptable  :$dst)>;
 def : Pat<(i32 (X86Wrapper tglobaladdr :$dst)), (MOV32ri tglobaladdr :$dst)>;
 def : Pat<(i32 (X86Wrapper texternalsym:$dst)), (MOV32ri texternalsym:$dst)>;
 
 def : Pat<(add R32:$src1, (X86Wrapper tconstpool:$src2)),
           (ADD32ri R32:$src1, tconstpool:$src2)>;
+def : Pat<(add R32:$src1, (X86Wrapper tjumptable:$src2)),
+          (ADD32ri R32:$src1, tjumptable:$src2)>;
 def : Pat<(add R32:$src1, (X86Wrapper tglobaladdr :$src2)),
           (ADD32ri R32:$src1, tglobaladdr:$src2)>;
 def : Pat<(add R32:$src1, (X86Wrapper texternalsym:$src2)),
           (ADD32ri R32:$src1, texternalsym:$src2)>;
 
+// FIXME: can you really ever store to a constant pool?
 def : Pat<(store (X86Wrapper tconstpool:$src), addr:$dst),
           (MOV32mi addr:$dst, tconstpool:$src)>;
 def : Pat<(store (X86Wrapper tglobaladdr:$src), addr:$dst),
diff --git a/lib/Target/X86/X86IntelAsmPrinter.cpp b/lib/Target/X86/X86IntelAsmPrinter.cpp
index 718a95b9ab..5f758554b3 100755
--- a/lib/Target/X86/X86IntelAsmPrinter.cpp
+++ b/lib/Target/X86/X86IntelAsmPrinter.cpp
@@ -112,14 +112,9 @@ void X86IntelAsmPrinter::printOp(const MachineOperand &MO,
   case MachineOperand::MO_UnextendedImmed:
     O << (int)MO.getImmedValue();
     return;
-  case MachineOperand::MO_MachineBasicBlock: {
-    MachineBasicBlock *MBBOp = MO.getMachineBasicBlock();
-    O << PrivateGlobalPrefix << "BB"
-      << Mang->getValueName(MBBOp->getParent()->getFunction())
-      << "_" << MBBOp->getNumber () << "\t# "
-      << MBBOp->getBasicBlock ()->getName ();
+  case MachineOperand::MO_MachineBasicBlock:
+    printBasicBlockLabel(MO.getMachineBasicBlock());
     return;
-  }
   case MachineOperand::MO_PCRelativeDisp:
     assert(0 && "Shouldn't use addPCDisp() when building X86 MachineInstrs");
     abort ();
diff --git a/utils/TableGen/DAGISelEmitter.cpp b/utils/TableGen/DAGISelEmitter.cpp
index e7ee71564c..e814211191 100644
--- a/utils/TableGen/DAGISelEmitter.cpp
+++ b/utils/TableGen/DAGISelEmitter.cpp
@@ -3225,6 +3225,7 @@ void DAGISelEmitter::EmitInstructionSelector(std::ostream &OS) {
      << "  case ISD::TargetConstant:\n"
      << "  case ISD::TargetConstantPool:\n"
      << "  case ISD::TargetFrameIndex:\n"
+     << "  case ISD::TargetJumpTable:\n"
      << "  case ISD::TargetGlobalAddress: {\n"
      << "    Result = N;\n"
      << "    return;\n"