thr3ads.net - llvm dev - [LLVMdev] Assert in live update from MI scheduler. [Jun 2012]

If this information is useful, please help other people find it:
Share via:

Andrew Trick

2012-Jun-13 18:38 UTC

[LLVMdev] Assert in live update from MI scheduler.

On Jun 13, 2012, at 10:49 AM, Sergei Larin <slarin at codeaurora.org>
wrote:> So if this early exit is taken:
> 
>  // SSA defs do not have output/anti dependencies.
>  // The current operand is a def, so we have at least one.
>  if (llvm::next(MRI.def_begin(Reg)) == MRI.def_end())
>    return;
> 
> we do not ever get to this point:
> 
>   VRegDefs.insert(VReg2SUnit(Reg, SU));
> 
> But later, when checking for anti dependency for another MI here:
> 
> void ScheduleDAGInstrs::addVRegUseDeps(SUnit *SU, unsigned OperIdx) {
> ...
>  // Add antidependence to the following def of the vreg it uses.
>  VReg2SUnitMap::iterator DefI = VRegDefs.find(Reg);
>  if (DefI != VRegDefs.end() && DefI->SU != SU)
>    DefI->SU->addPred(SDep(SU, SDep::Anti, 0, Reg));
> 
> We will never find that def in VRegDefs.find(Reg) even though it exists.
> 
> I know this has been working for a while, but I am still missing something
> here.
> What is this statement 
> 
> if (llvm::next(MRI.def_begin(Reg)) == MRI.def_end())
> 
> should guarantee? From it there must be more than one definition in MRI.def
> for that reg for it to work... 
> 
> 
> 
> 
> To connect it to the original example... When parsing (BU order) this
> instruction:
> 
> SU(1):   %vreg10<def> = LDriw %vreg9<kill>, 0;
mem:LD4[%stack.0.in]
> 
> The %vreg10<def> never inserted to VRegDefs, so with next
instruction:
> 
> SU(0):   %vreg1<def> = COPY %vreg10<kill>;
IntRegs:%vreg1,%vreg10
> 
> Anti dep on %vreg10 is never created.

Thanks for the detailed explanation! My understanding is that COPY
%vreg10<kill> is illegal because is has no reaching def on all paths
(LDriw is the only def).

Now, the (llvm::next(MRI.def_begin(Reg)) == MRI.def_end()) check is not really
sufficient to test SSA in the presence of undefined operands. However, I thought
we would have an IMPLICIT_DEF of the vreg in that case, even after the phi is
removed. That right Jakob? Otherwise we I think we should somehow mark the vreg
as being undefined.

Anyway, I added an assert to catch this problem (see below), and it never
triggered on X86. So my guess is that you have incorrect IR coming in. Can you
check where %vreg10 is defined. Before coalescing, was it a phi with an
<undef> operand?

It is safe to workaround the problem by removing the early exit following the
SSA check.

-Andy

--- a/lib/CodeGen/ScheduleDAGInstrs.cpp
+++ b/lib/CodeGen/ScheduleDAGInstrs.cpp
@@ -413,9 +413,11 @@ void ScheduleDAGInstrs::addVRegDefDeps(SUnit *SU, unsigned
OperIdx) {
 
   // SSA defs do not have output/anti dependencies.
   // The current operand is a def, so we have at least one.
-  if (llvm::next(MRI.def_begin(Reg)) == MRI.def_end())
+  if (llvm::next(MRI.def_begin(Reg)) == MRI.def_end()) {
+    //!!!
+    VRegDefs.insert(VReg2SUnit(Reg, SU));
     return;
-
+  }
   // Add output dependence to the next nearest def of this vreg.
   //
   // Unless this definition is dead, the output dependence should be
@@ -479,8 +481,10 @@ void ScheduleDAGInstrs::addVRegUseDeps(SUnit *SU, unsigned
OperIdx) {
 
   // Add antidependence to the following def of the vreg it uses.
   VReg2SUnitMap::iterator DefI = VRegDefs.find(Reg);
-  if (DefI != VRegDefs.end() && DefI->SU != SU)
+  if (DefI != VRegDefs.end() && DefI->SU != SU) {
+    assert(llvm::next(MRI.def_begin(Reg)) != MRI.def_end() &&
"SINGLEDEF");
     DefI->SU->addPred(SDep(SU, SDep::Anti, 0, Reg));
+  }

-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20120613/fa07b431/attachment.html>

Sergei Larin

2012-Jun-13 20:15 UTC

head link

[LLVMdev] Assert in live update from MI scheduler.

Andy, 

 

  You are probably right here - look at this - before phi elimination this
code looks much more sane:

 

# *** IR Dump After Live Variable Analysis ***:

# Machine code for function push: SSA

Function Live Outs: %R0

 

BB#0: derived from LLVM BB %entry

    %vreg5<def> = IMPLICIT_DEF; IntRegs:%vreg5

    %vreg4<def> = TFRI_V4 <ga:@xx_stack>; IntRegs:%vreg4

    Successors according to CFG: BB#1

 

BB#1: derived from LLVM BB %for.cond

    Predecessors according to CFG: BB#0 BB#1

    %vreg0<def> = PHI %vreg4, <BB#0>, %vreg3, <BB#1>;
IntRegs:%vreg0,%vreg4,%vreg3

    %vreg1<def> = PHI %vreg5, <BB#0>, %vreg2, <BB#1>;
IntRegs:%vreg1,%vreg5,%vreg2

    %vreg2<def> = LDriw %vreg0<kill>, 0; mem:LD4[%stack.0.in]
IntRegs:%vreg2,%vreg0

    %vreg3<def> = ADD_ri %vreg2, 8; IntRegs:%vreg3,%vreg2

    %vreg6<def> = CMPEQri %vreg2, 0; PredRegs:%vreg6 IntRegs:%vreg2

    JMP_cNot %vreg6<kill>, <BB#1>, %PC<imp-def>;
PredRegs:%vreg6

    JMP <BB#2>

    Successors according to CFG: BB#2 BB#1

 

BB#2: derived from LLVM BB %for.end

    Predecessors according to CFG: BB#1

    %vreg7<def> = LDriw %vreg1<kill>, 0;
mem:LD4[%first1](tbaa=!"any
pointer") IntRegs:%vreg7,%vreg1

    STriw_GP <ga:@yy_instr>, 0, %vreg7<kill>;
mem:ST4[@yy_instr](tbaa=!"any
pointer") IntRegs:%vreg7

    %vreg8<def> = IMPLICIT_DEF; IntRegs:%vreg8

    %R0<def> = COPY %vreg8<kill>; IntRegs:%vreg8

    JMPR %PC<imp-def>, %R31<imp-use>, %R0<imp-use,kill>

 

Right after the dead vreg is introduced:

 

# *** IR Dump After Eliminate PHI nodes for register allocation ***:

# Machine code for function push: Post SSA

Function Live Outs: %R0

 

BB#0: derived from LLVM BB %entry

    %vreg4<def> = TFRI_V4 <ga:@xx_stack>; IntRegs:%vreg4

    %vreg9<def> = COPY %vreg4<kill>; IntRegs:%vreg9,%vreg4

    Successors according to CFG: BB#1

 

BB#1: derived from LLVM BB %for.cond

    Predecessors according to CFG: BB#0 BB#1

    %vreg0<def> = COPY %vreg9<kill>; IntRegs:%vreg0,%vreg9

    %vreg1<def> = COPY %vreg10<kill>; IntRegs:%vreg1,%vreg10
<<<<<<<<<<<<<<<<<<<<<<<<<<<
Not defined on first iteration..

    %vreg2<def> = LDriw %vreg0<kill>, 0; mem:LD4[%stack.0.in]
IntRegs:%vreg2,%vreg0

    %vreg3<def> = ADD_ri %vreg2, 8; IntRegs:%vreg3,%vreg2

    %vreg6<def> = CMPEQri %vreg2, 0; PredRegs:%vreg6 IntRegs:%vreg2

    %vreg9<def> = COPY %vreg3<kill>; IntRegs:%vreg9,%vreg3

    %vreg10<def> = COPY %vreg2<kill>; IntRegs:%vreg10,%vreg2

    JMP_cNot %vreg6<kill>, <BB#1>, %PC<imp-def>;
PredRegs:%vreg6

    JMP <BB#2>

    Successors according to CFG: BB#2 BB#1

 

BB#2: derived from LLVM BB %for.end

    Predecessors according to CFG: BB#1

    %vreg7<def> = LDriw %vreg1<kill>, 0;
mem:LD4[%first1](tbaa=!"any
pointer") IntRegs:%vreg7,%vreg1

    STriw_GP <ga:@yy_instr>, 0, %vreg7<kill>;
mem:ST4[@yy_instr](tbaa=!"any
pointer") IntRegs:%vreg7

    %vreg8<def> = IMPLICIT_DEF; IntRegs:%vreg8

    %R0<def> = COPY %vreg8<kill>; IntRegs:%vreg8

    JMPR %PC<imp-def>, %R31<imp-use>, %R0<imp-use,kill>

 

# End machine code for function push.

 

So the problem is elsewhere after all. 

 

I'll keep on digging. Thanks.

 

Sergei

 

--

Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum.

 

From: Andrew Trick [mailto:atrick at apple.com] 
Sent: Wednesday, June 13, 2012 1:39 PM
To: Sergei Larin; Jakob Olesen
Cc: llvmdev at cs.uiuc.edu List
Subject: Re: [LLVMdev] Assert in live update from MI scheduler.

 

On Jun 13, 2012, at 10:49 AM, Sergei Larin <slarin at codeaurora.org>
wrote:

So if this early exit is taken:

 // SSA defs do not have output/anti dependencies.
 // The current operand is a def, so we have at least one.
 if (llvm::next(MRI.def_begin(Reg)) == MRI.def_end())
   return;

we do not ever get to this point:

  VRegDefs.insert(VReg2SUnit(Reg, SU));

But later, when checking for anti dependency for another MI here:

void ScheduleDAGInstrs::addVRegUseDeps(SUnit *SU, unsigned OperIdx) {
...
 // Add antidependence to the following def of the vreg it uses.
 VReg2SUnitMap::iterator DefI = VRegDefs.find(Reg);
 if (DefI != VRegDefs.end() && DefI->SU != SU)
   DefI->SU->addPred(SDep(SU, SDep::Anti, 0, Reg));

We will never find that def in VRegDefs.find(Reg) even though it exists.

I know this has been working for a while, but I am still missing something
here.
What is this statement 

if (llvm::next(MRI.def_begin(Reg)) == MRI.def_end())

should guarantee? From it there must be more than one definition in MRI.def
for that reg for it to work... 




To connect it to the original example... When parsing (BU order) this
instruction:

SU(1):   %vreg10<def> = LDriw %vreg9<kill>, 0; mem:LD4[%stack.0.in]

The %vreg10<def> never inserted to VRegDefs, so with next instruction:

SU(0):   %vreg1<def> = COPY %vreg10<kill>; IntRegs:%vreg1,%vreg10

Anti dep on %vreg10 is never created.

 

 

Thanks for the detailed explanation! My understanding is that COPY
%vreg10<kill> is illegal because is has no reaching def on all paths
(LDriw
is the only def). 

 

Now, the (llvm::next(MRI.def_begin(Reg)) == MRI.def_end()) check is not
really sufficient to test SSA in the presence of undefined operands.
However, I thought we would have an IMPLICIT_DEF of the vreg in that case,
even after the phi is removed. That right Jakob? Otherwise we I think we
should somehow mark the vreg as being undefined.

 

Anyway, I added an assert to catch this problem (see below), and it never
triggered on X86. So my guess is that you have incorrect IR coming in. Can
you check where %vreg10 is defined. Before coalescing, was it a phi with an
<undef> operand?

 

It is safe to workaround the problem by removing the early exit following
the SSA check.

 

-Andy

 

--- a/lib/CodeGen/ScheduleDAGInstrs.cpp

+++ b/lib/CodeGen/ScheduleDAGInstrs.cpp

@@ -413,9 +413,11 @@ void ScheduleDAGInstrs::addVRegDefDeps(SUnit *SU,
unsigned OperIdx) {

 

   // SSA defs do not have output/anti dependencies.

   // The current operand is a def, so we have at least one.

-  if (llvm::next(MRI.def_begin(Reg)) == MRI.def_end())

+  if (llvm::next(MRI.def_begin(Reg)) == MRI.def_end()) {

+    //!!!

+    VRegDefs.insert(VReg2SUnit(Reg, SU));

     return;

-

+  }

   // Add output dependence to the next nearest def of this vreg.

   //

   // Unless this definition is dead, the output dependence should be

@@ -479,8 +481,10 @@ void ScheduleDAGInstrs::addVRegUseDeps(SUnit *SU,
unsigned OperIdx) {

 

   // Add antidependence to the following def of the vreg it uses.

   VReg2SUnitMap::iterator DefI = VRegDefs.find(Reg);

-  if (DefI != VRegDefs.end() && DefI->SU != SU)

+  if (DefI != VRegDefs.end() && DefI->SU != SU) {

+    assert(llvm::next(MRI.def_begin(Reg)) != MRI.def_end() &&
"SINGLEDEF");

     DefI->SU->addPred(SDep(SU, SDep::Anti, 0, Reg));

+  }

 

-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20120613/fd3d1486/attachment.html>

Andrew Trick

2012-Jun-13 20:28 UTC

head link

[LLVMdev] Assert in live update from MI scheduler.

On Jun 13, 2012, at 1:15 PM, Sergei Larin <slarin at codeaurora.org>
wrote:
> Andy,
>  
>   You are probably right here – look at this – before phi elimination this
code looks much more sane:
>  
> # *** IR Dump After Live Variable Analysis ***:
> # Machine code for function push: SSA
> Function Live Outs: %R0
>  
> BB#0: derived from LLVM BB %entry
>     %vreg5<def> = IMPLICIT_DEF; IntRegs:%vreg5
>     %vreg4<def> = TFRI_V4 <ga:@xx_stack>; IntRegs:%vreg4
>     Successors according to CFG: BB#1
>  
> BB#1: derived from LLVM BB %for.cond
>     Predecessors according to CFG: BB#0 BB#1
>     %vreg0<def> = PHI %vreg4, <BB#0>, %vreg3, <BB#1>;
IntRegs:%vreg0,%vreg4,%vreg3
>     %vreg1<def> = PHI %vreg5, <BB#0>, %vreg2, <BB#1>;
IntRegs:%vreg1,%vreg5,%vreg2
>     %vreg2<def> = LDriw %vreg0<kill>, 0; mem:LD4[%stack.0.in]
IntRegs:%vreg2,%vreg0
>     %vreg3<def> = ADD_ri %vreg2, 8; IntRegs:%vreg3,%vreg2
>     %vreg6<def> = CMPEQri %vreg2, 0; PredRegs:%vreg6 IntRegs:%vreg2
>     JMP_cNot %vreg6<kill>, <BB#1>, %PC<imp-def>;
PredRegs:%vreg6
>     JMP <BB#2>
>     Successors according to CFG: BB#2 BB#1
>  
> BB#2: derived from LLVM BB %for.end
>     Predecessors according to CFG: BB#1
>     %vreg7<def> = LDriw %vreg1<kill>, 0;
mem:LD4[%first1](tbaa=!"any pointer") IntRegs:%vreg7,%vreg1
>     STriw_GP <ga:@yy_instr>, 0, %vreg7<kill>;
mem:ST4[@yy_instr](tbaa=!"any pointer") IntRegs:%vreg7
>     %vreg8<def> = IMPLICIT_DEF; IntRegs:%vreg8
>     %R0<def> = COPY %vreg8<kill>; IntRegs:%vreg8
>     JMPR %PC<imp-def>, %R31<imp-use>, %R0<imp-use,kill>
>  
> Right after the dead vreg is introduced:
>  
> # *** IR Dump After Eliminate PHI nodes for register allocation ***:
> # Machine code for function push: Post SSA
> Function Live Outs: %R0
>  
> BB#0: derived from LLVM BB %entry
>     %vreg4<def> = TFRI_V4 <ga:@xx_stack>; IntRegs:%vreg4
>     %vreg9<def> = COPY %vreg4<kill>; IntRegs:%vreg9,%vreg4
>     Successors according to CFG: BB#1
>  
> BB#1: derived from LLVM BB %for.cond
>     Predecessors according to CFG: BB#0 BB#1
>     %vreg0<def> = COPY %vreg9<kill>; IntRegs:%vreg0,%vreg9
>     %vreg1<def> = COPY %vreg10<kill>; IntRegs:%vreg1,%vreg10
<<<<<<<<<<<<<<<<<<<<<<<<<<<
Not defined on first iteration….
>     %vreg2<def> = LDriw %vreg0<kill>, 0; mem:LD4[%stack.0.in]
IntRegs:%vreg2,%vreg0
>     %vreg3<def> = ADD_ri %vreg2, 8; IntRegs:%vreg3,%vreg2
>     %vreg6<def> = CMPEQri %vreg2, 0; PredRegs:%vreg6 IntRegs:%vreg2
>     %vreg9<def> = COPY %vreg3<kill>; IntRegs:%vreg9,%vreg3
>     %vreg10<def> = COPY %vreg2<kill>; IntRegs:%vreg10,%vreg2
>     JMP_cNot %vreg6<kill>, <BB#1>, %PC<imp-def>;
PredRegs:%vreg6
>     JMP <BB#2>
>     Successors according to CFG: BB#2 BB#1
>  
> BB#2: derived from LLVM BB %for.end
>     Predecessors according to CFG: BB#1
>     %vreg7<def> = LDriw %vreg1<kill>, 0;
mem:LD4[%first1](tbaa=!"any pointer") IntRegs:%vreg7,%vreg1
>     STriw_GP <ga:@yy_instr>, 0, %vreg7<kill>;
mem:ST4[@yy_instr](tbaa=!"any pointer") IntRegs:%vreg7
>     %vreg8<def> = IMPLICIT_DEF; IntRegs:%vreg8
>     %R0<def> = COPY %vreg8<kill>; IntRegs:%vreg8
>     JMPR %PC<imp-def>, %R31<imp-use>, %R0<imp-use,kill>
>  
> # End machine code for function push.
>  
> So the problem is elsewhere after all…
Sergei,

If you don't want an undefined variable here, that's something you
should look into. Otherwise, the machine code before phi elimination looks ok.
Phi elimination is not doing everything I would like it to do in this case.
I'll have to try constructing a test case by hand. Until I figure out the
right fix, you may want to work around by disabling the SSA check in the
scheduler.

Thanks
-Andy


-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20120613/01a87da6/attachment.html>

Reasonably Related Threads

Search for more reasonably related threads

llvm dev - Jun 2012 - [LLVMdev] Assert in live update from MI scheduler.

[LLVMdev] Assert in live update from MI scheduler.

[LLVMdev] Assert in live update from MI scheduler.

[LLVMdev] Assert in live update from MI scheduler.

Reasonably Related Threads