Distribute the weight on the edge from switch to default statement to edges generated in lowering switch.

[congh]

Summary

Currently, when edge weights are assigned to edges that are created when lowering switch statement, the weight on the edge to default statement (let's call it "default weight" here) is not considered. We need to distribute this weight properly. However, without value profiling, we have no idea how to distribute it. In this patch, I applied the heuristic that this weight is evenly distributed to successors.

For example, given a switch statement with cases 1,2,3,5,10,11,20, and every edge from switch to each successor has weight 10. If there is a binary search tree built to test if n < 10, then its two out-edges will have weight 4x10+10/2 = 45 and 3x10 + 10/2 = 35 respectively (currently they are 40 and 30 without considering the default weight). Each distribution (which is 5 here) will be stored in each SwitchWorkListItem for further distribution.

There are some exceptions:

1. For a jump table header which doesn't have any edge to default statement, we don't distribute the default weight to it.
2. For a bit test header which covers a contiguous range and hence has no edges to default statement, we don't distribute the default weight to it.
3. When the branch checks a single value or a contiguous range with no edge to default statement, we don't distribute the default weight to it.

In other cases, the default weight is evenly distributed to successors.

[hans]

Thanks for digging into this!

lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp

8049

I think we spell it Fallthrough elsewhere, so maybe rename to FallthroughWeight?

8051

s/distributed/distribute/ ?

8056

Could probably just do "for (MachineBasicBlock *Succ : JumpMBB->successors())" here.

8094

s/distributed/distribute/

8098

shouldn't it be -= on the DefaultWeight?

8100

why do we need this else case?

test/CodeGen/X86/switch-edge-weight.ll

41

It would be super nice if these tests could have comments explaining why these weights are in fact the correct ones.

I don't know if this is a reasonable expectation or not, just throwing it out there - it would make it easier for someone reading the test to verify what's going on.

In this test it seems we'll have four ranges, {1}, {155-159}, {1134} and {1140}. I think the pivot here will be 1134, so the weight on the left is 10+50+10/2=65 and on the right is 10+10+10/5=25, so that matches my expectations. But why are the weights so low below? Shouldn't the edge from the 155-159 range to sw.bb have more weight?

[davidxl]

test/CodeGen/X86/switch-edge-weight.ll

41

The weight distribution makes sense to me.

BB#5 has as test ' %x == 1140'. Since BB#5's weight is 25 and 1140's weight is 10, so this leaves BB#6 15.

BB#6 has check %x == 1134. One successor is 10, and the remaining (part of the default) is 5.

[congh]

lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp

8049

OK.

8056

setSuccWeight() needs an iterator as input and that is why I use iterators in this loop.

8098

Here BTB->DefaultWeight hasn't been updated by adding DefaultWeight to it (it is initialized with UnhandledWeights which doesn't include DefaultWeight) . So it will share a half of it now.

8100

This is because UnhandledWeights doesn't include DefaultWeight. Or I can do this before this branch and use -= in the true body.

test/CodeGen/X86/switch-edge-weight.ll

41

I missed one more check that includes the edge weight from switch to 155-159 range. I will add it here and also add comments explaining why we check those numbers.

[congh]

Update the patch according to Hans's comments. Also add descriptions to the test file explaining what to test.

[hans]

LGTM!

lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp

8100

I see. I think your update made it easier to follow though, and it's nice that it matches the similar code further up.

test/CodeGen/X86/switch-edge-weight.ll

41

Very nice, thanks!

60

The switch has four clusters though, so it becomes a binary tree with range checks in the leafs, just like @test above. Is this one testing something that @test doesn't?

115

s/statement/basic block/

[congh]

Thanks for the review, Hans!

test/CodeGen/X86/switch-edge-weight.ll

60

In this switch statement there are two jump targets instead of 1 in @test. However, I found they are still testing the same thing so I will go ahead and delete this test. Thanks for pointing it out!

115

OK.

lib/CodeGen/SelectionDAG/SelectionDAGBuilder.h

private:
   typedef SmallVector<BitTestCase, 3> BitTestInfo;
 
   struct BitTestBlock {
     BitTestBlock(APInt F, APInt R, const Value *SV, unsigned Rg, MVT RgVT,
                  bool E, bool CR, MachineBasicBlock *P, MachineBasicBlock *D,
                  BitTestInfo C, uint32_t W)
         : First(F), Range(R), SValue(SV), Reg(Rg), RegVT(RgVT), Emitted(E),
           ContiguousRange(CR), Parent(P), Default(D), Cases(std::move(C)),
-          Weight(W) {}
+          Weight(W), DefaultWeight(0) {}
     APInt First;
     APInt Range;
     const Value *SValue;
     unsigned Reg;
     MVT RegVT;
     bool Emitted;
     bool ContiguousRange;
     MachineBasicBlock *Parent;
     MachineBasicBlock *Default;
     BitTestInfo Cases;
     uint32_t Weight;
+    uint32_t DefaultWeight;
   };
 
   /// Minimum jump table density, in percent.
   enum { MinJumpTableDensity = 40 };
 
   /// Check whether a range of clusters is dense enough for a jump table.
   bool isDense(const CaseClusterVector &Clusters, unsigned *TotalCases,
                unsigned First, unsigned Last);
private:
   void findBitTestClusters(CaseClusterVector &Clusters, const SwitchInst *SI);
 
   struct SwitchWorkListItem {
     MachineBasicBlock *MBB;
     CaseClusterIt FirstCluster;
     CaseClusterIt LastCluster;
     const ConstantInt *GE;
     const ConstantInt *LT;
+    uint32_t DefaultWeight;
   };
   typedef SmallVector<SwitchWorkListItem, 4> SwitchWorkList;
 
   /// Determine the rank by weight of CC in [First,Last]. If CC has more weight
   /// than each cluster in the range, its rank is 0.
   static unsigned caseClusterRank(const CaseCluster &CC, CaseClusterIt First,
                                   CaseClusterIt Last);
 

lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp

void SelectionDAGBuilder::visitBitTestHeader(BitTestBlock &B,
   }
 
   B.RegVT = VT.getSimpleVT();
   B.Reg = FuncInfo.CreateReg(B.RegVT);
   SDValue CopyTo = DAG.getCopyToReg(getControlRoot(), dl, B.Reg, Sub);
 
   MachineBasicBlock* MBB = B.Cases[0].ThisBB;
 
-  uint32_t DefaultWeight = getEdgeWeight(SwitchBB, B.Default);
-  addSuccessorWithWeight(SwitchBB, B.Default, DefaultWeight);
+  addSuccessorWithWeight(SwitchBB, B.Default, B.DefaultWeight);
   addSuccessorWithWeight(SwitchBB, MBB, B.Weight);
 
   SDValue BrRange = DAG.getNode(ISD::BRCOND, dl,
                                 MVT::Other, CopyTo, RangeCmp,
                                 DAG.getBasicBlock(B.Default));
 
   // Avoid emitting unnecessary branches to the next block.
   if (MBB != NextBlock(SwitchBB))
for (CaseClusterIt I = W.LastCluster; I > W.FirstCluster; ) {
       if (I->Kind == CC_Range && I->MBB == NextMBB) {
         std::swap(*I, *W.LastCluster);
         break;
       }
     }
   }
 
   // Compute total weight.
-  uint32_t UnhandledWeights = 0;
+  uint32_t DefaultWeight = W.DefaultWeight;
+  uint32_t UnhandledWeights = DefaultWeight;
   for (CaseClusterIt I = W.FirstCluster; I <= W.LastCluster; ++I) {
     UnhandledWeights += I->Weight;
     assert(UnhandledWeights >= I->Weight && "Weight overflow!");
   }
 
   MachineBasicBlock *CurMBB = W.MBB;
   for (CaseClusterIt I = W.FirstCluster, E = W.LastCluster; I <= E; ++I) {
     MachineBasicBlock *Fallthrough;
switch (I->Kind) {
         // FIXME: Optimize away range check based on pivot comparisons.
         JumpTableHeader *JTH = &JTCases[I->JTCasesIndex].first;
         JumpTable *JT = &JTCases[I->JTCasesIndex].second;
 
         // The jump block hasn't been inserted yet; insert it here.
         MachineBasicBlock *JumpMBB = JT->MBB;
         CurMF->insert(BBI, JumpMBB);
 
-        // Collect the sum of weights of outgoing edges from JumpMBB, which will
-        // be the edge weight on CurMBB->JumpMBB.
-        uint32_t JumpWeight = 0;
-        for (auto Succ : JumpMBB->successors())
-          JumpWeight += getEdgeWeight(JumpMBB, Succ);
-        uint32_t FallthruWeight = getEdgeWeight(CurMBB, Fallthrough);
+        uint32_t JumpWeight = I->Weight;
+        uint32_t FallthroughWeight = UnhandledWeights;
 
-        addSuccessorWithWeight(CurMBB, Fallthrough, FallthruWeight);
+        // If Fallthrough is a target of the jump table, we evenly distribute
+        // the weight on the edge to Fallthrough to successors of CurMBB.
+        // Also update the weight on the edge from JumpMBB to Fallthrough.
+        for (MachineBasicBlock::succ_iterator SI = JumpMBB->succ_begin(),
+                                              SE = JumpMBB->succ_end();
+             SI != SE; ++SI) {
+          if (*SI == Fallthrough) {
+            JumpWeight += DefaultWeight / 2;
+            FallthroughWeight -= DefaultWeight / 2;
+            JumpMBB->setSuccWeight(SI, DefaultWeight / 2);
+            break;
+          }
+        }
+
+        addSuccessorWithWeight(CurMBB, Fallthrough, FallthroughWeight);
         addSuccessorWithWeight(CurMBB, JumpMBB, JumpWeight);
 
         // The jump table header will be inserted in our current block, do the
         // range check, and fall through to our fallthrough block.
         JTH->HeaderBB = CurMBB;
         JT->Default = Fallthrough; // FIXME: Move Default to JumpTableHeader.
 
         // If we're in the right place, emit the jump table header right now.
switch (I->Kind) {
         // The bit test blocks haven't been inserted yet; insert them here.
         for (BitTestCase &BTC : BTB->Cases)
           CurMF->insert(BBI, BTC.ThisBB);
 
         // Fill in fields of the BitTestBlock.
         BTB->Parent = CurMBB;
         BTB->Default = Fallthrough;
 
-        // If we're in the right place, emit the bit test header header right now.
-        if (CurMBB ==SwitchMBB) {
+        BTB->DefaultWeight = UnhandledWeights;
+        // If the cases in bit test don't form a contiguous range, we evenly
+        // distribute the weight on the edge to Fallthrough to two successors
+        // of CurMBB.
+        if (!BTB->ContiguousRange) {
+          BTB->Weight += DefaultWeight / 2;
+          BTB->DefaultWeight -= DefaultWeight / 2;
+        }
+
+        // If we're in the right place, emit the bit test header right now.
+        if (CurMBB == SwitchMBB) {
           visitBitTestHeader(*BTB, SwitchMBB);
           BTB->Emitted = true;
         }
         break;
       }
       case CC_Range: {
         const Value *RHS, *LHS, *MHS;
         ISD::CondCode CC;
void SelectionDAGBuilder::splitWorkItem(SwitchWorkList &WorkList,
 
   assert(W.LastCluster - W.FirstCluster + 1 >= 2 && "Too small to split!");
 
   // Balance the tree based on branch weights to create a near-optimal (in terms
   // of search time given key frequency) binary search tree. See e.g. Kurt
   // Mehlhorn "Nearly Optimal Binary Search Trees" (1975).
   CaseClusterIt LastLeft = W.FirstCluster;
   CaseClusterIt FirstRight = W.LastCluster;
-  uint32_t LeftWeight = LastLeft->Weight;
-  uint32_t RightWeight = FirstRight->Weight;
+  uint32_t LeftWeight = LastLeft->Weight + W.DefaultWeight / 2;
+  uint32_t RightWeight = FirstRight->Weight + W.DefaultWeight / 2;
 
   // Move LastLeft and FirstRight towards each other from opposite directions to
   // find a partitioning of the clusters which balances the weight on both
   // sides. If LeftWeight and RightWeight are equal, alternate which side is
   // taken to ensure 0-weight nodes are distributed evenly.
   unsigned I = 0;
   while (LastLeft + 1 < FirstRight) {
     if (LeftWeight < RightWeight || (LeftWeight == RightWeight && (I & 1)))
void SelectionDAGBuilder::splitWorkItem(SwitchWorkList &WorkList,
   MachineBasicBlock *LeftMBB;
   if (FirstLeft == LastLeft && FirstLeft->Kind == CC_Range &&
       FirstLeft->Low == W.GE &&
       (FirstLeft->High->getValue() + 1LL) == Pivot->getValue()) {
     LeftMBB = FirstLeft->MBB;
   } else {
     LeftMBB = FuncInfo.MF->CreateMachineBasicBlock(W.MBB->getBasicBlock());
     FuncInfo.MF->insert(BBI, LeftMBB);
-    WorkList.push_back({LeftMBB, FirstLeft, LastLeft, W.GE, Pivot});
+    WorkList.push_back(
+        {LeftMBB, FirstLeft, LastLeft, W.GE, Pivot, W.DefaultWeight / 2});
     // Put Cond in a virtual register to make it available from the new blocks.
     ExportFromCurrentBlock(Cond);
   }
 
   // Similarly, we will branch to the RHS if Value >= Pivot. If RHS is a
   // single cluster, RHS.Low == Pivot, and we can branch to its destination
   // directly if RHS.High equals the current upper bound.
   MachineBasicBlock *RightMBB;
   if (FirstRight == LastRight && FirstRight->Kind == CC_Range &&
       W.LT && (FirstRight->High->getValue() + 1ULL) == W.LT->getValue()) {
     RightMBB = FirstRight->MBB;
   } else {
     RightMBB = FuncInfo.MF->CreateMachineBasicBlock(W.MBB->getBasicBlock());
     FuncInfo.MF->insert(BBI, RightMBB);
-    WorkList.push_back({RightMBB, FirstRight, LastRight, Pivot, W.LT});
+    WorkList.push_back(
+        {RightMBB, FirstRight, LastRight, Pivot, W.LT, W.DefaultWeight / 2});
     // Put Cond in a virtual register to make it available from the new blocks.
     ExportFromCurrentBlock(Cond);
   }
 
   // Create the CaseBlock record that will be used to lower the branch.
   CaseBlock CB(ISD::SETLT, Cond, Pivot, nullptr, LeftMBB, RightMBB, W.MBB,
                LeftWeight, RightWeight);
 
DEBUG({
     }
     dbgs() << '\n';
   });
 
   assert(!Clusters.empty());
   SwitchWorkList WorkList;
   CaseClusterIt First = Clusters.begin();
   CaseClusterIt Last = Clusters.end() - 1;
-  WorkList.push_back({SwitchMBB, First, Last, nullptr, nullptr});
+  uint32_t DefaultWeight = getEdgeWeight(SwitchMBB, DefaultMBB);
+  WorkList.push_back({SwitchMBB, First, Last, nullptr, nullptr, DefaultWeight});
 
   while (!WorkList.empty()) {
     SwitchWorkListItem W = WorkList.back();
     WorkList.pop_back();
     unsigned NumClusters = W.LastCluster - W.FirstCluster + 1;
 
     if (NumClusters > 3 && TM.getOptLevel() != CodeGenOpt::None) {
       // For optimized builds, lower large range as a balanced binary tree.
       splitWorkItem(WorkList, W, SI.getCondition(), SwitchMBB);
       continue;
     }
 
     lowerWorkItem(W, SI.getCondition(), SwitchMBB, DefaultMBB);
   }
 }

lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp

if (!SDB->BitTestCases[i].Emitted) {
       FuncInfo->InsertPt = FuncInfo->MBB->end();
       // Emit the code
       SDB->visitBitTestHeader(SDB->BitTestCases[i], FuncInfo->MBB);
       CurDAG->setRoot(SDB->getRoot());
       SDB->clear();
       CodeGenAndEmitDAG();
     }
 
-    uint32_t UnhandledWeight = 0;
-    for (unsigned j = 0, ej = SDB->BitTestCases[i].Cases.size(); j != ej; ++j)
-      UnhandledWeight += SDB->BitTestCases[i].Cases[j].ExtraWeight;
+    uint32_t UnhandledWeight = SDB->BitTestCases[i].Weight;
 
     for (unsigned j = 0, ej = SDB->BitTestCases[i].Cases.size(); j != ej; ++j) {
       UnhandledWeight -= SDB->BitTestCases[i].Cases[j].ExtraWeight;
       // Set the current basic block to the mbb we wish to insert the code into
       FuncInfo->MBB = SDB->BitTestCases[i].Cases[j].ThisBB;
       FuncInfo->InsertPt = FuncInfo->MBB->end();
       // Emit the code
 

test/CodeGen/AArch64/aarch64-deferred-spilling.ll

 ;RUN: llc < %s -mtriple=aarch64--linux-android -regalloc=greedy -enable-deferred-spilling=true -mcpu=cortex-a57 | FileCheck %s --check-prefix=CHECK --check-prefix=DEFERRED
 ;RUN: llc < %s -mtriple=aarch64--linux-android -regalloc=greedy -enable-deferred-spilling=false -mcpu=cortex-a57 | FileCheck %s --check-prefix=CHECK --check-prefix=REGULAR
 
 ; Check that we do not end up with useless spill code.
 ;
 ; Move to the basic block we are interested in.
 ;
 ; CHECK: // %if.then.120
 ;
-; REGULAR: str w22, [sp, #[[OFFSET:[0-9]+]]] // 4-byte Folded Spill
-; Check that w22 wouldn't need to be spilled since it is never reused.
-; REGULAR-NOT: {{[wx]}}22{{,?}}
+; REGULAR: str w21, [sp, #[[OFFSET:[0-9]+]]] // 4-byte Folded Spill
+; Check that w21 wouldn't need to be spilled since it is never reused.
+; REGULAR-NOT: {{[wx]}}21{{,?}}
 ;
 ; Check that w22 is used to carry a value through the call.
 ; DEFERRED-NOT: str {{[wx]}}22,
 ; DEFERRED: mov {{[wx]}}22,
 ; DEFERRED-NOT: str {{[wx]}}22,
 ;
 ; CHECK:        bl      fprintf
 ;
 ; DEFERRED-NOT: ldr {{[wx]}}22,
 ; DEFERRED: mov {{[wx][0-9]+}}, {{[wx]}}22
 ; DEFERRED-NOT: ldr {{[wx]}}22,
 ;
-; REGULAR-NOT: {{[wx]}}22{{,?}}
-; REGUAL: ldr w22, [sp, #[[OFFSET]]] // 4-byte Folded Reload
+; REGULAR-NOT: {{[wx]}}21{{,?}}
+; REGULAR: ldr w21, [sp, #[[OFFSET]]] // 4-byte Folded Reload
 ;
 ; End of the basic block we are interested in.
 ; CHECK:        b
 ; CHECK: {{[^:]+}}: // %sw.bb.123
 
 %struct.__sFILE = type { i8*, i32, i32, i32, i32, %struct.__sbuf, i32, i8*, i32 (i8*)*, i32 (i8*, i8*, i32)*, i64 (i8*, i64, i32)*, i32 (i8*, i8*, i32)*, %struct.__sbuf, i8*, i32, [3 x i8], [1 x i8], %struct.__sbuf, i32, i64 }
 %struct.__sbuf = type { i8*, i64 }
 %struct.DState = type { %struct.bz_stream*, i32, i8, i32, i8, i32, i32, i32, i32, i32, i8, i32, i32, i32, i32, i32, [256 x i32], i32, [257 x i32], [257 x i32], i32*, i16*, i8*, i32, i32, i32, i32, i32, [256 x i8], [16 x i8], [256 x i8], [4096 x i8], [16 x i32], [18002 x i8], [18002 x i8], [6 x [258 x i8]], [6 x [258 x i32]], [6 x [258 x i32]], [6 x [258 x i32]], [6 x i32], i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32*, i32*, i32* }

test/CodeGen/ARM/jump-table-islands.ll

 ; RUN: llc -mtriple=armv7-apple-ios8.0 -o - %s | FileCheck %s
 
 %BigInt = type i5500
 
 define %BigInt @test_moved_jumptable(i1 %tst, i32 %sw, %BigInt %l) {
 ; CHECK-LABEL: test_moved_jumptable:
 
 ; CHECK:   adr {{r[0-9]+}}, [[JUMP_TABLE:LJTI[0-9]+_[0-9]+]]
 ; CHECK:   b [[SKIP_TABLE:LBB[0-9]+_[0-9]+]]
 
 ; CHECK: [[JUMP_TABLE]]:
 ; CHECK:   .data_region jt32
 ; CHECK:   .long LBB{{[0-9]+_[0-9]+}}-[[JUMP_TABLE]]
 
 ; CHECK: [[SKIP_TABLE]]:
-; CHECK:   add pc, lr, {{r[0-9]+}}
+; CHECK:   add pc, {{r[0-9]+}}, {{r[0-9]+}}
   br i1 %tst, label %simple, label %complex
 
 simple:
   br label %end
 
 complex:
   switch i32 %sw, label %simple [ i32 0, label %other
                                   i32 1, label %third

test/CodeGen/Generic/MachineBranchProb.ll

entry:
   %conv = sext i32 %x to i64
   switch i64 %conv, label %return [
     i64 0, label %sw.bb
     i64 1, label %sw.bb
     i64 4, label %sw.bb
     i64 5, label %sw.bb1
   ], !prof !0
 ; CHECK: BB#0: derived from LLVM BB %entry
-; CHECK: Successors according to CFG: BB#2(64) BB#4(14)
+; CHECK: Successors according to CFG: BB#2(64) BB#4(21)
 ; CHECK: BB#4: derived from LLVM BB %entry
-; CHECK: Successors according to CFG: BB#1(10) BB#5(4)
+; CHECK: Successors according to CFG: BB#1(10) BB#5(11)
 ; CHECK: BB#5: derived from LLVM BB %entry
 ; CHECK: Successors according to CFG: BB#1(4) BB#3(7)
 
 sw.bb:
   br label %return
 
 sw.bb1:
   br label %return

test/CodeGen/Thumb2/v8_IT_3.ll

; CHECK-NOT: push
   ]
 
 bb:
   %tmp2 = load i32, i32* @G, align 4
   %tmp4 = icmp eq i32 %tmp2, 1
   br i1 %tmp4, label %bb1, label %bb8
 
 bb1:
-; CHECK: %bb6
+; CHECK: %entry
 ; CHECK: it eq
 ; CHECK-NEXT: ldreq
 ; CHECK-NEXT: it  eq
 ; CHECK-NEXT: cmpeq
 ; CHECK: %bb1
   %tmp5 = load i32, i32* %block_size, align 4
   %tmp6 = load i32, i32* %block_count, align 4
   %tmp7 = call %struct.FF* @Get() nounwind
   store %struct.FF* %tmp7, %struct.FF** @FuncPtr, align 4
   %tmp10 = zext i32 %tmp6 to i64
   %tmp11 = zext i32 %tmp5 to i64
   %tmp12 = mul nsw i64 %tmp10, %tmp11
   %tmp13 = call i32 @foo(i8* getelementptr inbounds ([6 x i8], [6 x i8]* @.str1, i32 0, i32 0), i64 %tmp12, i32 %tmp5) nounwind
   br label %bb8
 
 bb4:
 ; CHECK-PIC: cmp
 ; CHECK-PIC: cmp
+; CHECK-PIC: cmp
 ; CHECK-PIC-NEXT: bne
-; CHECK-PIC-NEXT: %bb4
+; CHECK-PIC: %bb6
 ; CHECK-PIC-NEXT: movs
 ; CHECK-PIC-NEXT: add
 ; CHECK-PIC-NEXT: pop
   ret i32 0
 
 bb6:
   ret i32 1
 

test/CodeGen/Thumb2/v8_IT_5.ll

 ; RUN: llc < %s -mtriple=thumbv8 -arm-atomic-cfg-tidy=0 | FileCheck %s
 ; RUN: llc < %s -mtriple=thumbv7 -arm-atomic-cfg-tidy=0 -arm-restrict-it | FileCheck %s
 ; CHECK: it ne
 ; CHECK-NEXT: cmpne
 ; CHECK-NEXT: bne [[JUMPTARGET:.LBB[0-9]+_[0-9]+]]
 ; CHECK: cbz
 ; CHECK-NEXT: %if.else163
 ; CHECK-NEXT: mov.w
 ; CHECK-NEXT: b
+; CHECK: [[JUMPTARGET]]:{{.*}}%if.else173
+; CHECK-NEXT: mov.w
+; CHECK-NEXT: pop
 ; CHECK-NEXT: %if.else145
 ; CHECK-NEXT: mov.w
-; CHECK: [[JUMPTARGET]]:{{.*}}%if.else173
 
 %struct.hc = type { i32, i32, i32, i32 }
 
 define i32 @t(i32 %type) optsize {
 entry:
   br i1 undef, label %if.then, label %if.else
 
 if.then:

test/CodeGen/X86/2006-10-19-SwitchUnnecessaryBranching.ll

 ; RUN: llc < %s -march=x86 -asm-verbose | FileCheck %s
 
 @str = internal constant [14 x i8] c"Hello world!\0A\00"    ; <[14 x i8]*> [#uses=1]
 @str.upgrd.1 = internal constant [13 x i8] c"Blah world!\0A\00"    ; <[13 x i8]*> [#uses=1]
 
 define i32 @test(i32 %argc, i8** %argv) nounwind {
 entry:
 ; CHECK: cmpl $2
-; CHECK-NEXT: jne
-; CHECK-NEXT: %bb2
+; CHECK-NEXT: je
+; CHECK-NEXT: %entry
 
   switch i32 %argc, label %UnifiedReturnBlock [
      i32 1, label %bb
      i32 2, label %bb2
   ]
 
 bb:   ; preds = %entry
   %tmp1 = tail call i32 (i8*, ...) @printf( i8* getelementptr ([14 x i8], [14 x i8]* @str, i32 0, i64 0) )    ; <i32> [#uses=0]

test/CodeGen/X86/switch-bt.ll

 ; RUN: llc -march=x86-64 -asm-verbose=false < %s | FileCheck %s
 
 ; This switch should use bit tests, and the third bit test case is just
 ; testing for one possible value, so it doesn't need a bt.
 
 ;      CHECK: movabsq $2305843009482129440, %r
 ; CHECK-NEXT: btq %rax, %r
-; CHECK-NEXT: jae
+; CHECK-NEXT: jb
 ;     CHECK: movl  $671088640, %e
 ; CHECK-NEXT: btq %rax, %r
 ; CHECK-NEXT: jae
 ;      CHECK: testq %rax, %r
 ; CHECK-NEXT: j
 
 define void @test(i8* %l) nounwind {
 entry:

 
 ; The balanced binary switch here would start with a comparison against 39, but
 ; it is currently starting with 29 because of the density-sum heuristic.
 ; CHECK: cmpl $39
 ; CHECK: jg
 ; CHECK: cmpl $10
 ; CHECK: je
 ; CHECK: cmpl $20
+; CHECK: je
+; CHECK: cmpl $30
 ; CHECK: jne
 ; CHECK: cmpl $40
 ; CHECK: je
 ; CHECK: cmpl $50
-; CHECK: jne
-; CHECK: cmpl $30
-; CHECK: jne
+; CHECK: je
 ; CHECK: cmpl $60
 ; CHECK: jne
 }

test/CodeGen/X86/switch-edge-weight.ll

 ; RUN: llc -march=x86-64 -print-machineinstrs=expand-isel-pseudos %s -o /dev/null 2>&1 | FileCheck %s
 
+declare void @foo(i32)
 
 ; CHECK-LABEL: test
 
 define void @test(i32 %x) nounwind {
 entry:
   switch i32 %x, label %sw.default [
-    i32 54, label %sw.bb
-    i32 55, label %sw.bb
-    i32 56, label %sw.bb
-    i32 58, label %sw.bb
-    i32 67, label %sw.bb
-    i32 68, label %sw.bb
-    i32 134, label %sw.bb
-    i32 140, label %sw.bb
+    i32 1, label %sw.bb
+    i32 155, label %sw.bb
+    i32 156, label %sw.bb
+    i32 157, label %sw.bb
+    i32 158, label %sw.bb
+    i32 159, label %sw.bb
+    i32 1134, label %sw.bb
+    i32 1140, label %sw.bb
   ], !prof !1
 
 sw.bb:
   call void @foo(i32 0)
   br label %sw.epilog
 
 sw.default:
   call void @foo(i32 1)
   br label %sw.epilog
 
 sw.epilog:
   ret void
 
 ; Check if weights are correctly assigned to edges generated from switch
 ; statement.
 ;
+; CHECK: BB#0:
+; BB#0 to BB#4: [0, 1133] (65 = 60 + 5)
+; BB#0 to BB#5: [1134, UINT32_MAX] (25 = 20 + 5)
+; CHECK: Successors according to CFG: BB#4(65) BB#5(25)
+;
 ; CHECK: BB#4:
-; CHECK: Successors according to CFG: BB#1(10) BB#6(10)
+; BB#4 to BB#1: [155, 159] (50)
+; BB#4 to BB#5: [0, 1133] - [155, 159] (15 = 10 + 5)
+; CHECK: Successors according to CFG: BB#1(50) BB#7(15)
+;
+; CHECK: BB#5:
+; BB#5 to BB#1: {1140} (10)
+; BB#5 to BB#6: [1134, UINT32_MAX] - {1140} (15 = 10 + 5)
+; CHECK: Successors according to CFG: BB#1(10) BB#6(15)
+;
 ; CHECK: BB#6:
-; CHECK: Successors according to CFG: BB#1(10) BB#2(10)
+; BB#6 to BB#1: {1134} (10)
+; BB#6 to BB#2: [1134, UINT32_MAX] - {1134, 1140} (5)
+; CHECK: Successors according to CFG: BB#1(10) BB#2(5)
 }
 
-declare void @foo(i32)
+; CHECK-LABEL: test2
+
+define void @test2(i32 %x) nounwind {
+entry:
+
+; This switch statement will be translated into range checks.
+
+  switch i32 %x, label %sw.default [
+    i32 1, label %sw.bb
+    i32 155, label %sw.bb
+    i32 156, label %sw.bb2
+    i32 157, label %sw.bb2
+    i32 1000, label %sw.bb
+  ], !prof !2
+
+sw.bb:
+  call void @foo(i32 0)
+  br label %sw.epilog
+
+sw.bb2:
+  call void @foo(i32 2)
+  br label %sw.epilog
+
+sw.default:
+  call void @foo(i32 1)
+  br label %sw.epilog
+
+sw.epilog:
+  ret void
+
+; Check if weights are correctly assigned to edges generated from switch
+; statement.
+;
+; CHECK: BB#0:
+; BB#0 to BB#5: [0, 155] (25 = 20 + 5)
+; BB#0 to BB#6: [156, UINT32_MAX] (35 = 30 + 5)
+; CHECK: Successors according to CFG: BB#5(25) BB#6(35)
+;
+; CHECK: BB#5:
+; BB#5 to BB#1: {1} (10)
+; BB#5 to BB#8: [0, 155] - {1} (15 = 10 + 5)
+; CHECK: Successors according to CFG: BB#1(10) BB#8(15)
+;
+; CHECK: BB#6:
+; BB#6 to BB#2: [156, 157] (20)
+; BB#6 to BB#7: [158, UINT32_MAX] (15 = 10 + 5)
+; CHECK: Successors according to CFG: BB#2(20) BB#7(15)
+;
+; CHECK: BB#7:
+; BB#7 to BB#1: {1000} (10)
+; BB#7 to BB#3: [158, UINT32_MAX] - {1000} (5)
+; CHECK: Successors according to CFG: BB#1(10) BB#3(5)
+}
+
+; CHECK-LABEL: test3
+
+define void @test3(i32 %x) nounwind {
+entry:
+
+; In this switch statement, there is an edge from jump table to default
+; statement.
+
+  switch i32 %x, label %sw.default [
+    i32 1, label %sw.bb
+    i32 10, label %sw.bb2
+    i32 11, label %sw.bb3
+    i32 12, label %sw.bb4
+    i32 13, label %sw.bb5
+    i32 14, label %sw.bb5
+  ], !prof !3
+
+sw.bb:
+  call void @foo(i32 0)
+  br label %sw.epilog
+
+sw.bb2:
+  call void @foo(i32 2)
+  br label %sw.epilog
+
+sw.bb3:
+  call void @foo(i32 3)
+  br label %sw.epilog
+
+sw.bb4:
+  call void @foo(i32 4)
+  br label %sw.epilog
+
+sw.bb5:
+  call void @foo(i32 5)
+  br label %sw.epilog
+
+sw.default:
+  call void @foo(i32 1)
+  br label %sw.epilog
+
+sw.epilog:
+  ret void
+
+; Check if weights are correctly assigned to edges generated from switch
+; statement.
+;
+; CHECK: BB#0:
+; BB#0 to BB#6: {0} + [15, UINT32_MAX] (5)
+; BB#0 to BB#8: [1, 14] (jump table) (65 = 60 + 5)
+; CHECK: Successors according to CFG: BB#6(5) BB#8(65)
+;
+; CHECK: BB#8:
+; BB#8 to BB#1: {1} (10)
+; BB#8 to BB#6: [2, 9] (5)
+; BB#8 to BB#2: {10} (10)
+; BB#8 to BB#3: {11} (10)
+; BB#8 to BB#4: {12} (10)
+; BB#8 to BB#5: {13, 14} (20)
+; CHECK: Successors according to CFG: BB#1(10) BB#6(5) BB#2(10) BB#3(10) BB#4(10) BB#5(20)
+}
+
+; CHECK-LABEL: test4
+
+define void @test4(i32 %x) nounwind {
+entry:
+
+; In this switch statement, there is no edge from jump table to default
+; statement.
+
+  switch i32 %x, label %sw.default [
+    i32 10, label %sw.bb
+    i32 11, label %sw.bb2
+    i32 12, label %sw.bb3
+    i32 13, label %sw.bb4
+    i32 14, label %sw.bb5
+  ], !prof !2
+
+sw.bb:
+  call void @foo(i32 0)
+  br label %sw.epilog
+
+sw.bb2:
+  call void @foo(i32 2)
+  br label %sw.epilog
+
+sw.bb3:
+  call void @foo(i32 3)
+  br label %sw.epilog
+
+sw.bb4:
+  call void @foo(i32 4)
+  br label %sw.epilog
+
+sw.bb5:
+  call void @foo(i32 5)
+  br label %sw.epilog
+
+sw.default:
+  call void @foo(i32 1)
+  br label %sw.epilog
+
+sw.epilog:
+  ret void
+
+; Check if weights are correctly assigned to edges generated from switch
+; statement.
+;
+; CHECK: BB#0:
+; BB#0 to BB#6: [0, 9] + [15, UINT32_MAX] {10}
+; BB#0 to BB#8: [10, 14] (jump table) (50)
+; CHECK: Successors according to CFG: BB#6(10) BB#8(50)
+;
+; CHECK: BB#8:
+; BB#8 to BB#1: {10} (10)
+; BB#8 to BB#2: {11} (10)
+; BB#8 to BB#3: {12} (10)
+; BB#8 to BB#4: {13} (10)
+; BB#8 to BB#5: {14} (10)
+; CHECK: Successors according to CFG: BB#1(10) BB#2(10) BB#3(10) BB#4(10) BB#5(10)
+}
+
+; CHECK-LABEL: test5
+
+define void @test5(i32 %x) nounwind {
+entry:
+
+; In this switch statement, there is no edge from bit test to default statement.
+
+  switch i32 %x, label %sw.default [
+    i32 1, label %sw.bb
+    i32 111, label %sw.bb2
+    i32 112, label %sw.bb3
+    i32 113, label %sw.bb3
+    i32 114, label %sw.bb2
+    i32 115, label %sw.bb2
+  ], !prof !3
+
+sw.bb:
+  call void @foo(i32 0)
+  br label %sw.epilog
+
+sw.bb2:
+  call void @foo(i32 2)
+  br label %sw.epilog
+
+sw.bb3:
+  call void @foo(i32 3)
+  br label %sw.epilog
+
+sw.default:
+  call void @foo(i32 1)
+  br label %sw.epilog
+
+sw.epilog:
+  ret void
+
+; Check if weights are correctly assigned to edges generated from switch
+; statement.
+;
+; CHECK: BB#0:
+; BB#0 to BB#6: [0, 110] + [116, UINT32_MAX] (20)
+; BB#0 to BB#7: [111, 115] (bit test) (50)
+; CHECK: Successors according to CFG: BB#6(20) BB#7(50)
+;
+; CHECK: BB#7:
+; BB#7 to BB#2: {111, 114, 115} (30)
+; BB#7 to BB#3: {112, 113} (20)
+; CHECK: Successors according to CFG: BB#2(30) BB#3(20)
+}
 
 !1 = !{!"branch_weights", i32 10, i32 10, i32 10, i32 10, i32 10, i32 10, i32 10, i32 10, i32 10} 
+!2 = !{!"branch_weights", i32 10, i32 10, i32 10, i32 10, i32 10, i32 10} 
+!3 = !{!"branch_weights", i32 10, i32 10, i32 10, i32 10, i32 10, i32 10, i32 10} 

test/CodeGen/X86/switch-order-weight.ll

 ; 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-LABEL: test1:
 ; CHECK-NOT: unr
 ; CHECK: cmpl $10
-; CHECK: bar
 ; CHECK: cmpl $20
+; CHECK: bar
 
 if.then:
   tail call void @unr(i32 23) noreturn nounwind
   unreachable
 
 if.then2:
   tail call void @bar(i32 42) nounwind
   br label %if.end7

test/CodeGen/X86/switch.ll

 bb0: tail call void @g(i32 0) br label %return
 bb1: tail call void @g(i32 1) br label %return
 return: ret void
 
 ; Should be lowered to two range checks.
 ; CHECK-LABEL: simple_ranges
 ; CHECK: leal -100
 ; CHECK: cmpl $4
-; CHECK: jae
+; CHECK: jb
 ; CHECK: cmpl $3
 ; CHECK: ja
 
 ; We do this even at -O0, because it's cheap and makes codegen faster.
 ; NOOPT-LABEL: simple_ranges
 ; NOOPT: subl $4
 ; NOOPT: jb
 ; NOOPT: addl $-100