[Soot-list] Constant propagation analysis in SOOT

[Bernhard Berger]

You are right. I didn't mention that. IFDS is not able to solve this kind of problem since it cannot "merge" expressions. I already tried it %-).


Am 11.09.2013 um 17:09 schrieb Marc-André Laverdière <marc-andre.laverdiere-papineau at polymtl.ca>:

> 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
>> 
> _______________________________________________
> Soot-list mailing list
> Soot-list at sable.mcgill.ca
> http://mailman.cs.mcgill.ca/mailman/listinfo/soot-list
> 
>