llvm dev - Jul 2006 - [LLVMdev] Critical edges

Dear guys,

    I've adapted the pass in BreakCriticalEdges.cpp so I can use it
before register allocation. But the pass is not changing the control
flow graph of the machine function. I think it is because I am inserting
the pass after the control flow graph of the machine function is built.
I am inserting the pass as required by the register allocator, and I
can see that the pass is splitting critical edges. Question is: where
do I insert this pass so its modifications reflects in the control
flow graph of the machine function? The code of the pass is the code
of BreakCriticalEdges.cpp, and it is a runOnFunction pass, not a
runOnMachineFunction.

Thank you very much,

Fernando

Hi,

    I am able to remove the critical edges now. I only had to insert the
line below in PPCTargetmachine.cpp.

  PM.add(createBreakCriticalEdgesPass());

However, it does not remove all the critical edges. I am getting a very
weird dataflow graph (even without the Break Critical edges pass). The
dataflow generated by MachineFunction::dump() for the program below is
given here:
http://compilers.cs.ucla.edu/fernando/projects/soc/images/loop_no_crit2.pdf

int main(int argc, char **argv) {
    int result = 0;
    int counter = argc;
    while(counter > 0) {
        if(counter % 3 == 0) {
            result--;
        } else {
            result++;
        }
        counter = counter - 1;
    }
    printf("Result = %d\n", result);
}

The problem is the no_exit block. I think it was changed by one of the
optimization passes, and was split into three basic blocks. But now there
is a phi function where both the parameters are defined in the same basic
block. Any of you guys now which pass I should cut off if I want to avoid
this optimization?

Thanks,

Fernando

>    I've adapted the pass in BreakCriticalEdges.cpp so I can use it
> before register allocation. But the pass is not changing the control
BreakCriticalEdges modifies the CFG of the LLVM IR, so you'd have to run 
it before any machine code is generated: i.e. before instruction 
selection.

-Chris
> flow graph of the machine function. I think it is because I am inserting
> the pass after the control flow graph of the machine function is built.
> I am inserting the pass as required by the register allocator, and I
> can see that the pass is splitting critical edges. Question is: where
> do I insert this pass so its modifications reflects in the control
> flow graph of the machine function? The code of the pass is the code
> of BreakCriticalEdges.cpp, and it is a runOnFunction pass, not a
> runOnMachineFunction.
>
> Thank you very much,
>
> Fernando
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>
-Chris

-- 
http://nondot.org/sabre/
http://llvm.org/

On Tue, 4 Jul 2006, Fernando Magno Quintao Pereira
wrote:
> However, it does not remove all the critical edges. I am getting a very
> weird dataflow graph (even without the Break Critical edges pass). The
> dataflow generated by MachineFunction::dump() for the program below is
> given here:
> http://compilers.cs.ucla.edu/fernando/projects/soc/images/loop_no_crit2.pdf
...
> The problem is the no_exit block. I think it was changed by one of the
> optimization passes, and was split into three basic blocks. But now there
> is a phi function where both the parameters are defined in the same basic
> block. Any of you guys now which pass I should cut off if I want to avoid
> this optimization?
This is due to instruction selection.  The llvm code turns your testcase 
into something like this:

   X += cond ? 1 : -1;

This is a 'select' instruction in LLVM.

Generic PowerPC chips doesn't support integer select instructions, so it 
must be lowered to a conditional branch.  This lowering is what you're 
seeing, there is no way to disable it.

If you don't want critical edges in the machine code CFG, you're going
to
have to write a machine code CFG critical edge splitting pass: LLVM 
doesn't currently have one.

-Chris

-- 
http://nondot.org/sabre/
http://llvm.org/