Rematerialization and spilling

I'm working on an out-of-tree target and am having some problems with rematerialization and spilling.

The target's load and store instructions affect the condition code register (CCR). Describing this in the InstrInfo.td file using Defs = [CCR] certainly prevents spills and fills from being inserted where they might clobber CCR but it also prevents the load instruction from being rematerialized because it defines a physical register (TargetInstrInfo::isReallyTriviallyReMaterializableGeneric()).

I've tried to take the approach that's used by the X86 target, in which instructions _are_ trivially rematerializable even if they implicitly define the condition code (EFLAGS) but must take care not to clobber EFLAGS if it's live at the point where the instruction is rematerialized. However, because my original load instruction implicitly defines CCR, and this isn't marked as dead, the instruction can't be deleted so the destination register is spilled anyway.

I thought maybe I should pretend that load and store don't implicitly define CCR but then I'd need to prevent spill / fill when CCR is live, e.g. between compare instructions and conditional branch instructions. Would machine instruction bundles be the right way to do this?

I'd be grateful for any advice.

Hi Steve,

LLVM’s register allocators assume that spills, fills, and copies can be safely inserted anywhere (except after terminator instructions). The register allocators simply can’t work without that assumption.

As far as I know, your only option is to make sure that CCR is never live anywhere. This means that you need to create pseudo-instructions that bundle cmp+jump so the register allocator will never attempt to insert spill code between them.

/jakob

Hi Jakob,

thanks for the advice. I'll do as you suggest and make sure that CCR is never live.

I can use pseudo-instructions to bundle cmp+jump but it's not ideal because I might also have to bundle cmp+jump+jump+... into a pseudo. Also, there are several flavours of cmp instruction so I might need a lot of pseudos.

That's what led me to wonder whether MachineInstrBundles might be a neater solution but I wasn't sure whether they were really intended, or suitable, for this purpose.

Steve

That might be possible, at least the register allocator understands bundles.

Passes before register allocation are not bundle aware, including the MI scheduler. You may be able to form the bundles with some kind of MI scheduler plug-in.

/jakob

That may not be necessary. The register allocator won’t insert anything between terminators.

/jakob

Great. Using pseudos sounds like it fill be feasible then.

Thanks

Steve

The MI scheduler pass is the place to do the bundling. Exposing bundles to earlier passes could be tricky.

If you’re not actually using MI, you can define your own pass instead and substitute it using TargetPassConfig::substititePass.

You can keep LiveIntervals up-to-date to avoid recomputing them. If you’re just moving instructions around, and no vregs will be live into the middle of a bundle (e.g only bundling cmp+jmp), then LIS->handleMove() should hopefully fix it. If you ever bundle something with live vregs into the middle of a bundle, you probably need handeMoveIntoBundle(). I’ve been wanting a better API for this, but it’s hard to develop without many in-tree users.

For those who want to reuse parts of the existing MachineScheduler, there are many places to plug in. MachineSchedRegistry provides the hook. At that point you can define your own ScheduleDAGInstrs or ScheduleDAGMI subclass. People who only want to define new heuristics should reuse ScheduleDAGMI directly and only define their own MachineSchedStrategy. It may be possible to bundle within MachineSchedStrategy::schedNode, but it would be easy to mess up ScheduleDAGMI’s iterators in the process.

-Andy