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 396 matching lines @@
   Func->reorderNodes();
 
   // Branch optimization.  This needs to be done just before code emission.  In
   // particular, no transformations that insert or reorder CfgNodes should be
   // done after branch optimization.  We go ahead and do it before nop insertion
   // to reduce the amount of work needed for searching for opportunities.
   Func->doBranchOpt();
   Func->dump("After branch optimization");
 
   // Nop insertion
-  if (Ctx->getFlags().shouldDoNopInsertion()) {
+  if (Ctx->getFlags().shouldDoNopInsertion())
     Func->doNopInsertion();
-  }
+
+  // Mark nodes that require sandbox alignment
+  if (Ctx->getFlags().getUseSandboxing())
+    Func->markNodesForSandboxing();
 }
 
 template <class Machine> void TargetX86Base<Machine>::translateOm1() {
   TimerMarker T(TimerStack::TT_Om1, Func);
 
   Func->placePhiLoads();
   if (Func->hasError())
     return;
   Func->placePhiStores();
   if (Func->hasError())
@@ skipping 16 matching lines @@
 
   Func->genFrame();
   if (Func->hasError())
     return;
   Func->dump("After stack frame mapping");
 
   // Nop insertion
   if (Ctx->getFlags().shouldDoNopInsertion()) {
     Func->doNopInsertion();
   }
+
+  // Mark nodes that require sandbox alignment
+  if (Ctx->getFlags().getUseSandboxing())
+    Func->markNodesForSandboxing();
 }
 
 inline bool canRMW(const InstArithmetic *Arith) {
   Type Ty = Arith->getDest()->getType();
   // X86 vector instructions write to a register and have no RMW option.
   if (isVectorType(Ty))
     return false;
   bool isI64 = Ty == IceType_i64;
 
   switch (Arith->getOp()) {
@@ skipping 642 matching lines @@
 
   if (!Ctx->getFlags().getUseSandboxing())
     return;
   // Change the original ret instruction into a sandboxed return sequence.
   // t:ecx = pop
   // bundle_lock
   // and t, ~31
   // jmp *t
   // bundle_unlock
   // FakeUse <original_ret_operand>
-  const SizeT BundleSize = 1
-                           << Func->getAssembler<>()->getBundleAlignLog2Bytes();
   Variable *T_ecx = makeReg(IceType_i32, Traits::RegisterSet::Reg_ecx);
   _pop(T_ecx);
-  _bundle_lock();
-  _and(T_ecx, Ctx->getConstantInt32(~(BundleSize - 1)));
-  _jmp(T_ecx);
-  _bundle_unlock();
+  lowerIndirectJump(T_ecx);
   if (RI->getSrcSize()) {
     Variable *RetValue = llvm::cast<Variable>(RI->getSrc(0));
     Context.insert(InstFakeUse::create(Func, RetValue));
   }
   RI->setDeleted();
 }
 
 template <class Machine> void TargetX86Base<Machine>::split64(Variable *Var) {
   switch (Var->getType()) {
   default:
@@ skipping 2827 matching lines @@
   } else {
     _bsr(T_Dest2, SecondVar);
     _xor(T_Dest2, ThirtyOne);
   }
   _test(SecondVar, SecondVar);
   _cmov(T_Dest2, T_Dest, Traits::Cond::Br_e);
   _mov(DestLo, T_Dest2);
   _mov(DestHi, Ctx->getConstantZero(IceType_i32));
 }
 
+template <class Machine>
+void TargetX86Base<Machine>::lowerIndirectJump(Variable *Target) {
+  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);
+  if (NeedSandboxing)
+    _bundle_unlock();
+}
+
 inline bool isAdd(const Inst *Inst) {
   if (const InstArithmetic *Arith =
           llvm::dyn_cast_or_null<const InstArithmetic>(Inst)) {
     return (Arith->getOp() == InstArithmetic::Add);
   }
   return false;
 }
 
 inline void dumpAddressOpt(const Cfg *Func, const Variable *Base,
                            const Variable *Index, uint16_t Shift,
@@ skipping 525 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) {

[Jim Stichnoth, 2015/07/30 15:20:24]

How about something like
  if (DefaultTarget) {
    ...
  } else {
    ...
  }

I don't know if written style guides cover this, but I'm fine with "if (A)" as
shorthand for "if (A != nullptr)", though not so happy with "if (!A)" as
shorthand for "if (A == nullptr)".

[ascull, 2015/07/30 17:30:00]

I have this way to match the `(DefaultTarget == nullptr)` below which places the
label.

[Jim Stichnoth, 2015/07/30 17:40:44]

I see.

       // 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);
+    IceString MangledName = Ctx->mangleName(Func->getFunctionName());
+    Constant *Base = Ctx->getConstantSym(
+        RelocOffset, InstJumpTable::makeName(MangledName, JumpTable->getId()),
+        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);
-    _jmp(Target);
-    // TODO(ascull): sandboxing for indirect jump
+    _mov(Target, TargetInMemory);
+    lowerIndirectJump(Target);
 
-    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.
-    // 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 = legalizeToReg(Src0Lo);
-        Src0Hi = legalizeToReg(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 = legalizeToReg(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;
-  }
-
   // 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