Iasm and obj lowering for advanced switch lowering.

src/IceTargetLoweringX86BaseImpl.h

 //===- subzero/src/IceTargetLoweringX86BaseImpl.h - x86 lowering -*- C++ -*-==//
 //
 //                        The Subzero Code Generator
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 ///
 /// \file
@@ skipping 4497 matching lines @@
   }
 
   _cmp(Comparison, Ctx->getConstantInt32(Max - Min));
 
   return Comparison;
 }
 
 template <class Machine>
 void TargetX86Base<Machine>::lowerCaseCluster(const CaseCluster &Case,
                                               Operand *Comparison, bool DoneCmp,
-                                              CfgNode *DefaultLabel) {
+                                              CfgNode *DefaultTarget) {
   switch (Case.getKind()) {
   case CaseCluster::JumpTable: {
     typename Traits::Insts::Label *SkipJumpTable;
 
     Operand *RangeIndex =
         lowerCmpRange(Comparison, Case.getLow(), Case.getHigh());
-    if (DefaultLabel != nullptr) {
-      _br(Traits::Cond::Br_a, DefaultLabel);
-    } else {
+    if (DefaultTarget == nullptr) {
       // Skip over jump table logic if comparison not in range and no default
       SkipJumpTable = Traits::Insts::Label::create(Func, this);
       _br(Traits::Cond::Br_a, SkipJumpTable);
+    } else {
+      _br(Traits::Cond::Br_a, DefaultTarget);
     }
 
     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 = legalizeToReg(RangeIndex);
     }
 
     constexpr RelocOffsetT RelocOffset = 0;
     constexpr bool SuppressMangling = true;
     Constant *Base = Ctx->getConstantSym(RelocOffset, JumpTable->getName(Func),
                                          SuppressMangling);
     Constant *Offset = nullptr;
     uint16_t Shift = typeWidthInBytesLog2(getPointerType());
     // TODO(ascull): remove need for legalize by allowing null base in memop
-    auto *MemTarget = Traits::X86OperandMem::create(
+    auto *TargetInMemory = Traits::X86OperandMem::create(
         Func, getPointerType(), legalizeToReg(Base), Offset, Index, Shift);
     Variable *Target = nullptr;
-    _mov(Target, MemTarget);
+    _mov(Target, TargetInMemory);
+
+    // Sandbox the indirect jump
+    const bool NeedSandboxing = Ctx->getFlags().getUseSandboxing();
+    if (NeedSandboxing) {
+      _bundle_lock();
+      const SizeT BundleSize =
+          1 << Func->getAssembler<>()->getBundleAlignLog2Bytes();
+      _and(Target, Ctx->getConstantInt32(~(BundleSize - 1)));
+    }
     _jmp(Target);
-    // TODO(ascull): sandboxing for indirect jump
+    if (NeedSandboxing)
+      _bundle_unlock();
 
-    if (DefaultLabel == nullptr)
+    if (DefaultTarget == nullptr)
       Context.insert(SkipJumpTable);
     return;
   }
   case CaseCluster::Range: {
-    if (Case.getHigh() == Case.getLow()) {
+    if (Case.isUnitRange()) {
       // Single item
-      Constant *Value = Ctx->getConstantInt32(Case.getLow());
-      if (!DoneCmp)
+      if (!DoneCmp) {
+        Constant *Value = Ctx->getConstantInt32(Case.getLow());
         _cmp(Comparison, Value);
-      _br(Traits::Cond::Br_e, Case.getLabel());
-      if (DefaultLabel != nullptr)
-        _br(DefaultLabel);
+      }
+      _br(Traits::Cond::Br_e, Case.getTarget());
+    } else if (DoneCmp && Case.isPairRange()) {
+      // Range of two items with first item aleady compared against
+      _br(Traits::Cond::Br_e, Case.getTarget());
+      Constant *Value = Ctx->getConstantInt32(Case.getHigh());
+      _cmp(Comparison, Value);
+      _br(Traits::Cond::Br_e, Case.getTarget());
     } else {
       // Range
       lowerCmpRange(Comparison, Case.getLow(), Case.getHigh());
-      _br(Traits::Cond::Br_be, Case.getLabel());
-      if (DefaultLabel != nullptr)
-        _br(DefaultLabel);
+      _br(Traits::Cond::Br_be, Case.getTarget());
     }
+    if (DefaultTarget != nullptr)
+      _br(DefaultTarget);
     return;
   }
   }
 }
 
 template <class Machine>
 void TargetX86Base<Machine>::lowerSwitch(const InstSwitch *Inst) {
   // Do it the old fashioned way unless asked for the advanced method
   if (!Ctx->getFlags().getUseAdvancedSwitchLowering()) {
     // This implements the most naive possible lowering.
@@ skipping 37 matching lines @@
       _br(Traits::Cond::Br_e, Inst->getLabel(I));
     }
 
     _br(Inst->getLabelDefault());
     return;
   }
 
   // Group cases together and navigate through them with a binary search
   CaseClusterArray CaseClusters = CaseCluster::clusterizeSwitch(Func, Inst);
   Operand *Src0 = Inst->getComparison();
-  CfgNode *DefaultLabel = Inst->getLabelDefault();
+  CfgNode *DefaultTarget = 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 (CaseClusters.back().getHigh() > UINT32_MAX) {
       // TODO(ascull): handle 64-bit case properly (currently naive version)
       // This might be handled by a higher level lowering of switches.
@@ skipping 17 matching lines @@
         Context.insert(Label);
       }
       _br(Inst->getLabelDefault());
       return;
     } else {
       // 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);
+      _br(Traits::Cond::Br_ne, DefaultTarget);
       Src0 = Src0Lo;
     }
   }
 
   // 32-bit lowering
 
   if (CaseClusters.size() == 1) {
     // Jump straight to default if needed. Currently a common case as jump
     // tables occur on their own.
     constexpr bool DoneCmp = false;
-    lowerCaseCluster(CaseClusters.front(), Src0, DoneCmp, DefaultLabel);
+    lowerCaseCluster(CaseClusters.front(), Src0, DoneCmp, DefaultTarget);
     return;
   }
 
   // Going to be using multiple times so get it in a register early
   Variable *Comparison = legalizeToReg(Src0);
 
   // A span is over the clusters
   struct SearchSpan {
     SearchSpan(SizeT Begin, SizeT Size, typename Traits::Insts::Label *Label)
         : Begin(Begin), Size(Size), Label(Label) {}
@@ skipping 14 matching lines @@
     if (Span.Label != nullptr)
       Context.insert(Span.Label);
 
     switch (Span.Size) {
     case 0:
       llvm::report_fatal_error("Invalid SearchSpan size");
       break;
 
     case 1:
       lowerCaseCluster(CaseClusters[Span.Begin], Comparison, DoneCmp,
-                       SearchSpanStack.empty() ? nullptr : DefaultLabel);
+                       SearchSpanStack.empty() ? nullptr : DefaultTarget);
       DoneCmp = false;
       break;
 
-    case 2:
-      lowerCaseCluster(CaseClusters[Span.Begin], Comparison, DoneCmp);
+    case 2: {
+      const CaseCluster *CaseA = &CaseClusters[Span.Begin];
+      const CaseCluster *CaseB = &CaseClusters[Span.Begin + 1];
+
+      // Placing a range last may allow register clobbering during the range
+      // test. That means there is no need to clone the register. If it is a
+      // unit range the comparison may have already been done in the binary
+      // search (DoneCmp) and so it should be placed first. If this is a range
+      // of two items and the comparison with the low value has already been
+      // done, comparing with the other element is cheaper than a range test.
+      // If the low end of the range is zero then there is no subtraction and
+      // nothing to be gained.
+      if (!CaseA->isUnitRange() &&
+          !(CaseA->getLow() == 0 || (DoneCmp && CaseA->isPairRange()))) {
+        std::swap(CaseA, CaseB);
+        DoneCmp = false;
+      }
+
+      lowerCaseCluster(*CaseA, Comparison, DoneCmp);
       DoneCmp = false;
-      lowerCaseCluster(CaseClusters[Span.Begin + 1], Comparison, DoneCmp,
-                       SearchSpanStack.empty() ? nullptr : DefaultLabel);
-      break;
+      lowerCaseCluster(*CaseB, Comparison, DoneCmp,
+                       SearchSpanStack.empty() ? nullptr : DefaultTarget);
+    } 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);
+      // TODO(ascull): does it alway have to be far?
+      _br(Traits::Cond::Br_b, Label, Traits::Insts::Br::Far);
       // 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);
       DoneCmp = true;
       break;
     }
   }
 
-  _br(DefaultLabel);
+  _br(DefaultTarget);
 }
 
 template <class Machine>
 void TargetX86Base<Machine>::scalarizeArithmetic(InstArithmetic::OpKind Kind,
                                                  Variable *Dest, Operand *Src0,
                                                  Operand *Src1) {
   assert(isVectorType(Dest->getType()));
   Type Ty = Dest->getType();
   Type ElementTy = typeElementType(Ty);
   SizeT NumElements = typeNumElements(Ty);
@@ skipping 856 matching lines @@
   }
   // the offset is not eligible for blinding or pooling, return the original
   // mem operand
   return MemOperand;
 }
 
 } // end of namespace X86Internal
 } // end of namespace Ice
 
 #endif // SUBZERO_SRC_ICETARGETLOWERINGX86BASEIMPL_H