Re: [PATCH] Asan static optimization (draft)

[Konstantin Serebryany <konstantin dot s dot serebryany at gmail dot com>]

BTW, here is one particular kind of static analysis which I am very
much interested in:
https://code.google.com/p/address-sanitizer/wiki/CompileTimeOptimizations#Escape_analysis_for_use-after-return

Here we can prove that a does not escape foo() and thus we may avoid
putting it on fake stack.

int bar();
int foo(unsigned i) {
  int a[3] = {bar(), bar(), bar()};
  return a[i % 3];
}

--kcc

On Tue, Aug 19, 2014 at 4:42 PM, Konstantin Serebryany
<konstantin.s.serebryany@gmail.com> wrote:
> On Mon, Aug 18, 2014 at 1:05 PM, Yuri Gribov <tetra2005@gmail.com> wrote:
>> On Fri, Aug 15, 2014 at 10:34 PM, Konstantin Serebryany
>> <konstantin.s.serebryany@gmail.com> wrote:
>>> If this is -O1 or higher,  then most (but not all) of your cases
>>> *should* be optimized by the compiler before asan kicks in.
>>
>> You mean hoisting memory accesses from branches?
>> Sure, the tests are simplified beyond all limits.
>> On the other hand even basic aliasing constraints
>> would obviously prevent optimization of pointer accesses
>> (but not of Asan checks!).
>
> Exactly. I am interested in full non-simplified tests where the
> regular optimizer has no chances,
> but asan- (tsan-, msan-) specific optimizer has.
>
>>
>>> (This may be different for GCC-asan because GCC-asan runs a bit too
>>> early, AFAICT. Maybe this *is* the problem we need to fix).
>>
>> Thanks for mentioning this, I'll try to experiment
>> with moving Asan pass across the compilation pipeline and
>> report my findings.
>>
>>> I am mainly interested in cases where the general optimizer can not
>>> possibly improve the code,
>>> but asan opt can eliminate redundant checks.
>>
>> As I mentined, I believe that aliasing may often restrict
>> optimizer's code hoisting ability.
>> And we certainly need Asan opt for combining checks.
>>
>>>> I already have a bunch of tests (which I plan to extend further). How
>>>> should I submit them s.t. they could be reused by LLVM?
>>>
>>> Maybe just start accumulating tests on the CompileTimeOptimizations wiki
>>> (as full functions that one can copy-paste to a .c file and build)?
>>> Once some new optimization is implemented in a compiler X,
>>> we'll copy the test with proper harness code (FileCheck/dejagnu/etc)
>>> to the X's repository
>>
>> Ok, so I'll firstly post tests on wiki and explicitely reference their
>> origin when submitting patches.
>>
>>>> Perhaps there is some prior work on verification of Java
>>>> range checks optimizers?
>>>
>>> There is ton of work for range check optimizers,
>>> but none of that
>>> fully applies to asan,
>>> since asan also checks use-after-free and init-order-fiasco.
>>
>> Could you give more details? How would
>> use-after-free/init-order-fiasco influence verification of redundant
>> elimination?
>
>
> Consider this:
>
> extern void foo(int *);
> int *a = new int [10];
> foo(a);
> ... = a[5];
>
> here, a[5] can not go out of bounds and regular Java-oriented
> algorithms will mark this as safe.
> However, foo() may delete 'a' and we'll have a use-after-free here.
>
> --kcc