[LLVMdev] Virtual register def doesn't dominate all uses

[Boris Boesler]

Hi!

During my backend development I get the error message for some tests:
*** Bad machine code: Virtual register def doesn't dominate all uses. ***

(C source-code, byte-code disassembly and printed machine code at the end of the email)

The first USE of vreg4 in BB#1 has no previous DEF in BB#0 or #1. But why? I can't see how the LLVM byte-code is transformed to the lower machine code.

One possible reason could be that I haven't implemented all operations, eg I didn't implement MUL at this stage. Their "state" is LEGAL and not CUSTOM or EXPAND. But it fails with implemented operations as well.

What did I do wrong? Missing implementation for some operations? What did I miss to implement?

Thanks in advance,
Boris

----8<----

C source-code:
int simple_loop(int end_loop_index)
{
int sum = 0;
for(int i = 0; i < end_loop_index; i++) {
sum += i;
}
return(sum);
}


LLVm byte-code disassembly:
; Function Attrs: nounwind readnone
define i32 @simple_loop(i32 %end_loop_index) #1 {
entry:
%cmp4 = icmp sgt i32 %end_loop_index, 0
br i1 %cmp4, label %for.cond.for.end_crit_edge, label %for.end

for.cond.for.end_crit_edge: ; preds = %entry
%0 = add i32 %end_loop_index, -2
%1 = add i32 %end_loop_index, -1
%2 = zext i32 %0 to i33
%3 = zext i32 %1 to i33
%4 = mul i33 %3, %2
%5 = lshr i33 %4, 1
%6 = trunc i33 %5 to i32
%7 = add i32 %6, %end_loop_index
%8 = add i32 %7, -1
br label %for.end

for.end: ; preds = %for.cond.for.end_crit_edge, %entry
%sum.0.lcssa = phi i32 [ %8, %for.cond.for.end_crit_edge ], [ 0, %entry ]
ret i32 %sum.0.lcssa
}


The emitted blocks are:
Function Live Ins: %R0 in %vreg2

BB#0: derived from LLVM BB %entry
Live Ins: %R0
%vreg2<def> = COPY %R0; IntRegs:%vreg2
%vreg3<def> = MV 0; SRegs:%vreg3
CMP %vreg2, 1, %FLAG<imp-def>; IntRegs:%vreg2
%vreg6<def> = COPY %vreg3; SRegs:%vreg6,%vreg3
BR_cc <BB#2>, 20, %FLAG<imp-use,kill>
BR <BB#1>
Successors according to CFG: BB#1(20) BB#2(12)

BB#1: derived from LLVM BB %for.cond.for.end_crit_edge
Predecessors according to CFG: BB#0
%vreg4<def> = MV %vreg4; IntRegs:%vreg4
%vreg5<def> = ADD %vreg4<kill>, -1; IntRegs:%vreg5,%vreg4
%vreg0<def> = COPY %vreg5<kill>; SRegs:%vreg0 IntRegs:%vreg5
%vreg6<def> = COPY %vreg0; SRegs:%vreg6,%vreg0
Successors according to CFG: BB#2

BB#2: derived from LLVM BB %for.end
Predecessors according to CFG: BB#0 BB#1
%vreg1<def> = COPY %vreg6<kill>; SRegs:%vreg1,%vreg6
%R0<def> = COPY %vreg1; SRegs:%vreg1
RETURN %R0<imp-use>

# End machine code for function simple_loop.

*** Bad machine code: Virtual register def doesn't dominate all uses. ***
- function: simple_loop
- basic block: BB#1 for.cond.for.end_crit_edge (0x7fd7cb025250)
- instruction: %vreg4<def> = MV %vreg4; IntRegs:%vreg4
LLVM ERROR: Found 1 machine code errors.


_______________________________________________
LLVM Developers mailing list
LLV...@cs.uiuc.edu http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

[Quentin Colombet]

Hi Boris,

I don’t see any phis in your machine code whereas the IR had some. This means you are already pretty late in the pipeline of the backend (i.e., after SSA form has been deconstructed).
Do you have any custom pass between instruction selection and the PHIElimination pass?

If so, I would look into them.

Cheers,
-Quentin

[Boris Boesler]

Hi Quentin,

yes, this happens quite late. With the Option --debug-pass=Structure it's in or after "Assembly Printer".
I do have a very simple DAGToDAGISel::Select() method:

SDNode *MyTargetDAGToDAGISel::Select(SDNode *N)
{
SDLoc dl(N);
// default implementation
if (N -> isMachineOpcode()) {
N -> setNodeId(-1);
return NULL; // Already selected.
}
SDNode *res = SelectCode(N);
return res;
}

Is that too simple? There are no further passes that eliminate anything.

Anyway, I have another test program, that could point to my bug:

int formal_args_3(int p1, int p2, int p3)
{
int v1 = p1;
int v2 = p2;
int v3 = p3;
int res = v1 + v2;
return(res);
}

I can compile this test and I get correct code. With option -view-sched-dags I can verify that all arguments are stored in the stack-frame, the local variables are initialized (several store operations in stack-frame) and the return value is evaluated.

But if I use the statement "int res = v1 + v2 + v3;" something strange happens: all arguments are stored in the stack-frame and the local variables are initialized. Now, the variables v1 and v2 are loaded, but they are not used (no ADD instructions) and a MOVE instruction register to register is generated that uses itself as an operand. This register should be stored and should be used as function result.

Well, the LOAD instruction uses another register class for the destination register than the ADD instruction uses for its operands, but both classes share some registers. That should not be a problem.

Any hints where I can search for my bug?

Thanks,
Boris

[Quentin Colombet]

Hi Boris,

On Oct 29, 2014, at 10:35 AM, Boris Boesler <bae...@gmx.de> wrote:

> Hi Quentin,
>
> yes, this happens quite late. With the Option --debug-pass=Structure it's in or after "Assembly Printer".
> I do have a very simple DAGToDAGISel::Select() method:
>
> SDNode *MyTargetDAGToDAGISel::Select(SDNode *N)
> {
> SDLoc dl(N);
> // default implementation
> if (N -> isMachineOpcode()) {
> N -> setNodeId(-1);
> return NULL; // Already selected.
> }
> SDNode *res = SelectCode(N);
> return res;
> }
>
> Is that too simple? There are no further passes that eliminate anything.
>
> Anyway, I have another test program, that could point to my bug:
>
> int formal_args_3(int p1, int p2, int p3)
> {
> int v1 = p1;
> int v2 = p2;
> int v3 = p3;
> int res = v1 + v2;
> return(res);
> }
>
> I can compile this test and I get correct code. With option -view-sched-dags I can verify that all arguments are stored in the stack-frame, the local variables are initialized (several store operations in stack-frame) and the return value is evaluated.
>
> But if I use the statement "int res = v1 + v2 + v3;" something strange happens: all arguments are stored in the stack-frame and the local variables are initialized. Now, the variables v1 and v2 are loaded, but they are not used (no ADD instructions) and a MOVE instruction register to register is generated that uses itself as an operand. This register should be stored and should be used as function result.
>
> Well, the LOAD instruction uses another register class for the destination register than the ADD instruction uses for its operands, but both classes share some registers. That should not be a problem.

Like you said, that shouldn’t be a problem.

>
> Any hints where I can search for my bug?

Try using -print-machineinstrs and check where the Machine IR diverge from what you were expected.
Then, you can use -debug-only <the offending pass> to have more details.

Cheers,
-Quentin

[Boris Boesler]

Hi Quentin,

I added some debug output (N->dump()) in ::Select(SDNode*N) and compared it to the dot/Graphviz output (-view-legalize-types-dags; the last one with correct code). I found out, that some SDNodes are not passed to the ::Select(SDNode*N), approximately 11 nodes are missing. The first add-node (v1+v2) is missing.

Is it normal that not all nodes are passes to ::Select()?

Thanks,
Boris

[Quentin Colombet]

On Oct 31, 2014, at 11:00 AM, Boris Boesler <bae...@gmx.de> wrote:

> Hi Quentin,
>

> I added some debug output (N->dump()) in ::Select(SDNode*N) and compared it to the dot/Graphviz output (-view-legalize-types-dags; the last one with correct code). I found out, that some SDNodes are not passed to the ::Select(SDNode*N), approximately 11 nodes are missing. The first add-node (v1+v2) is missing.
>
> Is it normal that not all nodes are passes to ::Select()?
>

Does not sound right!

They should be selected, unless they are dead (i.e., no uses).

Have you looked to the others dag (view-isel-dags in particular).

-Quentin

[Boris Boesler]

Hi Quentin,

Am 01.11.2014 um 00:39 schrieb Quentin Colombet <qcol...@apple.com>:

>
> On Oct 31, 2014, at 11:00 AM, Boris Boesler <bae...@gmx.de> wrote:
>
>> Hi Quentin,
>>
>> I added some debug output (N->dump()) in ::Select(SDNode*N) and compared it to the dot/Graphviz output (-view-legalize-types-dags; the last one with correct code). I found out, that some SDNodes are not passed to the ::Select(SDNode*N), approximately 11 nodes are missing. The first add-node (v1+v2) is missing.
>>
>> Is it normal that not all nodes are passes to ::Select()?
>>
>
> Does not sound right!
>
> They should be selected, unless they are dead (i.e., no uses).
>
> Have you looked to the others dag (view-isel-dags in particular).

Yes, the dags in view-isel-dags and view-legalize-types-dags are correct (the add operations are here and are their results are used) and the dags are the same.

Boris

[Quentin Colombet]

On Nov 1, 2014, at 2:19 AM, Boris Boesler <bae...@gmx.de> wrote:

Hi Quentin,

Am 01.11.2014 um 00:39 schrieb Quentin Colombet <qcol...@apple.com>:

On Oct 31, 2014, at 11:00 AM, Boris Boesler <bae...@gmx.de> wrote:

Hi Quentin,

I added some debug output (N->dump()) in ::Select(SDNode*N) and compared it to the dot/Graphviz output (-view-legalize-types-dags; the last one with correct code). I found out, that some SDNodes are not passed to the ::Select(SDNode*N), approximately 11 nodes are missing. The first add-node (v1+v2) is missing.

Is it normal that not all nodes are passes to ::Select()?

Does not sound right!

They should be selected, unless they are dead (i.e., no uses).

Have you looked to the others dag (view-isel-dags in particular).

Yes, the dags in view-isel-dags and view-legalize-types-dags are correct (the add operations are here and are their results are used) and the dags are the same.

And what about view-sched-dags?

This one should give you what has been selected. So if this is not correct, you have indeed a problem in the selection problem.

If that is the case, you can use -debug-only=isel to help you figuring out what is the problem.

-Quentin

[Boris Boesler]

Hi Quentin,

>> Yes, the dags in view-isel-dags and view-legalize-types-dags are correct (the add operations are here and are their results are used) and the dags are the same.
>
> And what about view-sched-dags?

The DAG looks like I described below (*)

> This one should give you what has been selected. So if this is not correct, you have indeed a problem in the selection problem.
> If that is the case, you can use -debug-only=isel to help you figuring out what is the problem.

This is the add node (sum + v3) from the dot file (-view-isel-dags):

Node0x7fef2a033610 [shape=record,shape=Mrecord,label="{{<s0>0|<s1>1}|add [ORD=21] [ID=29]|0x7fef2a033610|{<d0>i32}}"];

The debug output (-debug-only=isel) is:

ISEL: Starting pattern match on root node: 0x7fef2a033610: i32 = add 0x7fef2a033410, 0x7fef2a032f10 [ORD=21] [ID=29]

Skipped scope entry (due to false predicate) at index 3, continuing at 2566
Match failed at index 2575
Continuing at 2628
Match failed at index 2639
Continuing at 2659
Match failed at index 2663
Continuing at 2700
Continuing at 2701
Continuing at 2702
Match failed at index 2703
Continuing at 2817
Match failed at index 2818
Continuing at 2901
Match failed at index 2902
Continuing at 2985
Match failed at index 2986
Continuing at 3100
Match failed at index 3101
Continuing at 3215
Match failed at index 3216
Continuing at 3330
Match failed at index 3331
Continuing at 3445
Match failed at index 3447
Continuing at 3591
Match failed at index 3592
Continuing at 3706
Match failed at index 3707
Continuing at 3790
Match failed at index 3791
Continuing at 3874
Match failed at index 3875
Continuing at 3958
Match failed at index 3959
Continuing at 4046
Match failed at index 4047
Continuing at 4081
Match failed at index 4082
Continuing at 4116
Match failed at index 4117
Continuing at 4179
Match failed at index 4180
Continuing at 4209
Match failed at index 4210
Continuing at 4230
Match failed at index 4231
Continuing at 4261
Match failed at index 4262
Continuing at 4309
Match failed at index 4310
Continuing at 4322
Morphed node: 0x7fef2a033610: i32 = MVrr 0x7fef2a033610 [ORD=21]


Does the add operation become a MOVE instruction, or is this a chain of rules?

(*)

>>>>>> But if I use the statement "int res = v1 + v2 + v3;" something strange happens: all arguments are stored in the stack-frame and the local variables are initialized. Now, the variables v1 and v2 are loaded, but they are not used (no ADD instructions) and a MOVE instruction register to register is generated that uses itself as an operand. This register should be stored and should be used as function result.

Boris

[Quentin Colombet]

Yes, your add becomes a MVrr instruction. This is likely the problem.
Do you know how to debug this, or do you want me to give you basic directions?

-Quentin

[Boris Boesler]

Hi Quentin,

Am 03.11.2014 um 23:30 schrieb Quentin Colombet <qcol...@apple.com>:

>> Continuing at 4309
>> Match failed at index 4310
>> Continuing at 4322
>> Morphed node: 0x7fef2a033610: i32 = MVrr 0x7fef2a033610 [ORD=21]
>>
>>
>> Does the add operation become a MOVE instruction, or is this a chain of rules?
>
> Yes, your add becomes a MVrr instruction. This is likely the problem.
> Do you know how to debug this, or do you want me to give you basic directions?

I had a look at the matcher table and it looks as follows:

/*4309*/ /*Scope*/ 12, /*->4322*/
/*4310*/ OPC_CheckOpcode, TARGET_VAL(MBPISD::RET_FLAG),
/*4313*/ OPC_RecordNode, // #0 = 'retflag' chained node
/*4314*/ OPC_CaptureGlueInput,
/*4315*/ OPC_EmitMergeInputChains1_0,
/*4316*/ OPC_MorphNodeTo, TARGET_VAL(MyTarget::RETL), 0|OPFL_Chain|OPFL_GlueInput|OPFL_Variadic0,
0/*#VTs*/, 0/*#Ops*/,
// Src: (retflag) - Complexity = 3
// Dst: (RETL)
/*4322*/ /*Scope*/ 11, /*->4334*/
/*4323*/ OPC_RecordNode, // #0 = $a
/*4324*/ OPC_CheckType, MVT::i32,
/*4326*/ OPC_MorphNodeTo, TARGET_VAL(MyTarget::MVrr), 0,
1/*#VTs*/, MVT::i32, 1/*#Ops*/, 0,
// Src: AllRegs:i32:$a - Complexity = 3
// Dst: (MVrr:i32 AllRegs:i32:$a)
/*4334*/ /*Scope*/ 14, /*->4349*/
/*4335*/ OPC_CheckOpcode, TARGET_VAL(ISD::ADD),
/*4338*/ OPC_RecordChild0, // #0 = $a
/*4339*/ OPC_RecordChild1, // #1 = $b
/*4340*/ OPC_MorphNodeTo, TARGET_VAL(MyTarget::ADDrrr), 0,


Matching fails from the beginning because no pattern matches (that's correct) and it fails at index 4310 because ADD != MBPISD::RET_FLAG. Now, matching continues at index 4322 and the only check there is the typecheck MVT::i32 of the input. It doesn't check any opcodes! That means that if no pattern matches till this point any input becomes a MVrr, which is completely wrong. The pattern, that should match ADDrrr, is right at index 4334.
Well, MV patterns (ala [(set AllRegs:$dst, AllRegs:$a)]) are the first ones in my .td files. I'm guessing they appear in the same order in the matcher table.

Cross-check: Move the MV-patterns from the beginning to the end. Voila, it works.

I assume this is a bug/imperfection in the table match generator.

Knowing that, I can continue my work.

Thanks,

[Tim Northover]

Hi Boris,

On 5 November 2014 06:47, Boris Boesler <bae...@gmx.de> wrote:
> Cross-check: Move the MV-patterns from the beginning to the end. Voila, it works.

It would be better to delete those patterns entirely. They'll always
match (if asked) and never give a sane result.

> I assume this is a bug/imperfection in the table match generator.

It possibly should be a compile-time error, if we can detect it
reliably (maybe look for at least one real node being consumed?). But
the kind of pattern it's trying to represent just shouldn't exist.

Cheers.

Tim.

[Boris Boesler]

Hi!

Am 05.11.2014 um 16:05 schrieb Tim Northover <t.p.no...@gmail.com>:

> Hi Boris,
>
> On 5 November 2014 06:47, Boris Boesler <bae...@gmx.de> wrote:
>> Cross-check: Move the MV-patterns from the beginning to the end. Voila, it works.
>
> It would be better to delete those patterns entirely. They'll always
> match (if asked) and never give a sane result.

Hm, these are no patterns like "def : Pat<..>;". These are patterns inside instructions, and I do have to specify them to use them in copyPhysReg(), don't I?

Boris

[Tim Northover]

Hi Boris,

On 5 November 2014 07:14, Boris Boesler <bae...@gmx.de> wrote:
> Hm, these are no patterns like "def : Pat<..>;". These are patterns inside instructions,

Yep, just give empty square brackets as the pattern for MV
instructions. Sorry, I should have mentioned the inside-instruction
version in my initial message. It does basically the same thing as the
one I suggested. It just didn't occur to me that you could write it
there (I'd made my own mistakes with a separate Pat).

> and I do have to specify them to use them in copyPhysReg(), don't I?

copyPhysReg will be called automatically when LLVM wants to do a MV.
The default implementation will just assert, but you'll definitely
need to implement a sensible version making use of your own MVs sooner
or later.

Cheers.

Tim.

[Boris Boesler]

Hi Tim,

Am 05.11.2014 um 16:32 schrieb Tim Northover <t.p.no...@gmail.com>:

> Hi Boris,
>
> On 5 November 2014 07:14, Boris Boesler <bae...@gmx.de> wrote:
>> Hm, these are no patterns like "def : Pat<..>;". These are patterns inside instructions,
>
> Yep, just give empty square brackets as the pattern for MV
> instructions.

With the original order of instructions and a MV reg -> reg instruction with an empty pattern, works as you described.

Thanks,
Boris