Svadev mailing list

[John Criswell <criswell AT illinois.edu>]

On 8/17/12 4:41 PM, Ott Tinn wrote:
> Hi,
>
> The attached patch adds an optimization pass that removes fast
> load/store checks that are implied by other fast load/store checks.
> It works by traversing a dominator tree to find out which checks must
> always happen before other checks.
> It looks for fast load/store checks that are dominated by other fast
> load/store checks with the same access offset, access size, and object
> size triple.

There are some questions/issues with the current code:

1) The AccessData code is making assumptions about the layout of C++ 
memory objects.  If you want to use memcmp(), you should enclose the 
data field members into a structure and explicitly memcmp() the structs.

2) I'm not sure that the memcmp() code is correct.  Does the SCEV Offset 
field in AccessData contain information on the memory object being 
checked (i.e., will accessing the same offset into two different memory 
objects generate distinct SCEVs or the same SCEV)?

3) Can SE->getMinusSCEV() modify the LLVM IR (by inserting instructions 
to compute the offset)?  If so, then a) we must always return that the 
module is modified, and b) find a way to remove the code inserted 
(probably via dead code elimination).

4) How large of a program have you tested this code on?  The recursion 
is probably fine, but it's nice to test on real programs.

The code could also use a lot more comments.  Specifically,

1) Each method should have a comment explaining what it does.  It should 
have
    a) A high-level description of what the method does
    b) A list of inputs and what the inputs mean
    c) A list of outputs and what the outputs mean
    d) A description of what the return values means
    e) A list of known side effects (e.g., some class member contain 
will contain the set of checks to remove)

2) There should be a comment describing each step of the algorithm. For 
example, in the code:

if (PreviousChecks.count(Access)) {
+      ToRemove.push_back(CI);
+    } else {
+      PreviousChecks.insert(Access);
+      LocalChecks.push_back(Access);
+    }

... you should put a comment like:

//
// Check to see if we have seen this check previously.  If so, schedule 
it for removal.  Otherwise, record that we
// have seen this check for when we investigate other checks.
//


3) Contains should have a comment explaining their purpose. Something 
should explain that LocalChecks is a container holding the checks in the 
current basic block while PreviousChecks is the set of all checks that 
dominate the current basic block.

You can find plenty of commenting examples in the SAFECode passes.

Finally, another thing you may want to think about is whether the code 
can be made faster or shorter by utilizing the STL set union, 
difference, and intersection functions.  I haven't convinced myself that 
it can be done, but it might be possible.  Just something to think about 
for future enhancement.

-- John T.