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

[commits at source.squeak.org]

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

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

Name: Cog-eem.348
Author: eem
Time: 2 January 2019, 8:28:03.575104 pm
UUID: 3e6104dd-f9dc-471d-bdb9-c2583c7c20b3
Ancestors: Cog-eem.347

Add DominatorFinder, a simple InstructionStream subclass to help demonstrate that dominating conditional branches can be found using a simple FSM.

=============== Diff against Cog-eem.347 ===============

Item was changed:
  SystemOrganization addCategory: #'Cog-Bootstrapping'!
+ SystemOrganization addCategory: #'Cog-Explorations'!
  SystemOrganization addCategory: #'Cog-Morphing Bytecode Set'!
  SystemOrganization addCategory: #'Cog-ProcessorPlugins'!
  SystemOrganization addCategory: #'Cog-Processors'!
  SystemOrganization addCategory: #'Cog-Processors-Tests'!
  SystemOrganization addCategory: #'Cog-Scripting'!
  SystemOrganization addCategory: #'Cog-Scripts'!
  SystemOrganization addCategory: #'Cog-Tests'!

Item was added:
+ InstructionStream subclass: #DominatorFinder
+ 	instanceVariableNames: 'cameFroms dominators encoderClass thisInstruction previousInstruction jumpTarget thisPC targets'
+ 	classVariableNames: 'ReturnSelectors'
+ 	poolDictionaries: ''
+ 	category: 'Cog-Explorations'!
+ 
+ !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)
+ 
+ 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 added:
+ ----- Method: DominatorFinder class>>initialize (in category 'class initialization') -----
+ initialize
+ 	"self initialize"
+ 	ReturnSelectors := ((self systemNavigation allCallsOn: #return:from: localTo: Context) collect: [:mr| mr selector]) as: IdentitySet.!

Item was added:
+ ----- Method: DominatorFinder>>doesNotUnderstand: (in category 'message handling') -----
+ doesNotUnderstand: aMessage
+ 	self recordThisInstruction: aMessage!

Item was added:
+ ----- Method: DominatorFinder>>dominators (in category 'accessing') -----
+ dominators
+ 	"Scan to find the dominating conditional branches."
+ 	| end |
+ 	end := self method endPC.
+ 	[pc <= end] whileTrue:
+ 		[self interpretNextInstructionFor: self].
+ 	^dominators!

Item was added:
+ ----- 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 branch dominates the target of the unconditional branch"
+ 		previousInstruction == #jump:
+ 			ifTrue:
+ 		 		[(jumpTarget >= pc
+ 				  and: [(targets includes: jumpTarget) not]) ifTrue:
+ 					[dominators at: cameFromPC put: jumpTarget.
+ 					 targets add: jumpTarget]]
+ 			ifFalse:
+ 				[(targets includes: pc) ifFalse:
+ 					[dominators at: cameFromPC put: pc.
+ 					 targets add: pc]]].
+ 	thisPC := pc.
+ 	result := encoderClass interpretNextInstructionFor: client in: self.
+ 	previousInstruction := thisInstruction!

Item was added:
+ ----- Method: DominatorFinder>>isReturn: (in category 'private') -----
+ isReturn: aMessageSelector
+ 	^ReturnSelectors includes: aMessageSelector!

Item was added:
+ ----- Method: DominatorFinder>>jump: (in category 'instruction decoding') -----
+ jump: distance
+ 	jumpTarget := pc + distance.
+ 	self recordThisInstruction: (Message selector: #jump: argument: distance)!

Item was added:
+ ----- Method: DominatorFinder>>jump:if: (in category 'instruction decoding') -----
+ jump: distance if: condition
+ 	| target |
+ 	target := pc + distance.
+ 	(cameFroms at: target)
+ 		ifNil: [cameFroms at: target put: thisPC]
+ 		ifNotNil: [:cameFromPC| self assert: cameFromPC < thisPC].
+ 	self recordThisInstruction: (Message selector: #jump: argument: distance)!

Item was added:
+ ----- Method: DominatorFinder>>method:pc: (in category 'private') -----
+ method: method pc: startpc
+ 	super method: method pc: startpc.
+ 	cameFroms := Array new: method endPC.
+ 	encoderClass := method encoderClass.
+ 	dominators := Dictionary new.
+ 	targets := Set new!

Item was added:
+ ----- Method: DominatorFinder>>recordThisInstruction: (in category 'private') -----
+ recordThisInstruction: aMessage
+ 	thisInstruction := aMessage selector!