From f2beccf6b4e9eb59b5080ae866e8d59a38679f15 Mon Sep 17 00:00:00 2001
From: Benjamin Kramer <benny.kra@googlemail.com>
Date: Sat, 26 May 2012 20:01:32 +0000
Subject: [PATCH] SelectionDAGBuilder: When emitting small compare chains for
 switches order them by using edge weights.

SimplifyCFG tends to form a lot of 2-3 case switches when merging branches. Move
the most likely condition to the front so it is checked first and the others can
be skipped. This is currently not as effective as it could be because SimplifyCFG
destroys profiling metadata when merging branches and switches. Merging branch
weight metadata is tricky though.

This code touches at most 3 cases so I didn't use a proper sorting algorithm.

llvm-svn: 157521
---
 .../CodeGen/SelectionDAG/SelectionDAGBuilder.cpp   | 21 ++++++++++--
 llvm/test/CodeGen/X86/switch-order-weight.ll       | 37 ++++++++++++++++++++++
 2 files changed, 55 insertions(+), 3 deletions(-)
 create mode 100644 llvm/test/CodeGen/X86/switch-order-weight.ll

diff --git a/llvm/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp b/llvm/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp
index a9b7f66..0d37c62 100644
--- a/llvm/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp
+++ b/llvm/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp
@@ -1903,8 +1903,6 @@ bool SelectionDAGBuilder::handleSmallSwitchRange(CaseRec& CR,
                                                  const Value* SV,
                                                  MachineBasicBlock *Default,
                                                  MachineBasicBlock *SwitchBB) {
-  Case& BackCase  = *(CR.Range.second-1);
-
   // Size is the number of Cases represented by this range.
   size_t Size = CR.Range.second - CR.Range.first;
   if (Size > 3)
@@ -1972,11 +1970,28 @@ bool SelectionDAGBuilder::handleSmallSwitchRange(CaseRec& CR,
     }
   }
 
+  // Order cases by weight so the most likely case will be checked first.
+  BranchProbabilityInfo *BPI = FuncInfo.BPI;
+  if (BPI) {
+    for (CaseItr I = CR.Range.first, IE = CR.Range.second; I != IE; ++I) {
+      uint32_t IWeight = BPI->getEdgeWeight(SwitchBB->getBasicBlock(),
+                                            I->BB->getBasicBlock());
+      for (CaseItr J = CR.Range.first; J < I; ++J) {
+        uint32_t JWeight = BPI->getEdgeWeight(SwitchBB->getBasicBlock(),
+                                              J->BB->getBasicBlock());
+        if (IWeight > JWeight)
+          std::swap(*I, *J);
+      }
+    }
+  }
+
   // Rearrange the case blocks so that the last one falls through if possible.
+  Case &BackCase = *(CR.Range.second-1);
   if (NextBlock && Default != NextBlock && BackCase.BB != NextBlock) {
     // The last case block won't fall through into 'NextBlock' if we emit the
     // branches in this order.  See if rearranging a case value would help.
-    for (CaseItr I = CR.Range.first, E = CR.Range.second-1; I != E; ++I) {
+    // We start at the bottom as it's the case with the least weight.
+    for (CaseItr I = CR.Range.second-2, E = CR.Range.first-1; I != E; --I) {
       if (I->BB == NextBlock) {
         std::swap(*I, BackCase);
         break;
diff --git a/llvm/test/CodeGen/X86/switch-order-weight.ll b/llvm/test/CodeGen/X86/switch-order-weight.ll
new file mode 100644
index 0000000..0fdd56d
--- /dev/null
+++ b/llvm/test/CodeGen/X86/switch-order-weight.ll
@@ -0,0 +1,37 @@
+; RUN: llc -mtriple=x86_64-apple-darwin11 < %s | FileCheck %s
+
+; Check that the cases which lead to unreachable are checked after "10"
+
+define void @test1(i32 %x) nounwind uwtable ssp {
+entry:
+  switch i32 %x, label %if.end7 [
+    i32 0, label %if.then
+    i32 10, label %if.then2
+    i32 20, label %if.then5
+  ]
+
+; CHECK: test1:
+; CHECK-NOT: unr
+; CHECK: cmpl $10
+; CHECK: bar
+; CHECK: cmpl $20
+
+if.then:
+  tail call void @unr(i32 23) noreturn nounwind
+  unreachable
+
+if.then2:
+  tail call void @bar(i32 42) nounwind
+  br label %if.end7
+
+if.then5:
+  tail call void @unr(i32 5) noreturn nounwind
+  unreachable
+
+if.end7:
+  ret void
+}
+
+declare void @unr(i32) noreturn
+
+declare void @bar(i32)
-- 
2.7.4