search for: liveintervalunion

...nce using atoms instead of aliases. That will be faster since every register has fewer atoms than aliases. It also scales well when adding support for register sequence constraints since new super-registers don't add any atoms. In the greedy and basic allocators, it means that we will have one LiveIntervalUnion per atom instead of one per physical register as we do it today. > Whereas, I don't see a reason that proliferating register classes would be a problem now or in the future. > > Is it easy to distinguish a a couple classes that make up a disjoint coverage set (e.g. int regs, float re...

...atoms instead of aliases. That will be faster since every register has fewer atoms than aliases. It also scales well when adding support for register sequence constraints since new super-registers don't add any atoms. > > In the greedy and basic allocators, it means that we will have one LiveIntervalUnion per atom instead of one per physical register as we do it today. That's one way to make an algorithm scale well--just make the best case expensive enough. Actually, I like this approach very much, I just wonder if we need to 8x liveintervals for pure 64-bit code. -Andy

...stead of aliases. That will be faster since every register has fewer atoms than aliases. It also scales well when adding support for register sequence constraints since new super-registers don't add any atoms. >> >> In the greedy and basic allocators, it means that we will have one LiveIntervalUnion per atom instead of one per physical register as we do it today. > > That's one way to make an algorithm scale well--just make the best case expensive enough. Actually, I like this approach very much, I just wonder if we need to 8x liveintervals for pure 64-bit code. 8x is not necessary...

...ycle with a redefined LiveRange::overlap-function. On a multiple-issue cycle, a register that gets killed > can be reused by another MI - these live ranges do not then overlap. Redefining overlap() won't work for that. There is other code assuming that overlap means overlap, for example the LiveIntervalUnion used by the new register allocators. For VLIW, you probably want to number your packets instead of individual instructions. We don't have any VLIW support, so nobody has thought about how best to do it. > Well, I would like to schedule the VLIW code after SimpleRegisterCoalescer, so that I...

Hi (Jakob), in reference to the prior message below, I have the following follow-up questions, as I also need a scheduling pass prior to regalloc. I need to do this in order to set VLIW-flags, so that the RA is aware of several MI's per cycle with a redefined LiveRange::overlap-function. On a multiple-issue cycle, a register that gets killed can be reused by another MI - these live ranges do

...edefined LiveRange::overlap-function. On a multiple-issue cycle, a register that gets killed >> can be reused by another MI - these live ranges do not then overlap. > > Redefining overlap() won't work for that. There is other code assuming that overlap means overlap, for example the LiveIntervalUnion used by the new register allocators. > > For VLIW, you probably want to number your packets instead of individual instructions. We don't have any VLIW support, so nobody has thought about how best to do it. People had discussed VLIW support before, you may have a look at this: http://old...

...e reglist > > So similar to what's done in LRE_WillShrinkVirtReg(), it searches for live intervals where REG_Y is allocated and evicts them for reallocation. I don't know if there's a faster way of doing this but it's working :) Looks good. It is probably faster to scan the LiveIntervalUnion for REG_Y for assigned virtual registers, but the above code will work just fine. Technically, you should also check REG_Y's aliases, but there probably aren't any. > About your first question: the register has to be reserved throughout the whole function. > > Thanks for the hel...

Thanks for all the hints Jakob, I've added the following piece of code after the spill code handling inside selectOrSplit() (ignoring some control logic): for (LiveIntervals::const_iterator I = LIS->begin(), E = LIS->end(); I != E; ++I) { unsigned VirtReg = I->first; if ((TargetRegisterInfo::isVirtualRegister(VirtReg)) && (VRM->getPhys(VirtReg)

On Jun 21, 2011, at 10:20 AM, Jakob Stoklund Olesen wrote: > > On Jun 21, 2011, at 9:23 AM, Jim Grosbach wrote: > >> >> On Jun 21, 2011, at 8:51 AM, Jakob Stoklund Olesen wrote: >> >>> In the past, I've seen some pushback on the list against adding more register classes. You can see it in the code as well,

...ceptive to replacing the register allocator, but the design space was wide open. I knew from experience that we did not want to build a traditional interference graph. Chris, Evan, and Jakob all agreed on this point. I reasoned that an efficient implementation of LiveInterval along with a new "LiveIntervalUnion" data structure and mechanism for caching interference tests would be sufficient, and offered to build a prototype to prove it. This was an important step. My goal was never to develop a theoretically superior register allocator algorithm in its own right. On the contrary, Jakob and I wanted...

On Jun 21, 2011, at 9:23 AM, Jim Grosbach wrote: > > On Jun 21, 2011, at 8:51 AM, Jakob Stoklund Olesen wrote: > >> In the past, I've seen some pushback on the list against adding more register classes. You can see it in the code as well, TargetLowering::getRegClassForInlineAsmConstraint() returns a vector of registers instead of a real register class. >> >> What

...efined LiveRange::overlap-function. On a multiple-issue cycle, a register that gets killed > > can be reused by another MI - these live ranges do not then overlap. > > Redefining overlap() won't work for that. There is other code assuming that overlap means overlap, for example the LiveIntervalUnion used by the new register allocators. > > For VLIW, you probably want to number your packets instead of individual instructions. We don't have any VLIW support, so nobody has thought about how best to do it. > > > Well, I would like to schedule the VLIW code after SimpleRegister...

...the register allocator, but the design space was wide > open. I knew from experience that we did not want to build a > traditional interference graph. Chris, Evan, and Jakob all agreed on > this point. I reasoned that an efficient implementation of > LiveInterval along with a new "LiveIntervalUnion" data structure and > mechanism for caching interference tests would be sufficient, and > offered to build a prototype to prove it. > > This was an important step. My goal was never to develop a > theoretically superior register allocator algorithm in its own > right. On the...

Hi Jakob, Thanks for a very interesting description of the new register allocation algorithm in LLVM!!! Could you elaborate a bit on the following topics: 1) Do you have any plans to publish something more formal and detailed about this algorithm, e.g. a paper or something similar?  It would be nice to better understand how this algorithm relates to well-known algorithms described in the

I just uploaded a blog post outlining the new register allocation algorithm in LLVM 3.0. http://blog.llvm.org/2011/09/greedy-register-allocation-in-llvm-30.html Please direct comments here. /jakob

...Unit.cpp for Release+Asserts build llvm[2]: Compiling MCAsmInfoDarwin.cpp for Release+Asserts build llvm[2]: Compiling ELFYAML.cpp for Release+Asserts build llvm[3]: Compiling DWARFContext.cpp for Release+Asserts build llvm[2]: Compiling MCAsmInfoELF.cpp for Release+Asserts build llvm[2]: Compiling LiveIntervalUnion.cpp for Release+Asserts build llvm[2]: Compiling MCAsmStreamer.cpp for Release+Asserts build llvm[2]: Compiling Error.cpp for Release+Asserts build llvm[2]: Compiling IRObjectFile.cpp for Release+Asserts build llvm[3]: Compiling DWARFDebugAbbrev.cpp for Release+Asserts build llvm[2]: Compiling Live...