[LLVMdev] How to update LiveInterval information of newly inserted machine basic block

[Haishan]

Hi,

  I insert a new machine basic block(MBB) before Greedy Register Allocation, after Simple Register Coalescing. But I encounter a fatal 

error "regalloc = ... not currently supported with -O0". I use command line with opt level O2, not O0.

The probable reason of this error is that no LiveInterval information for newly MBB which is used by Register Allocation.

And, LiveIntervals depend on LiveVariables which require the machine function to be in SSA form.

However, in this case, the modified machine function(including newly inserted MBB) is not SSA form any more.

So, how to update LiveInterval information of newly MBB?

Could someone help me with that?

Thank you very much in advance.

-Haishan

[Andrew Trick]

Yes, I think error that means LiveIntervals have been invalidated. It is supposed to be user-friendly but should probably be changed to be more specific.

If you schedule a new pass between coalescing and regalloc, it needs to preserve LiveIntervals analysis. There are utilities to recompute live intervals for individual virtual registers. See LiveIntervals::computeVirtRegs. LiveVariables is not actually needed to update live intervals. It is only added as a requirement to make sure it runs before the 2-address pass.

-Andy

_______________________________________________
LLVM Developers mailing list
LLV...@cs.uiuc.edu         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

[Haishan]

At 2014-01-01 04:36:21,"Andrew Trick" <atr...@apple.com> wrote:

On Dec 31, 2013, at 3:52 AM, Haishan <hnd...@163.com> wrote:

Hi,

  I insert a new machine basic block(MBB) before Greedy Register Allocation, after Simple Register Coalescing. But I encounter a fatal 

error "regalloc = ... not currently supported with -O0". I use command line with opt level O2, not O0.

The probable reason of this error is that no LiveInterval information for newly MBB which is used by Register Allocation.

And, LiveIntervals depend on LiveVariables which require the machine function to be in SSA form.

However, in this case, the modified machine function(including newly inserted MBB) is not SSA form any more.

So, how to update LiveInterval information of newly MBB?

Could someone help me with that?

Thank you very much in advance.

-Haishan

Yes, I think error that means LiveIntervals have been invalidated. It is supposed to be user-friendly but should probably be changed to be more specific.

If you schedule a new pass between coalescing and regalloc, it needs to preserve LiveIntervals analysis. There are utilities to recompute live intervals for individual virtual registers. See LiveIntervals::computeVirtRegs. LiveVariables is not actually needed to update live intervals. It is only added as a requirement to make sure it runs before the 2-address pass.

-Andy

  Thank you for your reply.

  I do it as you tell me, and you are right.

  My update steps are shown following:

  LiveIntervals *LIS = &getAnalysis<LiveIntervals>();

    1. LIS->insertMBBInMaps(NewMBB)

    2. LIS->InsertMachineInstrRangeInMaps(NewMBB->begin(), NewMBB->end())

    3. Due to some machine instructions of NewMBB copy from OldMBB, I have to removeInterval firstly. Then I use LIS->createAndComputeVirtRegInterval() to update LiveInterval info of NewMBB.

    4. Then I want to delete OldMBB in the current MachineFuncion. At the same time, delete LiveIntervals info of OldMBB. So, firstly, Use RemoveMachineInstrFromMaps() to erase SlotIndexes info of OldMBB. And, delete OldMBB from current CFG. Lastly, remove all registers' interval, create and recompute virtual register interval info.

  However, I get an unreachable error "Use not jointly dominated by defs" in LiveRangeCalc.cpp:188.

So, comparing with Step3, Step4 generates an unreachable error, Why?

  Valid information of OldMBB is deleted when updating CFG? Is there something wrong with my updating steps?

  Thank you very much again.

  -Haishan

[Andrew Trick]

I’m haven’t done anything like this so I can only guess.

The error means that some path from function entry does not provide a reaching def for a vreg. You’ll have to analyze the CFG and debug to understand why.

My suggestion would be to completely update the CFG first, with no connections to the old block. Remove the old block, it’s instructions and vregs from maps. Then add the new block to maps and recompute.

You might need to keep track of any vregs referenced in the old block but not in the new block to ensure they are updated.

Hope it works.

-Andy

[Jakob Stoklund Olesen]

Those LIS->insert…() functions are only proxies for the corresponding functions on SlotIndexes. They only add the necessary slot indexes, they don’t update any liveness information.

We don’t have any support for updating liveness after inserting a new basic block. There is no reason you couldn’t do it, but the code doesn’t exist.

Thanks,

/jakob

[Andrew Trick]

Haishan is using createAndComputeVirtRegInterval for each vreg. I guess this should work if removeInterval is called first.

-Andy

[Jakob Stoklund Olesen]

The problem is with all the other virtual registers in the function. You need to decide if they are live through the new block or not. That isn’t computed automatically.

Thanks,

/jakob

[Andrew Trick]

He really just wants to rerun LiveIntervals analysis, but LiveVariables is no longer available. Would it work just to clear all the intervals rerun LiveIntervals::computeVirtRegs after all the CFG transforms are complete?

-Andy

[Jakob Stoklund Olesen]

On Jan 3, 2014, at 1:52 PM, Andrew Trick <atr...@apple.com> wrote:

He really just wants to rerun LiveIntervals analysis, but LiveVariables is no longer available. Would it work just to clear all the intervals rerun LiveIntervals::computeVirtRegs after all the CFG transforms are complete?

Yes, I should think so.

/jakob

[Haishan]

Thank you very much for your talk.

I think I could append more information about updating LiveIntervals.

1. It works well if I just use from step1 to step3, without step4.

2. In step4, I firstly use UnreachableBlockElim pass to delete OldMBB.

Then, remove all intervals and recompute all the virtual registers' LiveIntervals.

3. I debug source code in LiveRangeCalc.cpp and copy partial code shown following.

/// LiveRangeCalc.cpp

...

#ifndef NDEBUG

    if (MBB->pred_empty()) {

      MBB->getParent()->verify();

      llvm_unreachable("Use not jointly dominated by defs.");

    }

...

/// LiveRangeCalc.cpp

This MBB is the first block of MachineFunction. That's to say, This MBB doesn't have predecessor. It is reasonable?

From debug information, this unreachable error is generated from recompute a virtual register which isn't used or defined in this MBB. But this virtual register, in NewMBB,  is defined in a machine instruction which is copied from OldMBB.

So I am puzzled. 

Then, I do as Andy's suggestion, but it doesn't work, and it has same error.

Could you have any suggestion?

Thank you very much again.

-Haishan

[Andrew Trick]

Incrementally updating the live intervals will be complicated. You may be able to completely recompute them by clearing all VirtRegIntervals, then calling computeVirtRegs.

-Andy

[Haishan]

Hi, 

  Thank you very much for replying.

  I have some doubt about only using computeVirtRegs function to update LiveInterval.

  There are two other functions like "computeRegMasks() computeLiveInRegUnits()" in runOnMachineFunction of LiveIntervalAnalysis.cpp.

  So, I think that these two functions maybe effect updating LiveInterval information.

  What do you think of two functions?

  

  Thank you very much again.

  -Haishan

[Andrew Trick]

Yes, the safest thing would be to effectively rerun the LiveIntervals pass. After finishing your CFG changes, You could try:

  releaseMemory()

  VirtRegIntervals.resize(MRI->getNumVirtRegs());

  computeVirtRegs();

  computeRegMasks();

  computeLiveInRegUnits();

I haven't tried this myself, so you may need to experiment/debug.

-Andy

[Haishan]

Hi, Andy

  Thank you very much for help.

  I have debugged the llvm_unreachable error. The main reason of this error is that SlotIndexes info of OldMBB is not deleted completely after deleting OldMBB and updating CFG.

  So, I do it as your suggestion, clear SlotIndexes and LiveIntervals firstly by calling releaseMemory, then rerun SlotIndexes and LiveIntervals Analysis. 

  It works well.

  Thank you very much for your help.

  

  -Haishan