[LLVMdev] SSA or not SSA?

[Daniel Berlin]

On Thu, Jul 17, 2008 at 6:34 AM, Matthieu Moy <Matthieu.Moy at imag.fr> wrote:
> Patrick Meredith <pmeredit at uiuc.edu> writes:
>
>> Memory is what the i32* points too.  The i32* itself is in a
>> register.  You can store to it as many times as you want, but you
>> can't change the address, because that would violate SSA.
>
> Thanks,
>
> For the record, I finally understood by making a few experiments:
>
> This is (obviously) valid:
>
>  define i32 @main() {
>         %some-variable = add i32 1, 1   ; integer with the value 1+1
>         %some-other-variable = add i32 %some-variable, 1
>         ret i32 %some-other-variable
>  }
>
> This is not (the assembler complains with ``Redefinition of value
> 'some-variable' of type 'i32' ''):
>
>  define i32 @main() {
>         %some-variable = add i32 1, 1   ; integer with the value 1+1
>         %some-variable = add i32 %some-variable, 1
>         ret i32 %some-variable
>  }
>
> but this one is:
>
>  define i32 @main() {
>         %some-pointer = alloca i32 ; declares an int in memory (stack)
>         store i32 42, i32* %some-pointer
>         store i32 54, i32* %some-pointer
>         %retval = load i32* %some-pointer
>         ret i32 %retval
>  }
>
> In short, "Single Assignment" means "Single '='", not "Single
> 'store'".

Sure, because store is not an assignment.
It would be impossible to correctly rename memory for all programs,
since may-alias is undecidable at compile time and must-alias is
uncomputable at compile time.
The best you can do are conservative approximations, which would mean
sometimes your ssa form would be wrong.