VLIWPacketizerList: failing to schedule terminators

Hi,

I'm trying to use the VLIWPacketizerList to schedule instructions for
the R600 target, and I'm running into this assertion failure:
ScheduleDAGInstrs.cpp:558: Cannot schedule terminators or labels!

I think I might not be using the VLIWPacketizerList class correctly.
I've attached my code to this email. Can anyone spot what I'm doing
wrong?

Also, I had to add a LiveIntervals * parameter to the constructor of
this class in order to do pre-RA scheduling.

Thanks,
Tom

R600Packetizer.cpp (2.46 KB)

Tom,

  What is in your isSchedulingBoundary? If it contains isLabel you might
need to disable that assert:

assert(!MI->isTerminator() && !MI->isLabel() &&
           "Cannot schedule terminators or labels!");

Sergei Larin

Tom,

  What is in your isSchedulingBoundary? If it contains isLabel you might
need to disable that assert:

assert(!MI->isTerminator() && !MI->isLabel() &&
           "Cannot schedule terminators or labels!");

Sergei Larin

--
Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum.

I haven't implemented it, so it's still the default implementation.
Though, the assertion failure is happening before the main packetizer
loop, so it doesn't look like that function is ever called.

-Tom

Tom,

   I do not have your call stack, but packetizer calls
ScheduleDAGInstrs::buildSchedGraph to create dependency model. If this is
the first time you use the new MI sched infrastructure (like your target has
not implemented misched yet) there might be some work needed to implement
couple target hooks. isSchedulingBoundary is one of them. Also try to
disable that assert and see what happens. It sounds strange, but in some
cases that assert is overly restrictive.

Andy,

  Those are just my guesses, but the issue looks very similar to our first
experience with sched DAG constructor.

Sergei

Tom,

   I do not have your call stack, but packetizer calls
ScheduleDAGInstrs::buildSchedGraph to create dependency model. If this is
the first time you use the new MI sched infrastructure (like your target has
not implemented misched yet) there might be some work needed to implement
couple target hooks. isSchedulingBoundary is one of them. Also try to
disable that assert and see what happens. It sounds strange, but in some
cases that assert is overly restrictive.

Thanks, I disabled that assert, and I got a little farther. I hit
some more assertion failures finalizeBundle, because the
instructions were still using virtual registers. I'm not sure why
finalizeBundle doesn't currently handle virtual registers, maybe the
implementation isn't complete yet?

If I remove those asserts in finalizeBundle, I can get the program
to compile, and it has the VLIW bundles.

-Tom

Hi Tom,

We also ran into the same issue when packetizing for Hexagon. Let me try to
explain the problem:

The scheduler breaks down a basic block into regions (look at
MachineScheduler.cpp) - I believe for efficiency. There is an API
isSchedulingBoundary to check if an instruction is a scheduling boundary or
not. If it is a scheduling boundary, all existing instructions in the region
are scheduled and next region is started.

By default, isSchedulingBoundary returns true for labels and terminator
instructions. Further, there is a check in BuildSchedGraph (I think) that
asserts if it finds labels or terminator. I think that assert should be
changed to use isSchedulingBoundary API.

Another problem for VLIW machines is packetization of terminator instruction
with other instructions. For example, Hexagon allows to packetize
terminators with others if there is no true dependence. In the current
infrastructure, it's not possible to allow terminators to be included in the
region since it will assert in BuildSchedGraph.

I propose the following solution:

1. Change assert in BuildSchedGraph to use isSchedulingBoundary.
2. Change DAG construction so that there is a control edge between every
leaf node to the terminator instruction.
3. VLIW backends, override isSchedulingBoundary to return false for
terminators; 4. The region formation algorithm will select the entire basic
block (if there are no labels) for scheduling including terminators.
5. Control edge will make sure that terminator instruction is not reordered.

Please let me know what you guys think.

Thanks,
Sundeep

From: Das Gupta, Anshu
Sent: Thursday, March 29, 2012 1:46 PM
To: sundeepk@codeauroraforum.org; Kushwaha, Sundeep
Subject: FW: [LLVMdev] VLIWPacketizerList: failing to schedule terminators

From: llvmdev-bounces@cs.uiuc.edu [mailto:llvmdev-bounces@cs.uiuc.edu]
On Behalf Of Tom Stellard
Sent: Thursday, March 29, 2012 11:01 AM
To: Anshuman Dasgupta; Sergei Larin
Cc: llvmdev@cs.uiuc.edu
Subject: [LLVMdev] VLIWPacketizerList: failing to schedule terminators

Hi,

I'm trying to use the VLIWPacketizerList to schedule instructions for the

R600

target, and I'm running into this assertion failure:
ScheduleDAGInstrs.cpp:558: Cannot schedule terminators or labels!

I think I might not be using the VLIWPacketizerList class correctly.
I've attached my code to this email. Can anyone spot what I'm doing

wrong?

Also, I had to add a LiveIntervals * parameter to the constructor of this

class

Tom,

The version of VLIWPacketizerList currently checked in was designed to work for postRA scheduling. I want it to be adapted for use in preRA (called by MachineScheduler), but Sergei and others are still engaged in that process. Since nothing is checked in yet, you'll be running into the same issues as Sergei.

To me, the definition of "isSchedulingBoundary" is "something the DAG builder cannot handle". If you look at MachineScheduler::runOnFunction it jumps through hoops to avoid exposing boundaries to buildSchedGraph(). VLIWPacketizer doesn't have that logic, so it only works if isSchedulingBoundary returns false. Alternatively, you can disable the buildSchedGraph assert and hope for the best--let's just say it's not supported.

The MachineScheduler driver allows for two approaches to bundling:

1) Bundler operates on a larger scope than the scheduler (preferred): isSchedulingBoundary is true for branches, calls, and other strange barriers. Instructions can be reordered between the boundaries during schedule(), and the bundler can operate across regions via exitRegion() and finishBlock(). You will still have DAG edges from the instruction that a branch depends on to the branch (captured by ExitSU), but you won't have any DAG edges crossing the boundary.

2) Scheduler and bundler operate on the same scope (an entire block): isSchedulingBoundary = false and all instructions must be correctly handled by the DAG builder. DAG edges will be built for all instructions within the block.

>> Tom,
>>
>> I do not have your call stack, but packetizer calls
>> ScheduleDAGInstrs::buildSchedGraph to create dependency model. If this is
>> the first time you use the new MI sched infrastructure (like your target has
>> not implemented misched yet) there might be some work needed to implement
>> couple target hooks. isSchedulingBoundary is one of them. Also try to
>> disable that assert and see what happens. It sounds strange, but in some
>> cases that assert is overly restrictive.
>
> Thanks, I disabled that assert, and I got a little farther. I hit
> some more assertion failures finalizeBundle, because the
> instructions were still using virtual registers. I'm not sure why
> finalizeBundle doesn't currently handle virtual registers, maybe the
> implementation isn't complete yet?
>
> If I remove those asserts in finalizeBundle, I can get the program
> to compile, and it has the VLIW bundles.
>
> -Tom
>
>>
>> Andy,
>>
>> Those are just my guesses, but the issue looks very similar to our first
>> experience with sched DAG constructor.
>>
>> Sergei

Tom,

The version of VLIWPacketizerList currently checked in was designed to work for postRA scheduling. I want it to be adapted for use in preRA (called by MachineScheduler), but Sergei and others are still engaged in that process. Since nothing is checked in yet, you'll be running into the same issues as Sergei.

Ok, so I think I'll do a postRA packetizer for now and them come back to my
preRA packetizer once VLIWPacketizerList can handle it.

The reason I wanted to do a preRA packetizer is because in the R600
target, the set of destination registers an instruction can write to
is determined by its spot within the bundle. This means that either
after or during packetization, the backend needs to be able to change
the virtual register of an instruction to the class the corresponds to
its slot in the bundle.

To me, the definition of "isSchedulingBoundary" is "something the DAG builder cannot handle". If you look at MachineScheduler::runOnFunction it jumps through hoops to avoid exposing boundaries to buildSchedGraph(). VLIWPacketizer doesn't have that logic, so it only works if isSchedulingBoundary returns false. Alternatively, you can disable the buildSchedGraph assert and hope for the best--let's just say it's not supported.

The MachineScheduler driver allows for two approaches to bundling:

1) Bundler operates on a larger scope than the scheduler (preferred): isSchedulingBoundary is true for branches, calls, and other strange barriers. Instructions can be reordered between the boundaries during schedule(), and the bundler can operate across regions via exitRegion() and finishBlock(). You will still have DAG edges from the instruction that a branch depends on to the branch (captured by ExitSU), but you won't have any DAG edges crossing the boundary.

2) Scheduler and bundler operate on the same scope (an entire block): isSchedulingBoundary = false and all instructions must be correctly handled by the DAG builder. DAG edges will be built for all instructions within the block.

---
Now, regarding bundle creation. The FinalizeMachineBundles pass will "finalize" bundles for you after regalloc. You can enable that in your target config. e.g.

bool MyTargetPassConfig::addFinalizeRegAlloc() {
    addPass(FinalizeMachineBundlesID);
}

This does not create bundles, rather it wraps bundles in an extra layer of abstraction by copying all of the MachineOperands into a bundle header. I think we have enough other bundle abstractions that this step could be eliminated, but it's a bootstrapping mechanism that we rely on for now during postRA passes only.

VLIWPacketizer calls finalizeBundle explicitly because it's running after regalloc.

We do not want to see any Bundle instructions prior to regalloc. So a preRA scheduler should not call finalizeBundles. It can create bundles simply by setting the isInsideBundle flag on MachineInstrs. If you allow internal register dependencies you would also need to set isInternalRead on those MachineOperands.

Thanks, this information is really helpful. One question, though:
If preRA bundles can't have Bundle instructions, then how does the
register allocator determine the boundaries between bundles?

-Tom

The instruction stream looks like this:

instA
instB
instC
instD

Regalloc will see the bundle (B, C, D) and give all operands within that bundle the same slot index, so it won’t see interferences within the bundle.

See MachineInstr.h and MachineInstrBundle.h. There are helpers that work regardless of the fake “Bundle” instructions: isBundled, getBundleStart, MIBundleOperands…

We’ll surely want to adjust the API as people begin to actively use it.

-Andy