[Soot-list] How does Jimple preserve semantics with its partial SSA without Phi-node mechanism?? (with an example illustrating my idea)

[Laurie Hendren]

Hi All,

The local splitter divides local names as much as possible, without 
introducing phi-nodes.   It effectively gives a unique variable name to 
each UD-DU web.    The way this works is basically like this.  Pick a 
definition,  say  x=rhs.    Now find all uses of x,   for those uses 
find all defs of x,  for those defs find all uses,   and so on until you 
don't find any more uses or defs.       All those uses and defs are the 
UD-DU web for x.     Now you can rename x to a unique name, say x1, by 
renaming all the uses and defs in the web.

Here is a trivial example

x = 3;
...
y = x + 1;
x = 4;
...
z = x + 2;


becomes


x1 = 3;
...
y = x1 + 1;
x2 = 4;
....
z = x2 + 2;


Here is a more complicated example:

x = 3;
if (exp)
    x = x + 1;
else
    ...;
y = x + 2;
x = x + 1;

becomes

x1 = 3;
if (exp)
   x1 = x1 + 1;
else
    ...;
y = x1 + 2;
x2 = x1 + 1;

The reason you want to split the locals like this is that it will give 
you better precision for flow-insensitive analyses,  and it will remove 
unnecessary anti and output dependencies.

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

The local packer is something you might do after you have done all your 
analyses and transformations.  Because the splitter may have created a 
lot of local variables,  you *might* want to reduce the number of local 
variables in the final Jimple,  particularly if you are generating some 
higher-level code.     The local packer is basically like a register 
allocator,  except that will only allocate the same variable name to 
locals of the same type.

Cheers, Laurie





+--------------------------------------------------------------
| Laurie Hendren --- http://www.sable.mcgill.ca/~hendren
| Associate Dean (Academic), Faculty of Science
| Professor, School of Computer Science, McGill University
| *** New McLAB Release ***
| *** http://www.sable.mcgill.ca/mclab/Software.html ***
| Other Proj: www.sable.mcgill.ca/soot  www.sable.mcgill.ca/abc
+--------------------------------------------------------------

On 12/07/2012 6:40 AM, Quentin Sabah wrote:
>> Jimple is not SSA, but I think it is somewhat SSA because local variables have unique name whenver possible. Right?
> Mmh, Single Static Assignment means a variable is assigned only once in a method body, thus Phi-nodes are required when a variable may take different values depending on the control-flow.
>
> In Jimple it is perfectly allowed to re-assign a variable. However it generates a lot of temporary variables (the one starting with a $ sign), these variables usually represent values located on the stack in the JVM (operands and results of instructions). Reusing variable names is an optimization for the bytecode generation.
>
>