Prevent binary-tree deterioration in sparse trees.

[djasper]

Summary

This address part of llvm.org/PR22262. Specifically, it prevents counting a single element as having a density of 1 and thereby outweighing all other split points.

This is not a complete solution but works around the most pressing issue.

[chandlerc]

If Hans is OK with this as an interim solution, I am too. I would still like to see us split off table regions.

[hans]

I'm fine with this as an incremental improvement.

test/CodeGen/X86/switch-jump-table.ll

55 ↗

(On Diff #18443)

I'm not sure this test is in the right file. Is there a file dealing with binary tree lowering issues? If not, maybe we should have one?

91 ↗

(On Diff #18443)

Maybe this comment could be improved to reflect that 39 would be the ideal, but 29 is what it's currently doing. Otherwise, the diff between what the comment is saying and the test is testing could be confusing.

[djasper]

test/CodeGen/X86/switch-jump-table.ll

55 ↗

(On Diff #18443)

Moved to a different file.

91 ↗

(On Diff #18443)

Done.

[djasper]

Updated according to comments.
Also didn't just check for 1-element subsets, but for sets that are < TLI.getMinimumJumpTableEntries() as the density of those doesn't interest us.

[hans]

Still lgtm.

lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp

2434

Maybe add a comment about why we're doing this check?

[djasper]

Addressed comment and submitted as r226600.

lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp

2434

Done.

lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp

for (CaseItr I = CR.Range.first, E = CR.Range.second;
        I!=E; ++I)
     TSize += I->size();
 
   APInt LSize = FrontCase.size();
   APInt RSize = TSize-LSize;
   DEBUG(dbgs() << "Selecting best pivot: \n"
                << "First: " << First << ", Last: " << Last <<'\n'
                << "LSize: " << LSize << ", RSize: " << RSize << '\n');
+  const TargetLowering &TLI = DAG.getTargetLoweringInfo();
   for (CaseItr I = CR.Range.first, J=I+1, E = CR.Range.second;
        J!=E; ++I, ++J) {
     const APInt &LEnd = cast<ConstantInt>(I->High)->getValue();
     const APInt &RBegin = cast<ConstantInt>(J->Low)->getValue();
     APInt Range = ComputeRange(LEnd, RBegin);
     assert((Range - 2ULL).isNonNegative() &&
            "Invalid case distance");
     // Use volatile double here to avoid excess precision issues on some hosts,
     // e.g. that use 80-bit X87 registers.
     volatile double LDensity =
-        LSize.roundToDouble() / (LEnd - First + 1ULL).roundToDouble();
+        LSize.ult(TLI.getMinimumJumpTableEntries())
+            ? 0.0
+            : LSize.roundToDouble() / (LEnd - First + 1ULL).roundToDouble();
     volatile double RDensity =
-        RSize.roundToDouble() / (Last - RBegin + 1ULL).roundToDouble();
+        RSize.ult(TLI.getMinimumJumpTableEntries())
+            ? 0.0
+            : RSize.roundToDouble() / (Last - RBegin + 1ULL).roundToDouble();
     volatile double Metric = Range.logBase2() * (LDensity + RDensity);
     // Should always split in some non-trivial place
     DEBUG(dbgs() <<"=>Step\n"
                  << "LEnd: " << LEnd << ", RBegin: " << RBegin << '\n'
                  << "LDensity: " << LDensity
                  << ", RDensity: " << RDensity << '\n'
                  << "Metric: " << Metric << '\n');
     if (FMetric < Metric) {
       Pivot = J;
       FMetric = Metric;
       DEBUG(dbgs() << "Current metric set to: " << FMetric << '\n');
     }
 
     LSize += J->size();
     RSize -= J->size();
   }
 
-  const TargetLowering &TLI = DAG.getTargetLoweringInfo();
-  if (areJTsAllowed(TLI)) {
-    // If our case is dense we *really* should handle it earlier!
-    assert((FMetric > 0) && "Should handle dense range earlier!");
-  } else {
+  if (FMetric == 0 || !areJTsAllowed(TLI))
     Pivot = CR.Range.first + Size/2;
-  }
   splitSwitchCase(CR, Pivot, WorkList, SV, SwitchBB);
   return true;
 }
 
 void SelectionDAGBuilder::splitSwitchCase(CaseRec &CR, CaseItr Pivot,
                                           CaseRecVector &WorkList,
                                           const Value *SV,
                                           MachineBasicBlock *SwitchBB) {

test/CodeGen/X86/switch-bt.ll

switch i32 %x, label %if.end [
     i32 5, label %if.then
   ]
 if.then:
   tail call void @bar() nounwind
   ret void
 if.end:
   ret void
 }
+
+; Ensure that optimizing for jump tables doesn't needlessly deteriorate the
+; created binary tree search. See PR22262.
+define void @test4(i32 %x, i32* %y) {
+; CHECK-LABEL: test4:
+
+entry:
+  switch i32 %x, label %sw.default [
+    i32 10, label %sw.bb
+    i32 20, label %sw.bb1
+    i32 30, label %sw.bb2
+    i32 40, label %sw.bb3
+    i32 50, label %sw.bb4
+    i32 60, label %sw.bb5
+  ]
+sw.bb:
+  store i32 1, i32* %y
+  br label %sw.epilog
+sw.bb1:
+  store i32 2, i32* %y
+  br label %sw.epilog
+sw.bb2:
+  store i32 3, i32* %y
+  br label %sw.epilog
+sw.bb3:
+  store i32 4, i32* %y
+  br label %sw.epilog
+sw.bb4:
+  store i32 5, i32* %y
+  br label %sw.epilog
+sw.bb5:
+  store i32 6, i32* %y
+  br label %sw.epilog
+sw.default:
+  store i32 7, i32* %y
+  br label %sw.epilog
+sw.epilog:
+  ret void
+
+; 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 $29
+; CHECK: jg
+; CHECK: cmpl $10
+; CHECK: jne
+; CHECK: cmpl $49
+; CHECK: jg
+; CHECK: cmpl $30
+; CHECK: jne
+; CHECK: cmpl $20
+; CHECK: jne
+; CHECK: cmpl $50
+; CHECK: jne
+; CHECK: cmpl $40
+; CHECK: jne
+; CHECK: cmpl $60
+; CHECK: jne
+}