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, 181 insertions, 4 deletions

diff --git a/include/llvm/CodeGen/AsmPrinter.h b/include/llvm/CodeGen/AsmPrinter.h
index bb948eb..2a56543 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 f5ee2e6..f4b7c22 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 83f696f..0f511e3 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 e98caa5..d02493b 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 0000000..192fb65
--- /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 b2a2a9c..f72285e 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 01f56a9..f05b5b9 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 2bf3407..0e59d7b 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 1b7e8e6..7f317c5 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;