Inline memove for small constant sizes and refactor memcpy and memset.

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 3016 matching lines @@
     Call->addArg(Instr->getArg(0));
     Call->addArg(Instr->getArg(1));
     lowerCall(Call);
     return;
   }
   case Intrinsics::Memcpy: {
     lowerMemcpy(Instr->getArg(0), Instr->getArg(1), Instr->getArg(2));
     return;
   }
   case Intrinsics::Memmove: {
-    InstCall *Call = makeHelperCall(H_call_memmove, nullptr, 3);
-    Call->addArg(Instr->getArg(0));
-    Call->addArg(Instr->getArg(1));
-    Call->addArg(Instr->getArg(2));
-    lowerCall(Call);
+    lowerMemmove(Instr->getArg(0), Instr->getArg(1), Instr->getArg(2));
     return;
   }
   case Intrinsics::Memset: {
     lowerMemset(Instr->getArg(0), Instr->getArg(1), Instr->getArg(2));
     return;
   }
   case Intrinsics::NaClReadTP: {
     if (Ctx->getFlags().getUseSandboxing()) {
       Operand *Src = dispatchToConcrete(&Machine::createNaClReadTPSrcOperand);
       Variable *Dest = Instr->getDest();
@@ skipping 422 matching lines @@
     _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>
+Type TargetX86Base<Machine>::typeForSize(uint32_t Size, bool Overflow,

[Jim Stichnoth, 2015/08/12 13:41:47]

Is there anything machine-specific about this function?  If not, maybe move it
to IceTypes.cpp.

[ascull, 2015/08/17 22:18:52]

Possibly, as we discussed.

+                                         uint32_t LimitWidth) {
+  assert(Size != 0);
+  static const Type TypeForSize[] = {IceType_i8, IceType_i16, IceType_i32,
+                                     IceType_f64, IceType_v16i8};

[John, 2015/08/12 17:44:57]

See if

Traits::Is64Bit ? IceType_i64 : IceType_f64

works for 64 bit data types. If it does, than please use that instead.

[ascull, 2015/08/17 22:18:53]

That does work. And it sorts on of the TODOs, thanks.

+  uint32_t TyIndex = llvm::findLastSet(Size, llvm::ZB_Undefined);
+  if (Overflow && !llvm::isPowerOf2_32(Size))
+    ++TyIndex;
+  uint32_t MaxIndex =
+      LimitWidth ? llvm::findLastSet(LimitWidth, llvm::ZB_Undefined) : 4;

[Jim Stichnoth, 2015/08/12 13:41:47]

Can you use llvm::array_lengthof(TypeForSize)-1 instead of 4?
(assuming that's correct and what's meant)

[ascull, 2015/08/17 22:18:52]

This is the function I tried and failed to find, Thanks!
Done.

+  return TypeForSize[std::min(TyIndex, MaxIndex)];
+}
+
+template <class Machine>
+void TargetX86Base<Machine>::lowerCopyMem(Type Ty, Variable *Dest,
+                                          Variable *Src, uint32_t OffsetAmt) {
+  Constant *Offset = OffsetAmt ? Ctx->getConstantInt32(OffsetAmt) : nullptr;
+  // TODO(ascull): this or add nullptr test to _movp, _movq
+  Variable *Data = makeReg(Ty);
+
+  // TODO(ascull): is 64-bit better with vector or scalar movq?
+  auto *SrcMem = Traits::X86OperandMem::create(Func, Ty, Src, Offset);
+  if (isVectorType(Ty))
+    _movp(Data, SrcMem);
+  else if (Ty == IceType_f64)
+    _movq(Data, SrcMem);
+  else
+    _mov(Data, SrcMem);
+
+  auto *DestMem = Traits::X86OperandMem::create(Func, Ty, Dest, Offset);
+  if (isVectorType(Ty))
+    _storep(Data, DestMem);

[John, 2015/08/12 17:44:57]

just curious: why store[pq]\? instead of mov?

you could also do something like:

if (isVectorType()) {
  _movp()
  _storep()
} else if (Ty == i64) {
  _movq()
  _storeq()
} else {
  _mov()
  _store()
}

[ascull, 2015/08/17 22:18:53]

_store seems to be needed for writing to memory. I guess it's just to make it
clearer to read instead of trying to decipher the mov.

+  else if (Ty == IceType_f64)
+    _storeq(Data, DestMem);
+  else
+    _store(Data, DestMem);
+}
+
+template <class Machine>
 void TargetX86Base<Machine>::lowerMemcpy(Operand *Dest, Operand *Src,
                                          Operand *Count) {
   // There is a load and store for each chunk in the unroll
   constexpr uint32_t UNROLL_LIMIT = 8;
   constexpr uint32_t BytesPerStorep = 16;
-  constexpr uint32_t BytesPerStoreq = 8;
-  constexpr uint32_t BytesPerStorei32 = 4;
-  constexpr uint32_t BytesPerStorei16 = 2;
-  constexpr uint32_t BytesPerStorei8 = 1;
 
   // Check if the operands are constants
   const auto *CountConst = llvm::dyn_cast<const ConstantInteger32>(Count);
   const bool IsCountConst = CountConst != nullptr;
   const uint32_t CountValue = IsCountConst ? CountConst->getValue() : 0;
 
   if (IsCountConst && CountValue <= BytesPerStorep * UNROLL_LIMIT) {
     // Unlikely, but nothing to do if it does happen
     if (CountValue == 0)
       return;
 
     Variable *SrcBase = legalizeToReg(Src);
     Variable *DestBase = legalizeToReg(Dest);
 
-    auto lowerCopy = [this, DestBase, SrcBase](Type Ty, uint32_t OffsetAmt) {
-      Constant *Offset = OffsetAmt ? Ctx->getConstantInt32(OffsetAmt) : nullptr;
-      // TODO(ascull): this or add nullptr test to _movp, _movq
-      Variable *Data = makeReg(Ty);
+    // Find the largest type that can be used and use it as much as possible in
+    // reverse order. Then handle any remainder with overlapping copies. Since
+    // the remainder will be at the end, there will be reduces pressure on the

[Jim Stichnoth, 2015/08/12 13:41:47]

reduced (I think)

[ascull, 2015/08/17 22:18:53]

Done.

+    // memory unit as the access to the same memory are far apart.

[Jim Stichnoth, 2015/08/12 13:41:47]

accesses ?

[ascull, 2015/08/17 22:18:53]

Done.

+    Type Ty = typeForSize(CountValue);
+    uint32_t TyWidth = typeWidthInBytes(Ty);
 
-      // TODO(ascull): is 64-bit better with vector or scalar movq?
-      auto *SrcMem = Traits::X86OperandMem::create(Func, Ty, SrcBase, Offset);
-      if (isVectorType(Ty))
-        _movp(Data, SrcMem);
-      else if (Ty == IceType_f64)
-        _movq(Data, SrcMem);
-      else
-        _mov(Data, SrcMem);
-
-      auto *DestMem = Traits::X86OperandMem::create(Func, Ty, DestBase, Offset);
-      if (isVectorType(Ty))
-        _storep(Data, DestMem);
-      else if (Ty == IceType_f64)
-        _storeq(Data, DestMem);
-      else
-        _store(Data, DestMem);
-    };
-
-    // Lowers the assignment to the remaining bytes. Assumes the original size
-    // was large enough to allow for overlaps.
-    auto lowerLeftOvers = [this, lowerCopy, CountValue](uint32_t Size) {
-      if (Size > BytesPerStoreq) {
-        lowerCopy(IceType_v16i8, CountValue - BytesPerStorep);
-      } else if (Size > BytesPerStorei32) {
-        lowerCopy(IceType_f64, CountValue - BytesPerStoreq);
-      } else if (Size > BytesPerStorei16) {
-        lowerCopy(IceType_i32, CountValue - BytesPerStorei32);
-      } else if (Size > BytesPerStorei8) {
-        lowerCopy(IceType_i16, CountValue - BytesPerStorei16);
-      } else if (Size == BytesPerStorei8) {
-        lowerCopy(IceType_i8, CountValue - BytesPerStorei8);
-      }
-    };
-
-    if (CountValue >= BytesPerStorep) {
-      // Use large vector operations
-      for (uint32_t N = CountValue & 0xFFFFFFF0; N != 0;) {
-        N -= BytesPerStorep;
-        lowerCopy(IceType_v16i8, N);
-      }
-      lowerLeftOvers(CountValue & 0xF);
-      return;
+    uint32_t RemainingBytes = CountValue;

[John, 2015/08/12 17:44:57]

do you really need uint32_t's here? unless you really need the extra bit, please
use signed integers.

[ascull, 2015/08/17 22:18:53]

The CountValue comes from a size_t so is unsigned. I've changes Offset to int_32
to match getConstantInt32. What do you prefer signed?

+    uint32_t Offset = (CountValue & ~(TyWidth - 1)) - TyWidth;
+    while (RemainingBytes >= TyWidth) {
+      lowerCopyMem(Ty, DestBase, SrcBase, Offset);
+      RemainingBytes -= TyWidth;
+      Offset -= TyWidth;
     }
 
-    // Too small to use large vector operations so use small ones instead
-    if (CountValue >= BytesPerStoreq) {
-      lowerCopy(IceType_f64, 0);
-      lowerLeftOvers(CountValue - BytesPerStoreq);
+    if (RemainingBytes == 0)
       return;
-    }
 
-    // Too small for vector operations so use scalar ones
-    if (CountValue >= BytesPerStorei32) {
-      lowerCopy(IceType_i32, 0);
-      lowerLeftOvers(CountValue - BytesPerStorei32);
-      return;
-    }
-
-    // 3 is the awkward size as it is too small for the vector or 32-bit
-    // operations and will not work with lowerLeftOvers as there is no valid
-    // overlap.
-    if (CountValue == 3) {
-      lowerCopy(IceType_i16, 0);
-      lowerCopy(IceType_i8, 2);
-      return;
-    }
-
-    // 1 or 2 can be done in a single scalar copy
-    lowerLeftOvers(CountValue);
+    // Lower the remaining bytes. Adjust to larger types in order to make use
+    // of overlaps in the copies.
+    constexpr bool Overflow = true;
+    Type LeftOverTy = typeForSize(RemainingBytes, Overflow);
+    Offset = CountValue - typeWidthInBytes(LeftOverTy);

[John, 2015/08/12 17:44:57]

be careful with unaligned memory accesses. it might be better so simply copy
bytes?

[ascull, 2015/08/17 22:18:53]

This is the way gcc and clang do it. Since the alignment will not be known there
will be a large overhead in checking that. Doing it with bytes seems like it
would take longer, especially if there are 15 bytes! We also don't know if the
previous copies were aligned (hence the use of movups).

+    lowerCopyMem(LeftOverTy, DestBase, SrcBase, Offset);
     return;
   }
 
   // Fall back on a function call
   InstCall *Call = makeHelperCall(H_call_memcpy, nullptr, 3);
   Call->addArg(Dest);
   Call->addArg(Src);
   Call->addArg(Count);
+  lowerCall(Call);
+}
+
+template <class Machine>
+void TargetX86Base<Machine>::lowerMemmove(Operand *Dest, Operand *Src,
+                                          Operand *Count) {
+  // There is a load and store for each chunk in the unroll
+  constexpr uint32_t UNROLL_LIMIT = 8;
+  constexpr uint32_t BytesPerStorep = 16;
+
+  // Check if the operands are constants
+  const auto *CountConst = llvm::dyn_cast<const ConstantInteger32>(Count);
+  const bool IsCountConst = CountConst != nullptr;
+  const uint32_t CountValue = IsCountConst ? CountConst->getValue() : 0;
+
+  if (IsCountConst && CountValue <= BytesPerStorep * UNROLL_LIMIT) {
+    // Unlikely, but nothing to do if it does happen
+    if (CountValue == 0)
+      return;
+
+    Variable *SrcBase = legalizeToReg(Src);
+    Variable *DestBase = legalizeToReg(Dest);
+
+    // Make sure to only copy down to avoid overlap issues. This means Src must
+    // have a greater address than Dest.
+    _cmp(SrcBase, DestBase);
+    typename Traits::Insts::Label *Label =
+        Traits::Insts::Label::create(Func, this);
+    _br(Traits::Cond::Br_b, Label);
+    _xchg(SrcBase, DestBase);
+    Context.insert(Label);
+
+    // We can't assume overlapping copies are safe as the copy may overwrite
+    // the source. This means we need to repeatedly select the largest size to
+    // copy that doesn't cause overlap.
+    uint32_t Size = CountValue;
+    uint32_t Offset = 0;
+    while (Size > 0) {
+      Type Ty = typeForSize(Size);
+      lowerCopyMem(Ty, DestBase, SrcBase, Offset);
+      Size -= typeWidthInBytes(Ty);
+      Offset += typeWidthInBytes(Ty);
+    }
+
+    return;
+  }
+
+  // Fall back on a function call
+  InstCall *Call = makeHelperCall(H_call_memmove, nullptr, 3);
+  Call->addArg(Dest);
+  Call->addArg(Src);
+  Call->addArg(Count);
   lowerCall(Call);
 }
 
 template <class Machine>
 void TargetX86Base<Machine>::lowerMemset(Operand *Dest, Operand *Val,
                                          Operand *Count) {
   constexpr uint32_t UNROLL_LIMIT = 16;
   constexpr uint32_t BytesPerStorep = 16;
   constexpr uint32_t BytesPerStoreq = 8;
   constexpr uint32_t BytesPerStorei32 = 4;
-  constexpr uint32_t BytesPerStorei16 = 2;
-  constexpr uint32_t BytesPerStorei8 = 1;
   assert(Val->getType() == IceType_i8);
 
   // Check if the operands are constants
   const auto *CountConst = llvm::dyn_cast<const ConstantInteger32>(Count);
   const auto *ValConst = llvm::dyn_cast<const ConstantInteger32>(Val);
   const bool IsCountConst = CountConst != nullptr;
   const bool IsValConst = ValConst != nullptr;
   const uint32_t CountValue = IsCountConst ? CountConst->getValue() : 0;
   const uint32_t ValValue = IsValConst ? ValConst->getValue() : 0;
 
   // Unlikely, but nothing to do if it does happen
   if (IsCountConst && CountValue == 0)
     return;
 
   // TODO(ascull): if the count is constant but val is not it would be possible
   // to inline by spreading the value across 4 bytes and accessing subregs e.g.
   // eax, ax and al.
   if (IsCountConst && IsValConst) {
     Variable *Base = nullptr;
+    Variable *VecReg = nullptr;
     const uint32_t SpreadValue =
         (ValValue << 24) | (ValValue << 16) | (ValValue << 8) | ValValue;
-    Variable *VecReg = nullptr;
 
     auto lowerSet = [this, &Base, SpreadValue, &VecReg](Type Ty,
-                                                       uint32_t OffsetAmt) {
+                                                        uint32_t OffsetAmt) {
       assert(Base != nullptr);
       Constant *Offset = OffsetAmt ? Ctx->getConstantInt32(OffsetAmt) : nullptr;
 
       // TODO(ascull): is 64-bit better with vector or scalar movq?
       auto *Mem = Traits::X86OperandMem::create(Func, Ty, Base, Offset);
       if (isVectorType(Ty)) {
         assert(VecReg != nullptr);
         _storep(VecReg, Mem);
-      } else if (Ty == IceType_i64) {
+      } else if (Ty == IceType_f64) {
         assert(VecReg != nullptr);
         _storeq(VecReg, Mem);
       } else {
         _store(Ctx->getConstantInt(Ty, SpreadValue), Mem);
       }
     };
 
-    // Lowers the assignment to the remaining bytes. Assumes the original size
-    // was large enough to allow for overlaps.
-    auto lowerLeftOvers = [this, lowerSet, CountValue](uint32_t Size) {
-      if (Size > BytesPerStoreq) {
-        lowerSet(IceType_v16i8, CountValue - BytesPerStorep);
-      } else if (Size > BytesPerStorei32) {
-        lowerSet(IceType_i64, CountValue - BytesPerStoreq);
-      } else if (Size > BytesPerStorei16) {
-        lowerSet(IceType_i32, CountValue - BytesPerStorei32);
-      } else if (Size > BytesPerStorei8) {
-        lowerSet(IceType_i16, CountValue - BytesPerStorei16);
-      } else if (Size == BytesPerStorei8) {
-        lowerSet(IceType_i8, CountValue - BytesPerStorei8);
-      }
-    };
-
-    // When the value is zero it can be loaded into a vector register cheaply
-    // using the xor trick.
+    // Find the largest type that can be used and use it as much as possible in
+    // reverse order. Then handle any remainder with overlapping copies. Since
+    // the remainder will be at the end, there will be reduces pressure on the
+    // memory unit as the access to the same memory are far apart.
+    Type Ty;
     if (ValValue == 0 && CountValue >= BytesPerStoreq &&
         CountValue <= BytesPerStorep * UNROLL_LIMIT) {
+      // When the value is zero it can be loaded into a vector register cheaply
+      // using the xor trick.
       Base = legalizeToReg(Dest);
       VecReg = makeVectorOfZeros(IceType_v16i8);
+      Ty = typeForSize(CountValue);
+    } else if (CountValue <= BytesPerStorei32 * UNROLL_LIMIT) {
+      // When the value is non-zero or the count is small we can't use vector
+      // instructions so are limits to 32-bit stores.
+      Base = legalizeToReg(Dest);
+      constexpr bool Offset = false;
+      constexpr uint32_t LimitWidth = 4;
+      Ty = typeForSize(CountValue, Offset, LimitWidth);
+    }
 
-      // Too small to use large vector operations so use small ones instead
-      if (CountValue < BytesPerStorep) {
-        lowerSet(IceType_i64, 0);
-        lowerLeftOvers(CountValue - BytesPerStoreq);
-        return;
+    if (Base) {
+      uint32_t TyWidth = typeWidthInBytes(Ty);
+
+      uint32_t RemainingBytes = CountValue;
+      uint32_t Offset = (CountValue & ~(TyWidth - 1)) - TyWidth;
+      while (RemainingBytes >= TyWidth) {
+        lowerSet(Ty, Offset);
+        RemainingBytes -= TyWidth;
+        Offset -= TyWidth;
       }
 
-      // Use large vector operations
-      for (uint32_t N = CountValue & 0xFFFFFFF0; N != 0;) {
-        N -= 16;
-        lowerSet(IceType_v16i8, N);
-      }
-      lowerLeftOvers(CountValue & 0xF);
-      return;
-    }
+      if (RemainingBytes == 0)
+        return;
 
-    // TODO(ascull): load val into reg and select subregs e.g. eax, ax, al?
-    if (CountValue <= BytesPerStorei32 * UNROLL_LIMIT) {
-      Base = legalizeToReg(Dest);
-      // 3 is the awkward size as it is too small for the vector or 32-bit
-      // operations and will not work with lowerLeftOvers as there is no valid
-      // overlap.
-      if (CountValue == 3) {
-        lowerSet(IceType_i16, 0);
-        lowerSet(IceType_i8, 2);
-        return;
-      }
-
-      // TODO(ascull); 64-bit can do better with 64-bit mov
-      for (uint32_t N = CountValue & 0xFFFFFFFC; N != 0;) {
-        N -= 4;
-        lowerSet(IceType_i32, N);
-      }
-      lowerLeftOvers(CountValue & 0x3);
+      // Lower the remaining bytes. Adjust to larger types in order to make use
+      // of overlaps in the copies.
+      constexpr bool Overflow = true;
+      Type LeftOverTy = typeForSize(RemainingBytes, Overflow);
+      Offset = CountValue - typeWidthInBytes(LeftOverTy);
+      lowerSet(LeftOverTy, Offset);
       return;
     }
   }
 
   // Fall back on calling the memset function. The value operand needs to be
   // extended to a stack slot size because the PNaCl ABI requires arguments to
   // be at least 32 bits wide.
   Operand *ValExt;
   if (IsValConst) {
     ValExt = Ctx->getConstantInt(stackSlotType(), ValValue);
@@ skipping 1453 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