/*

* Copyright (C) 2015-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 "B3LowerToAir.h"

#if ENABLE(B3_JIT)

#include "AirBlockInsertionSet.h"

#include "AirCode.h"

#include "AirHelpers.h"

#include "AirInsertionSet.h"

#include "AirInstInlines.h"

#include "AirPrintSpecial.h"

#include "B3ArgumentRegValue.h"

#include "B3AtomicValue.h"

#include "B3BlockWorklist.h"

#include "B3CCallValue.h"

#include "B3CheckSpecial.h"

#include "B3Commutativity.h"

#include "B3Dominators.h"

#include "B3ExtractValue.h"

#include "B3FenceValue.h"

#include "B3MemoryValueInlines.h"

#include "B3PatchpointSpecial.h"

#include "B3PatchpointValue.h"

#include "B3PhaseScope.h"

#include "B3PhiChildren.h"

#include "B3Procedure.h"

#include "B3ProcedureInlines.h"

#include "B3SlotBaseValue.h"

#include "B3UpsilonValue.h"

#include "B3UseCounts.h"

#include "B3ValueInlines.h"

#include "B3Variable.h"

#include "B3VariableValue.h"

#include "B3WasmAddressValue.h"

#include <wtf/IndexMap.h>

#include <wtf/IndexSet.h>

#include <wtf/StdLibExtras.h>

#if !ASSERT_ENABLED

IGNORE_RETURN_TYPE_WARNINGS_BEGIN

#endif

namespace JSC { namespace B3 {

namespace {

namespace B3LowerToAirInternal {

static constexpr bool verbose = false;

}

using Arg = Air::Arg;

using Inst = Air::Inst;

using Code = Air::Code;

using Tmp = Air::Tmp;

using Air::moveForType;

using Air::relaxedMoveForType;

// FIXME: We wouldn't need this if Air supported Width modifiers in Air::Kind.

// https://bugs.webkit.org/show_bug.cgi?id=169247

#define OPCODE_FOR_WIDTH(opcode, width) ( \

(width) == Width8 ? Air::opcode ## 8 : \

(width) == Width16 ? Air::opcode ## 16 : \

(width) == Width32 ? Air::opcode ## 32 : \

Air::opcode ## 64)

#define OPCODE_FOR_CANONICAL_WIDTH(opcode, width) ( \

(width) == Width64 ? Air::opcode ## 64 : Air::opcode ## 32)

class LowerToAir {

public:

LowerToAir(Procedure& procedure)

: m_valueToTmp(procedure.values().size())

, m_phiToTmp(procedure.values().size())

, m_blockToBlock(procedure.size())

, m_useCounts(procedure)

, m_phiChildren(procedure)

, m_dominators(procedure.dominators())

, m_procedure(procedure)

, m_code(procedure.code())

, m_blockInsertionSet(m_code)

#if CPU(X86) || CPU(X86_64)

, m_eax(X86Registers::eax)

, m_ecx(X86Registers::ecx)

, m_edx(X86Registers::edx)

#endif

{

}

void run()

{

using namespace Air;

for (B3::BasicBlock* block : m_procedure)

m_blockToBlock[block] = m_code.addBlock(block->frequency());

auto ensureTupleTmps = [&] (Value* tupleValue, auto& hashTable) {

hashTable.ensure(tupleValue, [&] {

const auto tuple = m_procedure.tupleForType(tupleValue->type());

Vector<Tmp> tmps(tuple.size());

for (unsigned i = 0; i < tuple.size(); ++i)

tmps[i] = tmpForType(tuple[i]);

return tmps;

});

};

for (Value* value : m_procedure.values()) {

switch (value->opcode()) {

case Phi: {

if (value->type().isTuple()) {

ensureTupleTmps(value, m_tuplePhiToTmps);

ensureTupleTmps(value, m_tupleValueToTmps);

break;

}

m_phiToTmp[value] = m_code.newTmp(value->resultBank());

if (B3LowerToAirInternal::verbose)

dataLog("Phi tmp for ", *value, ": ", m_phiToTmp[value], "\n");

break;

}

case Get:

case Patchpoint:

case BottomTuple: {

if (value->type().isTuple())

ensureTupleTmps(value, m_tupleValueToTmps);

break;

}

default:

break;

}

}

for (Variable* variable : m_procedure.variables()) {

auto addResult = m_variableToTmps.add(variable, Vector<Tmp, 1>(m_procedure.resultCount(variable->type())));

ASSERT(addResult.isNewEntry);

for (unsigned i = 0; i < m_procedure.resultCount(variable->type()); ++i)

addResult.iterator->value[i] = tmpForType(m_procedure.typeAtOffset(variable->type(), i));

}

// Figure out which blocks are not rare.

m_fastWorklist.push(m_procedure[0]);

while (B3::BasicBlock* block = m_fastWorklist.pop()) {

for (B3::FrequentedBlock& successor : block->successors()) {

if (!successor.isRare())

m_fastWorklist.push(successor.block());

}

}

m_procedure.resetValueOwners(); // Used by crossesInterference().

// Lower defs before uses on a global level. This is a good heuristic to lock down a

// hoisted address expression before we duplicate it back into the loop.

for (B3::BasicBlock* block : m_procedure.blocksInPreOrder()) {

m_block = block;

m_isRare = !m_fastWorklist.saw(block);

if (B3LowerToAirInternal::verbose)

dataLog("Lowering Block ", *block, ":\n");

// Make sure that the successors are set up correctly.

for (B3::FrequentedBlock successor : block->successors()) {

m_blockToBlock[block]->successors().append(

Air::FrequentedBlock(m_blockToBlock[successor.block()], successor.frequency()));

}

// Process blocks in reverse order so we see uses before defs. That's what allows us

// to match patterns effectively.

for (unsigned i = block->size(); i--;) {

m_index = i;

m_value = block->at(i);

if (m_locked.contains(m_value))

continue;

m_insts.append(Vector<Inst>());

if (B3LowerToAirInternal::verbose)

dataLog("Lowering ", deepDump(m_procedure, m_value), ":\n");

lower();

if (B3LowerToAirInternal::verbose) {

for (Inst& inst : m_insts.last())

dataLog(" ", inst, "\n");

}

}

finishAppendingInstructions(m_blockToBlock[block]);

}

m_blockInsertionSet.execute();

Air::InsertionSet insertionSet(m_code);

for (Inst& inst : m_prologue)

insertionSet.insertInst(0, WTFMove(inst));

insertionSet.execute(m_code[0]);

}

private:

bool shouldCopyPropagate(Value* value)

{

switch (value->opcode()) {

case Trunc:

case Identity:

case Opaque:

return true;

default:

return false;

}

}

class ArgPromise {

WTF_MAKE_NONCOPYABLE(ArgPromise);

public:

ArgPromise() { }

ArgPromise(const Arg& arg, Value* valueToLock = nullptr)

: m_arg(arg)

, m_value(valueToLock)

{

}

void swap(ArgPromise& other)

{

std::swap(m_arg, other.m_arg);

std::swap(m_value, other.m_value);

std::swap(m_wasConsumed, other.m_wasConsumed);

std::swap(m_wasWrapped, other.m_wasWrapped);

std::swap(m_traps, other.m_traps);

}

ArgPromise(ArgPromise&& other)

{

swap(other);

}

ArgPromise& operator=(ArgPromise&& other)

{

swap(other);

return *this;

}

~ArgPromise()

{

if (m_wasConsumed)

RELEASE_ASSERT(m_wasWrapped);

}

void setTraps(bool value)

{

m_traps = value;

}

static ArgPromise tmp(Value* value)

{

ArgPromise result;

result.m_value = value;

return result;

}

explicit operator bool() const { return m_arg || m_value; }

Arg::Kind kind() const

{

if (!m_arg && m_value)

return Arg::Tmp;

return m_arg.kind();

}

const Arg& peek() const

{

return m_arg;

}

Arg consume(LowerToAir& lower)

{

m_wasConsumed = true;

if (!m_arg && m_value)

return lower.tmp(m_value);

if (m_value)

lower.commitInternal(m_value);

return m_arg;

}

template<typename... Args>

Inst inst(Args&&... args)

{

Inst result(std::forward<Args>(args)...);

result.kind.effects |= m_traps;

m_wasWrapped = true;

return result;

}

private:

// Three forms:

// Everything null: invalid.

// Arg non-null, value null: just use the arg, nothing special.

// Arg null, value non-null: it's a tmp, pin it when necessary.

// Arg non-null, value non-null: use the arg, lock the value.

Arg m_arg;

Value* m_value { nullptr };

bool m_wasConsumed { false };

bool m_wasWrapped { false };

bool m_traps { false };

};

// Consider using tmpPromise() in cases where you aren't sure that you want to pin the value yet.

// Here are three canonical ways of using tmp() and tmpPromise():

//

// Idiom #1: You know that you want a tmp() and you know that it will be valid for the

// instruction you're emitting.

//

// append(Foo, tmp(bar));

//

// Idiom #2: You don't know if you want to use a tmp() because you haven't determined if the

// instruction will accept it, so you query first. Note that the call to tmp() happens only after

// you are sure that you will use it.

//

// if (isValidForm(Foo, Arg::Tmp))

// append(Foo, tmp(bar))

//

// Idiom #3: Same as Idiom #2, but using tmpPromise. Notice that this calls consume() only after

// it's sure it will use the tmp. That's deliberate. Also note that you're required to pass any

// Inst you create with consumed promises through that promise's inst() function.

//

// ArgPromise promise = tmpPromise(bar);

// if (isValidForm(Foo, promise.kind()))

// append(promise.inst(Foo, promise.consume(*this)))

//

// In both idiom #2 and idiom #3, we don't pin the value to a temporary except when we actually

// emit the instruction. Both tmp() and tmpPromise().consume(*this) will pin it. Pinning means

// that we will henceforth require that the value of 'bar' is generated as a separate

// instruction. We don't want to pin the value to a temporary if we might change our minds, and

// pass an address operand representing 'bar' to Foo instead.

//

// Because tmp() pins, the following is not an idiom you should use:

//

// Tmp tmp = this->tmp(bar);

// if (isValidForm(Foo, tmp.kind()))

// append(Foo, tmp);

//

// That's because if isValidForm() returns false, you will have already pinned the 'bar' to a

// temporary. You might later want to try to do something like loadPromise(), and that will fail.

// This arises in operations that have both a Addr,Tmp and Tmp,Addr forms. The following code

// seems right, but will actually fail to ever match the Tmp,Addr form because by then, the right

// value is already pinned.

//

// auto tryThings = [this] (const Arg& left, const Arg& right) {

// if (isValidForm(Foo, left.kind(), right.kind()))

// return Inst(Foo, m_value, left, right);

// return Inst();

// };

// if (Inst result = tryThings(loadAddr(left), tmp(right)))

// return result;

// if (Inst result = tryThings(tmp(left), loadAddr(right))) // this never succeeds.

// return result;

// return Inst(Foo, m_value, tmp(left), tmp(right));

//

// If you imagine that loadAddr(value) is just loadPromise(value).consume(*this), then this code

// will run correctly - it will generate OK code - but the second form is never matched.

// loadAddr(right) will never succeed because it will observe that 'right' is already pinned.

// Of course, it's exactly because of the risky nature of such code that we don't have a

// loadAddr() helper and require you to balance ArgPromise's in code like this. Such code will

// work fine if written as:

//

// auto tryThings = [this] (ArgPromise& left, ArgPromise& right) {

// if (isValidForm(Foo, left.kind(), right.kind()))

// return left.inst(right.inst(Foo, m_value, left.consume(*this), right.consume(*this)));

// return Inst();

// };

// if (Inst result = tryThings(loadPromise(left), tmpPromise(right)))

// return result;

// if (Inst result = tryThings(tmpPromise(left), loadPromise(right)))

// return result;

// return Inst(Foo, m_value, tmp(left), tmp(right));

//

// Notice that we did use tmp in the fall-back case at the end, because by then, we know for sure

// that we want a tmp. But using tmpPromise in the tryThings() calls ensures that doing so

// doesn't prevent us from trying loadPromise on the same value.

Tmp tmp(Value* value)

{

Tmp& tmp = m_valueToTmp[value];

if (!tmp) {

while (shouldCopyPropagate(value))

value = value->child(0);

if (value->opcode() == FramePointer)

return Tmp(GPRInfo::callFrameRegister);

Tmp& realTmp = m_valueToTmp[value];

if (!realTmp) {

realTmp = m_code.newTmp(value->resultBank());

if (m_procedure.isFastConstant(value->key()))

m_code.addFastTmp(realTmp);

if (B3LowerToAirInternal::verbose)

dataLog("Tmp for ", *value, ": ", realTmp, "\n");

}

tmp = realTmp;

}

return tmp;

}

ArgPromise tmpPromise(Value* value)

{

return ArgPromise::tmp(value);

}

Tmp tmpForType(Type type)

{

return m_code.newTmp(bankForType(type));

}

const Vector<Tmp>& tmpsForTuple(Value* tupleValue)

{

ASSERT(tupleValue->type().isTuple());

switch (tupleValue->opcode()) {

case Phi:

case Patchpoint:

case BottomTuple: {

return m_tupleValueToTmps.find(tupleValue)->value;

}

case Get:

case Set:

return m_variableToTmps.find(tupleValue->as<VariableValue>()->variable())->value;

default:

break;

}

RELEASE_ASSERT_NOT_REACHED();

}

bool canBeInternal(Value* value)

{

// If one of the internal things has already been computed, then we don't want to cause

// it to be recomputed again.

if (m_valueToTmp[value])

return false;

// We require internals to have only one use - us. It's not clear if this should be numUses() or

// numUsingInstructions(). Ideally, it would be numUsingInstructions(), except that it's not clear

// if we'd actually do the right thing when matching over such a DAG pattern. For now, it simply

// doesn't matter because we don't implement patterns that would trigger this.

if (m_useCounts.numUses(value) != 1)

return false;

return true;

}

// If you ask canBeInternal() and then construct something from that, and you commit to emitting

// that code, then you must commitInternal() on that value. This is tricky, and you only need to

// do it if you're pattern matching by hand rather than using the patterns language. Long story

// short, you should avoid this by using the pattern matcher to match patterns.

void commitInternal(Value* value)

{

if (value)

m_locked.add(value);

}

bool crossesInterference(Value* value)

{

// If it's in a foreign block, then be conservative. We could handle this if we were

// willing to do heavier analysis. For example, if we had liveness, then we could label

// values as "crossing interference" if they interfere with anything that they are live

// across. But, it's not clear how useful this would be.

if (value->owner != m_value->owner)

return true;

Effects effects = value->effects();

for (unsigned i = m_index; i--;) {

Value* otherValue = m_block->at(i);

if (otherValue == value)

return false;

if (effects.interferes(otherValue->effects()))

return true;

}

ASSERT_NOT_REACHED();

return true;

}

bool isMergeableValue(Value* v, B3::Opcode b3Opcode, bool checkCanBeInternal = false)

{

if (v->opcode() != b3Opcode)

return false;

if (checkCanBeInternal && !canBeInternal(v))

return false;

if (m_locked.contains(v->child(0)))

return false;

return true;

}

template<typename Int, typename = Value::IsLegalOffset<Int>>

Arg indexArg(Tmp base, Value* index, unsigned scale, Int offset)

{

#if CPU(ARM64)

// Maybe, the ideal approach is to introduce a decorator (Index@EXT) to the Air operand

// to provide an extension opportunity for the specific form under the Air opcode.

if (isMergeableValue(index, ZExt32))

return Arg::index(base, tmp(index->child(0)), scale, offset, MacroAssembler::Extend::ZExt32);

if (isMergeableValue(index, SExt32))

return Arg::index(base, tmp(index->child(0)), scale, offset, MacroAssembler::Extend::SExt32);

#endif

return Arg::index(base, tmp(index), scale, offset);

}

template<typename Int, typename = Value::IsLegalOffset<Int>>

std::optional<unsigned> scaleForShl(Value* shl, Int offset, std::optional<Width> width = std::nullopt)

{

if (shl->opcode() != Shl)

return std::nullopt;

if (!shl->child(1)->hasInt32())

return std::nullopt;

unsigned logScale = shl->child(1)->asInt32();

if (shl->type() == Int32)

logScale &= 31;

else

logScale &= 63;

// Use 64-bit math to perform the shift so that <<32 does the right thing, but then switch

// to signed since that's what all of our APIs want.

int64_t bigScale = static_cast<uint64_t>(1) << static_cast<uint64_t>(logScale);

if (!isRepresentableAs<int32_t>(bigScale))

return std::nullopt;

unsigned scale = static_cast<int32_t>(bigScale);

if (!Arg::isValidIndexForm(scale, offset, width))

return std::nullopt;

return scale;

}

// This turns the given operand into an address.

template<typename Int, typename = Value::IsLegalOffset<Int>>

Arg effectiveAddr(Value* address, Int offset, Width width)

{

ASSERT(Arg::isValidAddrForm(offset, width));

auto fallback = [&] () -> Arg {

return Arg::addr(tmp(address), offset);

};

static constexpr unsigned lotsOfUses = 10; // This is arbitrary and we should tune it eventually.

// Only match if the address value isn't used in some large number of places.

if (m_useCounts.numUses(address) > lotsOfUses)

return fallback();

switch (address->opcode()) {

case Add: {

Value* left = address->child(0);

Value* right = address->child(1);

auto tryIndex = [&] (Value* index, Value* base) -> Arg {

std::optional<unsigned> scale = scaleForShl(index, offset, width);

if (!scale)

return Arg();

if (m_locked.contains(index->child(0)) || m_locked.contains(base))

return Arg();

return indexArg(tmp(base), index->child(0), *scale, offset);

};

if (Arg result = tryIndex(left, right))

return result;

if (Arg result = tryIndex(right, left))

return result;

if (m_locked.contains(left) || m_locked.contains(right)

|| !Arg::isValidIndexForm(1, offset, width))

return fallback();

return indexArg(tmp(left), right, 1, offset);

}

case Shl: {

Value* left = address->child(0);

// We'll never see child(1)->isInt32(0), since that would have been reduced. If the shift

// amount is greater than 1, then there isn't really anything smart that we could do here.

// We avoid using baseless indexes because their encoding isn't particularly efficient.

if (m_locked.contains(left) || !address->child(1)->isInt32(1)

|| !Arg::isValidIndexForm(1, offset, width))

return fallback();

return indexArg(tmp(left), left, 1, offset);

}

case FramePointer:

return Arg::addr(Tmp(GPRInfo::callFrameRegister), offset);

case SlotBase:

return Arg::stack(address->as<SlotBaseValue>()->slot(), offset);

case WasmAddress: {

WasmAddressValue* wasmAddress = address->as<WasmAddressValue>();

Value* pointer = wasmAddress->child(0);

if (!Arg::isValidIndexForm(1, offset, width) || m_locked.contains(pointer))

return fallback();

// FIXME: We should support ARM64 LDR 32-bit addressing, which will

// allow us to fuse a Shl ptr, 2 into the address. Additionally, and

// perhaps more importantly, it would allow us to avoid a truncating

// move. See: https://bugs.webkit.org/show_bug.cgi?id=163465

return indexArg(Tmp(wasmAddress->pinnedGPR()), pointer, 1, offset);

}

default:

return fallback();

}

}

// This gives you the address of the given Load or Store. If it's not a Load or Store, then

// it returns Arg().

Arg addr(Value* memoryValue)

{

MemoryValue* value = memoryValue->as<MemoryValue>();

if (!value)

return Arg();

if (value->requiresSimpleAddr())

return Arg::simpleAddr(tmp(value->lastChild()));

Value::OffsetType offset = value->offset();

Width width = value->accessWidth();

Arg result = effectiveAddr(value->lastChild(), offset, width);

RELEASE_ASSERT(result.isValidForm(width));

return result;

}

template<typename... Args>

Inst trappingInst(bool traps, Args&&... args)

{

Inst result(std::forward<Args>(args)...);

result.kind.effects |= traps;

return result;

}

template<typename... Args>

Inst trappingInst(Value* value, Args&&... args)

{

return trappingInst(value->traps(), std::forward<Args>(args)...);

}

ArgPromise loadPromiseAnyOpcode(Value* loadValue)

{

RELEASE_ASSERT(loadValue->as<MemoryValue>());

if (!canBeInternal(loadValue))

return Arg();

if (crossesInterference(loadValue))

return Arg();

// On x86, all loads have fences. Doing this kind of instruction selection will move the load,

// but that's fine because our interference analysis stops the motion of fences around other

// fences. So, any load motion we introduce here would not be observable.

if (!isX86() && loadValue->as<MemoryValue>()->hasFence())

return Arg();

Arg loadAddr = addr(loadValue);

RELEASE_ASSERT(loadAddr);

ArgPromise result(loadAddr, loadValue);

if (loadValue->traps())

result.setTraps(true);

return result;

}

ArgPromise loadPromise(Value* loadValue, B3::Opcode loadOpcode)

{

if (loadValue->opcode() != loadOpcode)

return Arg();

return loadPromiseAnyOpcode(loadValue);

}

ArgPromise loadPromise(Value* loadValue)

{

return loadPromise(loadValue, Load);

}

Arg imm(int64_t intValue)

{

if (Arg::isValidImmForm(intValue))

return Arg::imm(intValue);

return Arg();

}

Arg imm(Value* value)

{

if (value->hasInt())

return imm(value->asInt());

return Arg();

}

Arg bitImm(Value* value)

{

if (value->hasInt()) {

int64_t intValue = value->asInt();

if (Arg::isValidBitImmForm(intValue))

return Arg::bitImm(intValue);

}

return Arg();

}

Arg bitImm64(Value* value)

{

if (value->hasInt()) {

int64_t intValue = value->asInt();

if (Arg::isValidBitImm64Form(intValue))

return Arg::bitImm64(intValue);

}

return Arg();

}

Arg zeroReg()

{

return Arg::zeroReg();

}

Arg immOrTmp(Value* value)

{

if (Arg result = imm(value))

return result;

return tmp(value);

}

template<typename Functor>

void forEachImmOrTmp(Value* value, const Functor& func)

{

ASSERT(value->type() != Void);

if (!value->type().isTuple()) {

func(immOrTmp(value), value->type(), 0);

return;

}

const Vector<Type>& tuple = m_procedure.tupleForType(value->type());

const auto& tmps = tmpsForTuple(value);

for (unsigned i = 0; i < tuple.size(); ++i)

func(tmps[i], tuple[i], i);

}

// By convention, we use Oops to mean "I don't know".

Air::Opcode tryOpcodeForType(

Air::Opcode opcode32, Air::Opcode opcode64, Air::Opcode opcodeDouble, Air::Opcode opcodeFloat, Type type)

{

Air::Opcode opcode;

switch (type.kind()) {

case Int32:

opcode = opcode32;

break;

case Int64:

opcode = opcode64;

break;

case Float:

opcode = opcodeFloat;

break;

case Double:

opcode = opcodeDouble;

break;

default:

opcode = Air::Oops;

break;

}

return opcode;

}

Air::Opcode tryOpcodeForType(Air::Opcode opcode32, Air::Opcode opcode64, Type type)

{

return tryOpcodeForType(opcode32, opcode64, Air::Oops, Air::Oops, type);

}

Air::Opcode opcodeForType(

Air::Opcode opcode32, Air::Opcode opcode64, Air::Opcode opcodeDouble, Air::Opcode opcodeFloat, Type type)

{

Air::Opcode opcode = tryOpcodeForType(opcode32, opcode64, opcodeDouble, opcodeFloat, type);

RELEASE_ASSERT(opcode != Air::Oops);

return opcode;

}

Air::Opcode opcodeForType(Air::Opcode opcode32, Air::Opcode opcode64, Type type)

{

return tryOpcodeForType(opcode32, opcode64, Air::Oops, Air::Oops, type);

}

template<Air::Opcode opcode32, Air::Opcode opcode64, Air::Opcode opcodeDouble = Air::Oops, Air::Opcode opcodeFloat = Air::Oops>

void appendUnOp(Value* value)

{

Air::Opcode opcode = opcodeForType(opcode32, opcode64, opcodeDouble, opcodeFloat, value->type());

Tmp result = tmp(m_value);

// Two operand forms like:

// Op a, b

// mean something like:

// b = Op a

ArgPromise addr = loadPromise(value);

if (isValidForm(opcode, addr.kind(), Arg::Tmp)) {

append(addr.inst(opcode, m_value, addr.consume(*this), result));

return;

}

if (isValidForm(opcode, Arg::Tmp, Arg::Tmp)) {

append(opcode, tmp(value), result);

return;

}

ASSERT(value->type() == m_value->type());

append(relaxedMoveForType(m_value->type()), tmp(value), result);

append(opcode, result);

}

Air::Opcode opcodeBasedOnShiftKind(B3::Opcode b3Opcode,

Air::Opcode shl32, Air::Opcode shl64,

Air::Opcode sshr32, Air::Opcode sshr64,

Air::Opcode zshr32, Air::Opcode zshr64)

{

switch (b3Opcode) {

case Shl:

return tryOpcodeForType(shl32, shl64, m_value->type());

case SShr:

return tryOpcodeForType(sshr32, sshr64, m_value->type());

case ZShr:

return tryOpcodeForType(zshr32, zshr64, m_value->type());

default:

return Air::Oops;

}

}

// Call this method when doing two-operand lowering of a commutative operation. You have a choice of

// which incoming Value is moved into the result. This will select which one is likely to be most

// profitable to use as the result. Doing the right thing can have big performance consequences in tight

// kernels.

bool preferRightForResult(Value* left, Value* right)

{

// The default is to move left into result, because that's required for non-commutative instructions.

// The value that we want to move into result position is the one that dies here. So, if we're

// compiling a commutative operation and we know that actually right is the one that dies right here,

// then we can flip things around to help coalescing, which then kills the move instruction.

//

// But it's more complicated:

// - Used-once is a bad estimate of whether the variable dies here.

// - A child might be a candidate for coalescing with this value.

//

// Currently, we have machinery in place to recognize super obvious forms of the latter issue.

// We recognize when a child is a Phi that has this value as one of its children. We're very

// conservative about this; for example we don't even consider transitive Phi children.

bool leftIsPhiWithThis = m_phiChildren[left].transitivelyUses(m_value);

bool rightIsPhiWithThis = m_phiChildren[right].transitivelyUses(m_value);

if (leftIsPhiWithThis != rightIsPhiWithThis)

return rightIsPhiWithThis;

if (m_useCounts.numUsingInstructions(right) != 1)

return false;

if (m_useCounts.numUsingInstructions(left) != 1)

return true;

// The use count might be 1 if the variable is live around a loop. We can guarantee that we

// pick the variable that is least likely to suffer this problem if we pick the one that

// is closest to us in an idom walk. By convention, we slightly bias this in favor of

// returning true.

// We cannot prefer right if right is further away in an idom walk.

if (m_dominators.strictlyDominates(right->owner, left->owner))

return false;

return true;

}

template<Air::Opcode opcode32, Air::Opcode opcode64, Air::Opcode opcodeDouble, Air::Opcode opcodeFloat, Commutativity commutativity = NotCommutative>

void appendBinOp(Value* left, Value* right)

{

Air::Opcode opcode = opcodeForType(opcode32, opcode64, opcodeDouble, opcodeFloat, left->type());

Tmp result = tmp(m_value);

// Three-operand forms like:

// Op a, b, c

// mean something like:

// c = a Op b

if (isValidForm(opcode, Arg::Imm, Arg::Tmp, Arg::Tmp)) {

if (commutativity == Commutative) {

if (imm(right)) {

append(opcode, imm(right), tmp(left), result);

return;

}

} else {

// A non-commutative operation could have an immediate in left.

if (imm(left)) {

append(opcode, imm(left), tmp(right), result);

return;

}

}

}

if (isValidForm(opcode, Arg::BitImm, Arg::Tmp, Arg::Tmp)) {

if (commutativity == Commutative) {

if (Arg rightArg = bitImm(right)) {

append(opcode, rightArg, tmp(left), result);

return;

}

} else {

// A non-commutative operation could have an immediate in left.

if (Arg leftArg = bitImm(left)) {

append(opcode, leftArg, tmp(right), result);

return;

}

}

}

if (isValidForm(opcode, Arg::BitImm64, Arg::Tmp, Arg::Tmp)) {

if (commutativity == Commutative) {

if (Arg rightArg = bitImm64(right)) {

append(opcode, rightArg, tmp(left), result);

return;

}

} else {

// A non-commutative operation could have an immediate in left.

if (Arg leftArg = bitImm64(left)) {

append(opcode, leftArg, tmp(right), result);

return;

}

}

}

if (imm(right) && isValidForm(opcode, Arg::Tmp, Arg::Imm, Arg::Tmp)) {

append(opcode, tmp(left), imm(right), result);

return;

}

// Note that no extant architecture has a three-operand form of binary operations that also

// load from memory. If such an abomination did exist, we would handle it somewhere around

// here.

// Two-operand forms like:

// Op a, b

// mean something like:

// b = b Op a

// At this point, we prefer versions of the operation that have a fused load or an immediate

// over three operand forms.

if (left != right) {

ArgPromise leftAddr = loadPromise(left);

if (isValidForm(opcode, leftAddr.kind(), Arg::Tmp, Arg::Tmp)) {

append(leftAddr.inst(opcode, m_value, leftAddr.consume(*this), tmp(right), result));

return;

}

if (commutativity == Commutative) {

if (isValidForm(opcode, leftAddr.kind(), Arg::Tmp)) {

append(relaxedMoveForType(m_value->type()), tmp(right), result);

append(leftAddr.inst(opcode, m_value, leftAddr.consume(*this), result));

return;

}

}

ArgPromise rightAddr = loadPromise(right);

if (isValidForm(opcode, Arg::Tmp, rightAddr.kind(), Arg::Tmp)) {

append(rightAddr.inst(opcode, m_value, tmp(left), rightAddr.consume(*this), result));

return;

}

if (commutativity == Commutative) {

if (isValidForm(opcode, rightAddr.kind(), Arg::Tmp, Arg::Tmp)) {

append(rightAddr.inst(opcode, m_value, rightAddr.consume(*this), tmp(left), result));

return;

}

}

if (isValidForm(opcode, rightAddr.kind(), Arg::Tmp)) {

append(relaxedMoveForType(m_value->type()), tmp(left), result);

append(rightAddr.inst(opcode, m_value, rightAddr.consume(*this), result));

return;

}

}

if (imm(right) && isValidForm(opcode, Arg::Imm, Arg::Tmp)) {

append(relaxedMoveForType(m_value->type()), tmp(left), result);

append(opcode, imm(right), result);