/* * 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 "AirInstInlines.h" #include "AirPhaseScope.h" namespace JSC { namespace B3 { namespace Air { bool simplifyCFG(Code& code) { const 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)