Question about /llvm/trunk/lib/CodeGen/MachineScheduler.cpp

...this is moving from llvm-commits to llvm-dev.

1) Can a BB presented to the MI scheduler be _not_ terminated (end on a non
terminator MI) under any circumstances? Below you are speaking about "Empty
blocks, or blocks with only a single instruction that not a terminator..." -
What about the BB#4 below? Is it OK?

I don't *think* any MI pass should require terminators for single successor blocks laid out sequentially. It seems obvious to me that a block with multiple successors needs a terminator, but I don't know exactly where that's verified. On the other hand, prior to code placement, I often see unnecessary unconditional jumps. So I'm not sure what is considered best practice. Hopefully someone else on the list will clarify.

Either way it is definitely not an assumption made by the scheduler. In my previous message, I was pointing out corner cases present in the MachineScheduler::runOnMachineFunction loop--they all have to do with terminators or lack thereof.

It is interesting to note that a VLIW target will want to do block placement before final bundling. That's not something I plan to fix short term. I think you can deal with it in your target's pass config and let me know if we need to fix some assumptions in common code.

2) If above is true, can SUnit node in SchedDAG (constructed by
ScheduleDAGInstrs::BuildSchedGraph) be "dangling" - not having successors
(and/or predecessor)? (see example below).

Yes. The DAG can have multiple roots/leaves. We have special Entry/ExitSU that partially model latency of data flow across blocks and into call arguments, but they really only exist as a heuristic.

The reason I keep on asking this - both back ends we support (Hexagon and
ARM) are happily optimizing out fall-through branches away by the time BB
gets to the machine scheduler, resulting in a fragmented DAG... If your
intent is to handle that during actual scheduling - fine, but if any of the
above assumptions is false, please clarify.

That sounds like an ok assumption to me.

I also could add here that it seems that the
ScheduleDAGSDNodes::BuildSchedGraph has no difficulties dealing with a
similar situation.

The MachineScheduler only operates on the instructions that are mapped to SUnits produces by BuildSchedGraph. So if BuildSchedGraph can handle it so can the scheduler.

Here is the only issue I'm aware of...

Terminators are not included in the scheduler DAG, but a VLIW target will likely want to expose them to the bundler. One way to handle this would be to split the bundler into a separate pass. I don't actually think that makes sense. Firstly, it doesn't so much solve the problem as move it to another place. More importantly, the MachineScheduler pass should be flexible enough such we can integrate any target-specific transforms that want to make use of the preRA DAG. Think of MachineScheduler as some target-specific set of preRA DAG clients.

My solution for this is to allow the bundler to operate at a wider scope than the DAG. In other words, we can maintain bundler state across scheduling barriers. In the long-term, we want DAGs to span terminators under certain conditions, but it's still useful to be able to throw in scheduling barriers at times without breaking the bundler.

In the next few days I'll fixup the interface to allow that, and move things into a header so you can start checking in a Hexagon MachineScheduler pass if you want.

-Andy

1) Can a BB presented to the MI scheduler be _not_ terminated (end on a non
terminator MI) under any circumstances? Below you are speaking about "Empty
blocks, or blocks with only a single instruction that not a terminator..." -
What about the BB#4 below? Is it OK?

I don't *think* any MI pass should require terminators for single successor blocks laid out sequentially.

Right.

It seems obvious to me that a block with multiple successors needs a terminator, but I don't know exactly where that's verified.

It's not. In fact, a block can have a landing pad and a fall-through successor, and still not have a terminator. (Invokes ought to be terminators, but they currently aren't).

On the other hand, prior to code placement, I often see unnecessary unconditional jumps. So I'm not sure what is considered best practice. Hopefully someone else on the list will clarify.

Most targets try to keep branches minimal at all times, I think. It doesn't always work, so sometimes CodePlacementOpt has to clean it up.

/jakob