Solution for Interprocedural Analysis in-class Exercise

[Eric Wohlstadter]

Hi all,
You can find the solution for the interprocedural analysis in-class
exercise here: http://www.ugrad.cs.ubc.ca/~cs410/interproceduralExerciseSolution.pdf

Eric

[Dave Dosanjh]

Why is q not represented in the solution set of any node in the
testMethod CFG?

Thanks

Dave

[Dave Dosanjh]

If we were using method inlining, I can see q would not be included in
any solution set, because the return from getNextObject would have no
associated solutions, since we can infer its call to testMethod will
not return null, given the specific arguments passed. But using
summary, as the solution does, my understanding is we have to consider
possible solutions from testMethod irrespective of where it is called.
This would mean q "may" be null.... right?

If the instructor someone else could help clarify this, it would be
greatly appreciated.

Cheers

Dave

[Eric Wohlstadter]

Hi Dave,

 Essentially, the only sources of null in this code is through "o" and "p", i.e. if getNextObject were ever to return null from its call to testMethod, it would be the case this null value came to it from "q" via "o" or "p". 

But a null "o" can never flow into "q" because the assignment to "q" is guarded by (o != null). 

Likewise, a null "p" can never flow into "q" because the assignment to "q" is guarded by (p != null).

This might not be easily apparent upon visual inspection, but it works out if we follow the rules of the analysis. 

Eric  

[Michelle C]

For the START node for testMethod, why is the set {o},{o,p}? Yet after the RETURN for the method, the set is only {o,p}?

Thanks,
Michelle

[Brian McMahon]

Why do we have the two node sets in the CFG solution {p,o} and {p}. I was thinking that it could be to represent each of the method calls to testMethod put neither of the calls have the possibility to have both p and o being null at the same time.

[Eric Wohlstadter]

Hi Michelle,

 I'm not sure which exercise you are referring to. From the in-class exercise, I see {p}, {o,p}, but I don't see {o}, {o,p}.

Eric

[Eric Wohlstadter]

Yes, you are right. It is "to represent each of the method calls to testMethod". Since it is a MAY analysis, we take the union. 

It's true that "neither of the calls have the possibility to have both p and o being null at the same time", but this is an approximation algorithm so it is not always completely accurate. These approximation algorithms are important because (for example) for functions with recursion or loops, we don't know how many times the recursion or loops will iterate, we don't know the values of all input variables, etc...

Eric

[Brian McMahon]

Ok so I guess I'm correct in assuming that that the set {p,o} refers to the call from getNextObject and that the reason you include both p and o in the set is because of the mutual recursion but even though we don't know how many times this recursion happens p will still always be set if testMethod is called. So am I to understand that even though this is true we are still supposed to assume that p will be null in the event of mutual recursions like that? 

Also, why does {p} disappear in testMethod?

[Kevin Tam]

I was wondering about the "pruning" aspect of the solution.

For example, inside testMethod, at o==null, we know that our solution
set {o,p} currently indicates to us that o may be null. Does that
mean we can "prune" the branch where o==null is false? In the
solution you put {p} on the false branch, but would it be okay to just
ignore this branch altogether and not even compute it?

Kevin

[Kevin Tam]

I suppose pruning those branches is only okay if you are profiling a
different function.. ie: main, since you only care about main you
should only care about the return value of testMethod, hence you can
prune the branches that are inconsistent with the solution set. Is
this the correct way to think about it?

[Eric Wohlstadter]

It's not ok to "prune" the branch where "o==null" is false, because the set {o, p} means that "o" might be null, not that we know for sure that it is null. 

On the other hand, on some branch where "o==null" is true, if "o" was not in the set, then we could prune the true branch, because there is no way "o" could be null.

Eric

[Eric Wohlstadter]

I'm not sure I understand your comment, but I can say:

The important thing to remember is that a variable being in the solution set in this analysis mean "might be null". This is not enough information to prune anything because it is not guaranteed.

Pruning is possible when something is not in the set, because not being in the set means, "must not be null". In that case, we can prune branches with that are inconsistent with that guaranteed information.

Eric