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: