turn things like:

   if (X == 0 || X == 2)

...where the comparisons and branches are in different blocks... into a switch
instruction.  This comes up a lot in various programs, and works well with
the switch/switch merging code I checked earlier.  For example, this testcase:

int switchtest(int C) {
  return C == 0 ? f(123) :
         C == 1 ? f(3123) :
         C == 4 ? f(312) :
         C == 5 ? f(1234): f(444);
}

is converted into this:
        switch int %C, label %cond_false.3 [
                 int 0, label %cond_true.0
                 int 1, label %cond_true.1
                 int 4, label %cond_true.2
                 int 5, label %cond_true.3
        ]

instead of a whole bunch of conditional branches.

Admittedly the code is ugly, and incomplete.  To be complete, we need to add
br -> switch merging and switch -> br merging.  For example, this testcase:

struct foo { int Q, R, Z; };
#define A (X->Q+X->R * 123)
int test(struct foo *X) {
  return A  == 123 ? X1() :
        A == 12321 ? X2():
        (A == 111 || A == 222) ? X3() :
        A == 875 ? X4() : X5();
}

Gets compiled to this:
        switch int %tmp.7, label %cond_false.2 [
                 int 123, label %cond_true.0
                 int 12321, label %cond_true.1
                 int 111, label %cond_true.2
                 int 222, label %cond_true.2
        ]
...
cond_false.2:           ; preds = %entry
        %tmp.52 = seteq int %tmp.7, 875         ; <bool> [#uses=1]
        br bool %tmp.52, label %cond_true.3, label %cond_false.3

where the branch could be folded into the switch.

This kind of thing occurs *ALL OF THE TIME*, especially in programs like
176.gcc, which is a horrible mess of code.  It contains stuff like *shudder*:

#define SWITCH_TAKES_ARG(CHAR) \
  (   (CHAR) == 'D' \
   || (CHAR) == 'U' \
   || (CHAR) == 'o' \
   || (CHAR) == 'e' \
   || (CHAR) == 'u' \
   || (CHAR) == 'I' \
   || (CHAR) == 'm' \
   || (CHAR) == 'L' \
   || (CHAR) == 'A' \
   || (CHAR) == 'h' \
   || (CHAR) == 'z')

and

#define CONST_OK_FOR_LETTER_P(VALUE, C)                 \
  ((C) == 'I' ? SMALL_INTVAL (VALUE)                    \
   : (C) == 'J' ? SMALL_INTVAL (-(VALUE))               \
   : (C) == 'K' ? (unsigned)(VALUE) < 32                \
   : (C) == 'L' ? ((VALUE) & 0xffff) == 0               \
   : (C) == 'M' ? integer_ok_for_set (VALUE)            \
   : (C) == 'N' ? (VALUE) < 0                           \
   : (C) == 'O' ? (VALUE) == 0                          \
   : (C) == 'P' ? (VALUE) >= 0                          \
   : 0)

and

#define LEGITIMIZE_ADDRESS(X,OLDX,MODE,WIN)                     \
{                                                               \
  if (GET_CODE (X) == PLUS && CONSTANT_ADDRESS_P (XEXP (X, 1))) \
    (X) = gen_rtx (PLUS, SImode, XEXP (X, 0),                   \
                   copy_to_mode_reg (SImode, XEXP (X, 1)));     \
  if (GET_CODE (X) == PLUS && CONSTANT_ADDRESS_P (XEXP (X, 0))) \
    (X) = gen_rtx (PLUS, SImode, XEXP (X, 1),                   \
                   copy_to_mode_reg (SImode, XEXP (X, 0)));     \
  if (GET_CODE (X) == PLUS && GET_CODE (XEXP (X, 0)) == MULT)   \
    (X) = gen_rtx (PLUS, SImode, XEXP (X, 1),                   \
                   force_operand (XEXP (X, 0), 0));             \
  if (GET_CODE (X) == PLUS && GET_CODE (XEXP (X, 1)) == MULT)   \
    (X) = gen_rtx (PLUS, SImode, XEXP (X, 0),                   \
                   force_operand (XEXP (X, 1), 0));             \
  if (GET_CODE (X) == PLUS && GET_CODE (XEXP (X, 0)) == PLUS)   \
    (X) = gen_rtx (PLUS, Pmode, force_operand (XEXP (X, 0), NULL_RTX),\
                   XEXP (X, 1));                                \
  if (GET_CODE (X) == PLUS && GET_CODE (XEXP (X, 1)) == PLUS)   \
    (X) = gen_rtx (PLUS, Pmode, XEXP (X, 0),                    \
                   force_operand (XEXP (X, 1), NULL_RTX));      \
  if (GET_CODE (X) == SYMBOL_REF || GET_CODE (X) == CONST       \
           || GET_CODE (X) == LABEL_REF)                        \
    (X) = legitimize_address (flag_pic, X, 0, 0);               \
  if (memory_address_p (MODE, X))                               \
    goto WIN; }

and others.  These macros get used multiple times of course.  These are such
lovely candidates for macros, aren't they?  :)

This code also nicely handles LLVM constructs that look like this:

  if (isa<CastInst>(I))
   ...
  else if (isa<BranchInst>(I))
   ...
  else if (isa<SetCondInst>(I))
   ...
  else if (isa<UnwindInst>(I))
   ...
  else if (isa<VAArgInst>(I))
   ...

where the isa can obviously be a dyn_cast as well.  Switch instructions are a
good thing.


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

1 files changed, 74 insertions, 0 deletions

diff --git a/lib/Transforms/Utils/SimplifyCFG.cpp b/lib/Transforms/Utils/SimplifyCFG.cpp
index ca59276..0ea1079 100644
--- a/lib/Transforms/Utils/SimplifyCFG.cpp
+++ b/lib/Transforms/Utils/SimplifyCFG.cpp
@@ -690,6 +690,80 @@ bool llvm::SimplifyCFG(BasicBlock *BB) {
     return true;
   }
 
+  // If there is a single predecessor for this block, and if this block is a
+  // simple value comparison block (ie, contains X == C), see if we can fold
+  // this comparison into the comparison in our predecessor block, making the
+  // predecessor block terminator into a switch (or adding cases to a
+  // preexisting switch).
+  if (OnlyPred) {
+    if (SetCondInst *SCI = dyn_cast<SetCondInst>(BB->begin()))
+      if (SCI->getOpcode() == Instruction::SetEQ && SCI->hasOneUse() &&
+          isa<BranchInst>(SCI->use_back()) &&
+          SCI->getNext() == cast<BranchInst>(SCI->use_back())) {
+        // Okay, we know we have a block containing (only) a seteq and a
+        // conditional branch instruction.  If an integer value is being
+        // compared, if the comparison value is a constant, then check the
+        // predecessor.
+        BranchInst *BBBr = cast<BranchInst>(BB->getTerminator());
+        Value *CompVal = SCI->getOperand(0);
+        if (ConstantInt *CVal = dyn_cast<ConstantInt>(SCI->getOperand(1))) {
+          // We can do the merge if the predecessor contains either a
+          // conditional branch or a switch instruction which is operating on
+          // the CompVal.
+          if (BranchInst *BI = dyn_cast<BranchInst>(OnlyPred->getTerminator())){
+            // If it is a branch, then it must be a conditional branch,
+            // otherwise we would have merged it in before.  We can only handle
+            // this if the block we are looking at is the 'false' branch.
+            assert(BI->isConditional() &&
+                   "Should have previously merged blocks!");
+            if (SetCondInst *PredSCC= dyn_cast<SetCondInst>(BI->getCondition()))
+              if (PredSCC->getOperand(0) == CompVal &&
+                  PredSCC->getOpcode() == Instruction::SetEQ &&
+                  isa<ConstantInt>(PredSCC->getOperand(1)) &&
+                  BB == BI->getSuccessor(1) &&
+                  SafeToMergeTerminators(BI, BBBr)) {
+                // If the constants being compared are the same, then the
+                // comparison in this block could never come true.
+                if (SCI->getOperand(1) == PredSCC->getOperand(1)) {
+                  // Tell the block to skip over us, making us dead.
+                  BI->setSuccessor(1, BBBr->getSuccessor(1));
+                  AddPredecessorToBlock(BBBr->getSuccessor(1), OnlyPred, BB);
+                  return SimplifyCFG(BB);
+                }
+
+                // Otherwise, create the switch instruction!
+                SwitchInst *SI = new SwitchInst(CompVal, BBBr->getSuccessor(1),
+                                                BI);
+                // Add the edge from our predecessor, and remove the
+                // predecessors (now obsolete branch instruction).  This makes
+                // the current block dead.
+                SI->addCase(cast<Constant>(PredSCC->getOperand(1)),
+                            BI->getSuccessor(0));
+                OnlyPred->getInstList().erase(BI);
+                if (PredSCC->use_empty())
+                  PredSCC->getParent()->getInstList().erase(PredSCC);
+
+                // Add our case...
+                SI->addCase(cast<Constant>(SCI->getOperand(1)),
+                            BBBr->getSuccessor(0));
+
+                AddPredecessorToBlock(BBBr->getSuccessor(0), OnlyPred, BB);
+                AddPredecessorToBlock(BBBr->getSuccessor(1), OnlyPred, BB);
+
+                //std::cerr << "Formed Switch: " << SI;
+
+                // Made a big change!  Now this block is dead, so remove it.
+                return SimplifyCFG(BB);
+              }
+
+          } else if (SwitchInst *SI =
+                     dyn_cast<SwitchInst>(OnlyPred->getTerminator())) {
+
+          }
+        }
+      }
+  }
+
   for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI)
     if (BranchInst *BI = dyn_cast<BranchInst>((*PI)->getTerminator()))
       // Change br (X == 0 | X == 1), T, F into a switch instruction.