Speed up creation of live ranges for physical registers by using a segment set

[gasiunas]

Summary

The patch addresses a compile-time performance regression in the LiveIntervals analysis pass (see http://llvm.org/bugs/show_bug.cgi?id=18580). This regression is especially critical when compiling long functions. Our analysis had shown that the most of time is taken for generation of live intervals for physical registers. Insertions in the middle of the array of live ranges cause quadratic algorithmic complexity, which is apparently the main reason for the slow-down.

Overview of changes:

• The patch introduces an additional std::set<Segment>* member in LiveRange for storing segments in the phase of initial creation. The set is used if this member is not NULL, otherwise everything works the old way.
• The set of operations on LiveRange used during initial creation (i.e. used by createDeadDefs and extendToUses) have been reimplemented to use the segment set if it is available.
• After a live range is created the contents of the set are flushed to the segment vector, because the set is not as efficient as the vector for the later uses of the live range. After the flushing, the set is deleted and cannot be used again.
• The set is only for live ranges computed in LiveIntervalAnalysis::computeLiveInRegUnits() and getRegUnit() but not in computeVirtRegs(), because I did not bring any performance benefits to computeVirtRegs() and for some examples even brought a slow down.

[echristo]

Couple of questions:

a) Compile time results?
b) Why didn't it help/produce a slowdown for computeVirtRegs?
c) What's the slowdown look like for using it all the time? Is it because we're using find instead of set::upper_bound? Where are we running into issues?
d) It seems like we're duplicating a lot of code to do this, is there any way you can think of to remove that duplication here?

Couple of clean up comments:

a) Comments are a full sentence including captialization.
b) Pull the asserts out of the else blocks.
c) Single statement blocks shouldn't have braces.

-eric

[qcolombet]

Hi Vaidas,

I share Eric’s concerns/questions.
In particular, I think we should put more effort to reduce the amount of code we duplicate here. I gave some thoughts in the inlined comments.

Also, I think for performance evaluation it would be nice to be able to use or not use it every with a command line option. That would help to figure out what is the problem with computeVirtRegs. Moreover that would allow to completely disable it if we believe it has some problem.

After a live range is created the contents of the set are flushed to the segment vector, because the set is not as efficient as the vector for the later uses of the live range. After the flushing, the set is deleted and cannot be used again.

If we really want to use the set internally like this, we shouldn’t expose the createSegmentSet method in the public API. Therefore, I think we should try to completely expose this interface. I have thrown some ideas in the inlined comments.

Thanks for working on this!
-Quentin

include/llvm/CodeGen/LiveInterval.h

200

LLVM policy is to use variable names that start with a capital letter.
That said, the surrounded code already use such a naming convention, so I’d say it is fine.
Anyway, the formatting is not right, because ‘*’ should be with the variable name.

Use clang-format on your patch, please.

202

Use nullptr.

206

You do not need to check for NULL before calling delete.

456

Use nullptr (or nothing).

585

Typo: of/ => of

lib/CodeGen/LiveInterval.cpp

513

I believe this shouldn’t be necessary with some abstractions.
See LiveRange::segsetExtendInBlock.

770

Please do not use else after return: http://llvm.org/docs/CodingStandards.html#don-t-use-else-after-a-return

782

Please try to share this code between the vector and the set versions.
You could stick to the existing implementation (with some abstract on the iterator type) and use an abstraction for the final insertion for instance.

816

Same thing as segsetCreateDeadDef, you should share more logic between the implementations.
For instance, you could abstract begin(), upper_bound(), empty() and you should be able to reuse all the code.

837

Ditto.
Abstract end(), erase().

1156

Is this code path used during createDeadDefs and extendToUses?

lib/CodeGen/LiveIntervalAnalysis.cpp

315

I would prefer this to be an internal detail of the constructor of LiveRange.

332

What about pushing the flush into computeRegUnitRange?

Even better, could we automatically decide when to do the flush internally in the LiveRange class? E.g., the first time we actually need the vector capabilities.
That would remove this kind of explicit calls to flush that are easy to forget or misplace.

[gasiunas]

Hi Eric and Quentin,

Thanks for the comments! At first, I will give some info on performance.

To measure compliation time I used an example generated by the script from http://llvm.org/bugs/show_bug.cgi?id=18580 with the parameter 10000. This generates a C program with 10000 string objects and 10000 small if statements using these variables. The C program is compiled to IR by clang. This IR I then use to measure the compilation time of llc. I run llc with -01 to skip the optimization passes.

So with this example, the original llc runs about 19s and the llc with the patch runs about 10s.

Here is the result of profiling the llc without the patch (exported as CSV from vtune):
"Function Stack","CPU Time: Total by Utilization","CPU Time: Self by Utilization","Overhead and Spin Time: Total","Overhead and Spin Time: Self","Module","Function (Full)","Source File","Start Address"
" llvm::FPPassManager::runOnFunction","18.55","0","0","0","llc-no","llvm::FPPassManager::runOnFunction(llvm::Function&)","","0x1366d50"
" llvm::LiveIntervals::runOnMachineFunction","9.07199","0","0","0","llc-no","llvm::LiveIntervals::runOnMachineFunction(llvm::MachineFunction&)","","0xe8cb00"
" llvm::LiveIntervals::computeLiveInRegUnits","8.95999","0","0","0","llc-no","llvm::LiveIntervals::computeLiveInRegUnits(void)","","0xe8a1a0"
" llvm::LiveIntervals::computeRegUnitRange","8.95999","0","0","0","llc-no","llvm::LiveIntervals::computeRegUnitRange(llvm::LiveRange&, unsigned int)","","0xe89fd0"
" llvm::LiveRangeCalc::extendToUses","4.77199","0.0180017","0","0","llc-no","llvm::LiveRangeCalc::extendToUses(llvm::LiveRange&, unsigned int)","","0xe94640"
" llvm::LiveRangeCalc::extend","4.75399","0.00799807","0","0","llc-no","llvm::LiveRangeCalc::extend(llvm::LiveRange&, llvm::SlotIndex, unsigned int)","","0xe94420"
" llvm::LiveRange::extendInBlock","4.74599","0.0199952","0","0","llc-no","llvm::LiveRange::extendInBlock(llvm::SlotIndex, llvm::SlotIndex)","","0xe85f60"
" llvm::LiveRange::extendSegmentEndTo","4.726","4.726","0","0","llc-no","llvm::LiveRange::extendSegmentEndTo(llvm::LiveRange::Segment*, llvm::SlotIndex)","","0xe84a30"
" llvm::LiveRangeCalc::createDeadDefs","4.18799","0.0279962","0","0","llc-no","llvm::LiveRangeCalc::createDeadDefs(llvm::LiveRange&, unsigned int)","","0xe91650"
" llvm::LiveRange::createDeadDef","4.16","4.128","0","0","llc-no","llvm::LiveRange::createDeadDef(llvm::SlotIndex, llvm::BumpPtrAllocatorImpl<llvm::MallocAllocator, (unsigned long)4096, (unsigned long)4096>&)","","0xe880a0"
" llvm::LiveRange::find","0.0319956","0.0319956","0","0","llc-no","llvm::LiveRange::find(llvm::SlotIndex)","","0xe84530"
" llvm::LiveIntervals::computeVirtRegs","0.0920017","0","0","0","llc-no","llvm::LiveIntervals::computeVirtRegs(void)","","0xe8c9e0"
" llvm::LiveIntervals::computeVirtRegInterval","0.0840081","0","0","0","llc-no","llvm::LiveIntervals::computeVirtRegInterval(llvm::LiveInterval&)","","0xe8a6a0"
" llvm::LiveRangeCalc::reset","0.0440009","0.0440009","0","0","llc-no","llvm::LiveRangeCalc::reset(llvm::MachineFunction const*, llvm::SlotIndexes*, llvm::MachineDominatorTree*, llvm::BumpPtrAllocatorImpl<llvm::MallocAllocator, (unsigned long)4096, (unsigned long)4096>*)","","0xe94ba0"
" llvm::LiveRangeCalc::extendToUses","0.0320052","0.0320052","0","0","llc-no","llvm::LiveRangeCalc::extendToUses(llvm::LiveRange&, unsigned int)","","0xe94640"
" llvm::LiveRangeCalc::createDeadDefs","0.00800203","0","0","0","llc-no","llvm::LiveRangeCalc::createDeadDefs(llvm::LiveRange&, unsigned int)","","0xe91650"
" llvm::LiveIntervals::createInterval","0.00799364","0.00799364","0","0","llc-no","llvm::LiveIntervals::createInterval(unsigned int)","","0xe89f40"
" llvm::LiveIntervals::computeRegMasks","0.02","0.02","0","0","llc-no","llvm::LiveIntervals::computeRegMasks(void)","","0xe8b720"
" llvm::SelectionDAGISel::runOnMachineFunction","4.08","0.0160085","0","0","llc-no","llvm::SelectionDAGISel::runOnMachineFunction(llvm::MachineFunction&)","","0xd60d50"
" (anonymous namespace)::MachineBlockPlacement::runOnMachineFunction","1.77799","0","0","0","llc-no","(anonymous namespace)::MachineBlockPlacement::runOnMachineFunction(llvm::MachineFunction&)","","0xebb050"
" llvm::LiveVariables::runOnMachineFunction","0.370002","0","0","0","llc-no","llvm::LiveVariables::runOnMachineFunction(llvm::MachineFunction&)","","0xea1610"

Here is the profiler result of the llc with the patch:
"Function Stack","CPU Time: Total by Utilization","CPU Time: Self by Utilization","Overhead and Spin Time: Total","Overhead and Spin Time: Self","Module","Function (Full)","Source File","Start Address"
" llvm::FPPassManager::runOnFunction","9.72","0","0","0","llc-pr","llvm::FPPassManager::runOnFunction(llvm::Function&)","","0x1367190"
" llvm::SelectionDAGISel::runOnMachineFunction","4.08","0.0320187","0","0","llc-pr","llvm::SelectionDAGISel::runOnMachineFunction(llvm::MachineFunction&)","","0xd60e80"
" (anonymous namespace)::MachineBlockPlacement::runOnMachineFunction","1.57","0","0","0","llc-pr","(anonymous namespace)::MachineBlockPlacement::runOnMachineFunction(llvm::MachineFunction&)","","0xebb1e0"
" llvm::LiveVariables::runOnMachineFunction","0.378","0.0360253","0","0","llc-pr","llvm::LiveVariables::runOnMachineFunction(llvm::MachineFunction&)","","0xea17a0"
" (anonymous namespace)::VerifierLegacyPass::runOnFunction","0.29999","0.0160001","0","0","llc-pr","(anonymous namespace)::VerifierLegacyPass::runOnFunction(llvm::Function&)","","0x1392df0"
" llvm::LiveIntervals::runOnMachineFunction","0.267978","0","0","0","llc-pr","llvm::LiveIntervals::runOnMachineFunction(llvm::MachineFunction&)","","0xe8cc70"
" llvm::LiveIntervals::computeLiveInRegUnits","0.159983","0","0","0","llc-pr","llvm::LiveIntervals::computeLiveInRegUnits(void)","","0xe8a2e0"
" llvm::LiveIntervals::computeVirtRegs","0.0879867","0.0120113","0","0","llc-pr","llvm::LiveIntervals::computeVirtRegs(void)","","0xe8cb50"
" llvm::LiveIntervals::computeRegMasks","0.0200084","0.0200084","0","0","llc-pr","llvm::LiveIntervals::computeRegMasks(void)","","0xe8b890"
" (anonymous namespace)::MachineScheduler::runOnMachineFunction","0.25997","0","0","0","llc-pr","(anonymous namespace)::MachineScheduler::runOnMachineFunction(llvm::MachineFunction&)","","0xf074f0"
" llvm::MachineDominatorTree::runOnMachineFunction","0.255892","0","0","0","llc-pr","llvm::MachineDominatorTree::runOnMachineFunction(llvm::MachineFunction&)","","0xed3ca0"
" llvm::X86AsmPrinter::runOnMachineFunction","0.239961","0","0","0","llc-pr","llvm::X86AsmPrinter::runOnMachineFunction(llvm::MachineFunction&)","","0xb43390"
" (anonymous namespace)::MachineCSE::PerformCSE","0.219981","0.0440057","0","0","llc-pr","(anonymous namespace)::MachineCSE::PerformCSE(llvm::DomTreeNodeBase<llvm::MachineBasicBlock>*)","","0xec0620"
" (anonymous namespace)::RAGreedy::runOnMachineFunction","0.181984","0","0","0","llc-pr","(anonymous namespace)::RAGreedy::runOnMachineFunction(llvm::MachineFunction&)","","0xf4c440"
" llvm::SlotIndexes::runOnMachineFunction","0.144008","0.144008","0","0","llc-pr","llvm::SlotIndexes::runOnMachineFunction(llvm::MachineFunction&)","","0xf7f3f0"
" (anonymous namespace)::RegisterCoalescer::runOnMachineFunction","0.130013","0.0520054","0","0","llc-pr","(anonymous namespace)::RegisterCoalescer::runOnMachineFunction(llvm::MachineFunction&)","","0xf60390"
" (anonymous namespace)::StackColoring::runOnMachineFunction","0.128002","0.00800791","0","0","llc-pr","(anonymous namespace)::StackColoring::runOnMachineFunction(llvm::MachineFunction&)","","0xf914b0"

As you see, the optimization reduces the time of the LiveIntervals pass from 9s to 0.27s.

If I also activate the segment set in computeVirtRegInterval, then the time of the LiveIntervals pass goes slightly up to 0.32s. This difference is of course insignificant compared to the total time, but since this optimization is optional anyway, I don't see a reason why should we activate in computeVirtRegInterval.

Here is the profiler result for llc with the patch + segment set activated computeVirtRegInterval:
"Function Stack","CPU Time: Total by Utilization","CPU Time: Self by Utilization","Overhead and Spin Time: Total","Overhead and Spin Time: Self","Module","Function (Full)","Source File","Start Address"
" llvm::LiveIntervals::runOnMachineFunction","0.319991","0","0","0","llc-vr","llvm::LiveIntervals::runOnMachineFunction(llvm::MachineFunction&)","","0xe8cc80"
" llvm::LiveIntervals::computeLiveInRegUnits","0.167986","0","0","0","llc-vr","llvm::LiveIntervals::computeLiveInRegUnits(void)","","0xe8a2e0"
" llvm::LiveIntervals::computeRegUnitRange","0.147984","0","0","0","llc-vr","llvm::LiveIntervals::computeRegUnitRange(llvm::LiveRange&, unsigned int)","","0xe8a110"
" llvm::LiveRange::flushSegmentSet","0.0120047","0.0120047","0","0","llc-vr","llvm::LiveRange::flushSegmentSet(void)","","0xe86810"
" llvm::LiveRange::createDeadDef","0.00799748","0","0","0","llc-vr","llvm::LiveRange::createDeadDef(llvm::SlotIndex, llvm::BumpPtrAllocatorImpl<llvm::MallocAllocator, (unsigned long)4096, (unsigned long)4096>&)","","0xe881e0"
" llvm::LiveIntervals::computeVirtRegs","0.131992","0.0119954","0","0","llc-vr","llvm::LiveIntervals::computeVirtRegs(void)","","0xe8cb60"
" llvm::LiveIntervals::computeVirtRegInterval","0.0920111","0","0","0","llc-vr","llvm::LiveIntervals::computeVirtRegInterval(llvm::LiveInterval&)","","0xe8a810"
" llvm::LiveRangeCalc::createDeadDefs","0.0560275","0.0560275","0","0","llc-vr","llvm::LiveRangeCalc::createDeadDefs(llvm::LiveRange&, unsigned int)","","0xe917f0"
" llvm::LiveRangeCalc::extendToUses","0.0199875","0.00799175","0","0","llc-vr","llvm::LiveRangeCalc::extendToUses(llvm::LiveRange&, unsigned int)","","0xe947e0"
" llvm::LiveRangeCalc::reset","0.015996","0.015996","0","0","llc-vr","llvm::LiveRangeCalc::reset(llvm::MachineFunction const*, llvm::SlotIndexes*, llvm::MachineDominatorTree*, llvm::BumpPtrAllocatorImpl<llvm::MallocAllocator, (unsigned long)4096, (unsigned long)4096>*)","","0xe94d40"
" llvm::LiveRange::flushSegmentSet","0.0199879","0.0199879","0","0","llc-vr","llvm::LiveRange::flushSegmentSet(void)","","0xe86810"
" llvm::LiveIntervals::createInterval","0.00799796","0.00799796","0","0","llc-vr","llvm::LiveIntervals::createInterval(unsigned int)","","0xe8a080"
" llvm::LiveIntervals::computeRegMasks","0.0200124","0.0200124","0","0","llc-vr","llvm::LiveIntervals::computeRegMasks(void)","","0xe8b8a0"

My explanation of the performance differences is that the optimization is beneficial for very large live ranges with thousands of segments, because then insertion of new segments into the middle of the array is very expensive. For small live ranges using array is slightly more efficient that using set. However, in these cases LiveIntervals pass does not take much time anyway.

Vaidas

[gasiunas]

c) What's the slowdown look like for using it all the time? Is it because we're using find instead of set::upper_bound? Where are we running into issues?

I was experimenting with it almost a year ago, so I don't remember precisely which operations were slower. I think it was not lookup, but rather some range operations like splitting or merging of ranges, that work much faster with the array. Unfortunately, I cannot try out that again with the current patch, because now only the operations that are used in the initial computation of the live range are implemented for set.

d) It seems like we're duplicating a lot of code to do this, is there any way you can think of to remove that duplication here?

Yes I also don't like the code duplication. This was actually the reason why I hesitated to contribute that patch. I am open to suggestions.

b) Pull the asserts out of the else blocks.

Which ones do you mean? Note that most of the new code is a copy of analogous operations with vector.

Also, I think for performance evaluation it would be nice to be able to use or not use it every with a command line option. That would help to figure out what is the problem with computeVirtRegs. Moreover that would allow to completely disable it if we believe it has some problem.

Note that computeVirtRegs is not really a problem, it simply does not really need that optimization, but yes it makes sense to have an switch for the optimization as whole.

Vaidas

lib/CodeGen/LiveInterval.cpp

782

I don't see how it would work. Could you give some more details? Do you suggest having some adapter iterator wrapping one of the two iterators?

816

How can I abstract them, if the two iterator types are not compatible with each other?

1156

It is used in LiveRangeCalc::extendToUses through LiveRangeCalc::findReachingDefs

lib/CodeGen/LiveIntervalAnalysis.cpp

332

At first I put it to computeRegUnitRange, but I thought that is a more clear design if we have calls to createSegmentSet() and flushSegmentSet() at the same level.

Flushing automatically sounds good, I will try it out.

[qcolombet]

lib/CodeGen/LiveInterval.cpp

782

Yes something like that, or you can use a template argument for the iterator type. Though that can be messy quite quickly.

816

A new type on top of them, like you suggested ;).

1156

Ah right! Thanks.

[Gerolf]

include/llvm/CodeGen/LiveInterval.h

457

We don't repeat the function names in comments anymore.

include/llvm/CodeGen/LiveIntervalAnalysis.h

385

Since the focus is on speeding up computeRegUnitRange() is seems cleaner to handle both the segment set allocation and flushing locally within that function. This will also remove the asymmetry in your code where some calls are enclosed by createSegment() + flush(), while for others (ok, I only see one more) creation and flush are separate.

lib/CodeGen/LiveInterval.cpp

322

This is for the createDeadDef() call in computeRegUnitRange() only, right? Why not replace the call there directly with the call to the segmentSet function and remove this check?

511

Same as for createDeadDef().

766

I guess you could have templates for some of the segment set/segment utility routines if you wanted to push your design a bit. That would take care of some of the static code bloat.

1153

Hm. This looks like more changes than just adding a new data structure to handle live ranges calcs more efficiently. The existing updater checks for coalescing and spilling, while addSegment() does not. Please add a more detailed comment about the differences. Up until this point I was optimistic that the implementation could be cleaned up quite a bit, but now I'm not so sure anymore.

[gasiunas]

include/llvm/CodeGen/LiveIntervalAnalysis.h

385

The problem is that LiveIntervals::computeLiveInRegUnits calls createDeadDef before calling computeRegUnitRange.

lib/CodeGen/LiveInterval.cpp

322

Yes, I think it should work. That would simplify a bit.

766

Yes, templates is the only thing that comes to my mind for reduction of code repetition. Other techniques like object-oriented abstraction would be probably too heavyweight, because it is performance critical code. The problem with templates is however that they would introduce quite some additional complexity. I think I will need some helper classes for template instantiation. I will think about it.

1153

Are these coalescing and spilling checks also relevant for the LiveIntervals phase? Because in other cases, the segmentSet is not used.

[gasiunas]

• Implementations of createDeadDef, extendInBlock, addSegment are templatized to make them reusable for the segment set and the segment vector.
• The segment set is now created in LiveRange constructor, and flushSegmentSet is called in computeRegUnitRange
• Comments regarding coding style are addressed

[qcolombet]

Hi Vaidas,

Thanks for the refactoring, this is looking good!

I just have a couple of nitpicks (see inline comments) and one request:

• Could you add a cl::opt to override the use of segment set?

Thanks again,
-Quentin

include/llvm/CodeGen/LiveIntervalAnalysis.h

384

For debugging purposes, I would like we have a command line option to override this behavior.
This means we will have to update flushSegmentSet accordingly or not calling it when the option is false.

lib/CodeGen/LiveInterval.cpp

64

I believe this comment is out of date.

93

Ditto.

126

Using ’S' instead of ‘I' may be clearer here also it does not matter for correctness.
On a second thought, do we actually need S?

141

Ditto.

159

Do we really need to use segmentAt?
Couldn’t we use MergeTo directly?

163

Ditto.

233

Couldn’t this be a typedef?

260

Ditto.

324

Do not use else after return: http://llvm.org/docs/CodingStandards.html#don-t-use-else-after-a-return

490–507

Do not use else after return: http://llvm.org/docs/CodingStandards.html#don-t-use-else-after-a-return

513

Do not use else after return: http://llvm.org/docs/CodingStandards.html#don-t-use-else-after-a-return

1154

Capital letter and period to make a sentence.

lib/CodeGen/LiveIntervalAnalysis.cpp

314

For debugging purposes, I would like we have a command line option to override this behavior.
This means we will have to update flushSegmentSet accordingly or not calling it when the option is false.

[gasiunas]

• An option to turn-off use of the segment set for the computation of the live ranges of physregs.
• Various small changes addressing the comments of Quentin.

[gasiunas]

Hi Quentin,

Thanks a lot for the comments. I added the option to turn-off the optimization and fixed formatting and comments.

Best regards,
Vaidas

lib/CodeGen/LiveInterval.cpp

64

Indeed

126

The set iterator supports only const access to elements, therefore I need S = segmentAt(I) for const_cast.

Set iterators are read-only, because changing a set element may potentially affect is order in the set. Thus, we must be careful to change the segments in a way that preserves their order. Here it is no problem, because these algorithms were designed to take care of correct ordering.

233

Yes, it works. I just need to forward declare CalcLiveRangeUtilVector .

324

Done.

1154

Done

lib/CodeGen/LiveIntervalAnalysis.cpp

314

Done

[qcolombet]

Hi Vaidas,

LGTM.

Thanks,
-Quentin

[gasiunas]

Does anyone have further comments, or is the patch now ready to be merged?

Regards,
Vaidas

[atrick]

RubberStamp: I'm happy with the reviews and the code looks reasonable. Thanks reviewers.

[MatzeB]

Sorry for coming so late to the review, no need to address these issues before commit.

• Why is the SegmentSet part of the LiveRange? My understanding is that you only use it during initial live calculation anyway, and these calculations are done one another for each live range. So I'd assume it is enough to have the set as a member of the LiveRangeCalc class and not having an extra pointer in each LiveRange.
• for the createDeadDefs() part it may be interesting to simply append the new segments to the vector in any order and later run a sorting algorithm which also eliminates duplicates on the vector. This should reduce the O(n**2) complexity to O(n log n) and I'd imagine it to perform well in the case where only a few segments are used.
• It would be nice if the decision on whether to use the set or sorted vector based techniques could be based on the actual number of Defs/Uses of a register (deciding on whether it is a physreg seems a bit arbitrary to me although it's probably a good heuristic in practice). Unfortunately I don't see an easy way to determine the actual number of defs/uses for a vreg as that is only maintained as a double linked list without a counter at the moment, so it is probably okay as is.

[gasiunas]

Hi Matthias,

Thanks for your comments!

Why is the SegmentSet part of the LiveRange? My understanding is that you only use it during initial live calculation anyway, and these calculations are done one another for each live range. So I'd assume it is enough to have the set as a member of the LiveRangeCalc class and not having an extra pointer in each LiveRange.

At first I also thought that I could move the optimizations to LiveRangeCalc, but it is more difficult than it may appear. The methods addSegment and extendInBlock are used also outside the LiveRangeCalc, so I cannot move them completely out of LiveRange. Besides, the LiveRangeCalc is also used in the register allocation phase for splitting of live ranges. So we would need to maintain two modes of the algorithm in LiveRangeCalc in addition to a direct usage over LiveRange. Another difficulty is that the interface LiveRangeCalc is designed to work with multiple LiveRanges, so I cannot keep the segment set as a member of LiveRangeCalc, but rather pass it as an additional parameter from method to method. In some places the LiveRangeCalc uses the LiveRange indirectly over LiveRangeUpdater, so I would need to propagate the segment set to LiveRangeUpdater too or completely rewrite the code using the updater. It is all possible, but would require even more rewriting, and I don't really have a deep knowledge of the algorithm so that I would dare to rewrite it.

for the createDeadDefs() part it may be interesting to simply append the new segments to the vector in any order and later run a sorting algorithm which also eliminates duplicates on the vector. This should reduce the O(n**2) complexity to O(n log n) and I'd imagine it to perform well in the case where only a few segments are used.

Note that createDeadDef is also used outside the LiveIntervals phase, so we would still a version of createDeadDef that preserves the invariant of LiveRange.

It would be nice if the decision on whether to use the set or sorted vector based techniques could be based on the actual number of Defs/Uses of a register (deciding on whether it is a physreg seems a bit arbitrary to me although it's probably a good heuristic in practice). Unfortunately I don't see an easy way to determine the actual number of defs/uses for a vreg as that is only maintained as a double linked list without a counter at the moment, so it is probably okay as is.

Yet another approach would also be to rely always on the segment set for calculation of *all* live ranges in the LiveIntervals pass. Calculation of small live ranges is somewhat faster with vector, but it is only slightly faster and in that case the LiveIntervals pass runs very quickly anyway. I did not found examples with really large ranges for virtual registers, so I made a conservative decision to keep the computation of virtual registers as it is, because it is hard to choose a heuristic without a possibility to test it. But if anyone have some interesting examples I would be glad to evaluate them. Note that keeping the vector version of the algorithms is more important for later processing of the live ranges during register allocation, because insert operations are then not dominant anymore, and other operations work faster on the vector.

Best regards,
Vaidas

[qcolombet]

Hi all,

I agree with Vaidas that moving the set outside of the LiveRange may not be that easy.

Regarding the complexity improvements:

for the createDeadDefs() part it may be interesting to simply append the new segments to the vector in any order and later run a sorting algorithm which also eliminates duplicates on the vector. This should reduce the O(n**2) complexity to O(n log n) and I'd imagine it to perform well in the case where only a few segments are used.

I am not so sure that would be beneficial, indeed, we would have to do this sorting for each live range, i.e., O(m n log n) and I suspect that the (log n) factor will be bigger than the cost of the set for the cases we try to optimize.

Thanks,
-Quentin

[MatzeB]

As I said: Don't let my comments stop you from committing, fixing the performance regressions right now is important, cleaning the code up/avoiding the extra pointer can be dealt with later I guess.

[gasiunas]

Happy New Year to everyone!

Is there still an interest to merge this patch?

Best regards,
Vaidas

[qcolombet]

Hi Vaidas,

[gasiunas]

Is this change about to be merged or is some input from us still required?

Since I am leaving SAP by the end of this next week, please contact Philipp Becker (reviewer PCB) if you have any further questions about that change.

Kind regards,
Vaidas

[gasiunas]

Rebased on the latest llvm version and retested. It can be now commited.

Regards,
Vaidas

include/llvm/CodeGen/LiveInterval.h

 #define LLVM_CODEGEN_LIVEINTERVAL_H
 
 #include "llvm/ADT/IntEqClasses.h"
 #include "llvm/CodeGen/SlotIndexes.h"
 #include "llvm/Support/AlignOf.h"
 #include "llvm/Support/Allocator.h"
 #include <cassert>
 #include <climits>
+#include <set>
 
 namespace llvm {
   class CoalescerPair;
   class LiveIntervals;
   class MachineInstr;
   class MachineRegisterInfo;
   class TargetRegisterInfo;
   class raw_ostream;
public:
     };
 
     typedef SmallVector<Segment,4> Segments;
     typedef SmallVector<VNInfo*,4> VNInfoList;
 
     Segments segments;   // the liveness segments
     VNInfoList valnos;   // value#'s
 
+    // The segment set is used temporarily to accelerate initial computation
+    // of live ranges of physical registers in computeRegUnitRange.
+    // After that the set is flushed to the segment vector and deleted.
+    typedef std::set<Segment> SegmentSet;
+    SegmentSet *segmentSet;
+
     typedef Segments::iterator iterator;
     iterator begin() { return segments.begin(); }
     iterator end()   { return segments.end(); }
 
     typedef Segments::const_iterator const_iterator;
     const_iterator begin() const { return segments.begin(); }
     const_iterator end() const  { return segments.end(); }
 
     typedef VNInfoList::iterator vni_iterator;
     vni_iterator vni_begin() { return valnos.begin(); }
     vni_iterator vni_end()   { return valnos.end(); }
 
     typedef VNInfoList::const_iterator const_vni_iterator;
     const_vni_iterator vni_begin() const { return valnos.begin(); }
     const_vni_iterator vni_end() const   { return valnos.end(); }
 
     /// Constructs a new LiveRange object.
-    LiveRange() {
+    LiveRange(bool UseSegmentSet = false) : segmentSet(nullptr) {
+      if (UseSegmentSet)
+        segmentSet = new SegmentSet();
     }
 
     /// Constructs a new LiveRange object by copying segments and valnos from
     /// another LiveRange.
-    LiveRange(const LiveRange &Other, BumpPtrAllocator &Allocator) {
+    LiveRange(const LiveRange &Other, BumpPtrAllocator &Allocator) : segmentSet(nullptr) {
+      assert(Other.segmentSet == nullptr && "Copying of LiveRanges with active SegmentSets is not supported");
+
       // Duplicate valnos.
       for (const VNInfo *VNI : Other.valnos) {
         createValueCopy(VNI, Allocator);
       }
       // Now we can copy segments and remap their valnos.
       for (const Segment &S : Other.segments) {
         segments.push_back(Segment(S.start, S.end, valnos[S.valno->id]));
       }
     }
 
+    ~LiveRange() {
+      delete segmentSet;
+    }
+
     /// advanceTo - Advance the specified iterator to point to the Segment
     /// containing the specified position, or end() if the position is past the
     /// end of the range.  If no Segment contains this position, but the
     /// position is in a hole, this method returns an iterator pointing to the
     /// Segment immediately after the hole.
     iterator advanceTo(iterator I, SlotIndex Pos) {
       assert(I != end());
       if (Pos >= endIndex())
public:
     /// covered by this live range.
     /// Adjacent live ranges do not affect the covering:the liverange
     /// [1,5](5,10] covers (3,7].
     bool covers(const LiveRange &Other) const;
 
     /// Add the specified Segment to this range, merging segments as
     /// appropriate.  This returns an iterator to the inserted segment (which
     /// may have grown since it was inserted).
-    iterator addSegment(Segment S) {
-      return addSegmentFrom(S, segments.begin());
-    }
+    iterator addSegment(Segment S);
 
     /// extendInBlock - If this range is live before Kill in the basic block
     /// that starts at StartIdx, extend it to be live up to Kill, and return
     /// the value. If there is no segment before Kill, return NULL.
     VNInfo *extendInBlock(SlotIndex StartIdx, SlotIndex Kill);
 
     /// join - Join two live ranges (this, and other) together.  This applies
     /// mappings to the value numbers in the LHS/RHS ranges as specified.  If
     /// the ranges are not joinable, this aborts.
     void join(LiveRange &Other,
public:
     }
 
     bool operator<(const LiveRange& other) const {
       const SlotIndex &thisIndex = beginIndex();
       const SlotIndex &otherIndex = other.beginIndex();
       return thisIndex < otherIndex;
     }
 
+    /// Flush segment set into the regular segment vector.
+    /// The method is to be called after the live range
+    /// has been created, if use of the segment set was
+    /// activated in the constructor of the live range.
+    void flushSegmentSet();
+
     void print(raw_ostream &OS) const;
     void dump() const;
 
     /// \brief Walk the range and assert if any invariants fail to hold.
     ///
     /// Note that this is a no-op when asserts are disabled.
 #ifdef NDEBUG
     void verify() const {}
 #else
     void verify() const;
 #endif
 
   protected:
     /// Append a segment to the list of segments.
     void append(const LiveRange::Segment S);
 
   private:
-
-    iterator addSegmentFrom(Segment S, iterator From);
-    void extendSegmentEndTo(iterator I, SlotIndex NewEnd);
-    iterator extendSegmentStartTo(iterator I, SlotIndex NewStr);
+    friend class LiveRangeUpdater;
+    void addSegmentToSet(Segment S);
     void markValNoForDeletion(VNInfo *V);
 
   };
 
   inline raw_ostream &operator<<(raw_ostream &OS, const LiveRange &LR) {
     LR.print(OS);
     return OS;
   }
 
   /// LiveInterval - This class represents the liveness of a register,
   /// or stack slot.
   class LiveInterval : public LiveRange {
   public:

include/llvm/CodeGen/LiveIntervalAnalysis.h

 
 #include "llvm/ADT/IndexedMap.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/CodeGen/LiveInterval.h"
 #include "llvm/CodeGen/MachineBasicBlock.h"
 #include "llvm/CodeGen/MachineFunctionPass.h"
 #include "llvm/CodeGen/SlotIndexes.h"
 #include "llvm/Support/Allocator.h"
+#include "llvm/Support/CommandLine.h"
 #include "llvm/Target/TargetRegisterInfo.h"
 #include <cmath>
 #include <iterator>
 
 namespace llvm {
 
+  extern cl::opt<bool> UseSegmentSetForPhysRegs;
+
   class AliasAnalysis;
   class BitVector;
   class BlockFrequency;
   class LiveRangeCalc;
   class LiveVariables;
   class MachineDominatorTree;
   class MachineLoopInfo;
   class TargetRegisterInfo;
public:
     // efficiently.
 
     /// getRegUnit - Return the live range for Unit.
     /// It will be computed if it doesn't exist.
     LiveRange &getRegUnit(unsigned Unit) {
       LiveRange *LR = RegUnitRanges[Unit];
       if (!LR) {
         // Compute missing ranges on demand.
-        RegUnitRanges[Unit] = LR = new LiveRange();
+        // Use segment set to speed-up initial computation of the live range.
+        RegUnitRanges[Unit] = LR = new LiveRange(UseSegmentSetForPhysRegs);
         computeRegUnitRange(*LR, Unit);
       }
       return *LR;
     }
 
     /// getCachedRegUnit - Return the live range for Unit if it has already
     /// been computed, or NULL if it hasn't been computed yet.
     LiveRange *getCachedRegUnit(unsigned Unit) {
       return RegUnitRanges[Unit];

lib/CodeGen/LiveInterval.cpp

 #include "llvm/CodeGen/MachineRegisterInfo.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/Format.h"
 #include "llvm/Support/raw_ostream.h"
 #include "llvm/Target/TargetRegisterInfo.h"
 #include <algorithm>
 using namespace llvm;
 
+//===----------------------------------------------------------------------===//
+// Implementation of various methods necessary for calculation of live ranges.
+// The implementation of the methods abstracts from the concrete type of the
+// segment collection.
+//
+// Implementation of the class follows the Template design pattern. The base
+// class contains generic algorithms that call collection-specific methods,
+// which are provided in concrete subclasses. In order to avoid virtual calls
+// these methods are provided by means of C++ template instantiation.
+// The base class calls the methods of the subclass through method impl(),
+// which casts 'this' pointer to the type of the subclass.
+//
+//===----------------------------------------------------------------------===//
+
+template <typename ImplT, typename IteratorT, typename CollectionT>
+class CalcLiveRangeUtilBase {
+protected:
+  LiveRange *LR;
+
+protected:
+  CalcLiveRangeUtilBase(LiveRange *LR) : LR(LR) { }
+
+public:
+  typedef LiveRange::Segment Segment;
+  typedef IteratorT iterator;
+
+  VNInfo *createDeadDef(SlotIndex Def, VNInfo::Allocator &VNInfoAllocator) {
+    assert(!Def.isDead() && "Cannot define a value at the dead slot");
+
+    iterator I = impl().find(Def);
+    if (I == segments().end()) {
+      VNInfo *VNI = LR->getNextValue(Def, VNInfoAllocator);
+      impl().insertAtEnd(Segment(Def, Def.getDeadSlot(), VNI));
+      return VNI;
+    }
+
+    Segment *S = segmentAt(I);
+    if (SlotIndex::isSameInstr(Def, S->start)) {
+      assert(S->valno->def == S->start && "Inconsistent existing value def");
+
+      // It is possible to have both normal and early-clobber defs of the same
+      // register on an instruction. It doesn't make a lot of sense, but it is
+      // possible to specify in inline assembly.
+      //
+      // Just convert everything to early-clobber.
+      Def = std::min(Def, S->start);
+      if (Def != S->start)
+        S->start = S->valno->def = Def;
+      return S->valno;
+    }
+    assert(SlotIndex::isEarlierInstr(Def, S->start) && "Already live at def");
+    VNInfo *VNI = LR->getNextValue(Def, VNInfoAllocator);
+    segments().insert(I, Segment(Def, Def.getDeadSlot(), VNI));
+    return VNI;
+  }
+
+  VNInfo *extendInBlock(SlotIndex StartIdx, SlotIndex Kill) {
+    if (segments().empty())
+      return nullptr;
+    iterator I = impl().findInsertPos(Segment(Kill.getPrevSlot(), Kill, nullptr));
+    if (I == segments().begin())
+      return nullptr;
+    --I;
+    if (I->end <= StartIdx)
+      return nullptr;
+    if (I->end < Kill)
+      extendSegmentEndTo(I, Kill);
+    return I->valno;
+  }
+
+  /// This method is used when we want to extend the segment specified by I to end
+  /// at the specified endpoint.  To do this, we should merge and eliminate all
+  /// segments that this will overlap with.  The iterator is not invalidated.
+  void extendSegmentEndTo(iterator I, SlotIndex NewEnd) {
+    assert(I != segments().end() && "Not a valid segment!");
+    Segment *S = segmentAt(I);
+    VNInfo *ValNo = I->valno;
+
+    // Search for the first segment that we can't merge with.
+    iterator MergeTo = std::next(I);
+    for (; MergeTo != segments().end() && NewEnd >= MergeTo->end; ++MergeTo) {
+      assert(MergeTo->valno == ValNo && "Cannot merge with differing values!");
+    }
+
+    // If NewEnd was in the middle of a segment, make sure to get its endpoint.
+    S->end = std::max(NewEnd, std::prev(MergeTo)->end);
+
+    // If the newly formed segment now touches the segment after it and if they
+    // have the same value number, merge the two segments into one segment.
+    if (MergeTo != segments().end() && MergeTo->start <= I->end &&
+        MergeTo->valno == ValNo) {
+      S->end = MergeTo->end;
+      ++MergeTo;
+    }
+
+    // Erase any dead segments.
+    segments().erase(std::next(I), MergeTo);
+  }
+
+  /// This method is used when we want to extend the segment specified by I to
+  /// start at the specified endpoint.  To do this, we should merge and eliminate
+  /// all segments that this will overlap with.
+  iterator extendSegmentStartTo(iterator I, SlotIndex NewStart) {
+    assert(I != segments().end() && "Not a valid segment!");
+    Segment *S = segmentAt(I);
+    VNInfo *ValNo = I->valno;
+
+    // Search for the first segment that we can't merge with.
+    iterator MergeTo = I;
+    do {
+      if (MergeTo == segments().begin()) {
+        S->start = NewStart;
+        segments().erase(MergeTo, I);
+        return I;
+      }
+      assert(MergeTo->valno == ValNo && "Cannot merge with differing values!");
+      --MergeTo;
+    } while (NewStart <= MergeTo->start);
+
+    // If we start in the middle of another segment, just delete a range and
+    // extend that segment.
+    if (MergeTo->end >= NewStart && MergeTo->valno == ValNo) {
+      segmentAt(MergeTo)->end = S->end;
+    } else {
+      // Otherwise, extend the segment right after.
+      ++MergeTo;
+      Segment *MergeToSeg = segmentAt(MergeTo);
+      MergeToSeg->start = NewStart;
+      MergeToSeg->end = S->end;
+    }
+
+    segments().erase(std::next(MergeTo), std::next(I));
+    return MergeTo;
+  }
+
+  iterator addSegment(Segment S) {
+    SlotIndex Start = S.start, End = S.end;
+    iterator I = impl().findInsertPos(S);
+
+    // If the inserted segment starts in the middle or right at the end of
+    // another segment, just extend that segment to contain the segment of S.
+    if (I != segments().begin()) {
+      iterator B = std::prev(I);
+      if (S.valno == B->valno) {
+        if (B->start <= Start && B->end >= Start) {
+          extendSegmentEndTo(B, End);
+          return B;
+        }
+      } else {
+        // Check to make sure that we are not overlapping two live segments with
+        // different valno's.
+        assert(B->end <= Start &&
+               "Cannot overlap two segments with differing ValID's"
+               " (did you def the same reg twice in a MachineInstr?)");
+      }
+    }
+
+    // Otherwise, if this segment ends in the middle of, or right next to, another
+    // segment, merge it into that segment.
+    if (I != segments().end()) {
+      if (S.valno == I->valno) {
+        if (I->start <= End) {
+          I = extendSegmentStartTo(I, Start);
+
+          // If S is a complete superset of a segment, we may need to grow its
+          // endpoint as well.
+          if (End > I->end)
+            extendSegmentEndTo(I, End);
+          return I;
+        }
+      } else {
+        // Check to make sure that we are not overlapping two live segments with
+        // different valno's.
+        assert(I->start >= End &&
+               "Cannot overlap two segments with differing ValID's");
+      }
+    }
+
+    // Otherwise, this is just a new segment that doesn't interact with anything.
+    // Insert it.
+    return segments().insert(I, S);
+  }
+
+private:
+  ImplT& impl() { return *static_cast<ImplT*>(this); }
+
+  CollectionT& segments() { return impl().segmentsColl(); }
+
+  Segment *segmentAt(iterator I) { return const_cast<Segment*>(&(*I)); }
+};
+
+//===----------------------------------------------------------------------===//
+//   Instantiation of the methods for calculation of live ranges
+//   based on a segment vector.
+//===----------------------------------------------------------------------===//
+
+class CalcLiveRangeUtilVector;
+typedef CalcLiveRangeUtilBase<CalcLiveRangeUtilVector,
+                              LiveRange::iterator, LiveRange::Segments>
+  CalcLiveRangeUtilVectorBase;
+
+class CalcLiveRangeUtilVector : public CalcLiveRangeUtilVectorBase {
+public:
+  CalcLiveRangeUtilVector(LiveRange *LR) :
+    CalcLiveRangeUtilVectorBase(LR) { }
+
+private:
+  friend CalcLiveRangeUtilVectorBase;
+
+  LiveRange::Segments& segmentsColl() { return LR->segments; }
+
+  void insertAtEnd(const Segment& S) { LR->segments.push_back(S); }
+
+  iterator find(SlotIndex Pos) { return LR->find(Pos); }
+
+  iterator findInsertPos(Segment S) {
+    return std::upper_bound(LR->begin(), LR->end(), S.start);
+  }
+};
+
+//===----------------------------------------------------------------------===//
+//   Instantiation of the methods for calculation of live ranges
+//   based on a segment set.
+//===----------------------------------------------------------------------===//
+
+class CalcLiveRangeUtilSet;
+typedef CalcLiveRangeUtilBase<CalcLiveRangeUtilSet,
+                              LiveRange::SegmentSet::iterator,
+                              LiveRange::SegmentSet>
+  CalcLiveRangeUtilSetBase;
+
+class CalcLiveRangeUtilSet : public CalcLiveRangeUtilSetBase {
+public:
+  CalcLiveRangeUtilSet(LiveRange *LR) :
+    CalcLiveRangeUtilSetBase(LR) { }
+
+private:
+  friend CalcLiveRangeUtilSetBase;
+
+  LiveRange::SegmentSet& segmentsColl() { return *LR->segmentSet; }
+
+  void insertAtEnd(const Segment& S) {
+    LR->segmentSet->insert(LR->segmentSet->end(), S);
+  }
+
+  iterator find(SlotIndex Pos) {
+    iterator I = LR->segmentSet->upper_bound(Segment(Pos, Pos.getNextSlot(), nullptr));
+    if (I == LR->segmentSet->begin())
+      return I;
+    iterator PrevI = std::prev(I);
+    if (Pos < (*PrevI).end)
+      return PrevI;
+    return I;
+  }
+
+  iterator findInsertPos(Segment S) {
+    iterator I = LR->segmentSet->upper_bound(S);
+    if (I != LR->segmentSet->end() && !(S.start < *I))
+      ++I;
+    return I;
+  }
+};
+
+//===----------------------------------------------------------------------===//
+//   LiveRange methods
+//===----------------------------------------------------------------------===//
+
 LiveRange::iterator LiveRange::find(SlotIndex Pos) {
   // This algorithm is basically std::upper_bound.
   // Unfortunately, std::upper_bound cannot be used with mixed types until we
   // adopt C++0x. Many libraries can do it, but not all.
   if (empty() || Pos >= endIndex())
     return end();
   iterator I = begin();
   size_t Len = size();
   do {
     size_t Mid = Len >> 1;
     if (Pos < I[Mid].end)
       Len = Mid;
     else
       I += Mid + 1, Len -= Mid + 1;
   } while (Len);
   return I;
 }
 
 VNInfo *LiveRange::createDeadDef(SlotIndex Def,
                                   VNInfo::Allocator &VNInfoAllocator) {
-  assert(!Def.isDead() && "Cannot define a value at the dead slot");
-  iterator I = find(Def);
-  if (I == end()) {
-    VNInfo *VNI = getNextValue(Def, VNInfoAllocator);
-    segments.push_back(Segment(Def, Def.getDeadSlot(), VNI));
-    return VNI;
-  }
-  if (SlotIndex::isSameInstr(Def, I->start)) {
-    assert(I->valno->def == I->start && "Inconsistent existing value def");
-
-    // It is possible to have both normal and early-clobber defs of the same
-    // register on an instruction. It doesn't make a lot of sense, but it is
-    // possible to specify in inline assembly.
-    //
-    // Just convert everything to early-clobber.
-    Def = std::min(Def, I->start);
-    if (Def != I->start)
-      I->start = I->valno->def = Def;
-    return I->valno;
-  }
-  assert(SlotIndex::isEarlierInstr(Def, I->start) && "Already live at def");
-  VNInfo *VNI = getNextValue(Def, VNInfoAllocator);
-  segments.insert(I, Segment(Def, Def.getDeadSlot(), VNI));
-  return VNI;
+  // Use the segment set, if it is available.
+  if (segmentSet != nullptr)
+    return CalcLiveRangeUtilSet(this).createDeadDef(Def, VNInfoAllocator);
+  // Otherwise use the segment vector.
+  return CalcLiveRangeUtilVector(this).createDeadDef(Def, VNInfoAllocator);
 }
 
 // overlaps - Return true if the intersection of the two live ranges is
 // not empty.
 //
 // An example for overlaps():
 //
 // 0: A = ...
for (const Segment &S : segments) {
     if (!Seen.insert(VNI).second)
       continue;
     assert(!VNI->isUnused() && "Unused valno used by live segment");
     VNI->id = (unsigned)valnos.size();
     valnos.push_back(VNI);
   }
 }
 
-/// This method is used when we want to extend the segment specified by I to end
-/// at the specified endpoint.  To do this, we should merge and eliminate all
-/// segments that this will overlap with.  The iterator is not invalidated.
-void LiveRange::extendSegmentEndTo(iterator I, SlotIndex NewEnd) {
-  assert(I != end() && "Not a valid segment!");
-  VNInfo *ValNo = I->valno;
-
-  // Search for the first segment that we can't merge with.
-  iterator MergeTo = std::next(I);
-  for (; MergeTo != end() && NewEnd >= MergeTo->end; ++MergeTo) {
-    assert(MergeTo->valno == ValNo && "Cannot merge with differing values!");
-  }
-
-  // If NewEnd was in the middle of a segment, make sure to get its endpoint.
-  I->end = std::max(NewEnd, std::prev(MergeTo)->end);
-
-  // If the newly formed segment now touches the segment after it and if they
-  // have the same value number, merge the two segments into one segment.
-  if (MergeTo != end() && MergeTo->start <= I->end &&
-      MergeTo->valno == ValNo) {
-    I->end = MergeTo->end;
-    ++MergeTo;
-  }
+void LiveRange::addSegmentToSet(Segment S) {
+  CalcLiveRangeUtilSet(this).addSegment(S);
 
-  // Erase any dead segments.
-  segments.erase(std::next(I), MergeTo);
-}
-
-
-/// This method is used when we want to extend the segment specified by I to
-/// start at the specified endpoint.  To do this, we should merge and eliminate
-/// all segments that this will overlap with.
-LiveRange::iterator
-LiveRange::extendSegmentStartTo(iterator I, SlotIndex NewStart) {
-  assert(I != end() && "Not a valid segment!");
-  VNInfo *ValNo = I->valno;
-
-  // Search for the first segment that we can't merge with.
-  iterator MergeTo = I;
-  do {
-    if (MergeTo == begin()) {
-      I->start = NewStart;
-      segments.erase(MergeTo, I);
-      return I;
-    }
-    assert(MergeTo->valno == ValNo && "Cannot merge with differing values!");
-    --MergeTo;
-  } while (NewStart <= MergeTo->start);
-
-  // If we start in the middle of another segment, just delete a range and
-  // extend that segment.
-  if (MergeTo->end >= NewStart && MergeTo->valno == ValNo) {
-    MergeTo->end = I->end;
-  } else {
-    // Otherwise, extend the segment right after.
-    ++MergeTo;
-    MergeTo->start = NewStart;
-    MergeTo->end = I->end;
+LiveRange::iterator LiveRange::addSegment(Segment S) {
+  // Use the segment set, if it is available.
+  if (segmentSet != nullptr) {
+    addSegmentToSet(S);
+    return end();
   }
-
-  segments.erase(std::next(MergeTo), std::next(I));
-  return MergeTo;
+  // Otherwise use the segment vector.
+  return CalcLiveRangeUtilVector(this).addSegment(S);
 }
 
 void LiveRange::append(const Segment S) {
   // Check that the segment belongs to the back of the list.
   assert(segments.empty() || segments.back().end <= S.start);
   segments.push_back(S);
 }
 
-LiveRange::iterator LiveRange::addSegmentFrom(Segment S, iterator From) {
-  SlotIndex Start = S.start, End = S.end;
-  iterator it = std::upper_bound(From, end(), Start);
-
-  // If the inserted segment starts in the middle or right at the end of
-  // another segment, just extend that segment to contain the segment of S.
-  if (it != begin()) {
-    iterator B = std::prev(it);
-    if (S.valno == B->valno) {
-      if (B->start <= Start && B->end >= Start) {
-        extendSegmentEndTo(B, End);
-        return B;
-      }
-    } else {
-      // Check to make sure that we are not overlapping two live segments with
-      // different valno's.
-      assert(B->end <= Start &&
-             "Cannot overlap two segments with differing ValID's"
-             " (did you def the same reg twice in a MachineInstr?)");
-    }
-  }
-
-  // Otherwise, if this segment ends in the middle of, or right next to, another
-  // segment, merge it into that segment.
-  if (it != end()) {
-    if (S.valno == it->valno) {
-      if (it->start <= End) {
-        it = extendSegmentStartTo(it, Start);
-
-        // If S is a complete superset of a segment, we may need to grow its
-        // endpoint as well.
-        if (End > it->end)
-          extendSegmentEndTo(it, End);
-        return it;
-      }
-    } else {
-      // Check to make sure that we are not overlapping two live segments with
-      // different valno's.
-      assert(it->start >= End &&
-             "Cannot overlap two segments with differing ValID's");
-    }
-  }
-
-  // Otherwise, this is just a new segment that doesn't interact with anything.
-  // Insert it.
-  return segments.insert(it, S);
-}
-
 /// extendInBlock - If this range is live before Kill in the basic
 /// block that starts at StartIdx, extend it to be live up to Kill and return
 /// the value. If there is no live range before Kill, return NULL.
 VNInfo *LiveRange::extendInBlock(SlotIndex StartIdx, SlotIndex Kill) {
-  if (empty())
-    return nullptr;
-  iterator I = std::upper_bound(begin(), end(), Kill.getPrevSlot());
-  if (I == begin())
-    return nullptr;
-  --I;
-  if (I->end <= StartIdx)
-    return nullptr;
-  if (I->end < Kill)
-    extendSegmentEndTo(I, Kill);
-  return I->valno;
+  // Use the segment set, if it is available.
+  if (segmentSet != nullptr)
+    return CalcLiveRangeUtilSet(this).extendInBlock(StartIdx, Kill);
+  // Otherwise use the segment vector.
+  return CalcLiveRangeUtilVector(this).extendInBlock(StartIdx, Kill);
 }
 
 /// Remove the specified segment from this range.  Note that the segment must
 /// be in a single Segment in its entirety.
 void LiveRange::removeSegment(SlotIndex Start, SlotIndex End,
                               bool RemoveDeadValNo) {
   // Find the Segment containing this span.
   iterator I = find(Start);
VNInfo *LiveRange::MergeValueNumberInto(VNInfo *V1, VNInfo *V2) {
   }
 
   // Now that V1 is dead, remove it.
   markValNoForDeletion(V1);
 
   return V2;
 }
 
+void LiveRange::flushSegmentSet() {
+  assert(segmentSet != nullptr && "segment set must have been created");
+  assert(segments.empty() && "segment set can be used only initially before switching to the array");
+  segments.append(segmentSet->begin(), segmentSet->end());
+  delete segmentSet;
+  segmentSet = nullptr;
+  verify();
+}
+
 void LiveInterval::removeEmptySubRanges() {
   SubRange **NextPtr = &SubRanges;
   SubRange *I = *NextPtr;
   while (I != nullptr) {
     if (!I->empty()) {
       NextPtr = &I->Next;
       I = *NextPtr;
       continue;
     }
     // Skip empty subranges until we find the first nonempty one.
     do {
       I = I->Next;
     } while (I != nullptr && I->empty());
     *NextPtr = I;
   }
 }
 
 /// Helper function for constructMainRangeFromSubranges(): Search the CFG
 /// backwards until we find a place covered by a LiveRange segment that actually
 /// has a valno set.
 static VNInfo *searchForVNI(const SlotIndexes &Indexes, LiveRange &LR,
     const MachineBasicBlock *MBB,
     SmallPtrSetImpl<const MachineBasicBlock*> &Visited) {
   // We start the search at the end of MBB.
   SlotIndex EndIdx = Indexes.getMBBEndIdx(MBB);
   // In our use case we can't live the area covered by the live segments without
   // finding an actual VNI def.
   LiveRange::iterator I = LR.find(EndIdx.getPrevSlot());
   assert(I != LR.end());
   LiveRange::Segment &S = *I;
   if (S.valno != nullptr)
     return S.valno;
 
   VNInfo *VNI = nullptr;
   // Continue at predecessors (we could even go to idom with domtree available).
   for (const MachineBasicBlock *Pred : MBB->predecessors()) {
     // Avoid going in circles.
if (S.valno != nullptr)
       continue;
     // This can only happen at the begin of a basic block.
     assert(S.start.isBlock() && "valno should only be missing at block begin");
 
     Visited.clear();
     const MachineBasicBlock *MBB = Indexes.getMBBFromIndex(S.start);
     for (const MachineBasicBlock *Pred : MBB->predecessors()) {
       VNInfo *VNI = searchForVNI(Indexes, LI, Pred, Visited);
       if (VNI != nullptr) {
         S.valno = VNI;
         break;
       }
     }
     assert(S.valno != nullptr && "could not determine valno");
   }
 }
 
 void LiveInterval::constructMainRangeFromSubranges(
     const SlotIndexes &Indexes, VNInfo::Allocator &VNIAllocator) {
   // The basic observations on which this algorithm is based:
   // - Each Def/ValNo in a subrange must have a corresponding def on the main
   //   range, but not further defs/valnos are necessary.
   // - If any of the subranges is live at a point the main liverange has to be
   //   live too, conversily if no subrange is live the main range mustn't be
   //   live either.
   // We do this by scannig through all the subranges simultaneously creating new
   // segments in the main range as segments start/ends come up in the subranges.
   assert(hasSubRanges() && "expected subranges to be present");
   assert(segments.empty() && valnos.empty() && "expected empty main range");
 
   // Collect subrange, iterator pairs for the walk and determine first and last
   // SlotIndex involved.
   SmallVector<std::pair<const SubRange*, const_iterator>, 4> SRs;
   SlotIndex First;
   SlotIndex Last;
   for (const SubRange &SR : subranges()) {
     if (SR.empty())
       continue;
if (A.end < B.start)
     return false;
   assert(A.valno == B.valno && "Cannot overlap different values");
   return true;
 }
 
 void LiveRangeUpdater::add(LiveRange::Segment Seg) {
   assert(LR && "Cannot add to a null destination");
 
+  // Fall back to the regular add method if the live range
+  // is using the segment set instead of the segment vector.
+  if (LR->segmentSet != nullptr) {
+    LR->addSegmentToSet(Seg);
+    return;
+  }
+
   // Flush the state if Start moves backwards.
   if (!LastStart.isValid() || LastStart > Seg.start) {
     if (isDirty())
       flush();
     // This brings us to an uninitialized state. Reinitialize.
     assert(Spills.empty() && "Leftover spilled segments");
     WriteI = ReadI = LR->begin();
   }

lib/CodeGen/LiveIntervalAnalysis.cpp

 #else
 static bool EnablePrecomputePhysRegs = false;
 #endif // NDEBUG
 
 static cl::opt<bool> EnableSubRegLiveness(
   "enable-subreg-liveness", cl::Hidden, cl::init(true),
   cl::desc("Enable subregister liveness tracking."));
 
+namespace llvm {
+cl::opt<bool> UseSegmentSetForPhysRegs(
+  "use-segment-set-for-physregs", cl::Hidden, cl::init(true),
+  cl::desc("Use segment set for the computation of the live ranges of physregs."));
+}
+
 void LiveIntervals::getAnalysisUsage(AnalysisUsage &AU) const {
   AU.setPreservesCFG();
   AU.addRequired<AliasAnalysis>();
   AU.addPreserved<AliasAnalysis>();
   // LiveVariables isn't really required by this analysis, it is only required
   // here to make sure it is live during TwoAddressInstructionPass and
   // PHIElimination. This is temporary.
   AU.addRequired<LiveVariables>();
void LiveIntervals::computeRegUnitRange(LiveRange &LR, unsigned Unit) {
   for (MCRegUnitRootIterator Roots(Unit, TRI); Roots.isValid(); ++Roots) {
     for (MCSuperRegIterator Supers(*Roots, TRI, /*IncludeSelf=*/true);
          Supers.isValid(); ++Supers) {
       unsigned Reg = *Supers;
       if (!MRI->isReserved(Reg) && !MRI->reg_empty(Reg))
         LRCalc->extendToUses(LR, Reg);
     }
   }
+
+  // Flush the segment set to the segment vector.
+  if (UseSegmentSetForPhysRegs)
+    LR.flushSegmentSet();
 }
 
 
 /// computeLiveInRegUnits - Precompute the live ranges of any register units
 /// that are live-in to an ABI block somewhere. Register values can appear
 /// without a corresponding def when entering the entry block or a landing pad.
 ///
 void LiveIntervals::computeLiveInRegUnits() {
for (MachineFunction::const_iterator MFI = MF->begin(), MFE = MF->end();
     SlotIndex Begin = Indexes->getMBBStartIdx(MBB);
     DEBUG(dbgs() << Begin << "\tBB#" << MBB->getNumber());
     for (MachineBasicBlock::livein_iterator LII = MBB->livein_begin(),
          LIE = MBB->livein_end(); LII != LIE; ++LII) {
       for (MCRegUnitIterator Units(*LII, TRI); Units.isValid(); ++Units) {
         unsigned Unit = *Units;
         LiveRange *LR = RegUnitRanges[Unit];
         if (!LR) {
-          LR = RegUnitRanges[Unit] = new LiveRange();
+    // Use segment set to speed-up initial computation of the live range.
+          LR = RegUnitRanges[Unit] = new LiveRange(UseSegmentSetForPhysRegs);
           NewRanges.push_back(Unit);
         }
         VNInfo *VNI = LR->createDeadDef(Begin, getVNInfoAllocator());
         (void)VNI;
         DEBUG(dbgs() << ' ' << PrintRegUnit(Unit, TRI) << '#' << VNI->id);
       }
     }
     DEBUG(dbgs() << '\n');
   }
   DEBUG(dbgs() << "Created " << NewRanges.size() << " new intervals.\n");
 
   // Compute the 'normal' part of the ranges.
   for (unsigned i = 0, e = NewRanges.size(); i != e; ++i) {
     unsigned Unit = NewRanges[i];
     computeRegUnitRange(*RegUnitRanges[Unit], Unit);
   }
 }
 
 
 static void createSegmentsForValues(LiveRange &LR,
       iterator_range<LiveInterval::vni_iterator> VNIs) {
   for (auto VNI : VNIs) {
     if (VNI->isUnused())
       continue;
     SlotIndex Def = VNI->def;
     LR.addSegment(LiveRange::Segment(Def, Def.getDeadSlot(), VNI));