<html><head><meta http-equiv="Content-Type" content="text/html charset=utf-8"></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" class=""><div class="">If you don't have any register constraints SSA coloring boils down to: "Walk the program in dominance order and assign a fresh register to each def and release the register on a last use". However you need a way to implement register swaps for phi instructions afterwards although with infinite temp registers this is trivial.</div><div class="">I'd definitely recommend implementing a simple allocator from scratch, maybe reusing the liveness calculation, as you don't need all the tricks necessary to deal with register constraints, two-address instructions, precolored registers, spill code placement, ...</div><div class=""><br class=""></div><div class="">- Matthias</div><br class=""><div><blockquote type="cite" class=""><div class="">On Jun 19, 2015, at 9:50 AM, Quentin Colombet <<a href="mailto:qcolombet@apple.com" class="">qcolombet@apple.com</a>> wrote:</div><br class="Apple-interchange-newline"><div class=""><blockquote type="cite" class="" style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;"><div class=""><br class="Apple-interchange-newline">On Jun 19, 2015, at 7:49 AM, Jakob Stoklund Olesen <<a href="mailto:stoklund@2pi.dk" class="">stoklund@2pi.dk</a>> wrote:</div><br class="Apple-interchange-newline"><div class=""><div class="" style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;"><br class=""><div class=""><blockquote type="cite" class=""><div class="">On Jun 18, 2015, at 6:47 AM, JF Bastien <<a href="mailto:jfb@google.com" class="">jfb@google.com</a>> wrote:</div><br class="Apple-interchange-newline"><div class=""><div class="" style="font-family: Optima-Regular; font-size: 18px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;">We foresee having an infinite number of locals per function, but we plan to pre-color them so that locals whose lifetimes don't interfere can be merged. We can get clever and do this in an interesting order.</div></div></blockquote></div><br class=""><div class="">The NVPTX target does this with the existing register allocator by defining 800 physical registers of each type. It means you have to deal with unwanted spill code for those programs that exhaust the 800 registers.</div><div class=""><br class=""></div><div class="">The greedy register allocator doesn’t scale too well along that axis IMO. I think you get something like O(#vregs x #colors-used) behavior. It’s really designed to handle a small, fixed number of physical registers.</div><div class=""><br class=""></div><div class="">Matthias, Quentin: How well do the SSA-based register allocator algorithms work with infinite colors available?</div></div></div></blockquote><div style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;" class=""><br class=""></div><div style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;" class="">The SSA-based register allocators work in linear time of the number of instructions.</div><div style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;" class=""><br class=""></div><div style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;" class="">Cheers,</div><div style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;" class="">Q.</div><br class="" style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;"><blockquote type="cite" class="" style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;"><div class=""><div class="" style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;"><div class=""><br class=""></div><div class="">Thanks,</div><div class="">/jakob</div></div></div></blockquote></div></blockquote></div><br class=""></body></html>