[Soot-list] How can I tell if the two arrays overlap?

[Quentin Sabah]

Hi John,

> For the set of statements that I'm interested in (statements in a loop),
> I'll look for array references at the left of assignment statements, and for
> each such array reference, I'll search for definitions of the array
> references' bases (arr[i]'s base is arr) and follow such definitions until I
> reach a newarray Jimple value. During that recursive traversal process, if I
> run into any array bases that were found previously, then that's an
> indication of overlapping arrays.

You can use a points-to analysis to get the set of objects that may be
reachable from an array's elements. Take a look at 
PointsToAnalysis.reachingObjectsOfArrayElement:
http://www.sable.mcgill.ca/soot/doc/soot/PointsToAnalysis.html#reachingObjectsOfArrayElement(soot.PointsToSet)

If you only need to know if a given array $a may be referenced by the 2D 
array $b, you may take a look at the intersection of the points-to set 
of variable $a and the points-to set of the $b array's elements.

However, their is, to my knowledge, no existing analysis that maintain a 
points-to analysis on an array element basis. Also consider fine-tuning 
the points-to analysis to set the correct sensitivity/insensitivity to 
context and flow.

-- 
Quentin Sabah, CIFRE Ph.D. student
Grenoble University
INRIA-SARDES                   | STMicroelectronics/AST
Montbonnot, France             | Grenoble, France
mailto:quentin.sabah at inria.fr  | mailto:quentin.sabah at st.com
phone: +33 476 61 52 42        | phone: +33 476 58 44 14