[prev in list] [next in list] [prev in thread] [next in thread]
List: llvm-dev
Subject: Re: [llvm-dev] Assert in register allocation during last chance recoloring
From: Quentin Colombet via llvm-dev <llvm-dev () lists ! llvm ! org>
Date: 2016-11-28 21:22:04
Message-ID: 935AB772-4822-49C5-949F-2360E2913321 () apple ! com
[Download RAW message or body]
[Attachment #2 (multipart/alternative)]
Hi Sanjin,
The spilling/spliting strategy for big registers is known to be weak so I am not \
surprised you run into this problem.
I'll have a closer look (sometime this week or next week) and I'll comment in the PR.
Cheers,
-Quentin
> On Nov 22, 2016, at 1:22 PM, Sanjin Sijaric via llvm-dev <llvm-dev@lists.llvm.org> \
> wrote:
> Hi,
>
> I opened the bug #31122 for this issue.
>
> There are two parts to this problem. Compiled using "llc -debug-only=regalloc \
> test.ll", the test case attached to the bug fails with
> VirtRegMap.h:119: void llvm::VirtRegMap::clearVirt(unsigned int): Assertion \
> `Virt2PhysMap[virtReg] != NO_PHYS_REG && "attempt to clear a not assigned virtual \
> register"' failed.
> The code looks like:
>
> %vreg647<def> = COPY %vreg645; QQQQPR_with_dsub_7_then_ssub_0:%vreg647 \
> QQQQPR:%vreg645 %vreg657<def> = COPY %vreg655; \
> QQQQPR_with_dsub_7_then_ssub_0:%vreg657 QQQQPR:%vreg655 %vreg679<def> = COPY \
> %vreg678; QPR_VFP2:%vreg679 QPR:%vreg678 %vreg657:dsub_7_then_ssub_0<def> = VDIVS \
> %vreg679:ssub_2, %vreg647:dsub_7_then_ssub_0, pred:14, pred:%noreg; \
> QQQQPR_with_dsub_7_then_ssub_0:%vreg657,%vreg647 QPR_VFP2:%vreg679 %vreg659<def> = \
> COPY %vreg657; QQQQPR:%vreg659 QQQQPR_with_dsub_7_then_ssub_0:%vreg657
> This problem occurs during last chance recoloring, where %vreg679 doesn't get \
> allocated (and is marked as not spillable), so last chance recoloring kicks in. It \
> tries to allocate Q0 to %vreg679, where Q0_Q1_Q2_Q3 is assigned to %vreg647, which \
> interferes with %vreg679. Upon trying to allocate a register to %vreg647, %vreg679 \
> gets evicted from Q0. But %vreg679 is a fixed register, so it shouldn't get \
> evicted. Recoloring is thus deemed successful, and upon returning from \
> tryRecoloringCandidates, we assert when trying to unassign %vreg679.
> I can get around this by moving the virtual register under consideration in \
> tryLastChanceRecoloring (%vreg679) to RS_Done stage right before the call to \
> tryRecolringCandidates, and then restoring the original stage afterward. This \
> prevents the eviction of %vreg679 during recoloring. Alternatively, I can check \
> FixedRegisters in canEvictInterference and return false.
> After the assert is gone, I run into "LLVM ERROR: ran out of registers during \
> register allocation". Increasing lcr-max-depth doesn't help.
> To get past this error, I am thinking about spilling an actual physical register if \
> last chance recoloring fails. For example,
> P = ….
>
> virtX = …. Last chance recoloring fails,
>
> … = P
>
> …. = virtX
>
> will result in something along the lines of
>
> P = ….
>
> spill P to fi#0 (original P)
> P = …. (virtX is now in P)
> ….
> Spill P to fi#1 (this is virtX)
> Reload P form from fi#0 (original P)
> … = P
> ….
> Reload P from fi#1 (this is virtX)
> = P
>
> Does anyone have any other suggestions about dealing with this problem?
>
> Thank you,
> Sanjin
>
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev@lists.llvm.org <mailto:llvm-dev@lists.llvm.org>
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev \
> <http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev>
[Attachment #5 (text/html)]
<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="">Hi Sanjin,<div class=""><br \
class=""></div><div class="">The spilling/spliting strategy for big registers is \
known to be weak so I am not surprised you run into this problem.</div><div \
class=""><br class=""></div><div class="">I'll have a closer look (sometime this week \
or next week) and I'll comment in the PR.</div><div class=""><br class=""></div><div \
class="">Cheers,</div><div class="">-Quentin</div><div class=""><br \
class=""><div><blockquote type="cite" class=""><div class="">On Nov 22, 2016, at 1:22 \
PM, Sanjin Sijaric via llvm-dev <<a href="mailto:llvm-dev@lists.llvm.org" \
class="">llvm-dev@lists.llvm.org</a>> wrote:</div><br \
class="Apple-interchange-newline"><div class=""><div class="WordSection1" \
style="page: WordSection1; font-family: Helvetica; font-size: 12px; font-style: \
normal; font-variant-caps: normal; font-weight: normal; letter-spacing: 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 style="margin: 0in 0in 0.0001pt; font-size: 11pt; font-family: Calibri, \
sans-serif;" class="">Hi,<o:p class=""></o:p></div><div style="margin: 0in 0in \
0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class=""><o:p \
class=""> </o:p></div><div style="margin: 0in 0in 0.0001pt; font-size: 11pt; \
font-family: Calibri, sans-serif;" class="">I opened the bug #31122 for this \
issue.<o:p class=""></o:p></div><div style="margin: 0in 0in 0.0001pt; font-size: \
11pt; font-family: Calibri, sans-serif;" class=""><o:p \
class=""> </o:p></div><div style="margin: 0in 0in 0.0001pt; font-size: 11pt; \
font-family: Calibri, sans-serif;" class="">There are two parts to this problem. \
Compiled using "llc -debug-only=regalloc test.ll", the test case attached to the bug \
fails with<o:p class=""></o:p></div><div style="margin: 0in 0in 0.0001pt; font-size: \
11pt; font-family: Calibri, sans-serif;" class=""><o:p \
class=""> </o:p></div><div style="margin: 0in 0in 0.0001pt; font-size: 11pt; \
font-family: Calibri, sans-serif;" class="">VirtRegMap.h:119: void \
llvm::VirtRegMap::clearVirt(unsigned int): Assertion `Virt2PhysMap[virtReg] != \
NO_PHYS_REG && "attempt to clear a not assigned virtual register"' \
failed.<o:p class=""></o:p></div><div style="margin: 0in 0in 0.0001pt; font-size: \
11pt; font-family: Calibri, sans-serif;" class=""><o:p \
class=""> </o:p></div><div style="margin: 0in 0in 0.0001pt; font-size: 11pt; \
font-family: Calibri, sans-serif;" class="">The code looks like:<o:p \
class=""></o:p></div><div style="margin: 0in 0in 0.0001pt; font-size: 11pt; \
font-family: Calibri, sans-serif;" class=""><o:p class=""> </o:p></div><div \
style="margin: 0in 0in 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" \
class=""> %vreg647<def> = COPY %vreg645; \
QQQQPR_with_dsub_7_then_ssub_0:%vreg647 QQQQPR:%vreg645<o:p class=""></o:p></div><div \
style="margin: 0in 0in 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" \
class=""> %vreg657<def> = COPY \
%vreg655; QQQQPR_with_dsub_7_then_ssub_0:%vreg657 QQQQPR:%vreg655<o:p \
class=""></o:p></div><div style="margin: 0in 0in 0.0001pt; font-size: 11pt; \
font-family: Calibri, sans-serif;" \
class=""> %vreg679<def> = COPY \
%vreg678; QPR_VFP2:%vreg679 QPR:%vreg678<o:p class=""></o:p></div><div style="margin: \
0in 0in 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" \
class=""> \
%vreg657:dsub_7_then_ssub_0<def> = VDIVS %vreg679:ssub_2, \
%vreg647:dsub_7_then_ssub_0, pred:14, pred:%noreg; \
QQQQPR_with_dsub_7_then_ssub_0:%vreg657,%vreg647 QPR_VFP2:%vreg679<o:p \
class=""></o:p></div><div style="margin: 0in 0in 0.0001pt; font-size: 11pt; \
font-family: Calibri, sans-serif;" \
class=""> %vreg659<def> = COPY \
%vreg657; QQQQPR:%vreg659 QQQQPR_with_dsub_7_then_ssub_0:%vreg657<o:p \
class=""></o:p></div><div style="margin: 0in 0in 0.0001pt; font-size: 11pt; \
font-family: Calibri, sans-serif;" class=""><o:p class=""> </o:p></div><div \
style="margin: 0in 0in 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" \
class="">This problem occurs during last chance recoloring, where %vreg679 doesn't \
get allocated (and is marked as not spillable), so last chance recoloring kicks \
in. It tries to allocate Q0 to %vreg679, where Q0_Q1_Q2_Q3 is assigned to \
%vreg647, which interferes with %vreg679. Upon trying to allocate a register to \
%vreg647, %vreg679 gets evicted from Q0. But %vreg679 is a fixed register, so \
it shouldn't get evicted. Recoloring is thus deemed successful, and upon \
returning from tryRecoloringCandidates, we assert when trying to unassign \
%vreg679. <span class="Apple-converted-space"> </span><o:p \
class=""></o:p></div><div style="margin: 0in 0in 0.0001pt; font-size: 11pt; \
font-family: Calibri, sans-serif;" class=""><o:p class=""> </o:p></div><div \
style="margin: 0in 0in 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" \
class="">I can get around this by moving the virtual register under consideration in \
tryLastChanceRecoloring (%vreg679) to RS_Done stage right before the call to \
tryRecolringCandidates, and then restoring the original stage afterward. This \
prevents the eviction of %vreg679 during recoloring. Alternatively, I can \
check FixedRegisters in canEvictInterference and return false.<o:p \
class=""></o:p></div><div style="margin: 0in 0in 0.0001pt; font-size: 11pt; \
font-family: Calibri, sans-serif;" class=""><o:p class=""> </o:p></div><div \
style="margin: 0in 0in 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" \
class="">After the assert is gone, I run into "LLVM ERROR: ran out of registers \
during register allocation". Increasing lcr-max-depth doesn't help.<o:p \
class=""></o:p></div><div style="margin: 0in 0in 0.0001pt; font-size: 11pt; \
font-family: Calibri, sans-serif;" class=""><o:p class=""> </o:p></div><div \
style="margin: 0in 0in 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" \
class="">To get past this error, I am thinking about spilling an actual physical \
register if last chance recoloring fails. For example,<o:p \
class=""></o:p></div><div style="margin: 0in 0in 0.0001pt; font-size: 11pt; \
font-family: Calibri, sans-serif;" class=""><o:p class=""> </o:p></div><div \
style="margin: 0in 0in 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" \
class="">P = ….<o:p class=""></o:p></div><div style="margin: 0in 0in 0.0001pt; \
font-size: 11pt; font-family: Calibri, sans-serif;" class=""><o:p \
class=""> </o:p></div><div style="margin: 0in 0in 0.0001pt; font-size: 11pt; \
font-family: Calibri, sans-serif;" class="">virtX = …. Last chance recoloring \
fails,<span class="Apple-converted-space"> </span><o:p class=""></o:p></div><div \
style="margin: 0in 0in 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" \
class=""><o:p class=""> </o:p></div><div style="margin: 0in 0in 0.0001pt; \
font-size: 11pt; font-family: Calibri, sans-serif;" class="">… = P<o:p \
class=""></o:p></div><div style="margin: 0in 0in 0.0001pt; font-size: 11pt; \
font-family: Calibri, sans-serif;" class=""><o:p class=""> </o:p></div><div \
style="margin: 0in 0in 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" \
class="">…. = virtX<o:p class=""></o:p></div><div style="margin: 0in 0in 0.0001pt; \
font-size: 11pt; font-family: Calibri, sans-serif;" class=""><o:p \
class=""> </o:p></div><div style="margin: 0in 0in 0.0001pt; font-size: 11pt; \
font-family: Calibri, sans-serif;" class="">will result in something along the lines \
of<o:p class=""></o:p></div><div style="margin: 0in 0in 0.0001pt; font-size: 11pt; \
font-family: Calibri, sans-serif;" class=""><o:p class=""> </o:p></div><div \
style="margin: 0in 0in 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" \
class="">P = ….<o:p class=""></o:p></div><div style="margin: 0in 0in 0.0001pt; \
font-size: 11pt; font-family: Calibri, sans-serif;" class=""><o:p \
class=""> </o:p></div><div style="margin: 0in 0in 0.0001pt; font-size: 11pt; \
font-family: Calibri, sans-serif;" class="">spill P to fi#0 (original P)<o:p \
class=""></o:p></div><div style="margin: 0in 0in 0.0001pt; font-size: 11pt; \
font-family: Calibri, sans-serif;" class="">P = …. (virtX is now in P)<o:p \
class=""></o:p></div><div style="margin: 0in 0in 0.0001pt; font-size: 11pt; \
font-family: Calibri, sans-serif;" class="">….<o:p class=""></o:p></div><div \
style="margin: 0in 0in 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" \
class="">Spill P to fi#1 (this is virtX)<o:p class=""></o:p></div><div style="margin: \
0in 0in 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class="">Reload \
P form from fi#0 (original P)<o:p class=""></o:p></div><div style="margin: 0in 0in \
0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class="">… = P<o:p \
class=""></o:p></div><div style="margin: 0in 0in 0.0001pt; font-size: 11pt; \
font-family: Calibri, sans-serif;" class="">….<o:p class=""></o:p></div><div \
style="margin: 0in 0in 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" \
class="">Reload P from fi#1 (this is virtX)<o:p class=""></o:p></div><div \
style="margin: 0in 0in 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" \
class="">= P<o:p class=""></o:p></div><div style="margin: 0in 0in 0.0001pt; \
font-size: 11pt; font-family: Calibri, sans-serif;" class=""><o:p \
class=""> </o:p></div><div style="margin: 0in 0in 0.0001pt; font-size: 11pt; \
font-family: Calibri, sans-serif;" class="">Does anyone have any other suggestions \
about dealing with this problem?<o:p class=""></o:p></div><div style="margin: 0in 0in \
0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class=""><o:p \
class=""> </o:p></div><div style="margin: 0in 0in 0.0001pt; font-size: 11pt; \
font-family: Calibri, sans-serif;" class="">Thank you,<o:p class=""></o:p></div><div \
style="margin: 0in 0in 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" \
class="">Sanjin<o:p class=""></o:p></div><div style="margin: 0in 0in 0.0001pt; \
font-size: 11pt; font-family: Calibri, sans-serif;" class=""><o:p \
class=""> </o:p></div></div><span style="font-family: Helvetica; font-size: \
12px; font-style: normal; font-variant-caps: normal; font-weight: normal; \
letter-spacing: 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; float: none; display: inline !important;" \
class="">_______________________________________________</span><br \
style="font-family: Helvetica; font-size: 12px; font-style: normal; \
font-variant-caps: normal; font-weight: normal; letter-spacing: 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=""><span \
style="font-family: Helvetica; font-size: 12px; font-style: normal; \
font-variant-caps: normal; font-weight: normal; letter-spacing: 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; float: none; \
display: inline !important;" class="">LLVM Developers mailing list</span><br \
style="font-family: Helvetica; font-size: 12px; font-style: normal; \
font-variant-caps: normal; font-weight: normal; letter-spacing: 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=""><a \
href="mailto:llvm-dev@lists.llvm.org" style="color: rgb(149, 79, 114); \
text-decoration: underline; font-family: Helvetica; font-size: 12px; font-style: \
normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; \
orphans: auto; text-align: start; text-indent: 0px; text-transform: none; \
white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-size-adjust: auto; \
-webkit-text-stroke-width: 0px;" class="">llvm-dev@lists.llvm.org</a><br \
style="font-family: Helvetica; font-size: 12px; font-style: normal; \
font-variant-caps: normal; font-weight: normal; letter-spacing: 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=""><a \
href="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" style="color: rgb(149, \
79, 114); text-decoration: underline; font-family: Helvetica; font-size: 12px; \
font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: \
normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; \
white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-size-adjust: auto; \
-webkit-text-stroke-width: 0px;" \
class="">http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a></div></blockquote></div><br \
class=""></div></body></html>
[Attachment #6 (text/plain)]
_______________________________________________
LLVM Developers mailing list
llvm-dev@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
[prev in list] [next in list] [prev in thread] [next in thread]
Configure |
About |
News |
Add a list |
Sponsored by KoreLogic