[Vm-dev] VM Maker: VMMaker.oscog-eem.2018.mcz

[commits at source.squeak.org]

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

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

Name: VMMaker.oscog-eem.2018
Author: eem
Time: 1 December 2016, 10:47:33.781504 am
UUID: 2ca1b9f3-8f95-4dc0-9111-acfd6f7fe95f
Ancestors: VMMaker.oscog-EstebanLorenzano.2017

RegisterAllocatingCogit:

Reimplement mergeCurrentSimStackWith: to use a better algorithm.  Implement all but the register sort/swap code.

Esteban, amen!

=============== Diff against VMMaker.oscog-EstebanLorenzano.2017 ===============

Item was added:
+ ----- Method: RegisterAllocatingCogit>>assignToTempRegConflictingRegisterIn: (in category 'bytecode generator support') -----
+ assignToTempRegConflictingRegisterIn: conflictingRegisterMask
+ 	"Find the stackEntry in simStack whose liveRegister matches conflictingRegisterMask
+ 	 and assign it to TempReg."
+ 	self assert: (self isAPowerOfTwo: conflictingRegisterMask).
+ 	0 to: simStackPtr do:
+ 		[:i|
+ 		 (self simStackAt: i) registerMaskOrNone = conflictingRegisterMask ifTrue:
+ 			[(self simStackAt: i)
+ 				storeToReg: TempReg;
+ 				liveRegister: TempReg.
+ 			 ^self]].
+ 	self error: 'conflict entry not found'!

Item was added:
+ ----- Method: RegisterAllocatingCogit>>conflcitsResolvedBetweenSimStackAnd: (in category 'bytecode generator support') -----
+ conflcitsResolvedBetweenSimStackAnd: mergeSimStack 
+ 	"There are no register conflicts between simStack and mergeSimStack if
+ 	 traversing both stacks from hot end (simStackPtr) to cold end (0) no register
+ 	 exists in simStack that has previously existed in mergeSimStack.  This is because
+ 	 the resolution assigns values from simStack to registers in mergeSimStack and so
+ 	 must not assign to a register yet to be read."
+ 	 | regsWrittenToMask |
+ 	regsWrittenToMask := 0.
+ 	simStackPtr to: 0 by: -1 do:
+ 		[:i| | mergeMask currentMask |
+ 		mergeMask := (self simStack: mergeSimStack at: i) registerMaskOrNone.
+ 		currentMask := (self simStack: simStack at: i) registerMaskOrNone.
+ 		mergeMask ~= currentMask ifTrue:
+ 			[(currentMask anyMask: regsWrittenToMask) ifTrue:
+ 				[^false]].
+ 		regsWrittenToMask := regsWrittenToMask bitOr: mergeMask].
+ 	^true!

Item was added:
+ ----- Method: RegisterAllocatingCogit>>isAPowerOfTwo: (in category 'bytecode generator support') -----
+ isAPowerOfTwo: anInteger 
+ 	<inline: true>
+ 	^(anInteger bitAnd: anInteger - 1) = 0!

Item was removed:
- ----- Method: RegisterAllocatingCogit>>liveRegistersExceptingTopNItems: (in category 'simulation stack') -----
- liveRegistersExceptingTopNItems: n
- 	| regsSet |
- 	regsSet := 0.
- 	0 to: simStackPtr - n do:
- 		[:i|
- 		regsSet := regsSet bitOr: (self simStackAt: i) registerMask].
- 	LowcodeVM ifTrue:
- 		[(simNativeSpillBase max: 0) to: simNativeStackPtr - n do:
- 			[:i|
- 			regsSet := regsSet bitOr: (self simNativeStackAt: i) nativeRegisterMask]].
- 	^regsSet!

Item was added:
+ ----- Method: RegisterAllocatingCogit>>liveRegistersExceptingTopNItems:in: (in category 'simulation stack') -----
+ liveRegistersExceptingTopNItems: n in: aSimStack
+ 	<var: 'aSimStack' type: #'SimStackEntry *'>
+ 	| regsSet |
+ 	regsSet := 0.
+ 	0 to: simStackPtr - n do:
+ 		[:i|
+ 		regsSet := regsSet bitOr: (self simStack: aSimStack at: i) registerMask].
+ 	LowcodeVM ifTrue:
+ 		[self shouldBeImplemented.
+ 		 (simNativeSpillBase max: 0) to: simNativeStackPtr - n do:
+ 			[:i|
+ 			regsSet := regsSet bitOr: (self simNativeStackAt: i) nativeRegisterMask]].
+ 	^regsSet!

Item was changed:
  ----- Method: RegisterAllocatingCogit>>mergeCurrentSimStackWith: (in category 'bytecode generator support') -----
  mergeCurrentSimStackWith: mergeSimStack
  	<var: #mergeSimStack type: #'SimStackEntry *'>
+ 	"At a merge point the cogit expects the stack to be in the same state as mergeSimStack.
+ 	 mergeSimStack is the state as of some jump forward to this point.  So make simStack agree
+ 	 with mergeSimStack (it is, um, problematic to plant code at the jump).
+ 	 Values may have to be assigned to registers.  Registers may have to be swapped.
+ 	 The state of optStatus must agree."
+ 	| currentRegsMask mergeRegsMask potentialConflictRegMask conflictingRegsMask
+ 	   currentRegMask mergeRegMask currentEntry targetEntry |
+ 	<var: #currentEntry type: #'SimStackEntry *'>
+ 	<var: #targetEntry type: #'SimStackEntry *'>
+ 	mergeSimStack ifNil: [^self].
+ 	currentRegsMask := mergeRegsMask := potentialConflictRegMask := 0.
+ 	0 to: simStackPtr do:
- 	<var: #currentSSEntry type: #'SimStackEntry *'>
- 	<var: #expectedSSEntry type: #'SimStackEntry *'>
- 	"At merge point the cogit expects the stack to be in the same state as mergeSimStack.
- 	The logic is very naive, we align the existing state from the current stack to the merge stack
- 	from simStackPtr to methodOrBlockNumTemps, and if a conflict happen, we flush what remains
- 	to be merged."
- 	self flag: #TODO. "we could have a better algorithm with the current set of live registers to avoid flushing"
- 	simStackPtr to: methodOrBlockNumTemps by: -1 do:
  		[:i|
+ 		 currentRegMask := (currentEntry := self simStack: simStack at: i) registerMaskOrNone.
+ 		 mergeRegMask := (targetEntry := self simStack: mergeSimStack at: i) registerMaskOrNone.
+ 		 currentRegMask = mergeRegMask
+ 			ifTrue:
+ 				[self assert: (currentEntry isSameEntryAs: targetEntry)]
+ 			ifFalse: "This checks for a potential conflict..."
+ 				[(currentRegMask ~= 0 or: [mergeRegMask ~= 0]) ifTrue:
+ 					[potentialConflictRegMask := potentialConflictRegMask bitOr: (currentRegMask bitOr: mergeRegMask)]].
+ 		 currentRegsMask := currentRegsMask bitOr: currentRegMask.
+ 		 mergeRegsMask := mergeRegsMask bitOr: mergeRegMask].
+ 	conflictingRegsMask := potentialConflictRegMask bitAnd: (currentRegsMask bitAnd: mergeRegsMask).
+ 	"One simple algorithm is to spill everything if there are any conflicts and then pop back.
+ 	 But this is terrible :-(  Can we do better? Yes... Consider the following two simStacks
+ 		target:		0: | rA | __ | rB | rC | rD | <- sp
+ 		current:	0: | __ | __ | rD | rA | rC | <- sp
+ 	 If we were to assign in a naive order, 0 through sp rA would be overwritten before its value in current[3] is written to rC,
+ 	 and rC would be overwritten before its value in current[4] is written to rD.  But if we swap the registers in current so that
+ 	 they respect the reverse ordering in target we can assign directly:
+ 		swap current[3] & current[4]
+ 					0: | __ | __ | rD | rC | rA | <- sp
+ 	now do the assignment in the order target[0] := current[0],  target[1] := current[1], ...  target[4] := current[4],
+ 	i.e. rA := current[0]; rB := rD; (rC := rC); (rD := rD)."
+ 	conflictingRegsMask ~= 0 ifTrue:
+ 		[(self isAPowerOfTwo: conflictingRegsMask) "Multiple conflicts mean we have to sort"
+ 			ifFalse: [self swapCurrentRegistersInMask: currentRegsMask accordingToRegisterOrderIn: mergeSimStack]
+ 			ifTrue: [self assignToTempRegConflictingRegisterIn: conflictingRegsMask]].
+ 	self assert: (self conflcitsResolvedBetweenSimStackAnd: mergeSimStack).
+ 	simStackPtr to: 0 by: -1 do:
+ 		[:i|
+ 		 currentRegMask := (currentEntry := self simStack: simStack at: i) registerMaskOrNone.
+ 		 mergeRegMask := (targetEntry := self simStack: mergeSimStack at: i) registerMaskOrNone.
+ 		 mergeRegMask ~= 0
+ 			ifTrue:
+ 				[currentRegMask ~= mergeRegMask
+ 					ifTrue:
+ 						[currentEntry reconcilePoppingWith: targetEntry.
+ 						 simStack
+ 							at: i
+ 							put: (self
+ 									cCode: [mergeSimStack at: i]
+ 									inSmalltalk: [(mergeSimStack at: i) copy])]
+ 					ifFalse:
+ 						[self assert: (currentEntry isSameEntryAs: targetEntry)]]
+ 			ifFalse:
+ 				[self assert: (currentRegMask = 0 or: [currentEntry spilled]).
+ 				 self assert: (currentEntry isSameEntryAs: targetEntry) "really? here to check"]]!
- 			| currentSSEntry expectedSSEntry |
- 			currentSSEntry := self simStackAt: i.
- 			expectedSSEntry := self simStack: mergeSimStack at: i.
- 			expectedSSEntry type
- 				caseOf: {
- 					[SSBaseOffset]	-> [ self assert: (expectedSSEntry register = ReceiverResultReg or: [ expectedSSEntry register = FPReg ]).
- 										(expectedSSEntry register = ReceiverResultReg and: [needsFrame]) ifTrue: 
- 											[optStatus isReceiverResultRegLive ifFalse: 
- 												[self ssFlushFrom: i - 1 upThroughRegister: ReceiverResultReg.
- 											 	 self putSelfInReceiverResultReg ].
- 											 optStatus isReceiverResultRegLive: true].  ].
- 					[SSSpill]		-> [currentSSEntry ensureSpilledAt: (self frameOffsetOfTemporary: i) from: FPReg].
- 					[SSConstant]	-> [self assert: expectedSSEntry liveRegister notNil. 
- 										currentSSEntry storeToReg: expectedSSEntry liveRegister ].
- 					[SSRegister]	-> [(currentSSEntry type = SSRegister and: [currentSSEntry register = expectedSSEntry register])
- 											ifFalse: 
- 												[ self ssFlushFrom: i - 1 upThroughRegister: expectedSSEntry register.
- 												currentSSEntry storeToReg: expectedSSEntry register ] ]}.
- 			 ]!

Item was changed:
  ----- Method: RegisterAllocatingCogit>>ssStorePop:toPreferredReg: (in category 'simulation stack') -----
  ssStorePop: popBoolean toPreferredReg: preferredReg
  	"Store or pop the top simulated stack entry to a register.
  	 Use preferredReg if the entry is not itself a register.
  	 Answer the actual register the result ends up in."
  	| actualReg liveRegisters |
  	actualReg := preferredReg.
  	self ssTop type = SSRegister ifTrue: 
  		[self assert: (self ssTop liveRegister = NoReg
  					  or: [self ssTop liveRegister = self ssTop register]).
  		self assert: self ssTop spilled not.
  		actualReg := self ssTop register].
  	self ssTop liveRegister ~= NoReg ifTrue:
  		[actualReg := self ssTop liveRegister].
+ 	liveRegisters := self liveRegistersExceptingTopNItems: 1 in: simStack.
- 	liveRegisters := self liveRegistersExceptingTopNItems: 1.
  	(self register: actualReg isInMask: liveRegisters) ifTrue:
  		[actualReg := self allocateRegNotConflictingWith: (self registerMaskFor: preferredReg).
  		 actualReg = NoReg ifTrue:
  			[actualReg := preferredReg]].
  	self deny: (self register: actualReg isInMask: liveRegisters).
  	self ssStorePop: popBoolean toReg: actualReg. "generates nothing if ssTop is already in actualReg"
  	^actualReg!

Item was added:
+ ----- Method: StackToRegisterMappingCogit>>printSimStack: (in category 'simulation only') -----
+ printSimStack: aSimStack
+ 	<doNotGenerate>
+ 	self printSimStack: aSimStack toDepth: simStackPtr spillBase: simSpillBase on: coInterpreter transcript!