[LLVMdev] [Polly] Move Polly's execution later

[Tobias Grosser]

On 09/25/2013 04:55 AM, Star Tan wrote:
> Here is an update about moving Polly later.

Hi star tan,

thanks for your report.


>
> 1. Why does Polly generate incorrect code when we move Polly immediately after the loop rotating pass?
>
> It is mainly caused by a wrong polly merge block. When Polly detects a valid loop for Polyhedral transformations, it usually introduces a new basic block "polly.merge_new_and_old" after the original loop exit block. This new basic block contains a branch instruction that decides whether to exit or re-enter the loop like this:
>
> polly.loop_exit28:                                ; preds = %polly.stmt.for.body.i, %polly.loop_if25
>    br label %polly.merge_new_and_old
> polly.merge_new_and_old:                          ; preds = %polly.loop_exit28, %for.body.i
>    ...
>    %cmp = icmp slt i32 %2, 0
>    ...
>    br i1 %cmp, label %for.body, label %for.end12
> for.end12:                                        ; preds = %loop.exit
>    ...
>    ret i32 0
>
> Unfortunately, the new basic block "polly.merge_new_and_old" is marked as unreachable after a serial of immediate Loop optimizations in the following pass order:
>            Polly - Create LLVM-IR from SCoPs
>          Loop Pass Manager
>            Canonicalize natural loops
>            Loop-Closed SSA Form Pass
>            Rotate Loops
>            Loop Invariant Code Motion
>            Loop-Closed SSA Form Pass
>            Unswitch loops
>          Combine redundant instructions
>
> After those loop optimition passes, the "Combine redundant instructions" would treat the basic block "merge_new_and_old" unreachable and transfer the block "polly.loop_exit28" into an infinity loop:
> polly.loop_exit28:                                ; preds = %polly.stmt.for.body.i, %polly.loop_if25
>    br label polly.loop_exit28
>
> Actually, I have no idea why this happens, but experiments show that this problem can be addressed by adding a pass "MPM.add(createCFGSimplificationPass())" after Polly. It seems it is necessary to run this pass after Polly code generation.

Any pass order should yield correct code. If this is not the case there 
is either a bug in Polly or we expose a bug in LLVM. We should track 
this down.

Our path ordering decisions should not be driven by us trying to avoid 
triggering this bug.

As you already created a bug report, we should work on fixing it.
The next step would be to reduce the set of passes involved. You can do 
this by calling -debug-pass=Arguments


> 2. Where should we  move Polly to?
>
> There are many choices to move Polly later. Tobias suggests to move it immediately after the loop rotate pass (the first loop optimization pass), but unfortunately Polly would generate incorrect code in that case (http://llvm.org/bugs/show_bug.cgi?id=17323).
>
> By investigating those Polly canonicalization passes (polly/lib/RegisterPasses.cpp):
>      PM.add(llvm::createPromoteMemoryToRegisterPass());
>      PM.add(llvm::createInstructionCombiningPass());
>      PM.add(llvm::createCFGSimplificationPass());
>      PM.add(llvm::createTailCallEliminationPass());
>      PM.add(llvm::createCFGSimplificationPass());
>      PM.add(llvm::createReassociatePass());
>      PM.add(llvm::createLoopRotatePass());
>      PM.add(llvm::createInstructionCombiningPass());
>
> We can see that some of them are also called in common cases (lib/Transforms/IPO/PassManagerBuilder.cpp:181):
>
>    MPM.add(createEarlyCSEPass());
>    MPM.add(createJumpThreadingPass());
>    MPM.add(createCorrelatedValuePropagationPass());
>    MPM.add(createCFGSimplificationPass());     // also called in Polly
>    MPM.add(createInstructionCombiningPass());  // also called in Polly
>    MPM.add(createTailCallEliminationPass());   // also called in Polly
>    MPM.add(createCFGSimplificationPass());     // also called in Polly
>    MPM.add(createReassociatePass());           // also called in Polly
>    MPM.add(createLoopRotatePass());            // also called in Polly
>    MPM.add(createLICMPass());
>    MPM.add(createLoopUnswitchPass(SizeLevel || OptLevel < 3));
>
> The initial idea is to move Polly immediately after LoopRotatePass, which will maximum the reuse of canonicalization passes and we need only keep one canonicalization pass "createPromoteMemoryToRegisterPass" in Polly. Unfortunately, it would lead to errors as shown in previous analysis (see bug http://llvm.org/bugs/show_bug.cgi?id=17323). We need to run "createCFGSimplificationPass" to ensure the correct code.

In fact, I propose to move it _before_ the LoopRotate Pass. I think that 
is also what you tried, no?

> The second possible solution is to move Polly immediately before "createCFGSimplificationPass", and then remove all Polly canonicalization passes except the "createTailCallEliminationPass" and "createCFGSimplificationPass"! Unfortunately, it would still trigger an assert error when compiling some benchmarks in LLVM test-suite (see http://llvm.org/bugs/show_bug.cgi?id=17351).

I think this is too early, as most of the canonicalization is not yet 
done. We probably don't need to investigate this bug immediately, but
it would be nice if we could make it reproducible without your changes 
to polly. For this please run the command with -debug-pass=Arguments
and replace the -O3 with the actual set of commands that is needed to 
trigger the bug. If you can reduce the set of commands using bugpoint, 
that would be even better.

> Similarly I also investigated other points to move Polly, such as before "MPM.add(createTailCallEliminationPass())" or before "MPM.add(createCorrelatedValuePropagationPass())", but all these cases would trigger some unexpected compile error or execution error. I think we need more efforts to investigate why Polly cannot be placed in these points.

This is unfortunate. I wonder if they all have the same root cause.

In any case, I would focus on moving Polly _before_ the loop rotate pass 
and would start with fixing the blocking bug.

Tobias