SSA without phi

Hi Nicolas


In average programs, basic blocks are rather small, but the ones in
graphics (openGL) they can be larger.


What you will get:
1) Def-Use links, these you can get trivially in a basic block without ssa also
2) You will be able to have slightly more leeway in code motion (by
giving different definition number of each def)


You will lose most advantages that actually come with SSA:
1) Many uses will be defined outside your basic block and many
definitions will be used outside, no algorithm will work in uniform
way.
2) SSA reduces complexity of def-use webs, and therefore the
optimizations, you will get no advantage here


For complexity, you will probably only add more:
You will require renaming/color-out to fix this to come out of ssa
(you can't really have renamed ssa because you are unaware of stuff
outside your basic block)


The benefit of having SSA therefore is negligible, you could just use
non-ssa algorithms, they are not complex for a basic block


>> I would prefer keeping my intermediate code executable at all time.
This would
>> make it easier to reason about optimizations and follow every step (*).


You could think of it as nop :-). I am not sure if any reasoning will
be made easier.
I would suggest getting more familiar with SSA


>> (*) This is also a bit of a philospohical opinion. I want my compiler
>> to behave in a way that a programmer would optimize code


I would not like to think of compiler as an emulator of human optimizing code
Compiler can do symbolic evaluation, specialization, context sensitive
cross function stuff, inlining, register allocation etc.
The purpose of human is to make code maintainable, readable and stuff
also, compiler has no such restrictions


Best of luck :-)


~Inderaj Bains


---------------------------------------------------


I'm wondering whether it is possible to get (part of) the benefits of
SSA by using it only per basic block. This way I could avoid all the
complexity of phi functions.




The problem with phi functions is that they're not executable. I would
prefer keeping my intermediate code executable at all time. This would
make it easier to reason about optimizations and follow every step
(*). It's also fairly complex (almost convoluted in my opinion) to
correctly compute where to insert phi functions, especially when
trying to keep their number low.


So what I propose is to have single-assignment per basic block, but
allow reassignment of the same variables in other basic blocks. Is
this a known technique that has been compared to full SSA before? I
believe that all optimizations that work per basic block would still
work correctly. Things like dead code elimination and copy propagation
could still benefit from the single-assignment property. And by simply
looking at uses and definitions per basic block it could still
optimize across basic blocks.


Does this "Block Single Assignment" make any sense or would I lose
some significant advantages of SSA with phi functions? Or is it
equivalent with a known technique that is proven to be less efficient?


Thanks for all insights,


Nicolas Capens


(*) This is also a bit of a philospohical opinion. I want my compiler
to behave in a way that a programmer would optimize code. SSA with phi
functions just isn't natural, while the idea of static assignment is
fundamental in functional programming and well understood.


--
~Inderaj

Return to the comp.compilers page.
Search the comp.compilers archives again.