Diff
Modified: trunk/Source/_javascript_Core/ChangeLog (192120 => 192121)
--- trunk/Source/_javascript_Core/ChangeLog 2015-11-06 23:20:12 UTC (rev 192120)
+++ trunk/Source/_javascript_Core/ChangeLog 2015-11-06 23:34:31 UTC (rev 192121)
@@ -1,3 +1,50 @@
+2015-11-06 Filip Pizlo <[email protected]>
+
+ B3 and Air should simplify CFGs
+ https://bugs.webkit.org/show_bug.cgi?id=150960
+
+ Reviewed by Geoffrey Garen.
+
+ This adds CFG simplification to both B3 and Air.
+
+ In B3, the simplification is done inside the B3::reduceStrength() fixpoint because we expect
+ that it will help to reveal more optimization opportunities. This is going to be particularly
+ true when we add Phi elimination.
+
+ In Air, the simplification is its own phase. We expect it to produce most of its benefits once
+ we have coalescing. Then, CFG simplification in Air will unbreak critial edges.
+
+ * _javascript_Core.xcodeproj/project.pbxproj:
+ * assembler/AbortReason.h:
+ * assembler/MacroAssembler.h:
+ (JSC::MacroAssembler::oops): Reveal this as a method so that we can have an Oops instruction.
+ * b3/B3BasicBlock.h:
+ (JSC::B3::BasicBlock::predecessor):
+ (JSC::B3::BasicBlock::predecessors):
+ (JSC::B3::BasicBlock::containsPredecessor):
+ * b3/B3BasicBlockUtils.h: Bunch of fixes for blocks being killed.
+ (JSC::B3::replacePredecessor):
+ (JSC::B3::resetReachability):
+ * b3/B3ReduceStrength.cpp: Implement B3 CFG simplification.
+ * b3/B3ReduceStrength.h:
+ * b3/air/AirBasicBlock.h:
+ (JSC::B3::Air::BasicBlock::resize):
+ (JSC::B3::Air::BasicBlock::insts):
+ (JSC::B3::Air::BasicBlock::appendInst):
+ (JSC::B3::Air::BasicBlock::containsPredecessor):
+ * b3/air/AirGenerate.cpp:
+ (JSC::B3::Air::generate):
+ * b3/air/AirInst.cpp:
+ (JSC::B3::Air::Inst::hasArgEffects):
+ (JSC::B3::Air::Inst::dump):
+ * b3/air/AirInst.h:
+ * b3/air/AirLiveness.h:
+ (JSC::B3::Air::Liveness::Liveness): Fix for when blocks were killed.
+ * b3/air/AirOpcode.opcodes:
+ * b3/air/AirSimplifyCFG.cpp: Added.
+ (JSC::B3::Air::simplifyCFG):
+ * b3/air/AirSimplifyCFG.h: Added.
+
2015-11-05 Nikos Andronikos <[email protected]>
Add runtime and compile time flags for enabling Web Animations API and model.
Modified: trunk/Source/_javascript_Core/_javascript_Core.xcodeproj/project.pbxproj (192120 => 192121)
--- trunk/Source/_javascript_Core/_javascript_Core.xcodeproj/project.pbxproj 2015-11-06 23:20:12 UTC (rev 192120)
+++ trunk/Source/_javascript_Core/_javascript_Core.xcodeproj/project.pbxproj 2015-11-06 23:34:31 UTC (rev 192121)
@@ -280,12 +280,14 @@
0F300B7C18AB1B1400A6D72E /* DFGIntegerCheckCombiningPhase.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F300B7A18AB1B1400A6D72E /* DFGIntegerCheckCombiningPhase.h */; };
0F32BD101BB34F190093A57F /* HeapHelperPool.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F32BD0E1BB34F190093A57F /* HeapHelperPool.cpp */; };
0F32BD111BB34F190093A57F /* HeapHelperPool.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F32BD0F1BB34F190093A57F /* HeapHelperPool.h */; };
- 0F338DF91BE96AA80013C88F /* B3CCallValue.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F338DF71BE96AA80013C88F /* B3CCallValue.cpp */; };
- 0F338DFA1BE96AA80013C88F /* B3CCallValue.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F338DF81BE96AA80013C88F /* B3CCallValue.h */; };
0F338DF11BE93AD10013C88F /* B3StackmapValue.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F338DEF1BE93AD10013C88F /* B3StackmapValue.cpp */; };
0F338DF21BE93AD10013C88F /* B3StackmapValue.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F338DF01BE93AD10013C88F /* B3StackmapValue.h */; };
0F338DF51BE93D550013C88F /* B3ConstrainedValue.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F338DF31BE93D550013C88F /* B3ConstrainedValue.cpp */; };
0F338DF61BE93D550013C88F /* B3ConstrainedValue.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F338DF41BE93D550013C88F /* B3ConstrainedValue.h */; };
+ 0F338DF91BE96AA80013C88F /* B3CCallValue.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F338DF71BE96AA80013C88F /* B3CCallValue.cpp */; };
+ 0F338DFA1BE96AA80013C88F /* B3CCallValue.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F338DF81BE96AA80013C88F /* B3CCallValue.h */; };
+ 0F338DFD1BED51270013C88F /* AirSimplifyCFG.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F338DFB1BED51270013C88F /* AirSimplifyCFG.cpp */; };
+ 0F338DFE1BED51270013C88F /* AirSimplifyCFG.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F338DFC1BED51270013C88F /* AirSimplifyCFG.h */; };
0F34B14916D42010001CDA5A /* DFGUseKind.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F34B14716D4200E001CDA5A /* DFGUseKind.cpp */; };
0F34B14A16D42013001CDA5A /* DFGUseKind.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F34B14816D4200E001CDA5A /* DFGUseKind.h */; };
0F38B01117CF078000B144D3 /* LLIntEntrypoint.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F38B00F17CF077F00B144D3 /* LLIntEntrypoint.cpp */; };
@@ -2303,12 +2305,14 @@
0F300B7A18AB1B1400A6D72E /* DFGIntegerCheckCombiningPhase.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = DFGIntegerCheckCombiningPhase.h; path = dfg/DFGIntegerCheckCombiningPhase.h; sourceTree = "<group>"; };
0F32BD0E1BB34F190093A57F /* HeapHelperPool.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = HeapHelperPool.cpp; sourceTree = "<group>"; };
0F32BD0F1BB34F190093A57F /* HeapHelperPool.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = HeapHelperPool.h; sourceTree = "<group>"; };
- 0F338DF71BE96AA80013C88F /* B3CCallValue.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = B3CCallValue.cpp; path = b3/B3CCallValue.cpp; sourceTree = "<group>"; };
- 0F338DF81BE96AA80013C88F /* B3CCallValue.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = B3CCallValue.h; path = b3/B3CCallValue.h; sourceTree = "<group>"; };
0F338DEF1BE93AD10013C88F /* B3StackmapValue.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = B3StackmapValue.cpp; path = b3/B3StackmapValue.cpp; sourceTree = "<group>"; };
0F338DF01BE93AD10013C88F /* B3StackmapValue.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = B3StackmapValue.h; path = b3/B3StackmapValue.h; sourceTree = "<group>"; };
0F338DF31BE93D550013C88F /* B3ConstrainedValue.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = B3ConstrainedValue.cpp; path = b3/B3ConstrainedValue.cpp; sourceTree = "<group>"; };
0F338DF41BE93D550013C88F /* B3ConstrainedValue.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = B3ConstrainedValue.h; path = b3/B3ConstrainedValue.h; sourceTree = "<group>"; };
+ 0F338DF71BE96AA80013C88F /* B3CCallValue.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = B3CCallValue.cpp; path = b3/B3CCallValue.cpp; sourceTree = "<group>"; };
+ 0F338DF81BE96AA80013C88F /* B3CCallValue.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = B3CCallValue.h; path = b3/B3CCallValue.h; sourceTree = "<group>"; };
+ 0F338DFB1BED51270013C88F /* AirSimplifyCFG.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = AirSimplifyCFG.cpp; path = b3/air/AirSimplifyCFG.cpp; sourceTree = "<group>"; };
+ 0F338DFC1BED51270013C88F /* AirSimplifyCFG.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = AirSimplifyCFG.h; path = b3/air/AirSimplifyCFG.h; sourceTree = "<group>"; };
0F34B14716D4200E001CDA5A /* DFGUseKind.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = DFGUseKind.cpp; path = dfg/DFGUseKind.cpp; sourceTree = "<group>"; };
0F34B14816D4200E001CDA5A /* DFGUseKind.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = DFGUseKind.h; path = dfg/DFGUseKind.h; sourceTree = "<group>"; };
0F38B00F17CF077F00B144D3 /* LLIntEntrypoint.cpp */ = {isa = PBXFileReference; lastKnownFileType = sourcecode.cpp.cpp; name = LLIntEntrypoint.cpp; path = llint/LLIntEntrypoint.cpp; sourceTree = "<group>"; };
@@ -4524,6 +4528,8 @@
0FEC85611BDACDC70080FF74 /* AirRegisterPriority.h */,
0F45703A1BE45F0A0062A629 /* AirReportUsedRegisters.cpp */,
0F45703B1BE45F0A0062A629 /* AirReportUsedRegisters.h */,
+ 0F338DFB1BED51270013C88F /* AirSimplifyCFG.cpp */,
+ 0F338DFC1BED51270013C88F /* AirSimplifyCFG.h */,
0FEC85621BDACDC70080FF74 /* AirSpecial.cpp */,
0FEC85631BDACDC70080FF74 /* AirSpecial.h */,
0FEC85641BDACDC70080FF74 /* AirSpillEverything.cpp */,
@@ -6767,6 +6773,7 @@
0FBDB9AD1AB0FBC6000B57E5 /* DFGCallCreateDirectArgumentsSlowPathGenerator.h in Headers */,
0F7B294B14C3CD2F007C3DB1 /* DFGCapabilities.h in Headers */,
0FFFC95814EF90A200C72532 /* DFGCFAPhase.h in Headers */,
+ 0F338DFE1BED51270013C88F /* AirSimplifyCFG.h in Headers */,
0F3B3A281544C997003ED0FF /* DFGCFGSimplificationPhase.h in Headers */,
0F9D36951AE9CC33000D4DFB /* DFGCleanUpPhase.h in Headers */,
A77A424017A0BBFD00A8DB81 /* DFGClobberize.h in Headers */,
@@ -8486,6 +8493,7 @@
147F39CE107EC37600427A48 /* Identifier.cpp in Sources */,
A5FD0075189B038C00633231 /* IdentifiersFactory.cpp in Sources */,
C25F8BCD157544A900245B71 /* IncrementalSweeper.cpp in Sources */,
+ 0F338DFD1BED51270013C88F /* AirSimplifyCFG.cpp in Sources */,
0F13E04E16164A1F00DC8DE7 /* IndexingType.cpp in Sources */,
0F0A75221B94BFA900110660 /* InferredType.cpp in Sources */,
0FFC92111B94D4DF0071DD66 /* InferredTypeTable.cpp in Sources */,
Modified: trunk/Source/_javascript_Core/assembler/AbortReason.h (192120 => 192121)
--- trunk/Source/_javascript_Core/assembler/AbortReason.h 2015-11-06 23:20:12 UTC (rev 192120)
+++ trunk/Source/_javascript_Core/assembler/AbortReason.h 2015-11-06 23:34:31 UTC (rev 192121)
@@ -48,6 +48,7 @@
AHTagTypeNumberNotInPlace = 130,
AHTypeInfoInlineTypeFlagsAreValid = 140,
AHTypeInfoIsValid = 150,
+ B3Oops = 155,
DFGBailedAtTopOfBlock = 161,
DFGBailedAtEndOfNode = 162,
DFGBasicStorageAllocatorZeroSize = 170,
Modified: trunk/Source/_javascript_Core/assembler/MacroAssembler.h (192120 => 192121)
--- trunk/Source/_javascript_Core/assembler/MacroAssembler.h 2015-11-06 23:20:12 UTC (rev 192120)
+++ trunk/Source/_javascript_Core/assembler/MacroAssembler.h 2015-11-06 23:34:31 UTC (rev 192121)
@@ -472,6 +472,11 @@
return condition;
}
+ void oops()
+ {
+ abortWithReason(B3Oops);
+ }
+
static const unsigned BlindingModulus = 64;
bool shouldConsiderBlinding()
{
Modified: trunk/Source/_javascript_Core/b3/B3BasicBlock.h (192120 => 192121)
--- trunk/Source/_javascript_Core/b3/B3BasicBlock.h 2015-11-06 23:20:12 UTC (rev 192120)
+++ trunk/Source/_javascript_Core/b3/B3BasicBlock.h 2015-11-06 23:34:31 UTC (rev 192121)
@@ -88,6 +88,7 @@
BasicBlock*& predecessor(unsigned index) { return m_predecessors[index]; }
const PredecessorList& predecessors() const { return m_predecessors; }
PredecessorList& predecessors() { return m_predecessors; }
+ bool containsPredecessor(BasicBlock* block) { return m_predecessors.contains(block); }
bool addPredecessor(BasicBlock*);
bool removePredecessor(BasicBlock*);
Modified: trunk/Source/_javascript_Core/b3/B3BasicBlockUtils.h (192120 => 192121)
--- trunk/Source/_javascript_Core/b3/B3BasicBlockUtils.h 2015-11-06 23:20:12 UTC (rev 192120)
+++ trunk/Source/_javascript_Core/b3/B3BasicBlockUtils.h 2015-11-06 23:34:31 UTC (rev 192121)
@@ -64,14 +64,11 @@
template<typename BasicBlock>
bool replacePredecessor(BasicBlock* block, BasicBlock* from, BasicBlock* to)
{
- auto& predecessors = block->predecessors();
- for (unsigned i = 0; i < predecessors.size(); ++i) {
- if (predecessors[i] == from) {
- predecessors[i] = to;
- return true;
- }
- }
- return false;
+ bool changed = false;
+ // We do it this way because 'to' may already be a predecessor of 'block'.
+ changed |= removePredecessor(block, from);
+ changed |= addPredecessor(block, to);
+ return changed;
}
// This recomputes predecessors and removes blocks that aren't reachable.
@@ -80,8 +77,10 @@
Vector<std::unique_ptr<BasicBlock>>& blocks, const DeleteFunctor& deleteFunctor)
{
// Clear all predecessor lists first.
- for (auto& block : blocks)
- block->predecessors().resize(0);
+ for (auto& block : blocks) {
+ if (block)
+ block->predecessors().resize(0);
+ }
GraphNodeWorklist<BasicBlock*, IndexSet<BasicBlock>> worklist;
worklist.push(blocks[0].get());
@@ -93,6 +92,8 @@
}
for (unsigned i = 1; i < blocks.size(); ++i) {
+ if (!blocks[i])
+ continue;
if (blocks[i]->predecessors().isEmpty()) {
deleteFunctor(blocks[i].get());
blocks[i] = nullptr;
Modified: trunk/Source/_javascript_Core/b3/B3ReduceStrength.cpp (192120 => 192121)
--- trunk/Source/_javascript_Core/b3/B3ReduceStrength.cpp 2015-11-06 23:20:12 UTC (rev 192120)
+++ trunk/Source/_javascript_Core/b3/B3ReduceStrength.cpp 2015-11-06 23:34:31 UTC (rev 192121)
@@ -28,6 +28,7 @@
#if ENABLE(B3_JIT)
+#include "B3BasicBlockInlines.h"
#include "B3ControlValue.h"
#include "B3IndexSet.h"
#include "B3InsertionSetInlines.h"
@@ -90,13 +91,17 @@
bool run()
{
bool result = false;
+ bool first = true;
unsigned index = 0;
do {
m_changed = false;
m_changedCFG = false;
+ ++index;
- if (verbose) {
- dataLog("Reduce strength IR before iteration #", ++index, "\n");
+ if (first)
+ first = false;
+ else if (verbose) {
+ dataLog("B3 after iteration #", index - 1, " of reduceStrength:\n");
dataLog(m_proc);
}
@@ -108,6 +113,8 @@
m_insertionSet.execute(m_block);
}
+ simplifyCFG();
+
if (m_changedCFG) {
m_proc.resetReachability();
m_changed = true;
@@ -545,6 +552,7 @@
// Turn this: Branch(0, then, else)
// Into this: Jump(else)
if (triState == FalseTriState) {
+ branch->taken().block()->removePredecessor(m_block);
branch->convertToJump(branch->notTaken());
m_changedCFG = true;
break;
@@ -553,6 +561,7 @@
// Turn this: Branch(not 0, then, else)
// Into this: Jump(then)
if (triState == TrueTriState) {
+ branch->notTaken().block()->removePredecessor(m_block);
branch->convertToJump(branch->taken());
m_changedCFG = true;
break;
@@ -620,6 +629,118 @@
return false;
}
+ void 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.
+
+ // Note that this relies on predecessors being at least conservatively correct. It's fine for
+ // predecessors to mention a block that isn't actually a predecessor. It's *not* fine for a
+ // predecessor to be omitted. We assert as much in the loop. In practice, we precisely preserve
+ // predecessors during strength reduction since that minimizes the total number of fixpoint
+ // iterations needed to kill a lot of code.
+
+ for (BasicBlock* block : m_proc) {
+ checkPredecessorValidity();
+
+ // 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()->opcode() == Jump) {
+ BasicBlock* newSuccessor = successor->successorBlock(0);
+ if (newSuccessor != successor) {
+ newSuccessor->replacePredecessor(successor, block);
+ successor = newSuccessor;
+ m_changedCFG = true;
+ }
+ }
+ }
+
+ // Now check if the block's terminal can be replaced with a jump.
+ if (block->numSuccessors() > 1) {
+ // The terminal must not have weird effects.
+ Effects effects = block->last()->effects();
+ effects.terminal = false;
+ if (!effects.mustExecute()) {
+ // All of the successors must be the same.
+ bool allSame = true;
+ FrequentedBlock firstSuccessor = block->successor(0);
+ for (unsigned i = 1; i < block->numSuccessors(); ++i) {
+ if (block->successorBlock(i) != firstSuccessor.block()) {
+ allSame = false;
+ break;
+ }
+ }
+ if (allSame) {
+ block->last()->as<ControlValue>()->convertToJump(firstSuccessor);
+ m_changedCFG = true;
+ }
+ }
+ }
+
+ // Finally handle jumps to a block with one predecessor.
+ if (block->numSuccessors() == 1) {
+ 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* value = block->values().takeLast();
+ Origin jumpOrigin = value->origin();
+ RELEASE_ASSERT(value->as<ControlValue>());
+ m_proc.deleteValue(value);
+
+ // Append the full contents of the successor to the predecessor.
+ block->values().appendVector(successor->values());
+
+ // Make sure that the successor has nothing left in it. Make sure that the block
+ // has a terminal so that nobody chokes when they look at it.
+ successor->values().resize(0);
+ successor->appendNew<ControlValue>(m_proc, Oops, jumpOrigin);
+
+ // Ensure that predecessors of block's new successors know what's up.
+ for (BasicBlock* newSuccessor : block->successorBlocks())
+ newSuccessor->replacePredecessor(successor, block);
+ 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;
Modified: trunk/Source/_javascript_Core/b3/B3ReduceStrength.h (192120 => 192121)
--- trunk/Source/_javascript_Core/b3/B3ReduceStrength.h 2015-11-06 23:20:12 UTC (rev 192120)
+++ trunk/Source/_javascript_Core/b3/B3ReduceStrength.h 2015-11-06 23:34:31 UTC (rev 192121)
@@ -32,8 +32,8 @@
class Procedure;
-// Does strength reduction, constant folding, and canonicalization. In the future we may also have it
-// do CSE.
+// Does strength reduction, constant folding, canonicalization, CFG simplification, and DCE. In the
+// future we may also have it do CSE.
bool reduceStrength(Procedure&);
Modified: trunk/Source/_javascript_Core/b3/air/AirBasicBlock.h (192120 => 192121)
--- trunk/Source/_javascript_Core/b3/air/AirBasicBlock.h 2015-11-06 23:20:12 UTC (rev 192120)
+++ trunk/Source/_javascript_Core/b3/air/AirBasicBlock.h 2015-11-06 23:34:31 UTC (rev 192121)
@@ -65,6 +65,9 @@
void resize(unsigned size) { m_insts.resize(size); }
+ const InstList& insts() const { return m_insts; }
+ InstList& insts() { return m_insts; }
+
template<typename Inst>
void appendInst(Inst&& inst)
{
@@ -105,6 +108,7 @@
bool addPredecessor(BasicBlock*);
bool removePredecessor(BasicBlock*);
bool replacePredecessor(BasicBlock* from, BasicBlock* to);
+ bool containsPredecessor(BasicBlock* predecessor) const { return m_predecessors.contains(predecessor); }
void dump(PrintStream&) const;
void deepDump(PrintStream&) const;
Modified: trunk/Source/_javascript_Core/b3/air/AirGenerate.cpp (192120 => 192121)
--- trunk/Source/_javascript_Core/b3/air/AirGenerate.cpp 2015-11-06 23:20:12 UTC (rev 192120)
+++ trunk/Source/_javascript_Core/b3/air/AirGenerate.cpp 2015-11-06 23:34:31 UTC (rev 192121)
@@ -34,6 +34,7 @@
#include "AirGenerationContext.h"
#include "AirHandleCalleeSaves.h"
#include "AirReportUsedRegisters.h"
+#include "AirSimplifyCFG.h"
#include "AirSpillEverything.h"
#include "AirValidate.h"
#include "B3Common.h"
@@ -79,6 +80,10 @@
// shouldn't have to worry about this very much.
allocateStack(code);
+ // If we coalesced moves then we can unbreak critical edges. This is the main reason for this
+ // phase.
+ simplifyCFG(code);
+
// FIXME: We should really have a code layout optimization here.
// https://bugs.webkit.org/show_bug.cgi?id=150478
Modified: trunk/Source/_javascript_Core/b3/air/AirInst.cpp (192120 => 192121)
--- trunk/Source/_javascript_Core/b3/air/AirInst.cpp 2015-11-06 23:20:12 UTC (rev 192120)
+++ trunk/Source/_javascript_Core/b3/air/AirInst.cpp 2015-11-06 23:34:31 UTC (rev 192121)
@@ -28,11 +28,23 @@
#if ENABLE(B3_JIT)
+#include "AirInstInlines.h"
#include "B3Value.h"
#include <wtf/ListDump.h>
namespace JSC { namespace B3 { namespace Air {
+bool Inst::hasArgEffects()
+{
+ bool result = false;
+ forEachArg(
+ [&] (Arg&, Arg::Role role, Arg::Type) {
+ if (Arg::isDef(role))
+ result = true;
+ });
+ return result;
+}
+
void Inst::dump(PrintStream& out) const
{
out.print(opcode, " ", listDump(args));
Modified: trunk/Source/_javascript_Core/b3/air/AirInst.h (192120 => 192121)
--- trunk/Source/_javascript_Core/b3/air/AirInst.h 2015-11-06 23:20:12 UTC (rev 192120)
+++ trunk/Source/_javascript_Core/b3/air/AirInst.h 2015-11-06 23:34:31 UTC (rev 192121)
@@ -151,6 +151,9 @@
// implied by the second argument.
bool hasNonArgEffects();
+ // Tells you if this operation has arg effects.
+ bool hasArgEffects();
+
// Generate some code for this instruction. This is, like, literally our backend. If this is the
// terminal, it returns the jump that needs to be linked for the "then" case, with the "else"
// case being fall-through. This function is auto-generated by opcode_generator.rb.
Modified: trunk/Source/_javascript_Core/b3/air/AirLiveness.h (192120 => 192121)
--- trunk/Source/_javascript_Core/b3/air/AirLiveness.h 2015-11-06 23:20:12 UTC (rev 192120)
+++ trunk/Source/_javascript_Core/b3/air/AirLiveness.h 2015-11-06 23:34:31 UTC (rev 192121)
@@ -57,6 +57,8 @@
for (size_t blockIndex = code.size(); blockIndex--;) {
BasicBlock* block = code.at(blockIndex);
+ if (!block)
+ continue;
LocalCalc localCalc(*this, block);
for (size_t instIndex = block->size(); instIndex--;)
localCalc.execute(block->at(instIndex));
Modified: trunk/Source/_javascript_Core/b3/air/AirOpcode.opcodes (192120 => 192121)
--- trunk/Source/_javascript_Core/b3/air/AirOpcode.opcodes 2015-11-06 23:20:12 UTC (rev 192120)
+++ trunk/Source/_javascript_Core/b3/air/AirOpcode.opcodes 2015-11-06 23:34:31 UTC (rev 192121)
@@ -294,7 +294,7 @@
Ret /terminal
-Breakpoint /effects
+Oops /terminal
# Air allows for exotic behavior. A Patch's behavior is determined entirely by the Special operand,
# which must be the first operand.
Added: trunk/Source/_javascript_Core/b3/air/AirSimplifyCFG.cpp (0 => 192121)
--- trunk/Source/_javascript_Core/b3/air/AirSimplifyCFG.cpp (rev 0)
+++ trunk/Source/_javascript_Core/b3/air/AirSimplifyCFG.cpp 2015-11-06 23:34:31 UTC (rev 192121)
@@ -0,0 +1,169 @@
+/*
+ * 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().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->replacePredecessor(successor, block);
+ successor = newSuccessor;
+ changed = true;
+ }
+ }
+ }
+
+ // Now check if the block's terminal can be replaced with a jump.
+ if (block->numSuccessors() > 1) {
+ // The terminal must not have weird effects.
+ if (!block->last().hasArgEffects()
+ && !block->last().hasNonArgNonControlEffects()) {
+ // 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);
+ changed = true;
+ }
+ }
+ }
+
+ // Finally handle jumps to a block with one predecessor.
+ if (block->numSuccessors() == 1) {
+ 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(WTF::move(inst));
+
+ // Make sure that our successors are the successor's successors.
+ block->successors() = WTF::move(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)
+
+
Added: trunk/Source/_javascript_Core/b3/air/AirSimplifyCFG.h (0 => 192121)
--- trunk/Source/_javascript_Core/b3/air/AirSimplifyCFG.h (rev 0)
+++ trunk/Source/_javascript_Core/b3/air/AirSimplifyCFG.h 2015-11-06 23:34:31 UTC (rev 192121)
@@ -0,0 +1,44 @@
+/*
+ * 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.
+ */
+
+#ifndef AirSimplifyCFG_h
+#define AirSimplifyCFG_h
+
+#if ENABLE(B3_JIT)
+
+namespace JSC { namespace B3 { namespace Air {
+
+class Code;
+
+// Simplifies the control flow graph by removing jump-only blocks and merging jumps.
+
+bool simplifyCFG(Code&);
+
+} } } // namespace JSC::B3::Air
+
+#endif // ENABLE(B3_JIT)
+
+#endif // AirSimplifyCFG_h
+
