blob: 1788869427d3ad58354bbe77bdd2bc721dc5f1fb [file] [log] [blame]
/*
* Copyright (C) 2015 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 "AirSimplifyCFG.h"
#if ENABLE(B3_JIT)
#include "AirCode.h"
#include "AirPhaseScope.h"
namespace JSC { namespace B3 { namespace Air {
bool simplifyCFG(Code& code)
{
constexpr bool verbose = false;
PhaseScope phaseScope(code, "simplifyCFG");
// We have three easy simplification rules:
//
// 1) If a successor is a block that just jumps to another block, then jump directly to
// that block.
//
// 2) If all successors are the same and the operation has no effects, then use a jump
// instead.
//
// 3) If you jump to a block that is not you and has one predecessor, then merge.
//
// Note that because of the first rule, this phase may introduce critical edges. That's fine.
// If you need broken critical edges, then you have to break them yourself.
bool result = false;
for (;;) {
if (verbose) {
dataLog("Air before an iteration of simplifyCFG:\n");
dataLog(code);
}
bool changed = false;
for (BasicBlock* block : code) {
// We rely on predecessors being conservatively correct. Verify this here.
if (shouldValidateIRAtEachPhase()) {
for (BasicBlock* block : code) {
for (BasicBlock* successor : block->successorBlocks())
RELEASE_ASSERT(successor->containsPredecessor(block));
}
}
// We don't care about blocks that don't have successors.
if (!block->numSuccessors())
continue;
// First check if any of the successors of this block can be forwarded over.
for (BasicBlock*& successor : block->successorBlocks()) {
if (successor != block
&& successor->size() == 1
&& successor->last().kind.opcode == Jump) {
BasicBlock* newSuccessor = successor->successorBlock(0);
if (newSuccessor != successor) {
if (verbose) {
dataLog(
"Replacing ", pointerDump(block), "->", pointerDump(successor),
" with ", pointerDump(block), "->", pointerDump(newSuccessor), "\n");
}
// Note that we do not do replacePredecessor() because the block we're
// skipping will still have newSuccessor as its successor.
newSuccessor->addPredecessor(block);
successor = newSuccessor;
changed = true;
}
}
}
// Now check if the block's terminal can be replaced with a jump. The terminal must not
// have weird effects.
if (block->numSuccessors() > 1
&& !block->last().hasNonControlEffects()) {
// All of the successors must be the same.
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() = Inst(Jump, block->last().origin);
block->successors().resize(1);
block->successors()[0].frequency() = FrequencyClass::Normal;
changed = true;
}
}
// Finally handle jumps to a block with one predecessor.
if (block->numSuccessors() == 1
&& !block->last().hasNonControlEffects()) {
BasicBlock* successor = block->successorBlock(0);
if (successor != block && successor->numPredecessors() == 1) {
RELEASE_ASSERT(successor->predecessor(0) == block);
// We can merge the two blocks because the predecessor only jumps to the successor
// and the successor is only reachable from the predecessor.
// Remove the terminal.
Value* origin = block->insts().takeLast().origin;
// Append the full contents of the successor to the predecessor.
block->insts().reserveCapacity(block->size() + successor->size());
for (Inst& inst : *successor)
block->appendInst(WTFMove(inst));
// Make sure that our successors are the successor's successors.
block->successors() = WTFMove(successor->successors());
// Make sure that the successor has nothing left in it except an oops.
successor->resize(1);
successor->last() = Inst(Oops, origin);
successor->successors().clear();
// Ensure that the predecessors of block's new successors know what's up.
for (BasicBlock* newSuccessor : block->successorBlocks())
newSuccessor->replacePredecessor(successor, block);
if (verbose)
dataLog("Merged ", pointerDump(block), "->", pointerDump(successor), "\n");
changed = true;
}
}
}
if (!changed)
break;
result = true;
code.resetReachability();
}
return result;
}
} } } // namespace JSC::B3::Air
#endif // ENABLE(B3_JIT)