Svadev mailing list

[Ott Tinn <llvm AT otinn.com>]

On 21 September 2012 22:26, John Criswell 
<criswell AT illinois.edu>
 wrote:
> On 9/21/12 3:20 PM, John Criswell wrote:
>>
>> Dear Ott,
>>
>> Sorry for the long wait.  Please go ahead and commit this patch. You'll
>> probably need to adjust it slightly for the newly integrated libLTO and
>> Clang, but that should be pretty easy.
>
>
> BTW, do you have any lit tests for this optimization?  Now that I think
> about it, we should have some lit tests for the new optimization to make
> sure we don't break it in the future.
Yes, there are a few tests. There are also tests for other transforms
such as exactcheck-opt. I haven't tried to integrate any of them into
SAFECode's test system but it shouldn't be hard.

This optimization is covered under a set of tests that attempt to
capture some of the problems associated with optimizing checks based
on their failure being implied by an earlier check.

Implication tests:
https://github.com/otinn/llvm/tree/master/test/Instrumentation/MemorySafety/optimization/implication
The partitioning:
https://github.com/otinn/memory-safety-testing-utils/blob/master/test-partitions/implication.txt

Most of those tests are currently expected to fail because they were
created before the optimizations and the optimizations are not
advanced enough for all cases.

The most interesting successful case for this optimization:
https://github.com/otinn/llvm/blob/master/test/Instrumentation/MemorySafety/optimization/implication/0040.ll




>
> -- John T.
>
>>
>> -- John T.
>>
>> On 8/21/12 1:41 PM, Ott Tinn wrote:
>>>
>>> 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.
>>>>
>>
>> _______________________________________________
>> svadev mailing list
>> svadev AT cs.uiuc.edu
>> http://lists.cs.uiuc.edu/mailman/listinfo/svadev
>
>