[Soot-list] Constant propagation analysis in SOOT

Fri Sep 13 10:08:26 EDT 2013

I am not sure what you mean by 'merging' - arithmetic expressions?

I gave some thought about it, and maybe it can be done. IFDS is very
flexible. If I have the following jimple statement:

c = a + b

And a and b are known constants at this point, then you can generate a
fact for c with the value of a + b.

However, since IFDS works with separable variable problems, that means
that this expression could not be resolved right away. We would need to
inline the constant value of a and b and handle it in a second run.

There is a way to cheat though, and have it happen on the same run. The
HEROS flow function factory could be doing the inlining one variable at
a time and generate a fact for c the moment that all expressions are
inlined.

So we have c = a + b
Flow function for a=12 -> c = 12 + b -> return identity
Flow function for d=whatever -> no change -> return identity
Flow function for b=-4 -> c = 12 + -4 = 8 -> return b=-4 and c=8

One concern that I have is that the lattice for the set of all integers
could consume a lot of memory. I am not sure what the implementation is
like, but we'd probably need an
integer-list-morphing-into-a-sparse-bit-vector data structure to encode
that. This article gives us a good idea of which data structure to pick:
http://lemire.me/blog/archives/2012/10/23/when-is-a-bitmap-faster-than-an-integer-list/
(but note that the bench mark is for intersection only - we could have a
different break-even point)

The other problem is when a constant can have more than one possible
value - this method won't let you calculate the possible value ranges.
There could be cases when you could be getting a constant result anyway.

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

On 09/11/2013 11:35 AM, Bernhard Berger wrote:
> 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
>>
>>
> 
> 