Svadev mailing list

[Ott Tinn <llvm AT otinn.com>]

On 20 August 2012 21:33, John Criswell 
<criswell AT illinois.edu>
 wrote:
> 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.
Fixed.



> 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)?
It will create the same (pointer to) SCEV. This makes it possible to
remove otherwise identical fast load/store checks from different
objects.

One of the most complicated cases this pass can solve is the following:
int array1[50];
int array2[50];
for (int i = 0; i < idx; ++i) {
  array1[i] = i; // first check (kept)
  if (condition)
    array2[i] = i; // second check (removed)
}
Full test: 
https://github.com/otinn/llvm/blob/master/test/Instrumentation/MemorySafety/optimization/implication/0040.ll

SCEVs of the first check:
access pointer: 
{@array1,+,4}<%for.body>
object pointer: @array1
access offset: {0,+,4}<%for.body>

SCEVs of the second check:
access pointer: 
{@array2,+,4}<%for.body>
object pointer: @array2
access offset: {0,+,4}<%for.body>



> 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).
As far as I know it just creates an analysis object and SCEVExpander
could be used to turn it into code (not needed in this case).



> 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.
It has been used for compiling all of Chromium which has a bit over
6.5M load/store checks after the initial instrumentation.



> 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.
I added more comments throughout the code. If more/different styled
comments should be used then let me know.



> 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.
>

Attachment: optimize-implied-fast-ls-checks-v2.patch
Description: Binary data