Svadev mailing list

[John Criswell <criswell AT illinois.edu>]

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.

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