Lower icmp operations between vector values.

src/IceTargetLoweringX8632.cpp

 //===- subzero/src/IceTargetLoweringX8632.cpp - x86-32 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 TargetLoweringX8632 class, which
@@ skipping 154 matching lines @@
   {
     // Define a temporary set of enum values based on low-level
     // table entries.
     enum _tmp_enum {
 #define X(val, C_32, C1_64, C2_64, C3_64) _tmp_##val,
       ICMPX8632_TABLE
 #undef X
           _num
     };
 // Define a set of constants based on high-level table entries.
-#define X(tag, str) static const int _table1_##tag = InstIcmp::tag;
+#define X(tag, str, isunsigned) static const int _table1_##tag = InstIcmp::tag;
     ICEINSTICMP_TABLE;
 #undef X
 // Define a set of constants based on low-level table entries,
 // and ensure the table entry keys are consistent.
 #define X(val, C_32, C1_64, C2_64, C3_64)                                      \
   static const int _table2_##val = _tmp_##val;                                 \
   STATIC_ASSERT(_table1_##val == _table2_##val);
     ICMPX8632_TABLE;
 #undef X
 // Repeat the static asserts with respect to the high-level
 // table entries in case the high-level table has extra entries.
-#define X(tag, str) STATIC_ASSERT(_table1_##tag == _table2_##tag);
+#define X(tag, str, isunsigned) STATIC_ASSERT(_table1_##tag == _table2_##tag);
     ICEINSTICMP_TABLE;
 #undef X
   }
 
   // Validate the enum values in ICETYPEX8632_TABLE.
   {
     // Define a temporary set of enum values based on low-level
     // table entries.
     enum _tmp_enum {
 #define X(tag, elementty, cvt, sdss, pack, width) _tmp_##tag,
@@ skipping 1074 matching lines @@
         // Sz_mul_v16i8
         const IceString Helper = "Sz_mul_v16i8";
         const SizeT MaxSrcs = 2;
         InstCall *Call = makeHelperCall(Helper, Dest, MaxSrcs);
         Call->addArg(Src0);
         Call->addArg(Src1);
         lowerCall(Call);
       }
     } break;
     case InstArithmetic::Shl: {
       // Sz_shl_v4i32, Sz_shl_v8i16, Sz_shl_v16i8

[jvoung (off chromium), 2014/07/23 18:54:55]

Could this have used _psll then, for i32 and i16 elements?

[wala, 2014/07/23 20:40:36]

No. Unfortunately _psll shifts all the fields in the vector by the same amount.

The AVX2 instruction set has vpsllvd and vpsllvw that can be used for the
purposes of lowering shl.

       const IceString Helper = "Sz_shl_" + typeIdentString(Dest->getType());
       const SizeT MaxSrcs = 2;
       InstCall *Call = makeHelperCall(Helper, Dest, MaxSrcs);
       Call->addArg(Src0);
       Call->addArg(Src1);
       lowerCall(Call);
     } break;
     case InstArithmetic::Lshr: {
       // Sz_lshr_v4i32, Sz_lshr_v8i16, Sz_lshr_v16i8
       const IceString Helper = "Sz_lshr_" + typeIdentString(Dest->getType());
@@ skipping 961 matching lines @@
     _mov(Dest, NonDefault);
     Context.insert(Label);
   }
 }
 
 void TargetX8632::lowerIcmp(const InstIcmp *Inst) {
   Operand *Src0 = legalize(Inst->getSrc(0));
   Operand *Src1 = legalize(Inst->getSrc(1));
   Variable *Dest = Inst->getDest();
 
-  // If Src1 is an immediate, or known to be a physical register, we can
-  // allow Src0 to be a memory operand.  Otherwise, Src0 must be copied into
-  // a physical register.  (Actually, either Src0 or Src1 can be chosen for
-  // the physical register, but unfortunately we have to commit to one or
-  // the other before register allocation.)
-  bool IsSrc1ImmOrReg = false;
-  if (llvm::isa<Constant>(Src1)) {
-    IsSrc1ImmOrReg = true;
-  } else if (Variable *Var = llvm::dyn_cast<Variable>(Src1)) {
-    if (Var->hasReg())
+  if (isVectorType(Dest->getType())) {
+    Type Ty = Src0->getType();
+    // Promote i1 vectors to 128 bit integer vector types.
+    if (typeElementType(Ty) == IceType_i1) {
+      Type NewTy = IceType_NUM;
+      switch (Ty) {
+      default:
+        llvm_unreachable("unexpected type");
+        break;
+      case IceType_v4i1:
+        NewTy = IceType_v4i32;
+        break;
+      case IceType_v8i1:
+        NewTy = IceType_v8i16;
+        break;
+      case IceType_v16i1:
+        NewTy = IceType_v16i8;
+        break;
+      }
+      Variable *NewSrc0 = Func->makeVariable(NewTy, Context.getNode());
+      Variable *NewSrc1 = Func->makeVariable(NewTy, Context.getNode());
+      lowerCast(InstCast::create(Func, InstCast::Sext, NewSrc0, Src0));
+      lowerCast(InstCast::create(Func, InstCast::Sext, NewSrc1, Src1));
+      Src0 = NewSrc0;
+      Src1 = NewSrc1;
+      Ty = NewTy;
+    }
+
+    // SSE2 only has signed comparison operations.  Transform unsigned
+    // inputs in a manner that allows for the use of signed comparison
+    // operations by flipping the high order bits.
+    if (Inst->isUnsigned()) {

[Jim Stichnoth, 2014/07/23 17:29:28]

I have a minor problem and a major problem with isUnsigned().

Minor problem.  In IceInst.def, I would one of 3 values to describe the
signed-ness of the operation: -1 for definitely signed (sge, sgt, sle, slt), 1
for definitely unsigned (uge, ugt, ult, ule), and 0 for "don't care" or
non-signed (eq, ne).

Major problem.  I don't think the machinery behind isUnsigned() is justified for
this single use.  Why not just add one more switch statement on
Inst->getCondition() here?  (My opinion would change if we developed more use
cases for this operation.)

[wala, 2014/07/23 20:40:36]

Done.

Removed the unsigned attribute.

+      Variable *T0 = makeReg(Ty);
+      Variable *T1 = makeReg(Ty);
+      Variable *HighOrderBits = makeVectorOfHighOrderBits(Ty);
+      _movp(T0, Src0);
+      _pxor(T0, HighOrderBits);
+      _movp(T1, Src1);
+      _pxor(T1, HighOrderBits);
+      Src0 = T0;
+      Src1 = T1;
+    }
+
+    // TODO: ALIGNHACK: Both operands to compare instructions need to be
+    // in registers until stack alignment support is implemented.  Once
+    // there is support for stack alignment, LEGAL_HACK can be removed.
+#define LEGAL_HACK(Vect) legalizeToVar((Vect))
+    Variable *T = makeReg(Ty);
+    switch (Inst->getCondition()) {
+    default:
+      llvm_unreachable("unexpected condition");
+      break;
+    case InstIcmp::Eq: {
+      _movp(T, Src0);
+      _pcmpeq(T, LEGAL_HACK(Src1));
+    } break;
+    case InstIcmp::Ne: {
+      _movp(T, Src0);
+      _pcmpeq(T, LEGAL_HACK(Src1));
+      Variable *MinusOne = makeVectorOfMinusOnes(Ty);
+      _pxor(T, MinusOne);
+    } break;
+    case InstIcmp::Ugt:
+    case InstIcmp::Sgt: {
+      _movp(T, Src0);
+      _pcmpgt(T, LEGAL_HACK(Src1));
+    } break;
+    case InstIcmp::Uge:
+    case InstIcmp::Sge: {
+      // !(Src1 > Src0)
+      _movp(T, Src1);
+      _pcmpgt(T, LEGAL_HACK(Src0));
+      Variable *MinusOne = makeVectorOfMinusOnes(Ty);
+      _pxor(T, MinusOne);
+    } break;
+    case InstIcmp::Ult:
+    case InstIcmp::Slt: {
+      _movp(T, Src1);
+      _pcmpgt(T, LEGAL_HACK(Src0));
+    } break;
+    case InstIcmp::Ule:
+    case InstIcmp::Sle: {
+      // !(Src0 > Src1)
+      _movp(T, Src0);
+      _pcmpgt(T, LEGAL_HACK(Src1));
+      Variable *MinusOne = makeVectorOfMinusOnes(Ty);
+      _pxor(T, MinusOne);
+    } break;
+    }
+#undef LEGAL_HACK
+
+    _movp(Dest, T);
+
+    // The following pattern occurs often in lowered C and C++ code:
+    //
+    //   %cmp     = icmp pred <n x ty> %src0, %src1
+    //   %cmp.ext = sext <n x i1> %cmp to <n x ty>
+    //
+    // We can avoid the sext operation by copying the result from pcmpgt
+    // and pcmpeq, which is already sign extended, to the result of the
+    // sext operation
+    if (InstCast *NextCast =
+            llvm::dyn_cast_or_null<InstCast>(Context.getNextInst())) {
+      if (NextCast->getCastKind() == InstCast::Sext &&
+          NextCast->getSrc(0) == Dest) {
+        _movp(NextCast->getDest(), T);
+        // Skip over the instruction.
+        NextCast->setDeleted();
+        Context.advanceNext();
+      }
+    }

[jvoung (off chromium), 2014/07/23 18:54:55]

could this just return;

and then the scalar version doesn't need to be indented?

[wala, 2014/07/23 20:40:36]

Done.

+  } else {
+    // If Src1 is an immediate, or known to be a physical register, we can
+    // allow Src0 to be a memory operand.  Otherwise, Src0 must be copied into
+    // a physical register.  (Actually, either Src0 or Src1 can be chosen for
+    // the physical register, but unfortunately we have to commit to one or
+    // the other before register allocation.)
+    bool IsSrc1ImmOrReg = false;
+    if (llvm::isa<Constant>(Src1)) {
       IsSrc1ImmOrReg = true;
-  }
+    } else if (Variable *Var = llvm::dyn_cast<Variable>(Src1)) {
+      if (Var->hasReg())
+        IsSrc1ImmOrReg = true;
+    }
 
-  // Try to fuse a compare immediately followed by a conditional branch.  This
-  // is possible when the compare dest and the branch source operands are the
-  // same, and are their only uses.  TODO: implement this optimization for i64.
-  if (InstBr *NextBr = llvm::dyn_cast_or_null<InstBr>(Context.getNextInst())) {
-    if (Src0->getType() != IceType_i64 && !NextBr->isUnconditional() &&
-        Dest == NextBr->getSrc(0) && NextBr->isLastUse(Dest)) {
-      Operand *Src0New =
-          legalize(Src0, IsSrc1ImmOrReg ? Legal_All : Legal_Reg, true);
-      _cmp(Src0New, Src1);
-      _br(getIcmp32Mapping(Inst->getCondition()), NextBr->getTargetTrue(),
-          NextBr->getTargetFalse());
-      // Skip over the following branch instruction.
-      NextBr->setDeleted();
-      Context.advanceNext();
+    // Try to fuse a compare immediately followed by a conditional branch.  This
+    // is possible when the compare dest and the branch source operands are the
+    // same, and are their only uses.  TODO: implement this optimization for
+    // i64.
+    if (InstBr *NextBr =
+            llvm::dyn_cast_or_null<InstBr>(Context.getNextInst())) {
+      if (Src0->getType() != IceType_i64 && !NextBr->isUnconditional() &&
+          Dest == NextBr->getSrc(0) && NextBr->isLastUse(Dest)) {
+        Operand *Src0New =
+            legalize(Src0, IsSrc1ImmOrReg ? Legal_All : Legal_Reg, true);
+        _cmp(Src0New, Src1);
+        _br(getIcmp32Mapping(Inst->getCondition()), NextBr->getTargetTrue(),
+            NextBr->getTargetFalse());
+        // Skip over the following branch instruction.
+        NextBr->setDeleted();
+        Context.advanceNext();
+        return;
+      }
+    }
+
+    // a=icmp cond, b, c ==> cmp b,c; a=1; br cond,L1; FakeUse(a); a=0; L1:
+    Constant *Zero = Ctx->getConstantZero(IceType_i32);
+    Constant *One = Ctx->getConstantInt(IceType_i32, 1);
+    if (Src0->getType() == IceType_i64) {
+      InstIcmp::ICond Condition = Inst->getCondition();
+      size_t Index = static_cast<size_t>(Condition);
+      assert(Index < TableIcmp64Size);
+      Operand *Src1LoRI = legalize(loOperand(Src1), Legal_Reg | Legal_Imm);
+      Operand *Src1HiRI = legalize(hiOperand(Src1), Legal_Reg | Legal_Imm);
+      if (Condition == InstIcmp::Eq || Condition == InstIcmp::Ne) {
+        InstX8632Label *Label = InstX8632Label::create(Func, this);
+        _mov(Dest, (Condition == InstIcmp::Eq ? Zero : One));
+        _cmp(loOperand(Src0), Src1LoRI);
+        _br(InstX8632Br::Br_ne, Label);
+        _cmp(hiOperand(Src0), Src1HiRI);
+        _br(InstX8632Br::Br_ne, Label);
+        Context.insert(InstFakeUse::create(Func, Dest));
+        _mov(Dest, (Condition == InstIcmp::Eq ? One : Zero));
+        Context.insert(Label);
+      } else {
+        InstX8632Label *LabelFalse = InstX8632Label::create(Func, this);
+        InstX8632Label *LabelTrue = InstX8632Label::create(Func, this);
+        _mov(Dest, One);
+        _cmp(hiOperand(Src0), Src1HiRI);
+        _br(TableIcmp64[Index].C1, LabelTrue);
+        _br(TableIcmp64[Index].C2, LabelFalse);
+        _cmp(loOperand(Src0), Src1LoRI);
+        _br(TableIcmp64[Index].C3, LabelTrue);
+        Context.insert(LabelFalse);
+        Context.insert(InstFakeUse::create(Func, Dest));
+        _mov(Dest, Zero);
+        Context.insert(LabelTrue);
+      }
       return;
     }
+
+    // cmp b, c
+    Operand *Src0New =
+        legalize(Src0, IsSrc1ImmOrReg ? Legal_All : Legal_Reg, true);
+    InstX8632Label *Label = InstX8632Label::create(Func, this);
+    _cmp(Src0New, Src1);
+    _mov(Dest, One);
+    _br(getIcmp32Mapping(Inst->getCondition()), Label);
+    Context.insert(InstFakeUse::create(Func, Dest));
+    _mov(Dest, Zero);
+    Context.insert(Label);
   }
-
-  // a=icmp cond, b, c ==> cmp b,c; a=1; br cond,L1; FakeUse(a); a=0; L1:
-  Constant *Zero = Ctx->getConstantZero(IceType_i32);
-  Constant *One = Ctx->getConstantInt(IceType_i32, 1);
-  if (Src0->getType() == IceType_i64) {
-    InstIcmp::ICond Condition = Inst->getCondition();
-    size_t Index = static_cast<size_t>(Condition);
-    assert(Index < TableIcmp64Size);
-    Operand *Src1LoRI = legalize(loOperand(Src1), Legal_Reg | Legal_Imm);
-    Operand *Src1HiRI = legalize(hiOperand(Src1), Legal_Reg | Legal_Imm);
-    if (Condition == InstIcmp::Eq || Condition == InstIcmp::Ne) {
-      InstX8632Label *Label = InstX8632Label::create(Func, this);
-      _mov(Dest, (Condition == InstIcmp::Eq ? Zero : One));
-      _cmp(loOperand(Src0), Src1LoRI);
-      _br(InstX8632Br::Br_ne, Label);
-      _cmp(hiOperand(Src0), Src1HiRI);
-      _br(InstX8632Br::Br_ne, Label);
-      Context.insert(InstFakeUse::create(Func, Dest));
-      _mov(Dest, (Condition == InstIcmp::Eq ? One : Zero));
-      Context.insert(Label);
-    } else {
-      InstX8632Label *LabelFalse = InstX8632Label::create(Func, this);
-      InstX8632Label *LabelTrue = InstX8632Label::create(Func, this);
-      _mov(Dest, One);
-      _cmp(hiOperand(Src0), Src1HiRI);
-      _br(TableIcmp64[Index].C1, LabelTrue);
-      _br(TableIcmp64[Index].C2, LabelFalse);
-      _cmp(loOperand(Src0), Src1LoRI);
-      _br(TableIcmp64[Index].C3, LabelTrue);
-      Context.insert(LabelFalse);
-      Context.insert(InstFakeUse::create(Func, Dest));
-      _mov(Dest, Zero);
-      Context.insert(LabelTrue);
-    }
-    return;
-  }
-
-  // cmp b, c
-  Operand *Src0New =
-      legalize(Src0, IsSrc1ImmOrReg ? Legal_All : Legal_Reg, true);
-  InstX8632Label *Label = InstX8632Label::create(Func, this);
-  _cmp(Src0New, Src1);
-  _mov(Dest, One);
-  _br(getIcmp32Mapping(Inst->getCondition()), Label);
-  Context.insert(InstFakeUse::create(Func, Dest));
-  _mov(Dest, Zero);
-  Context.insert(Label);
 }
 
 void TargetX8632::lowerInsertElement(const InstInsertElement *Inst) {
   Operand *SourceVectOperand = Inst->getSrc(0);
   Operand *ElementToInsert = Inst->getSrc(1);
   ConstantInteger *ElementIndex =
       llvm::dyn_cast<ConstantInteger>(Inst->getSrc(2));
   // Only constant indices are allowed in PNaCl IR.
   assert(ElementIndex);
   unsigned Index = ElementIndex->getValue();
@@ skipping 1040 matching lines @@
   _br(Inst->getLabelDefault());
 }
 
 void TargetX8632::lowerUnreachable(const InstUnreachable * /*Inst*/) {
   const SizeT MaxSrcs = 0;
   Variable *Dest = NULL;
   InstCall *Call = makeHelperCall("ice_unreachable", Dest, MaxSrcs);
   lowerCall(Call);
 }
 
+// There is no support for loading or emitting vector constants, so the
+// vector values returned from makeVectorOfZeros, makeVectorOfOnes,
+// etc. are initialized with register operations.
+//
+// TODO(wala): Add limited support for vector constants so that
+// complex initialization in registers is unnecessary.
+
 Variable *TargetX8632::makeVectorOfZeros(Type Ty, int32_t RegNum) {
-  // There is no support for loading or emitting vector constants, so
-  // this value is initialized using register operations.
   Variable *Reg = makeReg(Ty, RegNum);
   // Insert a FakeDef, since otherwise the live range of Reg might
   // be overestimated.
   Context.insert(InstFakeDef::create(Func, Reg));
   _pxor(Reg, Reg);
   return Reg;
 }
 
+Variable *TargetX8632::makeVectorOfMinusOnes(Type Ty, int32_t RegNum) {
+  Variable *MinusOnes = makeReg(Ty, RegNum);
+  // Insert a FakeDef so the live range of MinusOnes is not overestimated.
+  Context.insert(InstFakeDef::create(Func, MinusOnes));
+  _pcmpeq(MinusOnes, MinusOnes);
+  return MinusOnes;
+}
+
 Variable *TargetX8632::makeVectorOfOnes(Type Ty, int32_t RegNum) {
-  // There is no support for loading or emitting vector constants, so
-  // this value is initialized using register operations.
   Variable *Dest = makeVectorOfZeros(Ty, RegNum);
-  Variable *MinusOne = makeReg(Ty);
-  // Insert a FakeDef so the live range of MinusOne is not overestimated.
-  Context.insert(InstFakeDef::create(Func, MinusOne));
-  _pcmpeq(MinusOne, MinusOne);
+  Variable *MinusOne = makeVectorOfMinusOnes(Ty);
   _psub(Dest, MinusOne);
   return Dest;
 }
 
+Variable *TargetX8632::makeVectorOfHighOrderBits(Type Ty, int32_t RegNum) {
+  assert(Ty == IceType_v4i32 || Ty == IceType_v4f32 || Ty == IceType_v8i16 ||
+         Ty == IceType_v16i8);
+  if (Ty == IceType_v4f32 || Ty == IceType_v4i32 || Ty == IceType_v8i16) {
+    Variable *Reg = makeVectorOfOnes(Ty, RegNum);
+    SizeT Shift = typeWidthInBytes(typeElementType(Ty)) * X86_CHAR_BIT - 1;
+    _psll(Reg, Ctx->getConstantInt(IceType_i8, Shift));
+    return Reg;
+  } else {
+    // SSE has no left shift operation for vectors of 8 bit integers.
+    const uint32_t HIGH_ORDER_BITS_MASK = 0x80808080;
+    Constant *ConstantMask =
+        Ctx->getConstantInt(IceType_i32, HIGH_ORDER_BITS_MASK);
+    Variable *Reg = makeReg(Ty, RegNum);
+    _movd(Reg, legalize(ConstantMask, Legal_Reg | Legal_Mem));
+    _pshufd(Reg, Reg, Ctx->getConstantZero(IceType_i8));
+    return Reg;
+  }
+}
+
 OperandX8632Mem *TargetX8632::getMemoryOperandForStackSlot(Type Ty,
                                                            Variable *Slot,
                                                            uint32_t Offset) {
   // Ensure that Loc is a stack slot.
   assert(Slot->getWeight() == RegWeight::Zero);
   assert(Slot->getRegNum() == Variable::NoRegister);
   // Compute the location of Loc in memory.
   // TODO(wala,stichnot): lea should not be required.  The address of
   // the stack slot is known at compile time (although not until after
   // addProlog()).
@@ skipping 318 matching lines @@
     for (SizeT i = 0; i < Size; ++i) {
       Str << "\t.byte\t" << (((unsigned)Data[i]) & 0xff) << "\n";
     }
     Str << "\t.size\t" << MangledName << ", " << Size << "\n";
   }
   Str << "\t" << (IsInternal ? ".local" : ".global") << "\t" << MangledName
       << "\n";
 }
 
 } // end of namespace Ice