From 56442dfdcf7b07c04b585de5205b9427b1739895 Mon Sep 17 00:00:00 2001
From: Benjamin Kramer <benny.kra@googlemail.com>
Date: Wed, 2 Feb 2011 15:56:22 +0000
Subject: SimplifyCFG: Turn switches into sub+icmp+branch if possible.

This makes the job of the later optzn passes easier, allowing the vast amount of
icmp transforms to chew on it.

We transform 840 switches in gcc.c, leading to a 16k byte shrink of the resulting
binary on i386-linux.

The testcase from README.txt now compiles into
  decl  %edi
  cmpl  $3, %edi
  sbbl  %eax, %eax
  andl  $1, %eax
  ret

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@124724 91177308-0d34-0410-b5e6-96231b3b80d8
---
 lib/Transforms/Utils/SimplifyCFG.cpp | 32 ++++++++++++++++++++++++++++++++
 1 file changed, 32 insertions(+)

(limited to 'lib/Transforms')

diff --git a/lib/Transforms/Utils/SimplifyCFG.cpp b/lib/Transforms/Utils/SimplifyCFG.cpp
index b9432c2..bf753dc 100644
--- a/lib/Transforms/Utils/SimplifyCFG.cpp
+++ b/lib/Transforms/Utils/SimplifyCFG.cpp
@@ -2237,6 +2237,34 @@ bool SimplifyCFGOpt::SimplifyUnreachable(UnreachableInst *UI) {
   return Changed;
 }
 
+/// TurnSwitchRangeIntoICmp - Turns a switch with that contains only a
+/// integer range comparison into a sub, an icmp and a branch.
+static bool TurnSwitchRangeIntoICmp(SwitchInst *SI) {
+  assert(SI->getNumCases() > 2 && "Degenerate switch?");
+  // We can do this transform if the switch consists of an ascending series
+  // and all cases point to the same destination.
+  for (unsigned I = 2, E = SI->getNumCases(); I != E; ++I)
+    if (SI->getSuccessor(I-1) != SI->getSuccessor(I) ||
+        SI->getCaseValue(I-1)->getValue()+1 != SI->getCaseValue(I)->getValue())
+      return false;
+
+  Constant *Offset = ConstantExpr::getNeg(SI->getCaseValue(1));
+  Constant *NumCases = ConstantInt::get(Offset->getType(), SI->getNumCases()-1);
+
+  Value *Sub = BinaryOperator::CreateAdd(SI->getCondition(), Offset, "off", SI);
+  Value *Cmp = new ICmpInst(SI, ICmpInst::ICMP_ULT, Sub, NumCases, "switch");
+  BranchInst::Create(SI->getSuccessor(1), SI->getDefaultDest(), Cmp, SI);
+
+  // Prune obsolete incoming values off the successor's PHI nodes.
+  for (BasicBlock::iterator BBI = SI->getSuccessor(1)->begin();
+       isa<PHINode>(BBI); ++BBI) {
+    for (unsigned I = 0, E = SI->getNumCases()-2; I != E; ++I)
+      cast<PHINode>(BBI)->removeIncomingValue(SI->getParent());
+  }
+  SI->eraseFromParent();
+
+  return true;
+}
 
 bool SimplifyCFGOpt::SimplifySwitch(SwitchInst *SI) {
   // If this switch is too complex to want to look at, ignore it.
@@ -2260,6 +2288,10 @@ bool SimplifyCFGOpt::SimplifySwitch(SwitchInst *SI) {
   if (SI == &*BBI)
     if (FoldValueComparisonIntoPredecessors(SI))
       return SimplifyCFG(BB) | true;
+
+  // Try to transform the switch into an icmp and a branch.
+  if (TurnSwitchRangeIntoICmp(SI))
+    return SimplifyCFG(BB) | true;
   
   return false;
 }
-- 
cgit v1.1