JKTKops / JKTKops/cspim

Fix TAC.Language to allow better optimization and generality

Open
#12 1 comment 0 reactions 0 assignees View on GitHub
bug
Dominant language
Haskell
Stars
5
Forks
0
PR merge metrics
No merged PRs in 30d

Description

Currently, RValues and LValues are set up to have _separate_ cases for accessing pointers vs arrays. But it makes more sense to degrade arrays into pointers at the TAC level, so that they can be properly optimized as such. The only RValue cases should be `RVar Var` and `RDeref Unique Offset`.

`RDeref` checks the type of the unique. If it is an array type, then it is treated as a pointer to its base offset. Otherwise, it is treated as a variable storing a pointer, and that pointer is loaded. In both cases, the resulting pointer is dereferenced. The unique in `RVar (Left unique)` continues to refer to the base offset of an array when `unique` has array type. Thus,
```
x[2];
```
becomes
```Haskell
LVar temp0 := RVar (Left x) -- &x
LVar temp1 := Binop (RVar (Left temp0)) Add (RVar (Right (IntConst 8))) -- &x + 8
LVar temp2 := RDeref temp1 0 -- *(&x + 8) ~ x[2]
```
which can get optimized to
```
LVar temp0 := RDeref x 8
```
and becomes MIPS
```
lw $v0, (8 + base offset of x)($fp)
```
or if x is at a label/GP offset:
```
lw $v0, x+8
```

In line with this, the code generator should be blinded to computing offsets; variables added to pointers should have their offset-multiplying instructions visible in the TAC. This lets us optimize, for example:
```
char x[5][5];
int y;
x[y];
```
becomes:
```
temp0 := y * 5
temp1 := temp0 + x
*temp1
```
And this would turn into MIPS:
```
lw $v0,
li $v1, 5
mult $v0, $v1
mflo $v0
addu $v1, $fp,
addu $v0, $v0, $v1
lw $v0, 0($v0)
```
However this mips is not good! For QtSpim, `mult` is a fast instruction, but on real machines it is not. We can optimize this TAC into:
```
temp0 := y << 2
temp1 := temp0 + y
temp2 := temp1 + x
*temp2
```
Which not only avoids `mult`, but is also purely 1 less instruction.

Just an example of why this method seems better.

Contributor guide

No contributing guide indexed for this repository

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.