Impact of an analysis pass on program run time

Project Infrastructure LLVM Dev List Archives
1

Hello,

I am working on finding good optimization sequences for a given program (phase ordering problem). I have the following setup.

  1. The source programs are translated into LLVM IR using -O0 + -scalarrepl.
  2. Find an optimization sequence using some strategy which translates the IR generated in the
    previous step into another IR.
  3. Apply llc -O2 and map the IR in to target assembly code.

Using the above setup I found that the sequence [-functionattrs, -loop-rotate, -licm, -basicaa] reduces the runtime of the program from 3.1 seconds (when compiled using -O2) down to 0.1 seconds. Removing any of the optimizations in the sequence including the analysis phase -basicaa increases the runtime back to 3.1 seconds or above. When I was explaining this strange behaviour in the HiPEAC conference some one asked me how can dropping an analysis phase will have an impact on the program runtime. Can some one explain what is happening here?

The program is office_stringsearch1 from the MiBench suite.

On the same lines the way we hit upon the sequence [-functionattrs, -loop-rotate, -licm, -basicaa] is by applying a sequence reduction algorithm wherein we take a long sequence (which we hit using genetic or random search algorithm) and keep dropping the optimizations until the program runtime doesn’t go up. So again the same question, why is that dropping -basicaa increases the program runtime?

-Suresh Purini

2

Hi Suresh, good alias analysis is essential for optimizing programs well. With
-basicaa you get decent alias analysis, without it you get poor quality alias
analysis. You may be wondering why -basicaa does something when it is listed
after the other options. I suggest you run opt with the -debug-pass=Executions
option (opt -help-hidden will show you this) to see the order in which things
are actually being run.

Ciao, Duncan.