Fix TAC.Language to allow better optimization and generality
- 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.