v8 graph node部分源码分析

node:

Node是graph的基本元素,graph中各node通过 input和use链 链接在一起
Node类大概如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Node
{
public:
static Node* New(Zone* zone, NodeId id, const Operator* op, int input_count,
Node* const* inputs, bool has_extensible_inputs);
static Node* Clone(Zone* zone, NodeId id, const Node* node);
class InputEdges;
class Inputs;
class UseEdges;
class Uses;
void AppendInput(Zone* zone, Node* new_to);
void InsertInput(Zone* zone, int index, Node* new_to);
...
private:
struct Use;
struct OutOfLineInputs; // 当input数量多余inline分配空间的容量时的 input的外部存储

/*头插法,first_use__指向头*/
void AppendUse(Use* use);
void RemoveUse(Use* use);
...
const Operator* op_;
Type type_;
Mark mark_;
uint32_t bit_field_;
Use* first_use_;

}

Node实例前后的内存布局,代码中注释的翻译:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
//============================================================================
//== Memory layout ===========================================================
//============================================================================
// 节省graph的空间非常重要。 我们使用内存布局技巧,以节省空间的方式将{Node}对象映射到{Use}对象,反之亦然。
//
// {Use} links are laid out in memory directly before a {Node}, followed by
// direct pointers to input {Nodes}.
//
// inline case:
// |Use #N |Use #N-1|...|Use #1 |Use #0 |Node xxxx |I#0|I#1|...|I#N-1|I#N|
// ^ ^ ^
// + Use + Node + Input
//
// 由于每个{Use}实例在成员bit_field_都记录了它的{input_index},因此可以计算出{Node}的位置。
//
// out-of-line case:
// |Node xxxx |
// ^ + outline ------------------+
// +----------------------------------------+
// | |
// v | node
// |Use #N |Use #N-1|...|Use #1 |Use #0 |OOL xxxxx |I#0|I#1|...|I#N-1|I#N|
// ^ ^
// + Use + Input
//
// Out-of-line storage of input lists is needed if appending an input to
// a node exceeds the maximum inline capacity.
// 如果向Node附加input超过最大inline容量,则需要input list的外部存储。

input指针开始的位置是在node实例的后面(高地址处):

1
2
3
Address Node::inputs_location() const {
return reinterpret_cast<Address>(this) + sizeof(Node);
}

为某个node增加input:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void Node::AppendInput(Zone* zone, Node* new_to) {
DCHECK_NOT_NULL(zone);
DCHECK_NOT_NULL(new_to);
int inline_count = InlineCountField::decode(bit_field_);
int inline_capacity = InlineCapacityField::decode(bit_field_);
if (inline_count < inline_capacity) {
// Append inline input.
bit_field_ = InlineCountField::update(bit_field_, inline_count + 1);
*GetInputPtr(inline_count) = new_to; //最新的位置赋值一个node指针(新增加的input)
Use* use = GetUsePtr(inline_count);
use->bit_field_ = Use::InputIndexField::encode(inline_count) | //这里记录了index
Use::InlineField::encode(true);
new_to->AppendUse(use);//将该use添加到新添加的input(node)的use链表中

} else {
// Append out-of-line input.

}
Verify();
}

添加use到链表使用的AppendUse函数:

1
2
3
4
5
6
7
void Node::AppendUse(Use* use) {
...
use->next = first_use_;
use->prev = nullptr;
if (first_use_) first_use_->prev = use;
first_use_ = use;
}

node实例的低地址处存储的直接是多个struct Use,不是指针,通过New函数可以看出来:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
Node* Node::New(Zone* zone, NodeId id, const Operator* op, int input_count,
Node* const* inputs, bool has_extensible_inputs) {
Node** input_ptr;
Use* use_ptr;
Node* node;
bool is_inline;
....

if (input_count > kMaxInlineCapacity) {
// Allocate out-of-line inputs.
....
} else {
// Allocate node with inline inputs. Capacity must be at least 1 so that
// an OutOfLineInputs pointer can be stored when inputs are added later.
int capacity = std::max(1, input_count);
if (has_extensible_inputs) {
const int max = kMaxInlineCapacity;
capacity = std::min(input_count + 3, max);
}
/* Node的大小 + 容量*(Node指针大小 + Use结构体大小)*/
size_t size = sizeof(Node) + capacity * (sizeof(Node*) + sizeof(Use));
intptr_t raw_buffer = reinterpret_cast<intptr_t>(zone->New(size));

/* 前面低地址处用来存储Use,中间是Node实例,后面高地址处存放Node指针
* raw_buffer + 容量*Use结构体的大小后才是Node实例的空间
*/
void* node_buffer =
reinterpret_cast<void*>(raw_buffer + capacity * sizeof(Use));

/*在指定位置(node_buffer)分配Node的空间*/
node = new (node_buffer) Node(id, op, input_count, capacity);
input_ptr = node->inline_inputs(); //input指针开始的位置
use_ptr = reinterpret_cast<Use*>(node);
is_inline = true;
}
// Initialize the input pointers and the uses.
// 这里代码和AppendInput差不多
for (int current = 0; current < input_count; ++current) {
Node* to = *inputs++;
input_ptr[current] = to;
Use* use = use_ptr - 1 - current;
use->bit_field_ = Use::InputIndexField::encode(current) |
Use::InlineField::encode(is_inline);
to->AppendUse(use);
}
node->Verify();
return node;
}

graph:

假设在turbolizer显示的图像大致如下:

1
2
3
4
5
   input_0          input_1
| |
|________________|
|
(use_1,use_0|node|input_0_ptr,input_1_ptr)

input在node的上面
graph创建类:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class JSONGraphEdgeWriter {
public:
JSONGraphEdgeWriter(std::ostream& os, Zone* zone, const Graph* graph)
: os_(os), all_(zone, graph, false), first_edge_(true) {}

void Print() {
for (Node* const node : all_.reachable) PrintEdges(node);
os_ << "\n";
}

void PrintEdges(Node* node) {
/*按顺序遍历该node的input*/
for (int i = 0; i < node->InputCount(); i++) {
Node* input = node->InputAt(i);
if (input == nullptr) continue;
PrintEdge(node, i, input);
/*from = node , to = input*/
}
}

void PrintEdge(Node* from, int index, Node* to) {
if (first_edge_) {
first_edge_ = false;
} else {
os_ << ",\n";
}
const char* edge_type = nullptr;
if (index < NodeProperties::FirstValueIndex(from)) {
edge_type = "unknown";
} else if (index < NodeProperties::FirstContextIndex(from)) {
edge_type = "value";
...
/*to是source,from是target*/
os_ << "{\"source\":" << SafeId(to) << ",\"target\":" << SafeId(from)
<< ",\"index\":" << index << ",\"type\":\"" << edge_type << "\"}";
}
private:
std::ostream& os_;
AllNodes all_;
bool first_edge_;
..
};

–trace-turbo生成的json:

1
2
{"source":29,"target":31,"index":0,"type":"value"},
{"source":30,"target":31,"index":1,"type":"value"},

再结合生成的图像可知source在上方,target在下方,即to是input,from是target.

use的存储

一个node实例有两个地方存储 Use.
第一个地方是node实例的低地址处,这里直接存储的Use实例:

1
2
use_1 use_0 | node实例 | input_0 input_1 
low addr high addr

另一个地方是: node实例中存储着一个Use链表,链表头是 first_use_ ,use的添加,插入,删除就是类中的AppendUse,InsertUse等函数.
例如 input_0 会把 use_0 放入到自己的链表中, input_1会把 use_1放入到自己的链表中.这样通过input可以找到node,通过node也可以找到input

如何遍历use_edge:

1
2
3
for (Edge edge : node->use_edges()) {//这里的node即是input
Node* const user = edge.from(); //获得target.
}

遍历的是该node实例中的以first_use_为链表头的use链表.每一次以该链表中的use和该use对应的input来初始化Edge,通过这个Edge实例,可以获得use所在域中的node实例:

Node类中的UseEdges类:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

class UseEdges final {
public:
using value_type = Edge;

class iterator;
inline iterator begin() const;
inline iterator end() const;

bool empty() const;

explicit UseEdges(Node* node) : node_(node) {}

private:
Node* node_;
};

UseEdges use_edges() { return UseEdges(this); }

/*用UseEdges中的node_初始化iterator*/
Node::UseEdges::iterator Node::UseEdges::begin() const {
return Node::UseEdges::iterator(this->node_);
}

Node::UseEdges::iterator Node::UseEdges::end() const {
return Node::UseEdges::iterator();
}

UseEdges类中的iterator类:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
// A forward iterator to visit the uses edges of a node.
class Node::UseEdges::iterator final {
public:
iterator(const iterator& other) = default;

Edge operator*() const { return Edge(current_, current_->input_ptr()); }
bool operator==(const iterator& other) const {
return current_ == other.current_;
}
bool operator!=(const iterator& other) const { return !(*this == other); }
iterator& operator++() {
DCHECK_NOT_NULL(current_);
current_ = next_;
next_ = current_ ? current_->next : nullptr;
return *this;
}
iterator operator++(int);

private:
friend class Node::UseEdges;

iterator() : current_(nullptr), next_(nullptr) {}
explicit iterator(Node* node)
: current_(node->first_use_),
next_(current_ ? current_->next : nullptr) {}

Node::Use* current_; //first use
Node::Use* next_; // first_use -> next
};

使用iterator这个类来遍历Node实例中的use链表,即链表头为first_use_的链表

Use_Edges::iterator的初始化:

1
2
3
explicit iterator(Node* node)
: current_(node->first_use_),
next_(current_ ? current_->next : nullptr) {}

使用node实例的first_use_来初始化current_ ,即将use链表头赋值给current.

看下Node类中的结构体Use:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
struct Use {
Use* next;
Use* prev;
uint32_t bit_field_;

int input_index() const { return InputIndexField::decode(bit_field_); }
bool is_inline_use() const { return InlineField::decode(bit_field_); }
Node** input_ptr() {
int index = input_index();//获得Appendinput时对应的index
Use* start = this + 1 + index;//获得该Use所在的域中的Node实例的地址
Node** inputs = is_inline_use() //获取对应的input的位置
? reinterpret_cast<Node*>(start)->inline_inputs()
: reinterpret_cast<OutOfLineInputs*>(start)->inputs();
return &inputs[index];//返回指向该Use对应的input的指针的指针
}

/*获得该Use所在的域中的Node实例的地址*/
Node* from() {
Use* start = this + 1 + input_index();
return is_inline_use() ? reinterpret_cast<Node*>(start)
: reinterpret_cast<OutOfLineInputs*>(start)->node_;
}

使用该iterator每一次返回的是Edge实例:

1
Edge operator*() const { return Edge(current_, current_->input_ptr()); }

这里使用Use和该Use对应的input_node来初始化Edge

Edge类如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
class Edge final {
public:
Node* from() const { return use_->from(); }
Node* to() const { return *input_ptr_; }
...
private:
...
Edge(Node::Use* use, Node** input_ptr) : use_(use), input_ptr_(input_ptr) {
...
}
Node::Use* use_;
Node** input_ptr_; //上面use_对应的&input
};//Edge

struct Use中from的定义如下:

1
2
3
4
5
6
7
8
9
10
11

/*获得该Use所在的域中的Node实例的地址
* use | node | input
* ^
*
*/
Node* from() {
Use* start = this + 1 + input_index();
return is_inline_use() ? reinterpret_cast<Node*>(start)
: reinterpret_cast<OutOfLineInputs*>(start)->node_;
}

这里from得到的就是图中的target,to是图中的source.