Introduction of improved switch lowering.

src/IceTargetLoweringX86BaseImpl.h

Index: src/IceTargetLoweringX86BaseImpl.h
diff --git a/src/IceTargetLoweringX86BaseImpl.h b/src/IceTargetLoweringX86BaseImpl.h
index a277db23adc70e92847a998e9dd6ac8e9e1a6454..4e37d26b0eb05519ec58e69e232859669ecf90bc 100644
--- a/src/IceTargetLoweringX86BaseImpl.h
+++ b/src/IceTargetLoweringX86BaseImpl.h
@@ -28,6 +28,8 @@
 #include "IceUtils.h"
 #include "llvm/Support/MathExtras.h"
 
+#include <stack>
+
 namespace Ice {
 namespace X86Internal {
 
@@ -4491,49 +4493,245 @@ template <class Machine> void TargetX86Base<Machine>::doAddressOptStore() {
 }
 
 template <class Machine>
+Operand *TargetX86Base<Machine>::lowerCmpRange(Operand *Comparison,
+                                               uint64_t Min,
+                                               uint64_t Max) {
+  // Subtracting 0 is a nop so don't do it
+  if (Min != 0) {
+    // Avoid clobbering the comparison by copying it
+    Variable *T = nullptr;
+    _mov(T, Comparison);
+    _sub(T, Ctx->getConstantInt32(Min));

[Jim Stichnoth, 2015/07/15 19:17:43]

Here and below, there seem to be assumptions that the uint64_t Min/Max values
actually fit into 32 bits.  This is either a bug, or needs to be
clarified/asserted.

[ascull, 2015/07/16 19:38:46]

Done.

+    Comparison = T;
+  }
+
+  _cmp(Comparison, Ctx->getConstantInt32(Max - Min));
+
+  return Comparison;
+}
+
+template <class Machine>
+void TargetX86Base<Machine>::lowerCaseCluster(const CaseCluster &Case,
+                                              Operand *Comparison,
+                                              CfgNode *DefaultLabel) {
+  switch (Case.getKind()) {
+  case CaseCluster::JumpTable: {
+    typename Traits::Insts::Label *Label;

[jvoung (off chromium), 2015/07/15 18:32:02]

Is there a more informative name for this? It's used for out of range (and when
there's no Default).

[ascull, 2015/07/16 19:38:46]

Done.

+
+    Operand *RangeIndex = lowerCmpRange(Comparison,
+                                        Case.getLow(),
+                                        Case.getHigh());
+    if (DefaultLabel != nullptr) {
+      _br(Traits::Cond::Br_a, DefaultLabel);
+    } else {
+      // Skip over jump table logic if copmarison not in range and no default

[jvoung (off chromium), 2015/07/15 18:32:02]

copmarison -> comparison

[ascull, 2015/07/16 19:38:46]

Done.

+      Label = Traits::Insts::Label::create(Func, this);
+      _br(Traits::Cond::Br_a, Label);
+    }
+
+    InstJumpTable *JumpTable = Case.getJumpTable();
+    Context.insert(JumpTable);
+
+    // Make sure the index is a register of the same width as the base
+    Variable *Index;
+    if (RangeIndex->getType() != getPointerType()) {
+      Index = makeReg(getPointerType());
+      _movzx(Index, RangeIndex);
+    } else {
+      Index = legalizeToVar(RangeIndex);
+    }
+
+    Constant *Offset = Ctx->getConstantSym(0, JumpTable->getName(Func), true);

[jvoung (off chromium), 2015/07/15 18:32:02]

We usually use

constexpr RelocOffsetT Offset = 0;
constexpr bool SuppressMangling = true;
Ctx->getConstantSym(Offset, ...->getName(Func), SuppressMangling);

so that it's more clear what the parameters are.

[ascull, 2015/07/16 19:38:46]

Done.

+    // TODO(ascull): remove need for legalize by allowing null base in memop
+    auto *MemTarget = Traits::X86OperandMem::create(Func, getPointerType(),
+      legalizeToVar(Offset), nullptr, Index, 2);

[Jim Stichnoth, 2015/07/15 19:17:43]

Same as Jan's comment above, for nullptr and 2.

Also, the "2" refers to the log width of a code pointer, but might this be 3 for
x86-64?  (at least non-sandboxed)

[ascull, 2015/07/16 19:38:46]

Done.

+    Variable *Target = makeReg(getPointerType());

[Jim Stichnoth, 2015/07/15 19:17:42]

I think you can just set Target=nullptr and the _mov() routine will handle the
makeReg() boilerplate.

[ascull, 2015/07/16 19:38:46]

But does does _mov() ensure the width will be the width size as as a pointer
which is required for the memory operand?

[Jim Stichnoth, 2015/07/17 15:33:47]

Take a look at definition of _mov():
    ...
    if (Dest == nullptr)
      Dest = makeReg(Src0->getType(), RegNum);
    ...
Here Src0 is MemTarget, which was created above with type getPointerType(), so I
think the types are the same.

[ascull, 2015/07/17 18:21:28]

Done.

+    _mov(Target, MemTarget);
+    _jmp(Target);

[Jim Stichnoth, 2015/07/15 19:17:43]

Leave a TODO about sandboxing the indirect jump - i.e., mask the Target to a
bundle boundary.

BTW, you'll also need to mark each CfgNode that is a potential target of an
indirect jump, because in sandbox mode, all those nodes need to be emitted
bundle-aligned.

[ascull, 2015/07/16 19:38:46]

Done.

+
+    if (DefaultLabel == nullptr)
+      Context.insert(Label);
+    return;
+  }
+  case CaseCluster::Range: {
+    if (Case.getHigh() == Case.getLow()) {
+      // Single item
+      Constant *Value = Ctx->getConstantInt32(Case.getLow());
+      _cmp(Comparison, Value);
+      _br(Traits::Cond::Br_e, Case.getLabel());
+      if (DefaultLabel != nullptr)
+        _br(DefaultLabel);
+    } else {
+      // Range
+      lowerCmpRange(Comparison, Case.getLow(), Case.getHigh());
+      _br(Traits::Cond::Br_be, Case.getLabel());
+      if (DefaultLabel != nullptr)
+        _br(DefaultLabel);
+    }
+    return;
+  }
+  }
+}
+
+template <class Machine>
 void TargetX86Base<Machine>::lowerSwitch(const InstSwitch *Inst) {
-  // This implements the most naive possible lowering.
-  // cmp a,val[0]; jeq label[0]; cmp a,val[1]; jeq label[1]; ... jmp default
+  // Do it the old fashioned way unless asked for the advanced method
+  if (!Ctx->getFlags().getUseAdvancedSwitchLowering()) {
+    // This implements the most naive possible lowering.
+    // cmp a,val[0]; jeq label[0]; cmp a,val[1]; jeq label[1]; ... jmp default
+    Operand *Src0 = Inst->getComparison();
+    SizeT NumCases = Inst->getNumCases();
+    if (Src0->getType() == IceType_i64) {
+      Src0 = legalize(Src0); // get Base/Index into physical registers
+      Operand *Src0Lo = loOperand(Src0);
+      Operand *Src0Hi = hiOperand(Src0);
+      if (NumCases >= 2) {
+        Src0Lo = legalizeToVar(Src0Lo);
+        Src0Hi = legalizeToVar(Src0Hi);
+      } else {
+        Src0Lo = legalize(Src0Lo, Legal_Reg | Legal_Mem);
+        Src0Hi = legalize(Src0Hi, Legal_Reg | Legal_Mem);
+      }
+      for (SizeT I = 0; I < NumCases; ++I) {
+        Constant *ValueLo = Ctx->getConstantInt32(Inst->getValue(I));
+        Constant *ValueHi = Ctx->getConstantInt32(Inst->getValue(I) >> 32);
+        typename Traits::Insts::Label *Label =
+            Traits::Insts::Label::create(Func, this);
+        _cmp(Src0Lo, ValueLo);
+        _br(Traits::Cond::Br_ne, Label);
+        _cmp(Src0Hi, ValueHi);
+        _br(Traits::Cond::Br_e, Inst->getLabel(I));
+        Context.insert(Label);
+      }
+      _br(Inst->getLabelDefault());
+      return;
+    }
+    // OK, we'll be slightly less naive by forcing Src into a physical
+    // register if there are 2 or more uses.
+    if (NumCases >= 2)
+      Src0 = legalizeToVar(Src0);
+    else
+      Src0 = legalize(Src0, Legal_Reg | Legal_Mem);
+    for (SizeT I = 0; I < NumCases; ++I) {
+      Constant *Value = Ctx->getConstantInt32(Inst->getValue(I));
+      _cmp(Src0, Value);
+      _br(Traits::Cond::Br_e, Inst->getLabel(I));
+    }
+ 
+    _br(Inst->getLabelDefault());
+    return;
+  }
+
+  // Doing it the clever way

[jvoung (off chromium), 2015/07/15 18:32:02]

At some point here, could describe what the clever way is (binary search)

[ascull, 2015/07/16 19:38:45]

Done.

+  CaseClusterArray CaseClusters = CaseCluster::clusterizeSwitch(Func, Inst);
   Operand *Src0 = Inst->getComparison();
-  SizeT NumCases = Inst->getNumCases();
+  CfgNode *DefaultLabel = Inst->getLabelDefault();
+
+  assert(CaseClusters.size() != 0); // Should always be at least one
+
   if (Src0->getType() == IceType_i64) {
     Src0 = legalize(Src0); // get Base/Index into physical registers
     Operand *Src0Lo = loOperand(Src0);
     Operand *Src0Hi = hiOperand(Src0);
-    if (NumCases >= 2) {
-      Src0Lo = legalizeToVar(Src0Lo);
-      Src0Hi = legalizeToVar(Src0Hi);
+    if (CaseClusters.back().getHigh() > UINT32_MAX) {
+      // TODO(ascull): handle 64-bit case properly (currently naive version)
+      SizeT NumCases = Inst->getNumCases();

[jvoung (off chromium), 2015/07/15 18:32:02]

Maybe factor out to a function and share the code for now.

[ascull, 2015/07/16 19:38:45]

I'm leaving this for now while we consider the higher level lowering of
switches.

+      if (NumCases >= 2) {
+        Src0Lo = legalizeToVar(Src0Lo);
+        Src0Hi = legalizeToVar(Src0Hi);
+      } else {
+        Src0Lo = legalize(Src0Lo, Legal_Reg | Legal_Mem);
+        Src0Hi = legalize(Src0Hi, Legal_Reg | Legal_Mem);
+      }
+      for (SizeT I = 0; I < NumCases; ++I) {
+        Constant *ValueLo = Ctx->getConstantInt32(Inst->getValue(I));
+        Constant *ValueHi = Ctx->getConstantInt32(Inst->getValue(I) >> 32);
+        typename Traits::Insts::Label *Label =
+            Traits::Insts::Label::create(Func, this);
+        _cmp(Src0Lo, ValueLo);
+        _br(Traits::Cond::Br_ne, Label);
+        _cmp(Src0Hi, ValueHi);
+        _br(Traits::Cond::Br_e, Inst->getLabel(I));
+        Context.insert(Label);
+      }
+      _br(Inst->getLabelDefault());
+      return;
     } else {
-      Src0Lo = legalize(Src0Lo, Legal_Reg | Legal_Mem);
+      // All the values are 32-bit so just check the operand is too and then
+      // fall through to the 32-bit implementation. This is a common case.
       Src0Hi = legalize(Src0Hi, Legal_Reg | Legal_Mem);
+      Constant *Zero = Ctx->getConstantInt32(0);
+      _cmp(Src0Hi, Zero);
+      _br(Traits::Cond::Br_ne, DefaultLabel);
+      Src0 = Src0Lo;
     }
-    for (SizeT I = 0; I < NumCases; ++I) {
-      Constant *ValueLo = Ctx->getConstantInt32(Inst->getValue(I));
-      Constant *ValueHi = Ctx->getConstantInt32(Inst->getValue(I) >> 32);
-      typename Traits::Insts::Label *Label =
-          Traits::Insts::Label::create(Func, this);
-      _cmp(Src0Lo, ValueLo);
-      _br(Traits::Cond::Br_ne, Label);
-      _cmp(Src0Hi, ValueHi);
-      _br(Traits::Cond::Br_e, Inst->getLabel(I));
-      Context.insert(Label);
-    }
-    _br(Inst->getLabelDefault());
+  }
+
+  // 32-bit lowering
+
+  if (CaseClusters.size() == 1) {
+    // Jump straight to default if needed. Currently a common case as jump
+    // tables occur on their own.
+    lowerCaseCluster(CaseClusters.front(), Src0, DefaultLabel);
     return;
   }
-  // OK, we'll be slightly less naive by forcing Src into a physical
-  // register if there are 2 or more uses.
-  if (NumCases >= 2)
-    Src0 = legalizeToVar(Src0);
-  else
-    Src0 = legalize(Src0, Legal_Reg | Legal_Mem);
-  for (SizeT I = 0; I < NumCases; ++I) {
-    Constant *Value = Ctx->getConstantInt32(Inst->getValue(I));
-    _cmp(Src0, Value);
-    _br(Traits::Cond::Br_e, Inst->getLabel(I));
+
+  // Going to be using multiple times so get it in a register early
+  Variable *Comparison = legalizeToVar(Src0);
+
+  // A span is over the clusters
+  struct SearchSpan {
+    SearchSpan(SizeT _Begin, SizeT _Size,

[jvoung (off chromium), 2015/07/15 18:32:02]

There's still some debate on what to do with shadowing:
https://codereview.chromium.org/1221643012/, and how to name the variables to
get around that.

Otherwise, for now the style is still to just shadow. So change _Begin -> Begin,
etc.

[Jim Stichnoth, 2015/07/15 19:17:43]

Also, I believe C/C++ forbid the underscore-uppercase prefix...

[ascull, 2015/07/16 19:38:45]

Done.

+               typename Traits::Insts::Label *_Label)
+      : Begin(_Begin), Size(_Size), Label(_Label) {}
+
+    SizeT Begin;
+    SizeT Size;
+    typename Traits::Insts::Label *Label;
+  };
+  std::stack<SearchSpan, std::deque<SearchSpan,CfgLocalAllocator<SearchSpan>>>
+    SearchSpanStack;
+  SearchSpanStack.emplace(0, CaseClusters.size(), nullptr);
+
+  while (!SearchSpanStack.empty()) {
+    SearchSpan span = SearchSpanStack.top();

[jvoung (off chromium), 2015/07/15 18:32:02]

"span" -> "Span"

[ascull, 2015/07/16 19:38:46]

Done.

+    SearchSpanStack.pop();
+
+    if (span.Label != nullptr)
+      Context.insert(span.Label);
+
+    switch (span.Size) {
+    case 0:
+      llvm_unreachable("Invalid SearchSpan size");

[Jim Stichnoth, 2015/07/15 19:17:43]

In general, use llvm::report_fatal_error() rather than llvm_unreachable().

[ascull, 2015/07/16 19:38:46]

Done.

+      break;
+
+    // Deliberate fall through for base cases
+    case 2:
+      lowerCaseCluster(CaseClusters[span.Begin+1], Comparison);
+    case 1:
+      // Can fall through to default branch on last span
+      lowerCaseCluster(CaseClusters[span.Begin  ], Comparison,

[jvoung (off chromium), 2015/07/15 18:32:02]

nit: Hmm haven't seen spacing attempt to line up the [ ], so I would just keep
it tight "[span.Begin], Comparison".

[ascull, 2015/07/16 19:38:46]

Done.

+          SearchSpanStack.empty() ? nullptr : DefaultLabel);
+      break;
+
+    default:
+      // Pick the middle item and branch b or ae
+      SizeT PivotIndex = span.Begin + (span.Size / 2);
+      const CaseCluster &Pivot = CaseClusters[PivotIndex];
+      Constant *Value = Ctx->getConstantInt32(Pivot.getLow());
+      // TODO(ascull): what if this jump is too big?
+      typename Traits::Insts::Label *Label = Traits::Insts::Label::create(Func,
+                                                                          this);
+      _cmp(Comparison, Value);
+      _br(Traits::Cond::Br_b, Label);
+      // Lower the left and (pivot+right) sides, falling through to the right
+      SearchSpanStack.emplace(span.Begin, span.Size / 2, Label);
+      SearchSpanStack.emplace(PivotIndex, span.Size - (span.Size / 2), nullptr);
+      break;
+    }
   }
 
-  _br(Inst->getLabelDefault());
+  _br(DefaultLabel); 
 }
 
 template <class Machine>