blob: e67f304af091d1ddea14f5bf536dade2660815c5 [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 "B3FoldPathConstants.h"
#if ENABLE(B3_JIT)
#include "B3BasicBlockInlines.h"
#include "B3CaseCollectionInlines.h"
#include "B3Dominators.h"
#include "B3InsertionSetInlines.h"
#include "B3PhaseScope.h"
#include "B3ProcedureInlines.h"
#include "B3SwitchValue.h"
#include "B3ValueInlines.h"
namespace JSC { namespace B3 {
namespace {
namespace B3FoldPathConstantsInternal {
static constexpr bool verbose = false;
}
class FoldPathConstants {
public:
FoldPathConstants(Procedure& proc)
: m_proc(proc)
, m_insertionSet(proc)
{
}
void run()
{
bool changed = false;
if (B3FoldPathConstantsInternal::verbose)
dataLog("B3 before folding path constants: \n", m_proc, "\n");
// Find all of the values that are the subject of a branch or switch. For any successor
// that we dominate, install a value override at that block.
HashMap<Value*, Vector<Override>> overrides;
Dominators& dominators = m_proc.dominators();
auto addOverride = [&] (
BasicBlock* from, Value* value, const Override& override) {
if (override.block->numPredecessors() != 1)
return;
ASSERT(override.block->predecessor(0) == from);
Vector<Override>& forValue =
overrides.add(value, Vector<Override>()).iterator->value;
if (ASSERT_ENABLED) {
for (const Override& otherOverride : forValue)
ASSERT_UNUSED(otherOverride, otherOverride.block != override.block);
}
if (B3FoldPathConstantsInternal::verbose)
dataLog("Overriding ", *value, " from ", *from, ": ", override, "\n");
forValue.append(override);
};
for (BasicBlock* block : m_proc) {
Value* branch = block->last();
switch (branch->opcode()) {
case Branch:
if (block->successorBlock(0) == block->successorBlock(1))
continue;
addOverride(
block, branch->child(0),
Override::nonZero(block->successorBlock(0)));
addOverride(
block, branch->child(0),
Override::constant(block->successorBlock(1), 0));
break;
case Switch: {
SwitchValue* switchValue = branch->as<SwitchValue>();
HashMap<BasicBlock*, unsigned> targetUses;
for (SwitchCase switchCase : switchValue->cases(block))
targetUses.add(switchCase.targetBlock(), 0).iterator->value++;
targetUses.add(switchValue->fallThrough(block), 0).iterator->value++;
for (SwitchCase switchCase : switchValue->cases(block)) {
if (targetUses.find(switchCase.targetBlock())->value != 1)
continue;
addOverride(
block, branch->child(0),
Override::constant(switchCase.targetBlock(), switchCase.caseValue()));
}
break;
}
default:
break;
}
}
// Install the constants in the override blocks. We use one-shot insertion sets because
// each block will get at most one thing inserted into it anyway.
for (auto& entry : overrides) {
for (Override& override : entry.value) {
if (!override.hasValue)
continue;
override.valueNode =
m_insertionSet.insertIntConstant(0, entry.key, override.value);
m_insertionSet.execute(override.block);
}
}
// Replace all uses of a value that has an override with that override, if appropriate.
// Certain instructions get special treatment.
auto getOverride = [&] (BasicBlock* block, Value* value) -> Override {
auto iter = overrides.find(value);
if (iter == overrides.end())
return Override();
Vector<Override>& forValue = iter->value;
Override result;
for (Override& override : forValue) {
if (dominators.dominates(override.block, block)
&& override.isBetterThan(result))
result = override;
}
if (B3FoldPathConstantsInternal::verbose)
dataLog("In block ", *block, " getting override for ", *value, ": ", result, "\n");
return result;
};
for (BasicBlock* block : m_proc) {
for (unsigned valueIndex = 0; valueIndex < block->size(); ++valueIndex) {
Value* value = block->at(valueIndex);
switch (value->opcode()) {
case Branch: {
if (getOverride(block, value->child(0)).isNonZero) {
value->replaceWithJump(block, block->taken());
changed = true;
}
break;
}
case Equal: {
if (value->child(1)->isInt(0)
&& getOverride(block, value->child(0)).isNonZero) {
value->replaceWithIdentity(
m_insertionSet.insertIntConstant(valueIndex, value, 0));
}
break;
}
case NotEqual: {
if (value->child(1)->isInt(0)
&& getOverride(block, value->child(0)).isNonZero) {
value->replaceWithIdentity(
m_insertionSet.insertIntConstant(valueIndex, value, 1));
}
break;
}
default:
break;
}
for (Value*& child : value->children()) {
Override override = getOverride(block, child);
if (override.valueNode)
child = override.valueNode;
}
}
m_insertionSet.execute(block);
}
if (changed) {
m_proc.resetReachability();
m_proc.invalidateCFG();
}
}
private:
struct Override {
Override()
{
}
static Override constant(BasicBlock* block, int64_t value)
{
Override result;
result.block = block;
result.hasValue = true;
result.value = value;
if (value)
result.isNonZero = true;
return result;
}
static Override nonZero(BasicBlock* block)
{
Override result;
result.block = block;
result.isNonZero = true;
return result;
}
bool isBetterThan(const Override& override)
{
if (hasValue && !override.hasValue)
return true;
if (isNonZero && !override.isNonZero)
return true;
return false;
}
void dump(PrintStream& out) const
{
out.print("{block = ", pointerDump(block), ", value = ");
if (hasValue)
out.print(value);
else
out.print("<none>");
out.print(", isNonZero = ", isNonZero);
if (valueNode)
out.print(", valueNode = ", *valueNode);
out.print("}");
}
BasicBlock* block { nullptr };
bool hasValue { false };
bool isNonZero { false };
int64_t value { 0 };
Value* valueNode { nullptr };
};
Procedure& m_proc;
InsertionSet m_insertionSet;
};
} // anonymous namespace
void foldPathConstants(Procedure& proc)
{
PhaseScope phaseScope(proc, "foldPathConstants");
FoldPathConstants foldPathConstants(proc);
foldPathConstants.run();
}
} } // namespace JSC::B3
#endif // ENABLE(B3_JIT)