Show Posts

This section allows you to view all posts made by this member. Note that you can only see posts made in areas you currently have access to.


Messages - Xeda112358

Pages: [1] 2 3 ... 306
1
TI Z80 / Re: Unnamed Optimizing Compiler
« on: Today at 01:28:08 pm »
I put it up on GitHub. I added the GotoIf() function, which is really important for a programming language. From this, I'll build blocks like If, While, For, etc.
Here is input code:
Code: [Select]
4->k
0->x
1->y
lbl0:
  x+y->z
  x+1->x
  y+1->y
  Disp(10*z)
  k-1->k
  GotoIf(lbl0,k!=0)
2->x
Disp(x)
And attached is a screenshot of what the program displays.
As cool as that is, the generated assembly code is pretty ugly:
Code: [Select]
#include "jq.inc"
#include "ti83plus.inc"
scrap           = 8000h
var_k           = scrap+0
var_x           = scrap+2
var_y           = scrap+4
var_z           = scrap+6
.db $BB,$6D
.org $9D95
 ld hl,4
 ld (var_k),hl
 ld hl,0
 ld (var_x),hl
 ld hl,1
 ld (var_y),hl
lbl0:
 ld hl,(var_x)
 ld de,(var_y)
 add hl,de
 ld (var_z),hl
 ld hl,(var_x)
 inc hl
 ld (var_x),hl
 ld hl,(var_y)
 inc hl
 ld (var_y),hl
 ld hl,(var_z)
 add hl,hl
 add hl,hl
 ld de,(var_z)
 add hl,de
 add hl,hl
 call disp_uint16
 ld hl,(var_k)
 dec hl
 ld (var_k),hl
 ld a,h
 or l
 jqnz(lbl0 )
 ld hl,2
 ld (var_x),hl
#include "disp_uint16.z80"

2
TI Z80 / Re: HYBRID (8X+)
« on: Today at 08:39:44 am »
Oh, great news! I've had a few big projects like that (lost and then years later found a place that had an earlier backup). Good luck; it's a lot of work trying to relearn your old code.

3
ASM / Re: Miscellaneous ASM Questions
« on: Yesterday at 02:10:19 pm »
Holy heck that is clever! So all you'd need a token hook, RawKeyHook, and parser hook.

4
TI Z80 / Re: Unnamed Optimizing Compiler
« on: Yesterday at 11:23:08 am »
I finally compiled a real program!

With this new iteration of the program, I am using an AST to perform algorithmic optimizations, but I am compiling with a modified version of the original method. Now it is producing better code that is (importantly) correct. My first attempt with this version got really, really slow on slightly complicated inputs-- I terminated the process after two hours trying to compile one line (it wasn't an infinite loop, either; the search space got huge).

So I modified it to allow limiting the amount of paths it kept in memory Keeping a single path would produce code like the previous version, but I found that 60-100 would produce decent code, while 200 produces better code.

It *still* doesn't track state, so there are lots of unnecessary ld hl,() and whatnot.

Anyways, here is what compiling via the commandline might look like:
Code: [Select]
#Convert the code to an intermediate representation
python sy.py test.txt

#Convert the intermediate representation to Z80 assembly, with the ti-83+ family header
python compile.py test.ir -TI8X -MAX_PATHS=150

#Compile
spasm test.asm bin/test.8xp -I inc -I routines

It will take a few seconds to generate the assembly, but it works! Attached is a screenshot of the following code:
Code: [Select]
3->x
6->y
Disp(3*(2*x+y*3)+9*(x+y))
Disp(1337)
Disp(3*(x+y)+9*(x+y))

5
ASM / Re: Miscellaneous ASM Questions
« on: April 22, 2019, 09:34:37 pm »
I'm fairly sure that the parser hook doesn't let you intercept non-function tokens. I could be wrong about that, but I don't think so.

6
TI Z80 / Re: Unnamed Optimizing Compiler
« on: April 21, 2019, 03:45:43 pm »
Looks pretty cool Xeda. Somewhat unrelated, but I was looking up info on Game Boy programming (the Game Boy uses a Z80 clone +/- some things) and apparently you can do C on it via SDCC (or so I've read). Not sure how efficient it is or fast, but it's a thing.
SDCC produces working, but somewhat inefficient code. One of the lofty goal for this project is to be able to convert LLVM IR code to (efficient) z80 assembly, for which there are existing C-->LLVM IR programs.

I know jacobly has done some pretty good work on llvm-z80, producing some pretty nice code, but there are some shortcomings still.

EDIT: I forgot to update :P I'm tired.

I'm running into a problem with the AST method. I'm trying to compile directly from the AST, and while the code seems correct, it isn't as efficient. The reason for this is that I haven't figured out an analogous algorithm that will work on ASTs without needlessly searching the entire set of potential codes. Most operations have four to eight implementations using different inputs/outputs. so, even compiling a short 9-token expression like (4+x)*3+7-y could have hundreds of thousands to millions of potential paths. The previous algorithm is able to drastically reduce the search space.

That said, I'm still able to get more clever with algorithmic optimizations. For example, if you try something like 3*(x+1)+5*(x+1), it will be optimized 8*(x+1) and then (x+1)<<3, producing the code:
Code: [Select]
ld hl,(x)
 inc hl
 add hl,hl
 add hl,hl
 add hl,hl
 call disp_uint16

However, 3*(x+1)+9*(x+1) will convert to 12*(x+1) and try to make a routine faster than calling multiplication since only two bits are set in 12, producing this code:
Code: [Select]
ld hl,(x)
 inc hl
 ld bc,(x)
 inc bc
 sla c
 rl b
 add hl,bc
 add hl,hl
 add hl,hl
 call disp_uint16
With the other method, this code would have compiled 12(x+1) to something like:
Code: [Select]
ld de,(x)
 inc de
 ld hl,(x)
 inc hl
 add hl,hl
 add hl,de
 add hl,hl
 add hl,hl
 call disp_uint16
It still isn't optimal since neither algorithm keeps track of the current state aside from input and output, but the latter code tries more code paths, even if they start out suboptimal. The AST-based algorithm makes local optimizations, while the previous algorithm took into account the whole code.

For reference, this is how I, a human (I swear), would implement it:
Code: [Select]
ld hl,(x)
 inc hl
 ld b,h
 ld c,l
 add hl,hl
 add hl,bc
 add hl,hl
 add hl,hl
 call disp_uint16
The main difference is that I take advantage of the fact that X+1 is held in HL, so I don't need to compute it again to put in BC or DE. This is because I am taking into account "state." That is, I know that HL already contains the value I want, whereas the compilers currently only know that HL holds some value.

One thing that I learned about in looking into LLVM is the idea of Static Single Assignment (SSAs), which I think will make it a lot easier to track state and optimize accordingly, providing a great improvement in code quality. The challenge with that is trying to optimally allocate variables, using registers, stack space, or RAM.

7
ASM / Re: Miscellaneous ASM Questions
« on: April 21, 2019, 03:35:41 pm »
Oh, you are right about that. That would be a little more difficult as you would have to resize variables.
When the parser hook triggers mode 0, the name of the program being parsed is in basic_prog. You could first scan for all tau tokens that can be directly replaced (and replace them), while counting all of the ones that need extra work. Then verify there is enough memory to insert an additional two bytes for each remaining entry. Use InsertMem at the end of the program, but remember to adjust the variable's size bytes as well as basic_end. Finally, replace the remaining tau tokens with "(2pi)".

It is a complicated process, so good luck!

8
TI Z80 / Re: Unnamed Optimizing Compiler
« on: April 20, 2019, 10:24:33 am »
I'm starting to switch over to using an Abstract Syntax Tree (AST) for processing, and it is honestly more fun than I thought it would be. The code for optimizing the subexpressions is much easier. For example, x*2^n ==> x<<n, or x+1 converted to x++ (in this case an increment, not increment and assignment).


I started back up the bad habit of hardcoding some things just to get it to work, so I'll need to work on that!

The current big issue is with more complicated expressions like (x+y)+(x+1). This doesn't look like it should be complicated, but it basically evaluates this tree:
Code: [Select]
    Disp
     |
     +
    / \
   /   \
  ++    +
  |    / \
  x   /   \
     y     x
It freezes up trying to compile the subtrees while getting the outputs in the right order. This is due to how terribly I hacked together the code that tracked input and output. My goal is to come up with a well-defined way to pass and receive arguments (including allowing stack and variable juggling as glue code :P)

9
ASM / Re: Miscellaneous ASM Questions
« on: April 19, 2019, 12:04:45 pm »
Oh, you might actually be able to do that relatively easily. If there is a getKey code for the tau token (you'd have to look it up, there might not be), then you could use a getKey hook to override a [PI] keypress.

Then you also have a parser hook that replaces all of the tau tokens with 2pi before passing it back to the OS parser. The nice thing is that 2pi takes 2 bytes and tau is a 2-byte token, so you don't even need to resize. I don't think the parser hook has a mode for when a program ends, so you won't be able to re-replace the 2pis as taus that way, but you could probably make your getKey hook do it!

EDIT: there is in fact a ktau in the ti83plus.inc ! You'll want to use the RawKeyHook and the Parser hook.

10
TI Z80 / Unnamed Optimizing Compiler
« on: April 17, 2019, 11:30:48 pm »
Hi, for a long time I've wanted to create a compiler (targeting the Z80) that was even better at optimizing. Back when I was first brainstorming a Grammer compiler, I had in mind the issues of existing Z80 C compilers and even Axe. The Z80 really is poorly suited to C, but Axe is actually pretty amazing (as many know). One thing that C, Axe, and Grammer all have in common is a standard way of passing arguments. For example, in the latter cases, the first arguments are passed in HL and BC (respectively). This doesn't always produce optimal code, but it is a lot easier to work with.

So my fantasy was writing a program on my computer that tried to find a more optimal way of passing arguments. I haven't managed it, but it is a lovely dream :)

I want to put this small, undocumented set of programs out for the public. I wrote it today and there are a bunch of issues, but on some code it works really well.

As an example, here is an example of input:
Code: [Select]
Disp((2*x+1)*6+x)
Disp((27*x+1)*4+x)
And output:
Code: [Select]
  ld hl,(var_x)
  add hl,hl \ inc l
  ld b,h \ ld c,l \ add hl,hl \ add hl,bc \ add hl,hl
  ld de,(var_x)
  add hl,de
  call disp_uint16
  ld de,27
  ld hl,(var_x)
  call mulHLDE
  inc hl
  add hl,hl \ add hl,hl
  ld de,(var_x)
  add hl,de
  call disp_uint16

irToZ80.db basically contains the conversions from a high-level token to low level assembly. Each routine has input and output registers defined, as well as size and timing to use as metrics for optimization.

I reused tokens.db from another project, all that is important is name, type, and precedence.

If you run ./compile, it passes test.txt through sy.py to convert the source code into an intermediate representation (basically RPN), then passes that file through irToZ80.py to generate Z80 assembly code.

I basically implemented what I think is Djikstra's Shortest Path algorithm to find the solution that minimizes the target metric. In this case, I try to find the code that minimizes (6*size)^2+(speed)^2.

11
ASM / Re: How do I load a symbol into a string?
« on: April 16, 2019, 08:50:06 pm »
Well it should be the same code with the push \ pop and at the top bcall(_RclAns) \ bcall(_ConvOP1).

12
ASM / Re: How do I load a symbol into a string?
« on: April 16, 2019, 08:40:24 pm »
You mean the OS variable, Ans (which is a float), converted to an 8-bit integer and then stored as a byte in Str0 ?

13
ASM / Re: How do I load a symbol into a string?
« on: April 16, 2019, 08:34:44 pm »
I'm going to be honest: at this point, I'm not sure I understand what you are asking. I thought you wanted to store the A register into Str0 as a byte?

14
ASM / Re: How do I load a symbol into a string?
« on: April 16, 2019, 08:17:26 pm »
Oh, just do same code, but push af first, and then instead of ld (hl),tA use pop af \ ld (hl),a

15
ASM / Re: How do I load a symbol into a string?
« on: April 16, 2019, 07:28:48 pm »
Do you mean the token, "A" ?
You'll need to verify that the string exists, then verify its size. Then it is simply a matter of writing the token. In this case, it is a 1-byte token and happens to correspond to the ASCII value (0x41).

If all you want is to make Str0="A", the easy way is to check if it exists, delete it if so, then create a new string of size 1, then load the bytes into it.
Code: [Select]
; Load the name into OP1
 ld hl,$09AA    ; internally, Str0 is represented as 0xAA09
 ld (OP1+1),hl

; Check if it exists and delete if necessary
 rst rFindSym
 jr c,make_str0
 bcall(_DelvarArc)
make_str0:

; Now create Str0 with size 1. Put the name in OP1 first
 ld hl,$09AA
 ld (OP1+1),hl

; Size is 1 byte
 ld hl,1
 bcall(_CreateStrng)

;Pointer to size bytes is in DE. Switch to HL
 ex de,hl

; Don't need the size, so skip those two bytes and get to the start of the data
 inc hl
 Inc hl

; Now write the token
 ld (hl),tA    ; if using ti83plus.inc. same as $41 or in this specific case, 'A'

;Done!
 ret
Please note that I haven't tested this; I'm on mobile so it was heck to type as it is :D

Pages: [1] 2 3 ... 306