Spec for HLL targeting NES

[Movax12]

I'm still tweaking it but I have some good stuff working for ca65, at least I think so ..

I have the ability to use IF()-ELSE-ENDIF blocks and WHILE()-DO-ENDWHILE, DO-WHILE() (and alternate syntax with REPEAT-UNTIL)

I can produce very efficient code, with the only limitations being that all ORs are first, then any ANDs.

[You can place one OR block on the end in brackets - due to the recursive nature of the macro code you cannot have more than one test on the left of an AND or OR, such as (cond1 || cond2) && cond3 ]

Brackets are not needed - sort of - I'll explain more when I am finished

Example:

Code: Select all

if ((buttonpressed BUTTON_A) && ((comp a > #$12) || (comp a < #$8))
  ; do stuff
endif

;OR

do
  ;code
  dex
while not zero && bit6 clear

Of course there are a few other caveats (functions that could be called could destroy flags you want to check), but for the most part, if you understand basically what it is doing, it is very fast and will use all BXX instructions as expected rather than creating boolean tests.

[strat]

I've finally made substantial progress, to the point it generates some workable assembly. Here's a sample:

Code: Select all

	index = 0
	ii2 = 0
	limit = 15
	s8 src[20]
	s8 dst[20]
	while ii2 < limit
		dst[index] = src[ii2]
		index = index + 1
		ii2 = ii2 + 1
	endw	

6502 output:

Code: Select all

        lda #0
        sta index
        sta ii2
        lda #15
        sta limit
        jmp CHECK_0
LOOP_0:
        ldy ii2
        lda src,Y
        ldx index
        sta dst,X
        inc index
        inc ii2
CHECK_0:
        lda ii2
        cmp limit
        bcc LOOP_0
ENDWHILE_0:

Of course this output isn't optimal - the finished compiler will do a second pass to keep the index vars in the x and y registers. Mostly this is to let people who were interested know I'm back to working on it. There's an updated spec in the original post. Since uc65 is now live and open source, it might be tempting to simply add the features I was planning for Noism. Except I don't like Java that much. Here's a complete progress report:

Fully implemented:
Syntax parsing and symbol generation
Line comments and block comments
Flow control and while/dowhile looping
Nested parenthetical operations
Indexed array accesses
Pointer declaration and addressing
Variable declaration
Function calls and returns
Number format checking
Basic syntax checking (i.e. can a symbol follow the previous symbol)
Output of pseudo-asm syntax, used for testing features and converting to target cpu

Partially implemented:
6502 asm output
Structures
Scoping and static allocation of space for inner-scoped variables

Not started yet:
Function pointers
.asm file output
Complete error checking
Compiler directives
Multi-byte variable accesses
Signed numbers
16-bit/multibyte code output
for looping
z80 asm output

[thefox]

I had completely forgotten about this project. It's nice to see you have made some progress.

[Bregalad]

I had completely forgotten about this project. It's nice to see you have made some progress.

I also had forgotten.
It looks like your code generation is pretty good !!
One thing it could do is to see that the check "ii2 < limit" will always be true on it's first iteration, and transform the while loop into a do-while loop, saving a useless jump in the code.
However I admit it's not as simple as it sound to implement.

Way better than the pure crap that CC65 generates (the same code would generate several kilobytes of code using indirect addressing all the time when you didn't even use pointers in the original code).

[Shiru]

Way better than the pure crap that CC65 generates (the same code would generate several kilobytes of code using indirect addressing all the time when you didn't even use pointers in the original code).

Examples of the crap by cc65:

Code: Select all

void test(void)
{
   unsigned char index = 0;
   unsigned char ii2 = 0;
   unsigned char limit = 15;
   unsigned char  src[20];
   unsigned char  dst[20];
   while (ii2 < limit)
   {
      dst[index] = src[ii2];
      ++index;
      ++ii2;
   }
}

generates a crap indeed:

Code: Select all

; ---------------------------------------------------------------
; void __near__ test (void)
; ---------------------------------------------------------------

.segment	"CODE"

.proc	_test: near

.segment	"CODE"

	lda     #$00
	jsr     pusha
	jsr     pusha
	lda     #$0F
	jsr     pusha
	ldy     #$28
	jsr     subysp
L0015:	ldy     #$29
	lda     (sp),y
	dey
	cmp     (sp),y
	bcs     L0016
	lda     sp
	ldx     sp+1
	ldy     #$2A
	clc
	adc     (sp),y
	bcc     L001A
	inx
L001A:	jsr     pushax
	lda     sp
	ldx     sp+1
	clc
	adc     #$16
	bcc     L001D
	inx
L001D:	ldy     #$2B
	clc
	adc     (sp),y
	bcc     L001E
	inx
L001E:	sta     ptr1
	stx     ptr1+1
	ldy     #$00
	lda     (ptr1),y
	jsr     staspidx
	ldy     #$2A
	clc
	lda     #$01
	adc     (sp),y
	sta     (sp),y
	dey
	clc
	lda     #$01
	adc     (sp),y
	sta     (sp),y
	jmp     L0015
L0016:	ldy     #$2B
	jmp     addysp

.endproc

However,

Code: Select all

void test(void)
{
   static unsigned char index = 0;
   static unsigned char ii2 = 0;
   static unsigned char limit = 15;
   static unsigned char  src[20];
   static unsigned char  dst[20];
   while (ii2 < limit)
   {
      dst[index] = src[ii2];
      ++index;
      ++ii2;
   }
}

generates (DATA and BSS sections omited):

Code: Select all

; ---------------------------------------------------------------
; void __near__ test (void)
; ---------------------------------------------------------------

.segment	"CODE"

.proc	_test: near

.segment	"CODE"

L001A:	lda     L0012
	cmp     L0014
	bcs     L001B
	lda     #<(L0019)
	ldx     #>(L0019)
	clc
	adc     L0010
	bcc     L001F
	inx
L001F:	sta     ptr1
	stx     ptr1+1
	ldy     L0012
	lda     L0017,y
	ldy     #$00
	sta     (ptr1),y
	inc     L0010
	inc     L0012
	jmp     L001A
L001B:	rts

.endproc

[qbradq]

Glad to see you're making progress!

[Movax12]

Looks good.

...saving a useless jump in the code.

I agree with this. I can't see a need to jump down to the branch. Have the branch at the start of the loop. Maybe I am missing something?

[Bregalad]

What you're missing is that this optimization is complicated to implement (while perfectly possible).
For all declared & initialized variables, there is need to have the initial value itself memorized in the compiler itself. If the variables are ever affected with anything other than a constant literal value (or another value that reduces to a constant literal) then it should be marked as "scratched".

Then when a while or for loop is encountered, the test condition has to be checked at compile time against the variables. If anything in the expression tree is marked as "scratched" then you can perrform no optimisation. Else you can evaluate the expression fully, and it'll either evaluate to "true" or "false".
If it evaluates to "false" then you can remove the loop completely (and it'd be a good idea to issue a warning to the user, as it's probably an error of his side).
If it evaluates to "true" then you can turn it into a do-while loop, so you avoid a dummy check at loop entering.

Note that this is my interpretation of the problem, the actual implementation might need to be even more complex than this short description.

@Shiru : Wow, CC65 can produce such code ? Declaring the variables as "static" makes so much a difference ? I'm very impressed
Definitely far to optimal code, but it's somewhat decent compared as to what it produces under normal conditions.
I should try to use CC65 again and declare everything "static" and see how it turns out.

Still it should be doable to hack the compiler so that everything is "static". Although this keywoard always confused the heck out of me in C. As far as I undestand it can have completely different meaning depending on where it's used. With GCC "static" global variables are invisible to other files, and "static" functions can use nonstandard calling convention (leading often to much more optimal code). In fact all functions should be static ideally but then you can give up separate compilation and intermixing with other languages.

[lidnariq]

Still it should be doable to hack the compiler so that everything is "static".

Look at the compile-time flag -Cl

[thefox]

As far as I undestand it can have completely different meaning depending on where it's used. With GCC "static" global variables are invisible to other files, and "static" functions can use nonstandard calling convention (leading often to much more optimal code). In fact all functions should be static ideally but then you can give up separate compilation and intermixing with other languages.

Yes, in global scope static makes the identifier (variable or a function) local to the module (file). In function scope it basically makes the variable a global variable in function scope.

Many compilers nowadays have link time code optimization, so I don't think your "ideal" of all functions being static is that useful in the end.

Also there's a slight difference between local static variables and the -Cl switch of cc65. When local static variables are used, the variable is only initialized once at the beginning of the program. When -Cl is used, the variables are initialized every time the function is entered.

[slobu]

Thanks for continuing forward on this project. There is definitely a target audience for this project and I'm thrilled to be one =)

[Movax12]

Then when a while or for loop is encountered, the test condition has to be checked at compile time against the variables.

I see what you are saying. I was thinking this would be better:

Code: Select all

LOOP_0:
        lda ii2
        cmp limit
        bcs ENDWHILE_0
        ldy ii2
        lda src,Y
        ldx index
        sta dst,X
        inc index
        inc ii2
        jmp LOOP_0
ENDWHILE_0:

But this way a JMP is required each loop rather than just the first. I may have to rethink the way I do some things.

[strat]

Thanks for the encouragement, y'all.

'dowhile' eliminates the jump to the first conditional check; the updated spec will mention that.

I agree with this. I can't see a need to jump down to the branch. Have the branch at the start of the loop. Maybe I am missing something?

If you need to test the condition before the loop runs at all, it's better to jump down there than to have the branch at the head of the loop, jumping past the loop if the test fails. Then the actual loop has to keep jumping back to the test. Ironically, this is one of the few sensible constructs of cc65.

The one optimization I'm really concerned with is eliminating any lda/sta/cmp/inc instruction that can be replaced with ldy/sty/cpy/iny and if the index var needs arithmetic, using tay in place of sta/ldy. I've got a good idea of how this will be implemented. Also, another one I'd like to implement is removing the cmp operation for countdown loops. (cc65 to its credit also eliminates cmp when beq/bne works).

Code: Select all

	while ind > 0
		ind = ind - 1
		ii2 = ii2 - 1
	endw
	
	LOOP_0:
		dec ii2
		dec ind
		bne LOOP_0

That second example of cc65 output still makes me glad to be working on this. I actually made a map-scrolling demo in C earlier this year, just to see if working on a whole new language was even worthwhile, and the most tiresome thing was flagging each var as local or global with a comment. cc65 doesn't allow anonymous unions, so that's also a little inconvenient though maybe tolerable.

[strat]

But this way a JMP is required each loop rather than just the first.

Yeah, I took extra care to make the compiler not output loops like this.

[Movax12]

Also, another one I'd like to implement is removing the cmp operation for countdown loops.

If you know your start and end values, this code snippet works for a FOR loop (8-bit, in ca65 macro code):

Code: Select all

 
; calculate the first invalid value (if this value is found at the test, exit the loop)
_END_COUNTER_VALUE_  = < ( ( _STEP_ + _TO_VALUE_) + ( _FROM_VALUE_ - _TO_VALUE_ .mod _STEP_) )

; if high bit of 2nd iteration and high bit of 2nd LAST iteration are high AND END_COUNTER_VALUE_ is positive

.if ( (_FROM_VALUE_ + _STEP_ ) & ( _END_COUNTER_VALUE_ - _STEP_ ) & $80 ) .and 
    (.not (_END_COUNTER_VALUE_ & $80))
            BMI START_LABEL
; if high bit of 2nd iteration and high bit of 2nd LAST iteration are low AND END_COUNTER_VALUE_ is negative
.elseif (.not (((_FROM_VALUE_ + _STEP_ ) | ( _END_COUNTER_VALUE_ - _STEP_ )) & $80 )) .and 
        (_END_COUNTER_VALUE_ & $80)
            BPL START_LABEL
; last value is zero
.elseif _END_COUNTER_VALUE_ = 0
            BNE START_LABEL
.else
    ; need to check loop against end value:
    .if .xmatch(_COUNTERVAR_, x) ; found X
        cpx #_END_COUNTER_VALUE_
    .elseif .xmatch(_COUNTERVAR_, y) ; found y
        cpy #_END_COUNTER_VALUE_
    .elseif .xmatch(_COUNTERVAR_, a) ; found a
        cmp #_END_COUNTER_VALUE_
    .else
        lda _COUNTERVAR_
        cmp #_END_COUNTER_VALUE_
    .endif
    BNE START_LABEL
.endif