llvm dev - Jun 2016 - Why not do machine instruction scheduling in SSA form?

Hi LLVM community,

Currently LLVM backend do pre-RA machine instruction scheduling in non-SSA form,
I doubt why not do machine scheduling in SSA machine instruction form? Now
LLVM’s machine scheduling uses a list-scheduling algorithm, but if we wang to
support more complex scheduling algorithms, for example, modulo scheduling for
loops, it seems more easy to accomplish this in SSA form as SSA is more suitable
for tracking dependencies and doing code motion.

I find that LiveIntervals analysis pass, which is required by RegPressureTracker
and MachineScheduler, cannot run before phi elimination. Is this one of the
reason that machine scheduling is not done in SSA form?

Any explanation is appreciated. Thanks a lot!



Cheers,
Xing

A motivation for scheduling later is that the program representation is closer
to the final instruction stream which makes the machine simulation more
accurate. If you schedule too early you do not see the instructions produced by
phi elimination and the two address fixup pass.

LiveIntervals should work on MachineSSA form. If it doesn't you should file
a bugzilla ticket with more details.

- Matthias
> On Jun 27, 2016, at 4:39 AM, Xing Su via llvm-dev <llvm-dev at
lists.llvm.org> wrote:
> 
> Hi LLVM community,
> 
> Currently LLVM backend do pre-RA machine instruction scheduling in non-SSA
form, I doubt why not do machine scheduling in SSA machine instruction form? Now
LLVM’s machine scheduling uses a list-scheduling algorithm, but if we wang to
support more complex scheduling algorithms, for example, modulo scheduling for
loops, it seems more easy to accomplish this in SSA form as SSA is more suitable
for tracking dependencies and doing code motion.
> 
> I find that LiveIntervals analysis pass, which is required by
RegPressureTracker and MachineScheduler, cannot run before phi elimination. Is
this one of the reason that machine scheduling is not done in SSA form?
> 
> Any explanation is appreciated. Thanks a lot!
> 
> 
> 
> Cheers,
> Xing
> 
> 
> 
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev

Thank you, Matthias

I tried to run LIS before PHI-elimination and got an assertion failure. I will
post my example later

Cheers,
Xing 
> 在 2016年6月28日，02:59，Matthias Braun <mbraun at apple.com> 写道：
> 
> A motivation for scheduling later is that the program representation is
closer to the final instruction stream which makes the machine simulation more
accurate. If you schedule too early you do not see the instructions produced by
phi elimination and the two address fixup pass.
> 
> LiveIntervals should work on MachineSSA form. If it doesn't you should
file a bugzilla ticket with more details.
> 
> - Matthias
> 
>> On Jun 27, 2016, at 4:39 AM, Xing Su via llvm-dev <llvm-dev at
lists.llvm.org> wrote:
>> 
>> Hi LLVM community,
>> 
>> Currently LLVM backend do pre-RA machine instruction scheduling in
non-SSA form, I doubt why not do machine scheduling in SSA machine instruction
form? Now LLVM’s machine scheduling uses a list-scheduling algorithm, but if we
wang to support more complex scheduling algorithms, for example, modulo
scheduling for loops, it seems more easy to accomplish this in SSA form as SSA
is more suitable for tracking dependencies and doing code motion.
>> 
>> I find that LiveIntervals analysis pass, which is required by
RegPressureTracker and MachineScheduler, cannot run before phi elimination. Is
this one of the reason that machine scheduling is not done in SSA form?
>> 
>> Any explanation is appreciated. Thanks a lot!
>> 
>> 
>> 
>> Cheers,
>> Xing
>> 
>> 
>> 
>> _______________________________________________
>> LLVM Developers mailing list
>> llvm-dev at lists.llvm.org
>> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>

> On Jun 27, 2016, at 4:39 AM, Xing Su via llvm-dev <llvm-dev at
lists.llvm.org> wrote:
> 
> Hi LLVM community,
> 
> Currently LLVM backend do pre-RA machine instruction scheduling in non-SSA
form, I doubt why not do machine scheduling in SSA machine instruction form? Now
LLVM’s machine scheduling uses a list-scheduling algorithm, but if we wang to
support more complex scheduling algorithms, for example, modulo scheduling for
loops, it seems more easy to accomplish this in SSA form as SSA is more suitable
for tracking dependencies and doing code motion.
> 
> I find that LiveIntervals analysis pass, which is required by
RegPressureTracker and MachineScheduler, cannot run before phi elimination. Is
this one of the reason that machine scheduling is not done in SSA form?
> 
> Any explanation is appreciated. Thanks a lot!
> 
> 
> 
> Cheers,
> Xing

I also find it awkward to schedule and register allocate after eliminating SSA
form (it would be possible to coalesce virtual registers while remaining in SSA
form). But in theory LLVM has the information you need. LiveIntervals provides
the reaching defs after MachineOperands have been renamed to coalesced vregs.
The only fundamental complexity is that LiveIntervals needs to be updated during
scheduling.

If I were writing a global code motion or cyclic code motion pass, I would run
it prior to phi elimination for the reasons you mention. For modulo scheduling,
it really depends on whether you want to see the copies and coalesced vregs
during scheduling. The machine model and interesting utilities like
MachineTraceMetrics are available prior to phi elimination. As Matthias said,
LiveIntervals is also available if you really need it, but then you might as
well just schedule after phi elimination, since LiveInterval update is the only
real downside.

-Andy