Reordering IR-level optimization passes.

[atrick]

Bugzilla Link	17809
Version	trunk
OS	All
CC	@hfinkel

Extended Description

In July, I proposed a new pass order pipeline that was fairly well received http://thread.gmane.org/gmane.comp.compilers.llvm.devel/63921

(There is a natural conflict between loop-nest-optimization and an otherwise efficient optimization pipieline, which this proposal does not solve).

However, the work is stalled. To make progress, we would need to begin taking incremental steps. It might be helpful if the new PassManager design is introduced first, but that isn't a requirement.

I'm filing a bug report now so people can add test cases or relate this to other bugs. That will help motivate the work.

Here is the original proposal:

Canonicalization passes are designed to normalize the IR in order to expose opportunities to subsequent machine independent passes. This simplifies writing machine independent optimizations and improves the quality of the compiler.

An important property of these passes is that they are repeatable. The may be invoked multiple times after inlining and should converge to a canonical form. They should not destructively transform the IR in a way that defeats subsequent analysis.

Canonicalization passes can make use of data layout, but are otherwise target independent. Adding target specific hooks to these passes can defeat the purpose of canonical IR.

IR Canonicalization Pipeline:

Function Passes {
SimplifyCFG
SROA-1
EarlyCSE
}
Call-Graph SCC Passes {
Inline
Function Passes {
EarlyCSE
SimplifyCFG
InstCombine
Early Loop Opts {
LoopSimplify
Rotate (when obvious)
Full-Unroll (when obvious)
}
SROA-2
InstCombine
GVN
Reassociate
Generic Loop Opts {
LICM (Rotate on-demand)
Unswitch
}
SCCP
InstCombine
JumpThreading
CorrelatedValuePropagation
AggressiveDCE
}
}

IR optimizations that require target information or destructively modify the IR can run in a separate pipeline. This helps make a more a clean distinction between passes that may and may not use TargetTransformInfo.

TargetTransformInfo encapsultes legal types and operation costs. IR instruction costs are approximate and relative. They do not represent def-use latencies nor do they distinguish between latency and cpu resources requirements--that level of machine modeling needs to be done in MI passes.

IR Lowering Pipeline:

Function Passes {
Target SimplifyCFG (OptimizeCFG?)
Target InstCombine (InstOptimize?)
Target Loop Opts {
SCEV
IndvarSimplify (mainly sxt/zxt elimination)
Vectorize/Unroll
LSR (move LFTR here too)
}
SLP Vectorize
LowerSwitch
CodeGenPrepare
}

The above pass ordering is roughly something I think we can live
with. Notice that I have:
Full-Unroll -> SROA-2 -> GVN -> Loop-Opts
since that solves some issues we have today.

I don't currently have any reason to reorder the "late" IR optimization passes (those after generic loop opts). We do either need a GVN-util that late loops opts and lowering passes may call on-demand after code motion, or we can rerun a non-iterative GVN-lite as a cleanup after lowering passes.

If anyone can think of important dependencies between IR passes, this would be good time to point it out.

We could probably make a minor adjustment to the opt driver so that the user can specify any mix of canonical and lowering passes. The first lowering pass and subsequent passes would run in the lowering function pass manager.

[llvmbot]

SystemZ testcase that benefits from earlier GVN
Following Andrew's suggestion, here's a test that produces inferior
code because GVN is run after the loop optimisations.

It is the equivalent of:

void
f (unsigned short *x, int *l)
{
int i;
for (i = 0; i < *l; i++)
if (x[i])
x[i]++;
}

The loop ought to be converted into decrement-and-branch form, just like:

void
f (unsigned short *x, int *l)
{
int c = *l;
int i;
for (i = 0; i < c; i++)
if (x[i])
x[i]++;
}

already is. The reason for the different treatment of the two loops
is that LoopStrengthReduce relies on IndVarSimplify to convert loop
exit conditions into a canonical != form:

// Equality (== and !=) ICmps are special. We can rewrite (i == N) as
// (N - i == 0), and this allows (N - i) to be the expression that we work
// with rather than just N or i, so we can consider the register
// requirements for both N and i at the same time. Limiting this code to
// equality icmps is not a problem because all interesting loops use
// equality icmps, thanks to IndVarSimplify.
if (ICmpInst *CI = dyn_cast<ICmpInst>(LF.UserInst))
  if (CI->isEquality()) {

However, the testcase still has two loads of *l by the time IndVarSimplify
is run; one for the precondition of the rotated loop and one for the loop
exit. This means that IndVarSimplify can't tell that the precondition
(skip the loop if *l <= 0) is operating on the same *l as the loop exit,
and therefore can't work out that *l is the trip count. The two "*l"s
are only fused by GVN, which runs after IndVarSimplify.

Moving GVN before IndVarSimplify gives me the code I was expecting.
See also the thread starting at:

http://lists.cs.uiuc.edu/pipermail/llvmdev/2013-October/067076.html

with comments from Andrew:

http://lists.cs.uiuc.edu/pipermail/llvmdev/2013-November/067233.html