Interpreter Plugins

Hans-Martin Mosner hm.mosner at cww.de
Tue Apr 14 18:26:51 UTC 1998


Mike Klein wrote:
> 
> What would also be nice, (in an ideal sense), would be if there was a platform
> independent way to invoke the C-compiler.  This would probably be easier on
> Unix where there is more likely to actually be a C-compiler.  Then the
> primitive-generation process could be closed-loop.
> 
> -- Mike Klein

I wanted to keep my mouth shut on this issue until something real
emerges from my desk, but since you're asking for it, here's what I'm
currently working on:

A translator which translates primitives into machine code right within
Squeak, without going through a C intermediate code and all that hassle.
Primitives for this compiler have just a <primitive> pragma, without a
number, and are translated into the instruction set of the processor on
the fly. I'm currently (almost) generating PowerPC code, but adapting
the code generator to other processors should be relatively easy.
The intermediate form is Static Single Assignment which lends itself
well to a number of optimization algorithms. With the aid of some very
simple type hints of the form "xyz mustBeInteger" etc. the compiler does
type flow analysis and inlines sends of selectors whose method can be
determined statically (actually, only those are allowed in the current
design).
I do not plan on making this a general-purpose Smalltalk translator,
since I think that a good bytecode interpreter (or JIT threaded code
generator) together with well-optimized primitives is a very good match
for most problems.

Here's an example of what can be generated at the moment:

The following method in class String has been modified to include the
<primitive> pargma and a type hint:

primBeginsWith: prefix
	"Answer whether the receiver begins with the given prefix string."

	| prefixSize |
	<primitive>

	prefix mustBeString.	"type assertion for the compiler"

	prefixSize := prefix size.

	self size < prefixSize ifTrue: [^false].
	1 to: prefixSize do:
		[:index | (self at: index) = (prefix at: index) ifFalse: [^false]].
	^true

The intermediate SSA code looks like this:

region 1 successors 2, 4
	1.1	load self   "used by: (4.3) (8.3)"	<String... of: <native
Character>>
	1.2	load arg1 prefix   "used by: (1.3) (4.1)"	<any>
	1.3	call fetchClassOf((1.2))   "used by: (1.5) (2.2)"	<native
Behavior...>
	1.4	constant String   "used by: (1.5)"	<native String class...=String>
	1.5	(1.4) = (1.3)   "used by: (1.6)"	<native Boolean>
	1.6	jump region 4 ifTrue: (1.5)	<any>
region 2 predecessors 1 successors 3, 4
	2.1	constant Symbol   "used by: (2.2)"	<native Symbol class=Symbol>
	2.2	(2.1) = (1.3)   "used by: (2.3)"	<native Boolean>
	2.3	jump region 4 ifTrue: (2.2)	<any>
region 3 predecessors 2
	3.1	load non-oop   "used by: (3.2)"	<prim fail>
	3.2	return (3.1)	<undef>
region 4 predecessors 1, 2 successors 5, 6
	4.1	type convert (1.2)   "used by: (4.2) (8.6)"	<String... of: <native
Character>>
	4.2	call stSizeOf((4.1))   "used by: (7.3) (4.4) (7.2)"	<native int
0...*>
	4.3	call stSizeOf((1.1))   "used by: (4.4)"	<native int 0...*>
	4.4	(4.3) < (4.2)   "used by: (4.5)"	<native Boolean>
	4.5	jump region 6 ifFalse: (4.4)	<any>
region 5 predecessors 4
	5.1	return false	<undef>
region 6 predecessors 4 successors 7
	6.1	constant 1   "used by: (7.1)"	<native int=1>
region 7 predecessors 6, 10 successors 8, 11
	7.1	Phi 1, (10.2)   "used by: (7.3) (7.2)"	<native int -*...*>
	7.2	(7.1) <= (4.2)   "used by: (7.4)"	<native Boolean>
	7.3	clip (7.1) <= (4.2)   "used by: (10.2) (8.2) (8.5)"	<native int
-*...*>
	7.4	jump region 11 ifFalse: (7.2)	<any>
region 8 predecessors 7 successors 9, 10
	8.1	constant 3   "used by: (8.2)"	<native int=3>
	8.2	(7.3) + (8.1)   "used by: (8.3)"	<native int
-1073741824...1073741823>
	8.3	access uint8 (1.1) at: (8.2)   "used by: (8.7)"	<native Character>
	8.4	constant 3   "used by: (8.5)"	<native int=3>
	8.5	(7.3) + (8.4)   "used by: (8.6)"	<native int
-1073741824...1073741823>
	8.6	access uint8 (4.1) at: (8.5)   "used by: (8.7)"	<native Character>
	8.7	(8.3) = (8.6)   "used by: (8.8)"	<native Boolean>
	8.8	jump region 10 ifTrue: (8.7)	<any>
region 9 predecessors 8
	9.1	return false	<undef>
region 10 predecessors 8 successors 7
	10.1	constant 1   "used by: (10.2)"	<native int=1>
	10.2	(7.3) + (10.1)   "used by: (7.1)"	<native int
-1073741824...1073741823>
	10.3	jump region 7	<any>
region 11 predecessors 7
	11.1	return true	<undef>

And the (partially incorrect...) PowerPC code is here:
(negative register numbers are pseudo-registers; the register coloring
algorithm does not work yet)

 region 1 successors 2, 4
	1.1	mr	R-2,R3   "used by: (4.5) (8.2)"	<String... of: <native
Character>>
	1.2	lwz	R-3,R4,0   "used by: (1.3) (4.1)"	<any>
	1.3	mr	R3,R-3
	1.4	bl	fetchClassOf
	1.5	mr	R-4,R3   "used by: (1.7) (2.2)"	<native Behavior...>
	1.6	li	R-5,String   "used by: (1.7)"	<native String class...=String>
	1.7	cmp	CR-1,R-5,R-4   "used by: (1.8)"
	1.8	CR-bit EQ, (1.7)   "used by: (1.9)"	<native Boolean>
	1.9	bc	IF,(1.8),region 4
region 2 predecessors 1 successors 3, 4
	2.1	li	R-6,Symbol   "used by: (2.2)"	<native Symbol class=Symbol>
	2.2	cmp	CR-2,R-6,R-4   "used by: (2.3)"
	2.3	CR-bit EQ, (2.2)   "used by: (2.4)"	<native Boolean>
	2.4	bc	IF,(2.3),region 4
region 3 predecessors 2
	3.1	li	R-7,0   "used by: (3.2)"	<prim fail>
	3.2	mr	R3,R-7   "used by: (3.3)"	<prim fail>
	3.3	blr
region 4 predecessors 1, 2 successors 5, 6
	4.1	srawi	R-8,R-3,1   "used by: (4.2) (8.4)"	<native int
-1073741824...1073741823>
	4.2	mr	R3,R-8
	4.3	bl	stSizeOf
	4.4	mr	R-9,R3   "used by: (4.8) (7.1)"	<native int 0...*>
	4.5	mr	R3,R-2
	4.6	bl	stSizeOf
	4.7	mr	R-10,R3   "used by: (4.8)"	<native int 0...*>
	4.8	cmp	CR-3,R-10,R-9   "used by: (4.9)"
	4.9	CR-bit LT, (4.8)   "used by: (4.10)"	<native Boolean>
	4.10	bc	IFNOT,(4.9),region 6
region 5 predecessors 4
	5.1	mr	R3,false   "used by: (5.2)"	<native False=false>
	5.2	blr
region 6 predecessors 4 successors 7
	6.1	li	R-11,1   "used by: (6.2)"	<native int=1>
	6.2	mr	R-1,R-11	<native int=1>
region 7 predecessors 6, 10 successors 8, 11
	7.1	cmp	CR-4,R-1,R-9   "used by: (7.2)"
	7.2	CR-bit NOT GT, (7.1)   "used by: (7.4)"	<native Boolean>
	7.3	mr	R-12,R-1   "used by: (8.1) (8.3) (10.1)"	<native int -*...*>
	7.4	bc	IFNOT,(7.2),region 11
region 8 predecessors 7 successors 9, 10
	8.1	addi	R-13,R-12,3   "used by: (8.2)"	<native int
-1073741824...1073741823>
	8.2	lbzx	R-14,R-2,R-13   "used by: (8.5)"	<native Character>
	8.3	addi	R-15,R-12,3   "used by: (8.4)"	<native int
-1073741824...1073741823>
	8.4	lbzx	R-16,R-8,R-15   "used by: (8.5)"	<native Character>
	8.5	cmp	CR-5,R-14,R-16   "used by: (8.6)"
	8.6	CR-bit EQ, (8.5)   "used by: (8.7)"	<native Boolean>
	8.7	bc	IF,(8.6),region 10
region 9 predecessors 8
	9.1	mr	R3,false   "used by: (9.2)"	<native False=false>
	9.2	blr
region 10 predecessors 8 successors 7
	10.1	addi	R-17,R-12,1   "used by: (10.2)"	<native int
-1073741824...1073741823>
	10.2	mr	R-1,R-17	<native int -1073741824...1073741823>
	10.3	b	region 7
region 11 predecessors 7
	11.1	mr	R3,true   "used by: (11.2)"	<native True=true>
	11.2	blr

Note that literals are not handled correctly yet, but you might get the
idea...

I hope to have the beast working in summer, at least for PowerPC and
Wintel processors.

Hans-Martin





More information about the Squeak-dev mailing list