llvm dev - Sep 2019 - some questions about DAG

Hello.


I am reading the code about DAG to DAG Instruction selection when I meet some
problems. I am confused about the using of ch, glue.

when will they be used? And what are they used for?

when a sdnode doesn't have an actual result, it would have an MVT::Other
typed result. But how to decide which sdnode is the user of this result?
for example, I have the DAG before instruction selection step, the corresponding
graph is in attachment:

SelectionDAG has 19 nodes:

t0: ch = EntryToken

t5: ch = store<ST4[%1]> t0, Constant:i32<11>,
FrameIndex:i32<0>, undef:i32

t8: ch = store<Volatile ST4[%2]> t5, Constant:i32<12>,
FrameIndex:i32<1>, undef:i32

t9: i32,ch = load<LD4[%1]> t8, FrameIndex:i32<0>, undef:i32

t12: i32,ch = load<Volatile LD4[%2]> t9:1, FrameIndex:i32<1>,
undef:i32

t14: ch = store<ST4[%1]> t12:1, t22, FrameIndex:i32<0>, undef:i32

t17: ch,glue = CopyToReg t14, Register:i32 %V0, t22

t11: i32 = add t9, Constant:i32<1>

t20: glue = Cpu0ISD::DivRem t11, t12

t22: i32,ch,glue = CopyFromReg t0, Register:i32 %HI, t20

t18: ch = Cpu0ISD::Ret t17, Register:i32 %V0, t17:1

The .ll code is as below:

*********************************************************************************************************************************


; ModuleID = 'ch4_1_mod.bc'
source_filename = "ch4_1_mod.cpp"
target datalayout = "E-m:m-p:32:32-i8:8:32-i16:16:32-i64:64-n32-S64"
target triple = "mips-unknown-linux-gnu"

; Function Attrs: nounwind
define i32 @_Z8test_modv() #0 {
%1 = alloca i32, align 4
%2 = alloca i32, align 4
store i32 11, i32* %1, align 4
store volatile i32 12, i32* %2, align 4
%3 = load i32, i32* %1, align 4
%4 = add nsw i32 %3, 1
%5 = load volatile i32, i32* %2, align 4
%6 = srem i32 %4, %5
store i32 %6, i32* %1, align 4
%7 = load i32, i32* %1, align 4
ret i32 %7
}

attributes #0 = { nounwind "disable-tail-calls"="false"
"less-precise-fpmad"="false"
"no-frame-pointer-elim"="true"
"no-frame-pointer-elim-non-leaf"
"no-infs-fp-math"="false"
"no-jump-tables"="false"
"no-nans-fp-math"="false"
"no-signed-zeros-fp-math"="false"
"stack-protector-buffer-size"="8"
"target-cpu"="mips32r2"
"target-features"="+mips32r2"
"unsafe-fp-math"="false"
"use-soft-float"="false" }

!llvm.ident = !{!0}

!0 = !{!"clang version 3.9.0 (tags/RELEASE_390/final)"}


*********************************************************************************************************************************

Considering t9 already has a i32 sdvalue, why ch is need? Does ch represent for
MVT::Other typed sdvalue?

t22 has 3 results. ch is one of them, but ch is not used by any node. why is it
created?

what about glue? what is it used for and when is it used?

And when the DAG is processed, there is usually a variable chain. what is it
used for? and how is it used? Does ch in DAG represent for chain?

Thanks a lot!













Jack





-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20190920/d25d7274/attachment-0001.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: ch4_1_mod-6-combine.jpg
Type: image/jpeg
Size: 136951 bytes
Desc: not available
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20190920/d25d7274/attachment-0001.jpg>

Hi Jack,

On Sat, 21 Sep 2019 at 07:33, 林政宗 via llvm-dev <llvm-dev at
lists.llvm.org> wrote:
> I am reading the code about DAG to DAG Instruction selection when I meet
some problems. I am confused about the using of ch, glue.
> when will they be used? And what are they used for?
"Chain" operands, sometimes written "ch" and with type
MVT::Other
represent the order nodes need to be evaluated in when it's not given
by normal types and dataflow. It normally happens for nodes that have
side-effects not directly modelled by the type system. For example
load and store nodes have a chain because they affect memory, and
can't be reordered.

"Glue" is even stronger, it's for cases where even normal
instructions
would be likely overwrite the desired effects. For example copying
arguments into particular registers before function calls, or a
compare followed by a branch where the flags register would be
clobbered by most arithmetic instructions.
> But how to decide which sdnode is the user of this result? for example, I
have the DAG before instruction selection step, the corresponding graph is in
attachment:
In general you can't tell. There may be nothing that actually depends
on a store in this graph, or it may be something like a fence, which
nothing can really depend on in a conventional sense.
> Considering t9 already has a i32 sdvalue, why ch is need? Does ch represent
for MVT::Other typed sdvalue?
To make sure it happens after the store in t5 and t8, in case they are
to the same area in memory. In fact it looks like it *is* the same
local variable as t5, but that might not be obvious in all cases.
> t22 has 3 results. ch is one of them, but ch is not used by any node. why
is it created?
Register copies like that can have ordering requirements. In this case
the glue would probably be sufficient to make things work, but in
general they look very much like loads & stores in affecting a
non-modelled outside resource (the specific register) in a way that it
might not be safe to move around.

I think if a node is specified to have a chain operand, it probably
has to be plumbed into the head & tail.
> what about glue? what is it used for and when is it used?
In this case it's that DivRem sets a specific, fixed, register, and
LLVM needs to get that value into a generic register as soon as
possible, before it gets clobbered by some other instruction, so the
DivRem is glued next to the CopyFromRegister.
> And when the DAG is processed, there is usually a variable chain. what is
it used for? and how is it used?
Code generally has to preserve existing chain constraints when it
transforms the DAG. That probably accounts for most "SDValue Chain"
variables you'll see in C++ code.

Occasionally we also need to create new ordering requirements. In that
case you might start at the EntryToken's chain argument and create a
parallel chain.

Cheers.

Tim.