AirAllocateStackByGraphColoring.cpp [plain text]
#include "config.h"
#include "AirAllocateStackByGraphColoring.h"
#if ENABLE(B3_JIT)
#include "AirArgInlines.h"
#include "AirCode.h"
#include "AirHandleCalleeSaves.h"
#include "AirInstInlines.h"
#include "AirLiveness.h"
#include "AirPhaseScope.h"
#include "AirStackAllocation.h"
#include "StackAlignment.h"
#include <wtf/ListDump.h>
namespace JSC { namespace B3 { namespace Air {
namespace {
namespace AirAllocateStackByGraphColoringInternal {
static const bool verbose = false;
}
struct CoalescableMove {
CoalescableMove()
{
}
CoalescableMove(StackSlot* src, StackSlot* dst, double frequency)
: src(src)
, dst(dst)
, frequency(frequency)
{
}
bool operator==(const CoalescableMove& other) const
{
return src == other.src
&& dst == other.dst
&& frequency == other.frequency;
}
bool operator!=(const CoalescableMove& other) const
{
return !(*this == other);
}
explicit operator bool() const
{
return *this != CoalescableMove();
}
void dump(PrintStream& out) const
{
out.print(pointerDump(src), "->", pointerDump(dst), "(", frequency, ")");
}
StackSlot* src { nullptr };
StackSlot* dst { nullptr };
double frequency { PNaN };
};
}
void allocateStackByGraphColoring(Code& code)
{
PhaseScope phaseScope(code, "allocateStackByGraphColoring");
handleCalleeSaves(code);
Vector<StackSlot*> assignedEscapedStackSlots =
allocateAndGetEscapedStackSlotsWithoutChangingFrameSize(code);
StackSlotLiveness liveness(code);
IndexMap<StackSlot*, HashSet<StackSlot*>> interference(code.stackSlots().size());
Vector<StackSlot*> slots;
auto isCoalescableMove = [&] (Inst& inst) -> bool {
Width width;
switch (inst.kind.opcode) {
case Move:
width = pointerWidth();
break;
case Move32:
case MoveFloat:
width = Width32;
break;
case MoveDouble:
width = Width64;
break;
default:
return false;
}
if (!Options::coalesceSpillSlots())
return false;
if (inst.args.size() != 3)
return false;
for (unsigned i = 0; i < 2; ++i) {
Arg arg = inst.args[i];
if (!arg.isStack())
return false;
StackSlot* slot = arg.stackSlot();
if (slot->kind() != StackSlotKind::Spill)
return false;
if (slot->byteSize() != bytes(width))
return false;
}
return true;
};
auto isUselessMove = [&] (Inst& inst) -> bool {
return isCoalescableMove(inst) && inst.args[0] == inst.args[1];
};
auto addEdge = [&] (StackSlot* a, StackSlot* b) {
interference[a].add(b);
interference[b].add(a);
};
Vector<CoalescableMove> coalescableMoves;
for (BasicBlock* block : code) {
StackSlotLiveness::LocalCalc localCalc(liveness, block);
auto interfere = [&] (unsigned instIndex) {
if (AirAllocateStackByGraphColoringInternal::verbose)
dataLog("Interfering: ", WTF::pointerListDump(localCalc.live()), "\n");
Inst* prevInst = block->get(instIndex);
Inst* nextInst = block->get(instIndex + 1);
if (prevInst && isCoalescableMove(*prevInst)) {
CoalescableMove move(prevInst->args[0].stackSlot(), prevInst->args[1].stackSlot(), block->frequency());
coalescableMoves.append(move);
for (StackSlot* otherSlot : localCalc.live()) {
if (otherSlot != move.src)
addEdge(move.dst, otherSlot);
}
prevInst = nullptr;
}
Inst::forEachDef<Arg>(
prevInst, nextInst,
[&] (Arg& arg, Arg::Role, Bank, Width) {
if (!arg.isStack())
return;
StackSlot* slot = arg.stackSlot();
if (slot->kind() != StackSlotKind::Spill)
return;
for (StackSlot* otherSlot : localCalc.live())
addEdge(slot, otherSlot);
});
};
for (unsigned instIndex = block->size(); instIndex--;) {
if (AirAllocateStackByGraphColoringInternal::verbose)
dataLog("Analyzing: ", block->at(instIndex), "\n");
Inst& inst = block->at(instIndex);
if (!inst.hasNonArgEffects()) {
bool ok = true;
inst.forEachArg(
[&] (Arg& arg, Arg::Role role, Bank, Width) {
if (Arg::isEarlyDef(role)) {
ok = false;
return;
}
if (!Arg::isLateDef(role))
return;
if (!arg.isStack()) {
ok = false;
return;
}
StackSlot* slot = arg.stackSlot();
if (slot->kind() != StackSlotKind::Spill) {
ok = false;
return;
}
if (localCalc.isLive(slot)) {
ok = false;
return;
}
});
if (ok)
inst = Inst();
}
interfere(instIndex);
localCalc.execute(instIndex);
}
interfere(-1);
block->insts().removeAllMatching(
[&] (const Inst& inst) -> bool {
return !inst;
});
}
if (AirAllocateStackByGraphColoringInternal::verbose) {
for (StackSlot* slot : code.stackSlots())
dataLog("Interference of ", pointerDump(slot), ": ", pointerListDump(interference[slot]), "\n");
}
std::sort(
coalescableMoves.begin(), coalescableMoves.end(),
[&] (CoalescableMove& a, CoalescableMove& b) -> bool {
return a.frequency > b.frequency;
});
IndexMap<StackSlot*, StackSlot*> remappedStackSlots(code.stackSlots().size());
auto remap = [&] (StackSlot* slot) -> StackSlot* {
if (!slot)
return nullptr;
for (;;) {
StackSlot* remappedSlot = remappedStackSlots[slot];
if (!remappedSlot)
return slot;
slot = remappedSlot;
}
};
for (CoalescableMove& move : coalescableMoves) {
move.src = remap(move.src);
move.dst = remap(move.dst);
if (move.src == move.dst)
continue;
if (interference[move.src].contains(move.dst))
continue;
StackSlot* slotToKill = move.src;
StackSlot* slotToKeep = move.dst;
remappedStackSlots[slotToKill] = slotToKeep;
for (StackSlot* interferingSlot : interference[slotToKill]) {
if (interferingSlot == slotToKill)
continue;
interference[interferingSlot].remove(slotToKill);
interference[interferingSlot].add(slotToKeep);
}
interference[slotToKeep].add(interference[slotToKill].begin(), interference[slotToKill].end());
interference[slotToKill].clear();
}
for (BasicBlock* block : code) {
for (Inst& inst : *block) {
for (Arg& arg : inst.args) {
if (arg.isStack())
arg = Arg::stack(remap(arg.stackSlot()), arg.offset());
}
if (isUselessMove(inst))
inst = Inst();
}
}
Vector<StackSlot*> otherSlots = assignedEscapedStackSlots;
for (StackSlot* slot : code.stackSlots()) {
if (remappedStackSlots[slot])
continue;
if (slot->offsetFromFP()) {
continue;
}
HashSet<StackSlot*>& interferingSlots = interference[slot];
otherSlots.resize(assignedEscapedStackSlots.size());
otherSlots.resize(assignedEscapedStackSlots.size() + interferingSlots.size());
unsigned nextIndex = assignedEscapedStackSlots.size();
for (StackSlot* otherSlot : interferingSlots)
otherSlots[nextIndex++] = otherSlot;
assign(slot, otherSlots);
}
updateFrameSizeBasedOnStackSlots(code);
code.setStackIsAllocated(true);
}
} } }
#endif // ENABLE(B3_JIT)