[Vm-dev] VM Maker: Cog-eem.351.mcz

commits at source.squeak.org commits at source.squeak.org
Sat Jan 5 03:00:31 UTC 2019 

Eliot Miranda uploaded a new version of Cog to project VM Maker:
http://source.squeak.org/VMMaker/Cog-eem.351.mcz

==================== Summary ====================

Name: Cog-eem.351
Author: eem
Time: 4 January 2019, 7:00:29.067063 pm
UUID: 138aec54-2135-458c-883a-3e1dd633a590
Ancestors: Cog-eem.350

Extend DominatorFinder to handle full blocks.
Fix its handling of conditional branch targets preceded by backward jumps (i.e. loops).
Beef up isEmptyIf to deal with expr ifTrue: [leaf].
Fix a slip in lastBlockOfOptimizedConditional

=============== Diff against Cog-eem.350 ===============

Item was changed:
  InstructionStream subclass: #DominatorFinder
  	instanceVariableNames: 'cameFroms dominators encoderClass thisInstruction previousInstruction jumpTarget thisPC'
  	classVariableNames: 'ReturnSelectors'
  	poolDictionaries: ''
  	category: 'Cog-Explorations'!
  
+ !DominatorFinder commentStamp: 'eem 1/4/2019 08:17' prior: 0!
- !DominatorFinder commentStamp: 'eem 1/2/2019 20:26' prior: 0!
  A DominatorFinder is an InstructionStream that finds the dominators of bytecodes.  Specifically it aims to find the dominating conditional branches for join points.  This is part of the register allocation problem, to know the common height of the stack at a join point.  Only items above the common height need to be merged.
  
  I believe finding dominators in bytecode can be done with a simple scan using an FSM, e.g. in scanMethod.  This class is part of an experiment to find out if I'm right.
  
  I observe that
  - the first conditional branch that branches to a target that is preceded by an unconditional branch dominates the target of the unconditional branch
  - if no conditional branch that branches to a target, branches to a target preceded by an unconditional branch (i.e. all are preceded by returns) then the first conditional branch dominates the target
  - a conditional branch that branches to a target preceded by a backward branch dominates its target (loops)
  
+ This DominatorFinder attempts to find conditional branches that dominate join points, while filtering out conditional branches that dominate non-joins (i.e. those following single returning ifs and those that jump to the end of loops).
+ 
  Instance Variables
  	cameFroms:			<Array>
  	dominators:			<Dictionary>
  	encoderClass:			<BytecodeEncoder>
  	previousInstruction:	<Symbol>
  	thisInstruction:			<Symbol>
  	thisPC:					<Integer>
  
  cameFroms
  	- the pcs of dominating conditional branches
  
  dominators
  	- dictionary of dominating pc to dominated pc
  
  encoderClass
  	- the encoderClass for the current method
  
  previousInstruction
  	- the selector of the Message for the previous bytecode during the scan
  
  thisInstruction
  	- the selector of the Message for the current bytecode during the scan
  
  thisPC
  	- the pc for the current bytecode during the scan
  !

Item was changed:
  ----- Method: DominatorFinder class>>dominatorTupleForMethod: (in category 'exploration') -----
  dominatorTupleForMethod: aCompiledMethod
  	"Answer a tuple of
  		dominating optimized nodes, (inlined if's that are found by DominatorFinder)
  		anomalous optimized nodes, (inlined if's that are not found by DominatorFinder)
+ 		dominated nodes, (inlined if's nested within other inlined if's that occur at the end of a basic block and hence jump to the same place as their parent)
+ 		dominator pcs (the dominator pcs found by the DominatorFinder)
+ 	 for aCompiledMethod.  It is expected that the anomaloius nodes should be empty."
+ 	| mn optimizedNodes
+ 	  dominators offenders dominated dominatorPCs |
- 		dominated nodes, (inlined if's nested within other inlined if's that occur at teh end of a basic block and hence jump to the same oplacfe as their parent)
- 		dominator pcs (the dominatopr pcs found by the DominatorFinder)
- 	 for aCompiledMethod"
- 	| mn dominators offenders dominatorPCs dominated |
  	mn := CompiledMethod
  			noCheckSetPreferredBytecodeSetTo: aCompiledMethod encoderClass
  			while:
+ 				[[:c :s|
+ 				  [c compile:(c sourceCodeAt: s)
- 				[[:c :s| c compile:(c sourceCodeAt: s)
  					environment: c environment
  					notifying: nil
  					trailer: aCompiledMethod trailer 
+ 					ifFail: [nil]]
+ 					on: SyntaxErrorNotification
+ 					do: [^#(#() #() #() #())]]
+ 						value: aCompiledMethod methodClass
+ 						value: aCompiledMethod selector].
+ 	"mn method ~= aCompiledMethod ifTrue:
+ 		[Transcript cr; show: 'warning: recompilation of ', aCompiledMethod reference, ' generated different code'.
+ 		 ^#(#() #() #() #())]."
+ 	dominatorPCs := (self on: mn method) dominators.
+ 	dominated := IdentitySet new. "The last statement of an inlined if cannot dominate the join of its enclosing if"
+ 	optimizedNodes := OrderedCollection new. "Avoid double traversal"
- 					ifFail: [nil]] value: aCompiledMethod methodClass value: aCompiledMethod selector].
- 	dominatorPCs := (self on: aCompiledMethod) dominators.
- 	dominated := Set new. "The last statement of an inlined if cannot dominate the join of its enclosing if"
  	mn node nodesDo:
  		[:n| | lastStatement |
+ 		(n isMessage and: [n isOptimized]) ifTrue:
+ 			[optimizedNodes addLast: n.
+ 			 n isOptimizedConditional ifTrue:
+ 				[lastStatement := n lastBlockOfOptimizedConditional statements last.
+ 				(lastStatement isMessage and: [lastStatement isOptimizedConditional]) ifTrue:
+ 					[dominated add: lastStatement]]]].
+ 	dominators := OrderedCollection new: optimizedNodes size.
+ 	offenders := OrderedCollection new: optimizedNodes size.
+ 	optimizedNodes do:
- 		(n isMessage and: [n isOptimizedConditional]) ifTrue:
- 			[lastStatement := n lastBlockOfOptimizedConditional statements last.
- 			(lastStatement isMessage and: [lastStatement isOptimizedConditional]) ifTrue:
- 				[dominated add: lastStatement]]].
- 	dominators := OrderedCollection new.
- 	offenders := OrderedCollection new.
- 	mn node nodesDo:
  		[:n|
+ 		(n isOptimizedLoop not				"Loop CBs do dominate, but their target is not a join point"
+ 		 and: [n isSingleReturningIf not		"ifTrue: [^foo] CBs do dominate but their target is not a join point"
+ 		 and: [n isEmptyIf not				"ifTrue: [] generates no code"
+ 		 and: [n pc ~= 0					"caseOf: nodes get assigned a pc of 0; go figure..."
+ 		 and: [(dominated includes: n) not]]]]) ifTrue:
- 		(n isMessage and: [n isOptimized and: [n isSingleReturningIf not and: [(dominated includes: n) not]]]) ifTrue:
  			[((dominatorPCs at: n pc ifAbsent: nil)
  				ifNil: [offenders]
  				ifNotNil: [dominators]) addLast: n]].
  	^{ dominators. offenders. dominated. dominatorPCs }!

Item was changed:
  ----- Method: DominatorFinder>>interpretNextInstructionFor: (in category 'decoding') -----
  interpretNextInstructionFor: client
  	| result |
  	(cameFroms at: pc) ifNotNil:
  		[:cameFromPC|
+ 		"the first conditional branch that branches to a target that is preceded by an unconditional forward branch dominates the target of the unconditional branch.
+ 		 (an unconditional backward branch indicates a loop)"
+ 		(previousInstruction == #jump:
+ 		 and: [jumpTarget >= pc])
- 		"the first conditional branch that branches to a target that is preceded by an unconditional branch dominates the target of the unconditional branch"
- 		previousInstruction == #jump:
  			ifTrue:
+ 		 		[(cameFroms at: jumpTarget) ifNil:
- 		 		[(jumpTarget >= pc
- 				  and: [(cameFroms at: jumpTarget) isNil]) ifTrue:
  					[self assert: (dominators includesKey: cameFromPC) not.
  					 dominators at: cameFromPC put: jumpTarget]]
  			ifFalse:
  				"the first conditional branch that branches to a target not preceded by an unconditional branch dominates the target of the conditional branch"
  				[(dominators at: cameFromPC ifAbsent: nil) ifNil:
  					[dominators at: cameFromPC put: pc]]].
  	thisPC := pc.
  	result := encoderClass interpretNextInstructionFor: client in: self.
  	previousInstruction := thisInstruction!

Item was added:
+ ----- Method: DominatorFinder>>pushFullClosure:numCopied: (in category 'instruction decoding') -----
+ pushFullClosure: aCompiledBlock numCopied: numCopied
+ 	self recordThisInstruction: #pushFullClosure:numCopied:;
+ 		recurseIntoBlock: aCompiledBlock!

Item was added:
+ ----- Method: DominatorFinder>>pushFullClosure:numCopied:receiverOnStack:ignoreOuterContext: (in category 'instruction decoding') -----
+ pushFullClosure: aCompiledBlock numCopied: numCopied receiverOnStack: rcvrOnStack ignoreOuterContext: ignoreOuterContext
+ 	self recordThisInstruction: #pushFullClosure:numCopied:receiverOnStack:ignoreOuterContext:;
+ 		recurseIntoBlock: aCompiledBlock!

Item was added:
+ ----- Method: DominatorFinder>>recurseIntoBlock: (in category 'private') -----
+ recurseIntoBlock: aCompiledBlock
+ 	"Recurse into a full block. Map its dominating pcs appropriately to match
+ 	 BytecodeEncoder>>nextPC's representyation for the pcs in nested full blocks."
+ 	(self class on: aCompiledBlock) dominators keysAndValuesDo:
+ 		[:key :value|
+ 		 dominators
+ 			at: (key isInteger ifTrue: [aCompiledBlock -> key] ifFalse: [key])
+ 			put: value]!

Item was added:
+ ----- Method: MessageNode>>isEmptyIf (in category '*Cog-Explorations-testing') -----
+ isEmptyIf
+ 	| block |
+ 	^((special between: 1 and: 2) "ifTrue:/ifFalse:"
+ 	    or: [special between: 15 and: 16]) "ifNil:/ifNotNil:"
+ 		and: [((block := self lastBlockOfOptimizedConditional) isJust: NodeNil)
+ 			or: [block returns not and: [block statements size = 1 and: [block statements first isLeaf]]]]!

Item was changed:
  ----- Method: MessageNode>>lastBlockOfOptimizedConditional (in category '*Cog-Explorations-testing') -----
  lastBlockOfOptimizedConditional
  	"Answer the actual last block for an inlined conditional"
  
  	^special >= 1 ifTrue:
+ 		[special <= 2 ifTrue: [^arguments at: special].	"ifTrue: ifFalse:"
- 		[special <= 2 ifTrue: [^arguments first].	"ifTrue: ifFalse:"
  		 special <= 4 ifTrue: [^arguments last].	"ifTrue:ifFalse: ifFalse:ifTrue:"
  		 special <= 6 ifTrue: [^arguments first].	"and: or:"
  		 special <= 14 ifTrue: [^nil].
  		 special <= 16 ifTrue: [^arguments first].	"ifNil: ifNotNil:"
  		 special <= 18 ifTrue: [^arguments last]]	"ifNil:ifNotNil: ifNotNil:ifNil:"!

More information about the Vm-dev mailing list