Jump to content

Photo

Possible optimization

Intybasic

13 replies to this topic

#1 artrag OFFLINE  

artrag

    Stargunner

  • 1,212 posts

Posted Tue Aug 21, 2018 10:53 AM

I was trying to evaluate the asm produced by Intybasic under a number of cases and I ended with this:

		#d = enemy_cards(e+0)
		#e = enemy_cards(e+1)
		#f = varptr #backtab(20+4+0+c)
		poke #f-1,0
		for n=0 to 3 
			poke #f+0, #d:		#f=1+#f
			poke #f+0, #e:		#f=1+#f
		next

Whose loop becomes this in asm:

0x5332                          T22:
                                	;[142] 			poke #f+0, #d:		#f=1+#f
                                	SRCFILE "testbasic.bas",142
5332   0280 0308                	MVI V8,R0
5334   0281 030E                	MVI V10,R1
5336   0248                     	MVO@ R0,R1
5337   02B8 0001                	MVII #1,R0
5339   00C8                     	ADDR R1,R0
533A   0240 030E                	MVO R0,V10
                                	;[143] 			poke #f+0, #e:		#f=1+#f
                                	SRCFILE "testbasic.bas",143
533C   0280 030D                	MVI V9,R0
533E   0281 030E                	MVI V10,R1
5340   0248                     	MVO@ R0,R1
5341   02B8 0001                	MVII #1,R0
5343   00C8                     	ADDR R1,R0
5344   0240 030E                	MVO R0,V10
                                	;[144] 		next
                                	SRCFILE "testbasic.bas",144
5346   0280 0115                	MVI V1,R0
5348   0008                     	INCR R0
5349   0240 0115                	MVO R0,V1
534B   0378 0003                	CMPI #3,R0
534D   0226 001C                	BLE T22

Actually I was expecting the use if INCR instead of ADDR and the reuse of f# in R1 without loading it in and out of ram

Something like this:

T22:
	;[142] 			poke #f+0, #d:		#f=1+#f
	MVI V8,R0
	MVI V10,R1
	MVO@ R0,R1

	INCR R1
	;[143] 			poke #f+0, #e:		#f=1+#f
	MVI V9,R0
	MVO@ R0,R1

	INCR R1 
	MVO R1,V10

	;[144] 		next
	MVI V1,R0
	INCR R0
	MVO R0,V1
	CMPI #3,R0
	BLE T22

Even better if you keep in registers the variables in the whole loop



	MVI V10,R1
T22:
	;[142] 			poke #f+0, #d:		#f=1+#f
	MVI V8,R0
	MVO@ R0,R1
	INCR R1
	;[143] 			poke #f+0, #e:		#f=1+#f
	MVI V9,R0
	MVO@ R0,R1
	INCR R1 
	;[144] 		next
	MVI V1,R0
	INCR R0
	MVO R0,V1
	CMPI #3,R0
	BLE T22
	
	MVO R1,V10


#2 intvnut OFFLINE  

intvnut

    River Patroller

  • 3,235 posts
  • Location:@R6 (top of stack)

Posted Tue Aug 21, 2018 11:54 AM

Also, more generally, this sequence could be condensed a bit:

5337   02B8 0001                	MVII #1,R0
5339   00C8                     	ADDR R1,R0

If you have a constant other than 1, this could become ADDI #cst, Rx.   And, of course, ADDI #1, Rx can be replaced by INCR Rx if you don't need full flags for a subsequent branch. That's the common case.  (INCR only sets sign/zero, and not carry/overflow.)

 

I think the culprit here is how the add was written:  #f = 1 + #f.  You'll get a better result if you write it as #f = #f + 1. Compare and contrast:

 .

    ;[1] #f = 1 + #f
    SRCFILE "add.bas",1
    MVII #1,R0
    ADD V1,R0
    MVO R0,V1

    ;[2] #f = #f + 1
    SRCFILE "add.bas",2
    INCR R0
    MVO R0,V1

.

I've found IntyBASIC is often rather sensitive to the order of operations in an expression, due to the nature of its code generator.  IIRC, it's a straightforward tree walk, with only minimal transformations on the tree.  IntyBASIC does do some basic register tracking to try to reuse values that were already in registers.  You can see that in my example above:  It didn't re-read #f for the second statement.

 

However, it doesn't have a global register allocator that would allow keeping values in registers across an entire loop (such as loop counters).

 

One thing IntyBASIC might benefit from are C-like ++ and -- operators that can fold an increment or decrement into an expression.  Yes, they're not very BASIC-like, but they do provide a cheap opportunity for optimization while retaining a fairly straightforward code generator.


Edited by intvnut, Tue Aug 21, 2018 11:54 AM.


#3 artrag OFFLINE  

artrag

    Stargunner

  • Topic Starter
  • 1,212 posts

Posted Tue Aug 21, 2018 12:20 PM

I second the proposal of adding an increment/decrement operator if adding this optimization rule is not possible for its intrinsic structure

#4 artrag OFFLINE  

artrag

    Stargunner

  • Topic Starter
  • 1,212 posts

Posted Tue Aug 21, 2018 12:27 PM

By the way, is there an opcode able to do an indirect assignment to the location pointed by a register and increment the register?

#5 nanochess OFFLINE  

nanochess

    Processorus Polyglotus

  • 5,797 posts
  • Coding something good
  • Location:Mexico City

Posted Tue Aug 21, 2018 12:38 PM

By the way, is there an opcode able to do an indirect assignment to the location pointed by a register and increment the register?


MVO@ R0,R4
When using R4 and R5 as source/target with instructions including the character @, the used register auto-increments.

Check chapter 8 of my book for a complete list of opcodes.

#6 DZ-Jay OFFLINE  

DZ-Jay

    Quadrunner

  • 12,032 posts
  • The P-Machinery AGE is almost here!
  • Location:NC, USA

Posted Tue Aug 21, 2018 12:51 PM

I second the proposal of adding an increment/decrement operator if adding this optimization rule is not possible for its intrinsic structure



Microsoft added "Inc(arg)" and "Dec(arg)" functions to its Basic-ish dialects. Perhaps that's the way. :)

#7 DZ-Jay OFFLINE  

DZ-Jay

    Quadrunner

  • 12,032 posts
  • The P-Machinery AGE is almost here!
  • Location:NC, USA

Posted Tue Aug 21, 2018 1:11 PM

By the way, is there an opcode able to do an indirect assignment to the location pointed by a register and increment the register?


R4, R5, and R6, are auto-increment registers. They will increment automatically when accessing memory indirectly. R4 and R5 post-increment (x++), while R6 pre-increments (++x). That makes R6 work as a Stack Pointer.

dZ.

#8 intvnut OFFLINE  

intvnut

    River Patroller

  • 3,235 posts
  • Location:@R6 (top of stack)

Posted Tue Aug 21, 2018 1:44 PM

while R6 pre-increments (++x). That makes R6 work as a Stack Pointer.

 

Not quite.  R6 also post-increments on write, and pre-decrements on read.  That is:

.

MVO@ R0, R6  ; Writes R0 to @R6, then sets R6 = R6 + 1.
MVI@ R6, R0  ; Sets R6 = R6 - 1, then reads @R6 into R0.

.

You need both increment and decrement to get a stack pointer.  On the CP1600, all of the auto-increments are always post-increments.  What makes R6 behave like a stack pointer is that reads through R6 (and only reads) pre-decrement instead.  

 

(Edited, because with AA's comment editor, WYSINWYG.)


Edited by intvnut, Tue Aug 21, 2018 1:45 PM.


#9 artrag OFFLINE  

artrag

    Stargunner

  • Topic Starter
  • 1,212 posts

Posted Tue Aug 21, 2018 2:35 PM


	ASM ; #f = usr myprint(#f,#d,#e)	
	ASM MYPRINT: PROC	
	ASM		MOVR R0,R4
	ASM 		MVO@ R1,R4	
	ASM 		MVO@ R2,R4	
	ASM		MOVR R4,R0
	ASM 		JR R5
	ASM 		ENDP

I ended with this



#10 intvnut OFFLINE  

intvnut

    River Patroller

  • 3,235 posts
  • Location:@R6 (top of stack)

Posted Tue Aug 21, 2018 2:55 PM


	ASM ; #f = usr myprint(#f,#d,#e)	
	ASM MYPRINT: PROC	
	ASM		MOVR R0,R4
	ASM 		MVO@ R1,R4	
	ASM 		MVO@ R2,R4	
	ASM		MOVR R4,R0
	ASM 		JR R5
	ASM 		ENDP

I ended with this

 

 

 

If you always update #f, I wonder if this might be marginally better:

; CALL myprint(#d, #e, VARPTR #f)
MYPRINT: PROC
    MVI@ R2, R4
    MVO@ R0, R4
    MVO@ R1, R4
    MVO@ R4, R2
    JR   R5
    ENDP

It's too bad that IntyBASIC variable names are opaque to assembly code.  (e.g. V1, V3, etc. instead of V.F, V.MYVAR, etc.)



#11 artrag OFFLINE  

artrag

    Stargunner

  • Topic Starter
  • 1,212 posts

Posted Tue Aug 21, 2018 3:09 PM

That was also my proposal tons of post ago, to use a common name space for basic and assembly  



#12 nanochess OFFLINE  

nanochess

    Processorus Polyglotus

  • 5,797 posts
  • Coding something good
  • Location:Mexico City

Posted Tue Aug 21, 2018 4:36 PM

It's too bad that IntyBASIC variable names are opaque to assembly code.  (e.g. V1, V3, etc. instead of V.F, V.MYVAR, etc.)

 
 

That was also my proposal tons of post ago, to use a common name space for basic and assembly


It's in my TODO list. I know it's useful but I need to get courage to go all over the compiler and change everything.

#13 DZ-Jay OFFLINE  

DZ-Jay

    Quadrunner

  • 12,032 posts
  • The P-Machinery AGE is almost here!
  • Location:NC, USA

Posted Wed Aug 22, 2018 4:36 AM

 

Not quite.  R6 also post-increments on write, and pre-decrements on read.  That is:

.

MVO@ R0, R6  ; Writes R0 to @R6, then sets R6 = R6 + 1.
MVI@ R6, R0  ; Sets R6 = R6 - 1, then reads @R6 into R0.

.

You need both increment and decrement to get a stack pointer.  On the CP1600, all of the auto-increments are always post-increments.  What makes R6 behave like a stack pointer is that reads through R6 (and only reads) pre-decrement instead.  

 

(Edited, because with AA's comment editor, WYSINWYG.)

 

True.  That's what I get for responding quickly on my phone... :dunce:

 

In any case, I think the important point is the use of R4 and R5 and auto-incrment.

 

    -dZ.



#14 artrag OFFLINE  

artrag

    Stargunner

  • Topic Starter
  • 1,212 posts

Posted Wed Sep 26, 2018 1:53 AM

About namespace...
What if next versions of intybasic introduce for labels, procedures and variables, a sort of modules able to make local name within a module X start - module X end?

It could increase the reuse of procedures and snippets, and allows to put order in the use of variables.

Old games without modules will compile as having a single name space...





Also tagged with one or more of these keywords: Intybasic

0 user(s) are browsing this forum

0 members, 0 guests, 0 anonymous users