SelectionDAGISel can now natively handle Switch instructions, in the same

manner that the LowerSwitch LLVM to LLVM pass does: emitting a binary
search tree of basic blocks.  The new approach has several advantages:
it is faster, it generates significantly smaller code in many cases, and
it paves the way for implementing dense switch tables as a jump table by
handling switches directly in the instruction selector.

This functionality is currently only enabled on x86, but should be safe for
every target.  In anticipation of making it the default, the cfg is now
properly updated in the x86, ppc, and sparc select lowering code.


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

1 files changed, 28 insertions, 1 deletions

diff --git a/include/llvm/CodeGen/SelectionDAGISel.h b/include/llvm/CodeGen/SelectionDAGISel.h
index 1bdf055c47..2bf3407199 100644
--- a/include/llvm/CodeGen/SelectionDAGISel.h
+++ b/include/llvm/CodeGen/SelectionDAGISel.h
@@ -16,7 +16,8 @@
 #define LLVM_CODEGEN_SELECTIONDAG_ISEL_H
 
 #include "llvm/Pass.h"
-#include "llvm/CodeGen/ValueTypes.h"
+#include "llvm/Constant.h"
+#include "llvm/CodeGen/SelectionDAGNodes.h"
 
 namespace llvm {
   class SelectionDAG;
@@ -66,6 +67,27 @@ public:
   /// to use for this target when scheduling the DAG.
   virtual HazardRecognizer *CreateTargetHazardRecognizer();
   
+  /// CaseBlock - This structure is used to communicate between SDLowering and
+  /// SDISel for the code generation of additional basic blocks needed by multi-
+  /// case switch statements.
+  struct CaseBlock {
+    CaseBlock(ISD::CondCode cc, Value *s, Constant *c, MachineBasicBlock *lhs,
+              MachineBasicBlock *rhs, MachineBasicBlock *me) : 
+    CC(cc), SwitchV(s), CaseC(c), LHSBB(lhs), RHSBB(rhs), ThisBB(me) {}
+    // CC - the condition code to use for the case block's setcc node
+    ISD::CondCode CC;
+    // SwitchV - the value to be switched on, 'foo' in switch(foo)
+    Value *SwitchV;
+    // CaseC - the constant the setcc node will compare against SwitchV
+    Constant *CaseC;
+    // LHSBB - the block to branch to if the setcc is true
+    MachineBasicBlock *LHSBB;
+    // RHSBB - the block to branch to if the setcc is false
+    MachineBasicBlock *RHSBB;
+    // ThisBB - the blcok into which to emit the code for the setcc and branches
+    MachineBasicBlock *ThisBB;
+  };
+  
 protected:
   /// Pick a safe ordering and emit instructions for each target node in the
   /// graph.
@@ -85,8 +107,13 @@ private:
   void BuildSelectionDAG(SelectionDAG &DAG, BasicBlock *LLVMBB,
            std::vector<std::pair<MachineInstr*, unsigned> > &PHINodesToUpdate,
                          FunctionLoweringInfo &FuncInfo);
+  void CodeGenAndEmitDAG(SelectionDAG &DAG);
   void LowerArguments(BasicBlock *BB, SelectionDAGLowering &SDL,
                       std::vector<SDOperand> &UnorderedChains);
+
+  /// SwitchCases - Vector of CaseBlock structures used to communicate
+  /// SwitchInst code generation information.
+  std::vector<CaseBlock> SwitchCases;
 };
 
 }