AMDGPU/SI: Add lane tracking to SI Scheduler

[axeldavy]

Summary

This patch adds lane tracking to SI Scheduler.

To handle lanes,
. When a register is always used with all its lanes, it replaces the register with RegisterMaskPair(Reg, LaneBitMask::all())
. In the other cases, it determines a 'basis' of masks such that any register/lane usage can be decomposed into fake registers of RegisterMaskPair(Reg, LaneBitMask element of the basis).

Previously the code assumed that a Register cannot be defined if already defined. LaneMasks break this assumption.
Decomposing into unique RegisterMaskPair "registers" (such that the Lanes don't intersect) enables to reuse the previous assumption.
A RegisterMaskPair can only be defined if not already alive. Thus enables to use the previous code, with some updates to how register usage is computed.

depends on D31123 and D31587

[axeldavy]

I removed the usage of the [] operator for DenseMap<unsigned, RegisterMaskPair> IdentifierToReg.

This doesn't need anymore RegisterMaskPair to have a default constructor with no argument.

[rampitec]

lib/Target/AMDGPU/SIMachineScheduler.cpp

1476

Forgot '&'?

1653

Can you please avoid copy here and in function's arguments?

1728

auto& (and in other places too)?

[axeldavy]

lib/Target/AMDGPU/SIMachineScheduler.cpp

1476

indeed. Thanks.

1653

Right, I can get
SIScheduleBlockScheduler::getPairsForRegs(const SmallVector<RegisterMaskPair, 8> &Regs)
{

SmallVector<RegisterMaskPair, 8> Result;
for (const auto &RegPair : Regs) {

But for the line with:
for (const auto RegPairRes : getPairsForReg(RegPair.RegUnit,

Do you mean just use &RegPairRes ?
Daniel Berlin suggested to use std::transform in combination with a new vector_inserter to replace the two loops.
That wouldn't prevent the fact there is in all cases a copy from getPairsForReg results into the result tab of getPairsForRegs.

I could probably solve the issue by adding a new getPairsForReg function that takes the Result array to append to, and using that helper with the two functions. Do you think that would be a good solution ?

1728

Ok

[rampitec]

lib/Target/AMDGPU/SIMachineScheduler.cpp

1653

Yes, it sounds more efficient to me.

[axeldavy]

Use more references.
Improved efficiency of getPairsForReg.

[rampitec]

lib/Target/AMDGPU/SIMachineScheduler.cpp

1635

ToAppend is passed by value... As far as I understand it should not work, i.e. it should not return any values.

1664

Argument needs to be reference.

[axeldavy]

Fix getPairsForRegs.

[axeldavy]

Use reference for the input argument of getPairsForRegs.

[rampitec]

In D31124#707998, @axeldavy wrote:

Use reference for the input argument of getPairsForRegs.

Thank you. It looks good, but w/o reference previous version should not been working. I.e. it looks like this code is not covered by any test.
I think you need to add tests for this.

[axeldavy]

Si scheduler has a test file: test/CodeGen/AMDGPU/si-scheduler.ll

But perhaps you meant a test with subreg ?
I'm afraid it's hard to design a test for subregs specifically, since if the ops using subregs are inside the same blocks, the blocks inputs and outputs won't have subregs. And block creation algorithms can vary.

[rampitec]

In D31124#708105, @axeldavy wrote:

Si scheduler has a test file: test/CodeGen/AMDGPU/si-scheduler.ll

But perhaps you meant a test with subreg ?
I'm afraid it's hard to design a test for subregs specifically, since if the ops using subregs are inside the same blocks, the blocks inputs and outputs won't have subregs. And block creation algorithms can vary.

You can create a MIR test. For example schedule-regpressure.mir runs only machine scheduler.

[axeldavy]

Check shouldTrackLaneMask when building the list of the Block outputs.
When not set, force the LaneMask to be full. Because of findDefsBetween, if can end up partial.
Fixes assertion fault on some shaders.

[axeldavy]

In D31124#708110, @rampitec wrote:

In D31124#708105, @axeldavy wrote:

Si scheduler has a test file: test/CodeGen/AMDGPU/si-scheduler.ll

But perhaps you meant a test with subreg ?
I'm afraid it's hard to design a test for subregs specifically, since if the ops using subregs are inside the same blocks, the blocks inputs and outputs won't have subregs. And block creation algorithms can vary.

You can create a MIR test. For example schedule-regpressure.mir runs only machine scheduler.

That doesn't entirely fix the mentionned problem.
Sisched works by regroupping instructions into Blocks, and scheduling the Blocks between them.
For the test to really check subregs, we'd have to make sure some blocks have subreg outputs.
One way would be to have the subregs involve high latency instructions, because those are always in separated blocks when there is Data dependency.
That is complicated though, I'd have to really investigate how to write tests.

[axeldavy]

Switched the order of the patch with https://reviews.llvm.org/D30147

[vpykhtin]

Why SIScheduleBlockCreator::scheduleInsideBlocks() actually move instructions? Why it isn't done on the final scheduling?

lib/Target/AMDGPU/SIMachineScheduler.cpp

1388

duplicated code

lib/Target/AMDGPU/SIMachineScheduler.h

498

You can make it const and return reference, like

const SmallVector<RegisterMaskPair, 8> &getInRegs() const;

502

Ditto

[vpykhtin]

Ok, I understood SIScheduleBlockCreator::scheduleInsideBlocks() moves instructions to actually get LiveIn and LiveOut set for a block, but this is rather heavy. Have you thought about getting those using DAG directly, not regpressure tracker? By the common sence the dependencies between blocks correspond to that liveness info. There is a problem however: LiveIn and LiveOut dependencies aren't modelled for boundary SUs. I have local patch that build such dependencies - scheduling region LiveIns edges comes from EntrySU, LiveOut - to ExitSU. Another problem - dependency edges doesn't have lanemask, need to think how to deal with this.

lib/Target/AMDGPU/SIMachineScheduler.cpp

387

I would move LIS->getInstructionIndex(*BeginBlock).getRegSlot(), LIS->getInstructionIndex(*EndBlock).getRegSlot() out of the loop

[axeldavy]

In D31124#712336, @vpykhtin wrote:

Ok, I understood SIScheduleBlockCreator::scheduleInsideBlocks() moves instructions to actually get LiveIn and LiveOut set for a block, but this is rather heavy. Have you thought about getting those using DAG directly, not regpressure tracker? By the common sence the dependencies between blocks correspond to that liveness info. There is a problem however: LiveIn and LiveOut dependencies aren't modelled for boundary SUs. I have local patch that build such dependencies - scheduling region LiveIns edges comes from EntrySU, LiveOut - to ExitSU. Another problem - dependency edges doesn't have lanemask, need to think how to deal with this.

This part is the slowest part of the scheduler (handleMove is very innefficient). It's probably a good idea to replace it with a faster system.

[axeldavy]

lib/Target/AMDGPU/SIMachineScheduler.cpp

1388

This is duplicated with your iterative scheduler, and I suggested to have a common function for both schedulers and the default scheduler (you said you extracted the code from there), but you didn't take the comment into account.
Do you want a common function for both SI schedulers or with default scheduler too ?

lib/Target/AMDGPU/SIMachineScheduler.h

498

Right.

I had in mind we'd add the correct computation of the block liveins here (as for GCNScheduler), but for now we can return reference.

[vpykhtin]

lib/Target/AMDGPU/SIMachineScheduler.cpp

1388

Yes, I remember that comment. This doesn't mean this code should be duplicated even more, I encorage you to make short functions whenever possible, even for your own use. This code is actually isn't very efficient and I planned to make efficient version, I should have been noted this, sorry.

[axeldavy]

Updated according to comments.

[rampitec]

lib/Target/AMDGPU/SIMachineScheduler.cpp

1300

According to coding standard, if (...) return;

[vpykhtin]

Axel, thanks for the update.

If you aren't going to add test for this, can you at least run your change on the debug build (or release with asserts) with sisched turned on by default over all AMDGPU lit tests? They mostly would fail on miscompare, but they should run without asserts.

[axeldavy]

In D31124#712850, @vpykhtin wrote:

Axel, thanks for the update.

If you aren't going to add test for this, can you at least run your change on the debug build (or release with asserts) with sisched turned on by default over all AMDGPU lit tests? They mostly would fail on miscompare, but they should run without asserts.

I think it is a good idea to add a test, I think it'd have to be something with a lot of loads and involving a lot of subregs. I just hadn't time yet to write it.

[vpykhtin]

lib/Target/AMDGPU/SIMachineScheduler.cpp

1870

SmallPtrSet is designed for pointer types but used for unsigned type, gcc complains, try consider SmallDenseSet.

[vpykhtin]

I ran lit tests with sished with ShouldTrackLaneMasks=true enabled by default with this patch, the following tests asserted:

******************** TEST 'LLVM :: CodeGen/AMDGPU/fceil64.ll' FAILED ********************
llc: /srv/vpykhtin/git/llvm/lib/CodeGen/RegisterPressure.cpp:74: void decreaseSetPressure(std::vector<unsigned int>&, const llvm::MachineRegisterInfo&, unsigned int, llvm::LaneBitmask, llvm::LaneBitmask): Assertion `CurrSetPressure[*PSetI] >= Weight && "register pressure underflow"' failed.
******************** TEST 'LLVM :: CodeGen/AMDGPU/fp_to_sint.f64.ll' FAILED ********************
llc: /srv/vpykhtin/git/llvm/lib/CodeGen/RegisterPressure.cpp:74: void decreaseSetPressure(std::vector<unsigned int>&, const llvm::MachineRegisterInfo&, unsigned int, llvm::LaneBitmask, llvm::LaneBitmask): Assertion `CurrSetPressure[*PSetI] >= Weight && "register pressure underflow"' failed.
******************** TEST 'LLVM :: CodeGen/AMDGPU/fp_to_uint.f64.ll' FAILED ********************
llc: /srv/vpykhtin/git/llvm/lib/CodeGen/RegisterPressure.cpp:74: void decreaseSetPressure(std::vector<unsigned int>&, const llvm::MachineRegisterInfo&, unsigned int, llvm::LaneBitmask, llvm::LaneBitmask): Assertion `CurrSetPressure[*PSetI] >= Weight && "register pressure underflow"' failed.
******************** TEST 'LLVM :: CodeGen/AMDGPU/srem.ll' FAILED ********************
llc: /srv/vpykhtin/git/llvm/lib/CodeGen/RegisterPressure.cpp:74: void decreaseSetPressure(std::vector<unsigned int>&, const llvm::MachineRegisterInfo&, unsigned int, llvm::LaneBitmask, llvm::LaneBitmask): Assertion `CurrSetPressure[*PSetI] >= Weight && "register pressure underflow"' failed.
******************** TEST 'LLVM :: CodeGen/AMDGPU/urem.ll' FAILED ********************
llc: /srv/vpykhtin/git/llvm/lib/CodeGen/RegisterPressure.cpp:74: void decreaseSetPressure(std::vector<unsigned int>&, const llvm::MachineRegisterInfo&, unsigned int, llvm::LaneBitmask, llvm::LaneBitmask): Assertion `CurrSetPressure[*PSetI] >= Weight && "register pressure underflow"' failed.

I enabled sisched by commenting out the following line:

ScheduleDAGInstrs *GCNPassConfig::createMachineScheduler(
  MachineSchedContext *C) const {
  const SISubtarget &ST = C->MF->getSubtarget<SISubtarget>();
  //if (ST.enableSIScheduler())
    return createSIMachineScheduler(C);
  return createGCNMaxOccupancyMachineScheduler(C);
}

[axeldavy]

This would indicate that handleMove + adjustLaneLiveness is insufficient. Do you have any ideas about what is missing ?

In D31124#715170, @vpykhtin wrote:

I ran lit tests with sished with ShouldTrackLaneMasks=true enabled by default with this patch, the following tests asserted:

******************** TEST 'LLVM :: CodeGen/AMDGPU/fceil64.ll' FAILED ********************
llc: /srv/vpykhtin/git/llvm/lib/CodeGen/RegisterPressure.cpp:74: void decreaseSetPressure(std::vector<unsigned int>&, const llvm::MachineRegisterInfo&, unsigned int, llvm::LaneBitmask, llvm::LaneBitmask): Assertion `CurrSetPressure[*PSetI] >= Weight && "register pressure underflow"' failed.
******************** TEST 'LLVM :: CodeGen/AMDGPU/fp_to_sint.f64.ll' FAILED ********************
llc: /srv/vpykhtin/git/llvm/lib/CodeGen/RegisterPressure.cpp:74: void decreaseSetPressure(std::vector<unsigned int>&, const llvm::MachineRegisterInfo&, unsigned int, llvm::LaneBitmask, llvm::LaneBitmask): Assertion `CurrSetPressure[*PSetI] >= Weight && "register pressure underflow"' failed.
******************** TEST 'LLVM :: CodeGen/AMDGPU/fp_to_uint.f64.ll' FAILED ********************
llc: /srv/vpykhtin/git/llvm/lib/CodeGen/RegisterPressure.cpp:74: void decreaseSetPressure(std::vector<unsigned int>&, const llvm::MachineRegisterInfo&, unsigned int, llvm::LaneBitmask, llvm::LaneBitmask): Assertion `CurrSetPressure[*PSetI] >= Weight && "register pressure underflow"' failed.
******************** TEST 'LLVM :: CodeGen/AMDGPU/srem.ll' FAILED ********************
llc: /srv/vpykhtin/git/llvm/lib/CodeGen/RegisterPressure.cpp:74: void decreaseSetPressure(std::vector<unsigned int>&, const llvm::MachineRegisterInfo&, unsigned int, llvm::LaneBitmask, llvm::LaneBitmask): Assertion `CurrSetPressure[*PSetI] >= Weight && "register pressure underflow"' failed.
******************** TEST 'LLVM :: CodeGen/AMDGPU/urem.ll' FAILED ********************
llc: /srv/vpykhtin/git/llvm/lib/CodeGen/RegisterPressure.cpp:74: void decreaseSetPressure(std::vector<unsigned int>&, const llvm::MachineRegisterInfo&, unsigned int, llvm::LaneBitmask, llvm::LaneBitmask): Assertion `CurrSetPressure[*PSetI] >= Weight && "register pressure underflow"' failed.

I enabled sisched by commenting out the following line:

ScheduleDAGInstrs *GCNPassConfig::createMachineScheduler(
  MachineSchedContext *C) const {
  const SISubtarget &ST = C->MF->getSubtarget<SISubtarget>();
  //if (ST.enableSIScheduler())
    return createSIMachineScheduler(C);
  return createGCNMaxOccupancyMachineScheduler(C);
}

[vpykhtin]

I didn't debugged it and I don't know why you decided so.

In D31124#715389, @axeldavy wrote:

This would indicate that handleMove + adjustLaneLiveness is insufficient. Do you have any ideas about what is missing ?

[axeldavy]

The assert you have is in CodeGen/RegisterPressure.cpp: void decreaseSetPressure

This call can be from only three locations:
. in SIScheduleBlock::initRegPressure, when we initialize block liveins and liveouts for a given Block.
. In SIScheduleBlock::schedule, when we compute the register usage inside a block with the scheduled order inside the Block.
. outside sisched

If outside sisched, it means we have given an invalid schedule.
For the first two cases, it likely means we have done something wrong when changing the order of the SUs, and thus that handleMove and adjustLaneLiveness wouldn't be enough.

In D31124#715398, @vpykhtin wrote:

I didn't debugged it and I don't know why you decided so.

In D31124#715389, @axeldavy wrote:

This would indicate that handleMove + adjustLaneLiveness is insufficient. Do you have any ideas about what is missing ?

[vpykhtin]

Stack trace:

llc: /srv/vpykhtin/git/llvm/lib/CodeGen/RegisterPressure.cpp:74: void decreaseSetPressure(std::vector<unsigned int>&, const llvm::MachineRegisterInfo&, unsigned int, llvm::LaneBitmask, llvm::LaneBitmask): Assertion `CurrSetPre
ssure[*PSetI] >= Weight && "register pressure underflow"' failed.
#0 0x00000000030175bb llvm::sys::PrintStackTrace(llvm::raw_ostream&) /srv/vpykhtin/git/llvm/lib/Support/Unix/Signals.inc:398:0
#1 0x000000000301764c PrintStackTraceSignalHandler(void*) /srv/vpykhtin/git/llvm/lib/Support/Unix/Signals.inc:462:0
#2 0x0000000003015aac llvm::sys::RunSignalHandlers() /srv/vpykhtin/git/llvm/lib/Support/Signals.cpp:44:0
#3 0x0000000003016f53 SignalHandler(int) /srv/vpykhtin/git/llvm/lib/Support/Unix/Signals.inc:252:0
#4 0x00002af5bbdcc330 __restore_rt (/lib/x86_64-linux-gnu/libpthread.so.0+0x10330)
#5 0x00002af5bce85c37 gsignal /build/eglibc-oGUzwX/eglibc-2.19/signal/../nptl/sysdeps/unix/sysv/linux/raise.c:56:0
#6 0x00002af5bce89028 abort /build/eglibc-oGUzwX/eglibc-2.19/stdlib/abort.c:91:0
#7 0x00002af5bce7ebf6 __assert_fail_base /build/eglibc-oGUzwX/eglibc-2.19/assert/assert.c:92:0
#8 0x00002af5bce7eca2 (/lib/x86_64-linux-gnu/libc.so.6+0x2fca2)
#9 0x000000000270061f decreaseSetPressure(std::vector<unsigned int, std::allocator<unsigned int> >&, llvm::MachineRegisterInfo const&, unsigned int, llvm::LaneBitmask, llvm::LaneBitmask) /srv/vpykhtin/git/llvm/lib/CodeGen/RegisterPressure.cpp:75:0
#10 0x0000000002700d9b llvm::RegPressureTracker::decreaseRegPressure(unsigned int, llvm::LaneBitmask, llvm::LaneBitmask) /srv/vpykhtin/git/llvm/lib/CodeGen/RegisterPressure.cpp:158:0
#11 0x0000000002703e14 llvm::RegPressureTracker::advance(llvm::RegisterOperands const&) /srv/vpykhtin/git/llvm/lib/CodeGen/RegisterPressure.cpp:892:0
#12 0x0000000002704053 llvm::RegPressureTracker::advance() /srv/vpykhtin/git/llvm/lib/CodeGen/RegisterPressure.cpp:933:0
#13 0x0000000001561341 llvm::SIScheduleBlock::initRegPressure(llvm::MachineInstrBundleIterator<llvm::MachineInstr, false>, llvm::MachineInstrBundleIterator<llvm::MachineInstr, false>) /srv/vpykhtin/git/llvm/lib/Target/AMDGPU/SIMachineScheduler.cpp:338:0
#14 0x0000000001561756 llvm::SIScheduleBlock::schedule(llvm::MachineInstrBundleIterator<llvm::MachineInstr, false>, llvm::MachineInstrBundleIterator<llvm::MachineInstr, false>) /srv/vpykhtin/git/llvm/lib/Target/AMDGPU/SIMachineScheduler.cpp:415:0
#15 0x000000000156726e llvm::SIScheduleBlockCreator::scheduleInsideBlocks() /srv/vpykhtin/git/llvm/lib/Target/AMDGPU/SIMachineScheduler.cpp:1375:0
#16 0x0000000001562d74 llvm::SIScheduleBlockCreator::getBlocks(llvm::SISchedulerBlockCreatorVariant) /srv/vpykhtin/git/llvm/lib/Target/AMDGPU/SIMachineScheduler.cpp:661:0
#17 0x000000000156a92d llvm::SIScheduler::scheduleVariant(llvm::SISchedulerBlockCreatorVariant, llvm::SISchedulerBlockSchedulerVariant) /srv/vpykhtin/git/llvm/lib/Target/AMDGPU/SIMachineScheduler.cpp:1929:0
#18 0x000000000156bb10 llvm::SIScheduleDAGMI::schedule() /srv/vpykhtin/git/llvm/lib/Target/AMDGPU/SIMachineScheduler.cpp:2120:0
#19 0x0000000002648b0d (anonymous namespace)::MachineSchedulerBase::scheduleRegions(llvm::ScheduleDAGInstrs&, bool) /srv/vpykhtin/git/llvm/lib/CodeGen/MachineScheduler.cpp:524:0
#20 0x0000000002647f56 (anonymous namespace)::MachineScheduler::runOnMachineFunction(llvm::MachineFunction&) /srv/vpykhtin/git/llvm/lib/CodeGen/MachineScheduler.cpp:387:0
#21 0x00000000025bdc15 llvm::MachineFunctionPass::runOnFunction(llvm::Function&) /srv/vpykhtin/git/llvm/lib/CodeGen/MachineFunctionPass.cpp:62:0
#22 0x000000000297d26c llvm::FPPassManager::runOnFunction(llvm::Function&) /srv/vpykhtin/git/llvm/lib/IR/LegacyPassManager.cpp:1513:0
#23 0x000000000297d3ff llvm::FPPassManager::runOnModule(llvm::Module&) /srv/vpykhtin/git/llvm/lib/IR/LegacyPassManager.cpp:1534:0
#24 0x000000000297d79a (anonymous namespace)::MPPassManager::runOnModule(llvm::Module&) /srv/vpykhtin/git/llvm/lib/IR/LegacyPassManager.cpp:1590:0
#25 0x000000000297deea llvm::legacy::PassManagerImpl::run(llvm::Module&) /srv/vpykhtin/git/llvm/lib/IR/LegacyPassManager.cpp:1693:0
#26 0x000000000297e12b llvm::legacy::PassManager::run(llvm::Module&) /srv/vpykhtin/git/llvm/lib/IR/LegacyPassManager.cpp:1725:0
#27 0x0000000001243107 compileModule(char**, llvm::LLVMContext&) /srv/vpykhtin/git/llvm/tools/llc/llc.cpp:579:0
#28 0x0000000001241788 main /srv/vpykhtin/git/llvm/tools/llc/llc.cpp:331:0
#29 0x00002af5bce70f45 __libc_start_main /build/eglibc-oGUzwX/eglibc-2.19/csu/libc-start.c:321:0
#30 0x000000000123f799 _start (/srv/vpykhtin/git/debug.llvm/./bin/llc+0x123f799)
Stack dump:
0.      Program arguments: /srv/vpykhtin/git/debug.llvm/./bin/llc -march=amdgcn -verify-machineinstrs
1.      Running pass 'Function Pass Manager' on module '<stdin>'.
2.      Running pass 'Machine Instruction Scheduler' on function '@fceil_v4f64'

[vpykhtin]

In general, I think moving instructions just to use standard RP tracker to discover liveins/liveouts isn't a good idea. It isn't only slow but doesn't look reliable too. Why not discover these sets using DAG directly?

[axeldavy]

Could you describe how you would get all the relevant information ?

Liveins are everything needed by instructions of the block that are not produced by the block (but you need to be careful of register reuse. Some SU in the block may produce the register, but after another would have consumed it).
LiveOuts are everything produced by the Block which is not released (because another consumer elsewhere). Similarly you need to capture when the register is consumed for the last time in the Block (there may be a later block with a consumer of the register, but another instruction of another Block would have produced the register before).
This seems hard to do without correct liveIntervals. Those are correct only when reordering and doing handleMove, etc.

In D31124#715499, @vpykhtin wrote:

In general, I think moving instructions just to use standard RP tracker to discover liveins/liveouts isn't a good idea. It isn't only slow but doesn't look reliable too. Why not discover these sets using DAG directly?

[vpykhtin]

I may miss something, but it looks that you can build data edges when building a superdag consisting of blocks. Incoming data edges would be liveins, outcoming - liveouts.

In D31124#715509, @axeldavy wrote:

Could you describe how you would get all the relevant information ?

Liveins are everything needed by instructions of the block that are not produced by the block (but you need to be careful of register reuse. Some SU in the block may produce the register, but after another would have consumed it).
LiveOuts are everything produced by the Block which is not released (because another consumer elsewhere). Similarly you need to capture when the register is consumed for the last time in the Block (there may be a later block with a consumer of the register, but another instruction of another Block would have produced the register before).
This seems hard to do without correct liveIntervals. Those are correct only when reordering and doing handleMove, etc.

In D31124#715499, @vpykhtin wrote:

In general, I think moving instructions just to use standard RP tracker to discover liveins/liveouts isn't a good idea. It isn't only slow but doesn't look reliable too. Why not discover these sets using DAG directly?

[axeldavy]

Yes, that could work.
I didn't think of that.

Can we rely on having these properties:
. If SU(i) relies on the register produced by SU(j), there is a data dependency (even if SU(i) depends on SU(k), which depends itself on SU(j), in other words, redundancies are not removed).
. A data dependency between SU(j) and SU(i) always means that SU(i) needs as input the output of SU(j).

To sum up, do we have equivalence between "SU(i) has data dependency with SU(j)" and "one of SU(i) inputs is SU(j) output"

If we have these, I think we can make it work.

In D31124#715515, @vpykhtin wrote:

I may miss something, but it looks that you can build data edges when building a superdag consisting of blocks. Incoming data edges would be liveins, outcoming - liveouts.

[vpykhtin]

If SU(i) uses register produced by SI(j):

SU(i) has a predecessor data edge with a number of register produced by SU(j)
SU(j) has a successor data edge with a number of register used by SU(i)

Except that data edges doesn't contain lanemask, but I think this can be solved.

This way SU(i) has predecessor data edges for all used registers in that SU, and SU(j) has successor data edges for every SU using SU(j)'s output.

In D31124#715528, @axeldavy wrote:

Yes, that could work.
I didn't think of that.

Can we rely on having these properties:
. If SU(i) relies on the register produced by SU(j), there is a data dependency (even if SU(i) depends on SU(k), which depends itself on SU(j), in other words, redundancies are not removed).
. A data dependency between SU(j) and SU(i) always means that SU(i) needs as input the output of SU(j).

To sum up, do we have equivalence between "SU(i) has data dependency with SU(j)" and "one of SU(i) inputs is SU(j) output"

If we have these, I think we can make it work.

In D31124#715515, @vpykhtin wrote:

I may miss something, but it looks that you can build data edges when building a superdag consisting of blocks. Incoming data edges would be liveins, outcoming - liveouts.

[axeldavy]

This update reworks significantly the structure of the scheduler.

. Put all the code to handle register tracking into a class SISchedulerRPTracker. The class handles lane tracking as described previously.
. The code to schedule inside blocks has been completly reworked to use this class. Thus it doesn't use default RPTracker anymore, doesn't call handleMove, etc and is thus very significantly faster.

depends on D31587

[vpykhtin]

First part of comments related only to C++ issues

lib/Target/AMDGPU/SIMachineScheduler.cpp

144

const SmallVectorImpl<RegisterMaskPair> &

196

I recommend use auto

210

You're iterating over a vector increasing its' size at the same time. This is almost ok, except that vector can reallocate and all iterators would become invalidated.

Iterator Invalidation Rules (C++03)
vector: all iterators and references before the point of insertion are unaffected, unless the new container size is greater than the previous capacity (in which case all iterators and references are invalidated) [23.2.4.3/1]

217

Use const SmallVectorImpl<RegisterMaskPair> &

229

auto

247

auto

294

auto

325

SmallPtrSet is designed for pointers, gcc would complain, try consider SmallDenseSet

Are you developing using MSVS?

344

I saw a lot of such code snippets in your code, please make a function

376

#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
LLVM_DUMP_METHOD

lib/Target/AMDGPU/SIMachineScheduler.h

102

I think I should change unsiged to signed values inside GCNRegPressure structure so we could use it as a regpressure difference too.

123

const SmallVectorImpl<RegisterMaskPair> &

In general, when using Small... containers use SmallContainerImpl<T>& for passing by reference, its designed to be used so.

124

ditto

218

const SmallVectorImpl<RegisterMaskPair>&

219

ditto

247

const SmallVector<RegisterMaskPair, 8> &getInRegs() const { return LiveInRegs; }

248

ditto

387

const SmallVectorImpl<RegisterMaskPair>&

389

ditto

520

const SmallVector<RegisterMaskPair, 8> &getInRegs() const

524

ditto

[vpykhtin]

The following tests assert with this (and predecessors) patches with SISched turned on by default:

FAIL: LLVM :: CodeGen/AMDGPU/coalescer-subrange-crash.ll (4169 of 20226)
******************** TEST 'LLVM :: CodeGen/AMDGPU/coalescer-subrange-crash.ll' FAILED ********************
Script:
--
/srv/vpykhtin/git/debug.llvm/./bin/llc -march=amdgcn -verify-machineinstrs < /srv/vpykhtin/git/llvm/test/CodeGen/AMDGPU/coalescer-subrange-crash.ll | /srv/vpykhtin/git/debug.llvm/./bin/FileCheck /srv/vpykhtin/git/llvm/test/CodeGen/AMDGPU
/coalescer-subrange-crash.ll
--
Exit Code: 2

Command Output (stderr):
--
llc: malloc.c:2372: sysmalloc: Assertion `(old_top == (((mbinptr) (((char *) &((av)->bins[((1) - 1) * 2])) - __builtin_offsetof (struct malloc_chunk, fd)))) && old_size == 0) || ((unsigned long) (old_size) >= (unsigned long)((((__builtin_offsetof (struct malloc_chunk, fd_nextsize))+((2 *(sizeof(size_t))) - 1)) & ~((2 *(sizeof(size_t))) - 1))) && ((old_top)->size & 0x1) && ((unsigned long) old_end & pagemask) == 0)' failed.

FileCheck error: '-' is empty.
FileCheck command line:  /srv/vpykhtin/git/debug.llvm/./bin/FileCheck /srv/vpykhtin/git/llvm/test/CodeGen/AMDGPU/coalescer-subrange-crash.ll


FAIL: LLVM :: CodeGen/AMDGPU/undefined-subreg-liverange.ll (5010 of 20226)
******************** TEST 'LLVM :: CodeGen/AMDGPU/undefined-subreg-liverange.ll' FAILED ********************
Script:
--
/srv/vpykhtin/git/debug.llvm/./bin/llc -march=amdgcn -verify-machineinstrs < /srv/vpykhtin/git/llvm/test/CodeGen/AMDGPU/undefined-subreg-liverange.ll | /srv/vpykhtin/git/debug.llvm/./bin/FileCheck /srv/vpykhtin/git/llvm/test/CodeGen/AMDG
PU/undefined-subreg-liverange.ll
--
Exit Code: 1

Command Output (stderr):
--
llc: /srv/vpykhtin/git/llvm/lib/Target/AMDGPU/SIMachineScheduler.cpp:1793: void llvm::SIScheduleBlockCreator::removeUseFromDef(llvm::SmallVector<llvm::RegisterMaskPair, 8u>&, unsigned int, const llvm::SUnit*): Assertion `UsePos != Uses.end()' failed.
#0 0x00000000030298dd llvm::sys::PrintStackTrace(llvm::raw_ostream&) /srv/vpykhtin/git/llvm/lib/Support/Unix/Signals.inc:398:0
#1 0x000000000302996e PrintStackTraceSignalHandler(void*) /srv/vpykhtin/git/llvm/lib/Support/Unix/Signals.inc:462:0
#2 0x0000000003027dce llvm::sys::RunSignalHandlers() /srv/vpykhtin/git/llvm/lib/Support/Signals.cpp:43:0
#3 0x0000000003029275 SignalHandler(int) /srv/vpykhtin/git/llvm/lib/Support/Unix/Signals.inc:252:0
#4 0x00002b433235c330 __restore_rt (/lib/x86_64-linux-gnu/libpthread.so.0+0x10330)
#5 0x00002b4333415c37 gsignal /build/eglibc-MjiXCM/eglibc-2.19/signal/../nptl/sysdeps/unix/sysv/linux/raise.c:56:0
#6 0x00002b4333419028 abort /build/eglibc-MjiXCM/eglibc-2.19/stdlib/abort.c:91:0
#7 0x00002b433340ebf6 __assert_fail_base /build/eglibc-MjiXCM/eglibc-2.19/assert/assert.c:92:0
#8 0x00002b433340eca2 (/lib/x86_64-linux-gnu/libc.so.6+0x2fca2)
#9 0x000000000157376e llvm::SIScheduleBlockCreator::removeUseFromDef(llvm::SmallVector<llvm::RegisterMaskPair, 8u>&, unsigned int, llvm::SUnit const*) /srv/vpykhtin/git/llvm/lib/Target/AMDGPU/SIMachineScheduler.cpp:1795:0
#10 0x00000000015727e3 llvm::SIScheduleBlockCreator::createBlocksForVariant(llvm::SISchedulerBlockCreatorVariant) /srv/vpykhtin/git/llvm/lib/Target/AMDGPU/SIMachineScheduler.cpp:1613:0
#11 0x000000000156ef3e llvm::SIScheduleBlockCreator::getBlocks(llvm::SISchedulerBlockCreatorVariant) /srv/vpykhtin/git/llvm/lib/Target/AMDGPU/SIMachineScheduler.cpp:1043:0
#12 0x0000000001574e69 llvm::SIScheduler::scheduleVariant(llvm::SISchedulerBlockCreatorVariant, llvm::SISchedulerBlockSchedulerVariant) /srv/vpykhtin/git/llvm/lib/Target/AMDGPU/SIMachineScheduler.cpp:2073:0
#13 0x0000000001575eea llvm::SIScheduleDAGMI::schedule() /srv/vpykhtin/git/llvm/lib/Target/AMDGPU/SIMachineScheduler.cpp:2233:0
#14 0x0000000002659da5 (anonymous namespace)::MachineSchedulerBase::scheduleRegions(llvm::ScheduleDAGInstrs&, bool) /srv/vpykhtin/git/llvm/lib/CodeGen/MachineScheduler.cpp:524:0
#15 0x00000000026591ee (anonymous namespace)::MachineScheduler::runOnMachineFunction(llvm::MachineFunction&) /srv/vpykhtin/git/llvm/lib/CodeGen/MachineScheduler.cpp:387:0
#16 0x00000000025ce4f9 llvm::MachineFunctionPass::runOnFunction(llvm::Function&) /srv/vpykhtin/git/llvm/lib/CodeGen/MachineFunctionPass.cpp:62:0
#17 0x000000000298e138 llvm::FPPassManager::runOnFunction(llvm::Function&) /srv/vpykhtin/git/llvm/lib/IR/LegacyPassManager.cpp:1513:0
#18 0x000000000298e2cb llvm::FPPassManager::runOnModule(llvm::Module&) /srv/vpykhtin/git/llvm/lib/IR/LegacyPassManager.cpp:1534:0
#19 0x000000000298e666 (anonymous namespace)::MPPassManager::runOnModule(llvm::Module&) /srv/vpykhtin/git/llvm/lib/IR/LegacyPassManager.cpp:1590:0
#20 0x000000000298edb6 llvm::legacy::PassManagerImpl::run(llvm::Module&) /srv/vpykhtin/git/llvm/lib/IR/LegacyPassManager.cpp:1693:0
#21 0x000000000298eff7 llvm::legacy::PassManager::run(llvm::Module&) /srv/vpykhtin/git/llvm/lib/IR/LegacyPassManager.cpp:1725:0
#22 0x000000000124c627 compileModule(char**, llvm::LLVMContext&) /srv/vpykhtin/git/llvm/tools/llc/llc.cpp:579:0
#23 0x000000000124aca8 main /srv/vpykhtin/git/llvm/tools/llc/llc.cpp:331:0
#24 0x00002b4333400f45 __libc_start_main /build/eglibc-MjiXCM/eglibc-2.19/csu/libc-start.c:321:0
#25 0x0000000001248cb9 _start (/srv/vpykhtin/git/debug.llvm/./bin/llc+0x1248cb9)
Stack dump:
0.      Program arguments: /srv/vpykhtin/git/debug.llvm/./bin/llc -march=amdgcn -verify-machineinstrs
1.      Running pass 'Function Pass Manager' on module '<stdin>'.
2.      Running pass 'Machine Instruction Scheduler' on function '@partially_undef_copy'

FAIL: LLVM :: CodeGen/AMDGPU/unigine-liveness-crash.ll (5126 of 20226)
******************** TEST 'LLVM :: CodeGen/AMDGPU/unigine-liveness-crash.ll' FAILED ********************
Script:
--
/srv/vpykhtin/git/debug.llvm/./bin/llc -march=amdgcn -verify-machineinstrs < /srv/vpykhtin/git/llvm/test/CodeGen/AMDGPU/unigine-liveness-crash.ll | /srv/vpykhtin/git/debug.llvm/./bin/FileCheck /srv/vpykhtin/git/llvm/test/CodeGen/AMDGPU/unigine-liveness-crash.ll
--
Exit Code: 2

Command Output (stderr):
--
#0 0x00000000030298dd llvm::sys::PrintStackTrace(llvm::raw_ostream&) /srv/vpykhtin/git/llvm/lib/Support/Unix/Signals.inc:398:0
#1 0x000000000302996e PrintStackTraceSignalHandler(void*) /srv/vpykhtin/git/llvm/lib/Support/Unix/Signals.inc:462:0
#2 0x0000000003027dce llvm::sys::RunSignalHandlers() /srv/vpykhtin/git/llvm/lib/Support/Signals.cpp:43:0
#3 0x0000000003029275 SignalHandler(int) /srv/vpykhtin/git/llvm/lib/Support/Unix/Signals.inc:252:0
#4 0x00002ac49b609330 __restore_rt (/lib/x86_64-linux-gnu/libpthread.so.0+0x10330)
#5 0x000000000156a920 llvm::SISchedulerRPTracker::SISchedulerRPTracker(llvm::SmallVector<llvm::RegisterMaskPair, 8u> const&, llvm::SmallVector<llvm::RegisterMaskPair, 8u> const&, std::vector<llvm::SmallVector<unsigned int, 8u>, std::allocator<llvm::SmallVector<unsigned int, 8u> > > const&, std::vector<llvm::SmallVector<unsigned int, 8u>, std::allocator<llvm::SmallVector<unsigned int, 8u> > > const&, std::vector<llvm::SmallVector<llvm::RegisterMaskPair, 8u>, std::allocator<llvm::SmallVector<llvm::RegisterMaskPair, 8u> > > const&, std::vector<llvm::SmallVector<llvm::RegisterMaskPair, 8u>, std::allocator<llvm::SmallVector<llvm::RegisterMaskPair, 8u> > > const&, llvm::MachineRegisterInfo const*, llvm::TargetRegisterInfo const*, unsigned int, unsigned int, bool) /srv/vpykhtin/git/llvm/lib/Target/AMDGPU/SIMachineScheduler.cpp:198:0
#6 0x000000000156dace llvm::SIScheduleBlock::schedule() /srv/vpykhtin/git/llvm/lib/Target/AMDGPU/SIMachineScheduler.cpp:835:0
#7 0x000000000156df10 llvm::SIScheduleBlock::finalize() /srv/vpykhtin/git/llvm/lib/Target/AMDGPU/SIMachineScheduler.cpp:877:0
#8 0x0000000001572b1d llvm::SIScheduleBlockCreator::createBlocksForVariant(llvm::SISchedulerBlockCreatorVariant) /srv/vpykhtin/git/llvm/lib/Target/AMDGPU/SIMachineScheduler.cpp:1647:0
#9 0x000000000156ef3e llvm::SIScheduleBlockCreator::getBlocks(llvm::SISchedulerBlockCreatorVariant) /srv/vpykhtin/git/llvm/lib/Target/AMDGPU/SIMachineScheduler.cpp:1043:0
#10 0x0000000001574e69 llvm::SIScheduler::scheduleVariant(llvm::SISchedulerBlockCreatorVariant, llvm::SISchedulerBlockSchedulerVariant) /srv/vpykhtin/git/llvm/lib/Target/AMDGPU/SIMachineScheduler.cpp:2073:0
#11 0x0000000001575eea llvm::SIScheduleDAGMI::schedule() /srv/vpykhtin/git/llvm/lib/Target/AMDGPU/SIMachineScheduler.cpp:2233:0
#12 0x0000000002659da5 (anonymous namespace)::MachineSchedulerBase::scheduleRegions(llvm::ScheduleDAGInstrs&, bool) /srv/vpykhtin/git/llvm/lib/CodeGen/MachineScheduler.cpp:524:0
#13 0x00000000026591ee (anonymous namespace)::MachineScheduler::runOnMachineFunction(llvm::MachineFunction&) /srv/vpykhtin/git/llvm/lib/CodeGen/MachineScheduler.cpp:387:0
#14 0x00000000025ce4f9 llvm::MachineFunctionPass::runOnFunction(llvm::Function&) /srv/vpykhtin/git/llvm/lib/CodeGen/MachineFunctionPass.cpp:62:0
#15 0x000000000298e138 llvm::FPPassManager::runOnFunction(llvm::Function&) /srv/vpykhtin/git/llvm/lib/IR/LegacyPassManager.cpp:1513:0
#16 0x000000000298e2cb llvm::FPPassManager::runOnModule(llvm::Module&) /srv/vpykhtin/git/llvm/lib/IR/LegacyPassManager.cpp:1534:0
#17 0x000000000298e666 (anonymous namespace)::MPPassManager::runOnModule(llvm::Module&) /srv/vpykhtin/git/llvm/lib/IR/LegacyPassManager.cpp:1590:0
#18 0x000000000298edb6 llvm::legacy::PassManagerImpl::run(llvm::Module&) /srv/vpykhtin/git/llvm/lib/IR/LegacyPassManager.cpp:1693:0
#19 0x000000000298eff7 llvm::legacy::PassManager::run(llvm::Module&) /srv/vpykhtin/git/llvm/lib/IR/LegacyPassManager.cpp:1725:0
#20 0x000000000124c627 compileModule(char**, llvm::LLVMContext&) /srv/vpykhtin/git/llvm/tools/llc/llc.cpp:579:0
#21 0x000000000124aca8 main /srv/vpykhtin/git/llvm/tools/llc/llc.cpp:331:0
#22 0x00002ac49c6adf45 __libc_start_main /build/eglibc-MjiXCM/eglibc-2.19/csu/libc-start.c:321:0
#23 0x0000000001248cb9 _start (/srv/vpykhtin/git/debug.llvm/./bin/llc+0x1248cb9)
Stack dump:
0.      Program arguments: /srv/vpykhtin/git/debug.llvm/./bin/llc -march=amdgcn -verify-machineinstrs
1.      Running pass 'Function Pass Manager' on module '<stdin>'.
2.      Running pass 'Machine Instruction Scheduler' on function '@main'

[axeldavy]

For the first assert, it's a mistake in my code. Instead of assert, I should return doing nothing.

For the second error, I don't understand. There doesn't seem to be anything wrong at this line,
and when I run llc on that .ll I don't get error.

In D31124#720304, @vpykhtin wrote:

The following tests assert with this (and predecessors) patches with SISched turned on by default:

FAIL: LLVM :: CodeGen/AMDGPU/coalescer-subrange-crash.ll (4169 of 20226)
******************** TEST 'LLVM :: CodeGen/AMDGPU/coalescer-subrange-crash.ll' FAILED ********************
Script:
--
/srv/vpykhtin/git/debug.llvm/./bin/llc -march=amdgcn -verify-machineinstrs < /srv/vpykhtin/git/llvm/test/CodeGen/AMDGPU/coalescer-subrange-crash.ll | /srv/vpykhtin/git/debug.llvm/./bin/FileCheck /srv/vpykhtin/git/llvm/test/CodeGen/AMDGPU
/coalescer-subrange-crash.ll
--
Exit Code: 2

Command Output (stderr):
--
llc: malloc.c:2372: sysmalloc: Assertion `(old_top == (((mbinptr) (((char *) &((av)->bins[((1) - 1) * 2])) - __builtin_offsetof (struct malloc_chunk, fd)))) && old_size == 0) || ((unsigned long) (old_size) >= (unsigned long)((((__builtin_offsetof (struct malloc_chunk, fd_nextsize))+((2 *(sizeof(size_t))) - 1)) & ~((2 *(sizeof(size_t))) - 1))) && ((old_top)->size & 0x1) && ((unsigned long) old_end & pagemask) == 0)' failed.

FileCheck error: '-' is empty.
FileCheck command line:  /srv/vpykhtin/git/debug.llvm/./bin/FileCheck /srv/vpykhtin/git/llvm/test/CodeGen/AMDGPU/coalescer-subrange-crash.ll


FAIL: LLVM :: CodeGen/AMDGPU/undefined-subreg-liverange.ll (5010 of 20226)
******************** TEST 'LLVM :: CodeGen/AMDGPU/undefined-subreg-liverange.ll' FAILED ********************
Script:
--
/srv/vpykhtin/git/debug.llvm/./bin/llc -march=amdgcn -verify-machineinstrs < /srv/vpykhtin/git/llvm/test/CodeGen/AMDGPU/undefined-subreg-liverange.ll | /srv/vpykhtin/git/debug.llvm/./bin/FileCheck /srv/vpykhtin/git/llvm/test/CodeGen/AMDG
PU/undefined-subreg-liverange.ll
--
Exit Code: 1

Command Output (stderr):
--
llc: /srv/vpykhtin/git/llvm/lib/Target/AMDGPU/SIMachineScheduler.cpp:1793: void llvm::SIScheduleBlockCreator::removeUseFromDef(llvm::SmallVector<llvm::RegisterMaskPair, 8u>&, unsigned int, const llvm::SUnit*): Assertion `UsePos != Uses.end()' failed.
#0 0x00000000030298dd llvm::sys::PrintStackTrace(llvm::raw_ostream&) /srv/vpykhtin/git/llvm/lib/Support/Unix/Signals.inc:398:0
#1 0x000000000302996e PrintStackTraceSignalHandler(void*) /srv/vpykhtin/git/llvm/lib/Support/Unix/Signals.inc:462:0
#2 0x0000000003027dce llvm::sys::RunSignalHandlers() /srv/vpykhtin/git/llvm/lib/Support/Signals.cpp:43:0
#3 0x0000000003029275 SignalHandler(int) /srv/vpykhtin/git/llvm/lib/Support/Unix/Signals.inc:252:0
#4 0x00002b433235c330 __restore_rt (/lib/x86_64-linux-gnu/libpthread.so.0+0x10330)
#5 0x00002b4333415c37 gsignal /build/eglibc-MjiXCM/eglibc-2.19/signal/../nptl/sysdeps/unix/sysv/linux/raise.c:56:0
#6 0x00002b4333419028 abort /build/eglibc-MjiXCM/eglibc-2.19/stdlib/abort.c:91:0
#7 0x00002b433340ebf6 __assert_fail_base /build/eglibc-MjiXCM/eglibc-2.19/assert/assert.c:92:0
#8 0x00002b433340eca2 (/lib/x86_64-linux-gnu/libc.so.6+0x2fca2)
#9 0x000000000157376e llvm::SIScheduleBlockCreator::removeUseFromDef(llvm::SmallVector<llvm::RegisterMaskPair, 8u>&, unsigned int, llvm::SUnit const*) /srv/vpykhtin/git/llvm/lib/Target/AMDGPU/SIMachineScheduler.cpp:1795:0
#10 0x00000000015727e3 llvm::SIScheduleBlockCreator::createBlocksForVariant(llvm::SISchedulerBlockCreatorVariant) /srv/vpykhtin/git/llvm/lib/Target/AMDGPU/SIMachineScheduler.cpp:1613:0
#11 0x000000000156ef3e llvm::SIScheduleBlockCreator::getBlocks(llvm::SISchedulerBlockCreatorVariant) /srv/vpykhtin/git/llvm/lib/Target/AMDGPU/SIMachineScheduler.cpp:1043:0
#12 0x0000000001574e69 llvm::SIScheduler::scheduleVariant(llvm::SISchedulerBlockCreatorVariant, llvm::SISchedulerBlockSchedulerVariant) /srv/vpykhtin/git/llvm/lib/Target/AMDGPU/SIMachineScheduler.cpp:2073:0
#13 0x0000000001575eea llvm::SIScheduleDAGMI::schedule() /srv/vpykhtin/git/llvm/lib/Target/AMDGPU/SIMachineScheduler.cpp:2233:0
#14 0x0000000002659da5 (anonymous namespace)::MachineSchedulerBase::scheduleRegions(llvm::ScheduleDAGInstrs&, bool) /srv/vpykhtin/git/llvm/lib/CodeGen/MachineScheduler.cpp:524:0
#15 0x00000000026591ee (anonymous namespace)::MachineScheduler::runOnMachineFunction(llvm::MachineFunction&) /srv/vpykhtin/git/llvm/lib/CodeGen/MachineScheduler.cpp:387:0
#16 0x00000000025ce4f9 llvm::MachineFunctionPass::runOnFunction(llvm::Function&) /srv/vpykhtin/git/llvm/lib/CodeGen/MachineFunctionPass.cpp:62:0
#17 0x000000000298e138 llvm::FPPassManager::runOnFunction(llvm::Function&) /srv/vpykhtin/git/llvm/lib/IR/LegacyPassManager.cpp:1513:0
#18 0x000000000298e2cb llvm::FPPassManager::runOnModule(llvm::Module&) /srv/vpykhtin/git/llvm/lib/IR/LegacyPassManager.cpp:1534:0
#19 0x000000000298e666 (anonymous namespace)::MPPassManager::runOnModule(llvm::Module&) /srv/vpykhtin/git/llvm/lib/IR/LegacyPassManager.cpp:1590:0
#20 0x000000000298edb6 llvm::legacy::PassManagerImpl::run(llvm::Module&) /srv/vpykhtin/git/llvm/lib/IR/LegacyPassManager.cpp:1693:0
#21 0x000000000298eff7 llvm::legacy::PassManager::run(llvm::Module&) /srv/vpykhtin/git/llvm/lib/IR/LegacyPassManager.cpp:1725:0
#22 0x000000000124c627 compileModule(char**, llvm::LLVMContext&) /srv/vpykhtin/git/llvm/tools/llc/llc.cpp:579:0
#23 0x000000000124aca8 main /srv/vpykhtin/git/llvm/tools/llc/llc.cpp:331:0
#24 0x00002b4333400f45 __libc_start_main /build/eglibc-MjiXCM/eglibc-2.19/csu/libc-start.c:321:0
#25 0x0000000001248cb9 _start (/srv/vpykhtin/git/debug.llvm/./bin/llc+0x1248cb9)
Stack dump:
0.      Program arguments: /srv/vpykhtin/git/debug.llvm/./bin/llc -march=amdgcn -verify-machineinstrs
1.      Running pass 'Function Pass Manager' on module '<stdin>'.
2.      Running pass 'Machine Instruction Scheduler' on function '@partially_undef_copy'

FAIL: LLVM :: CodeGen/AMDGPU/unigine-liveness-crash.ll (5126 of 20226)
******************** TEST 'LLVM :: CodeGen/AMDGPU/unigine-liveness-crash.ll' FAILED ********************
Script:
--
/srv/vpykhtin/git/debug.llvm/./bin/llc -march=amdgcn -verify-machineinstrs < /srv/vpykhtin/git/llvm/test/CodeGen/AMDGPU/unigine-liveness-crash.ll | /srv/vpykhtin/git/debug.llvm/./bin/FileCheck /srv/vpykhtin/git/llvm/test/CodeGen/AMDGPU/unigine-liveness-crash.ll
--
Exit Code: 2

Command Output (stderr):
--
#0 0x00000000030298dd llvm::sys::PrintStackTrace(llvm::raw_ostream&) /srv/vpykhtin/git/llvm/lib/Support/Unix/Signals.inc:398:0
#1 0x000000000302996e PrintStackTraceSignalHandler(void*) /srv/vpykhtin/git/llvm/lib/Support/Unix/Signals.inc:462:0
#2 0x0000000003027dce llvm::sys::RunSignalHandlers() /srv/vpykhtin/git/llvm/lib/Support/Signals.cpp:43:0
#3 0x0000000003029275 SignalHandler(int) /srv/vpykhtin/git/llvm/lib/Support/Unix/Signals.inc:252:0
#4 0x00002ac49b609330 __restore_rt (/lib/x86_64-linux-gnu/libpthread.so.0+0x10330)
#5 0x000000000156a920 llvm::SISchedulerRPTracker::SISchedulerRPTracker(llvm::SmallVector<llvm::RegisterMaskPair, 8u> const&, llvm::SmallVector<llvm::RegisterMaskPair, 8u> const&, std::vector<llvm::SmallVector<unsigned int, 8u>, std::allocator<llvm::SmallVector<unsigned int, 8u> > > const&, std::vector<llvm::SmallVector<unsigned int, 8u>, std::allocator<llvm::SmallVector<unsigned int, 8u> > > const&, std::vector<llvm::SmallVector<llvm::RegisterMaskPair, 8u>, std::allocator<llvm::SmallVector<llvm::RegisterMaskPair, 8u> > > const&, std::vector<llvm::SmallVector<llvm::RegisterMaskPair, 8u>, std::allocator<llvm::SmallVector<llvm::RegisterMaskPair, 8u> > > const&, llvm::MachineRegisterInfo const*, llvm::TargetRegisterInfo const*, unsigned int, unsigned int, bool) /srv/vpykhtin/git/llvm/lib/Target/AMDGPU/SIMachineScheduler.cpp:198:0
#6 0x000000000156dace llvm::SIScheduleBlock::schedule() /srv/vpykhtin/git/llvm/lib/Target/AMDGPU/SIMachineScheduler.cpp:835:0
#7 0x000000000156df10 llvm::SIScheduleBlock::finalize() /srv/vpykhtin/git/llvm/lib/Target/AMDGPU/SIMachineScheduler.cpp:877:0
#8 0x0000000001572b1d llvm::SIScheduleBlockCreator::createBlocksForVariant(llvm::SISchedulerBlockCreatorVariant) /srv/vpykhtin/git/llvm/lib/Target/AMDGPU/SIMachineScheduler.cpp:1647:0
#9 0x000000000156ef3e llvm::SIScheduleBlockCreator::getBlocks(llvm::SISchedulerBlockCreatorVariant) /srv/vpykhtin/git/llvm/lib/Target/AMDGPU/SIMachineScheduler.cpp:1043:0
#10 0x0000000001574e69 llvm::SIScheduler::scheduleVariant(llvm::SISchedulerBlockCreatorVariant, llvm::SISchedulerBlockSchedulerVariant) /srv/vpykhtin/git/llvm/lib/Target/AMDGPU/SIMachineScheduler.cpp:2073:0
#11 0x0000000001575eea llvm::SIScheduleDAGMI::schedule() /srv/vpykhtin/git/llvm/lib/Target/AMDGPU/SIMachineScheduler.cpp:2233:0
#12 0x0000000002659da5 (anonymous namespace)::MachineSchedulerBase::scheduleRegions(llvm::ScheduleDAGInstrs&, bool) /srv/vpykhtin/git/llvm/lib/CodeGen/MachineScheduler.cpp:524:0
#13 0x00000000026591ee (anonymous namespace)::MachineScheduler::runOnMachineFunction(llvm::MachineFunction&) /srv/vpykhtin/git/llvm/lib/CodeGen/MachineScheduler.cpp:387:0
#14 0x00000000025ce4f9 llvm::MachineFunctionPass::runOnFunction(llvm::Function&) /srv/vpykhtin/git/llvm/lib/CodeGen/MachineFunctionPass.cpp:62:0
#15 0x000000000298e138 llvm::FPPassManager::runOnFunction(llvm::Function&) /srv/vpykhtin/git/llvm/lib/IR/LegacyPassManager.cpp:1513:0
#16 0x000000000298e2cb llvm::FPPassManager::runOnModule(llvm::Module&) /srv/vpykhtin/git/llvm/lib/IR/LegacyPassManager.cpp:1534:0
#17 0x000000000298e666 (anonymous namespace)::MPPassManager::runOnModule(llvm::Module&) /srv/vpykhtin/git/llvm/lib/IR/LegacyPassManager.cpp:1590:0
#18 0x000000000298edb6 llvm::legacy::PassManagerImpl::run(llvm::Module&) /srv/vpykhtin/git/llvm/lib/IR/LegacyPassManager.cpp:1693:0
#19 0x000000000298eff7 llvm::legacy::PassManager::run(llvm::Module&) /srv/vpykhtin/git/llvm/lib/IR/LegacyPassManager.cpp:1725:0
#20 0x000000000124c627 compileModule(char**, llvm::LLVMContext&) /srv/vpykhtin/git/llvm/tools/llc/llc.cpp:579:0
#21 0x000000000124aca8 main /srv/vpykhtin/git/llvm/tools/llc/llc.cpp:331:0
#22 0x00002ac49c6adf45 __libc_start_main /build/eglibc-MjiXCM/eglibc-2.19/csu/libc-start.c:321:0
#23 0x0000000001248cb9 _start (/srv/vpykhtin/git/debug.llvm/./bin/llc+0x1248cb9)
Stack dump:
0.      Program arguments: /srv/vpykhtin/git/debug.llvm/./bin/llc -march=amdgcn -verify-machineinstrs
1.      Running pass 'Function Pass Manager' on module '<stdin>'.
2.      Running pass 'Machine Instruction Scheduler' on function '@main'

[axeldavy]

Fixed the assert in removeUseFromDef.

Added some const and replaced SmallVector<RegisterMaskPair, 8> by SmallVectorImpl<RegisterMaskPair>

[axeldavy]

lib/Target/AMDGPU/SIMachineScheduler.cpp

210

What do you suggest to fix this problem ?

376

Why LLVM_DUMP_METHOD on an empty line ?

lib/Target/AMDGPU/SIMachineScheduler.h

218

right, I missed that for this update. Will be for next time.

387

canno be const here because we remove things from Uses.

[vpykhtin]

Thanks Axel!

I had to mention that I'm enabling SISched by commenting out

ScheduleDAGInstrs *GCNPassConfig::createMachineScheduler(
  MachineSchedContext *C) const {
  const SISubtarget &ST = C->MF->getSubtarget<SISubtarget>();
  //if (ST.enableSIScheduler())
    return createSIMachineScheduler(C);
  //return createGCNMaxOccupancyMachineScheduler(C);
}

This way I got ShouldTrackLaneMasks = true

[axeldavy]

Sure. In this patch I make ShouldTrackLaneMasks set to true always.

In D31124#720730, @vpykhtin wrote:

Thanks Axel!

I had to mention that I'm enabling SISched by commenting out

ScheduleDAGInstrs *GCNPassConfig::createMachineScheduler(
  MachineSchedContext *C) const {
  const SISubtarget &ST = C->MF->getSubtarget<SISubtarget>();
  //if (ST.enableSIScheduler())
    return createSIMachineScheduler(C);
  //return createGCNMaxOccupancyMachineScheduler(C);
}

This way I got ShouldTrackLaneMasks = true

[vpykhtin]

For the second assert it may be the case for iterator invalidation, though I haven't checked.

lib/Target/AMDGPU/SIMachineScheduler.cpp

210

Easy way is to reserve sufficient number of elements to avoid reallocation, but this is not reliable as code correctness depends on reserve which is in general optional. You may consider using std::list for this.

376

I meant something like this:

#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)

LLVM_DUMP_METHOD
SISchedulerRPTracker::printDebugLives()

[axeldavy]

I think I took into account all remaining comments, please tell if I missed something.

[axeldavy]

I had incorrectly tested after introducing getPressureOfReg.
RPTracker->getPressureOfReg uses were incorrect, because the RPTracker wasn't initialized yet at the moment it was called.

I fixed the problem by defining it twice (each version using the available data in its class).
This is a small function, introduced to remove redundant code as you suggested.
If you have a better suggestion I'll take it.

[arsenm]

Is this still needed?

[axeldavy]

In D31124#1406796, @arsenm wrote:

Is this still needed?

To my knowledge, yes. Do you have any insight on why it wouldn't be anymore ? Has there been change related to lane tracking ?

lib/Target/AMDGPU/SIMachineScheduler.h

 #include "llvm/CodeGen/MachineScheduler.h"
 #include "llvm/CodeGen/RegisterPressure.h"
 #include "llvm/CodeGen/ScheduleDAG.h"
+#include "llvm/MC/LaneBitmask.h"
 #include <cassert>
 #include <cstdint>
 #include <map>

   // Note that some registers are not 32 bits,
   // and thus the pressure is not equal
   // to the number of live registers.
-  std::set<unsigned> LiveInRegs;
-  std::set<unsigned> LiveOutRegs;
+  SmallVector<RegisterMaskPair, 8> LiveInRegs;
+  SmallVector<RegisterMaskPair, 8> LiveOutRegs;
 
   bool Scheduled = false;
   bool HighLatencyBlock = false;

     return InternalAdditionnalPressure;
   }
 
-  std::set<unsigned> &getInRegs() { return LiveInRegs; }
-  std::set<unsigned> &getOutRegs() { return LiveOutRegs; }
+  SmallVector<RegisterMaskPair, 8> &getInRegs() { return LiveInRegs; }
+  SmallVector<RegisterMaskPair, 8> &getOutRegs() { return LiveOutRegs; }
 
   void printDebug(bool Full);
 

   SISchedulerBlockSchedulerVariant Variant;
   std::vector<SIScheduleBlock*> Blocks;
 
-  std::vector<std::map<unsigned, unsigned>> LiveOutRegsNumUsages;
-  std::set<unsigned> LiveRegs;
+  // For each register, basis of LaneBitmask to generate all
+  // LaneBitmasks involved in the scheduling.
+  // If the register is not in the map, it is assumed it is always
+  // used with full mask.
+  std::map<unsigned, SmallVector<LaneBitmask, 8>> LaneMaskBasisForReg;
+
+  // The RegisterMaskPair below are assumed to be pairs (Reg, Mask)
+  // such that Mask is in LaneMaskBasisForReg[Reg] if exists.
+  std::vector<std::map<RegisterMaskPair, unsigned>> LiveOutRegsNumUsages;
+  std::map<unsigned, LaneBitmask> LiveRegs;
   // Num of schedulable unscheduled blocks reading the register.
-  std::map<unsigned, unsigned> LiveRegsConsumers;
+  std::map<RegisterMaskPair, unsigned> LiveRegsConsumers;
+  // Blocks's getInRegs, but with RegisterMaskPair with Mask
+  // in LaneMaskBasisForReg[Reg] if exists.
+  DenseMap<unsigned, SmallVector<RegisterMaskPair, 8>> InRegsForBlock;
+  DenseMap<unsigned, SmallVector<RegisterMaskPair, 8>> OutRegsForBlock;
 
   std::vector<unsigned> LastPosHighLatencyParentScheduled;
   int LastPosWaitedHighLatency;

   unsigned getSGPRUsage() { return maxSregUsage; }
 
 private:
+
+  // Convert Reg/Mask to a list of Reg/Mask, with Mask in
+  // LaneMaskBasisForReg.
+  SmallVector<RegisterMaskPair, 8> getPairsForReg(unsigned Reg,
+                                                  LaneBitmask Mask);
+  // ToAppend: where to append the result.
+  void getPairsForReg(SmallVector<RegisterMaskPair, 8> &ToAppend,
+                      unsigned Reg, LaneBitmask Mask);
+  // Idem for a list of Reg/Mask
+  SmallVector<RegisterMaskPair, 8> getPairsForRegs(
+    const SmallVector<RegisterMaskPair, 8> &Regs);
+
   struct SIBlockSchedCandidate : SISchedulerCandidate {
     // The best Block candidate.
     SIScheduleBlock *Block = nullptr;

                             SIBlockSchedCandidate &TryCand);
   SIScheduleBlock *pickBlock();
 
-  void addLiveRegs(std::set<unsigned> &Regs);
-  void decreaseLiveRegs(SIScheduleBlock *Block, std::set<unsigned> &Regs);
+  // The Mask in RegisterMaskPair needs to be
+  // element of LaneMaskBasisForReg.
+  void addLiveRegs(SmallVector<RegisterMaskPair, 8> &Regs);
+  void decreaseLiveRegs(SIScheduleBlock *Block,
+                        SmallVector<RegisterMaskPair, 8> &Regs);
   void releaseBlockSuccs(SIScheduleBlock *Parent);
   void blockScheduled(SIScheduleBlock *Block);
 
   // Check register pressure change
-  // by scheduling a block with these LiveIn and LiveOut.
-  std::vector<int> checkRegUsageImpact(std::set<unsigned> &InRegs,
-                                       std::set<unsigned> &OutRegs);
+  // by scheduling a block
+  void checkRegUsageImpact(unsigned BlockID, int &DiffVGPR, int &DiffSGPR);
 
   void schedule();
 };

   SIScheduleBlockCreator BlockCreator;
 
 public:
-  SIScheduler(SIScheduleDAGMI *DAG) : DAG(DAG), BlockCreator(DAG) {}
+  SIScheduler(SIScheduleDAGMI *DAG) :
+    DAG(DAG), BlockCreator(DAG) {}
 
   ~SIScheduler() = default;
 

 
   // To init Block's RPTracker.
   void initRPTracker(RegPressureTracker &RPTracker) {
-    RPTracker.init(&MF, RegClassInfo, LIS, BB, RegionBegin, false, false);
+    RPTracker.init(&MF, RegClassInfo, LIS, BB, RegionBegin, ShouldTrackLaneMasks, false);
   }
 
   MachineBasicBlock *getBB() { return BB; }

                                                      unsigned &VgprUsage,
                                                      unsigned &SgprUsage);
 
-  std::set<unsigned> getInRegs() {
-    std::set<unsigned> InRegs;
-    for (const auto &RegMaskPair : RPTracker.getPressure().LiveInRegs) {
-      InRegs.insert(RegMaskPair.RegUnit);
-    }
-    return InRegs;
+  const SmallVector<RegisterMaskPair, 8> getInRegs() {
+    return RPTracker.getPressure().LiveInRegs;
   }
 
-  std::set<unsigned> getOutRegs() {
-    std::set<unsigned> OutRegs;
-    for (const auto &RegMaskPair : RPTracker.getPressure().LiveOutRegs) {
-      OutRegs.insert(RegMaskPair.RegUnit);
-    }
-    return OutRegs;
+  const SmallVector<RegisterMaskPair, 8> getOutRegs() {
+    return RPTracker.getPressure().LiveOutRegs;
   };
 
   unsigned getVGPRSetID() const { return VGPRSetID; }
   unsigned getSGPRSetID() const { return SGPRSetID; }
 
+  bool shouldTrackLaneMasks() const { return ShouldTrackLaneMasks; }
+
 private:
   void topologicalSort();
   // After scheduling is done, improve low latency placements.

lib/Target/AMDGPU/SIMachineScheduler.cpp

 #include "llvm/CodeGen/MachineScheduler.h"
 #include "llvm/CodeGen/RegisterPressure.h"
 #include "llvm/CodeGen/SlotIndexes.h"
+#include "llvm/MC/LaneBitmask.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/ErrorHandling.h"
 #include "llvm/Support/raw_ostream.h"

   Scheduled = true;
 }
 
-// Returns if the register was set between first and last.
-static bool isDefBetween(unsigned Reg,
+// Returns if one of the register lanes was set between first and last.
+// Lanes is set to the lane mask set.
+static LaneBitmask findDefsBetween(unsigned Reg,
                            SlotIndex First, SlotIndex Last,
                            const MachineRegisterInfo *MRI,
                            const LiveIntervals *LIS) {
-  for (MachineRegisterInfo::def_instr_iterator
-       UI = MRI->def_instr_begin(Reg),
-       UE = MRI->def_instr_end(); UI != UE; ++UI) {
-    const MachineInstr* MI = &*UI;
+  LaneBitmask LaneMask = LaneBitmask::getNone();
+  const TargetRegisterInfo *TRI = MRI->getTargetRegisterInfo();
+  for (const MachineOperand &MO : MRI->def_operands(Reg)) {
+    const MachineInstr* MI = MO.getParent();
     if (MI->isDebugValue())
       continue;
     SlotIndex InstSlot = LIS->getInstructionIndex(*MI).getRegSlot();
-    if (InstSlot >= First && InstSlot <= Last)
-      return true;
+    if (InstSlot >= First && InstSlot <= Last) {
+        unsigned SubRegIdx = MO.getSubReg();
+        LaneBitmask DefMask = TRI->getSubRegIndexLaneMask(SubRegIdx);
+        LaneMask |= DefMask;
+    }
   }
-  return false;
+  return LaneMask;
 }
 
 void SIScheduleBlock::initRegPressure(MachineBasicBlock::iterator BeginBlock,

   TopRPTracker.addLiveRegs(RPTracker.getPressure().LiveInRegs);
   BotRPTracker.addLiveRegs(RPTracker.getPressure().LiveOutRegs);
 
+  LiveInRegs.clear();
+
   // Do not Track Physical Registers, because it messes up.
   for (const auto &RegMaskPair : RPTracker.getPressure().LiveInRegs) {
     if (TargetRegisterInfo::isVirtualRegister(RegMaskPair.RegUnit))
-      LiveInRegs.insert(RegMaskPair.RegUnit);
+      LiveInRegs.push_back(RegMaskPair);
   }
   LiveOutRegs.clear();
   // There is several possibilities to distinguish:

   // The RPTracker's LiveOutRegs has 1, 3, (some correct or incorrect)4, 5, 7
   // Comparing to LiveInRegs is not sufficient to differenciate 4 vs 5, 7
   // The use of findDefBetween removes the case 4.
+  // LaneMask: Conceptually this is the same than described above, except
+  // we differenciate what happens for all reg lanes.
   for (const auto &RegMaskPair : RPTracker.getPressure().LiveOutRegs) {
     unsigned Reg = RegMaskPair.RegUnit;
-    if (TargetRegisterInfo::isVirtualRegister(Reg) &&
-        isDefBetween(Reg, LIS->getInstructionIndex(*BeginBlock).getRegSlot(),
-                     LIS->getInstructionIndex(*EndBlock).getRegSlot(), MRI,
-                     LIS)) {
-      LiveOutRegs.insert(Reg);
-    }
+    if (!TargetRegisterInfo::isVirtualRegister(Reg))
+      continue;
+    LaneBitmask LaneMask = findDefsBetween(Reg,
+      LIS->getInstructionIndex(*BeginBlock).getRegSlot(),
+      LIS->getInstructionIndex(*EndBlock).getRegSlot(), MRI,
+      LIS);
+    // Being in LaneMask but not in RegMaskPair.LaneMask means the lane
+    // Was temporarily defined, but then consumed in the block.
+    LaneMask &= RegMaskPair.LaneMask;
+    if (LaneMask.any())
+      LiveOutRegs.push_back(RegisterMaskPair(RegMaskPair.RegUnit,
+                                             DAG->shouldTrackLaneMasks() ? LaneMask :
+                                             LaneBitmask::getAll()));
   }
 
   // Pressure = sum_alive_registers register size

     dbgs() << "LiveOutPressure " << LiveOutPressure[DAG->getSGPRSetID()] << ' '
            << LiveOutPressure[DAG->getVGPRSetID()] << "\n\n";
     dbgs() << "LiveIns:\n";
-    for (unsigned Reg : LiveInRegs)
-      dbgs() << PrintVRegOrUnit(Reg, DAG->getTRI()) << ' ';
+    for (const auto &Ins : LiveInRegs) {
+      dbgs() << PrintVRegOrUnit(Ins.RegUnit, DAG->getTRI());
+      if (!Ins.LaneMask.all())
+        dbgs() << ':' << PrintLaneMask(Ins.LaneMask);
+      dbgs() << ' ';
+    }
 
     dbgs() << "\nLiveOuts:\n";
-    for (unsigned Reg : LiveOutRegs)
-      dbgs() << PrintVRegOrUnit(Reg, DAG->getTRI()) << ' ';
+    for (const auto &Outs : LiveOutRegs) {
+      dbgs() << PrintVRegOrUnit(Outs.RegUnit, DAG->getTRI());
+      if (!Outs.LaneMask.all())
+        dbgs() << ':' << PrintLaneMask(Outs.LaneMask);
+      dbgs() << ' ';
+    }
   }
 
   dbgs() << "\nInstructions:\n";

         // It would gain a lot if there was a way to recompute the
         // LiveIntervals for the entire scheduling region.
         DAG->getLIS()->handleMove(*MI, /*UpdateFlags=*/true);
+
+        if (!MI->isDebugValue()) {
+          // Reset read - undef flags and update them later.
+          for (auto &Op : MI->operands())
+            if (Op.isReg() && Op.isDef())
+              Op.setIsUndef(false);
+
+          RegisterOperands RegOpers;
+          RegOpers.collect(*MI, *DAG->getTRI(), *DAG->getMRI(),
+                           DAG->shouldTrackLaneMasks(), false);
+          // Adjust liveness and add missing dead+read-undef flags.
+          auto SlotIdx = DAG->getLIS()->getInstructionIndex(*MI).getRegSlot();
+          RegOpers.adjustLaneLiveness(*DAG->getLIS(), *DAG->getMRI(), SlotIdx, MI);
+        }
         PosNew.push_back(CurrentTopFastSched);
       }
     }

     MachineBasicBlock::iterator POld = PosOld[i-1];
     MachineBasicBlock::iterator PNew = PosNew[i-1];
     if (PNew != POld) {
+      MachineInstr &MI = *POld;
       // Update the instruction stream.
       DAG->getBB()->splice(POld, DAG->getBB(), PNew);
 
       // Update LiveIntervals.
       DAG->getLIS()->handleMove(*POld, /*UpdateFlags=*/true);
+
+      if (!MI.isDebugValue()) {
+        // Reset read - undef flags and update them later.
+        for (auto &Op : MI.operands())
+          if (Op.isReg() && Op.isDef())
+            Op.setIsUndef(false);
+
+        RegisterOperands RegOpers;
+        RegOpers.collect(MI, *DAG->getTRI(), *DAG->getMRI(),
+                         DAG->shouldTrackLaneMasks(), false);
+        // Adjust liveness and add missing dead+read-undef flags.
+        auto SlotIdx = DAG->getLIS()->getInstructionIndex(MI).getRegSlot();
+        RegOpers.adjustLaneLiveness(*DAG->getLIS(), *DAG->getMRI(), SlotIdx, &MI);
+      }
     }
   }
 

   LastPosWaitedHighLatency(0), NumBlockScheduled(0), VregCurrentUsage(0),
   SregCurrentUsage(0), maxVregUsage(0), maxSregUsage(0) {
 
+  MachineRegisterInfo *MRI = DAG->getMRI();
+  // To track register usage, we define for each register definition
+  // a number of usages before it gets released.
+  // This doesn't work with LaneMasks.
+  // To handle LaneMasks, we 'cut' registers affected by LaneMasks
+  // into all their different Lanes possible
+  // and behave as if that (reg, LaneMask) was a register.
+  std::map<unsigned, SmallVector<LaneBitmask, 8>> RegWithLaneMask;
+  for (SIScheduleBlock *Block : Blocks) {
+    for (const auto &Ins : Block->getInRegs()) {
+      if (!Ins.LaneMask.all() &&
+          Ins.LaneMask != MRI->getMaxLaneMaskForVReg(Ins.RegUnit))
+        RegWithLaneMask[Ins.RegUnit].push_back(Ins.LaneMask);
+    }
+    for (const auto &Outs : Block->getOutRegs()) {
+      if (!Outs.LaneMask.all() &&
+          Outs.LaneMask != MRI->getMaxLaneMaskForVReg(Outs.RegUnit))
+        RegWithLaneMask[Outs.RegUnit].push_back(Outs.LaneMask);
+    }
+  }
+  for (const auto &Ins : DAG->getInRegs()) {
+    if (!Ins.LaneMask.all() &&
+        Ins.LaneMask != MRI->getMaxLaneMaskForVReg(Ins.RegUnit))
+      RegWithLaneMask[Ins.RegUnit].push_back(Ins.LaneMask);
+  }
+  for (const auto &Outs : DAG->getOutRegs()) {
+    if (!Outs.LaneMask.all() &&
+        Outs.LaneMask != MRI->getMaxLaneMaskForVReg(Outs.RegUnit))
+      RegWithLaneMask[Outs.RegUnit].push_back(Outs.LaneMask);
+  }
+  // Since we ignored when the lane mask was getMaxLaneMaskForVReg,
+  // we need to add it back. It doesn't hurt if there was no element
+  // with this mask for this register.
+  for (auto &RegLaneMasks : RegWithLaneMask) {
+    RegLaneMasks.second.push_back(MRI->getMaxLaneMaskForVReg(RegLaneMasks.first));
+  }
+
+  for (const auto &RegLaneMasks : RegWithLaneMask) {
+    SmallVector<LaneBitmask, 8> &LaneBasis =
+      LaneMaskBasisForReg[RegLaneMasks.first];
+    for (const LaneBitmask &LaneMask : RegLaneMasks.second) {
+      LaneBitmask Remaining = LaneMask;
+      for (SmallVector<LaneBitmask, 8>::iterator I = LaneBasis.begin();
+           I != LaneBasis.end(); ++I) {
+        LaneBitmask Elem = *I;
+        if ((Remaining & Elem).none())
+          continue;
+        if ((Remaining & Elem) == Elem) {
+          Remaining &= ~Elem;
+          continue;
+        }
+        // Remaining intersects with Elem, but Elem is not
+        // included in remaining. We divide Elem into two elements.
+        // The one included in Remaining, and the rest.
+        LaneBitmask NewElem = Elem & ~Remaining;
+        *I = Elem & Remaining;
+        LaneBasis.push_back(NewElem);
+      }
+      if (Remaining.any())
+        LaneBasis.push_back(Remaining);
+    }
+  }
+
+  for (unsigned i = 0, e = Blocks.size(); i != e; ++i) {
+    SIScheduleBlock *Block = Blocks[i];
+    InRegsForBlock[i] = getPairsForRegs(Block->getInRegs());
+    OutRegsForBlock[i] = getPairsForRegs(Block->getOutRegs());
+  }
+
   // Fill the usage of every output
   // Warning: while by construction we always have a link between two blocks
   // when one needs a result from the other, the number of users of an output

   LiveOutRegsNumUsages.resize(Blocks.size());
   for (unsigned i = 0, e = Blocks.size(); i != e; ++i) {
     SIScheduleBlock *Block = Blocks[i];
-    for (unsigned Reg : Block->getInRegs()) {
+    for (const auto &RegPair : InRegsForBlock[i]) {
       bool Found = false;
       int topoInd = -1;
       for (SIScheduleBlock* Pred: Block->getPreds()) {
-        std::set<unsigned> PredOutRegs = Pred->getOutRegs();
-        std::set<unsigned>::iterator RegPos = PredOutRegs.find(Reg);
-
-        if (RegPos != PredOutRegs.end()) {
+        const SmallVector<RegisterMaskPair, 8> &PredOutRegs =
+          OutRegsForBlock[Pred->getID()];
+        for (const auto &RegPair2 : PredOutRegs) {
+          if (RegPair == RegPair2) {
             Found = true;
             if (topoInd < BlocksStruct.TopDownBlock2Index[Pred->getID()]) {
               topoInd = BlocksStruct.TopDownBlock2Index[Pred->getID()];
+            }
+            break;
           }
         }
       }
 
       if (!Found)
-        continue;
-
-      int PredID = BlocksStruct.TopDownIndex2Block[topoInd];
-      ++LiveOutRegsNumUsages[PredID][Reg];
+        // Fill LiveRegsConsumers for regs that were already
+        // defined before scheduling.
+        ++LiveRegsConsumers[RegPair];
+      else {
+        int PredID = BlocksStruct.TopDownIndex2Block[topoInd];
+        ++LiveOutRegsNumUsages[PredID][RegPair];
+      }
     }
   }
 

   }
 #endif
 
-  std::set<unsigned> InRegs = DAG->getInRegs();
+  SmallVector<RegisterMaskPair, 8> InRegs = getPairsForRegs(DAG->getInRegs());
   addLiveRegs(InRegs);
 
   // Increase LiveOutRegsNumUsages for blocks
   // producing registers consumed in another
   // scheduling region.
-  for (unsigned Reg : DAG->getOutRegs()) {
+  for (const RegisterMaskPair &RegPair : getPairsForRegs(DAG->getOutRegs())) {
     for (unsigned i = 0, e = Blocks.size(); i != e; ++i) {
       // Do reverse traversal
+      bool Found = false;
       int ID = BlocksStruct.TopDownIndex2Block[Blocks.size()-1-i];
       SIScheduleBlock *Block = Blocks[ID];
-      const std::set<unsigned> &OutRegs = Block->getOutRegs();
-
-      if (OutRegs.find(Reg) == OutRegs.end())
-        continue;
+      const SmallVector<RegisterMaskPair, 8> &OutRegs =
+        OutRegsForBlock[Block->getID()];
 
-      ++LiveOutRegsNumUsages[ID][Reg];
-      break;
-    }
-  }
-
-  // Fill LiveRegsConsumers for regs that were already
-  // defined before scheduling.
-  for (unsigned i = 0, e = Blocks.size(); i != e; ++i) {
-    SIScheduleBlock *Block = Blocks[i];
-    for (unsigned Reg : Block->getInRegs()) {
-      bool Found = false;
-      for (SIScheduleBlock* Pred: Block->getPreds()) {
-        std::set<unsigned> PredOutRegs = Pred->getOutRegs();
-        std::set<unsigned>::iterator RegPos = PredOutRegs.find(Reg);
-
-        if (RegPos != PredOutRegs.end()) {
+      for (const auto &RegPair2 : OutRegs) {
+        if (RegPair == RegPair2) {
           Found = true;
           break;
         }
       }
 
       if (!Found)
-        ++LiveRegsConsumers[Reg];
+        continue;
+
+      ++LiveOutRegsNumUsages[ID][RegPair];
+      break;
     }
   }
 

   );
 }
 
+SmallVector<RegisterMaskPair, 8>
+SIScheduleBlockScheduler::getPairsForReg(unsigned Reg, LaneBitmask Mask)
+{
+  SmallVector<RegisterMaskPair, 8> Result;
+
+  getPairsForReg(Result, Reg, Mask);
+
+  return Result;
+}
+
+void
+SIScheduleBlockScheduler::getPairsForReg(SmallVector<RegisterMaskPair, 8> &ToAppend,
+                                         unsigned Reg, LaneBitmask Mask)
+{
+  auto Basis = LaneMaskBasisForReg.find(Reg);
+  if (Basis == LaneMaskBasisForReg.end()) {
+    assert(Mask.all() || Mask == DAG->getMRI()->getMaxLaneMaskForVReg(Reg));
+    // We want unicity of the RegisterMaskPair for a same register/mask
+    // Thus replace getMaxLaneMaskForVReg by all, since they have the same
+    // meaning.
+    // Note: Physical registers have Mask.all(), but are disallowed
+    // to call getMaxLaneMaskForVReg.
+    if (!Mask.all() && Mask == DAG->getMRI()->getMaxLaneMaskForVReg(Reg))
+      Mask = LaneBitmask::getAll();
+    ToAppend.push_back(RegisterMaskPair(Reg, Mask));
+  } else {
+    for (const auto &Elem : Basis->second) {
+      if ((Mask & Elem).any()) {
+        assert((Mask & Elem) == Elem);
+        ToAppend.push_back(RegisterMaskPair(Reg, Elem));
+        Mask &= ~Elem;
+      }
+    }
+    // Mask.all will have a non-none value.
+    // We want Mask.all equivalent to the max lane mask.
+    assert((Mask & DAG->getMRI()->getMaxLaneMaskForVReg(Reg)).none());
+  }
+}
+
+SmallVector<RegisterMaskPair, 8>
+SIScheduleBlockScheduler::getPairsForRegs(const SmallVector<RegisterMaskPair, 8> &Regs)
+{
+  SmallVector<RegisterMaskPair, 8> Result;
+
+  std::for_each(Regs.begin(), Regs.end(),
+                [&](const RegisterMaskPair &RegPair){
+                  getPairsForReg(Result, RegPair.RegUnit,
+                                 RegPair.LaneMask);
+                });
+
+  return Result;
+}
+
 bool SIScheduleBlockScheduler::tryCandidateLatency(SIBlockSchedCandidate &Cand,
                                                    SIBlockSchedCandidate &TryCand) {
   if (!Cand.isValid()) {

     for (SIScheduleBlock* Block : ReadyBlocks)
       dbgs() << Block->getID() << ' ';
     dbgs() << "\nCurrent Live:\n";
-    for (unsigned Reg : LiveRegs)
-      dbgs() << PrintVRegOrUnit(Reg, DAG->getTRI()) << ' ';
+    for (const auto &RegPair : LiveRegs) {
+      dbgs() << PrintVRegOrUnit(RegPair.first, DAG->getTRI());
+      if (!RegPair.second.all())
+        dbgs() << ':' << PrintLaneMask(RegPair.second);
+     dbgs() << ' ';
+    }
     dbgs() << '\n';
     dbgs() << "Current VGPRs: " << VregCurrentUsage << '\n';
     dbgs() << "Current SGPRs: " << SregCurrentUsage << '\n';

   for (std::vector<SIScheduleBlock*>::iterator I = ReadyBlocks.begin(),
        E = ReadyBlocks.end(); I != E; ++I) {
     SIBlockSchedCandidate TryCand;
+    unsigned TryCandID;
+    int SGPRUsageDiff;
+
     TryCand.Block = *I;
+    TryCandID = TryCand.Block->getID();
     TryCand.IsHighLatency = TryCand.Block->isHighLatencyBlock();
-    TryCand.VGPRUsageDiff =
-      checkRegUsageImpact(TryCand.Block->getInRegs(),
-                          TryCand.Block->getOutRegs())[DAG->getVGPRSetID()];
+    checkRegUsageImpact(TryCandID, TryCand.VGPRUsageDiff, SGPRUsageDiff);
     TryCand.NumSuccessors = TryCand.Block->getSuccs().size();
     TryCand.NumHighLatencySuccessors =
       TryCand.Block->getNumHighLatencySuccessors();
     TryCand.LastPosHighLatParentScheduled =
       (unsigned int) std::max<int> (0,
-         LastPosHighLatencyParentScheduled[TryCand.Block->getID()] -
+         LastPosHighLatencyParentScheduled[TryCandID] -
            LastPosWaitedHighLatency);
     TryCand.Height = TryCand.Block->Height;
     // Try not to increase VGPR usage too much, else we may spill.

 
 // Tracking of currently alive registers to determine VGPR Usage.
 
-void SIScheduleBlockScheduler::addLiveRegs(std::set<unsigned> &Regs) {
-  for (unsigned Reg : Regs) {
+void SIScheduleBlockScheduler::addLiveRegs(SmallVector<RegisterMaskPair, 8> &Regs) {
+  for (const RegisterMaskPair &RegPair : Regs) {
+    unsigned Reg = RegPair.RegUnit;
     // For now only track virtual registers.
     if (!TargetRegisterInfo::isVirtualRegister(Reg))
       continue;
-    // If not already in the live set, then add it.
-    (void) LiveRegs.insert(Reg);
+
+    LiveRegs[Reg] |= RegPair.LaneMask;
   }
 }
 
 void SIScheduleBlockScheduler::decreaseLiveRegs(SIScheduleBlock *Block,
-                                       std::set<unsigned> &Regs) {
-  for (unsigned Reg : Regs) {
+                                                SmallVector<RegisterMaskPair, 8> &Regs) {
+  for (const RegisterMaskPair &RegPair : Regs) {
     // For now only track virtual registers.
-    std::set<unsigned>::iterator Pos = LiveRegs.find(Reg);
+    std::map<unsigned, LaneBitmask>::iterator Pos = LiveRegs.find(RegPair.RegUnit);
     assert (Pos != LiveRegs.end() && // Reg must be live.
-               LiveRegsConsumers.find(Reg) != LiveRegsConsumers.end() &&
-               LiveRegsConsumers[Reg] >= 1);
-    --LiveRegsConsumers[Reg];
-    if (LiveRegsConsumers[Reg] == 0)
-      LiveRegs.erase(Pos);
+            LiveRegsConsumers.find(RegPair) != LiveRegsConsumers.end() &&
+            LiveRegsConsumers[RegPair] >= 1);
+    --LiveRegsConsumers[RegPair];
+    if (LiveRegsConsumers[RegPair] == 0) {
+      if (Pos->second == RegPair.LaneMask)
+        LiveRegs.erase(Pos);
+      else
+        Pos->second &= ~RegPair.LaneMask;
+    }
   }
 }
 

 }
 
 void SIScheduleBlockScheduler::blockScheduled(SIScheduleBlock *Block) {
-  decreaseLiveRegs(Block, Block->getInRegs());
-  addLiveRegs(Block->getOutRegs());
+  unsigned ID = Block->getID();
+  decreaseLiveRegs(Block, InRegsForBlock[ID]);
+  addLiveRegs(OutRegsForBlock[ID]);
   releaseBlockSuccs(Block);
-  for (std::map<unsigned, unsigned>::iterator RegI =
-       LiveOutRegsNumUsages[Block->getID()].begin(),
-       E = LiveOutRegsNumUsages[Block->getID()].end(); RegI != E; ++RegI) {
-    std::pair<unsigned, unsigned> RegP = *RegI;
+  for (std::map<RegisterMaskPair, unsigned>::iterator RegI =
+       LiveOutRegsNumUsages[ID].begin(),
+       E = LiveOutRegsNumUsages[ID].end(); RegI != E; ++RegI) {
+    std::pair<RegisterMaskPair, unsigned> RegP = *RegI;
     // We produce this register, thus it must not be previously alive.
     assert(LiveRegsConsumers.find(RegP.first) == LiveRegsConsumers.end() ||
            LiveRegsConsumers[RegP.first] == 0);
     LiveRegsConsumers[RegP.first] += RegP.second;
   }
-  if (LastPosHighLatencyParentScheduled[Block->getID()] >
+  if (LastPosHighLatencyParentScheduled[ID] >
         (unsigned)LastPosWaitedHighLatency)
     LastPosWaitedHighLatency =
-      LastPosHighLatencyParentScheduled[Block->getID()];
+      LastPosHighLatencyParentScheduled[ID];
   ++NumBlockScheduled;
 }
 
-std::vector<int>
-SIScheduleBlockScheduler::checkRegUsageImpact(std::set<unsigned> &InRegs,
-                                     std::set<unsigned> &OutRegs) {
-  std::vector<int> DiffSetPressure;
-  DiffSetPressure.assign(DAG->getTRI()->getNumRegPressureSets(), 0);
+void
+SIScheduleBlockScheduler::checkRegUsageImpact(unsigned BlockID,
+                                              int &DiffVGPR,
+                                              int &DiffSGPR) {
+  SmallDenseMap<unsigned, LaneBitmask> Map;
+  SmallPtrSet<unsigned, 8> Set;
+  unsigned VGPRSetID = DAG->getVGPRSetID();
+  unsigned SGPRSetID = DAG->getSGPRSetID();
 
-  for (unsigned Reg : InRegs) {
+  DiffVGPR = 0;
+  DiffSGPR = 0;
+
+  for (const auto &RegPair : InRegsForBlock[BlockID]) {
     // For now only track virtual registers.
+    unsigned Reg = RegPair.RegUnit;
     if (!TargetRegisterInfo::isVirtualRegister(Reg))
       continue;
-    if (LiveRegsConsumers[Reg] > 1)
+
+    if (LiveRegsConsumers[RegPair] > 1)
       continue;
-    PSetIterator PSetI = DAG->getMRI()->getPressureSets(Reg);
-    for (; PSetI.isValid(); ++PSetI) {
-      DiffSetPressure[*PSetI] -= PSetI.getWeight();
+    Map[Reg] |= RegPair.LaneMask;
+  }
+
+  for (const auto &RegPair : Map) {
+    if (LiveRegs[RegPair.first] == RegPair.second) {
+      PSetIterator PSetI = DAG->getMRI()->getPressureSets(RegPair.first);
+      for (; PSetI.isValid(); ++PSetI) {
+        if (*PSetI == VGPRSetID)
+          DiffVGPR -= PSetI.getWeight();
+        if (*PSetI == SGPRSetID)
+          DiffSGPR -= PSetI.getWeight();
+      }
     }
   }
 
-  for (unsigned Reg : OutRegs) {
+  for (const auto &RegPair : OutRegsForBlock[BlockID]) {
     // For now only track virtual registers.
+    unsigned Reg = RegPair.RegUnit;
     if (!TargetRegisterInfo::isVirtualRegister(Reg))
       continue;
-    PSetIterator PSetI = DAG->getMRI()->getPressureSets(Reg);
-    for (; PSetI.isValid(); ++PSetI) {
-      DiffSetPressure[*PSetI] += PSetI.getWeight();
-    }
+
+    Set.insert(Reg);
   }
 
-  return DiffSetPressure;
+  for (unsigned Reg : Set) {
+    // Check register is not already alive (at least some lanes)
+    if (LiveRegs.find(Reg) == LiveRegs.end()) {
+      PSetIterator PSetI = DAG->getMRI()->getPressureSets(Reg);
+      for (; PSetI.isValid(); ++PSetI) {
+        if (*PSetI == VGPRSetID)
+          DiffVGPR += PSetI.getWeight();
+        if (*PSetI == SGPRSetID)
+          DiffSGPR += PSetI.getWeight();
+      }
+    }
+  }
 }
 
 // SIScheduler //

   VgprUsage = 0;
   SgprUsage = 0;
   for (_Iterator RegI = First; RegI != End; ++RegI) {
-    unsigned Reg = *RegI;
+    unsigned Reg = RegI->first;
     // For now only track virtual registers
     if (!TargetRegisterInfo::isVirtualRegister(Reg))
       continue;