Handle control flow on dot graphs. - Phi Nodes

[Aaron3154518]

Some functions have multiple possible returns. Currently we use the same return data space for each return which creates multiple writes with no read in between.

Example:
Eval_Spline_F() either returns 0.0 or - if an if statement is triggered - an expression. The return variable is first assigned 0 and then assigned the expression with the if conditions placed in it's iteration space. The 0 assignment then has no reads and exists separate from the graph.

[Aaron3154518]

From Dr. Olschanowsky on Slack:

we need to add what is called a phi node or a join.
First, we have to detect this is happening. This means finding statements that happen 0 or N times. (the 0 being very important)
In this case the if statement makes it so that the second assignment will happen 0 or 1 times
One option is to refactor the code to avoid this case.
That means adding an else
Then we have to be sure that when we have an if and an else the versioning is done in such a way that they get the same name

1. identify this case
2. find the condition that causes it (k<N) for example
3. add a phi node to the computation (this will be needed for correctness) if(condition) var = var_1 else var = var_0

So when we add a statement - check to see if it writes to a dataspace that already exists. If it does - check to see if the statement might execute 0 times. If so, add the statement and add the phi node
This won't work if several statements all have the same condition that creates the issue. Then we need to wait on adding the phi node

[Aaron3154518]

We have N constraints.
Constraint 1 (C1) contains a read for dataspace D.
Constraint 2-(N-1) contain writes to D and have some unique constraint(s) within them.
Constraint N contains a write to D and has no unique constraint.

[Aaron3154518]

Example:
foo = 0; // C4 (3rd write) Stop here because C3 has no unique constraints.
if (j > N) {
foo = 4; // C3 (2nd write) Don't stop because C2 has a unique constraint (j > N)
}
if (i > N) {
foo = 1; // C2 (1st write) C2 != C1 (i > N)
}
bar = foo; // C1 (read)

[Aaron3154518]

Definitions:

1. Source read - the statement which reads from the variable for which we are generating a phi node. (the statement which triggers the phi node search)
2. Guaranteed write - The nearest write which is guaranteed to occur. This means every condition which governs its execution also governs the source read's execution
3. First write - The nearest write, no matter what conditions govern its execution.

Locate phi node:
At each read:

• Loop backwards through statement
  • Identify a guaranteed write and a first write

If there is no guaranteed write or the guaranteed write is also the first write, no phi node is needed.

Add phi node:
Get the iteration spaces for the source read and first write and project out (remove) all iterators.
Get the conditions from the first write which are not in the source read

• Conditions for the source read are guaranteed to be true when we reach the source read and thus are unnecessary to evaluate

Generate a phi statement of the form var = conditions ? first write : guaranteed write;

Other Notes:
If a condition is true, it is removed from the list of conditions. We have no conditions if all conditions are true.
If a condition is false, all conditions are removed.
To differentiate between these two cases, we add a new condition test__ == 0. This condition cannot be resolved to true/false and will not be removed when projecting out iterators. Thus:

• If we have no conditions, test was removed by another condition being false
  • generate var = guaranteed write; instead of var = false ? first write : guaranteed write;
• If we have one condition, it must be test and so all other conditions are true
  • generate var = first write; instead of var = true ? first write : guaranteed write;
• If we have 2+ conditions, then we have legitimate conditions to evaluate. Add all of them except test
  • generate var = conditions ? first write : guaranteed write;

[Aaron3154518]

Phi nodes implemented!!!!!!!!!!!

[Aaron3154518]

Issues remaining:

• phi nodes copy their execution schedule from the statement for whom they are generated. We should give them their own execution schedule
• If a phi node is ever added using addStmt(), it will generate another phi node, which is unnecessary and causes problems like double SSA renaming (var__w__2__w__3). This happens in appendComputation(), for example. To avoid this, we end phi statements with ;; instead of ;. Then if we find ;;, we don't generate a phi node. We need a better solution for identifying phi nodes.
• All reads/writes for the phi node are given {[0]->[0]} as their access relation. This may not be correct, especially for conditions. We need to get the correct access relations.
• If a condition has multiple instances of the same data space, it will be recorded > once. When re-adding "$", this will add "$" > once. (We would end up with something like $$var$$). Use a set instead of a vector to store data spaces so that duplicates are ignored.

[Aaron3154518]

See #154 for fixing execution schedules