Changeset 192121 in webkit
- Timestamp:
- Nov 6, 2015 3:34:31 PM (8 years ago)
- Location:
- trunk/Source/JavaScriptCore
- Files:
-
- 2 added
- 14 edited
Legend:
- Unmodified
- Added
- Removed
-
trunk/Source/JavaScriptCore/ChangeLog
r192093 r192121 1 2015-11-06 Filip Pizlo <fpizlo@apple.com> 2 3 B3 and Air should simplify CFGs 4 https://bugs.webkit.org/show_bug.cgi?id=150960 5 6 Reviewed by Geoffrey Garen. 7 8 This adds CFG simplification to both B3 and Air. 9 10 In B3, the simplification is done inside the B3::reduceStrength() fixpoint because we expect 11 that it will help to reveal more optimization opportunities. This is going to be particularly 12 true when we add Phi elimination. 13 14 In Air, the simplification is its own phase. We expect it to produce most of its benefits once 15 we have coalescing. Then, CFG simplification in Air will unbreak critial edges. 16 17 * JavaScriptCore.xcodeproj/project.pbxproj: 18 * assembler/AbortReason.h: 19 * assembler/MacroAssembler.h: 20 (JSC::MacroAssembler::oops): Reveal this as a method so that we can have an Oops instruction. 21 * b3/B3BasicBlock.h: 22 (JSC::B3::BasicBlock::predecessor): 23 (JSC::B3::BasicBlock::predecessors): 24 (JSC::B3::BasicBlock::containsPredecessor): 25 * b3/B3BasicBlockUtils.h: Bunch of fixes for blocks being killed. 26 (JSC::B3::replacePredecessor): 27 (JSC::B3::resetReachability): 28 * b3/B3ReduceStrength.cpp: Implement B3 CFG simplification. 29 * b3/B3ReduceStrength.h: 30 * b3/air/AirBasicBlock.h: 31 (JSC::B3::Air::BasicBlock::resize): 32 (JSC::B3::Air::BasicBlock::insts): 33 (JSC::B3::Air::BasicBlock::appendInst): 34 (JSC::B3::Air::BasicBlock::containsPredecessor): 35 * b3/air/AirGenerate.cpp: 36 (JSC::B3::Air::generate): 37 * b3/air/AirInst.cpp: 38 (JSC::B3::Air::Inst::hasArgEffects): 39 (JSC::B3::Air::Inst::dump): 40 * b3/air/AirInst.h: 41 * b3/air/AirLiveness.h: 42 (JSC::B3::Air::Liveness::Liveness): Fix for when blocks were killed. 43 * b3/air/AirOpcode.opcodes: 44 * b3/air/AirSimplifyCFG.cpp: Added. 45 (JSC::B3::Air::simplifyCFG): 46 * b3/air/AirSimplifyCFG.h: Added. 47 1 48 2015-11-05 Nikos Andronikos <nikos.andronikos-webkit@cisra.canon.com.au> 2 49 -
trunk/Source/JavaScriptCore/JavaScriptCore.xcodeproj/project.pbxproj
r191994 r192121 281 281 0F32BD101BB34F190093A57F /* HeapHelperPool.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F32BD0E1BB34F190093A57F /* HeapHelperPool.cpp */; }; 282 282 0F32BD111BB34F190093A57F /* HeapHelperPool.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F32BD0F1BB34F190093A57F /* HeapHelperPool.h */; }; 283 0F338DF91BE96AA80013C88F /* B3CCallValue.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F338DF71BE96AA80013C88F /* B3CCallValue.cpp */; };284 0F338DFA1BE96AA80013C88F /* B3CCallValue.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F338DF81BE96AA80013C88F /* B3CCallValue.h */; };285 283 0F338DF11BE93AD10013C88F /* B3StackmapValue.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F338DEF1BE93AD10013C88F /* B3StackmapValue.cpp */; }; 286 284 0F338DF21BE93AD10013C88F /* B3StackmapValue.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F338DF01BE93AD10013C88F /* B3StackmapValue.h */; }; 287 285 0F338DF51BE93D550013C88F /* B3ConstrainedValue.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F338DF31BE93D550013C88F /* B3ConstrainedValue.cpp */; }; 288 286 0F338DF61BE93D550013C88F /* B3ConstrainedValue.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F338DF41BE93D550013C88F /* B3ConstrainedValue.h */; }; 287 0F338DF91BE96AA80013C88F /* B3CCallValue.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F338DF71BE96AA80013C88F /* B3CCallValue.cpp */; }; 288 0F338DFA1BE96AA80013C88F /* B3CCallValue.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F338DF81BE96AA80013C88F /* B3CCallValue.h */; }; 289 0F338DFD1BED51270013C88F /* AirSimplifyCFG.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F338DFB1BED51270013C88F /* AirSimplifyCFG.cpp */; }; 290 0F338DFE1BED51270013C88F /* AirSimplifyCFG.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F338DFC1BED51270013C88F /* AirSimplifyCFG.h */; }; 289 291 0F34B14916D42010001CDA5A /* DFGUseKind.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F34B14716D4200E001CDA5A /* DFGUseKind.cpp */; }; 290 292 0F34B14A16D42013001CDA5A /* DFGUseKind.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F34B14816D4200E001CDA5A /* DFGUseKind.h */; }; … … 2304 2306 0F32BD0E1BB34F190093A57F /* HeapHelperPool.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = HeapHelperPool.cpp; sourceTree = "<group>"; }; 2305 2307 0F32BD0F1BB34F190093A57F /* HeapHelperPool.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = HeapHelperPool.h; sourceTree = "<group>"; }; 2306 0F338DF71BE96AA80013C88F /* B3CCallValue.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = B3CCallValue.cpp; path = b3/B3CCallValue.cpp; sourceTree = "<group>"; };2307 0F338DF81BE96AA80013C88F /* B3CCallValue.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = B3CCallValue.h; path = b3/B3CCallValue.h; sourceTree = "<group>"; };2308 2308 0F338DEF1BE93AD10013C88F /* B3StackmapValue.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = B3StackmapValue.cpp; path = b3/B3StackmapValue.cpp; sourceTree = "<group>"; }; 2309 2309 0F338DF01BE93AD10013C88F /* B3StackmapValue.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = B3StackmapValue.h; path = b3/B3StackmapValue.h; sourceTree = "<group>"; }; 2310 2310 0F338DF31BE93D550013C88F /* B3ConstrainedValue.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = B3ConstrainedValue.cpp; path = b3/B3ConstrainedValue.cpp; sourceTree = "<group>"; }; 2311 2311 0F338DF41BE93D550013C88F /* B3ConstrainedValue.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = B3ConstrainedValue.h; path = b3/B3ConstrainedValue.h; sourceTree = "<group>"; }; 2312 0F338DF71BE96AA80013C88F /* B3CCallValue.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = B3CCallValue.cpp; path = b3/B3CCallValue.cpp; sourceTree = "<group>"; }; 2313 0F338DF81BE96AA80013C88F /* B3CCallValue.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = B3CCallValue.h; path = b3/B3CCallValue.h; sourceTree = "<group>"; }; 2314 0F338DFB1BED51270013C88F /* AirSimplifyCFG.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = AirSimplifyCFG.cpp; path = b3/air/AirSimplifyCFG.cpp; sourceTree = "<group>"; }; 2315 0F338DFC1BED51270013C88F /* AirSimplifyCFG.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = AirSimplifyCFG.h; path = b3/air/AirSimplifyCFG.h; sourceTree = "<group>"; }; 2312 2316 0F34B14716D4200E001CDA5A /* DFGUseKind.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = DFGUseKind.cpp; path = dfg/DFGUseKind.cpp; sourceTree = "<group>"; }; 2313 2317 0F34B14816D4200E001CDA5A /* DFGUseKind.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = DFGUseKind.h; path = dfg/DFGUseKind.h; sourceTree = "<group>"; }; … … 4525 4529 0F45703A1BE45F0A0062A629 /* AirReportUsedRegisters.cpp */, 4526 4530 0F45703B1BE45F0A0062A629 /* AirReportUsedRegisters.h */, 4531 0F338DFB1BED51270013C88F /* AirSimplifyCFG.cpp */, 4532 0F338DFC1BED51270013C88F /* AirSimplifyCFG.h */, 4527 4533 0FEC85621BDACDC70080FF74 /* AirSpecial.cpp */, 4528 4534 0FEC85631BDACDC70080FF74 /* AirSpecial.h */, … … 6768 6774 0F7B294B14C3CD2F007C3DB1 /* DFGCapabilities.h in Headers */, 6769 6775 0FFFC95814EF90A200C72532 /* DFGCFAPhase.h in Headers */, 6776 0F338DFE1BED51270013C88F /* AirSimplifyCFG.h in Headers */, 6770 6777 0F3B3A281544C997003ED0FF /* DFGCFGSimplificationPhase.h in Headers */, 6771 6778 0F9D36951AE9CC33000D4DFB /* DFGCleanUpPhase.h in Headers */, … … 8487 8494 A5FD0075189B038C00633231 /* IdentifiersFactory.cpp in Sources */, 8488 8495 C25F8BCD157544A900245B71 /* IncrementalSweeper.cpp in Sources */, 8496 0F338DFD1BED51270013C88F /* AirSimplifyCFG.cpp in Sources */, 8489 8497 0F13E04E16164A1F00DC8DE7 /* IndexingType.cpp in Sources */, 8490 8498 0F0A75221B94BFA900110660 /* InferredType.cpp in Sources */, -
trunk/Source/JavaScriptCore/assembler/AbortReason.h
r189999 r192121 49 49 AHTypeInfoInlineTypeFlagsAreValid = 140, 50 50 AHTypeInfoIsValid = 150, 51 B3Oops = 155, 51 52 DFGBailedAtTopOfBlock = 161, 52 53 DFGBailedAtEndOfNode = 162, -
trunk/Source/JavaScriptCore/assembler/MacroAssembler.h
r192072 r192121 473 473 } 474 474 475 void oops() 476 { 477 abortWithReason(B3Oops); 478 } 479 475 480 static const unsigned BlindingModulus = 64; 476 481 bool shouldConsiderBlinding() -
trunk/Source/JavaScriptCore/b3/B3BasicBlock.h
r191865 r192121 89 89 const PredecessorList& predecessors() const { return m_predecessors; } 90 90 PredecessorList& predecessors() { return m_predecessors; } 91 bool containsPredecessor(BasicBlock* block) { return m_predecessors.contains(block); } 91 92 92 93 bool addPredecessor(BasicBlock*); -
trunk/Source/JavaScriptCore/b3/B3BasicBlockUtils.h
r191816 r192121 65 65 bool replacePredecessor(BasicBlock* block, BasicBlock* from, BasicBlock* to) 66 66 { 67 auto& predecessors = block->predecessors(); 68 for (unsigned i = 0; i < predecessors.size(); ++i) { 69 if (predecessors[i] == from) { 70 predecessors[i] = to; 71 return true; 72 } 73 } 74 return false; 67 bool changed = false; 68 // We do it this way because 'to' may already be a predecessor of 'block'. 69 changed |= removePredecessor(block, from); 70 changed |= addPredecessor(block, to); 71 return changed; 75 72 } 76 73 … … 81 78 { 82 79 // Clear all predecessor lists first. 83 for (auto& block : blocks) 84 block->predecessors().resize(0); 80 for (auto& block : blocks) { 81 if (block) 82 block->predecessors().resize(0); 83 } 85 84 86 85 GraphNodeWorklist<BasicBlock*, IndexSet<BasicBlock>> worklist; … … 94 93 95 94 for (unsigned i = 1; i < blocks.size(); ++i) { 95 if (!blocks[i]) 96 continue; 96 97 if (blocks[i]->predecessors().isEmpty()) { 97 98 deleteFunctor(blocks[i].get()); -
trunk/Source/JavaScriptCore/b3/B3ReduceStrength.cpp
r192088 r192121 29 29 #if ENABLE(B3_JIT) 30 30 31 #include "B3BasicBlockInlines.h" 31 32 #include "B3ControlValue.h" 32 33 #include "B3IndexSet.h" … … 91 92 { 92 93 bool result = false; 94 bool first = true; 93 95 unsigned index = 0; 94 96 do { 95 97 m_changed = false; 96 98 m_changedCFG = false; 97 98 if (verbose) { 99 dataLog("Reduce strength IR before iteration #", ++index, "\n"); 99 ++index; 100 101 if (first) 102 first = false; 103 else if (verbose) { 104 dataLog("B3 after iteration #", index - 1, " of reduceStrength:\n"); 100 105 dataLog(m_proc); 101 106 } … … 108 113 m_insertionSet.execute(m_block); 109 114 } 115 116 simplifyCFG(); 110 117 111 118 if (m_changedCFG) { … … 546 553 // Into this: Jump(else) 547 554 if (triState == FalseTriState) { 555 branch->taken().block()->removePredecessor(m_block); 548 556 branch->convertToJump(branch->notTaken()); 549 557 m_changedCFG = true; … … 554 562 // Into this: Jump(then) 555 563 if (triState == TrueTriState) { 564 branch->notTaken().block()->removePredecessor(m_block); 556 565 branch->convertToJump(branch->taken()); 557 566 m_changedCFG = true; … … 619 628 } 620 629 return false; 630 } 631 632 void simplifyCFG() 633 { 634 // We have three easy simplification rules: 635 // 636 // 1) If a successor is a block that just jumps to another block, then jump directly to 637 // that block. 638 // 639 // 2) If all successors are the same and the operation has no effects, then use a jump 640 // instead. 641 // 642 // 3) If you jump to a block that is not you and has one predecessor, then merge. 643 // 644 // Note that because of the first rule, this phase may introduce critical edges. That's fine. 645 // If you need broken critical edges, then you have to break them yourself. 646 647 // Note that this relies on predecessors being at least conservatively correct. It's fine for 648 // predecessors to mention a block that isn't actually a predecessor. It's *not* fine for a 649 // predecessor to be omitted. We assert as much in the loop. In practice, we precisely preserve 650 // predecessors during strength reduction since that minimizes the total number of fixpoint 651 // iterations needed to kill a lot of code. 652 653 for (BasicBlock* block : m_proc) { 654 checkPredecessorValidity(); 655 656 // We don't care about blocks that don't have successors. 657 if (!block->numSuccessors()) 658 continue; 659 660 // First check if any of the successors of this block can be forwarded over. 661 for (BasicBlock*& successor : block->successorBlocks()) { 662 if (successor != block 663 && successor->size() == 1 664 && successor->last()->opcode() == Jump) { 665 BasicBlock* newSuccessor = successor->successorBlock(0); 666 if (newSuccessor != successor) { 667 newSuccessor->replacePredecessor(successor, block); 668 successor = newSuccessor; 669 m_changedCFG = true; 670 } 671 } 672 } 673 674 // Now check if the block's terminal can be replaced with a jump. 675 if (block->numSuccessors() > 1) { 676 // The terminal must not have weird effects. 677 Effects effects = block->last()->effects(); 678 effects.terminal = false; 679 if (!effects.mustExecute()) { 680 // All of the successors must be the same. 681 bool allSame = true; 682 FrequentedBlock firstSuccessor = block->successor(0); 683 for (unsigned i = 1; i < block->numSuccessors(); ++i) { 684 if (block->successorBlock(i) != firstSuccessor.block()) { 685 allSame = false; 686 break; 687 } 688 } 689 if (allSame) { 690 block->last()->as<ControlValue>()->convertToJump(firstSuccessor); 691 m_changedCFG = true; 692 } 693 } 694 } 695 696 // Finally handle jumps to a block with one predecessor. 697 if (block->numSuccessors() == 1) { 698 BasicBlock* successor = block->successorBlock(0); 699 if (successor != block && successor->numPredecessors() == 1) { 700 RELEASE_ASSERT(successor->predecessor(0) == block); 701 702 // We can merge the two blocks, because the predecessor only jumps to the successor 703 // and the successor is only reachable from the predecessor. 704 705 // Remove the terminal. 706 Value* value = block->values().takeLast(); 707 Origin jumpOrigin = value->origin(); 708 RELEASE_ASSERT(value->as<ControlValue>()); 709 m_proc.deleteValue(value); 710 711 // Append the full contents of the successor to the predecessor. 712 block->values().appendVector(successor->values()); 713 714 // Make sure that the successor has nothing left in it. Make sure that the block 715 // has a terminal so that nobody chokes when they look at it. 716 successor->values().resize(0); 717 successor->appendNew<ControlValue>(m_proc, Oops, jumpOrigin); 718 719 // Ensure that predecessors of block's new successors know what's up. 720 for (BasicBlock* newSuccessor : block->successorBlocks()) 721 newSuccessor->replacePredecessor(successor, block); 722 m_changedCFG = true; 723 } 724 } 725 } 726 727 if (m_changedCFG && verbose) { 728 dataLog("B3 after simplifyCFG:\n"); 729 dataLog(m_proc); 730 } 731 } 732 733 void checkPredecessorValidity() 734 { 735 if (!shouldValidateIRAtEachPhase()) 736 return; 737 738 for (BasicBlock* block : m_proc) { 739 for (BasicBlock* successor : block->successorBlocks()) 740 RELEASE_ASSERT(successor->containsPredecessor(block)); 741 } 621 742 } 622 743 -
trunk/Source/JavaScriptCore/b3/B3ReduceStrength.h
r191705 r192121 33 33 class Procedure; 34 34 35 // Does strength reduction, constant folding, and canonicalization. In the future we may also have it36 // do CSE.35 // Does strength reduction, constant folding, canonicalization, CFG simplification, and DCE. In the 36 // future we may also have it do CSE. 37 37 38 38 bool reduceStrength(Procedure&); -
trunk/Source/JavaScriptCore/b3/air/AirBasicBlock.h
r191846 r192121 66 66 void resize(unsigned size) { m_insts.resize(size); } 67 67 68 const InstList& insts() const { return m_insts; } 69 InstList& insts() { return m_insts; } 70 68 71 template<typename Inst> 69 72 void appendInst(Inst&& inst) … … 106 109 bool removePredecessor(BasicBlock*); 107 110 bool replacePredecessor(BasicBlock* from, BasicBlock* to); 111 bool containsPredecessor(BasicBlock* predecessor) const { return m_predecessors.contains(predecessor); } 108 112 109 113 void dump(PrintStream&) const; -
trunk/Source/JavaScriptCore/b3/air/AirGenerate.cpp
r191865 r192121 35 35 #include "AirHandleCalleeSaves.h" 36 36 #include "AirReportUsedRegisters.h" 37 #include "AirSimplifyCFG.h" 37 38 #include "AirSpillEverything.h" 38 39 #include "AirValidate.h" … … 79 80 // shouldn't have to worry about this very much. 80 81 allocateStack(code); 82 83 // If we coalesced moves then we can unbreak critical edges. This is the main reason for this 84 // phase. 85 simplifyCFG(code); 81 86 82 87 // FIXME: We should really have a code layout optimization here. -
trunk/Source/JavaScriptCore/b3/air/AirInst.cpp
r191705 r192121 29 29 #if ENABLE(B3_JIT) 30 30 31 #include "AirInstInlines.h" 31 32 #include "B3Value.h" 32 33 #include <wtf/ListDump.h> 33 34 34 35 namespace JSC { namespace B3 { namespace Air { 36 37 bool Inst::hasArgEffects() 38 { 39 bool result = false; 40 forEachArg( 41 [&] (Arg&, Arg::Role role, Arg::Type) { 42 if (Arg::isDef(role)) 43 result = true; 44 }); 45 return result; 46 } 35 47 36 48 void Inst::dump(PrintStream& out) const -
trunk/Source/JavaScriptCore/b3/air/AirInst.h
r192072 r192121 152 152 bool hasNonArgEffects(); 153 153 154 // Tells you if this operation has arg effects. 155 bool hasArgEffects(); 156 154 157 // Generate some code for this instruction. This is, like, literally our backend. If this is the 155 158 // terminal, it returns the jump that needs to be linked for the "then" case, with the "else" -
trunk/Source/JavaScriptCore/b3/air/AirLiveness.h
r191865 r192121 58 58 for (size_t blockIndex = code.size(); blockIndex--;) { 59 59 BasicBlock* block = code.at(blockIndex); 60 if (!block) 61 continue; 60 62 LocalCalc localCalc(*this, block); 61 63 for (size_t instIndex = block->size(); instIndex--;) -
trunk/Source/JavaScriptCore/b3/air/AirOpcode.opcodes
r192072 r192121 295 295 Ret /terminal 296 296 297 Breakpoint /effects 297 Oops /terminal 298 298 299 299 # Air allows for exotic behavior. A Patch's behavior is determined entirely by the Special operand,
Note: See TracChangeset
for help on using the changeset viewer.