#include "config.h"
#include "B3FixSSA.h"
#if ENABLE(B3_JIT)
#include "B3BasicBlockInlines.h"
#include "B3BreakCriticalEdges.h"
#include "B3Dominators.h"
#include "B3InsertionSetInlines.h"
#include "B3PhaseScope.h"
#include "B3ProcedureInlines.h"
#include "B3SSACalculator.h"
#include "B3UpsilonValue.h"
#include "B3ValueInlines.h"
#include "B3Variable.h"
#include "B3VariableLiveness.h"
#include "B3VariableValue.h"
#include <wtf/CommaPrinter.h>
#include <wtf/IndexSet.h>
#include <wtf/IndexSparseSet.h>
namespace JSC { namespace B3 {
namespace {
namespace B3FixSSAInternal {
static const bool verbose = false;
}
void killDeadVariables(Procedure& proc)
{
IndexSet<Variable*> liveVariables;
for (Value* value : proc.values()) {
if (value->opcode() == Get)
liveVariables.add(value->as<VariableValue>()->variable());
}
for (Value* value : proc.values()) {
if (value->opcode() == Set && !liveVariables.contains(value->as<VariableValue>()->variable()))
value->replaceWithNop();
}
for (Variable* variable : proc.variables()) {
if (!liveVariables.contains(variable))
proc.deleteVariable(variable);
}
}
void fixSSALocally(Procedure& proc)
{
IndexSparseSet<KeyValuePair<unsigned, Value*>> mapping(proc.variables().size());
for (BasicBlock* block : proc.blocksInPreOrder()) {
mapping.clear();
for (unsigned valueIndex = 0; valueIndex < block->size(); ++valueIndex) {
Value* value = block->at(valueIndex);
value->performSubstitution();
switch (value->opcode()) {
case Get: {
VariableValue* variableValue = value->as<VariableValue>();
Variable* variable = variableValue->variable();
if (KeyValuePair<unsigned, Value*>* replacement = mapping.get(variable->index()))
value->replaceWithIdentity(replacement->value);
break;
}
case Set: {
VariableValue* variableValue = value->as<VariableValue>();
Variable* variable = variableValue->variable();
mapping.set(variable->index(), value->child(0));
break;
}
default:
break;
}
}
}
}
void fixSSAGlobally(Procedure& proc)
{
VariableLiveness liveness(proc);
for (BasicBlock* block : proc) {
VariableLiveness::LocalCalc localCalc(liveness, block);
for (unsigned valueIndex = block->size(); valueIndex--;) {
Value* value = block->at(valueIndex);
if (value->opcode() == Set && !localCalc.isLive(value->as<VariableValue>()->variable()))
value->replaceWithNop();
localCalc.execute(valueIndex);
}
}
VariableLiveness::LiveAtHead liveAtHead = liveness.liveAtHead();
SSACalculator ssa(proc);
Vector<Variable*> calcVarToVariable;
IndexMap<Variable*, SSACalculator::Variable*> variableToCalcVar(proc.variables().size());
for (Variable* variable : proc.variables()) {
SSACalculator::Variable* calcVar = ssa.newVariable();
RELEASE_ASSERT(calcVar->index() == calcVarToVariable.size());
calcVarToVariable.append(variable);
variableToCalcVar[variable] = calcVar;
}
for (BasicBlock* block : proc) {
for (Value* value : *block) {
if (value->opcode() != Set)
continue;
Variable* variable = value->as<VariableValue>()->variable();
if (SSACalculator::Variable* calcVar = variableToCalcVar[variable])
ssa.newDef(calcVar, block, value->child(0));
}
}
{
TimingScope timingScope("fixSSA: computePhis");
ssa.computePhis(
[&] (SSACalculator::Variable* calcVar, BasicBlock* block) -> Value* {
Variable* variable = calcVarToVariable[calcVar->index()];
if (!liveAtHead.isLiveAtHead(block, variable))
return nullptr;
Value* phi = proc.add<Value>(Phi, variable->type(), block->at(0)->origin());
if (B3FixSSAInternal::verbose) {
dataLog(
"Adding Phi for ", pointerDump(variable), " at ", *block, ": ",
deepDump(proc, phi), "\n");
}
return phi;
});
}
TimingScope timingScope("fixSSA: convert");
InsertionSet insertionSet(proc);
IndexSparseSet<KeyValuePair<unsigned, Value*>> mapping(proc.variables().size());
IndexSet<Value*> valuesToDelete;
for (BasicBlock* block : proc.blocksInPreOrder()) {
mapping.clear();
auto ensureMapping = [&] (Variable* variable, unsigned valueIndex, Origin origin) -> Value* {
KeyValuePair<unsigned, Value*>* found = mapping.get(variable->index());
if (found)
return found->value;
SSACalculator::Variable* calcVar = variableToCalcVar[variable];
SSACalculator::Def* def = ssa.reachingDefAtHead(block, calcVar);
if (def) {
mapping.set(variable->index(), def->value());
return def->value();
}
return insertionSet.insertBottom(valueIndex, origin, variable->type());
};
for (SSACalculator::Def* phiDef : ssa.phisForBlock(block)) {
Variable* variable = calcVarToVariable[phiDef->variable()->index()];
insertionSet.insertValue(0, phiDef->value());
mapping.set(variable->index(), phiDef->value());
}
for (unsigned valueIndex = 0; valueIndex < block->size(); ++valueIndex) {
Value* value = block->at(valueIndex);
value->performSubstitution();
switch (value->opcode()) {
case Get: {
VariableValue* variableValue = value->as<VariableValue>();
Variable* variable = variableValue->variable();
value->replaceWithIdentity(ensureMapping(variable, valueIndex, value->origin()));
valuesToDelete.add(value);
break;
}
case Set: {
VariableValue* variableValue = value->as<VariableValue>();
Variable* variable = variableValue->variable();
mapping.set(variable->index(), value->child(0));
value->replaceWithNop();
break;
}
default:
break;
}
}
unsigned upsilonInsertionPoint = block->size() - 1;
Origin upsilonOrigin = block->last()->origin();
for (BasicBlock* successorBlock : block->successorBlocks()) {
for (SSACalculator::Def* phiDef : ssa.phisForBlock(successorBlock)) {
Value* phi = phiDef->value();
SSACalculator::Variable* calcVar = phiDef->variable();
Variable* variable = calcVarToVariable[calcVar->index()];
Value* mappedValue = ensureMapping(variable, upsilonInsertionPoint, upsilonOrigin);
if (B3FixSSAInternal::verbose) {
dataLog(
"Mapped value for ", *variable, " with successor Phi ", *phi,
" at end of ", *block, ": ", pointerDump(mappedValue), "\n");
}
insertionSet.insert<UpsilonValue>(
upsilonInsertionPoint, upsilonOrigin, mappedValue->foldIdentity(), phi);
}
}
insertionSet.execute(block);
}
for (BasicBlock* block : proc) {
block->values().removeAllMatching(
[&] (Value* value) -> bool {
if (!valuesToDelete.contains(value) && value->opcode() != Nop)
return false;
proc.deleteValue(value);
return true;
});
}
if (B3FixSSAInternal::verbose) {
dataLog("B3 after SSA conversion:\n");
dataLog(proc);
}
}
}
void demoteValues(Procedure& proc, const IndexSet<Value*>& values)
{
HashMap<Value*, Variable*> map;
HashMap<Value*, Variable*> phiMap;
for (Value* value : values.values(proc.values())) {
map.add(value, proc.addVariable(value->type()));
if (value->opcode() == Phi)
phiMap.add(value, proc.addVariable(value->type()));
}
if (B3FixSSAInternal::verbose) {
dataLog("Demoting values as follows:\n");
dataLog(" map = ");
CommaPrinter comma;
for (auto& entry : map)
dataLog(comma, *entry.key, "=>", *entry.value);
dataLog("\n");
dataLog(" phiMap = ");
comma = CommaPrinter();
for (auto& entry : phiMap)
dataLog(comma, *entry.key, "=>", *entry.value);
dataLog("\n");
}
InsertionSet insertionSet(proc);
for (BasicBlock* block : proc) {
if (block->numPredecessors()) {
Value* value = block->predecessor(0)->last();
Variable* variable = map.get(value);
if (variable) {
RELEASE_ASSERT(block->numPredecessors() == 1); insertionSet.insert<VariableValue>(0, Set, value->origin(), variable, value);
}
}
for (unsigned valueIndex = 0; valueIndex < block->size(); ++valueIndex) {
Value* value = block->at(valueIndex);
if (value->opcode() == Phi) {
if (Variable* variable = phiMap.get(value)) {
value->replaceWithIdentity(
insertionSet.insert<VariableValue>(
valueIndex, Get, value->origin(), variable));
}
} else {
for (Value*& child : value->children()) {
if (Variable* variable = map.get(child)) {
child = insertionSet.insert<VariableValue>(
valueIndex, Get, value->origin(), variable);
}
}
if (UpsilonValue* upsilon = value->as<UpsilonValue>()) {
if (Variable* variable = phiMap.get(upsilon->phi())) {
insertionSet.insert<VariableValue>(
valueIndex, Set, upsilon->origin(), variable, upsilon->child(0));
value->replaceWithNop();
}
}
}
if (Variable* variable = map.get(value)) {
if (valueIndex + 1 < block->size()) {
insertionSet.insert<VariableValue>(
valueIndex + 1, Set, value->origin(), variable, value);
}
}
}
insertionSet.execute(block);
}
}
bool fixSSA(Procedure& proc)
{
PhaseScope phaseScope(proc, "fixSSA");
if (proc.variables().isEmpty())
return false;
fixSSALocally(proc);
killDeadVariables(proc);
if (proc.variables().isEmpty())
return false;
breakCriticalEdges(proc);
fixSSAGlobally(proc);
return true;
}
} }
#endif // ENABLE(B3_JIT)