AirEmitShuffle.cpp [plain text]
#include "config.h"
#include "AirEmitShuffle.h"
#if ENABLE(B3_JIT)
#include "AirCode.h"
#include "AirInstInlines.h"
#include <wtf/GraphNodeWorklist.h>
#include <wtf/ListDump.h>
namespace JSC { namespace B3 { namespace Air {
namespace {
namespace AirEmitShuffleInternal {
static const bool verbose = false;
}
template<typename Functor>
Tmp findPossibleScratch(Code& code, Bank bank, const Functor& functor) {
for (Reg reg : code.regsInPriorityOrder(bank)) {
Tmp tmp(reg);
if (functor(tmp))
return tmp;
}
return Tmp();
}
Tmp findPossibleScratch(Code& code, Bank bank, const Arg& arg1, const Arg& arg2) {
return findPossibleScratch(
code, bank,
[&] (Tmp tmp) -> bool {
return !arg1.usesTmp(tmp) && !arg2.usesTmp(tmp);
});
}
struct Rotate {
Vector<ShufflePair> loop; Vector<ShufflePair> fringe; };
}
Bank ShufflePair::bank() const
{
if (src().isMemory() && dst().isMemory() && width() > pointerWidth()) {
return FP;
}
if (src().isGP() && dst().isGP()) {
return GP;
}
return FP;
}
Vector<Inst, 2> ShufflePair::insts(Code& code, Value* origin) const
{
if (UNLIKELY(src().isMemory() && dst().isMemory()))
return { Inst(moveFor(bank(), width()), origin, src(), dst(), code.newTmp(bank())) };
if (isValidForm(moveFor(bank(), width()), src().kind(), dst().kind()))
return { Inst(moveFor(bank(), width()), origin, src(), dst()) };
ASSERT(isValidForm(moveFor(bank(), width()), Arg::Addr, Arg::Tmp));
ASSERT(isValidForm(moveFor(bank(), width()), Arg::Tmp, Arg::Tmp));
ASSERT(isValidForm(moveFor(bank(), width()), Arg::Tmp, Arg::Addr));
ASSERT(src().isSomeImm());
Tmp tmp = code.newTmp(bank());
ASSERT(isValidForm(Move, Arg::BigImm, Arg::Tmp));
ASSERT(isValidForm(moveFor(bank(), width()), Arg::Tmp, dst().kind()));
return {
Inst(Move, origin, Arg::bigImm(src().value()), tmp),
Inst(moveFor(bank(), width()), origin, tmp, dst()),
};
}
void ShufflePair::dump(PrintStream& out) const
{
out.print(width(), ":", src(), "=>", dst());
}
Inst createShuffle(Value* origin, const Vector<ShufflePair>& pairs)
{
Inst result(Shuffle, origin);
for (const ShufflePair& pair : pairs)
result.append(pair.src(), pair.dst(), Arg::widthArg(pair.width()));
return result;
}
Vector<Inst> emitShuffle(
Code& code, Vector<ShufflePair> pairs, std::array<Arg, 2> scratches, Bank bank,
Value* origin)
{
if (AirEmitShuffleInternal::verbose) {
dataLog(
"Dealing with pairs: ", listDump(pairs), " and scratches ", scratches[0], ", ",
scratches[1], "\n");
}
pairs.removeAllMatching(
[&] (const ShufflePair& pair) -> bool {
return pair.src() == pair.dst();
});
#if !ASSERT_DISABLED
for (const ShufflePair& pair : pairs) {
ASSERT(pair.src().isBank(bank));
ASSERT(pair.dst().isBank(bank));
ASSERT(pair.dst().isTmp() || pair.dst().isMemory());
}
#endif // !ASSERT_DISABLED
HashMap<Arg, Vector<ShufflePair>> shifts;
Vector<Rotate> rotates;
{
HashMap<Arg, Vector<ShufflePair>> mapping;
for (const ShufflePair& pair : pairs)
mapping.add(pair.src(), Vector<ShufflePair>()).iterator->value.append(pair);
Vector<ShufflePair> currentPairs;
while (!mapping.isEmpty()) {
ASSERT(currentPairs.isEmpty());
Arg originalSrc = mapping.begin()->key;
ASSERT(!shifts.contains(originalSrc));
if (AirEmitShuffleInternal::verbose)
dataLog("Processing from ", originalSrc, "\n");
GraphNodeWorklist<Arg> worklist;
worklist.push(originalSrc);
while (Arg src = worklist.pop()) {
HashMap<Arg, Vector<ShufflePair>>::iterator iter = mapping.find(src);
if (iter == mapping.end()) {
if (AirEmitShuffleInternal::verbose)
dataLog("Trying to append shift at ", src, "\n");
currentPairs.appendVector(shifts.take(src));
continue;
}
Vector<ShufflePair> pairs = WTFMove(iter->value);
mapping.remove(iter);
for (const ShufflePair& pair : pairs) {
currentPairs.append(pair);
ASSERT(pair.src() == src);
worklist.push(pair.dst());
}
}
ASSERT(currentPairs.size());
ASSERT(currentPairs[0].src() == originalSrc);
if (AirEmitShuffleInternal::verbose)
dataLog("currentPairs = ", listDump(currentPairs), "\n");
bool isRotate = false;
for (const ShufflePair& pair : currentPairs) {
if (pair.dst() == originalSrc) {
isRotate = true;
break;
}
}
if (isRotate) {
if (AirEmitShuffleInternal::verbose)
dataLog("It's a rotate.\n");
Rotate rotate;
bool ok;
if (currentPairs.last().dst() == originalSrc) {
ok = true;
for (unsigned i = currentPairs.size() - 1; i--;)
ok &= currentPairs[i].dst() == currentPairs[i + 1].src();
} else
ok = false;
if (ok)
rotate.loop = WTFMove(currentPairs);
else {
HashMap<Arg, ShufflePair> dstMapping;
for (const ShufflePair& pair : currentPairs)
dstMapping.add(pair.dst(), pair);
ShufflePair pair = dstMapping.take(originalSrc);
for (;;) {
rotate.loop.append(pair);
auto iter = dstMapping.find(pair.src());
if (iter == dstMapping.end())
break;
pair = iter->value;
dstMapping.remove(iter);
}
rotate.loop.reverse();
for (const ShufflePair& pair : currentPairs) {
if (dstMapping.contains(pair.dst()))
rotate.fringe.append(pair);
}
}
for (unsigned i = rotate.loop.size() - 1; i--;)
ASSERT(rotate.loop[i].dst() == rotate.loop[i + 1].src());
rotates.append(WTFMove(rotate));
currentPairs.shrink(0);
} else {
if (AirEmitShuffleInternal::verbose)
dataLog("It's a shift.\n");
shifts.add(originalSrc, WTFMove(currentPairs));
}
}
}
if (AirEmitShuffleInternal::verbose) {
dataLog("Shifts:\n");
for (auto& entry : shifts)
dataLog(" ", entry.key, ": ", listDump(entry.value), "\n");
dataLog("Rotates:\n");
for (auto& rotate : rotates)
dataLog(" loop = ", listDump(rotate.loop), ", fringe = ", listDump(rotate.fringe), "\n");
}
auto moveForWidth = [&] (Width width) -> Opcode {
return moveFor(bank, width);
};
Opcode conservativeMove = moveForWidth(conservativeWidth(bank));
Vector<Vector<Inst>> resultPacks;
Vector<Inst> result;
auto commitResult = [&] () {
resultPacks.append(WTFMove(result));
};
auto getScratch = [&] (unsigned index, Tmp possibleScratch) -> Tmp {
if (scratches[index].isTmp())
return scratches[index].tmp();
if (!possibleScratch)
return Tmp();
result.append(Inst(conservativeMove, origin, possibleScratch, scratches[index]));
return possibleScratch;
};
auto returnScratch = [&] (unsigned index, Tmp tmp) {
if (Arg(tmp) != scratches[index])
result.append(Inst(conservativeMove, origin, scratches[index], tmp));
};
auto handleShiftPair = [&] (const ShufflePair& pair, unsigned scratchIndex) {
Opcode move = moveForWidth(pair.width());
if (!isValidForm(move, pair.src().kind(), pair.dst().kind())) {
Tmp scratch =
getScratch(scratchIndex, findPossibleScratch(code, bank, pair.src(), pair.dst()));
RELEASE_ASSERT(scratch);
if (isValidForm(move, pair.src().kind(), Arg::Tmp))
result.append(Inst(moveForWidth(pair.width()), origin, pair.src(), scratch));
else {
ASSERT(pair.src().isSomeImm());
ASSERT(move == Move32);
result.append(Inst(Move, origin, Arg::bigImm(pair.src().value()), scratch));
}
result.append(Inst(moveForWidth(pair.width()), origin, scratch, pair.dst()));
returnScratch(scratchIndex, scratch);
return;
}
result.append(Inst(move, origin, pair.src(), pair.dst()));
};
auto handleShift = [&] (Vector<ShufflePair>& shift) {
for (unsigned i = shift.size(); i--;)
handleShiftPair(shift[i], 0);
Arg lastDst = shift.last().dst();
if (lastDst.isTmp()) {
for (Arg& scratch : scratches) {
ASSERT(scratch != lastDst);
if (!scratch.isTmp()) {
scratch = lastDst;
break;
}
}
}
};
for (auto& entry : shifts) {
Vector<ShufflePair>& shift = entry.value;
if (shift.last().dst().isTmp())
handleShift(shift);
commitResult();
}
for (auto& entry : shifts) {
Vector<ShufflePair>& shift = entry.value;
if (!shift.last().dst().isTmp())
handleShift(shift);
commitResult();
}
for (Rotate& rotate : rotates) {
if (!rotate.fringe.isEmpty()) {
handleShift(rotate.fringe);
}
bool canSwap = false;
Opcode swap = Oops;
Width swapWidth = Width8;
if (bank == GP) {
swap = Swap32;
swapWidth = Width32;
bool hasMemory = false;
bool hasIndex = false;
for (ShufflePair& pair : rotate.loop) {
switch (pair.width()) {
case Width32:
break;
case Width64:
swap = Swap64;
swapWidth = Width64;
break;
default:
RELEASE_ASSERT_NOT_REACHED();
break;
}
hasMemory |= pair.src().isMemory() || pair.dst().isMemory();
hasIndex |= pair.src().isIndex() || pair.dst().isIndex();
}
canSwap = isValidForm(swap, Arg::Tmp, Arg::Tmp);
if (hasMemory) {
canSwap &= isValidForm(swap, Arg::Tmp, Arg::Addr);
for (ShufflePair& pair : rotate.loop)
canSwap &= pair.width() == swapWidth;
}
if (hasIndex)
canSwap &= isValidForm(swap, Arg::Tmp, Arg::Index);
}
if (canSwap) {
for (unsigned i = rotate.loop.size() - 1; i--;) {
Arg left = rotate.loop[i].src();
Arg right = rotate.loop[i + 1].src();
if (left.isMemory() && right.isMemory()) {
Tmp scratch = getScratch(0, findPossibleScratch(code, bank, left, right));
RELEASE_ASSERT(scratch);
result.append(Inst(moveForWidth(swapWidth), origin, left, scratch));
result.append(Inst(swap, origin, scratch, right));
result.append(Inst(moveForWidth(swapWidth), origin, scratch, left));
returnScratch(0, scratch);
continue;
}
if (left.isMemory())
std::swap(left, right);
result.append(Inst(swap, origin, left, right));
}
for (ShufflePair pair : rotate.loop) {
if (pair.width() == swapWidth)
continue;
RELEASE_ASSERT(pair.width() == Width32);
RELEASE_ASSERT(swapWidth == Width64);
RELEASE_ASSERT(pair.dst().isTmp());
result.append(Inst(Move32, origin, pair.dst(), pair.dst()));
}
} else {
Tmp scratch = findPossibleScratch(
code, bank,
[&] (Tmp tmp) -> bool {
for (ShufflePair pair : rotate.loop) {
if (pair.src().usesTmp(tmp))
return false;
if (pair.dst().usesTmp(tmp))
return false;
}
return true;
});
scratch = getScratch(0, scratch);
Arg rotateSave = scratch ? Arg(scratch) : scratches[0];
handleShiftPair(
ShufflePair(rotate.loop.last().dst(), rotateSave, rotate.loop[0].width()), 1);
for (unsigned i = rotate.loop.size(); i-- > 1;)
handleShiftPair(rotate.loop[i], 1);
handleShiftPair(
ShufflePair(rotateSave, rotate.loop[0].dst(), rotate.loop[0].width()), 1);
if (scratch)
returnScratch(0, scratch);
}
commitResult();
}
ASSERT(result.isEmpty());
for (unsigned i = resultPacks.size(); i--;)
result.appendVector(resultPacks[i]);
return result;
}
Vector<Inst> emitShuffle(
Code& code, const Vector<ShufflePair>& pairs,
const std::array<Arg, 2>& gpScratch, const std::array<Arg, 2>& fpScratch,
Value* origin)
{
Vector<ShufflePair> gpPairs;
Vector<ShufflePair> fpPairs;
for (const ShufflePair& pair : pairs) {
switch (pair.bank()) {
case GP:
gpPairs.append(pair);
break;
case FP:
fpPairs.append(pair);
break;
}
}
Vector<Inst> result;
result.appendVector(emitShuffle(code, gpPairs, gpScratch, GP, origin));
result.appendVector(emitShuffle(code, fpPairs, fpScratch, FP, origin));
return result;
}
} } }
#endif // ENABLE(B3_JIT)