FAQ
Interesting false positive on Windows, when I attempted to download 1.4's
source code from the official website (redirect to storage.googleapis.com).

Anyway, yeah looking at the C code, it doesn't look much better (except I
have a lot more experience in C than Go, so it is comforting seeing the
types on the left hand side and declared ahead of time for C89
compatibility. I guess I'm mostly on my own for means of understanding the
source code. Thanks for the information on Ninit though, definitely enough
to know that I can continue in the direction I am headed.
On Monday, June 6, 2016 at 1:07:25 PM UTC-4, Keith Randall wrote:



On Mon, Jun 6, 2016 at 10:03 AM, Kyle Stanly <thei...@gmail.com
<javascript:>> wrote:
Would it be possible to see the original C code? Maybe I could better
understand how it was originally written (hopefully). Assuming that the old
code was well documented, I might be able to make certain connections
between the original and translated code.
Sure, download go1.4. Walk is in src/cmd/gc/walk.c, for example.
All the documentation from the C code was moved to the Go code, so you
probably won't find anything you haven't seen already. Assuming the old
code was well documented is not a good assumption...

On Monday, June 6, 2016 at 12:49:00 PM UTC-4, Keith Randall wrote:


On Mon, Jun 6, 2016 at 7:09 AM, Kyle Stanly wrote:

This is the struct in question...




type Node struct {
// Tree structure.
// Generic recursive walks should follow these fields.
Left *Node
Right *Node
Ninit Nodes
Nbody Nodes
List Nodes
Rlist Nodes


// most nodes
Type *Type
Orig *Node // original form, for printing, and tracking copies of
ONAMEs


// func
Func *Func


// ONAME
Name *Name


Sym *Sym // various
E interface{} // Opt or Val, see methods below


// Various. Usually an offset into a struct. For example, ONAME nodes
// that refer to local variables use it to identify their stack frame
// position. ODOT, ODOTPTR, and OINDREG use it to indicate offset
// relative to their base address. ONAME nodes on the left side of an
// OKEY within an OSTRUCTLIT use it to store the named field's offset.
// OXCASE and OXFALL use it to validate the use of fallthrough.
// Possibly still more uses. If you find any, document them.
Xoffset int64


Lineno int32


// OREGISTER, OINDREG
Reg int16


Esc uint16 // EscXXX


Op Op
Ullman uint8 // sethi/ullman number
Addable bool // addressable
Etype EType // op for OASOP, etype for OTYPE, exclam for export,
6g saved reg, ChanDir for OTCHAN
Bounded bool // bounds check unnecessary
NonNil bool // guaranteed to be non-nil
Class Class // PPARAM, PAUTO, PEXTERN, etc
Embedded uint8 // ODCLFIELD embedded type
Colas bool // OAS resulting from :=
Diag uint8 // already printed error about this
Noescape bool // func arguments do not escape; TODO(rsc): move
Noescape to Func struct (see CL 7360)
Walkdef uint8
Typecheck uint8
Local bool
Dodata uint8
Initorder uint8
Used bool
Isddd bool // is the argument variadic
Implicit bool
Addrtaken bool // address taken, even if not moved to heap
Assigned bool // is the variable ever assigned to
Likely int8 // likeliness of if statement
hasVal int8 // +1 for Val, -1 for Opt, 0 for not yet set
flags uint8 // TODO: store more bool fields in this flag field
}

As can be seen, there is quite a few things here that aren't explicitly
documented. I've a few questions on the developers who created it, and
would appreciate some insight. I'm working on extending the language for a
research project this summer, hence knowing how each Node interacts with
each other in the AST would be extremely helpful..


1) The biggest one, is Ninit. Are these nodes that must be walked
before processing the current node, recursively (I.E, Init is walked, and
if a Init node also has Init nodes, they are done first, etc.). These are
the biggest objects of actual confusion to me, because I use it used a lot
and I do not understand it. It also seems that Nodes aren't always removed
from Ninit, so I'm not sure where this is going. What is the actual purpose
of Ninit? Are they guaranteed to be called before the current node?
Yes, Ninit on a node should happen before that node (and recursively on
Ninits in an Ninit). It is generally used to keep track of side-effecting
code. OFOR with ORANGE uses Ninit to set up the iteration variable, for
example.
Ninits should be removed whenever they are added to a statement list.
Otherwise they would be executed twice.

I ask because I want to know if it is possible to inject code (if it is
a certain Op, and based on a Node's Type), and to do so, I need to have
code called before certain instructions, and then some after. This is for
some acquire-release semantics I want to experiment with. I.E, acquire
before an instruction, and release after an instruction. Even if it won't
be accepted, it is something I want to try out and understand (as I have
something else planned, and knowledge like this would help immensely).

2) What precisely does List and RList do? Are they for parameter Lists
and return parameter lists for functions (I.E Func)? Is this needed because
there are no unions in Go, and hence all fields even those not needed for
each individual Node is present? I'm wondering why there aren't just
subclasses of Nodes, but I'm sure it'd complicate code (even if it's feel
more readable to me). There are so many fields in Node, and a lot of them
seem unused for a lot of operations. What if there was a particular
subclass of Node called FuncNode, or MapNode, or ArrayNode, or SliceNode,
etc. Then they would contain only the relevant information needed, making
it easier to read. Thats just me though.
List and RList are generally used for nodes which have variable-length
argument lists, like call nodes.
All this code was originally written in C and autotranslated to Go, so
there are still lots of C-isms in it. I think if we'd written from scratch
we'd use something closer to go/ast <https://goto.google.com/ast>.

3) How does walkexpr actually work? I see a lot of calls to n.Right =
walkexpr(n.Right, init). Does it pretty much end up resolving what n.Right
is to it's final value? I.E, using the Op OINDEX and OAS as an example
here...

arr[idx + 1] = idx + 2

It would become...

OAS
/ \
OINDEX OADD
/ \ / \
arr OADD idx 2
/ \
idx 1

I'm assuming that walkexpr do the following...

1) Walk OAS's left child to obtain OINDEX
2) Walk OINDEX's left child to obtain arr
3) Walk OINDEX's right child to obtain OADD
4) Walk OADD's left child to obtain idx
5) Walk OADD's right child to obtain 1
6) Combine idx and 1
7) Obtain position of in arr at idx + 1
8) Walk OAS's right child to obtain OADD
9) Walk OADD's left child to obtain idx
10) Walk OADD's right child to obtain 2
11) Combined idx and 2
12) Finally, assign arr[idx + 1] to idx + 2

However, what if there was an init for accessing arr? When would that
be called? In fact, when does any of the code actually get called? It seems
to be just appending nodes, but never using them. Do nodes added to Ninit
only get called after the entire tree is walked? Can someone point me to
exactly where it calls them?
Walk is used to rewrite complicated Go ops to simpler ones, pick
orderings of evaluation, etc. It's pretty much a grab-bag of simple
optimizations and/or lowerings to runtime calls. So for your example, walk
is a no-op, as the backend can generate code from this AST as is.

The AST is actually processed in the backend to produce code (Genlist
and friends for the legacy backend, buildssa and friends for the SSA
backend).

Ninit fields get pulled out by walk and added to the list of nodes in
the parent. So if you had something like
OBLOCK
a
b
c

and b has an Ninit field, then after walk you would have:
OBLOCK
a
b.Ninit
b (with its Ninit field cleared)
c


4) How am I supposed to go about reading, comprehending and
understanding the AST? It seems to be very complex, but I am determined in
eventually understanding how it works, and how to modify it. There is a lot
of undocumented portions of code, variables with one or two letter names
with HUGE scopes (Like literally over a thousand), some goto jumps here and
there, etc. Not to insult the person who wrote it, but it doesn't feel like
it had readability in mind.
Yes, it isn't the easiest code to jump into. Sorry about that. Part of
that is the C->Go translator. Part is the dearth of comments in the
original C. We've been working on fixing it up. CLs to add documentation
are welcome.

Any help would be appreciated. If this is the wrong section, let me
know.

--
You received this message because you are subscribed to the Google
Groups "golang-dev" group.
To unsubscribe from this group and stop receiving emails from it, send
an email to golang-dev+...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.
--
You received this message because you are subscribed to the Google Groups
"golang-dev" group.
To unsubscribe from this group and stop receiving emails from it, send an
email to golang-dev+...@googlegroups.com <javascript:>.
For more options, visit https://groups.google.com/d/optout.
--
You received this message because you are subscribed to the Google Groups "golang-dev" group.
To unsubscribe from this group and stop receiving emails from it, send an email to golang-dev+unsubscribe@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

Search Discussions

Discussion Posts

Previous

Follow ups

Related Discussions

Discussion Navigation
viewthread | post
posts ‹ prev | 5 of 7 | next ›
Discussion Overview
groupgolang-dev @
categoriesgo
postedJun 6, '16 at 2:18p
activeJun 6, '16 at 6:32p
posts7
users4
websitegolang.org

People

Translate

site design / logo © 2021 Grokbase