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

9 files changed, 281 insertions, 11 deletions

diff --git a/lib/CodeGen/AsmPrinter.cpp b/lib/CodeGen/AsmPrinter.cpp
index 11c6f23..48d4a20 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 c0b2cdf..4be2419 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 d37fef4..4243076 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 65c902f..da89ea1 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 973e3ec1..f92c084 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 d635747..6f9e977 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 c0118af..bf95a92 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 ec1050f..c26632a 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 96a81e0..7fcaaf5 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) {