[LLVMbugs] [Bug 13225] New: AddressSanitizer produces intractibly slow compiles for global initializers

[bugzilla-daemon at llvm.org]

http://llvm.org/bugs/show_bug.cgi?id=13225

             Bug #: 13225
           Summary: AddressSanitizer produces intractibly slow compiles
                    for global initializers
           Product: new-bugs
           Version: unspecified
          Platform: Other
        OS/Version: All
            Status: NEW
          Severity: enhancement
          Priority: P
         Component: new bugs
        AssignedTo: unassignedbugs at nondot.org
        ReportedBy: chandlerc at gmail.com
                CC: kcc at google.com, llvmbugs at cs.uiuc.edu,
                    matthewbg at google.com, nlewycky at google.com
    Classification: Unclassified


After r159191 where Kostya enabled ASan instrumentation on global init 
functions, an old failure mode for ASan has become critical: it creates too 
many basic blocks.

Specifically, when instrumenting loads and stores, ASan creates new basic 
blocks.

Very large, mechanically generated global initializers (not uncommon sadly, 
more common than other large functions) produce *huge* global init functions.

When we enable ASan on the latter, it results in terrible slowdowns of the 
entire optimizer chain.

There are several conspiring bugs here:

1) MachineCSE seems to have N^2 (at least) complexity w.r.t. these *particular* 
basic block patterns. It's far and away the worst offender, and it clearly is 
an algorithmic bug within that routine. With that fixed we get down to 
extremely slow compiles rather than interminable compiles.

2) AddressSanitizer could almost certainly do something more clever to avoid 
the basic block count it currently imposes.

3) MachineBlockPlacement and a couple of other codegen passes are also slower 
than they "should be" for these inputs. They aren't the root of the problem, 
but they probably deserve some attention even as the other two aspects are 
fixed.


Until either #1 or #2 is fixed, I think r159191 has to be backed out, as this 
is... very frustratingly common.


I've attached a preprocessor-based C program that can be used to stress test 
these issues. Uncomment lines to watch the problem get worse. This could almost 
certainly be simplified, but it gives very nice "real world" sets of loads and 
stores which we can watch go throuh the optimization and codegen pipelines. The 
loads and stores are essentially identical in this test case to real world code 
we hit with this problem.

-- 
Configure bugmail: http://llvm.org/bugs/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
You are on the CC list for the bug.