ARM lowering integer divide and remainder, with div by 0 checks.

src/IceTargetLoweringARM32.cpp

 //===- subzero/src/IceTargetLoweringARM32.cpp - ARM32 lowering ------------===//
 //
 //                        The Subzero Code Generator
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 // This file implements the TargetLoweringARM32 class, which consists almost
@@ skipping 123 matching lines @@
 uint32_t applyStackAlignmentTy(uint32_t Value, Type Ty) {
   // Use natural alignment, except that normally (non-NaCl) ARM only
   // aligns vectors to 8 bytes.
   // TODO(jvoung): Check this ...
   size_t typeAlignInBytes = typeWidthInBytes(Ty);
   if (isVectorType(Ty))
     typeAlignInBytes = 8;
   return Utils::applyAlignment(Value, typeAlignInBytes);
 }
 
+// Conservatively check if at compile time, we know that the operand is
+// definitely non-zero.
+bool operandMustNotBeZero(const Operand *Op) {

[Jim Stichnoth, 2015/06/30 14:14:09]

May want to tweak the function name to express the test against *integer* zero
as opposed to 0.0 .

Maybe something like isGuaranteedNonzeroInt() ?

[jvoung (off chromium), 2015/06/30 16:58:08]

Done.

+  if (auto *Const = llvm::dyn_cast<ConstantInteger32>(Op)) {
+    return Const->getValue() != 0;
+  }
+  return false;
+}
+
 } // end of anonymous namespace
 
-TargetARM32::TargetARM32(Cfg *Func) : TargetLowering(Func) {
+TargetARM32Features::TargetARM32Features(const ClFlags &Flags) {
   static_assert(
       (ARM32InstructionSet::End - ARM32InstructionSet::Begin) ==
           (TargetInstructionSet::ARM32InstructionSet_End -
            TargetInstructionSet::ARM32InstructionSet_Begin),
       "ARM32InstructionSet range different from TargetInstructionSet");
-  if (Func->getContext()->getFlags().getTargetInstructionSet() !=
+  if (Flags.getTargetInstructionSet() !=
       TargetInstructionSet::BaseInstructionSet) {
     InstructionSet = static_cast<ARM32InstructionSet>(
-        (Func->getContext()->getFlags().getTargetInstructionSet() -
+        (Flags.getTargetInstructionSet() -
          TargetInstructionSet::ARM32InstructionSet_Begin) +
         ARM32InstructionSet::Begin);
   }
+}
+
+TargetARM32::TargetARM32(Cfg *Func)
+    : TargetLowering(Func), CPUFeatures(Func->getContext()->getFlags()) {
   // TODO: Don't initialize IntegerRegisters and friends every time.
   // Instead, initialize in some sort of static initializer for the
   // class.
   llvm::SmallBitVector IntegerRegisters(RegARM32::Reg_NUM);
   llvm::SmallBitVector FloatRegisters(RegARM32::Reg_NUM);
   llvm::SmallBitVector VectorRegisters(RegARM32::Reg_NUM);
   llvm::SmallBitVector InvalidRegisters(RegARM32::Reg_NUM);
   ScratchRegs.resize(RegARM32::Reg_NUM);
 #define X(val, encode, name, scratch, preserved, stackptr, frameptr, isInt,    \
           isFP)                                                                \
@@ skipping 833 matching lines @@
     Variable *T = makeReg(IceType_i32);
     _mov(T, TotalSize);
     Operand *AddAmount = legalize(Ctx->getConstantInt32(Alignment - 1));
     _add(T, T, AddAmount);
     alignRegisterPow2(T, Alignment);
     _sub(SP, SP, T);
   }
   _mov(Dest, SP);
 }
 
+InstARM32Label *TargetARM32::beginDiv0Check(Type Ty, Operand *SrcLo,
+                                            Operand *SrcHi) {
+  bool ElideCheck = operandMustNotBeZero(SrcLo);

[Jim Stichnoth, 2015/06/30 14:14:09]

What do you think about starting the function like this?

  if (operandMustNotBeZero(SrcLo) || operandMustNotBeZero(SrcHi))
    return nullptr;

and then operandMustNotBeZero() returns false on a nullptr arg?  (perhaps by
changing dyn_cast<> to dyn_cast_or_null<>)

[jvoung (off chromium), 2015/06/30 16:58:08]

Done.

+  if (Ty == IceType_i64) {
+    ElideCheck = ElideCheck || operandMustNotBeZero(SrcHi);
+  }
+  if (ElideCheck)
+    return nullptr;
+  InstARM32Label *Label = InstARM32Label::create(Func, this);
+  Variable *SrcLoReg = legalizeToVar(SrcLo);
+  switch (Ty) {
+  default:
+    llvm_unreachable("Unexpected type");
+  case IceType_i8: {
+    Operand *Mask =
+        legalize(Ctx->getConstantInt32(0xFF), Legal_Reg | Legal_Flex);
+    _tst(SrcLoReg, Mask);
+    break;
+  }
+  case IceType_i16: {
+    Operand *Mask =
+        legalize(Ctx->getConstantInt32(0xFFFF), Legal_Reg | Legal_Flex);
+    _tst(SrcLoReg, Mask);
+    break;
+  }
+  case IceType_i32: {
+    _tst(SrcLoReg, SrcLoReg);
+    break;
+  }
+  case IceType_i64: {
+    Variable *ScratchReg = makeReg(IceType_i32);
+    _orrs(ScratchReg, SrcLoReg, SrcHi);
+    // ScratchReg isn't going to be used, but we need the
+    // side-effect of setting flags from this operation.
+    Context.insert(InstFakeUse::create(Func, ScratchReg));
+  }
+  }
+  _br(Label, CondARM32::EQ);
+  return Label;
+}
+
+void TargetARM32::endDiv0Check(InstARM32Label *CheckLabel) {
+  if (CheckLabel) {
+    Context.insert(CheckLabel);

[jvoung (off chromium), 2015/06/30 16:58:08]

Oops, also realized that I need to do the trap, and jump over that instead.
Otherwise, the div code will fall through and also hit the trap (or would need
another jump to jump over it).

Changed this around to just have "div0Check" instead of "begin/end...".

Really need those execution crosstests...

[Jim Stichnoth, 2015/06/30 17:06:51]

Heh... I think those cross tests explicitly avoid dividing by zero.

+    _trap();
+  }
+}
+
+void TargetARM32::lowerIDivRem(Variable *Dest, Variable *T, Variable *Src0R,
+                               Operand *Src1, ExtInstr ExtFunc,
+                               DivInstr DivFunc, const char *DivHelperName,
+                               bool IsRemainder) {
+  InstARM32Label *Label = beginDiv0Check(Dest->getType(), Src1, nullptr);
+  Variable *Src1R = legalizeToVar(Src1);
+  Variable *T0R = Src0R;
+  Variable *T1R = Src1R;
+  if (Dest->getType() != IceType_i32) {
+    T0R = makeReg(IceType_i32);
+    (this->*ExtFunc)(T0R, Src0R, CondARM32::AL);
+    T1R = makeReg(IceType_i32);
+    (this->*ExtFunc)(T1R, Src1R, CondARM32::AL);
+  }
+  if (hasCPUFeature(TargetARM32Features::HWDivArm)) {
+    (this->*DivFunc)(T, T0R, T1R, CondARM32::AL);
+    if (IsRemainder) {
+      Variable *T2 = makeReg(IceType_i32);
+      _mls(T2, T, T1R, T0R);
+      T = T2;
+    }
+    _mov(Dest, T);
+  } else {
+    const SizeT MaxSrcs = 2;
+    InstCall *Call = makeHelperCall(DivHelperName, Dest, MaxSrcs);
+    Call->addArg(T0R);
+    Call->addArg(T1R);
+    lowerCall(Call);
+  }
+  endDiv0Check(Label);
+  return;
+}
+
 void TargetARM32::lowerArithmetic(const InstArithmetic *Inst) {
   Variable *Dest = Inst->getDest();
   // TODO(jvoung): Should be able to flip Src0 and Src1 if it is easier
   // to legalize Src0 to flex or Src1 to flex and there is a reversible
   // instruction. E.g., reverse subtract with immediate, register vs
   // register, immediate.
   // Or it may be the case that the operands aren't swapped, but the
   // bits can be flipped and a different operation applied.
   // E.g., use BIC (bit clear) instead of AND for some masks.
   Operand *Src0 = Inst->getSrc(0);
@@ skipping 153 matching lines @@
            Pred);
       _mov(DestLo, T_Lo);
       Variable *T_Hi = makeReg(IceType_i32);
       _mov(T_Hi, OperandARM32FlexReg::create(Func, IceType_i32, Src0RHi,
                                              RShiftKind, Src1RLo));
       _mov(DestHi, T_Hi);
     } break;
     case InstArithmetic::Udiv:
     case InstArithmetic::Sdiv:
     case InstArithmetic::Urem:
-    case InstArithmetic::Srem:
-      UnimplementedError(Func->getContext()->getFlags());
-      break;
+    case InstArithmetic::Srem: {
+      // Check for divide by 0 (ARM normally doesn't trap, but we want it
+      // to trap for NaCl).
+      InstARM32Label *Label = nullptr;
+      // Src1Lo and Src1Hi may have already been legalized to a register,
+      // which will hide a constant source operand. Instead, check the
+      // not-yet-legalized Src1 to optimize-out a divide by 0 check.
+      if (auto *C64 = llvm::dyn_cast<ConstantInteger64>(Src1)) {
+        if (C64->getValue() == 0) {
+          Label = beginDiv0Check(IceType_i64, Src1Lo, Src1Hi);
+        }
+      } else {
+        Label = beginDiv0Check(IceType_i64, Src1Lo, Src1Hi);
+      }
+      // Technically, ARM has their own aeabi routines, but we can use the
+      // non-aeabi routine as well.  LLVM uses __aeabi_ldivmod for div,
+      // but uses the more standard __moddi3 for rem.
+      const char *HelperName = "";
+      switch (Inst->getOp()) {
+      case InstArithmetic::Udiv:
+        HelperName = H_udiv_i64;
+        break;
+      case InstArithmetic::Sdiv:
+        HelperName = H_sdiv_i64;
+        break;
+      case InstArithmetic::Urem:
+        HelperName = H_urem_i64;
+        break;
+      case InstArithmetic::Srem:
+        HelperName = H_srem_i64;
+        break;
+      default:
+        llvm_unreachable("Should have only matched div ops.");
+        break;
+      }
+      const SizeT MaxSrcs = 2;

[Jim Stichnoth, 2015/06/30 14:14:09]

constexpr?

[jvoung (off chromium), 2015/06/30 16:58:08]

Done.

+      InstCall *Call = makeHelperCall(HelperName, Dest, MaxSrcs);
+      Call->addArg(Inst->getSrc(0));
+      Call->addArg(Inst->getSrc(1));
+      lowerCall(Call);
+      endDiv0Check(Label);
+      return;
+    }
     case InstArithmetic::Fadd:
     case InstArithmetic::Fsub:
     case InstArithmetic::Fmul:
     case InstArithmetic::Fdiv:
     case InstArithmetic::Frem:
       llvm_unreachable("FP instruction with i64 type");
       break;
     }
   } else if (isVectorType(Dest->getType())) {
     UnimplementedError(Func->getContext()->getFlags());
   } else { // Dest->getType() is non-i64 scalar
     Variable *Src0R = legalizeToVar(Inst->getSrc(0));
-    Src1 = legalize(Inst->getSrc(1), Legal_Reg | Legal_Flex);
+    Operand *Src1RF = legalize(Inst->getSrc(1), Legal_Reg | Legal_Flex);
     Variable *T = makeReg(Dest->getType());
     switch (Inst->getOp()) {
     case InstArithmetic::_num:
       llvm_unreachable("Unknown arithmetic operator");
       break;
     case InstArithmetic::Add: {
-      _add(T, Src0R, Src1);
+      _add(T, Src0R, Src1RF);
       _mov(Dest, T);
     } break;
     case InstArithmetic::And: {
-      _and(T, Src0R, Src1);
+      _and(T, Src0R, Src1RF);
       _mov(Dest, T);
     } break;
     case InstArithmetic::Or: {
-      _orr(T, Src0R, Src1);
+      _orr(T, Src0R, Src1RF);
       _mov(Dest, T);
     } break;
     case InstArithmetic::Xor: {
-      _eor(T, Src0R, Src1);
+      _eor(T, Src0R, Src1RF);
       _mov(Dest, T);
     } break;
     case InstArithmetic::Sub: {
-      _sub(T, Src0R, Src1);
+      _sub(T, Src0R, Src1RF);
       _mov(Dest, T);
     } break;
     case InstArithmetic::Mul: {
-      Variable *Src1R = legalizeToVar(Src1);
+      Variable *Src1R = legalizeToVar(Src1RF);
       _mul(T, Src0R, Src1R);
       _mov(Dest, T);
     } break;
     case InstArithmetic::Shl:
-      _lsl(T, Src0R, Src1);
+      _lsl(T, Src0R, Src1RF);
       _mov(Dest, T);
       break;
     case InstArithmetic::Lshr:
-      _lsr(T, Src0R, Src1);
+      _lsr(T, Src0R, Src1RF);
       _mov(Dest, T);
       break;
     case InstArithmetic::Ashr:
-      _asr(T, Src0R, Src1);
+      _asr(T, Src0R, Src1RF);
       _mov(Dest, T);
       break;
-    case InstArithmetic::Udiv:
-      UnimplementedError(Func->getContext()->getFlags());
-      break;
-    case InstArithmetic::Sdiv:
-      UnimplementedError(Func->getContext()->getFlags());
-      break;
-    case InstArithmetic::Urem:
-      UnimplementedError(Func->getContext()->getFlags());
-      break;
-    case InstArithmetic::Srem:
-      UnimplementedError(Func->getContext()->getFlags());
-      break;
+    case InstArithmetic::Udiv: {
+      constexpr bool IsRemainder = false;
+      lowerIDivRem(Dest, T, Src0R, Src1, &TargetARM32::_uxt,
+                   &TargetARM32::_udiv, H_udiv_i32, IsRemainder);
+      return;
+    }
+    case InstArithmetic::Sdiv: {
+      constexpr bool IsRemainder = false;
+      lowerIDivRem(Dest, T, Src0R, Src1, &TargetARM32::_sxt,
+                   &TargetARM32::_sdiv, H_sdiv_i32, IsRemainder);
+      return;
+    }
+    case InstArithmetic::Urem: {
+      constexpr bool IsRemainder = true;
+      lowerIDivRem(Dest, T, Src0R, Src1, &TargetARM32::_uxt,
+                   &TargetARM32::_udiv, H_urem_i32, IsRemainder);
+      return;
+    }
+    case InstArithmetic::Srem: {
+      constexpr bool IsRemainder = true;
+      lowerIDivRem(Dest, T, Src0R, Src1, &TargetARM32::_sxt,
+                   &TargetARM32::_sdiv, H_srem_i32, IsRemainder);
+      return;
+    }
     case InstArithmetic::Fadd:
       UnimplementedError(Func->getContext()->getFlags());
       break;
     case InstArithmetic::Fsub:
       UnimplementedError(Func->getContext()->getFlags());
       break;
     case InstArithmetic::Fmul:
       UnimplementedError(Func->getContext()->getFlags());
       break;
     case InstArithmetic::Fdiv:
@@ skipping 50 matching lines @@
   if (Inst->isUnconditional()) {
     _br(Inst->getTargetUnconditional());
     return;
   }
   Operand *Cond = Inst->getCondition();
   // TODO(jvoung): Handle folding opportunities.
 
   Variable *Src0R = legalizeToVar(Cond);
   Constant *Zero = Ctx->getConstantZero(IceType_i32);
   _cmp(Src0R, Zero);
-  _br(CondARM32::NE, Inst->getTargetTrue(), Inst->getTargetFalse());
+  _br(Inst->getTargetTrue(), Inst->getTargetFalse(), CondARM32::NE);
 }
 
 void TargetARM32::lowerCall(const InstCall *Instr) {
   MaybeLeafFunc = false;
   NeedsStackAlignment = true;
 
   // Assign arguments to registers and stack. Also reserve stack.
   TargetARM32::CallingConv CC;
   // Pair of Arg Operand -> GPR number assignments.
   llvm::SmallVector<std::pair<Operand *, int32_t>,
@@ skipping 714 matching lines @@
       Operand *ValueHi = Ctx->getConstantInt32(Inst->getValue(I) >> 32);
       ValueLo = legalize(ValueLo, Legal_Reg | Legal_Flex);
       ValueHi = legalize(ValueHi, Legal_Reg | Legal_Flex);
       _cmp(Src0Lo, ValueLo);
       _cmp(Src0Hi, ValueHi, CondARM32::EQ);
       _br(Inst->getLabel(I), CondARM32::EQ);
     }
     _br(Inst->getLabelDefault());
     return;
   }
- 
+
   // 32 bit integer
   Variable *Src0Var = legalizeToVar(Src0);
   for (SizeT I = 0; I < NumCases; ++I) {
     Operand *Value = Ctx->getConstantInt32(Inst->getValue(I));
     Value = legalize(Value, Legal_Reg | Legal_Flex);
     _cmp(Src0Var, Value);
     _br(Inst->getLabel(I), CondARM32::EQ);
   }
   _br(Inst->getLabelDefault());
 }
 
 void TargetARM32::lowerUnreachable(const InstUnreachable * /*Inst*/) {
-  UnimplementedError(Func->getContext()->getFlags());
+  _trap();
 }
 
 // Turn an i64 Phi instruction into a pair of i32 Phi instructions, to
 // preserve integrity of liveness analysis.  Undef values are also
 // turned into zeroes, since loOperand() and hiOperand() don't expect
 // Undef input.
 void TargetARM32::prelowerPhis() {
   UnimplementedError(Func->getContext()->getFlags());
 }
 
@@ skipping 283 matching lines @@
   }
 }
 
 void TargetDataARM32::lowerConstants() {
   if (Ctx->getFlags().getDisableTranslation())
     return;
   UnimplementedError(Ctx->getFlags());
 }
 
 TargetHeaderARM32::TargetHeaderARM32(GlobalContext *Ctx)
-    : TargetHeaderLowering(Ctx) {}
+    : TargetHeaderLowering(Ctx), CPUFeatures(Ctx->getFlags()) {}
 
 void TargetHeaderARM32::lower() {
   OstreamLocker L(Ctx);
   Ostream &Str = Ctx->getStrEmit();
   Str << ".syntax unified\n";
   // Emit build attributes in format: .eabi_attribute TAG, VALUE.
   // See Sec. 2 of "Addenda to, and Errata in the ABI for the ARM architecture"
   // http://infocenter.arm.com/help/topic/com.arm.doc.ihi0045d/IHI0045D_ABI_addenda.pdf
   //
   // Tag_conformance should be be emitted first in a file-scope
   // sub-subsection of the first public subsection of the attributes.
   Str << ".eabi_attribute 67, \"2.09\"      @ Tag_conformance\n";
   // Chromebooks are at least A15, but do A9 for higher compat.
-  Str << ".cpu    cortex-a9\n"
-      << ".eabi_attribute 6, 10   @ Tag_CPU_arch: ARMv7\n"
+  // For some reason, the LLVM ARM asm parser has the .cpu directive override
+  // the mattr specified on the commandline. So to test hwdiv, we need to set
+  // the .cpu directive higher (can't just rely on --mattr=...).
+  if (CPUFeatures.hasFeature(TargetARM32Features::HWDivArm)) {
+    Str << ".cpu    cortex-a15\n";
+  } else {
+    Str << ".cpu    cortex-a9\n";
+  }
+  Str << ".eabi_attribute 6, 10   @ Tag_CPU_arch: ARMv7\n"
       << ".eabi_attribute 7, 65   @ Tag_CPU_arch_profile: App profile\n";
   Str << ".eabi_attribute 8, 1    @ Tag_ARM_ISA_use: Yes\n"
       << ".eabi_attribute 9, 2    @ Tag_THUMB_ISA_use: Thumb-2\n";
-  // TODO(jvoung): check other CPU features like HW div.
   Str << ".fpu    neon\n"
       << ".eabi_attribute 17, 1   @ Tag_ABI_PCS_GOT_use: permit directly\n"
       << ".eabi_attribute 20, 1   @ Tag_ABI_FP_denormal\n"
       << ".eabi_attribute 21, 1   @ Tag_ABI_FP_exceptions\n"
       << ".eabi_attribute 23, 3   @ Tag_ABI_FP_number_model: IEEE 754\n"
       << ".eabi_attribute 34, 1   @ Tag_CPU_unaligned_access\n"
       << ".eabi_attribute 24, 1   @ Tag_ABI_align_needed: 8-byte\n"
       << ".eabi_attribute 25, 1   @ Tag_ABI_align_preserved: 8-byte\n"
       << ".eabi_attribute 28, 1   @ Tag_ABI_VFP_args\n"
       << ".eabi_attribute 36, 1   @ Tag_FP_HP_extension\n"
       << ".eabi_attribute 38, 1   @ Tag_ABI_FP_16bit_format\n"
       << ".eabi_attribute 42, 1   @ Tag_MPextension_use\n"
       << ".eabi_attribute 68, 1   @ Tag_Virtualization_use\n";
+  if (CPUFeatures.hasFeature(TargetARM32Features::HWDivArm)) {
+    Str << ".eabi_attribute 44, 2   @ Tag_DIV_use\n";
+  }
   // Technically R9 is used for TLS with Sandboxing, and we reserve it.
   // However, for compatibility with current NaCl LLVM, don't claim that.
   Str << ".eabi_attribute 14, 3   @ Tag_ABI_PCS_R9_use: Not used\n";
 }
 
 } // end of namespace Ice