[Soot-list] Constant propagation analysis in SOOT

[Marc-André Laverdière]

Just adding my two cents.

If you want to maximally propagate constants, then you would need

a) A fixed-point algorithm, since you want to calculate the arithmetic
expressions, and thus create new constants along the way
b) An interprocedural analysis

Marc-André Laverdière-Papineau
Doctorant - PhD Candidate

On 09/11/2013 01:18 AM, Bernhard Berger wrote:
> Hi Zhoulai,
> 
> I think that you are correct and the result of a constant expression is
> not propagated. I think that you have to implement your own constant
> propagation if you want to do the following steps a) propagate constants
> b) calculate the results of "constant expressions" c) propagate the
> results of constant expressions and d) "merge" constants with same
> value. Take a look at [1] for more details on intra-procedural analysis
> in Soot. Furthermore there is a Visitor-Pattern for statements and
> expressions [2], [3].
> 
> Bernhard
> 
> [1] http://www.bodden.de/2008/09/22/soot-intra/
> [2] https://github.com/Sable/soot/blob/develop/src/soot/jimple/AbstractStmtSwitch.java
> [3] https://github.com/Sable/soot/blob/develop/src/soot/jimple/AbstractExprSwitch.java
> 
> Am 10.09.2013 um 09:05 schrieb Zhoulai FU <zhoulai.fu at gmail.com
> <mailto:zhoulai.fu at gmail.com>>:
> 
>> Hi, Bernhard,
>>
>> Thanks for your quick reply.  My expected results will be a mapping
>> from 'x' to the value lattice 3 and 'unknown', respectively for  
>>
>> y=3; z=3; if (?) {x=y} else {x=z};
>> and 
>> y=2; z=4; if (?) {x=y} else {x=z};
>>
>> If I understand correctly, the current implementation in SOOT's
>> "soot.jimple.toolkits.scalar.ConstantPropagatorAndFolder" takes only
>> one pass  (thus its algorithm should be  linear), so I think it would
>> be easier to rewrite the analysis than to extend it for a more precise
>> constant propagation.  Let me know pls if I misunderstand. 
>>
>>  Zhoulai
>>
>> On Sep 10, 2013, at 7:37 AM, Bernhard Berger <berber at tzi.de
>> <mailto:berber at tzi.de>> wrote:
>>
>>> Hi Zhoulai,
>>>
>>> what is the result you want to get? Just the fact that x in print(x)
>>> is constant in all cases or that x is definitely 3 (what would be
>>> your expected result in the case that y = 2 and z = 4)? Do you want
>>> this information intra procedural or inter procedural?
>>>
>>> The ConstantPropagatorAndFolder works in a intra procedural way and
>>> propagates nuemric constants and calculates the result of expressions
>>> on numeric constants. I think the current implementation can be
>>> extended to a version that checks that all definitions of a use have
>>> the same constant value. If you change the code feel free to
>>> contribute the enhancements back to the soot community.
>>>
>>> Regards,
>>>
>>> Bernhard 
>>>
>>> Am 10.09.2013 um 07:19 schrieb Zhoulai <zell08v at gmail.com
>>> <mailto:zell08v at gmail.com>>:
>>>
>>>> Dear all,
>>>>
>>>> I am about to use  a constant propagation/folder  analysis under
>>>> Soot framework. It seems  that there exists  one such implementation
>>>> in SOOT already:
>>>>
>>>> soot.jimple.toolkits.scalar.ConstantPropagatorAndFolder
>>>>
>>>> However,  this implementation seems to be naive.  If I understand
>>>> correctly its source code,
>>>>
>>>> http://www.massapi.com/source/sootsrc-2.4.0/src/soot/jimple/toolkits/scalar/ConstantPropagatorAndFolder.java.html
>>>>
>>>> the implementation associates with local variables a constant only
>>>> if this  underlined variable has a single definition site.   For
>>>> example, the implementation  cannot decide that 'x' is a constant 
>>>> for the snippet below:
>>>>
>>>> y=3; z=3; if (?) {x=y} else {x=z};
>>>> print (x);
>>>>
>>>> In my application, I need that 'x' be recognized as constant.
>>>> Although this is not a difficult problem, I would try to avoid code
>>>> duplication whenever possible. So would you please tell me whether
>>>> Soot has built in a more sophisticated constant propagation analysis
>>>> than its "ConstantPropagatorAndFolder" mentioned above, such as the
>>>> conditional constant propagation?  Thanks in advance.
>>>>
>>>> Zhoulai (zell)
>>>>
>>>>
>>>>
>>>> _______________________________________________
>>>> Soot-list mailing list
>>>> Soot-list at sable.mcgill.ca <mailto:Soot-list at sable.mcgill.ca>
>>>> http://mailman.cs.mcgill.ca/mailman/listinfo/soot-list
>>>
>>
> 
> 
> 
> _______________________________________________
> Soot-list mailing list
> Soot-list at sable.mcgill.ca
> http://mailman.cs.mcgill.ca/mailman/listinfo/soot-list
>