1A: Improving CCP

Starting with our CCP pass, extend it to exploit information from the comparisons that control the etas. Your modifications should be limited to ssaopt.cc.

The main point of this part of the assignment is to get familiar with CASH and the data structures used to manipulate and traverse pegasus.

Your goal is to improve the ccp pass by understanding the effect of predicate evaluation on the kinds of values that can be passed by an eta node. In the following small C snippet and its assoiciated pegasus graph we can see an example of how we can improve the ccp pass.

Since we know that the only value of x that can be passed from the pink basic block to the blue basic block is 10, we can use that information to show that y, in the blue basic block, is 15 at output.

The approach you should take is to modify what happens for the op_eta arm of the main switch in Procedure:ccp().

1B: Implementing Aggresive Dead Code Elimination

Implement aggressive dead code elimination. Rather than starting with the assumption that all nodes are live, start with the assumption that all are dead, then mark them live iteratively. Your modifications should be limited to ssaopt.cc.

coding hint: to remove nodes permanently, use this code:

        ForAll(DeadIterator) {
              Operation* op = DeadIterator();
              op->getParent()->remove_dead_node(op);
        }

(although another way to do it might be to just disconnect their outputs, and then let regular DCE remove them.)

1B alternative

Change CCP to conditional range analysis. See us first if you choose this though to avoid taking on too big a project. Your modifications should be limited to ssaopt.cc.

To get the test case, do an update in Sample/2/.

Information on Pegasus internals is available through the Useful Info link. Also, there is a new reference paper for Pegasus/CASH on the Schedule page.

ALGORITHM HINTS

There is one thing that we glossed over a bit---the dataflow also performs constant folding (in the CCP elements, not permanently) when a foldable op has all Constant input CCP values. See the last bullet.
The Pegasus IR blurs the line between control flow and data flow. So now, we consider "executability" on a per-operation basis rather than on a per-basic-block basis. How does this change the algorithm? Is there any real difference between an Operation being "not executable" and its output Wire being "undefined"? What lattice values on a predicate input indicate that a predicated operation can execute? (Hint: see the code for handling an op_cal.) How does speculative execution affect the idea of executability?
Which Pegasus operation type or types correspond to phi nodes?
What nodes need to be initialized, and how? Constants? Procedure arguments?
Do you create a CCPelement for every Wire right away, or only on demand? This is a coding implementation matter -- either way will work.
There are two very useful routines for constant folding in simplify.cc:
```
bool Operation::constantFoldUnaryOp(immed left, immed* result);
bool Operation::constantFoldBinaryOp(immed left, immed right, immed* result);
```
If the operation can be folded to a compile-time constant, the constant is placed in the immed pointed to by result and return value is true. [If you see any bugs or assertion failures when using these routines, please e-mail us immediately.]