How to update LiveInterval information of newly inserted machine basic block

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

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();

  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

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

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

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

-Andy

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

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

Yes, I should think so.

/jakob

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

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

-Andy

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

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

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.

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

-Andy

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?

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

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