add flow-sensitivity

[damorim]

Considerar chamada de metodos em uma linha quando "targetLine" for especificado.

Considere que a linha "if (foo() > a.x)" eh a "targetLine".

Neste caso, todos os campos acessados por foo() devem fazer parte do read-set usado para encontrar dependencias de dados com esta linha.

target() {
...
if (foo() > a.x) {
..
}
...
}

[damorim]

Por favor, considere o caso abaixo como caso mais geral. O caso de uma chamada de metodo no contexto de uma linha de interesse eh mais especifico.

foo() {
// all dependencies that can flow to the target are relevant
// TARGET LINE
// ... irrelevant, if cannot flow to target
}

Em resumo, eh preciso considerar as dependencias de controle (atraves do CFG?) para saber o que pode propagar para a TARGET LINE.

P.S. isto foi discutido em sala, mas esquecemos de atualizar a issue

[tarsiswt]

I'm a bit confused about this.

So now we have to use some kind of flow-sensitive analysis to identify dependencies towards the target line. Are these control dependencies only? How does this relates to #12?

Can anyone provide examples of how this might work?

[damorim]

Yes, this is (indirectly) related to issue #12.

Yes, we are trying to make the analysis flow-sensitive. This makes sense only in the context where the user informs a target line. The impact of this change (in size of dependency graph) depends on the size of the program and location of the target line.

Clarification:

• Check function foo() above (again).
• Consider the part after the TARGET line: There could be several read accesses in this region. They are all irrelevant to compute TARGET.
• Consider the part before the TARGET line: there could be read accesses in the region that influences the computation of TARGET. So, we do not want just to filter read accesses that arise in this line, we actually need to consider any access that can reach it. Otherwise, the analysis will not be sound.

P.S. This is important but not critical. I created another label to differentiate these cases.

[imlm]

In class there was a mention to use the program CFG to find dependencies for the target line. I was wondering if we could not just use a DefUse to transitively find these dependencies.
The pseudo-code would be like this:

find every use in targetLine
for each use u do:
    transitively look for definitions of u

To transitively look for definitions we would use the methods SSAInstruction.getNumberOfUses -> SSAInstruction.getUse -> DefUse.getDef -> SSAInstruction.getNumberOfUses -> SSAInstruction.getUse -> DefUse.getDef -> ...

At every definition site we would check for field accesses and method calls to accumulate the read set that will be used when building the dependency graph.

Does this sound reasonable? Or am I missing something?

[imlm]

Consider the following example:

public class FooFlowSensitivity {

  int x, y, z;
  static int w;
  ...

  public void read1(){
    int a =  w;
    foo();
    if(a > 20){ /* targetLine */
      ...
    }
  }

  private void foo() {
    w = x + y + z;
  }
  ...
}

In the method read1(), should an edge between foo() and read1() exist?
foo() writes in w, but w is always read before the call to foo().

In a more general way, should the following flow consist in a dependency?

...
{read-to-field}
{write-to-field}
{indirect-read-to-field} [optional]
...

If yes, then simply using the DefUse information won't be enough, if no, simply using the CFG would give us imprecise results!

[imlm]

During class today someone inquired about the behavior when we a have loop construction.
The example below shows how a loop could actually be problematic when computing the read set that may flow to target line simply using DefUse.

public class FooFlowSensitivity {

  int x, y;

  public void readLoop(){
    while(x > 0){ // targetLine
      bar(); // reads y
      foobar();
    }
  }

  private void foobar() {
     y--;
  }

  private void bar() {
      x = y;
  }
}

If we simply used DefUse we would miss the read dependency at the call to bar() in the while loop.

For now I dropped the idea of just using the DefUse analysis and the current implementation uses a CFG instead.
I am still wondering if we can make use of DefUse information to refine the results of this CFG-based implementation.