<html><head><base href="x-msg://1179/"></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space; "><br><div><div>On Jul 1, 2011, at 4:02 PM, Villmow, Micah wrote:</div><br class="Apple-interchange-newline"><blockquote type="cite"><span class="Apple-style-span" style="border-collapse: separate; font-family: Helvetica; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-border-horizontal-spacing: 0px; -webkit-border-vertical-spacing: 0px; -webkit-text-decorations-in-effect: none; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px; font-size: medium; "><div lang="EN-US" link="blue" vlink="purple" style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space; "><div class="WordSection1" style="page: WordSection1; "><div style="margin-top: 0in; margin-right: 0in; margin-bottom: 0.0001pt; margin-left: 0in; font-size: 12pt; font-family: 'Times New Roman', serif; "><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125); "><o:p> </o:p></span></div><div style="margin-top: 0in; margin-right: 0in; margin-bottom: 0.0001pt; margin-left: 0in; font-size: 12pt; font-family: 'Times New Roman', serif; "><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125); "><o:p> </o:p></span></div><div style="border-top-style: none; border-right-style: none; border-bottom-style: none; border-width: initial; border-color: initial; border-left-style: solid; border-left-color: blue; border-left-width: 1.5pt; padding-top: 0in; padding-right: 0in; padding-bottom: 0in; padding-left: 4pt; position: static; z-index: auto; "><div><div style="border-right-style: none; border-bottom-style: none; border-left-style: none; border-width: initial; border-color: initial; border-top-style: solid; border-top-color: rgb(181, 196, 223); border-top-width: 1pt; padding-top: 3pt; padding-right: 0in; padding-bottom: 0in; padding-left: 0in; "><div style="margin-top: 0in; margin-right: 0in; margin-bottom: 0.0001pt; margin-left: 0in; font-size: 12pt; font-family: 'Times New Roman', serif; "><b><span style="font-size: 10pt; font-family: Tahoma, sans-serif; ">From:</span></b><span style="font-size: 10pt; font-family: Tahoma, sans-serif; "><span class="Apple-converted-space"> </span>Jakob Stoklund Olesen [mailto:stoklund@2pi.dk]<span class="Apple-converted-space"> </span><br><b>Sent:</b><span class="Apple-converted-space"> </span>Friday, July 01, 2011 2:56 PM<br><b>To:</b><span class="Apple-converted-space"> </span>Villmow, Micah<br><b>Cc:</b><span class="Apple-converted-space"> </span><a href="mailto:llvmdev@cs.uiuc.edu" style="color: blue; text-decoration: underline; ">llvmdev@cs.uiuc.edu</a><br><b>Subject:</b><span class="Apple-converted-space"> </span>Re: [LLVMdev] (no subject)<o:p></o:p></span></div></div></div><div style="margin-top: 0in; margin-right: 0in; margin-bottom: 0.0001pt; margin-left: 0in; font-size: 12pt; font-family: 'Times New Roman', serif; "><o:p> </o:p></div><div style="margin-top: 0in; margin-right: 0in; margin-bottom: 0.0001pt; margin-left: 0in; font-size: 12pt; font-family: 'Times New Roman', serif; "><o:p> </o:p></div><div><div><div style="margin-top: 0in; margin-right: 0in; margin-bottom: 0.0001pt; margin-left: 0in; font-size: 12pt; font-family: 'Times New Roman', serif; ">On Jul 1, 2011, at 12:16 PM, Villmow, Micah wrote:<o:p></o:p></div></div><div style="margin-top: 0in; margin-right: 0in; margin-bottom: 0.0001pt; margin-left: 0in; font-size: 12pt; font-family: 'Times New Roman', serif; "><br><br><o:p></o:p></div><div><div><div style="margin-top: 0in; margin-right: 0in; margin-bottom: 0.0001pt; margin-left: 0in; font-size: 12pt; font-family: 'Times New Roman', serif; "><span style="font-size: 11pt; font-family: Calibri, sans-serif; ">I'm trying to debug a problem with our custom backend with using a tiered register allocation setup.<o:p></o:p></span></div></div><div><div style="margin-top: 0in; margin-right: 0in; margin-bottom: 0.0001pt; margin-left: 0in; font-size: 12pt; font-family: 'Times New Roman', serif; "><span style="font-size: 11pt; font-family: Calibri, sans-serif; "> <o:p></o:p></span></div></div><div><div style="margin-top: 0in; margin-right: 0in; margin-bottom: 0.0001pt; margin-left: 0in; font-size: 12pt; font-family: 'Times New Roman', serif; "><span style="font-size: 11pt; font-family: Calibri, sans-serif; ">Just a little background. My target uses vec4 32bit registers and I want to have three levels of registers setup.<o:p></o:p></span></div></div><div><div style="margin-top: 0in; margin-right: 0in; margin-bottom: 0.0001pt; margin-left: 0in; font-size: 12pt; font-family: 'Times New Roman', serif; "><span style="font-size: 11pt; font-family: Calibri, sans-serif; ">Each vec4 register can have two sub-regs of size vec2 32bit, and each sub-reg, has its own two sub-regs of 32bit each.<o:p></o:p></span></div></div><div><div style="margin-top: 0in; margin-right: 0in; margin-bottom: 0.0001pt; margin-left: 0in; font-size: 12pt; font-family: 'Times New Roman', serif; "><span style="font-size: 11pt; font-family: Calibri, sans-serif; ">So it looks like this, xyzw -> {xy, zw} -> {x, y, z, w}.<o:p></o:p></span></div></div><div><div style="margin-top: 0in; margin-right: 0in; margin-bottom: 0.0001pt; margin-left: 0in; font-size: 12pt; font-family: 'Times New Roman', serif; "><span style="font-size: 11pt; font-family: Calibri, sans-serif; "> <o:p></o:p></span></div></div><div><div style="margin-top: 0in; margin-right: 0in; margin-bottom: 0.0001pt; margin-left: 0in; font-size: 12pt; font-family: 'Times New Roman', serif; "><span style="font-size: 11pt; font-family: Calibri, sans-serif; ">Now the problem I am having is that for some reason, the linearscan allocator is running out of registers to allocate.<o:p></o:p></span></div></div><div><div style="margin-top: 0in; margin-right: 0in; margin-bottom: 0.0001pt; margin-left: 0in; font-size: 12pt; font-family: 'Times New Roman', serif; "><span style="font-size: 11pt; font-family: Calibri, sans-serif; "> <o:p></o:p></span></div></div><div><div style="margin-top: 0in; margin-right: 0in; margin-bottom: 0.0001pt; margin-left: 0in; font-size: 12pt; font-family: 'Times New Roman', serif; "><span style="font-size: 11pt; font-family: Calibri, sans-serif; ">This makes no sense to me as I have 1024 vec4 registers(so 2048 vec2 and 4096 scalars).<o:p></o:p></span></div></div><div><div style="margin-top: 0in; margin-right: 0in; margin-bottom: 0.0001pt; margin-left: 0in; font-size: 12pt; font-family: 'Times New Roman', serif; "><span style="font-size: 11pt; font-family: Calibri, sans-serif; ">So I limited to a very small test case where I have 1 vec4(2 vec2 and 4 scalar) registers with<o:p></o:p></span></div></div><div><div style="margin-top: 0in; margin-right: 0in; margin-bottom: 0.0001pt; margin-left: 0in; font-size: 12pt; font-family: 'Times New Roman', serif; "><span style="font-size: 11pt; font-family: Calibri, sans-serif; ">a function that requires 1 vec4 register and 5 scalar registers. So, basically what happens<o:p></o:p></span></div></div><div><div style="margin-top: 0in; margin-right: 0in; margin-bottom: 0.0001pt; margin-left: 0in; font-size: 12pt; font-family: 'Times New Roman', serif; "><span style="font-size: 11pt; font-family: Calibri, sans-serif; ">is that everything works fine until the live-in register(which is scalar) to the function<o:p></o:p></span></div></div><div><div style="margin-top: 0in; margin-right: 0in; margin-bottom: 0.0001pt; margin-left: 0in; font-size: 12pt; font-family: 'Times New Roman', serif; "><span style="font-size: 11pt; font-family: Calibri, sans-serif; ">conflicts with a register that is allocated for the vector(as it is a sub-sub-reg). The<o:p></o:p></span></div></div><div><div style="margin-top: 0in; margin-right: 0in; margin-bottom: 0.0001pt; margin-left: 0in; font-size: 12pt; font-family: 'Times New Roman', serif; "><span style="font-size: 11pt; font-family: Calibri, sans-serif; ">linear scan allocator attempts to spill the live-in onto itself and then asserts with<o:p></o:p></span></div></div><div><div style="margin-top: 0in; margin-right: 0in; margin-bottom: 0.0001pt; margin-left: 0in; font-size: 12pt; font-family: 'Times New Roman', serif; "><span style="font-size: 10pt; font-family: 'Courier New'; ">assert(<span style="color: blue; ">false</span><span class="apple-converted-space"> </span>&&<span class="apple-converted-space"> </span><span style="color: rgb(163, 21, 21); ">"Ran out of registers during register allocation!"</span>);.</span><span style="font-size: 11pt; font-family: Calibri, sans-serif; "><o:p></o:p></span></div></div><div><div style="margin-top: 0in; margin-right: 0in; margin-bottom: 0.0001pt; margin-left: 0in; font-size: 12pt; font-family: 'Times New Roman', serif; "><span style="font-size: 10pt; font-family: 'Courier New'; "> </span><span style="font-size: 11pt; font-family: Calibri, sans-serif; "><o:p></o:p></span></div></div><div><div style="margin-top: 0in; margin-right: 0in; margin-bottom: 0.0001pt; margin-left: 0in; font-size: 12pt; font-family: 'Times New Roman', serif; "><span style="font-size: 11pt; font-family: Calibri, sans-serif; ">I've attached the output of running LLC on my test case, which<o:p></o:p></span></div></div><div><div style="margin-top: 0in; margin-right: 0in; margin-bottom: 0.0001pt; margin-left: 0in; font-size: 12pt; font-family: 'Times New Roman', serif; "><span style="font-size: 11pt; font-family: Calibri, sans-serif; ">I don't know if it will be helpful or not, to see what the live<o:p></o:p></span></div></div><div><div style="margin-top: 0in; margin-right: 0in; margin-bottom: 0.0001pt; margin-left: 0in; font-size: 12pt; font-family: 'Times New Roman', serif; "><span style="font-size: 11pt; font-family: Calibri, sans-serif; ">interval and reg allocator are doing.<o:p></o:p></span></div></div><div><div style="margin-top: 0in; margin-right: 0in; margin-bottom: 0.0001pt; margin-left: 0in; font-size: 12pt; font-family: 'Times New Roman', serif; "><span style="font-size: 11pt; font-family: Calibri, sans-serif; "> <o:p></o:p></span></div></div><div><div style="margin-top: 0in; margin-right: 0in; margin-bottom: 0.0001pt; margin-left: 0in; font-size: 12pt; font-family: 'Times New Roman', serif; "><span style="font-size: 11pt; font-family: Calibri, sans-serif; ">I'm having trouble debugging this, any idea on where I might want to look?<o:p></o:p></span></div></div></div><div><div style="margin-top: 0in; margin-right: 0in; margin-bottom: 0.0001pt; margin-left: 0in; font-size: 12pt; font-family: 'Times New Roman', serif; "><o:p> </o:p></div></div><div><div style="margin-top: 0in; margin-right: 0in; margin-bottom: 0.0001pt; margin-left: 0in; font-size: 12pt; font-family: 'Times New Roman', serif; ">It's hard to tell without knowing your target. Why does the allocator think there are no free registers in your register class?<o:p></o:p></div><div style="margin-top: 0in; margin-right: 0in; margin-bottom: 0.0001pt; margin-left: 0in; font-size: 12pt; font-family: 'Times New Roman', serif; "><b><i><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125); ">[Villmow, Micah] That is what I can't figure out. I am only setting the live-in's and some special registers as reserved, and with 1k vector registers, I should not be having any trouble. Somehow the register allocator thinks all registers are used, but if that is the case, it should spill to memory, and even that is failing! If I don't use sub-registers, then I don't have this<o:p></o:p></span></i></b></div><div style="margin-top: 0in; margin-right: 0in; margin-bottom: 0.0001pt; margin-left: 0in; font-size: 12pt; font-family: 'Times New Roman', serif; "><b><i><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125); ">problem, but then I really can't specify that one register class is a subclass of another.</span></i></b><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125); "><o:p></o:p></span></div></div><div><div style="margin-top: 0in; margin-right: 0in; margin-bottom: 0.0001pt; margin-left: 0in; font-size: 12pt; font-family: 'Times New Roman', serif; "><o:p> </o:p></div></div><blockquote style="margin-top: 5pt; margin-bottom: 5pt; "><div style="margin-top: 0in; margin-right: 0in; margin-bottom: 0.0001pt; margin-left: 0in; font-size: 12pt; font-family: 'Times New Roman', serif; "><span class="apple-style-span"><span style="font-size: 11.5pt; font-family: Calibri, sans-serif; ">Another question is how do I influence the spill costs? I want to make live in's</span></span><span class="apple-style-span"><span style="font-size: 13.5pt; font-family: Menlo, serif; "><o:p></o:p></span></span></div><div><div><div style="margin-top: 0in; margin-right: 0in; margin-bottom: 0.0001pt; margin-left: 0in; font-size: 12pt; font-family: 'Times New Roman', serif; "><span style="font-size: 11pt; font-family: Calibri, sans-serif; "> </span><span style="font-size: 11pt; font-family: Calibri, sans-serif; "><o:p></o:p></span></div></div><div><div style="margin-top: 0in; margin-right: 0in; margin-bottom: 0.0001pt; margin-left: 0in; font-size: 12pt; font-family: 'Times New Roman', serif; "><span style="font-size: 11pt; font-family: Calibri, sans-serif; ">infinitely expensive to spill, so any superreg or super-super-reg of the live in<o:p></o:p></span></div></div><div><div style="margin-top: 0in; margin-right: 0in; margin-bottom: 0.0001pt; margin-left: 0in; font-size: 12pt; font-family: 'Times New Roman', serif; "><span style="font-size: 11pt; font-family: Calibri, sans-serif; ">never gets allocated.<o:p></o:p></span></div></div></div></blockquote><div><div style="margin-top: 0in; margin-right: 0in; margin-bottom: 0.0001pt; margin-left: 0in; font-size: 12pt; font-family: 'Times New Roman', serif; "><o:p> </o:p></div></div></div><div style="margin-top: 0in; margin-right: 0in; margin-bottom: 0.0001pt; margin-left: 0in; font-size: 12pt; font-family: 'Times New Roman', serif; ">It's not clear what you mean here. Spill costs are assigned to virtual registers, and virtual registers don't have sub- or super-registers.<o:p></o:p></div><div><div style="margin-top: 0in; margin-right: 0in; margin-bottom: 0.0001pt; margin-left: 0in; font-size: 12pt; font-family: 'Times New Roman', serif; "><o:p> </o:p></div></div><div><div style="margin-top: 0in; margin-right: 0in; margin-bottom: 0.0001pt; margin-left: 0in; font-size: 12pt; font-family: 'Times New Roman', serif; ">If you mean linear scan's emergency spilling of physical registers, that should never happen anyway. Something else is wrong.<o:p></o:p></div><div style="margin-top: 0in; margin-right: 0in; margin-bottom: 0.0001pt; margin-left: 0in; font-size: 12pt; font-family: 'Times New Roman', serif; "><b><i><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125); ">[Villmow, Micah] Yeah, i'm hitting this assert to because I'm emergency spilling twice some times.</span></i></b></div></div></div></div></div></span></blockquote><div><br></div><div>Are you intentionally creating new virtual registers after register allocation?</div><div><br></div><div>That assert implies the live ranges of the virtual registers being created after register allocation are too big and overlap. The register scavenger constrains its problem to only a single register being scavenged at a time. The idea is to only use it when you need a temporary register with a very, very short live range (usually two or three instructions) to materialize a value into or something like that. Anything more complicated should go through the real register allocator.</div><div><br></div><div>-Jim</div><br><blockquote type="cite"><span class="Apple-style-span" style="border-collapse: separate; font-family: Helvetica; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-border-horizontal-spacing: 0px; -webkit-border-vertical-spacing: 0px; -webkit-text-decorations-in-effect: none; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px; font-size: medium; "><div lang="EN-US" link="blue" vlink="purple" style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space; "><div class="WordSection1" style="page: WordSection1; "><div style="border-top-style: none; border-right-style: none; border-bottom-style: none; border-width: initial; border-color: initial; border-left-style: solid; border-left-color: blue; border-left-width: 1.5pt; padding-top: 0in; padding-right: 0in; padding-bottom: 0in; padding-left: 4pt; position: static; z-index: auto; "><div><div style="margin-top: 0in; margin-right: 0in; margin-bottom: 0.0001pt; margin-left: 0in; font-size: 12pt; font-family: 'Times New Roman', serif; "><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125); "><o:p></o:p></span></div></div><div><div style="margin-top: 0in; margin-right: 0in; margin-bottom: 0.0001pt; margin-left: 0in; font-size: 12pt; font-family: 'Times New Roman', serif; "><o:p> </o:p></div></div><div><div style="margin-top: 0in; margin-right: 0in; margin-bottom: 0.0001pt; margin-left: 0in; font-size: 12pt; font-family: 'Times New Roman', serif; ">BTW, the new greedy register allocator is way better. It never makes mistakes!<o:p></o:p></div></div><div><div style="margin-top: 0in; margin-right: 0in; margin-bottom: 0.0001pt; margin-left: 0in; font-size: 12pt; font-family: 'Times New Roman', serif; "><o:p> </o:p></div></div><div><div style="margin-top: 0in; margin-right: 0in; margin-bottom: 0.0001pt; margin-left: 0in; font-size: 12pt; font-family: 'Times New Roman', serif; ">/jakob<o:p></o:p></div></div><div><div style="margin-top: 0in; margin-right: 0in; margin-bottom: 0.0001pt; margin-left: 0in; font-size: 12pt; font-family: 'Times New Roman', serif; "><o:p> </o:p></div></div></div></div>_______________________________________________<br>LLVM Developers mailing list<br><a href="mailto:LLVMdev@cs.uiuc.edu" style="color: blue; text-decoration: underline; ">LLVMdev@cs.uiuc.edu</a><span class="Apple-converted-space"> </span> <a href="http://llvm.cs.uiuc.edu" style="color: blue; text-decoration: underline; ">http://llvm.cs.uiuc.edu</a><br><a href="http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev" style="color: blue; text-decoration: underline; ">http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev</a><br></div></span></blockquote></div><br></body></html>