B3ReduceStrength.cpp [plain text]
#include "config.h"
#include "B3ReduceStrength.h"
#if ENABLE(B3_JIT)
#include "B3BasicBlockInlines.h"
#include "B3BlockInsertionSet.h"
#include "B3ComputeDivisionMagic.h"
#include "B3Dominators.h"
#include "B3InsertionSetInlines.h"
#include "B3MemoryValue.h"
#include "B3PhaseScope.h"
#include "B3PhiChildren.h"
#include "B3ProcedureInlines.h"
#include "B3PureCSE.h"
#include "B3SlotBaseValue.h"
#include "B3StackSlot.h"
#include "B3UpsilonValue.h"
#include "B3ValueKeyInlines.h"
#include "B3ValueInlines.h"
#include "B3Variable.h"
#include "B3VariableValue.h"
#include <wtf/GraphNodeWorklist.h>
#include <wtf/HashMap.h>
#include <wtf/IndexSet.h>
namespace JSC { namespace B3 {
namespace {
bool verbose = false;
class IntRange {
public:
IntRange()
{
}
IntRange(int64_t min, int64_t max)
: m_min(min)
, m_max(max)
{
}
template<typename T>
static IntRange top()
{
return IntRange(std::numeric_limits<T>::min(), std::numeric_limits<T>::max());
}
static IntRange top(Type type)
{
switch (type) {
case Int32:
return top<int32_t>();
case Int64:
return top<int64_t>();
default:
RELEASE_ASSERT_NOT_REACHED();
return IntRange();
}
}
template<typename T>
static IntRange rangeForMask(T mask)
{
if (!(mask + 1))
return top<T>();
return IntRange(0, mask);
}
static IntRange rangeForMask(int64_t mask, Type type)
{
switch (type) {
case Int32:
return rangeForMask<int32_t>(static_cast<int32_t>(mask));
case Int64:
return rangeForMask<int64_t>(mask);
default:
RELEASE_ASSERT_NOT_REACHED();
return IntRange();
}
}
template<typename T>
static IntRange rangeForZShr(int32_t shiftAmount)
{
typename std::make_unsigned<T>::type mask = 0;
mask--;
mask >>= shiftAmount;
return rangeForMask<T>(static_cast<T>(mask));
}
static IntRange rangeForZShr(int32_t shiftAmount, Type type)
{
switch (type) {
case Int32:
return rangeForZShr<int32_t>(shiftAmount);
case Int64:
return rangeForZShr<int64_t>(shiftAmount);
default:
RELEASE_ASSERT_NOT_REACHED();
return IntRange();
}
}
int64_t min() const { return m_min; }
int64_t max() const { return m_max; }
void dump(PrintStream& out) const
{
out.print("[", m_min, ",", m_max, "]");
}
template<typename T>
bool couldOverflowAdd(const IntRange& other)
{
return sumOverflows<T>(m_min, other.m_min)
|| sumOverflows<T>(m_min, other.m_max)
|| sumOverflows<T>(m_max, other.m_min)
|| sumOverflows<T>(m_max, other.m_max);
}
bool couldOverflowAdd(const IntRange& other, Type type)
{
switch (type) {
case Int32:
return couldOverflowAdd<int32_t>(other);
case Int64:
return couldOverflowAdd<int64_t>(other);
default:
return true;
}
}
template<typename T>
bool couldOverflowSub(const IntRange& other)
{
return differenceOverflows<T>(m_min, other.m_min)
|| differenceOverflows<T>(m_min, other.m_max)
|| differenceOverflows<T>(m_max, other.m_min)
|| differenceOverflows<T>(m_max, other.m_max);
}
bool couldOverflowSub(const IntRange& other, Type type)
{
switch (type) {
case Int32:
return couldOverflowSub<int32_t>(other);
case Int64:
return couldOverflowSub<int64_t>(other);
default:
return true;
}
}
template<typename T>
bool couldOverflowMul(const IntRange& other)
{
return productOverflows<T>(m_min, other.m_min)
|| productOverflows<T>(m_min, other.m_max)
|| productOverflows<T>(m_max, other.m_min)
|| productOverflows<T>(m_max, other.m_max);
}
bool couldOverflowMul(const IntRange& other, Type type)
{
switch (type) {
case Int32:
return couldOverflowMul<int32_t>(other);
case Int64:
return couldOverflowMul<int64_t>(other);
default:
return true;
}
}
template<typename T>
IntRange shl(int32_t shiftAmount)
{
T newMin = static_cast<T>(m_min) << static_cast<T>(shiftAmount);
T newMax = static_cast<T>(m_max) << static_cast<T>(shiftAmount);
if ((newMin >> shiftAmount) != static_cast<T>(m_min))
newMin = std::numeric_limits<T>::min();
if ((newMax >> shiftAmount) != static_cast<T>(m_max))
newMax = std::numeric_limits<T>::max();
return IntRange(newMin, newMax);
}
IntRange shl(int32_t shiftAmount, Type type)
{
switch (type) {
case Int32:
return shl<int32_t>(shiftAmount);
case Int64:
return shl<int64_t>(shiftAmount);
default:
RELEASE_ASSERT_NOT_REACHED();
return IntRange();
}
}
template<typename T>
IntRange sShr(int32_t shiftAmount)
{
T newMin = static_cast<T>(m_min) >> static_cast<T>(shiftAmount);
T newMax = static_cast<T>(m_max) >> static_cast<T>(shiftAmount);
return IntRange(newMin, newMax);
}
IntRange sShr(int32_t shiftAmount, Type type)
{
switch (type) {
case Int32:
return sShr<int32_t>(shiftAmount);
case Int64:
return sShr<int64_t>(shiftAmount);
default:
RELEASE_ASSERT_NOT_REACHED();
return IntRange();
}
}
template<typename T>
IntRange zShr(int32_t shiftAmount)
{
if (!shiftAmount)
return *this;
if (m_min < 0)
return rangeForZShr<T>(shiftAmount);
typedef typename std::make_unsigned<T>::type UnsignedT;
UnsignedT newMin = static_cast<UnsignedT>(m_min) >> static_cast<UnsignedT>(shiftAmount);
UnsignedT newMax = static_cast<UnsignedT>(m_max) >> static_cast<UnsignedT>(shiftAmount);
return IntRange(newMin, newMax);
}
IntRange zShr(int32_t shiftAmount, Type type)
{
switch (type) {
case Int32:
return zShr<int32_t>(shiftAmount);
case Int64:
return zShr<int64_t>(shiftAmount);
default:
RELEASE_ASSERT_NOT_REACHED();
return IntRange();
}
}
template<typename T>
IntRange add(const IntRange& other)
{
if (couldOverflowAdd<T>(other))
return top<T>();
return IntRange(m_min + other.m_min, m_max + other.m_max);
}
IntRange add(const IntRange& other, Type type)
{
switch (type) {
case Int32:
return add<int32_t>(other);
case Int64:
return add<int64_t>(other);
default:
RELEASE_ASSERT_NOT_REACHED();
return IntRange();
}
}
template<typename T>
IntRange sub(const IntRange& other)
{
if (couldOverflowSub<T>(other))
return top<T>();
return IntRange(m_min - other.m_max, m_max - other.m_min);
}
IntRange sub(const IntRange& other, Type type)
{
switch (type) {
case Int32:
return sub<int32_t>(other);
case Int64:
return sub<int64_t>(other);
default:
RELEASE_ASSERT_NOT_REACHED();
return IntRange();
}
}
template<typename T>
IntRange mul(const IntRange& other)
{
if (couldOverflowMul<T>(other))
return top<T>();
return IntRange(
std::min(
std::min(m_min * other.m_min, m_min * other.m_max),
std::min(m_max * other.m_min, m_max * other.m_max)),
std::max(
std::max(m_min * other.m_min, m_min * other.m_max),
std::max(m_max * other.m_min, m_max * other.m_max)));
}
IntRange mul(const IntRange& other, Type type)
{
switch (type) {
case Int32:
return mul<int32_t>(other);
case Int64:
return mul<int64_t>(other);
default:
RELEASE_ASSERT_NOT_REACHED();
return IntRange();
}
}
private:
int64_t m_min { 0 };
int64_t m_max { 0 };
};
class ReduceStrength {
public:
ReduceStrength(Procedure& proc)
: m_proc(proc)
, m_insertionSet(proc)
, m_blockInsertionSet(proc)
{
}
bool run()
{
bool result = false;
bool first = true;
unsigned index = 0;
do {
m_changed = false;
m_changedCFG = false;
++index;
if (first)
first = false;
else if (verbose) {
dataLog("B3 after iteration #", index - 1, " of reduceStrength:\n");
dataLog(m_proc);
}
simplifyCFG();
if (m_changedCFG) {
m_proc.resetReachability();
m_proc.invalidateCFG();
m_changed = true;
}
killDeadCode();
simplifySSA();
m_proc.resetValueOwners();
m_dominators = &m_proc.dominators(); m_pureCSE.clear();
for (BasicBlock* block : m_proc.blocksInPreOrder()) {
m_block = block;
for (m_index = 0; m_index < block->size(); ++m_index) {
if (verbose) {
dataLog(
"Looking at ", *block, " #", m_index, ": ",
deepDump(m_proc, block->at(m_index)), "\n");
}
m_value = m_block->at(m_index);
m_value->performSubstitution();
reduceValueStrength();
replaceIfRedundant();
}
m_insertionSet.execute(m_block);
}
m_changedCFG |= m_blockInsertionSet.execute();
if (m_changedCFG) {
m_proc.resetReachability();
m_proc.invalidateCFG();
m_dominators = nullptr; m_changed = true;
}
result |= m_changed;
} while (m_changed);
return result;
}
private:
void reduceValueStrength()
{
switch (m_value->opcode()) {
case Add:
handleCommutativity();
if (m_value->child(0)->opcode() == Add && isInt(m_value->type())) {
Value* newSum = m_value->child(1)->addConstant(m_proc, m_value->child(0)->child(1));
if (newSum) {
m_insertionSet.insertValue(m_index, newSum);
m_value->child(0) = m_value->child(0)->child(0);
m_value->child(1) = newSum;
m_changed = true;
break;
}
if (!m_value->child(1)->hasInt() && m_value->child(0)->child(1)->hasInt()) {
Value* value = m_value->child(0)->child(0);
Value* constant = m_value->child(0)->child(1);
Value* otherValue = m_value->child(1);
m_value->child(0) =
m_insertionSet.insert<Value>(
m_index, Add, m_value->origin(), value, otherValue);
m_value->child(1) = constant;
m_changed = true;
break;
}
}
if (isInt(m_value->type())
&& !m_value->child(0)->hasInt()
&& m_value->child(1)->opcode() == Add
&& m_value->child(1)->child(1)->hasInt()) {
Value* value = m_value->child(1)->child(0);
Value* constant = m_value->child(1)->child(1);
Value* otherValue = m_value->child(0);
m_value->child(0) =
m_insertionSet.insert<Value>(
m_index, Add, m_value->origin(), value, otherValue);
m_value->child(1) = constant;
m_changed = true;
break;
}
if (Value* constantAdd = m_value->child(0)->addConstant(m_proc, m_value->child(1))) {
replaceWithNewValue(constantAdd);
break;
}
if (m_value->isInteger() && m_value->child(0) == m_value->child(1)) {
replaceWithNewValue(
m_proc.add<Value>(
Shl, m_value->origin(), m_value->child(0),
m_insertionSet.insert<Const32Value>(m_index, m_value->origin(), 1)));
break;
}
if (m_value->child(1)->isInt(0) || m_value->child(1)->isNegativeZero()) {
replaceWithIdentity(m_value->child(0));
break;
}
if (m_value->isInteger()
&& m_value->child(0)->opcode() == Sub
&& m_value->child(1)->isInt(-1)
&& m_value->child(0)->child(0)->isInt(0)) {
replaceWithNewValue(m_proc.add<Value>(BitXor, m_value->origin(), m_value->child(0)->child(1), m_value->child(1)));
break;
}
break;
case Sub:
if (Value* constantSub = m_value->child(0)->subConstant(m_proc, m_value->child(1))) {
replaceWithNewValue(constantSub);
break;
}
if (isInt(m_value->type())) {
if (Value* negatedConstant = m_value->child(1)->negConstant(m_proc)) {
m_insertionSet.insertValue(m_index, negatedConstant);
replaceWithNew<Value>(
Add, m_value->origin(), m_value->child(0), negatedConstant);
break;
}
if (m_value->child(0)->isInt(0)) {
replaceWithNew<Value>(Neg, m_value->origin(), m_value->child(1));
break;
}
}
break;
case Neg:
if (Value* constant = m_value->child(0)->negConstant(m_proc)) {
replaceWithNewValue(constant);
break;
}
if (m_value->child(0)->opcode() == Neg) {
replaceWithIdentity(m_value->child(0)->child(0));
break;
}
break;
case Mul:
handleCommutativity();
if (Value* value = m_value->child(0)->mulConstant(m_proc, m_value->child(1))) {
replaceWithNewValue(value);
break;
}
if (m_value->child(1)->hasInt()) {
int64_t factor = m_value->child(1)->asInt();
if (!factor) {
replaceWithIdentity(m_value->child(1));
break;
}
if (factor == 1) {
replaceWithIdentity(m_value->child(0));
break;
}
if (factor == -1) {
replaceWithNewValue(
m_proc.add<Value>(
Sub, m_value->origin(),
m_insertionSet.insertIntConstant(m_index, m_value, 0),
m_value->child(0)));
break;
}
if (hasOneBitSet(factor)) {
unsigned shiftAmount = WTF::fastLog2(static_cast<uint64_t>(factor));
replaceWithNewValue(
m_proc.add<Value>(
Shl, m_value->origin(), m_value->child(0),
m_insertionSet.insert<Const32Value>(
m_index, m_value->origin(), shiftAmount)));
break;
}
} else if (m_value->child(1)->hasDouble()) {
double factor = m_value->child(1)->asDouble();
if (factor == 1) {
replaceWithIdentity(m_value->child(0));
break;
}
}
break;
case Div:
if (replaceWithNewValue(m_value->child(0)->divConstant(m_proc, m_value->child(1))))
break;
if (m_value->child(1)->hasInt()) {
switch (m_value->child(1)->asInt()) {
case -1:
replaceWithNewValue(
m_proc.add<Value>(Neg, m_value->origin(), m_value->child(0)));
break;
case 0:
replaceWithIdentity(m_value->child(1));
break;
case 1:
replaceWithIdentity(m_value->child(0));
break;
default:
if (m_value->type() != Int32)
break;
int32_t divisor = m_value->child(1)->asInt32();
DivisionMagic<int32_t> magic = computeDivisionMagic(divisor);
Value* magicQuotient = m_insertionSet.insert<Value>(
m_index, Trunc, m_value->origin(),
m_insertionSet.insert<Value>(
m_index, ZShr, m_value->origin(),
m_insertionSet.insert<Value>(
m_index, Mul, m_value->origin(),
m_insertionSet.insert<Value>(
m_index, SExt32, m_value->origin(), m_value->child(0)),
m_insertionSet.insert<Const64Value>(
m_index, m_value->origin(), magic.magicMultiplier)),
m_insertionSet.insert<Const32Value>(
m_index, m_value->origin(), 32)));
if (divisor > 0 && magic.magicMultiplier < 0) {
magicQuotient = m_insertionSet.insert<Value>(
m_index, Add, m_value->origin(), magicQuotient, m_value->child(0));
}
if (divisor < 0 && magic.magicMultiplier > 0) {
magicQuotient = m_insertionSet.insert<Value>(
m_index, Sub, m_value->origin(), magicQuotient, m_value->child(0));
}
if (magic.shift > 0) {
magicQuotient = m_insertionSet.insert<Value>(
m_index, SShr, m_value->origin(), magicQuotient,
m_insertionSet.insert<Const32Value>(
m_index, m_value->origin(), magic.shift));
}
replaceWithIdentity(
m_insertionSet.insert<Value>(
m_index, Add, m_value->origin(), magicQuotient,
m_insertionSet.insert<Value>(
m_index, ZShr, m_value->origin(), magicQuotient,
m_insertionSet.insert<Const32Value>(
m_index, m_value->origin(), 31))));
break;
}
break;
}
break;
case UDiv:
if (replaceWithNewValue(m_value->child(0)->uDivConstant(m_proc, m_value->child(1))))
break;
if (m_value->child(1)->hasInt()) {
switch (m_value->child(1)->asInt()) {
case 0:
replaceWithIdentity(m_value->child(1));
break;
case 1:
replaceWithIdentity(m_value->child(0));
break;
default:
break;
}
}
break;
case Mod:
if (replaceWithNewValue(m_value->child(0)->modConstant(m_proc, m_value->child(1))))
break;
if (m_value->child(1)->hasInt()) {
switch (m_value->child(1)->asInt()) {
case 0:
replaceWithIdentity(m_value->child(1));
break;
default:
Kind divKind = Div;
divKind.setIsChill(m_value->isChill());
replaceWithIdentity(
m_insertionSet.insert<Value>(
m_index, Sub, m_value->origin(),
m_value->child(0),
m_insertionSet.insert<Value>(
m_index, Mul, m_value->origin(),
m_insertionSet.insert<Value>(
m_index, divKind, m_value->origin(),
m_value->child(0), m_value->child(1)),
m_value->child(1))));
break;
}
break;
}
break;
case UMod:
replaceWithNewValue(m_value->child(0)->uModConstant(m_proc, m_value->child(1)));
break;
case BitAnd:
handleCommutativity();
if (Value* constantBitAnd = m_value->child(0)->bitAndConstant(m_proc, m_value->child(1))) {
replaceWithNewValue(constantBitAnd);
break;
}
if (m_value->child(0)->opcode() == BitAnd) {
Value* newConstant = m_value->child(1)->bitAndConstant(m_proc, m_value->child(0)->child(1));
if (newConstant) {
m_insertionSet.insertValue(m_index, newConstant);
m_value->child(0) = m_value->child(0)->child(0);
m_value->child(1) = newConstant;
m_changed = true;
}
}
if (m_value->child(0) == m_value->child(1)) {
replaceWithIdentity(m_value->child(0));
break;
}
if (m_value->child(1)->isInt(0)) {
replaceWithIdentity(m_value->child(1));
break;
}
if ((m_value->type() == Int64 && m_value->child(1)->isInt(0xffffffffffffffff))
|| (m_value->type() == Int32 && m_value->child(1)->isInt(0xffffffff))) {
replaceWithIdentity(m_value->child(0));
break;
}
if (m_value->child(1)->isInt64(0xffffffffllu)) {
Value* newValue = m_insertionSet.insert<Value>(
m_index, ZExt32, m_value->origin(),
m_insertionSet.insert<Value>(m_index, Trunc, m_value->origin(), m_value->child(0)));
replaceWithIdentity(newValue);
break;
}
if (m_value->child(0)->opcode() == SExt8 && m_value->child(1)->hasInt32()
&& !(m_value->child(1)->asInt32() & 0xffffff00)) {
m_value->child(0) = m_value->child(0)->child(0);
m_changed = true;
}
if (m_value->child(0)->opcode() == SExt16 && m_value->child(1)->hasInt32()
&& !(m_value->child(1)->asInt32() & 0xffff0000)) {
m_value->child(0) = m_value->child(0)->child(0);
m_changed = true;
}
if (m_value->child(0)->opcode() == SExt32 && m_value->child(1)->hasInt32()
&& !(m_value->child(1)->asInt32() & 0xffffffff00000000llu)) {
m_value->child(0) = m_insertionSet.insert<Value>(
m_index, ZExt32, m_value->origin(),
m_value->child(0)->child(0), m_value->child(0)->child(1));
m_changed = true;
}
if (m_value->child(1)->hasInt()) {
int64_t constant2 = m_value->child(1)->asInt();
switch (m_value->child(0)->opcode()) {
case BitOr:
case BitXor:
if (m_value->child(0)->child(1)->hasInt()
&& !(m_value->child(0)->child(1)->asInt() & constant2)) {
m_value->child(0) = m_value->child(0)->child(0);
m_changed = true;
break;
}
break;
default:
break;
}
}
break;
case BitOr:
handleCommutativity();
if (Value* constantBitOr = m_value->child(0)->bitOrConstant(m_proc, m_value->child(1))) {
replaceWithNewValue(constantBitOr);
break;
}
if (m_value->child(0)->opcode() == BitOr) {
Value* newConstant = m_value->child(1)->bitOrConstant(m_proc, m_value->child(0)->child(1));
if (newConstant) {
m_insertionSet.insertValue(m_index, newConstant);
m_value->child(0) = m_value->child(0)->child(0);
m_value->child(1) = newConstant;
m_changed = true;
}
}
if (m_value->child(0) == m_value->child(1)) {
replaceWithIdentity(m_value->child(0));
break;
}
if (m_value->child(1)->isInt(0)) {
replaceWithIdentity(m_value->child(0));
break;
}
if ((m_value->type() == Int64 && m_value->child(1)->isInt(0xffffffffffffffff))
|| (m_value->type() == Int32 && m_value->child(1)->isInt(0xffffffff))) {
replaceWithIdentity(m_value->child(1));
break;
}
break;
case BitXor:
handleCommutativity();
if (Value* constantBitXor = m_value->child(0)->bitXorConstant(m_proc, m_value->child(1))) {
replaceWithNewValue(constantBitXor);
break;
}
if (m_value->child(0)->opcode() == BitXor) {
Value* newConstant = m_value->child(1)->bitXorConstant(m_proc, m_value->child(0)->child(1));
if (newConstant) {
m_insertionSet.insertValue(m_index, newConstant);
m_value->child(0) = m_value->child(0)->child(0);
m_value->child(1) = newConstant;
m_changed = true;
}
}
if (m_value->child(1)->isInt32(1)) {
if (Value* invertedCompare = m_value->child(0)->invertedCompare(m_proc)) {
replaceWithNewValue(invertedCompare);
break;
}
}
if (m_value->child(0) == m_value->child(1)) {
replaceWithNewValue(m_proc.addIntConstant(m_value, 0));
break;
}
if (m_value->child(1)->isInt(0)) {
replaceWithIdentity(m_value->child(0));
break;
}
break;
case Shl:
if (Value* constant = m_value->child(0)->shlConstant(m_proc, m_value->child(1))) {
replaceWithNewValue(constant);
break;
}
handleShiftAmount();
break;
case SShr:
if (Value* constant = m_value->child(0)->sShrConstant(m_proc, m_value->child(1))) {
replaceWithNewValue(constant);
break;
}
if (m_value->child(1)->hasInt32()
&& m_value->child(0)->opcode() == Shl
&& m_value->child(0)->child(1)->hasInt32()
&& m_value->child(1)->asInt32() == m_value->child(0)->child(1)->asInt32()) {
switch (m_value->child(1)->asInt32()) {
case 16:
if (m_value->type() == Int32) {
replaceWithNewValue(
m_proc.add<Value>(
SExt16, m_value->origin(), m_value->child(0)->child(0)));
}
break;
case 24:
if (m_value->type() == Int32) {
replaceWithNewValue(
m_proc.add<Value>(
SExt8, m_value->origin(), m_value->child(0)->child(0)));
}
break;
case 32:
if (m_value->type() == Int64) {
replaceWithNewValue(
m_proc.add<Value>(
SExt32, m_value->origin(),
m_insertionSet.insert<Value>(
m_index, Trunc, m_value->origin(),
m_value->child(0)->child(0))));
}
break;
default:
break;
}
if (m_value->opcode() != SShr)
break;
}
handleShiftAmount();
break;
case ZShr:
if (Value* constant = m_value->child(0)->zShrConstant(m_proc, m_value->child(1))) {
replaceWithNewValue(constant);
break;
}
handleShiftAmount();
break;
case RotR:
if (Value* constant = m_value->child(0)->rotRConstant(m_proc, m_value->child(1))) {
replaceWithNewValue(constant);
break;
}
handleShiftAmount();
break;
case RotL:
if (Value* constant = m_value->child(0)->rotLConstant(m_proc, m_value->child(1))) {
replaceWithNewValue(constant);
break;
}
handleShiftAmount();
break;
case Abs:
if (Value* constant = m_value->child(0)->absConstant(m_proc)) {
replaceWithNewValue(constant);
break;
}
if (m_value->child(0)->opcode() == Abs) {
replaceWithIdentity(m_value->child(0));
break;
}
if (m_value->child(0)->opcode() == BitwiseCast) {
Value* mask;
if (m_value->type() == Double)
mask = m_insertionSet.insert<Const64Value>(m_index, m_value->origin(), ~(1ll << 63));
else
mask = m_insertionSet.insert<Const32Value>(m_index, m_value->origin(), ~(1l << 31));
Value* bitAnd = m_insertionSet.insert<Value>(m_index, BitAnd, m_value->origin(),
m_value->child(0)->child(0),
mask);
Value* cast = m_insertionSet.insert<Value>(m_index, BitwiseCast, m_value->origin(), bitAnd);
replaceWithIdentity(cast);
break;
}
break;
case Ceil:
if (Value* constant = m_value->child(0)->ceilConstant(m_proc)) {
replaceWithNewValue(constant);
break;
}
if (m_value->child(0)->isRounded()) {
replaceWithIdentity(m_value->child(0));
break;
}
break;
case Floor:
if (Value* constant = m_value->child(0)->floorConstant(m_proc)) {
replaceWithNewValue(constant);
break;
}
if (m_value->child(0)->isRounded()) {
replaceWithIdentity(m_value->child(0));
break;
}
break;
case Sqrt:
if (Value* constant = m_value->child(0)->sqrtConstant(m_proc)) {
replaceWithNewValue(constant);
break;
}
break;
case BitwiseCast:
if (Value* constant = m_value->child(0)->bitwiseCastConstant(m_proc)) {
replaceWithNewValue(constant);
break;
}
if (m_value->child(0)->opcode() == BitwiseCast) {
replaceWithIdentity(m_value->child(0)->child(0));
break;
}
break;
case SExt8:
if (m_value->child(0)->hasInt32()) {
int32_t result = static_cast<int8_t>(m_value->child(0)->asInt32());
replaceWithNewValue(m_proc.addIntConstant(m_value, result));
break;
}
if (m_value->child(0)->opcode() == SExt8 || m_value->child(0)->opcode() == SExt16) {
m_value->child(0) = m_value->child(0)->child(0);
m_changed = true;
}
if (m_value->child(0)->opcode() == BitAnd && m_value->child(0)->child(1)->hasInt32()) {
Value* input = m_value->child(0)->child(0);
int32_t mask = m_value->child(0)->child(1)->asInt32();
if ((mask & 0xff) == 0xff) {
m_value->child(0) = input;
m_changed = true;
break;
}
if (!(mask & 0x80)) {
replaceWithNewValue(
m_proc.add<Value>(
BitAnd, m_value->origin(), input,
m_insertionSet.insert<Const32Value>(
m_index, m_value->origin(), mask & 0x7f)));
break;
}
}
break;
case SExt16:
if (m_value->child(0)->hasInt32()) {
int32_t result = static_cast<int16_t>(m_value->child(0)->asInt32());
replaceWithNewValue(m_proc.addIntConstant(m_value, result));
break;
}
if (m_value->child(0)->opcode() == SExt16) {
m_value->child(0) = m_value->child(0)->child(0);
m_changed = true;
}
if (m_value->child(0)->opcode() == SExt8) {
replaceWithIdentity(m_value->child(0));
break;
}
if (m_value->child(0)->opcode() == BitAnd && m_value->child(0)->child(1)->hasInt32()) {
Value* input = m_value->child(0)->child(0);
int32_t mask = m_value->child(0)->child(1)->asInt32();
if ((mask & 0xffff) == 0xffff) {
m_value->child(0) = input;
m_changed = true;
break;
}
if (!(mask & 0x8000)) {
replaceWithNewValue(
m_proc.add<Value>(
BitAnd, m_value->origin(), input,
m_insertionSet.insert<Const32Value>(
m_index, m_value->origin(), mask & 0x7fff)));
break;
}
}
break;
case SExt32:
if (m_value->child(0)->hasInt32()) {
replaceWithNewValue(m_proc.addIntConstant(m_value, m_value->child(0)->asInt32()));
break;
}
if (m_value->child(0)->opcode() == BitAnd && m_value->child(0)->child(1)->hasInt32()
&& !(m_value->child(0)->child(1)->asInt32() & 0x80000000)) {
replaceWithNewValue(
m_proc.add<Value>(
ZExt32, m_value->origin(), m_value->child(0)));
break;
}
break;
case ZExt32:
if (m_value->child(0)->hasInt32()) {
replaceWithNewValue(
m_proc.addIntConstant(
m_value,
static_cast<uint64_t>(static_cast<uint32_t>(m_value->child(0)->asInt32()))));
break;
}
break;
case Trunc:
if (m_value->child(0)->hasInt64() || m_value->child(0)->hasDouble()) {
replaceWithNewValue(
m_proc.addIntConstant(m_value, static_cast<int32_t>(m_value->child(0)->asInt64())));
break;
}
if (m_value->child(0)->opcode() == SExt32 || m_value->child(0)->opcode() == ZExt32) {
replaceWithIdentity(m_value->child(0)->child(0));
break;
}
switch (m_value->child(0)->opcode()) {
case Add:
case Sub:
case BitOr:
case BitXor:
if (m_value->child(0)->child(1)->hasInt64()
&& !(m_value->child(0)->child(1)->asInt64() & 0xffffffffll)) {
m_value->child(0) = m_value->child(0)->child(0);
m_changed = true;
break;
}
break;
default:
break;
}
break;
case IToD:
if (Value* constant = m_value->child(0)->iToDConstant(m_proc)) {
replaceWithNewValue(constant);
break;
}
break;
case IToF:
if (Value* constant = m_value->child(0)->iToFConstant(m_proc)) {
replaceWithNewValue(constant);
break;
}
break;
case FloatToDouble:
if (Value* constant = m_value->child(0)->floatToDoubleConstant(m_proc)) {
replaceWithNewValue(constant);
break;
}
break;
case DoubleToFloat:
if (m_value->child(0)->opcode() == FloatToDouble) {
replaceWithIdentity(m_value->child(0)->child(0));
break;
}
if (Value* constant = m_value->child(0)->doubleToFloatConstant(m_proc)) {
replaceWithNewValue(constant);
break;
}
break;
case Select:
if (m_value->child(0)->hasInt32()) {
replaceWithIdentity(
m_value->child(0)->asInt32() ? m_value->child(1) : m_value->child(2));
break;
}
if (m_value->child(0)->opcode() == Equal && m_value->child(0)->child(1)->isInt(0)) {
m_value->child(0) = m_value->child(0)->child(0);
std::swap(m_value->child(1), m_value->child(2));
m_changed = true;
break;
}
if (m_value->child(0)->opcode() == BitXor
&& m_value->child(0)->child(1)->isInt32(1)
&& m_value->child(0)->child(0)->returnsBool()) {
m_value->child(0) = m_value->child(0)->child(0);
std::swap(m_value->child(1), m_value->child(2));
m_changed = true;
break;
}
if (m_value->child(0)->opcode() == BitAnd
&& m_value->child(0)->child(1)->hasInt()
&& m_value->child(0)->child(1)->asInt() & 1
&& m_value->child(0)->child(0)->returnsBool()) {
m_value->child(0) = m_value->child(0)->child(0);
m_changed = true;
break;
}
if (m_value->child(1) == m_value->child(2)) {
replaceWithIdentity(m_value->child(1));
break;
}
break;
case Load8Z:
case Load8S:
case Load16Z:
case Load16S:
case Load:
case Store8:
case Store16:
case Store: {
Value* address = m_value->lastChild();
MemoryValue* memory = m_value->as<MemoryValue>();
if (address->opcode() == Add && address->child(1)->hasIntPtr()) {
intptr_t offset = address->child(1)->asIntPtr();
if (!sumOverflows<intptr_t>(offset, memory->offset())) {
offset += memory->offset();
int32_t smallOffset = static_cast<int32_t>(offset);
if (smallOffset == offset) {
address = address->child(0);
memory->lastChild() = address;
memory->setOffset(smallOffset);
m_changed = true;
}
}
}
if (memory->offset()) {
if (Value* newAddress = address->addConstant(m_proc, memory->offset())) {
m_insertionSet.insertValue(m_index, newAddress);
address = newAddress;
memory->lastChild() = newAddress;
memory->setOffset(0);
m_changed = true;
}
}
break;
}
case CCall: {
double(*fmodDouble)(double, double) = fmod;
if (m_value->type() == Double
&& m_value->numChildren() == 3
&& m_value->child(0)->isIntPtr(reinterpret_cast<intptr_t>(fmodDouble))
&& m_value->child(1)->type() == Double
&& m_value->child(2)->type() == Double) {
replaceWithNewValue(m_value->child(1)->modConstant(m_proc, m_value->child(2)));
}
break;
}
case Equal:
handleCommutativity();
if (m_value->child(0)->returnsBool() && m_value->child(1)->isInt32(0)) {
replaceWithNew<Value>(
BitXor, m_value->origin(), m_value->child(0),
m_insertionSet.insert<Const32Value>(m_index, m_value->origin(), 1));
break;
}
if (m_value->child(0)->returnsBool() && m_value->child(1)->isInt32(1)) {
replaceWithIdentity(m_value->child(0));
break;
}
replaceWithNewValue(
m_proc.addBoolConstant(
m_value->origin(),
m_value->child(0)->equalConstant(m_value->child(1))));
break;
case NotEqual:
handleCommutativity();
if (m_value->child(0)->returnsBool()) {
if (m_value->child(1)->isInt32(0)) {
replaceWithIdentity(m_value->child(0));
break;
}
if (m_value->child(1)->isInt32(1)) {
replaceWithNew<Value>(
Equal, m_value->origin(), m_value->child(0),
m_insertionSet.insertIntConstant(m_index, m_value->origin(), Int32, 0));
break;
}
}
replaceWithNewValue(
m_proc.addBoolConstant(
m_value->origin(),
m_value->child(0)->notEqualConstant(m_value->child(1))));
break;
case LessThan:
replaceWithNewValue(
m_proc.addBoolConstant(
m_value->origin(),
m_value->child(0)->lessThanConstant(m_value->child(1))));
break;
case GreaterThan:
replaceWithNewValue(
m_proc.addBoolConstant(
m_value->origin(),
m_value->child(0)->greaterThanConstant(m_value->child(1))));
break;
case LessEqual:
replaceWithNewValue(
m_proc.addBoolConstant(
m_value->origin(),
m_value->child(0)->lessEqualConstant(m_value->child(1))));
break;
case GreaterEqual:
replaceWithNewValue(
m_proc.addBoolConstant(
m_value->origin(),
m_value->child(0)->greaterEqualConstant(m_value->child(1))));
break;
case Above:
replaceWithNewValue(
m_proc.addBoolConstant(
m_value->origin(),
m_value->child(0)->aboveConstant(m_value->child(1))));
break;
case Below:
replaceWithNewValue(
m_proc.addBoolConstant(
m_value->origin(),
m_value->child(0)->belowConstant(m_value->child(1))));
break;
case AboveEqual:
replaceWithNewValue(
m_proc.addBoolConstant(
m_value->origin(),
m_value->child(0)->aboveEqualConstant(m_value->child(1))));
break;
case BelowEqual:
replaceWithNewValue(
m_proc.addBoolConstant(
m_value->origin(),
m_value->child(0)->belowEqualConstant(m_value->child(1))));
break;
case EqualOrUnordered:
handleCommutativity();
replaceWithNewValue(
m_proc.addBoolConstant(
m_value->origin(),
m_value->child(1)->equalOrUnorderedConstant(m_value->child(0))));
break;
case CheckAdd: {
if (replaceWithNewValue(m_value->child(0)->checkAddConstant(m_proc, m_value->child(1))))
break;
handleCommutativity();
if (m_value->child(1)->isInt(0)) {
replaceWithIdentity(m_value->child(0));
break;
}
IntRange leftRange = rangeFor(m_value->child(0));
IntRange rightRange = rangeFor(m_value->child(1));
if (!leftRange.couldOverflowAdd(rightRange, m_value->type())) {
replaceWithNewValue(
m_proc.add<Value>(Add, m_value->origin(), m_value->child(0), m_value->child(1)));
break;
}
break;
}
case CheckSub: {
if (replaceWithNewValue(m_value->child(0)->checkSubConstant(m_proc, m_value->child(1))))
break;
if (m_value->child(1)->isInt(0)) {
replaceWithIdentity(m_value->child(0));
break;
}
if (Value* negatedConstant = m_value->child(1)->checkNegConstant(m_proc)) {
m_insertionSet.insertValue(m_index, negatedConstant);
m_value->as<CheckValue>()->convertToAdd();
m_value->child(1) = negatedConstant;
m_changed = true;
break;
}
IntRange leftRange = rangeFor(m_value->child(0));
IntRange rightRange = rangeFor(m_value->child(1));
if (!leftRange.couldOverflowSub(rightRange, m_value->type())) {
replaceWithNewValue(
m_proc.add<Value>(Sub, m_value->origin(), m_value->child(0), m_value->child(1)));
break;
}
break;
}
case CheckMul: {
if (replaceWithNewValue(m_value->child(0)->checkMulConstant(m_proc, m_value->child(1))))
break;
handleCommutativity();
if (m_value->child(1)->hasInt()) {
bool modified = true;
switch (m_value->child(1)->asInt()) {
case 0:
replaceWithNewValue(m_proc.addIntConstant(m_value, 0));
break;
case 1:
replaceWithIdentity(m_value->child(0));
break;
case 2:
m_value->as<CheckValue>()->convertToAdd();
m_value->child(1) = m_value->child(0);
m_changed = true;
break;
default:
modified = false;
break;
}
if (modified)
break;
}
IntRange leftRange = rangeFor(m_value->child(0));
IntRange rightRange = rangeFor(m_value->child(1));
if (!leftRange.couldOverflowMul(rightRange, m_value->type())) {
replaceWithNewValue(
m_proc.add<Value>(Mul, m_value->origin(), m_value->child(0), m_value->child(1)));
break;
}
break;
}
case Check: {
CheckValue* checkValue = m_value->as<CheckValue>();
if (checkValue->child(0)->isLikeZero()) {
checkValue->replaceWithNop();
m_changed = true;
break;
}
if (checkValue->child(0)->isLikeNonZero()) {
PatchpointValue* patchpoint =
m_insertionSet.insert<PatchpointValue>(m_index, Void, checkValue->origin());
patchpoint->effects = Effects();
patchpoint->effects.reads = HeapRange::top();
patchpoint->effects.exitsSideways = true;
for (unsigned i = 1; i < checkValue->numChildren(); ++i)
patchpoint->append(checkValue->constrainedChild(i));
patchpoint->setGenerator(checkValue->generator());
for (unsigned i = m_index + 1; i < m_block->size() - 1; ++i)
m_block->at(i)->replaceWithBottom(m_insertionSet, m_index);
m_block->last()->replaceWithOops(m_block);
m_block->last()->setOrigin(checkValue->origin());
checkValue->replaceWithNop();
m_changedCFG = true;
break;
}
if (checkValue->child(0)->opcode() == NotEqual
&& checkValue->child(0)->child(1)->isInt(0)) {
checkValue->child(0) = checkValue->child(0)->child(0);
m_changed = true;
}
static const unsigned selectSpecializationBound = 3;
Value* select = findRecentNodeMatching(
m_value->child(0), selectSpecializationBound,
[&] (Value* value) -> bool {
return value->opcode() == Select
&& (value->child(1)->isConstant() && value->child(2)->isConstant());
});
if (select) {
specializeSelect(select);
break;
}
break;
}
case Branch: {
if (m_value->child(0)->opcode() == NotEqual && m_value->child(0)->child(1)->isInt(0)) {
m_value->child(0) = m_value->child(0)->child(0);
m_changed = true;
}
if (m_value->child(0)->opcode() == Equal && m_value->child(0)->child(1)->isInt(0)) {
m_value->child(0) = m_value->child(0)->child(0);
std::swap(m_block->taken(), m_block->notTaken());
m_changed = true;
}
if (m_value->child(0)->opcode() == BitXor
&& m_value->child(0)->child(1)->isInt32(1)
&& m_value->child(0)->child(0)->returnsBool()) {
m_value->child(0) = m_value->child(0)->child(0);
std::swap(m_block->taken(), m_block->notTaken());
m_changed = true;
}
if (m_value->child(0)->opcode() == BitAnd
&& m_value->child(0)->child(1)->hasInt()
&& m_value->child(0)->child(1)->asInt() & 1
&& m_value->child(0)->child(0)->returnsBool()) {
m_value->child(0) = m_value->child(0)->child(0);
m_changed = true;
}
TriState triState = m_value->child(0)->asTriState();
if (triState == FalseTriState) {
m_block->taken().block()->removePredecessor(m_block);
m_value->replaceWithJump(m_block, m_block->notTaken());
m_changedCFG = true;
break;
}
if (triState == TrueTriState) {
m_block->notTaken().block()->removePredecessor(m_block);
m_value->replaceWithJump(m_block, m_block->taken());
m_changedCFG = true;
break;
}
Value* check = m_pureCSE.findMatch(
ValueKey(Check, Void, m_value->child(0)), m_block, *m_dominators);
if (check) {
m_block->taken().block()->removePredecessor(m_block);
m_value->replaceWithJump(m_block, m_block->notTaken());
m_changedCFG = true;
}
break;
}
default:
break;
}
}
template<typename Functor>
Value* findRecentNodeMatching(Value* start, unsigned bound, const Functor& functor)
{
unsigned startIndex = bound < m_index ? m_index - bound : 0;
Value* result = nullptr;
start->walk(
[&] (Value* value) -> Value::WalkStatus {
bool found = false;
for (unsigned i = startIndex; i <= m_index; ++i) {
if (m_block->at(i) == value)
found = true;
}
if (!found)
return Value::IgnoreChildren;
if (functor(value)) {
result = value;
return Value::Stop;
}
return Value::Continue;
});
return result;
}
void specializeSelect(Value* source)
{
if (verbose)
dataLog("Specializing select: ", deepDump(m_proc, source), "\n");
BasicBlock* predecessor =
m_blockInsertionSet.splitForward(m_block, m_index, &m_insertionSet);
unsigned startIndex = UINT_MAX;
for (unsigned i = predecessor->size(); i--;) {
if (predecessor->at(i) == source) {
startIndex = i;
break;
}
}
RELEASE_ASSERT(startIndex != UINT_MAX);
static const unsigned numCases = 2;
BasicBlock* cases[numCases];
for (unsigned i = 0; i < numCases; ++i)
cases[i] = m_blockInsertionSet.insertBefore(m_block);
HashMap<Value*, Value*> mappings[2];
Value* predicate = source->child(0);
for (unsigned i = 0; i < numCases; ++i)
mappings[i].add(source, source->child(1 + i));
auto cloneValue = [&] (Value* value) {
ASSERT(value != source);
for (unsigned i = 0; i < numCases; ++i) {
Value* clone = m_proc.clone(value);
for (Value*& child : clone->children()) {
if (Value* newChild = mappings[i].get(child))
child = newChild;
}
if (value->type() != Void)
mappings[i].add(value, clone);
cases[i]->append(clone);
if (value->type() != Void)
cases[i]->appendNew<UpsilonValue>(m_proc, value->origin(), clone, value);
}
value->replaceWithPhi();
};
predecessor->removeLast(m_proc);
for (unsigned i = 0; i < numCases; ++i) {
cases[i]->appendNew<UpsilonValue>(
m_proc, source->origin(), source->child(1 + i), source);
}
source->replaceWithPhi();
m_insertionSet.insertValue(m_index, source);
for (unsigned i = startIndex + 1; i < predecessor->size(); ++i) {
Value* value = predecessor->at(i);
value->owner = nullptr;
cloneValue(value);
if (value->type() != Void)
m_insertionSet.insertValue(m_index, value);
else
m_proc.deleteValue(value);
}
cloneValue(m_value);
predecessor->values().resize(startIndex);
predecessor->appendNew<Value>(m_proc, Branch, source->origin(), predicate);
predecessor->setSuccessors(FrequentedBlock(cases[0]), FrequentedBlock(cases[1]));
for (unsigned i = 0; i < numCases; ++i) {
cases[i]->appendNew<Value>(m_proc, Jump, m_value->origin());
cases[i]->setSuccessors(FrequentedBlock(m_block));
}
m_changed = true;
predecessor->updatePredecessorsAfter();
}
void handleCommutativity()
{
ASSERT(m_value->numChildren() >= 2);
if (m_value->child(1)->isConstant())
return;
if (m_value->child(0)->isConstant()) {
std::swap(m_value->child(0), m_value->child(1));
m_changed = true;
return;
}
if (m_value->child(0)->index() > m_value->child(1)->index()) {
std::swap(m_value->child(0), m_value->child(1));
m_changed = true;
return;
}
}
IntRange rangeFor(Value* value, unsigned timeToLive = 5)
{
if (!timeToLive)
return IntRange::top(value->type());
switch (value->opcode()) {
case Const32:
case Const64: {
int64_t intValue = value->asInt();
return IntRange(intValue, intValue);
}
case BitAnd:
if (value->child(1)->hasInt())
return IntRange::rangeForMask(value->child(1)->asInt(), value->type());
break;
case SShr:
if (value->child(1)->hasInt32()) {
return rangeFor(value->child(0), timeToLive - 1).sShr(
value->child(1)->asInt32(), value->type());
}
break;
case ZShr:
if (value->child(1)->hasInt32()) {
return rangeFor(value->child(0), timeToLive - 1).zShr(
value->child(1)->asInt32(), value->type());
}
break;
case Shl:
if (value->child(1)->hasInt32()) {
return rangeFor(value->child(0), timeToLive - 1).shl(
value->child(1)->asInt32(), value->type());
}
break;
case Add:
return rangeFor(value->child(0), timeToLive - 1).add(
rangeFor(value->child(1), timeToLive - 1), value->type());
case Sub:
return rangeFor(value->child(0), timeToLive - 1).sub(
rangeFor(value->child(1), timeToLive - 1), value->type());
case Mul:
return rangeFor(value->child(0), timeToLive - 1).mul(
rangeFor(value->child(1), timeToLive - 1), value->type());
default:
break;
}
return IntRange::top(value->type());
}
template<typename ValueType, typename... Arguments>
void replaceWithNew(Arguments... arguments)
{
replaceWithNewValue(m_proc.add<ValueType>(arguments...));
}
bool replaceWithNewValue(Value* newValue)
{
if (!newValue)
return false;
m_insertionSet.insertValue(m_index, newValue);
m_value->replaceWithIdentity(newValue);
m_changed = true;
return true;
}
void replaceWithIdentity(Value* newValue)
{
m_value->replaceWithIdentity(newValue);
m_changed = true;
}
void handleShiftAmount()
{
if (m_value->child(1)->isInt32(0)) {
replaceWithIdentity(m_value->child(0));
return;
}
unsigned mask = sizeofType(m_value->type()) * 8 - 1;
if (m_value->child(1)->opcode() == BitAnd
&& m_value->child(1)->child(1)->hasInt32()
&& (m_value->child(1)->child(1)->asInt32() & mask) == mask) {
m_value->child(1) = m_value->child(1)->child(0);
m_changed = true;
}
}
void replaceIfRedundant()
{
m_changed |= m_pureCSE.process(m_value, *m_dominators);
}
void simplifyCFG()
{
if (verbose) {
dataLog("Before simplifyCFG:\n");
dataLog(m_proc);
}
for (BasicBlock* block : m_proc) {
if (verbose)
dataLog("Considering block ", *block, ":\n");
checkPredecessorValidity();
if (!block->numSuccessors())
continue;
for (BasicBlock*& successor : block->successorBlocks()) {
if (successor != block
&& successor->size() == 1
&& successor->last()->opcode() == Jump) {
BasicBlock* newSuccessor = successor->successorBlock(0);
if (newSuccessor != successor) {
if (verbose) {
dataLog(
"Replacing ", pointerDump(block), "->", pointerDump(successor),
" with ", pointerDump(block), "->", pointerDump(newSuccessor),
"\n");
}
newSuccessor->addPredecessor(block);
successor = newSuccessor;
m_changedCFG = true;
}
}
}
if (block->numSuccessors() > 1) {
Effects effects = block->last()->effects();
effects.terminal = false;
if (!effects.mustExecute()) {
bool allSame = true;
BasicBlock* firstSuccessor = block->successorBlock(0);
for (unsigned i = 1; i < block->numSuccessors(); ++i) {
if (block->successorBlock(i) != firstSuccessor) {
allSame = false;
break;
}
}
if (allSame) {
if (verbose) {
dataLog(
"Changing ", pointerDump(block), "'s terminal to a Jump.\n");
}
block->last()->replaceWithJump(block, FrequentedBlock(firstSuccessor));
m_changedCFG = true;
}
}
}
if (block->numSuccessors() == 1) {
BasicBlock* successor = block->successorBlock(0);
if (successor != block && successor->numPredecessors() == 1) {
RELEASE_ASSERT(successor->predecessor(0) == block);
Value* value = block->values().takeLast();
Origin jumpOrigin = value->origin();
RELEASE_ASSERT(value->effects().terminal);
m_proc.deleteValue(value);
block->values().appendVector(successor->values());
block->successors() = successor->successors();
successor->values().resize(0);
successor->appendNew<Value>(m_proc, Oops, jumpOrigin);
successor->clearSuccessors();
for (BasicBlock* newSuccessor : block->successorBlocks())
newSuccessor->replacePredecessor(successor, block);
if (verbose) {
dataLog(
"Merged ", pointerDump(block), "->", pointerDump(successor), "\n");
}
m_changedCFG = true;
}
}
}
if (m_changedCFG && verbose) {
dataLog("B3 after simplifyCFG:\n");
dataLog(m_proc);
}
}
void checkPredecessorValidity()
{
if (!shouldValidateIRAtEachPhase())
return;
for (BasicBlock* block : m_proc) {
for (BasicBlock* successor : block->successorBlocks())
RELEASE_ASSERT(successor->containsPredecessor(block));
}
}
void killDeadCode()
{
GraphNodeWorklist<Value*, IndexSet<Value>> worklist;
Vector<UpsilonValue*, 64> upsilons;
for (BasicBlock* block : m_proc) {
for (Value* value : *block) {
Effects effects;
if (value->opcode() != Phi && value->opcode() != Upsilon)
effects = value->effects();
if (effects.mustExecute())
worklist.push(value);
if (UpsilonValue* upsilon = value->as<UpsilonValue>())
upsilons.append(upsilon);
}
}
for (;;) {
while (Value* value = worklist.pop()) {
for (Value* child : value->children())
worklist.push(child);
}
bool didPush = false;
for (size_t upsilonIndex = 0; upsilonIndex < upsilons.size(); ++upsilonIndex) {
UpsilonValue* upsilon = upsilons[upsilonIndex];
if (worklist.saw(upsilon->phi())) {
worklist.push(upsilon);
upsilons[upsilonIndex--] = upsilons.last();
upsilons.takeLast();
didPush = true;
}
}
if (!didPush)
break;
}
IndexSet<Variable> liveVariables;
for (BasicBlock* block : m_proc) {
size_t sourceIndex = 0;
size_t targetIndex = 0;
while (sourceIndex < block->size()) {
Value* value = block->at(sourceIndex++);
if (worklist.saw(value)) {
if (VariableValue* variableValue = value->as<VariableValue>())
liveVariables.add(variableValue->variable());
block->at(targetIndex++) = value;
} else {
m_proc.deleteValue(value);
m_changed = true;
}
}
block->values().resize(targetIndex);
}
for (Variable* variable : m_proc.variables()) {
if (!liveVariables.contains(variable))
m_proc.deleteVariable(variable);
}
}
void simplifySSA()
{
PhiChildren phiChildren(m_proc);
for (Value* phi : phiChildren.phis()) {
Value* otherChild = nullptr;
bool ok = true;
for (Value* child : phiChildren[phi].values()) {
if (child == phi)
continue;
if (child == otherChild)
continue;
if (!otherChild) {
otherChild = child;
continue;
}
ok = false;
break;
}
if (!ok)
continue;
if (!otherChild) {
continue;
}
m_changed = true;
for (Value* upsilon : phiChildren[phi])
upsilon->replaceWithNop();
phi->replaceWithIdentity(otherChild);
}
}
Procedure& m_proc;
InsertionSet m_insertionSet;
BlockInsertionSet m_blockInsertionSet;
BasicBlock* m_block { nullptr };
unsigned m_index { 0 };
Value* m_value { nullptr };
Dominators* m_dominators { nullptr };
PureCSE m_pureCSE;
bool m_changed { false };
bool m_changedCFG { false };
};
}
bool reduceStrength(Procedure& proc)
{
PhaseScope phaseScope(proc, "reduceStrength");
ReduceStrength reduceStrength(proc);
return reduceStrength.run();
}
} }
#endif // ENABLE(B3_JIT)