blob: 77afd8853b6b717e7de63b9db6b497bdec9256e8 [file] [log] [blame]
/*
* Copyright (C) 2016-2019 Apple Inc. All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* are met:
* 1. Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
* 2. Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in the
* documentation and/or other materials provided with the distribution.
*
* THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
* EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
* PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR
* CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
* EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
* PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
* PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
* OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
* OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*/
#include "config.h"
#include "AirFixObviousSpills.h"
#if ENABLE(B3_JIT)
#include "AirArgInlines.h"
#include "AirCode.h"
#include "AirInstInlines.h"
#include "AirPhaseScope.h"
#include <wtf/IndexMap.h>
#include <wtf/ListDump.h>
namespace JSC { namespace B3 { namespace Air {
namespace {
namespace AirFixObviousSpillsInternal {
static constexpr bool verbose = false;
}
class FixObviousSpills {
public:
FixObviousSpills(Code& code)
: m_code(code)
, m_atHead(code.size())
, m_notBottom(code.size())
, m_shouldVisit(code.size())
{
}
void run()
{
if (AirFixObviousSpillsInternal::verbose)
dataLog("Code before fixObviousSpills:\n", m_code);
computeAliases();
fixCode();
}
private:
void computeAliases()
{
m_notBottom.quickSet(0);
m_shouldVisit.quickSet(0);
bool changed = true;
while (changed) {
changed = false;
for (unsigned blockIndex : m_shouldVisit) {
m_shouldVisit.quickClear(blockIndex);
BasicBlock* block = m_code[blockIndex];
ASSERT(m_notBottom.quickGet(blockIndex));
m_block = block;
m_state = m_atHead[block];
if (AirFixObviousSpillsInternal::verbose)
dataLog("Executing block ", *m_block, ": ", m_state, "\n");
for (m_instIndex = 0; m_instIndex < block->size(); ++m_instIndex)
executeInst();
// Before we call merge we must make sure that the two states are sorted.
m_state.sort();
for (BasicBlock* successor : block->successorBlocks()) {
unsigned successorIndex = successor->index();
State& toState = m_atHead[successor];
if (m_notBottom.quickGet(successorIndex)) {
bool changedAtSuccessorHead = toState.merge(m_state);
if (changedAtSuccessorHead) {
changed = true;
m_shouldVisit.quickSet(successorIndex);
}
} else { // The state at head of successor is bottom
toState = m_state;
changed = true;
m_notBottom.quickSet(successorIndex);
m_shouldVisit.quickSet(successorIndex);
}
}
}
}
}
void fixCode()
{
for (BasicBlock* block : m_code) {
m_block = block;
m_state = m_atHead[block];
RELEASE_ASSERT(m_notBottom.quickGet(block->index()));
for (m_instIndex = 0; m_instIndex < block->size(); ++m_instIndex) {
fixInst();
executeInst();
}
}
}
template<typename Func>
void forAllAliases(const Func& func)
{
Inst& inst = m_block->at(m_instIndex);
switch (inst.kind.opcode) {
case Move:
if (inst.args[0].isSomeImm()) {
if (inst.args[1].isReg())
func(RegConst(inst.args[1].reg(), inst.args[0].value()));
else if (isSpillSlot(inst.args[1]))
func(SlotConst(inst.args[1].stackSlot(), inst.args[0].value()));
} else if (isSpillSlot(inst.args[0]) && inst.args[1].isReg()) {
if (std::optional<int64_t> constant = m_state.constantFor(inst.args[0]))
func(RegConst(inst.args[1].reg(), *constant));
func(RegSlot(inst.args[1].reg(), inst.args[0].stackSlot(), RegSlot::AllBits));
} else if (inst.args[0].isReg() && isSpillSlot(inst.args[1])) {
if (std::optional<int64_t> constant = m_state.constantFor(inst.args[0]))
func(SlotConst(inst.args[1].stackSlot(), *constant));
func(RegSlot(inst.args[0].reg(), inst.args[1].stackSlot(), RegSlot::AllBits));
}
break;
case Move32:
if (inst.args[0].isSomeImm()) {
if (inst.args[1].isReg())
func(RegConst(inst.args[1].reg(), static_cast<uint32_t>(inst.args[0].value())));
else if (isSpillSlot(inst.args[1]))
func(SlotConst(inst.args[1].stackSlot(), static_cast<uint32_t>(inst.args[0].value())));
} else if (isSpillSlot(inst.args[0]) && inst.args[1].isReg()) {
if (std::optional<int64_t> constant = m_state.constantFor(inst.args[0]))
func(RegConst(inst.args[1].reg(), static_cast<uint32_t>(*constant)));
func(RegSlot(inst.args[1].reg(), inst.args[0].stackSlot(), RegSlot::ZExt32));
} else if (inst.args[0].isReg() && isSpillSlot(inst.args[1])) {
if (std::optional<int64_t> constant = m_state.constantFor(inst.args[0]))
func(SlotConst(inst.args[1].stackSlot(), static_cast<int32_t>(*constant)));
func(RegSlot(inst.args[0].reg(), inst.args[1].stackSlot(), RegSlot::Match32));
}
break;
case MoveFloat:
if (isSpillSlot(inst.args[0]) && inst.args[1].isReg())
func(RegSlot(inst.args[1].reg(), inst.args[0].stackSlot(), RegSlot::Match32));
else if (inst.args[0].isReg() && isSpillSlot(inst.args[1]))
func(RegSlot(inst.args[0].reg(), inst.args[1].stackSlot(), RegSlot::Match32));
break;
case MoveDouble:
if (isSpillSlot(inst.args[0]) && inst.args[1].isReg())
func(RegSlot(inst.args[1].reg(), inst.args[0].stackSlot(), RegSlot::AllBits));
else if (inst.args[0].isReg() && isSpillSlot(inst.args[1]))
func(RegSlot(inst.args[0].reg(), inst.args[1].stackSlot(), RegSlot::AllBits));
break;
default:
break;
}
}
void executeInst()
{
Inst& inst = m_block->at(m_instIndex);
if (AirFixObviousSpillsInternal::verbose)
dataLog(" Executing ", inst, ": ", m_state, "\n");
Inst::forEachDefWithExtraClobberedRegs<Arg>(
&inst, &inst,
[&] (const Arg& arg, Arg::Role, Bank, Width) {
if (AirFixObviousSpillsInternal::verbose)
dataLog(" Clobbering ", arg, "\n");
m_state.clobber(arg);
});
forAllAliases(
[&] (const auto& alias) {
m_state.addAlias(alias);
});
}
void fixInst()
{
Inst& inst = m_block->at(m_instIndex);
if (AirFixObviousSpillsInternal::verbose)
dataLog("Fixing inst ", inst, ": ", m_state, "\n");
// Check if alias analysis says that this is unnecessary.
bool shouldLive = true;
forAllAliases(
[&] (const auto& alias) {
shouldLive &= !m_state.contains(alias);
});
if (!shouldLive) {
inst = Inst();
return;
}
// First handle some special instructions.
switch (inst.kind.opcode) {
case Move: {
if (inst.args[0].isBigImm() && inst.args[1].isReg()
&& isValidForm(Add64, Arg::Imm, Arg::Tmp, Arg::Tmp)) {
// BigImm materializations are super expensive on both x86 and ARM. Let's try to
// materialize this bad boy using math instead. Note that we use unsigned math here
// since it's more deterministic.
uint64_t myValue = inst.args[0].value();
Reg myDest = inst.args[1].reg();
for (const RegConst& regConst : m_state.regConst) {
uint64_t otherValue = regConst.constant;
// Let's try add. That's the only thing that works on all platforms, since it's
// the only cheap arithmetic op that x86 does in three operands. Long term, we
// should add fancier materializations here for ARM if the BigImm is yuge.
uint64_t delta = myValue - otherValue;
if (Arg::isValidImmForm(delta)) {
inst.kind = Add64;
inst.args.resize(3);
inst.args[0] = Arg::imm(delta);
inst.args[1] = Tmp(regConst.reg);
inst.args[2] = Tmp(myDest);
return;
}
}
return;
}
break;
}
default:
break;
}
// FIXME: This code should be taught how to simplify the spill-to-spill move
// instruction. Basically it needs to know to remove the scratch arg.
// https://bugs.webkit.org/show_bug.cgi?id=171133
// Create a copy in case we invalidate the instruction. That doesn't happen often.
Inst instCopy = inst;
// The goal is to replace references to stack slots. We only care about early uses. We can't
// handle UseDefs. We could teach this to handle UseDefs if we inserted a store instruction
// after and we proved that the register aliased to the stack slot dies here. We can get that
// information from the liveness analysis. We also can't handle late uses, because we don't
// look at late clobbers when doing this.
bool didThings = false;
auto handleArg = [&] (Arg& arg, Arg::Role role, Bank, Width width) {
if (!isSpillSlot(arg))
return;
if (!Arg::isEarlyUse(role))
return;
if (Arg::isAnyDef(role))
return;
// Try to get a register if at all possible.
if (const RegSlot* alias = m_state.getRegSlot(arg.stackSlot())) {
switch (width) {
case Width64:
if (alias->mode != RegSlot::AllBits)
return;
if (AirFixObviousSpillsInternal::verbose)
dataLog(" Replacing ", arg, " with ", alias->reg, "\n");
arg = Tmp(alias->reg);
didThings = true;
return;
case Width32:
if (AirFixObviousSpillsInternal::verbose)
dataLog(" Replacing ", arg, " with ", alias->reg, " (subwidth case)\n");
arg = Tmp(alias->reg);
didThings = true;
return;
default:
return;
}
}
// Revert to immediate if that didn't work.
if (const SlotConst* alias = m_state.getSlotConst(arg.stackSlot())) {
if (AirFixObviousSpillsInternal::verbose)
dataLog(" Replacing ", arg, " with constant ", alias->constant, "\n");
if (Arg::isValidImmForm(alias->constant))
arg = Arg::imm(alias->constant);
else
arg = Arg::bigImm(alias->constant);
didThings = true;
return;
}
};
inst.forEachArg(handleArg);
if (!didThings || inst.isValidForm())
return;
// We introduced something invalid along the way. Back up and carefully handle each argument.
inst = instCopy;
ASSERT(inst.isValidForm());
inst.forEachArg(
[&] (Arg& arg, Arg::Role role, Bank bank, Width width) {
Arg argCopy = arg;
handleArg(arg, role, bank, width);
if (!inst.isValidForm())
arg = argCopy;
});
}
static bool isSpillSlot(const Arg& arg)
{
return arg.isStack() && arg.stackSlot()->isSpill();
}
struct RegConst {
RegConst()
{
}
RegConst(Reg reg, int64_t constant)
: reg(reg)
, constant(constant)
{
}
explicit operator bool() const
{
return !!reg;
}
bool operator==(const RegConst& other) const
{
return reg == other.reg
&& constant == other.constant;
}
bool operator<(const RegConst& other) const
{
return reg < other.reg || (reg == other.reg && constant < other.constant);
}
void dump(PrintStream& out) const
{
out.print(reg, "->", constant);
}
Reg reg;
int64_t constant { 0 };
};
struct RegSlot {
enum Mode : int8_t {
AllBits,
ZExt32, // Register contains zero-extended contents of stack slot.
Match32 // Low 32 bits of register match low 32 bits of stack slot.
};
RegSlot()
{
}
RegSlot(Reg reg, StackSlot* slot, Mode mode)
: slot(slot)
, reg(reg)
, mode(mode)
{
}
explicit operator bool() const
{
return slot && reg;
}
bool operator==(const RegSlot& other) const
{
return slot == other.slot
&& reg == other.reg
&& mode == other.mode;
}
bool operator<(const RegSlot& other) const
{
// We ignore `mode` on purpose, see merge() for how we deal with it.
return slot < other.slot || (slot == other.slot && reg < other.reg);
}
void dump(PrintStream& out) const
{
out.print(pointerDump(slot), "->", reg);
switch (mode) {
case AllBits:
out.print("(AllBits)");
break;
case ZExt32:
out.print("(ZExt32)");
break;
case Match32:
out.print("(Match32)");
break;
}
}
StackSlot* slot { nullptr };
Reg reg;
Mode mode { AllBits };
};
struct SlotConst {
SlotConst()
{
}
SlotConst(StackSlot* slot, int64_t constant)
: slot(slot)
, constant(constant)
{
}
explicit operator bool() const
{
return slot;
}
bool operator==(const SlotConst& other) const
{
return slot == other.slot
&& constant == other.constant;
}
bool operator<(const SlotConst& other) const
{
return slot < other.slot || (slot == other.slot && constant < other.constant);
}
void dump(PrintStream& out) const
{
out.print(pointerDump(slot), "->", constant);
}
StackSlot* slot { nullptr };
int64_t constant { 0 };
};
struct State {
void addAlias(const RegConst& newAlias)
{
regConst.append(newAlias);
#if ASSERT_ENABLED
m_isSorted = false;
#endif
}
void addAlias(const RegSlot& newAlias)
{
regSlot.append(newAlias);
#if ASSERT_ENABLED
m_isSorted = false;
#endif
}
void addAlias(const SlotConst& newAlias)
{
slotConst.append(newAlias);
#if ASSERT_ENABLED
m_isSorted = false;
#endif
}
bool contains(const RegConst& alias)
{
return regConst.contains(alias);
}
bool contains(const RegSlot& alias)
{
return regSlot.contains(alias);
}
bool contains(const SlotConst& alias)
{
return slotConst.contains(alias);
}
const RegConst* getRegConst(Reg reg) const
{
for (const RegConst& alias : regConst) {
if (alias.reg == reg)
return &alias;
}
return nullptr;
}
const RegSlot* getRegSlot(Reg reg) const
{
for (const RegSlot& alias : regSlot) {
if (alias.reg == reg)
return &alias;
}
return nullptr;
}
const RegSlot* getRegSlot(StackSlot* slot) const
{
for (const RegSlot& alias : regSlot) {
if (alias.slot == slot)
return &alias;
}
return nullptr;
}
const RegSlot* getRegSlot(Reg reg, StackSlot* slot) const
{
for (const RegSlot& alias : regSlot) {
if (alias.reg == reg && alias.slot == slot)
return &alias;
}
return nullptr;
}
const SlotConst* getSlotConst(StackSlot* slot) const
{
for (const SlotConst& alias : slotConst) {
if (alias.slot == slot)
return &alias;
}
return nullptr;
}
std::optional<int64_t> constantFor(const Arg& arg)
{
if (arg.isReg()) {
if (const RegConst* alias = getRegConst(arg.reg()))
return alias->constant;
return std::nullopt;
}
if (arg.isStack()) {
if (const SlotConst* alias = getSlotConst(arg.stackSlot()))
return alias->constant;
return std::nullopt;
}
return std::nullopt;
}
void clobber(const Arg& arg)
{
if (arg.isReg()) {
regConst.removeAllMatching(
[&] (const RegConst& alias) -> bool {
return alias.reg == arg.reg();
});
regSlot.removeAllMatching(
[&] (const RegSlot& alias) -> bool {
return alias.reg == arg.reg();
});
return;
}
if (arg.isStack()) {
slotConst.removeAllMatching(
[&] (const SlotConst& alias) -> bool {
return alias.slot == arg.stackSlot();
});
regSlot.removeAllMatching(
[&] (const RegSlot& alias) -> bool {
return alias.slot == arg.stackSlot();
});
}
}
void sort()
{
std::sort(regConst.begin(), regConst.end(), [] (const RegConst& a, const RegConst& b) {
return a < b;
});
std::sort(slotConst.begin(), slotConst.end(), [] (const SlotConst& a, const SlotConst& b) {
return a < b;
});
std::sort(regSlot.begin(), regSlot.end(), [] (const RegSlot& a, const RegSlot& b) {
return a < b;
});
#if ASSERT_ENABLED
m_isSorted = true;
#endif
}
// Takes two sorted vectors, for each element in the first, it looks for the first element in the second which is not smaller.
// If such an element exist, call f on both the element from the first vector and this element.
// Remove the element from the first vector unless f returned true (so f says whether to keep the element)
// Returns true if any element has been removed.
template<typename T, typename Func>
static bool filterVectorAgainst(Vector<T>& own, const Vector<T>& other, Func f)
{
const T* it = other.begin();
const T* end = other.end();
return !!own.removeAllMatching(
[&] (T& alias) {
it = std::find_if_not(it, end, [&] (const T& otherAlias) {
return otherAlias < alias;
});
if (it == end)
return true;
return !f(alias, *it);
});
}
bool merge(const State& other)
{
ASSERT(m_isSorted);
ASSERT(other.m_isSorted);
bool changed = false;
changed |= filterVectorAgainst(regConst, other.regConst, [](RegConst& a, const RegConst& b) { return a == b; });
changed |= filterVectorAgainst(slotConst, other.slotConst, [](SlotConst& a, const SlotConst& b) { return a == b; });
changed |= filterVectorAgainst(regSlot, other.regSlot, [&](RegSlot& alias, const RegSlot& otherAlias) {
if (alias.reg != otherAlias.reg || alias.slot != otherAlias.slot)
return false;
if (alias.mode != RegSlot::Match32 && alias.mode != otherAlias.mode) {
alias.mode = RegSlot::Match32;
changed = true;
}
return true;
});
return changed;
}
void dump(PrintStream& out) const
{
out.print(
"{regConst = [", listDump(regConst), "], slotConst = [", listDump(slotConst),
"], regSlot = [", listDump(regSlot), "]}");
}
Vector<RegConst> regConst;
Vector<SlotConst> slotConst;
Vector<RegSlot> regSlot;
#if ASSERT_ENABLED
bool m_isSorted { true };
#endif
};
Code& m_code;
IndexMap<BasicBlock*, State> m_atHead;
State m_state;
BitVector m_notBottom;
BitVector m_shouldVisit;
BasicBlock* m_block { nullptr };
unsigned m_instIndex { 0 };
};
} // anonymous namespace
void fixObviousSpills(Code& code)
{
PhaseScope phaseScope(code, "fixObviousSpills");
FixObviousSpills fixObviousSpills(code);
fixObviousSpills.run();
}
} } } // namespace JSC::B3::Air
#endif // ENABLE(B3_JIT)