chunk_codegen.py 88.7 KB
Newer Older
oahzxl's avatar
init  
oahzxl committed
1
2
import colossalai
import torch
oahzxl's avatar
oahzxl committed
3
import copy
oahzxl's avatar
init  
oahzxl committed
4
5
from typing import List, Callable, Any, Tuple, Dict, Iterable

oahzxl's avatar
oahzxl committed
6
from torch.fx.node import Node, Argument, map_arg, _type_repr, _get_qualified_name
oahzxl's avatar
oahzxl committed
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
from torch.fx.graph import (
    _Namespace,
    PythonCode,
    _custom_builtins,
    _is_from_torch,
    _format_target,
    magic_methods,
    CodeGen,
    _origin_type_map,
    inplace_methods,
    _CustomBuiltin,
)
from colossalai.fx.profiler import (
    calculate_fwd_out,
    calculate_fwd_tmp,
    parameter_size,
    activation_size,
)

oahzxl's avatar
oahzxl committed
26
CODEGEN_AVAILABLE = True
oahzxl's avatar
oahzxl committed
27
__all__ = ["ChunkCodeGen"]
oahzxl's avatar
init  
oahzxl committed
28
29


oahzxl's avatar
oahzxl committed
30
31
32
def _delete_free_var_from_last_use(user_to_last_uses):
    for key, value in user_to_last_uses.items():
        for n in value:
oahzxl's avatar
oahzxl committed
33
            if n.op == "placeholder":
oahzxl's avatar
oahzxl committed
34
35
                user_to_last_uses[key].remove(n)

oahzxl's avatar
oahzxl committed
36

37
def _get_node_shape(node):
oahzxl's avatar
oahzxl committed
38
39
    if hasattr(node.meta["tensor_meta"], "shape"):
        return node.meta["tensor_meta"].shape
40
41
    return None

oahzxl's avatar
oahzxl committed
42

oahzxl's avatar
oahzxl committed
43
def _is_non_compute_node(node):
oahzxl's avatar
oahzxl committed
44
45
46
    if any(i in node.op for i in ["placeholder", "get_attr", "output"]) or any(
        i in node.name for i in ["getitem", "getattr"]
    ):
oahzxl's avatar
oahzxl committed
47
48
        return True
    return False
oahzxl's avatar
oahzxl committed
49
50


oahzxl's avatar
oahzxl committed
51
def _is_non_compute_node_except_placeholder(node):
oahzxl's avatar
oahzxl committed
52
53
54
    if any(i in node.op for i in ["get_attr", "output"]) or any(
        i in node.name for i in ["getitem", "getattr"]
    ):
oahzxl's avatar
oahzxl committed
55
56
57
58
        return True
    return False


oahzxl's avatar
oahzxl committed
59
60
61
62
63
64
65
66
def _is_non_compute_node_except_placeholder_output(node):
    if any(i in node.op for i in ["get_attr"]) or any(
        i in node.name for i in ["getitem", "getattr"]
    ):
        return True
    return False


oahzxl's avatar
oahzxl committed
67
class IndexTracer(object):
oahzxl's avatar
oahzxl committed
68
69
    def __init__(self, node_list) -> None:
        self.node_list = node_list
70
        self.idx_trace_list = self._init_idx_trace_list()
oahzxl's avatar
oahzxl committed
71
        self.idx_trace_equal = []
oahzxl's avatar
oahzxl committed
72
        self.idx_view_list = {}
oahzxl's avatar
oahzxl committed
73
        self.idx_count = -1
oahzxl's avatar
oahzxl committed
74
        self.all_reorder_map = {i: i for i in range(len(self.idx_trace_list))}
oahzxl's avatar
oahzxl committed
75

76
77
    def _init_idx_trace_list(self):
        idx_trace_list = []
oahzxl's avatar
oahzxl committed
78
        for n in self.node_list:
oahzxl's avatar
oahzxl committed
79
            if _get_node_shape(n) != None:
80
                cur_trace = {
oahzxl's avatar
oahzxl committed
81
82
83
                    "idx": [None for _ in range(len(_get_node_shape(n)))],
                    "compute": [[] for _ in range(len(_get_node_shape(n)))],
                    "source": [{} for _ in range(len(_get_node_shape(n)))],
84
85
                }
            else:
oahzxl's avatar
oahzxl committed
86
                cur_trace = {"idx": [], "compute": [], "source": []}
87
88
            idx_trace_list.append(cur_trace)
        return idx_trace_list
oahzxl's avatar
oahzxl committed
89

oahzxl's avatar
oahzxl committed
90
    def _add_index(self):
oahzxl's avatar
oahzxl committed
91
92
        """
        Update the count and return it. To record the idx number.
oahzxl's avatar
oahzxl committed
93

oahzxl's avatar
oahzxl committed
94
95
        Returns:
            idx_count: int
oahzxl's avatar
oahzxl committed
96
        """
oahzxl's avatar
oahzxl committed
97
        self.idx_count += 1
oahzxl's avatar
oahzxl committed
98
        return self.idx_count
oahzxl's avatar
oahzxl committed
99

100
    def _del_dim(self, idx, dim_idx):
oahzxl's avatar
oahzxl committed
101
102
103
104
        self.idx_trace_list[idx]["idx"].pop(dim_idx)
        self.idx_trace_list[idx]["compute"].pop(dim_idx)
        self.idx_trace_list[idx]["source"].pop(dim_idx)

105
106
107
108
    def _add_dim(self, node_idx, dim_idx):
        self.idx_trace_list[node_idx]["idx"].insert(dim_idx, self._add_index())
        self.idx_trace_list[node_idx]["compute"].insert(dim_idx, [])
        self.idx_trace_list[node_idx]["source"].insert(dim_idx, {})
oahzxl's avatar
oahzxl committed
109

110
111
112
113
    def _transform_index(self, node, node_dim):
        node_idx = self._find_idx_trace_from_node(node)
        dims = list(range(len(node_idx)))
        return dims[node_dim]
oahzxl's avatar
oahzxl committed
114

115
116
117
118
119
    def _inherit_index(self, node_from, node_from_dim, node_to, node_to_dim):
        node_from_dim = self._transform_index(node_from, node_from_dim)
        node_to_dim = self._transform_index(node_to, node_to_dim)
        node_from_trace = self._find_trace_from_node(node_from)
        node_to_trace = self._find_trace_from_node(node_to)
oahzxl's avatar
oahzxl committed
120
121
122
123
        node_to_trace["idx"][node_to_dim] = node_from_trace["idx"][node_from_dim]
        node_to_trace["compute"][node_to_dim] = copy.deepcopy(
            node_from_trace["compute"][node_from_dim]
        )
oahzxl's avatar
oahzxl committed
124
        self._add_source(node_from, node_from_dim, node_to, node_to_dim, init=True)
oahzxl's avatar
oahzxl committed
125

126
127
128
129
130
131
132
    def _inherit_all_computation(self, node_from, node_to):
        node_from_compute = self._find_compute_trace_from_node(node_from)
        node_to_compute = self._find_compute_trace_from_node(node_to)
        assert len(node_from_compute) == len(node_to_compute)
        for i in range(len(node_from_compute)):
            self._add_source(node_from, i, node_to, i)
            node_to_compute[i] = copy.deepcopy(node_from_compute[i])
oahzxl's avatar
oahzxl committed
133

oahzxl's avatar
oahzxl committed
134
    def _add_source(self, node_from, node_from_dim, node_to, node_to_dim, init=False):
135
        node_from_dim = self._transform_index(node_from, node_from_dim)
oahzxl's avatar
oahzxl committed
136
        node_from_trace_source = self._find_source_trace_from_node(node_from)
137
        node_to_dim = self._transform_index(node_to, node_to_dim)
oahzxl's avatar
oahzxl committed
138
        node_to_trace_source = self._find_source_trace_from_node(node_to)
oahzxl's avatar
oahzxl committed
139
        node_from_idx = _find_idx_by_name(node_from.name, self.node_list)
oahzxl's avatar
oahzxl committed
140
        if init:
oahzxl's avatar
oahzxl committed
141
            node_to_trace_source[node_to_dim] = {}
oahzxl's avatar
oahzxl committed
142
        # add dim to cur new source
oahzxl's avatar
oahzxl committed
143
144
        if node_from_idx not in node_to_trace_source[node_to_dim]:
            node_to_trace_source[node_to_dim][node_from_idx] = [node_from_dim]
oahzxl's avatar
oahzxl committed
145
        else:
oahzxl's avatar
oahzxl committed
146
147
            if node_from_dim not in node_to_trace_source[node_to_dim][node_from_idx]:
                node_to_trace_source[node_to_dim][node_from_idx].append(
oahzxl's avatar
oahzxl committed
148
149
                    node_from_dim
                )
oahzxl's avatar
oahzxl committed
150
        # update inputs source
oahzxl's avatar
oahzxl committed
151
152
153
154
155
156
157
        for node_idx, node_dim in node_from_trace_source[node_from_dim].items():
            if node_idx not in node_to_trace_source[node_to_dim]:
                node_to_trace_source[node_to_dim][node_idx] = copy.deepcopy(node_dim)
            else:
                for d in node_dim:
                    if d not in node_to_trace_source[node_to_dim][node_idx]:
                        node_to_trace_source[node_to_dim][node_idx].append(d)
oahzxl's avatar
oahzxl committed
158

159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
    def _mark_computation_from_node(self, node_from, node_to, exclude=None):
        if exclude == None:
            exclude = []
        else:
            exclude = [self._transform_index(node_to, i) for i in exclude]
        node_from_compute = self._find_compute_trace_from_node(node_from)
        node_to_compute = self._find_compute_trace_from_node(node_to)
        # assert len(node_from_compute) == len(node_to_compute)
        for i in range(-1, -min(len(node_from_compute), len(node_to_compute)) - 1, -1):
            if self._transform_index(node_to, i) in exclude:
                continue
            self._add_source(node_from, i, node_to, i)
            for j in node_from_compute[i]:
                if j not in node_to_compute[i]:
                    node_to_compute[i].append(j)
oahzxl's avatar
oahzxl committed
174

175
    def _mark_idx_equal(self, node1, dim1, node2, dim2):
oahzxl's avatar
oahzxl committed
176
177
178
179
180
181
        """
        Mark 2 index to be equal.

        Args:
            idx1 (int): index count.
            idx2 (int): index count.
182
183
184
185
186
187
188
        """
        # node1_idx = _find_idx_by_name(node1.name, self.nodes_list)
        # node2_idx = _find_idx_by_name(node2.name, self.nodes_list)
        # if node1_idx > node2_idx:
        #     self._add_source(node2, dim2, node1, dim1)
        # else:
        #     self._add_source(node1, dim1, node2, dim2)
oahzxl's avatar
oahzxl committed
189

oahzxl's avatar
oahzxl committed
190
    def _mark_computation(self, node, idx, dim):
oahzxl's avatar
oahzxl committed
191
192
193
194
195
196
197
        """
        Mark some dims of node as computed.

        Args:
            node (node)
            idx (int): node index
            dim (list or int): dims to be marked as computed
oahzxl's avatar
oahzxl committed
198
        """
oahzxl's avatar
oahzxl committed
199
200
        if isinstance(dim, int):
            dim = [dim]
201
        dims = list(range(len(_get_node_shape(node))))
oahzxl's avatar
oahzxl committed
202
        for d in dim:
203
            cur_dim = dims[d]
oahzxl's avatar
oahzxl committed
204
205
            if idx not in self.idx_trace_list[idx]["compute"][cur_dim]:
                self.idx_trace_list[idx]["compute"][cur_dim].append(idx)
206

oahzxl's avatar
oahzxl committed
207
    def _find_trace_from_node(self, node):
oahzxl's avatar
oahzxl committed
208
209
210
211
212
213
214
215
        """
        Find node idx and compute trace by the node.

        Args:
            node (node)
        Returns:
            idx (list): idx of the node
            compute (list): computed idx of the node.
oahzxl's avatar
oahzxl committed
216
        """
oahzxl's avatar
oahzxl committed
217
        node_idx = _find_idx_by_name(node.name, self.node_list)
oahzxl's avatar
oahzxl committed
218
        node_dict = self.idx_trace_list[node_idx]
219
        return node_dict
oahzxl's avatar
oahzxl committed
220

oahzxl's avatar
oahzxl committed
221
222
223
224
225
226
227
228
229
230
    def _find_source_trace_from_node(self, node):
        """
        Find node source trace by the node.

        Args:
            node (node)
        Returns:
            idx (list): idx of the node
            compute (list): computed idx of the node.
        """
oahzxl's avatar
oahzxl committed
231
        node_idx = _find_idx_by_name(node.name, self.node_list)
oahzxl's avatar
oahzxl committed
232
233
234
        node_dict = self.idx_trace_list[node_idx]
        return node_dict["source"]

oahzxl's avatar
oahzxl committed
235
    def _find_idx_trace_from_node(self, node):
oahzxl's avatar
oahzxl committed
236
237
238
239
240
241
242
        """
        Find node idx trace by the node.

        Args:
            node (node)
        Returns:
            idx (list): idx of the node
oahzxl's avatar
oahzxl committed
243
        """
oahzxl's avatar
oahzxl committed
244
        node_idx = _find_idx_by_name(node.name, self.node_list)
oahzxl's avatar
oahzxl committed
245
246
        return self.idx_trace_list[node_idx]["idx"]

oahzxl's avatar
oahzxl committed
247
    def _find_compute_trace_from_node(self, node):
oahzxl's avatar
oahzxl committed
248
249
250
251
252
253
254
        """
        Find node compute trace by the node.

        Args:
            node (node)
        Returns:
            compute (list): computed idx of the node.
oahzxl's avatar
oahzxl committed
255
        """
oahzxl's avatar
oahzxl committed
256
        node_idx = _find_idx_by_name(node.name, self.node_list)
oahzxl's avatar
oahzxl committed
257
258
        return self.idx_trace_list[node_idx]["compute"]

259
    def _assign_index_as_input(self, node, node_idx, input_node=None):
oahzxl's avatar
oahzxl committed
260
261
262
263
264
265
        """
        Assign node's trace as its input node.

        Args:
            node (node)
            node_idx (int)
266
267
268
        """
        if input_node == None:
            input_node = node.args[0]
oahzxl's avatar
oahzxl committed
269
        input_node_idx = _find_idx_by_name(input_node.name, self.node_list)
oahzxl's avatar
oahzxl committed
270
271
        input_node_idx_trace = self.idx_trace_list[input_node_idx]["idx"]

oahzxl's avatar
oahzxl committed
272
        new_idx_trace = copy.deepcopy(input_node_idx_trace)
oahzxl's avatar
oahzxl committed
273
274
        self.idx_trace_list[node_idx]["idx"] = new_idx_trace

275
        self._inherit_all_computation(input_node, node)
oahzxl's avatar
oahzxl committed
276

oahzxl's avatar
oahzxl committed
277
    def _assign_all_index(self, node, node_idx):
oahzxl's avatar
oahzxl committed
278
279
280
281
282
283
        """
        Add new index for all node's dims.

        Args:
            node (node)
            node_idx (int)
oahzxl's avatar
oahzxl committed
284
285
        """
        shape = node.meta["tensor_meta"].shape
oahzxl's avatar
oahzxl committed
286
287
        new_trace = []
        for _ in shape:
oahzxl's avatar
oahzxl committed
288
            new_trace.append(self._add_index())
oahzxl's avatar
oahzxl committed
289
        self.idx_trace_list[node_idx]["idx"] = new_trace
oahzxl's avatar
oahzxl committed
290

oahzxl's avatar
oahzxl committed
291
    def _assign_transpose_index(self, node, node_idx):
oahzxl's avatar
oahzxl committed
292
293
294
295
296
297
298
299
        """
        Assign index for transpose op.
        1. swap input's dim according to transpose args
        2. inherit input's computation

        Args:
            node (node)
            node_idx (int)
oahzxl's avatar
oahzxl committed
300
        """
301
        input_node = node.args[0]
oahzxl's avatar
oahzxl committed
302
        tranpose_dim = node.args[1:]
oahzxl's avatar
oahzxl committed
303

304
305
306
        self._assign_index_as_input(node, node_idx, input_node)
        self._inherit_index(input_node, tranpose_dim[1], node, tranpose_dim[0])
        self._inherit_index(input_node, tranpose_dim[0], node, tranpose_dim[1])
oahzxl's avatar
oahzxl committed
307

oahzxl's avatar
oahzxl committed
308
    def _assign_permute_index(self, node, node_idx):
oahzxl's avatar
oahzxl committed
309
310
311
312
313
314
315
316
        """
        Assign index for permute op.
        1. swap input's dim according to permute args
        2. inherit input's computation

        Args:
            node (node)
            node_idx (int)
oahzxl's avatar
oahzxl committed
317
        """
oahzxl's avatar
oahzxl committed
318
        permute_dim = node.args[1:]
319
        input_node = node.args[0]
oahzxl's avatar
oahzxl committed
320

321
        self._assign_index_as_input(node, node_idx, input_node)
oahzxl's avatar
oahzxl committed
322
        for idx, d in enumerate(permute_dim):
323
            self._inherit_index(input_node, d, node, idx)
oahzxl's avatar
oahzxl committed
324

oahzxl's avatar
oahzxl committed
325
    def _assign_linear_index(self, node, node_idx):
oahzxl's avatar
oahzxl committed
326
327
328
329
330
331
332
333
334
        """
        Assign index for linear op.
        1. copy trace from input node and change last index accroding to weight
        2. mark equal for input node last index, weight first dim and bias dim.
        3. inherit input's computation, mark computation for last dim.

        Args:
            node (node)
            node_idx (int)
oahzxl's avatar
oahzxl committed
335
336
337
338
339
340
        """
        if len(node.args) == 2:
            input_node, weight = node.args
            bias = None
        else:
            input_node, weight, bias = node.args
oahzxl's avatar
oahzxl committed
341

342
343
        self._assign_index_as_input(node, node_idx)
        self._inherit_index(weight, 1, node, -1)
oahzxl's avatar
oahzxl committed
344

oahzxl's avatar
oahzxl committed
345
        self._mark_computation(node, node_idx, [-1])
346
        self._mark_idx_equal(input_node, -1, weight, 0)
oahzxl's avatar
oahzxl committed
347

oahzxl's avatar
oahzxl committed
348
        if bias:
349
            self._mark_idx_equal(input_node, -1, bias, 0)
oahzxl's avatar
oahzxl committed
350

oahzxl's avatar
oahzxl committed
351
    def _assign_matmul_index(self, node, node_idx):
oahzxl's avatar
oahzxl committed
352
353
354
355
356
357
358
359
360
        """
        Assign index for matmul op.
        1. copy trace from matmul_left and change last index accroding to matmul_right. (assert they have same length)
        2. mark equal for input matmul_left -1 index and matmul_right -2 dim.
        3. inherit matmul_left and matmul_right computation, mark computation for last dim.

        Args:
            node (node)
            node_idx (int)
oahzxl's avatar
oahzxl committed
361
        """
oahzxl's avatar
oahzxl committed
362
        matmul_left, matmul_right = node.args
oahzxl's avatar
oahzxl committed
363
364

        assert len(_get_node_shape(matmul_left)) == len(_get_node_shape(matmul_right))
365
366
        self._assign_index_as_input(node, node_idx, matmul_left)
        self._inherit_index(matmul_right, -1, node, -1)
oahzxl's avatar
oahzxl committed
367

368
        self._mark_computation_from_node(matmul_right, node, [-1, -2])
oahzxl's avatar
oahzxl committed
369
        self._mark_computation(node, node_idx, [-1])
370
        self._mark_idx_equal(matmul_left, -1, matmul_right, -2)
oahzxl's avatar
oahzxl committed
371

oahzxl's avatar
oahzxl committed
372
    def _assign_layernorm_index(self, node, idx):
oahzxl's avatar
oahzxl committed
373
374
375
376
377
378
379
380
381
        """
        Assign index for layernorm op.
        1. assign index as input node
        2. inherit computation and mark last 2 dims as computed.

        Args:
            node (node)
            node_idx (int)
        """
oahzxl's avatar
oahzxl committed
382
        self._assign_index_as_input(node, idx)
oahzxl's avatar
oahzxl committed
383
        self._mark_computation(node, idx, [-1])
oahzxl's avatar
oahzxl committed
384

oahzxl's avatar
oahzxl committed
385
    def _assign_elementwise_index(self, node, idx):
oahzxl's avatar
oahzxl committed
386
387
388
389
390
391
392
393
        """
        Assign index for element-wise op (eg. relu sigmoid add mul).
        1. assign index as input node
        2. inherit computation from all input nodes.

        Args:
            node (node)
            node_idx (int)
oahzxl's avatar
oahzxl committed
394
        """
oahzxl's avatar
oahzxl committed
395
        self._assign_index_as_input(node, idx)
396
        nodes_in = []
oahzxl's avatar
oahzxl committed
397
        for node_in in node.args:
398
399
400
401
402
403
404
405
406
407
            if type(node_in) == type(node):
                nodes_in.append(node_in)
                self._mark_computation_from_node(node_in, node)
        assert len(nodes_in) <= 2
        if len(nodes_in) == 2:
            node_in0_shape = _get_node_shape(nodes_in[0])
            node_in1_shape = _get_node_shape(nodes_in[1])
            for i in range(-1, -min(len(node_in0_shape), len(node_in1_shape)) - 1, -1):
                if node_in0_shape[i] == node_in1_shape[i]:
                    self._mark_idx_equal(nodes_in[0], i, nodes_in[1], i)
oahzxl's avatar
oahzxl committed
408

409
410
411
412
413
    def _assgin_no_change_index(self, node, idx):
        self._assign_index_as_input(node, idx)
        for node_in in node.args:
            if type(node_in) == type(node):
                self._mark_computation_from_node(node_in, node)
oahzxl's avatar
oahzxl committed
414

415
416
417
418
419
420
421
422
423
424
    def _assign_einsum_index(self, node, idx):
        """
        Assign index for einsum op.

        Args:
            node (node)
            node_idx (int)
        """
        patterns = node.args[0]
        input_nodes = node.args[1:]
oahzxl's avatar
oahzxl committed
425

426
427
428
        patterns = patterns.replace(" ", "")
        left, right = patterns.split("->")
        left = left.split(",")
oahzxl's avatar
oahzxl committed
429

430
431
432
433
434
435
436
        all_index = []
        for i in left:
            for c in i:
                all_index.append(c)
        all_index = set(all_index)
        free_index = set([i for i in right])
        sum_index = all_index - free_index
oahzxl's avatar
oahzxl committed
437

438
439
440
441
        for right_idx, right_indice in enumerate(right):
            for left_idx, left_str in enumerate(left):
                if right_indice in left_str:
                    source_idx = left_str.index(right_indice)
oahzxl's avatar
oahzxl committed
442
443
444
445
                    self._inherit_index(
                        input_nodes[left_idx], source_idx, node, right_idx
                    )

oahzxl's avatar
oahzxl committed
446
447
448
449
450
        # for i in sum_index:
        #     for left_idx, left_str in enumerate(left):
        #         if i in left_str:
        #             self._mark_computation(node, idx, left_str.index(i))
        #             break
oahzxl's avatar
oahzxl committed
451

oahzxl's avatar
oahzxl committed
452
    def _assign_softmax_index(self, node, idx):
oahzxl's avatar
oahzxl committed
453
454
455
456
457
458
459
460
        """
        Assign index for softmax op.
        1. assign index as input node
        2. inherit computation and mark softmax dim as computed.

        Args:
            node (node)
            node_idx (int)
oahzxl's avatar
oahzxl committed
461
        """
oahzxl's avatar
oahzxl committed
462
        self._assign_index_as_input(node, idx)
oahzxl's avatar
oahzxl committed
463
464
        self._mark_computation(node, idx, [node.kwargs["dim"]])

oahzxl's avatar
oahzxl committed
465
466
467
468
469
470
471
472
    def _assign_unsqueeze_index(self, node, node_idx):
        """
        Assign index for unsqueeze op.
        1. assign new index for unsqueeze dim

        Args:
            node (node)
            node_idx (int)
473
474
        """
        self._del_dim(node_idx, -1)
oahzxl's avatar
oahzxl committed
475
        self._assign_index_as_input(node, node_idx)
476
        self._add_dim(node_idx, node.args[1])
oahzxl's avatar
oahzxl committed
477

oahzxl's avatar
oahzxl committed
478
479
480
481
482
483
484
485
    def _assign_dropout_index(self, node, node_idx):
        """
        Assign index for unsqueeze op.
        1. assign new index for unsqueeze dim

        Args:
            node (node)
            node_idx (int)
oahzxl's avatar
oahzxl committed
486
        """
oahzxl's avatar
oahzxl committed
487
        self._assign_index_as_input(node, node_idx)
oahzxl's avatar
oahzxl committed
488

oahzxl's avatar
oahzxl committed
489
490
491
492
493
494
495
496
    def _assign_ones_like_index(self, node, node_idx):
        """
        Assign index for oneslike op.
        1. assign new index for all dim

        Args:
            node (node)
            node_idx (int)
oahzxl's avatar
oahzxl committed
497
        """
oahzxl's avatar
oahzxl committed
498
        self._assign_all_index(node, node_idx)
oahzxl's avatar
oahzxl committed
499

oahzxl's avatar
oahzxl committed
500
    def _assign_view_reshape_index(self, node, node_idx):
oahzxl's avatar
oahzxl committed
501
502
503
504
505
506
        """
        Assign index for view and reshape op.
        1. get origin shape and target shape by meta info.
        2. compute the real value of -1 in target shape.
        3. determine changed dim, and assgin index for generated dim.
        4. log changed dim and generated dim for restore
oahzxl's avatar
oahzxl committed
507
508
        5. inherit computation.
        6. TODO: look into view list to see whether the view is associated with other,
oahzxl's avatar
oahzxl committed
509
510
511
512
513
           if so assgin equal dim according to previous view.

        Args:
            node (node)
            node_idx (int)
oahzxl's avatar
oahzxl committed
514
        """
oahzxl's avatar
oahzxl committed
515
516
        # get data, turn into number
        origin_node = node.args[0]
oahzxl's avatar
oahzxl committed
517
        origin_shape = origin_node.meta["tensor_meta"].shape
oahzxl's avatar
oahzxl committed
518
519
520
521
522
        target_shape = []
        for i in range(1, len(node.args)):
            if isinstance(node.args[i], int):
                target_shape.append(node.args[i])
            else:
oahzxl's avatar
oahzxl committed
523
                target_shape.append(node.args[i].meta["fwd_out"][0])
oahzxl's avatar
oahzxl committed
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542

        # compute the value of -1
        if -1 in target_shape:
            origin_product = 1
            for i in origin_shape:
                origin_product *= i
            target_product = -1
            for i in target_shape:
                target_product *= i
            shape_idx = target_shape.index(-1)
            target_shape[shape_idx] = origin_product // target_product

        # determine changed dim
        len_diff = len(origin_shape) - len(target_shape)
        if len_diff == 1:
            # dim merge
            dim_equal = [i == j for i, j in zip(origin_shape[:-1], target_shape)]
            dim_to = [dim_equal.index(False)]
            dim_from = [dim_equal.index(False), dim_equal.index(False) + 1]
543
            self._add_dim(node_idx, -1)
oahzxl's avatar
oahzxl committed
544
545
546
547
548
        elif len_diff == -1:
            # dim expand
            dim_equal = [i == j for i, j in zip(origin_shape, target_shape[:-1])]
            dim_from = [dim_equal.index(False)]
            dim_to = [dim_equal.index(False), dim_equal.index(False) + 1]
549
            self._del_dim(node_idx, -1)
oahzxl's avatar
oahzxl committed
550
        else:
oahzxl's avatar
oahzxl committed
551
552
553
554
555
556
557
            raise NotImplementedError(
                "shape"
                + str(origin_shape)
                + "and"
                + str(target_shape)
                + "view not implemented"
            )
oahzxl's avatar
oahzxl committed
558
559

        # get new index
oahzxl's avatar
oahzxl committed
560
        origin_trace = self._find_idx_trace_from_node(origin_node)
561
        self._assign_index_as_input(node, node_idx, origin_node)
oahzxl's avatar
oahzxl committed
562
563
        dim_from.reverse()
        for i in dim_from:
564
            self._del_dim(node_idx, i)
oahzxl's avatar
oahzxl committed
565
        for i in dim_to:
566
            self._add_dim(node_idx, i)
oahzxl's avatar
oahzxl committed
567

oahzxl's avatar
oahzxl committed
568
        # inherit computation
oahzxl's avatar
oahzxl committed
569
        compute_log = self._find_compute_trace_from_node(origin_node)
oahzxl's avatar
oahzxl committed
570
571
572
        for i in dim_from:
            if origin_trace[i] in compute_log:
                for j in dim_to:
oahzxl's avatar
oahzxl committed
573
                    self._mark_computation(node, node_idx, [j])
oahzxl's avatar
oahzxl committed
574
                break
oahzxl's avatar
oahzxl committed
575

oahzxl's avatar
oahzxl committed
576
        # log view, not used now
oahzxl's avatar
oahzxl committed
577
578
579
580
581
582
        view_dict = {
            "idx_from": [origin_trace[i] for i in dim_from],
            "dim_from": dim_from,
            "idx_to": [self.idx_trace_list[node_idx]["idx"][i] for i in dim_to],
            "dim_to": dim_to,
        }
oahzxl's avatar
oahzxl committed
583
        self.idx_view_list[node] = view_dict
584

oahzxl's avatar
oahzxl committed
585
586
587
588
589
590
591
    def _merge_equal_idx(self):
        idx_equal = copy.deepcopy(self.idx_trace_equal)
        idx_equal.reverse()
        for idx in idx_equal:
            merge_to = min(idx)
            merge_from = max(idx)
            for trace in self.idx_trace_list:
oahzxl's avatar
oahzxl committed
592
593
594
595
596
                if merge_from in trace["idx"]:
                    trace["idx"] = [
                        merge_to if i == merge_from else i for i in trace["idx"]
                    ]

oahzxl's avatar
oahzxl committed
597
    def trace_index(self):
oahzxl's avatar
oahzxl committed
598
        for idx, node in enumerate(self.node_list):
oahzxl's avatar
oahzxl committed
599
            if node.op == "placeholder":
oahzxl's avatar
oahzxl committed
600
                self._assign_all_index(node, idx)
oahzxl's avatar
oahzxl committed
601
602
            elif node.op == "call_method":
                if "transpose" in node.name:
oahzxl's avatar
oahzxl committed
603
                    self._assign_transpose_index(node, idx)
oahzxl's avatar
oahzxl committed
604
                elif "permute" in node.name:
oahzxl's avatar
oahzxl committed
605
                    self._assign_permute_index(node, idx)
oahzxl's avatar
oahzxl committed
606
                elif "view" in node.name or "reshape" in node.name:
oahzxl's avatar
oahzxl committed
607
                    self._assign_view_reshape_index(node, idx)
oahzxl's avatar
oahzxl committed
608
                elif "unsqueeze" in node.name:
oahzxl's avatar
oahzxl committed
609
                    self._assign_unsqueeze_index(node, idx)
oahzxl's avatar
oahzxl committed
610
                elif any(i in node.name for i in ["to", "contiguous"]):
611
                    self._assgin_no_change_index(node, idx)
oahzxl's avatar
oahzxl committed
612
613
                else:
                    raise NotImplementedError(node.name, "method not implemented yet!")
oahzxl's avatar
oahzxl committed
614
615
            elif node.op == "call_function":
                if "linear" in node.name:
oahzxl's avatar
oahzxl committed
616
                    self._assign_linear_index(node, idx)
oahzxl's avatar
oahzxl committed
617
                elif "matmul" in node.name:
oahzxl's avatar
oahzxl committed
618
                    self._assign_matmul_index(node, idx)
oahzxl's avatar
oahzxl committed
619
                elif "softmax" in node.name:
oahzxl's avatar
oahzxl committed
620
                    self._assign_softmax_index(node, idx)
oahzxl's avatar
oahzxl committed
621
                elif any(n in node.name for n in ["mul", "add", "sigmoid", "relu"]):
oahzxl's avatar
oahzxl committed
622
                    self._assign_elementwise_index(node, idx)
oahzxl's avatar
oahzxl committed
623
                elif "ones_like" in node.name:
oahzxl's avatar
oahzxl committed
624
                    self._assign_ones_like_index(node, idx)
oahzxl's avatar
oahzxl committed
625
                elif "dropout" in node.name:
oahzxl's avatar
oahzxl committed
626
                    self._assign_dropout_index(node, idx)
oahzxl's avatar
oahzxl committed
627
                elif "einsum" in node.name:
628
                    self._assign_einsum_index(node, idx)
oahzxl's avatar
oahzxl committed
629
630
631
632
                elif "getattr" in node.name:
                    continue  # get attr like shape
                elif "getitem" in node.name:
                    continue  # get item in list
oahzxl's avatar
oahzxl committed
633
                else:
oahzxl's avatar
oahzxl committed
634
635
636
637
638
                    raise NotImplementedError(
                        node.name, "function not implemented yet!"
                    )
            elif node.op == "call_module":
                if any(n in node.name for n in ["layernorm", "norm"]):
oahzxl's avatar
oahzxl committed
639
                    self._assign_layernorm_index(node, idx)
oahzxl's avatar
oahzxl committed
640
641
                else:
                    raise NotImplementedError(node.name, "module not implemented yet!")
oahzxl's avatar
oahzxl committed
642
643
644
            elif node.op == "get_attr":
                self._assign_all_index(node, idx)  # get param
            elif node.op == "output":
oahzxl's avatar
oahzxl committed
645
                continue
oahzxl's avatar
oahzxl committed
646
647
            else:
                raise NotImplementedError(node.op, "op not implemented yet!")
648
        # self._merge_equal_idx()
oahzxl's avatar
oahzxl committed
649

oahzxl's avatar
oahzxl committed
650
651
652
653
654
655
656
657
658
659
660
661
    def check_index_source(self, start_dim, start_node, start_idx, end_dim, end_node):
        """
        Check 2 given index: one index should be source of the other
        Args:
            start_idx(int): start node chunk dim
            start_node(node): start node
            end_idx(int): end node chunk dim
            end_node(node): end node

        Returns:
            bool: True if check pass
        """
oahzxl's avatar
oahzxl committed
662
        start_node_idx = _find_idx_by_name(start_node.name, self.node_list)
oahzxl's avatar
oahzxl committed
663
        end_node_trace = self._find_trace_from_node(end_node)
oahzxl's avatar
oahzxl committed
664
665
666
667
        end_node_trace_source = end_node_trace["source"][end_dim]
        sorted_source = sorted(
            end_node_trace_source.items(), key=lambda d: d[0], reverse=True
        )
oahzxl's avatar
oahzxl committed
668
        for node_idx, node_dim in sorted_source:
oahzxl's avatar
oahzxl committed
669
            if node_idx == start_node_idx and start_dim in node_dim:
oahzxl's avatar
oahzxl committed
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
                return True
            # it means we meet a node outside the loop, and the node is not input node
            if node_idx < start_idx:
                return False
        return False

    def check_index_compute(self, start_idx, end_dim, end_node, end_idx):
        """
        Check 2 given index: check they haven't been computed in the source trace.
        Args:
            start_idx(int): start node chunk dim
            start_node(node): start node
            end_idx(int): end node chunk dim
            end_node(node): end node

        Returns:
            bool: True if check pass
        """
        end_node_trace = self._find_trace_from_node(end_node)
oahzxl's avatar
oahzxl committed
689
        end_node_compute = end_node_trace["compute"][end_dim]
oahzxl's avatar
oahzxl committed
690
691
        if any(start_idx <= i <= end_idx for i in end_node_compute):
            return False
692
        return True
oahzxl's avatar
oahzxl committed
693

694
    def get_node_chunk_dim(self, node_from, node_from_dim, node_to):
oahzxl's avatar
oahzxl committed
695
696
        node_from_source = self._find_source_trace_from_node(node_from)
        dim_source = node_from_source[node_from_dim]
oahzxl's avatar
oahzxl committed
697
        node_to_idx = _find_idx_by_name(node_to.name, self.node_list)
oahzxl's avatar
oahzxl committed
698
699
700
701
702
        for k, v in dim_source.items():
            if k == node_to_idx:
                return v
        return None

703
    def _find_inherit_dim(self, input_node, input_dim, node):
oahzxl's avatar
oahzxl committed
704
        input_node_idx = _find_idx_by_name(input_node.name, self.node_list)
705
706
707
708
        node_trace_source = self._find_source_trace_from_node(node)
        for node_dim in range(len(_get_node_shape(node))):
            if (
                input_node_idx in node_trace_source[node_dim]
oahzxl's avatar
oahzxl committed
709
                and input_dim[0] in node_trace_source[node_dim][input_node_idx]
710
            ):
oahzxl's avatar
oahzxl committed
711
712
                return node_dim
        return None
713

oahzxl's avatar
oahzxl committed
714
    def check_index_duplicate(self, chunk_infos, return_dim=False):
715
716
717
        input_dim_after_node = {}
        for input_node_idx, input_node in enumerate(chunk_infos["inputs"]):
            for k, v in chunk_infos["inputs_dim"][input_node_idx].items():
oahzxl's avatar
oahzxl committed
718
                inherit_dim = self._find_inherit_dim(input_node, v, self.node_list[k])
oahzxl's avatar
oahzxl committed
719
720
                if inherit_dim:
                    input_dim_after_node[k] = inherit_dim
721

oahzxl's avatar
oahzxl committed
722
        for node in self.node_list[
723
724
725
726
727
            chunk_infos["region"][0] : chunk_infos["region"][1] + 1
        ]:
            if _is_non_compute_node_except_placeholder(node):
                continue
            count = 0
oahzxl's avatar
oahzxl committed
728
            duplicate_dims = []
729
730
            node_trace_source = self._find_source_trace_from_node(node)
            for node_dim in range(len(_get_node_shape(node))):
oahzxl's avatar
oahzxl committed
731
732
                duplicate_dim = []
                duplicate_flag = False
733
734
735
                dim_source = node_trace_source[node_dim]
                for k, v in dim_source.items():
                    if chunk_infos["region"][0] <= k <= chunk_infos["region"][1]:
oahzxl's avatar
oahzxl committed
736
737
738
739
740
741
742
                        if k in input_dim_after_node and input_dim_after_node[k] in v:
                            duplicate_flag = True
                            duplicate_dim.append((k, v))
                duplicate_dims.append(duplicate_dim)
                if duplicate_flag:
                    count += 1

743
            if count > 1:
oahzxl's avatar
oahzxl committed
744
745
746
747
748
749
750
751
                if return_dim:
                    return False, duplicate_dims
                else:
                    return False
        if return_dim:
            return True, None
        else:
            return True
752

oahzxl's avatar
oahzxl committed
753
754
755
756
757
758
759
760
761
762
763
764
    def _assgin_single_node_flow(
        self,
        arg_node,
        start_idx,
        end_idx,
        cur_node_dim,
        cur_node_compute,
        cur_node_source,
        cur_node_fix_dim,
        all_node_info,
        next_node_list,
    ):
oahzxl's avatar
oahzxl committed
765
        arg_idx = _find_idx_by_name(arg_node.name, self.node_list)
oahzxl's avatar
oahzxl committed
766
767
768
        # arg in chunk range or be inputs
        if not (start_idx <= arg_idx < end_idx):
            return True
oahzxl's avatar
oahzxl committed
769

oahzxl's avatar
oahzxl committed
770
771
772
773
774
775
776
777
778
779
780
        # find arg dim
        if cur_node_dim is not None:
            # dim is computed
            if arg_idx in cur_node_compute[cur_node_dim]:
                return False
            if arg_idx not in cur_node_source[cur_node_dim]:
                arg_dim = None
            else:
                arg_dim = cur_node_source[cur_node_dim][arg_idx][0]
        else:
            arg_dim = None
oahzxl's avatar
oahzxl committed
781

oahzxl's avatar
oahzxl committed
782
783
784
785
786
787
788
        # get fix dim
        arg_fix_dim = []
        if cur_node_dim is not None:
            for i in cur_node_fix_dim:
                fix_dim_source = cur_node_source[i]
                if arg_idx in fix_dim_source:
                    arg_fix_dim.append(fix_dim_source[arg_idx][0])
oahzxl's avatar
oahzxl committed
789

oahzxl's avatar
oahzxl committed
790
791
        # if already in node_info, arg dim must be same
        if arg_node in all_node_info:
oahzxl's avatar
oahzxl committed
792
            if all_node_info[arg_node]["chunk_dim"] != arg_dim:
oahzxl's avatar
oahzxl committed
793
                return False
oahzxl's avatar
oahzxl committed
794
795
796
            all_node_info[arg_node]["fix_dim"] = list(
                set(all_node_info[arg_node]["fix_dim"] + arg_fix_dim)
            )
oahzxl's avatar
oahzxl committed
797
798
        # else add it to list
        else:
oahzxl's avatar
oahzxl committed
799
800
            all_node_info[arg_node] = {"chunk_dim": arg_dim, "fix_dim": arg_fix_dim}

oahzxl's avatar
oahzxl committed
801
802
        next_node_list.append(arg_node)
        return True
oahzxl's avatar
oahzxl committed
803

oahzxl's avatar
oahzxl committed
804
    def flow_search(self, start_idx, start_dim, end_idx, end_dim):
oahzxl's avatar
oahzxl committed
805
806
807
808
809
810
        inputs, outputs = _find_chunk_compute_input_and_output_nodes(
            self.node_list[start_idx : end_idx + 1]
        )
        # only single ouput
        if len(outputs) > 1:
            return None
oahzxl's avatar
oahzxl committed
811

oahzxl's avatar
oahzxl committed
812
        cur_node_list = [self.node_list[end_idx]]  # start from the last node
oahzxl's avatar
oahzxl committed
813
814
        all_node_info = {cur_node_list[0]: {"chunk_dim": end_dim, "fix_dim": []}}

oahzxl's avatar
oahzxl committed
815
816
817
818
819
        while len(cur_node_list) > 0:
            next_node_list = []

            for cur_node in cur_node_list:
                # get cur node info
oahzxl's avatar
oahzxl committed
820
821
                cur_node_chunk_dim = all_node_info[cur_node]["chunk_dim"]
                cur_node_fix_dim = all_node_info[cur_node]["fix_dim"]
oahzxl's avatar
oahzxl committed
822
                cur_node_idx = _find_idx_by_name(cur_node.name, self.node_list)
oahzxl's avatar
oahzxl committed
823
                if cur_node_chunk_dim:
oahzxl's avatar
oahzxl committed
824
825
                    cur_node_compute = self._find_compute_trace_from_node(cur_node)
                    cur_node_source = self._find_source_trace_from_node(cur_node)
oahzxl's avatar
oahzxl committed
826
827
                else:
                    cur_node_compute = cur_node_source = None
oahzxl's avatar
oahzxl committed
828

oahzxl's avatar
oahzxl committed
829
830
831
832
833
834
835
836
                # get all valid args
                arg_list = []
                for arg in cur_node.args:
                    if type(arg) != type(cur_node):
                        continue
                    if _is_non_compute_node(arg):
                        continue
                    arg_list.append(arg)
oahzxl's avatar
oahzxl committed
837
838
839
840
841
842
843
844
845
846
847
                    flow_flag = self._assgin_single_node_flow(
                        arg,
                        start_idx,
                        end_idx,
                        cur_node_chunk_dim,
                        cur_node_compute,
                        cur_node_source,
                        cur_node_fix_dim,
                        all_node_info,
                        next_node_list,
                    )
oahzxl's avatar
oahzxl committed
848
849
                    if flow_flag == False:
                        return None
oahzxl's avatar
oahzxl committed
850

oahzxl's avatar
oahzxl committed
851
852
853
                if len(arg_list) == 2:
                    if any(i in cur_node.name for i in ["add", "mul"]):
                        for arg in arg_list:
oahzxl's avatar
oahzxl committed
854
855
                            if not (
                                start_idx
oahzxl's avatar
oahzxl committed
856
                                <= _find_idx_by_name(arg.name, self.node_list)
oahzxl's avatar
oahzxl committed
857
858
                                < end_idx
                            ):
oahzxl's avatar
oahzxl committed
859
                                continue
oahzxl's avatar
oahzxl committed
860
861
                            arg_chunk_dim = all_node_info[arg]["chunk_dim"]
                            arg_fix_dim = all_node_info[arg]["fix_dim"]
oahzxl's avatar
oahzxl committed
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
                            arg_shape = _get_node_shape(arg)
                            # add all dim as fix dim except chunk dim
                            for i, shape in enumerate(arg_shape):
                                if shape != 1 and i != cur_node_chunk_dim:
                                    if i == arg_chunk_dim:
                                        return None
                                    if i not in arg_fix_dim:
                                        arg_fix_dim.append(i)
                    elif "einsum" in cur_node.name:
                        pass
                    elif "matmul" in cur_node.name:
                        pass
                    else:
                        raise NotImplementedError()
            cur_node_list = next_node_list
oahzxl's avatar
oahzxl committed
877

oahzxl's avatar
oahzxl committed
878
879
880
881
        inputs_dim = []
        remove_inputs = []
        for input_node in inputs:
            input_dict = {}
oahzxl's avatar
oahzxl committed
882
            input_node_idx = _find_idx_by_name(input_node.name, self.node_list)
oahzxl's avatar
oahzxl committed
883
884
885
886
887
            for user in input_node.users.keys():
                if _is_non_compute_node(user):
                    continue
                user_idx = _find_idx_by_name(user.name, self.node_list)
                if start_idx <= user_idx <= end_idx:
oahzxl's avatar
oahzxl committed
888
                    chunk_dim = all_node_info[user]["chunk_dim"]
oahzxl's avatar
oahzxl committed
889
                    if chunk_dim is not None:
oahzxl's avatar
oahzxl committed
890
891
892
893
894
                        user_source = self._find_source_trace_from_node(user)[chunk_dim]
                        if input_node_idx in user_source:
                            input_dict[user_idx] = user_source[input_node_idx]
                        else:
                            return None
oahzxl's avatar
oahzxl committed
895
896
897
898
899
900
901
            if len(input_dict) == 0:
                remove_inputs.append(input_node)
            else:
                inputs_dim.append(input_dict)
        for i in remove_inputs:
            if i in inputs:
                inputs.remove(i)
oahzxl's avatar
oahzxl committed
902

oahzxl's avatar
oahzxl committed
903
904
905
906
907
908
909
        chunk_info = {
            "region": (start_idx, end_idx),
            "inputs": inputs,
            "inputs_non_chunk": [],
            "inputs_dim": inputs_dim,
            "outputs": outputs,
            "outputs_dim": end_dim,
oahzxl's avatar
oahzxl committed
910
            "node_chunk_dim": all_node_info,
oahzxl's avatar
oahzxl committed
911
912
            "args": {},
        }
oahzxl's avatar
oahzxl committed
913

oahzxl's avatar
oahzxl committed
914
915
916
917
        # move useless nodes ahead of loop
        # get all possible prepose nodes
        maybe_prepose_nodes = []
        for node, node_info in all_node_info.items():
oahzxl's avatar
oahzxl committed
918
            if node_info["chunk_dim"] is None:
oahzxl's avatar
oahzxl committed
919
                maybe_prepose_nodes.append(node)
oahzxl's avatar
oahzxl committed
920
        maybe_prepose_nodes.sort(
oahzxl's avatar
oahzxl committed
921
            key=lambda x: _find_idx_by_name(x.name, self.node_list),
oahzxl's avatar
oahzxl committed
922
923
            reverse=True,
        )  # from last node to first node
oahzxl's avatar
oahzxl committed
924
925
926
927
928
929
        prepose_nodes = []
        # set every node as root, search its args, if all legal, turn root and args as prepose nodes
        while len(maybe_prepose_nodes) > 0:
            tmp_cur_prepose_nodes = [maybe_prepose_nodes[0]]
            tmp_cur_related_prepose_nodes = []
            prepose_flag = True
oahzxl's avatar
oahzxl committed
930

oahzxl's avatar
oahzxl committed
931
932
            # loop cur node's all arg until out of chunk
            while len(tmp_cur_prepose_nodes) > 0:
oahzxl's avatar
oahzxl committed
933
934
                if prepose_flag == False:
                    break
oahzxl's avatar
oahzxl committed
935
936
937
                tmp_next_prepose_nodes = []
                tmp_cur_related_prepose_nodes.extend(tmp_cur_prepose_nodes)
                for cur_prepose_node in tmp_cur_prepose_nodes:
oahzxl's avatar
oahzxl committed
938
939
                    if prepose_flag == False:
                        break
oahzxl's avatar
oahzxl committed
940
941
942
943
                    for cur_prepose_node_arg in cur_prepose_node.args:
                        if type(cur_prepose_node_arg) != type(cur_prepose_node):
                            continue
                        # out of loop
oahzxl's avatar
oahzxl committed
944
945
946
947
948
949
950
                        if not (
                            start_idx
                            <= _find_idx_by_name(
                                cur_prepose_node_arg.name, self.node_list
                            )
                            < end_idx
                        ):
oahzxl's avatar
oahzxl committed
951
952
953
                            continue
                        # compute op in loop
                        elif cur_prepose_node_arg in all_node_info:
oahzxl's avatar
oahzxl committed
954
                            if all_node_info[cur_prepose_node_arg]["chunk_dim"] is None:
oahzxl's avatar
oahzxl committed
955
956
957
                                tmp_next_prepose_nodes.append(cur_prepose_node_arg)
                            else:
                                prepose_flag = False
oahzxl's avatar
oahzxl committed
958
                                break
oahzxl's avatar
oahzxl committed
959
960
961
962
                        # non compute op
                        else:
                            tmp_next_prepose_nodes.append(cur_prepose_node_arg)
                tmp_cur_prepose_nodes = tmp_next_prepose_nodes
oahzxl's avatar
oahzxl committed
963

oahzxl's avatar
oahzxl committed
964
965
966
967
968
969
970
971
972
973
            if prepose_flag == False:
                maybe_prepose_nodes.remove(maybe_prepose_nodes[0])
                continue
            else:
                for n in tmp_cur_related_prepose_nodes:
                    if n not in prepose_nodes:
                        prepose_nodes.append(n)
                    if n in maybe_prepose_nodes:
                        maybe_prepose_nodes.remove(n)
        # sort by index
oahzxl's avatar
oahzxl committed
974
        prepose_nodes.sort(key=lambda x: _find_idx_by_name(x.name, self.node_list))
oahzxl's avatar
oahzxl committed
975
        chunk_info["args"]["prepose_nodes"] = prepose_nodes
oahzxl's avatar
oahzxl committed
976

oahzxl's avatar
oahzxl committed
977
        # we need to log input nodes to avoid deleteing them in the loop
oahzxl's avatar
oahzxl committed
978
979
980
981
        chunk_node_list = self.node_list[start_idx : end_idx + 1]
        # also need to get some prepose node's arg out of non_chunk_inputs
        for n in prepose_nodes:
            chunk_node_list.remove(n)
oahzxl's avatar
oahzxl committed
982
        non_chunk_inputs = _find_chunk_all_input_nodes(chunk_node_list)
oahzxl's avatar
oahzxl committed
983
        for i in non_chunk_inputs:
oahzxl's avatar
oahzxl committed
984
            if i not in chunk_info["inputs"]:
oahzxl's avatar
oahzxl committed
985
                chunk_info["inputs_non_chunk"].append(i)
oahzxl's avatar
oahzxl committed
986

oahzxl's avatar
oahzxl committed
987
988
        # reassgin reshape size, some size may have changed due to chunk
        chunk_info = self._reassgin_reshape_size(chunk_info)
oahzxl's avatar
oahzxl committed
989

oahzxl's avatar
oahzxl committed
990
        return chunk_info
oahzxl's avatar
oahzxl committed
991

oahzxl's avatar
oahzxl committed
992
    def _reassgin_reshape_size(self, chunk_info):
oahzxl's avatar
oahzxl committed
993
        chunk_region = chunk_info["region"]
oahzxl's avatar
oahzxl committed
994
        reshape_size = {}
oahzxl's avatar
oahzxl committed
995
996
997
        chunk_shape = _get_node_shape(chunk_info["outputs"][0])[
            chunk_info["outputs_dim"]
        ]
oahzxl's avatar
oahzxl committed
998
999
        for node in self.node_list[chunk_region[0] : chunk_region[1] + 1]:
            if any(i in node.name for i in ["reshape", "view"]):
oahzxl's avatar
oahzxl committed
1000
1001
                reshape_args = node.args[1:]
                reshape_log = self.idx_view_list[node]
oahzxl's avatar
oahzxl committed
1002
                chunk_dim = chunk_info["node_chunk_dim"][node]["chunk_dim"]
oahzxl's avatar
oahzxl committed
1003
1004
                reshape_size[node.name] = {}
                for reshape_arg_dim, reshape_arg in enumerate(reshape_args):
oahzxl's avatar
oahzxl committed
1005
                    if reshape_arg_dim in reshape_log["dim_to"]:
oahzxl's avatar
oahzxl committed
1006
1007
                        continue
                    if reshape_arg_dim == chunk_dim:
oahzxl's avatar
oahzxl committed
1008
1009
1010
                        reshape_size[node.name][reshape_arg.name] = (
                            "min(chunk_size, %d - chunk_idx)" % chunk_shape
                        )
oahzxl's avatar
oahzxl committed
1011
        chunk_info["reshape_size"] = reshape_size
oahzxl's avatar
oahzxl committed
1012
1013
        return chunk_info

oahzxl's avatar
oahzxl committed
1014
1015
1016
1017
1018
1019
1020
1021
1022
1023
1024
1025
1026
1027
1028
1029
1030
1031
1032
1033
1034
1035
1036
1037
1038
1039
1040
1041
1042
    def _get_reorder_map(self, chunk_info):
        reorder_map = {i: i for i in range(len(self.node_list))}

        chunk_region_start = chunk_info["region"][0]
        chunk_region_end = chunk_info["region"][1]
        chunk_prepose_nodes = chunk_info["args"]["prepose_nodes"]
        chunk_prepose_nodes_idx = [
            _find_idx_by_name(i.name, self.node_list) for i in chunk_prepose_nodes
        ]
        # put prepose nodes ahead
        for idx, n in enumerate(chunk_prepose_nodes):
            n_idx = chunk_prepose_nodes_idx[idx]
            reorder_map[n_idx] = chunk_region_start + idx
        # put other nodes after prepose nodes
        for n in self.node_list[chunk_region_start : chunk_region_end + 1]:
            if n in chunk_prepose_nodes:
                continue
            n_idx = _find_idx_by_name(n.name, self.node_list)
            pos = sum([n_idx < i for i in chunk_prepose_nodes_idx])
            reorder_map[n_idx] = n_idx + pos

        return reorder_map

    def _reorder_chunk_info(self, chunk_info, reorder_map):
        # update chunk info
        chunk_info["region"] = (
            chunk_info["region"][0] + len(chunk_info["args"]["prepose_nodes"]),
            chunk_info["region"][1],
        )
oahzxl's avatar
oahzxl committed
1043
        new_inputs_dim = []
oahzxl's avatar
oahzxl committed
1044
1045
1046
1047
        for idx, input_dim in enumerate(chunk_info["inputs_dim"]):
            new_input_dim = {}
            for k, v in input_dim.items():
                new_input_dim[reorder_map[k]] = v
oahzxl's avatar
oahzxl committed
1048
1049
            new_inputs_dim.append(new_input_dim)
        chunk_info["inputs_dim"] = new_inputs_dim
oahzxl's avatar
oahzxl committed
1050
1051
1052
1053
1054
1055
1056
1057
1058
1059
1060
1061
1062
1063
1064
1065
1066
1067
1068
1069
1070
1071
1072
1073
1074
1075
1076
1077
1078
1079
1080
1081
1082
1083
1084
1085
1086
1087
1088
1089
1090
1091
1092
1093
1094
1095
1096
1097
1098
1099
        return chunk_info

    def _update_all_reorder_map(self, reorder_map):
        for origin_idx, map_idx in self.all_reorder_map.items():
            self.all_reorder_map[origin_idx] = reorder_map[map_idx]

    def _reorder_self_node_list(self, reorder_map):
        new_node_list = [None for _ in range(len(self.node_list))]
        for old_idx, new_idx in reorder_map.items():
            new_node_list[new_idx] = self.node_list[old_idx]
        self.node_list = new_node_list

    def _reorder_idx_trace(self, reorder_map):
        # reorder list
        new_idx_trace_list = [None for _ in range(len(self.idx_trace_list))]
        for old_idx, new_idx in reorder_map.items():
            new_idx_trace_list[new_idx] = self.idx_trace_list[old_idx]
        self.idx_trace_list = new_idx_trace_list
        # update compute
        for idx_trace in self.idx_trace_list:
            compute = idx_trace["compute"]
            for dim_compute in compute:
                for idx, i in enumerate(dim_compute):
                    dim_compute[idx] = reorder_map[i]
        # update source
        for idx_trace in self.idx_trace_list:
            source = idx_trace["source"]
            for dim_idx, dim_source in enumerate(source):
                new_dim_source = {}
                for k, v in dim_source.items():
                    new_dim_source[reorder_map[k]] = v
                source[dim_idx] = new_dim_source

    def reorder_all(self, chunk_info):
        if chunk_info is None:
            return chunk_info
        if len(chunk_info["args"]["prepose_nodes"]) == 0:
            return chunk_info
        reorder_map = self._get_reorder_map(chunk_info)
        self._update_all_reorder_map(reorder_map)
        self._reorder_idx_trace(reorder_map)
        self._reorder_self_node_list(reorder_map)
        chunk_info = self._reorder_chunk_info(chunk_info, reorder_map)
        return chunk_info

    def reorder_node_list(self, node_list):
        new_node_list = [None for _ in range(len(node_list))]
        for old_idx, new_idx in self.all_reorder_map.items():
            new_node_list[new_idx] = node_list[old_idx]
        return new_node_list
oahzxl's avatar
oahzxl committed
1100
1101
1102
1103
1104
1105
1106
1107
1108
1109
1110
1111
1112
    
    def tmp_reorder(self, node_list, chunk_info):
        if len(chunk_info["args"]["prepose_nodes"]) == 0:
            return node_list, chunk_info
        reorder_map = self._get_reorder_map(chunk_info)
        
        # new tmp node list
        new_node_list = [None for _ in range(len(node_list))]
        for old_idx, new_idx in reorder_map.items():
            new_node_list[new_idx] = node_list[old_idx]
    
        chunk_info = self._reorder_chunk_info(chunk_info, reorder_map)
        return new_node_list, chunk_info
oahzxl's avatar
oahzxl committed
1113

oahzxl's avatar
oahzxl committed
1114

oahzxl's avatar
oahzxl committed
1115
class MemoryEstimator(object):
oahzxl's avatar
oahzxl committed
1116
    def __init__(self, index_tracer: IndexTracer) -> None:
oahzxl's avatar
oahzxl committed
1117
        pass
oahzxl's avatar
oahzxl committed
1118

oahzxl's avatar
oahzxl committed
1119
    def _get_meta_node_size(self, x):
oahzxl's avatar
oahzxl committed
1120
        x = x.meta["tensor_meta"]
oahzxl's avatar
oahzxl committed
1121
1122
        x = x.numel * torch.tensor([], dtype=x.dtype).element_size()
        return x
oahzxl's avatar
oahzxl committed
1123

oahzxl's avatar
oahzxl committed
1124
    def _get_output_node(self, n):
oahzxl's avatar
oahzxl committed
1125
1126
1127
1128
1129
        fwd_out = {
            x.uuid: x
            for x in n.meta["fwd_out"]
            if isinstance(x, torch.Tensor) and hasattr(x, "uuid")
        }
oahzxl's avatar
oahzxl committed
1130
1131
        out_size = activation_size(fwd_out)
        out_node = [n.name] if out_size > 0 else []
oahzxl's avatar
oahzxl committed
1132
1133
        # if any(i in n.name for i in ['transpose', 'permute', 'view']):
        #     out_size = 0
oahzxl's avatar
oahzxl committed
1134
        return out_size, out_node
oahzxl's avatar
oahzxl committed
1135

oahzxl's avatar
oahzxl committed
1136
1137
    def _get_output_node_size(self, n):
        return self._get_output_node(n)[0]
oahzxl's avatar
oahzxl committed
1138

oahzxl's avatar
oahzxl committed
1139
1140
    def _add_active_node(self, n, active_list):
        new_active = self._get_output_node(n)[1]
oahzxl's avatar
oahzxl committed
1141
        if n.op == "placeholder":
oahzxl's avatar
oahzxl committed
1142
            new_active.append(n.name)
oahzxl's avatar
oahzxl committed
1143
1144
1145
        for i in new_active:
            if i not in active_list:
                active_list.append(i)
oahzxl's avatar
oahzxl committed
1146

oahzxl's avatar
oahzxl committed
1147
    def _get_delete_node(self, user, user_to_last_uses, to_keep=None):
oahzxl's avatar
oahzxl committed
1148
1149
        delete_size = 0
        delete_node = []
oahzxl's avatar
oahzxl committed
1150
        if user.op not in ("output",):
oahzxl's avatar
oahzxl committed
1151
            nodes_to_delete = user_to_last_uses.get(user, [])
oahzxl's avatar
oahzxl committed
1152
1153
1154
1155
1156
1157
1158
1159
            if to_keep is not None:
                keep_list = []
                for n in nodes_to_delete:
                    if n.name in to_keep:
                        keep_list.append(n)
                for n in keep_list:
                    if n in nodes_to_delete:
                        nodes_to_delete.remove(n)
oahzxl's avatar
oahzxl committed
1160
1161
1162
1163
1164
1165
            if len(nodes_to_delete):
                out_node = [self._get_output_node(i) for i in nodes_to_delete]
                delete_size = sum([i[0] for i in out_node])
                for i in range(len(out_node)):
                    if out_node[i][0] > 0:
                        delete_node.append(out_node[i][1][0])
oahzxl's avatar
oahzxl committed
1166
                    elif nodes_to_delete[i].op == "placeholder":
oahzxl's avatar
oahzxl committed
1167
                        delete_node.append(nodes_to_delete[i].name)
oahzxl's avatar
oahzxl committed
1168
1169
                    # elif any(j in nodes_to_delete[i].name for j in ['transpose', 'permute', 'view']):
                    #     delete_node.append(nodes_to_delete[i].name)
oahzxl's avatar
oahzxl committed
1170
        return delete_size, delete_node
oahzxl's avatar
oahzxl committed
1171

oahzxl's avatar
oahzxl committed
1172
1173
    def _get_delete_node_size(self, user, user_to_last_uses, to_keep):
        return self._get_delete_node(user, user_to_last_uses, to_keep)[0]
oahzxl's avatar
oahzxl committed
1174

oahzxl's avatar
oahzxl committed
1175
    def _remove_deactive_node(self, user, user_to_last_uses, active_list):
oahzxl's avatar
oahzxl committed
1176
1177
        delete_node = self._get_delete_node(user, user_to_last_uses)[1]
        for i in delete_node:
oahzxl's avatar
oahzxl committed
1178
1179
            if i in active_list:
                active_list.remove(i)
oahzxl's avatar
oahzxl committed
1180
1181
1182
1183

    def _get_chunk_inputs_size(
        self, chunk_inputs, chunk_inputs_non_chunk, node_list, chunk_end_idx
    ):
oahzxl's avatar
oahzxl committed
1184
1185
1186
        nodes_to_delete = []
        for chunk_input in chunk_inputs + chunk_inputs_non_chunk:
            chunk_input_users = chunk_input.users.keys()
oahzxl's avatar
oahzxl committed
1187
1188
1189
            chunk_input_users_idx = [
                _find_idx_by_name(i.name, node_list) for i in chunk_input_users
            ]
oahzxl's avatar
oahzxl committed
1190
1191
1192
1193
1194
1195
            if all(i <= chunk_end_idx for i in chunk_input_users_idx):
                if chunk_input not in nodes_to_delete:
                    nodes_to_delete.append(chunk_input)
        out_node = [self._get_output_node(i) for i in nodes_to_delete]
        delete_size = sum([i[0] for i in out_node])
        return delete_size
oahzxl's avatar
oahzxl committed
1196

oahzxl's avatar
oahzxl committed
1197
1198
1199
1200
1201
1202
1203
1204
1205
1206
1207
1208
1209
1210
1211
1212
    def _get_last_usr(self, nodes):
        node_to_last_use: Dict[Node, Node] = {}
        user_to_last_uses: Dict[Node, List[Node]] = {}

        def register_last_uses(n: Node, user: Node):
            if n not in node_to_last_use:
                node_to_last_use[n] = user
                user_to_last_uses.setdefault(user, []).append(n)

        for node in reversed(nodes):
            map_arg(node.args, lambda n: register_last_uses(n, node))
            map_arg(node.kwargs, lambda n: register_last_uses(n, node))
        return user_to_last_uses

    def _get_contiguous_memory(self, node, not_contiguous_list, delete=False):
        mem = 0
oahzxl's avatar
oahzxl committed
1213
1214
        not_contiguous_ops = ["permute"]
        inherit_contiguous_ops = ["transpose", "view"]
oahzxl's avatar
oahzxl committed
1215

oahzxl's avatar
oahzxl committed
1216
1217
1218
        if node.op == "call_function" and any(
            n in node.name for n in ["matmul", "reshape"]
        ):
oahzxl's avatar
oahzxl committed
1219
1220
1221
1222
            for n in node.args:
                if n in not_contiguous_list:
                    # matmul won't change origin tensor, but create a tmp copy
                    mem += self._get_output_node_size(n)
oahzxl's avatar
oahzxl committed
1223
        elif node.op == "call_module":
oahzxl's avatar
oahzxl committed
1224
1225
1226
1227
1228
            for n in node.args:
                if n in not_contiguous_list:
                    # module will just make origin tensor to contiguous
                    if delete:
                        not_contiguous_list.remove(n)
oahzxl's avatar
oahzxl committed
1229
1230
1231
        elif node.op == "call_method" and any(
            i in node.name for i in not_contiguous_ops
        ):
oahzxl's avatar
oahzxl committed
1232
1233
1234
1235
            if node not in not_contiguous_list:
                not_contiguous_list.append(node)
        return mem

oahzxl's avatar
oahzxl committed
1236
1237
1238
    def _get_chunk_ratio(self, node, chunk_node_dim, chunk_size):
        if node not in chunk_node_dim:
            return 1.0
oahzxl's avatar
oahzxl committed
1239
        node_shape = _get_node_shape(node)
oahzxl's avatar
oahzxl committed
1240
        chunk_dim = chunk_node_dim[node]["chunk_dim"]
oahzxl's avatar
oahzxl committed
1241
1242
1243
1244
        if chunk_dim is None:
            return 1.0
        else:
            return float(chunk_size) / node_shape[chunk_dim]
oahzxl's avatar
oahzxl committed
1245

oahzxl's avatar
oahzxl committed
1246
    def _get_chunk_delete_node_size(
oahzxl's avatar
oahzxl committed
1247
        self, user, user_to_last_uses, chunk_ratio, chunk_inputs_names
oahzxl's avatar
oahzxl committed
1248
    ):
oahzxl's avatar
oahzxl committed
1249
1250
        # if any(j in user.name for j in ['transpose', 'permute', 'view']):
        #     return 0
oahzxl's avatar
oahzxl committed
1251
        if user.op in ("placeholder", "output"):
oahzxl's avatar
oahzxl committed
1252
1253
1254
1255
            return 0
        nodes_to_delete = user_to_last_uses.get(user, [])
        delete_size = 0
        for n in nodes_to_delete:
oahzxl's avatar
oahzxl committed
1256
1257
1258
            if n.name in chunk_inputs_names:
                continue
            delete_size += self._get_output_node_size(n) * chunk_ratio
oahzxl's avatar
oahzxl committed
1259
        return delete_size
oahzxl's avatar
oahzxl committed
1260

oahzxl's avatar
oahzxl committed
1261
1262
1263
1264
    def _print_mem_log(self, log, nodes, title=None):
        if title:
            print(title)
        for idx, (l, n) in enumerate(zip(log, nodes)):
oahzxl's avatar
oahzxl committed
1265
            print("%s:%.2f \t" % (n.name, l), end="")
oahzxl's avatar
oahzxl committed
1266
1267
1268
1269
            if (idx + 1) % 3 == 0:
                print("")
        print("\n")

oahzxl's avatar
oahzxl committed
1270
1271
1272
1273
    def _print_compute_op_mem_log(self, log, nodes, title=None):
        if title:
            print(title)
        for idx, (l, n) in enumerate(zip(log, nodes)):
oahzxl's avatar
oahzxl committed
1274
            if n.op in ["placeholder", "get_attr", "output"]:
oahzxl's avatar
oahzxl committed
1275
                continue
oahzxl's avatar
oahzxl committed
1276
            if any(i in n.name for i in ["getitem", "getattr"]):
oahzxl's avatar
oahzxl committed
1277
                continue
oahzxl's avatar
oahzxl committed
1278
            print("%s:%.2f \t" % (n.name, l), end="")
oahzxl's avatar
oahzxl committed
1279
1280
1281
            if (idx + 1) % 3 == 0:
                print("")
        print("\n")
oahzxl's avatar
oahzxl committed
1282
1283
1284

    def estimate_chunk_inference_mem(
        self,
oahzxl's avatar
oahzxl committed
1285
        node_list,
oahzxl's avatar
oahzxl committed
1286
        chunk_infos=None,
oahzxl's avatar
oahzxl committed
1287
        print_mem=False,
oahzxl's avatar
oahzxl committed
1288
    ):
oahzxl's avatar
oahzxl committed
1289
1290
1291
        act_memory = 0.0
        act_memory_peak_log = []
        act_memory_after_node_log = []
oahzxl's avatar
oahzxl committed
1292
1293
        active_node_list = []
        active_node_list_log = []
oahzxl's avatar
oahzxl committed
1294
        not_contiguous_list = []
oahzxl's avatar
oahzxl committed
1295
1296
1297
        user_to_last_uses = self._get_last_usr(node_list)
        user_to_last_uses_no_free_var = self._get_last_usr(node_list)
        _delete_free_var_from_last_use(user_to_last_uses_no_free_var)
oahzxl's avatar
oahzxl committed
1298

oahzxl's avatar
oahzxl committed
1299
        use_chunk = True if chunk_infos is not None else False
oahzxl's avatar
oahzxl committed
1300
        chunk_within = False
oahzxl's avatar
oahzxl committed
1301
        chunk_region_idx = None
oahzxl's avatar
oahzxl committed
1302
        chunk_ratio = 1  # use it to estimate chunk mem
oahzxl's avatar
oahzxl committed
1303
        chunk_inputs_names = []
oahzxl's avatar
oahzxl committed
1304

oahzxl's avatar
oahzxl committed
1305
1306
1307
1308
1309
1310
1311
1312
1313
1314
        if use_chunk:
            chunk_regions = [i["region"] for i in chunk_infos]
            chunk_starts = [i[0] for i in chunk_regions]
            chunk_ends = [i[1] for i in chunk_regions]
            chunk_inputs = [i["inputs"] for i in chunk_infos]
            chunk_inputs_non_chunk = [i["inputs_non_chunk"] for i in chunk_infos]
            chunk_inputs_names = [j.name for i in chunk_inputs for j in i] + [
                j.name for i in chunk_inputs_non_chunk for j in i
            ]
            chunk_outputs = [i["outputs"][0] for i in chunk_infos]
oahzxl's avatar
oahzxl committed
1315
            chunk_node_dim = [i["node_chunk_dim"] for i in chunk_infos]
1316
1317
1318
            chunk_sizes = [
                i["chunk_size"] if "chunk_size" in i else 1 for i in chunk_infos
            ]
oahzxl's avatar
oahzxl committed
1319
1320
1321

        for idx, node in enumerate(node_list):
            # if node in chunk start nodes, change chunk ratio and add chunk_tensor
oahzxl's avatar
oahzxl committed
1322
            if use_chunk and idx in chunk_starts:
oahzxl's avatar
oahzxl committed
1323
                chunk_within = True
oahzxl's avatar
oahzxl committed
1324
                chunk_region_idx = chunk_starts.index(idx)
oahzxl's avatar
oahzxl committed
1325
1326
1327
                act_memory += self._get_output_node_size(
                    chunk_outputs[chunk_region_idx]
                ) / (1024**2)
oahzxl's avatar
oahzxl committed
1328
1329
1330

            # determine chunk ratio for current node
            if chunk_within:
oahzxl's avatar
oahzxl committed
1331
                chunk_ratio = self._get_chunk_ratio(
oahzxl's avatar
oahzxl committed
1332
                    node,
oahzxl's avatar
oahzxl committed
1333
                    chunk_node_dim[chunk_region_idx],
1334
                    chunk_sizes[chunk_region_idx],
oahzxl's avatar
oahzxl committed
1335
1336
                )

oahzxl's avatar
oahzxl committed
1337
            # if node is placeholder, just add the size of the node
oahzxl's avatar
oahzxl committed
1338
1339
            if node.op == "placeholder":
                act_memory += self._get_meta_node_size(node) * chunk_ratio / (1024**2)
oahzxl's avatar
oahzxl committed
1340
1341
                act_memory_peak_log.append(act_memory)
            # skip output
oahzxl's avatar
oahzxl committed
1342
            elif node.op == "output":
oahzxl's avatar
oahzxl committed
1343
                continue
oahzxl's avatar
oahzxl committed
1344
1345
1346
1347
1348
            # no change for non compute node
            elif _is_non_compute_node_except_placeholder(node):
                act_memory_peak_log.append(act_memory)
            # node is a compute op
            # calculate tmp, output node and delete node memory
oahzxl's avatar
oahzxl committed
1349
            else:
oahzxl's avatar
oahzxl committed
1350
                # forward memory
oahzxl's avatar
oahzxl committed
1351
                # TODO: contiguous_memory still not accurate for matmul, view, reshape and transpose
oahzxl's avatar
oahzxl committed
1352
1353
1354
1355
1356
1357
1358
1359
                act_memory += (
                    self._get_contiguous_memory(node, not_contiguous_list)
                    * chunk_ratio
                    / (1024**2)
                )
                act_memory += (
                    self._get_output_node_size(node) * chunk_ratio / (1024**2)
                )
oahzxl's avatar
oahzxl committed
1360
1361
1362
                # record max act memory
                act_memory_peak_log.append(act_memory)
                # delete useless memory
oahzxl's avatar
oahzxl committed
1363
1364
1365
1366
1367
                act_memory -= (
                    self._get_contiguous_memory(node, not_contiguous_list, delete=True)
                    * chunk_ratio
                    / (1024**2)
                )
oahzxl's avatar
oahzxl committed
1368
                # delete unused vars not in chunk_input_list
oahzxl's avatar
oahzxl committed
1369
                # we can't delete input nodes until chunk ends
oahzxl's avatar
oahzxl committed
1370
                if chunk_within:
oahzxl's avatar
oahzxl committed
1371
                    act_memory -= self._get_chunk_delete_node_size(
oahzxl's avatar
oahzxl committed
1372
1373
1374
                        node,
                        user_to_last_uses_no_free_var,
                        chunk_ratio,
oahzxl's avatar
oahzxl committed
1375
                        chunk_inputs_names,
oahzxl's avatar
oahzxl committed
1376
                    ) / (1024**2)
oahzxl's avatar
oahzxl committed
1377
                else:
oahzxl's avatar
oahzxl committed
1378
                    act_memory -= self._get_delete_node_size(
oahzxl's avatar
oahzxl committed
1379
                        node, user_to_last_uses_no_free_var, chunk_inputs_names
oahzxl's avatar
oahzxl committed
1380
                    ) / (1024**2)
oahzxl's avatar
oahzxl committed
1381

oahzxl's avatar
oahzxl committed
1382
            # log active node, only effective without chunk
oahzxl's avatar
oahzxl committed
1383
1384
1385
1386
            self._add_active_node(node, active_node_list)
            self._remove_deactive_node(node, user_to_last_uses, active_node_list)

            # if node in chunk end nodes, restore chunk settings
oahzxl's avatar
oahzxl committed
1387
            if use_chunk and idx in chunk_ends:
oahzxl's avatar
oahzxl committed
1388
1389
1390
                act_memory -= (
                    self._get_output_node_size(node) * chunk_ratio / (1024**2)
                )
oahzxl's avatar
oahzxl committed
1391
                act_memory -= self._get_chunk_inputs_size(
oahzxl's avatar
oahzxl committed
1392
1393
                    chunk_inputs[chunk_region_idx],
                    chunk_inputs_non_chunk[chunk_region_idx],
oahzxl's avatar
oahzxl committed
1394
                    node_list,
oahzxl's avatar
oahzxl committed
1395
1396
                    chunk_regions[chunk_region_idx][1],
                ) / (1024**2)
oahzxl's avatar
oahzxl committed
1397
                chunk_within = False
oahzxl's avatar
oahzxl committed
1398
                chunk_ratio = 1
oahzxl's avatar
oahzxl committed
1399
                chunk_region_idx = None
oahzxl's avatar
oahzxl committed
1400

oahzxl's avatar
oahzxl committed
1401
            act_memory_after_node_log.append(act_memory)
oahzxl's avatar
oahzxl committed
1402
            active_node_list_log.append(copy.deepcopy(active_node_list))
oahzxl's avatar
oahzxl committed
1403

oahzxl's avatar
oahzxl committed
1404
1405
1406
1407
1408
        if print_mem:
            print("with chunk" if use_chunk else "without chunk")
            # self._print_mem_log(act_memory_peak_log, node_list, "peak")
            # self._print_mem_log(act_memory_after_node_log, node_list, "after")
            self._print_compute_op_mem_log(act_memory_peak_log, node_list, "peak")
oahzxl's avatar
oahzxl committed
1409
1410
1411
            self._print_compute_op_mem_log(
                act_memory_after_node_log, node_list, "after"
            )
oahzxl's avatar
oahzxl committed
1412

oahzxl's avatar
oahzxl committed
1413
1414
1415
1416
1417
        # param_memory = parameter_size(gm)
        # all_memory = act_memory + param_memory
        return act_memory_peak_log, act_memory_after_node_log, active_node_list_log


oahzxl's avatar
oahzxl committed
1418
class ChunkSelector(object):
oahzxl's avatar
oahzxl committed
1419
    def __init__(
oahzxl's avatar
oahzxl committed
1420
1421
1422
1423
        self,
        index_tracer: IndexTracer,
        memory_estimator: MemoryEstimator,
        max_memory=None,
oahzxl's avatar
oahzxl committed
1424
    ):
oahzxl's avatar
oahzxl committed
1425
        self.index_tracer = index_tracer
oahzxl's avatar
oahzxl committed
1426
        self.memory_estimator = memory_estimator
oahzxl's avatar
oahzxl committed
1427
1428
1429
1430
1431
        if max_memory is not None:
            self.stratge = "fit_memory"
            self.max_memory = max_memory  # MB
        else:
            self.stratge = "min_memory"
oahzxl's avatar
oahzxl committed
1432
1433
1434
1435
1436
1437
1438
1439
1440

    def _select_best_chunk_region(
        self, possible_chunk_regions, chunk_infos, peak_node, max_chunk_region, mem_peak
    ):
        if self.stratge == "min_memory":
            best_region = self._select_min_memory_chunk_region(
                possible_chunk_regions, chunk_infos
            )
        elif self.stratge == "fit_memory":
oahzxl's avatar
oahzxl committed
1441
            best_region = self._select_fit_memory_chunk_region(
oahzxl's avatar
oahzxl committed
1442
1443
1444
1445
1446
1447
                possible_chunk_regions,
                chunk_infos,
                peak_node,
                max_chunk_region,
                mem_peak,
            )
oahzxl's avatar
oahzxl committed
1448
1449
1450
        else:
            raise RuntimeError()
        return best_region
oahzxl's avatar
oahzxl committed
1451
1452
1453
1454

    def _select_fit_memory_chunk_region(
        self, possible_chunk_regions, chunk_infos, peak_node, max_chunk_region, mem_peak
    ):
oahzxl's avatar
oahzxl committed
1455
1456
1457
        # stop chunk if max memory satisfy memory limit
        if max(mem_peak) < self.max_memory:
            return None
oahzxl's avatar
oahzxl committed
1458

oahzxl's avatar
oahzxl committed
1459
1460
1461
1462
1463
1464
1465
1466
        # remove illegal regions
        illegal_regions = []
        for i in possible_chunk_regions:
            if not self._is_legal_region(i, chunk_infos):
                illegal_regions.append(i)
        for i in illegal_regions:
            if i in possible_chunk_regions:
                possible_chunk_regions.remove(i)
oahzxl's avatar
oahzxl committed
1467

oahzxl's avatar
oahzxl committed
1468
1469
1470
        # get mem for chunk region
        regions_dict = []
        for region in possible_chunk_regions:
oahzxl's avatar
oahzxl committed
1471
1472
1473
            cur_region = region.copy()
            cur_node_list, cur_region = self.index_tracer.tmp_reorder(self.index_tracer.node_list, cur_region)
            cur_chunk_infos = chunk_infos + [cur_region]
oahzxl's avatar
oahzxl committed
1474
            cur_mem_peak = self.memory_estimator.estimate_chunk_inference_mem(
oahzxl's avatar
oahzxl committed
1475
                cur_node_list, cur_chunk_infos
oahzxl's avatar
oahzxl committed
1476
1477
1478
1479
            )[0]
            cur_chunk_region_peak = cur_mem_peak[
                max_chunk_region[0] : max_chunk_region[1] + 1
            ]
oahzxl's avatar
oahzxl committed
1480
1481
            cur_chunk_region_max_peak = max(cur_chunk_region_peak)
            if cur_chunk_region_max_peak < self.max_memory:
oahzxl's avatar
oahzxl committed
1482
1483
1484
1485
1486
1487
1488
1489
1490
                regions_dict.append(
                    {
                        "chunk_info": region,
                        "chunk_max_mem": cur_chunk_region_max_peak,
                        "chunk_len": self._get_compute_node_num(
                            region["region"][0], region["region"][1]
                        ),
                    }
                )
oahzxl's avatar
oahzxl committed
1491
1492
1493
        # no region found
        if len(regions_dict) == 0:
            return None
oahzxl's avatar
oahzxl committed
1494

oahzxl's avatar
oahzxl committed
1495
1496
1497
1498
        # select the min chunk len
        chunk_len = [i["chunk_len"] for i in regions_dict]
        best_region_idx = chunk_len.index(min(chunk_len))
        best_region = regions_dict[best_region_idx]["chunk_info"]
1499
1500
1501

        # get max chunk size
        best_region = self._get_fit_chunk_size(best_region, chunk_infos)
oahzxl's avatar
oahzxl committed
1502
        return best_region
oahzxl's avatar
oahzxl committed
1503

1504
1505
1506
1507
1508
1509
1510
1511
    def _get_fit_chunk_size(self, chunk_info, chunk_infos):
        chunk_size = 1
        chunk_info["chunk_size"] = chunk_size
        cur_chunk_max_mem = 0
        # search a region
        while cur_chunk_max_mem < self.max_memory:
            chunk_size *= 2
            chunk_info["chunk_size"] = chunk_size
oahzxl's avatar
oahzxl committed
1512
1513
1514
            cur_chunk_info = chunk_info.copy()
            cur_node_list, cur_chunk_info = self.index_tracer.tmp_reorder(self.index_tracer.node_list, cur_chunk_info)
            cur_chunk_infos = chunk_infos + [cur_chunk_info]
1515
            cur_mem_peak = self.memory_estimator.estimate_chunk_inference_mem(
oahzxl's avatar
oahzxl committed
1516
                cur_node_list, cur_chunk_infos
1517
1518
1519
1520
1521
1522
1523
1524
1525
1526
1527
1528
1529
1530
1531
1532
            )[0]
            cur_chunk_max_mem = max(
                cur_mem_peak[chunk_info["region"][0] : chunk_info["region"][1] + 1]
            )
        # search exact size
        chunk_info["chunk_size"] = self._chunk_size_binary_search(
            chunk_size // 2, chunk_size, chunk_info, chunk_infos
        )
        return chunk_info

    def _chunk_size_binary_search(self, l, r, chunk_info, chunk_infos):
        if l >= 16:
            gap = 4
        else:
            gap = 1
        while r >= l + gap:
oahzxl's avatar
oahzxl committed
1533
            mid = int((l + r) / 2 + 0.5)
1534
            chunk_info["chunk_size"] = mid
oahzxl's avatar
oahzxl committed
1535
1536
1537
            cur_chunk_info = chunk_info.copy()
            cur_node_list, cur_chunk_info = self.index_tracer.tmp_reorder(self.index_tracer.node_list, cur_chunk_info)
            cur_chunk_infos = chunk_infos + [cur_chunk_info]
1538
            cur_mem_peak = self.memory_estimator.estimate_chunk_inference_mem(
oahzxl's avatar
oahzxl committed
1539
                cur_node_list, cur_chunk_infos
1540
1541
1542
1543
1544
1545
1546
1547
1548
1549
            )[0]
            cur_chunk_max_mem = max(
                cur_mem_peak[chunk_info["region"][0] : chunk_info["region"][1] + 1]
            )
            if cur_chunk_max_mem >= self.max_memory:
                r = mid - gap
            else:
                l = mid + gap
        return l

oahzxl's avatar
oahzxl committed
1550
1551
    def _get_compute_node_num(self, start, end):
        count = 0
oahzxl's avatar
oahzxl committed
1552
        for i in self.index_tracer.node_list[start : end + 1]:
oahzxl's avatar
oahzxl committed
1553
            if not _is_non_compute_node(i):
oahzxl's avatar
oahzxl committed
1554
1555
                count += 1
        return count
oahzxl's avatar
oahzxl committed
1556

oahzxl's avatar
oahzxl committed
1557
1558
1559
1560
1561
1562
1563
1564
1565
1566
1567
1568
1569
    def _select_min_memory_chunk_region(self, possible_chunk_regions, chunk_infos):
        max_region_range = 0
        best_region = None
        while len(possible_chunk_regions) > 0:
            for i in possible_chunk_regions:
                if i["region"][1] - i["region"][0] > max_region_range:
                    best_region = i
                    max_region_range = i["region"][1] - i["region"][0]
            if self._is_legal_region(best_region, chunk_infos):
                break
            possible_chunk_regions.remove(i)
            max_region_range = 0
            best_region = None
oahzxl's avatar
oahzxl committed
1570
        if best_region is not None:
oahzxl's avatar
oahzxl committed
1571
            best_region["chunk_size"] = 1
oahzxl's avatar
oahzxl committed
1572
1573
1574
1575
1576
1577
1578
1579
1580
1581
1582
1583
1584
1585
1586
1587
1588
1589
        return best_region

    def _is_legal_region(self, cur_chunk_info, chunk_infos):
        (chunk_region_start, chunk_region_end) = cur_chunk_info["region"]
        if cur_chunk_info in chunk_infos:
            return False
        if chunk_region_end < chunk_region_start:
            return False
        for i in chunk_infos:
            region = i["region"]
            if not (
                (chunk_region_start > region[1] and chunk_region_end > region[1])
                or (chunk_region_start < region[0] and chunk_region_end < region[0])
            ):
                return False
        return True


oahzxl's avatar
oahzxl committed
1590
class ChunkRegionSearch(object):
oahzxl's avatar
oahzxl committed
1591
    def __init__(self, gm, max_memory=None) -> None:
oahzxl's avatar
oahzxl committed
1592
        self.gm = gm
oahzxl's avatar
oahzxl committed
1593
        self.index_tracer = IndexTracer(list(gm.graph.nodes))
oahzxl's avatar
oahzxl committed
1594
        self.index_tracer.trace_index()
oahzxl's avatar
oahzxl committed
1595
        self.memory_estimator = MemoryEstimator(self.index_tracer)
oahzxl's avatar
oahzxl committed
1596
        self.chunk_selector = ChunkSelector(
oahzxl's avatar
oahzxl committed
1597
            self.index_tracer, self.memory_estimator, max_memory=max_memory
oahzxl's avatar
oahzxl committed
1598
        )
oahzxl's avatar
oahzxl committed
1599
1600
1601

    def _find_peak_node(self, mem_peak):
        max_value = max(mem_peak)
oahzxl's avatar
oahzxl committed
1602
        max_idx = mem_peak.index(max_value)
oahzxl's avatar
oahzxl committed
1603
        return max_idx
oahzxl's avatar
oahzxl committed
1604

oahzxl's avatar
oahzxl committed
1605
1606
    def _get_free_var(self):
        free_var_idx = []
oahzxl's avatar
oahzxl committed
1607
        for idx, n in enumerate(self.index_tracer.node_list):
oahzxl's avatar
oahzxl committed
1608
            if n.op == "placeholder":
oahzxl's avatar
oahzxl committed
1609
1610
                free_var_idx.append(idx)
        return free_var_idx
oahzxl's avatar
oahzxl committed
1611

oahzxl's avatar
oahzxl committed
1612
1613
1614
1615
1616
1617
1618
1619
    def _get_min_free_var(self, active_node_list, free_vars):
        min_len = 999
        for idx, n in enumerate(active_node_list):
            if idx in free_vars:
                continue
            if len(n) < min_len:
                min_len = len(n)
        return min_len
oahzxl's avatar
oahzxl committed
1620

1621
    def _search_max_chunk_region(self, active_node, peak_node, chunk_regions):
oahzxl's avatar
oahzxl committed
1622
        free_vars = self._get_free_var()
oahzxl's avatar
oahzxl committed
1623
1624
1625
1626
        free_var_num = len(free_vars)
        active_node_num = [len(i) for i in active_node]
        min_active_node_num = min(active_node_num[free_var_num:])
        threshold = max(free_var_num, min_active_node_num)
oahzxl's avatar
oahzxl committed
1627

oahzxl's avatar
oahzxl committed
1628
        # from peak_node to free_var
oahzxl's avatar
oahzxl committed
1629
1630
        inside_flag = False
        chunk_region_start = free_var_num
oahzxl's avatar
oahzxl committed
1631
        for i in range(peak_node, -1, -1):
oahzxl's avatar
oahzxl committed
1632
1633
1634
            if active_node_num[i] <= threshold:
                inside_flag = True
            if inside_flag and active_node_num[i] > threshold:
oahzxl's avatar
oahzxl committed
1635
1636
                chunk_region_start = i + 1
                break
oahzxl's avatar
oahzxl committed
1637

oahzxl's avatar
oahzxl committed
1638
        # from peak_node to len-2
oahzxl's avatar
oahzxl committed
1639
        inside_flag = False
oahzxl's avatar
oahzxl committed
1640
        chunk_region_end = len(active_node) - 1
oahzxl's avatar
oahzxl committed
1641
        for i in range(peak_node, len(active_node)):
oahzxl's avatar
oahzxl committed
1642
1643
1644
            if active_node_num[i] <= threshold:
                inside_flag = True
            if inside_flag and active_node_num[i] > threshold:
oahzxl's avatar
oahzxl committed
1645
                chunk_region_end = i
oahzxl's avatar
oahzxl committed
1646
                break
1647
1648
1649
1650
1651
1652
1653
1654
1655
1656
1657
1658
1659
1660
1661

        for i in chunk_regions:
            region = i["region"]
            if chunk_region_start >= region[0] and chunk_region_end <= region[1]:
                return None
            elif (
                region[0] <= chunk_region_start <= region[1]
                and chunk_region_end > region[1]
            ):
                chunk_region_start = region[1] + 1
            elif (
                region[0] <= chunk_region_end <= region[1]
                and chunk_region_start < region[0]
            ):
                chunk_region_end = region[0] - 1
oahzxl's avatar
oahzxl committed
1662
        return chunk_region_start, chunk_region_end
oahzxl's avatar
oahzxl committed
1663

oahzxl's avatar
oahzxl committed
1664
    def _is_not_compute(self, trace, chunk_range, dim_idx):
oahzxl's avatar
oahzxl committed
1665
        if trace["idx"][dim_idx] not in trace["compute"]:
oahzxl's avatar
oahzxl committed
1666
            return True
oahzxl's avatar
oahzxl committed
1667
1668
1669
1670
        if trace["idx"][dim_idx] in trace["compute"] and all(
            i < chunk_range[0] or i > chunk_range[1]
            for i in trace["compute"][trace["idx"][dim_idx]]
        ):
oahzxl's avatar
oahzxl committed
1671
1672
            return True
        return False
oahzxl's avatar
oahzxl committed
1673

oahzxl's avatar
oahzxl committed
1674
    def _find_free_dim(self, input_trace, output_trace, start_idx, end_idx):
oahzxl's avatar
oahzxl committed
1675
1676
        start_traces = input_trace[start_idx]
        end_trace = output_trace[end_idx]
oahzxl's avatar
oahzxl committed
1677
        end_node = self.index_tracer.node_list[end_idx]
oahzxl's avatar
oahzxl committed
1678
        chunk_infos = []
oahzxl's avatar
oahzxl committed
1679
        for end_dim, _ in enumerate(end_trace["idx"]):
oahzxl's avatar
oahzxl committed
1680
            if len(start_traces) > 1:
1681
                continue
oahzxl's avatar
oahzxl committed
1682
            for start_node, start_trace in start_traces.items():
oahzxl's avatar
oahzxl committed
1683
                for start_dim, _ in enumerate(start_trace["idx"]):
oahzxl's avatar
oahzxl committed
1684
                    # dim size cannot be 1
oahzxl's avatar
oahzxl committed
1685
1686
1687
1688
                    if (
                        _get_node_shape(end_node)[end_dim] == 1
                        or _get_node_shape(start_node)[start_dim] == 1
                    ):
oahzxl's avatar
oahzxl committed
1689
1690
1691
                        continue
                    # check index source align
                    if not self.index_tracer.check_index_source(
oahzxl's avatar
oahzxl committed
1692
1693
                        start_dim, start_node, start_idx, end_dim, end_node
                    ):
oahzxl's avatar
oahzxl committed
1694
1695
1696
                        continue
                    # check index copmute
                    if not self.index_tracer.check_index_compute(
oahzxl's avatar
oahzxl committed
1697
1698
                        start_idx, end_dim, end_node, end_idx
                    ):
oahzxl's avatar
oahzxl committed
1699
                        continue
oahzxl's avatar
oahzxl committed
1700
                    # flow search
oahzxl's avatar
oahzxl committed
1701
1702
                    chunk_info = self.index_tracer.flow_search(
                        start_idx, start_dim, end_idx, end_dim
oahzxl's avatar
oahzxl committed
1703
                    )
oahzxl's avatar
oahzxl committed
1704
                    if chunk_info is None:
oahzxl's avatar
oahzxl committed
1705
                        continue
1706
1707
1708
                    # check index copmute
                    if not self.index_tracer.check_index_duplicate(chunk_info):
                        continue
oahzxl's avatar
oahzxl committed
1709
1710
                    chunk_infos.append(chunk_info)
        return chunk_infos
oahzxl's avatar
oahzxl committed
1711

oahzxl's avatar
oahzxl committed
1712
1713
    def _search_possible_chunk_regions(self, max_chunk_region, peak_node):
        possible_chunk_region = []
oahzxl's avatar
oahzxl committed
1714
        output_trace = copy.deepcopy(self.index_tracer.idx_trace_list)
oahzxl's avatar
oahzxl committed
1715
        input_trace = []  # trace of a node's input nodes
oahzxl's avatar
oahzxl committed
1716
        for _, n in enumerate(self.index_tracer.node_list):
oahzxl's avatar
oahzxl committed
1717
1718
            cur_trace = {}
            for arg in n.args:
oahzxl's avatar
oahzxl committed
1719
1720
1721
                if type(arg) == type(n) and not _is_non_compute_node_except_placeholder(
                    arg
                ):
oahzxl's avatar
oahzxl committed
1722
1723
1724
1725
                    cur_trace[arg] = self.index_tracer._find_trace_from_node(arg)
            input_trace.append(cur_trace)

        for start_idx in range(max_chunk_region[0], peak_node + 1):
oahzxl's avatar
oahzxl committed
1726
            for end_idx in range(peak_node, max_chunk_region[1] + 1):
oahzxl's avatar
oahzxl committed
1727
                # skip non compute nodes
oahzxl's avatar
oahzxl committed
1728
                if _is_non_compute_node(
oahzxl's avatar
oahzxl committed
1729
1730
                    self.index_tracer.node_list[start_idx]
                ) or _is_non_compute_node(self.index_tracer.node_list[end_idx]):
oahzxl's avatar
oahzxl committed
1731
                    continue
oahzxl's avatar
oahzxl committed
1732

oahzxl's avatar
oahzxl committed
1733
                # select free dim
oahzxl's avatar
oahzxl committed
1734
1735
1736
                chunk_info = self._find_free_dim(
                    input_trace, output_trace, start_idx, end_idx
                )
oahzxl's avatar
oahzxl committed
1737
1738
                if len(chunk_info) > 0:
                    possible_chunk_region.extend(chunk_info)
oahzxl's avatar
oahzxl committed
1739
        return possible_chunk_region
oahzxl's avatar
oahzxl committed
1740

1741
    def _step_search(self, mem_peak, active_node, chunk_regions):
oahzxl's avatar
oahzxl committed
1742
        peak_node = self._find_peak_node(mem_peak)
1743
1744
1745
1746
1747
        max_chunk_region = self._search_max_chunk_region(
            active_node, peak_node, chunk_regions
        )
        if max_chunk_region == None:
            return None
oahzxl's avatar
oahzxl committed
1748
1749
1750
        possible_chunk_regions = self._search_possible_chunk_regions(
            max_chunk_region, peak_node
        )
oahzxl's avatar
oahzxl committed
1751
        best_chunk_region = self.chunk_selector._select_best_chunk_region(
oahzxl's avatar
oahzxl committed
1752
            possible_chunk_regions, chunk_regions, peak_node, max_chunk_region, mem_peak
oahzxl's avatar
oahzxl committed
1753
        )
oahzxl's avatar
oahzxl committed
1754
        best_chunk_region = self.index_tracer.reorder_all(best_chunk_region)
oahzxl's avatar
oahzxl committed
1755
        return best_chunk_region
oahzxl's avatar
oahzxl committed
1756

oahzxl's avatar
oahzxl committed
1757
1758
1759
1760
1761
    def _stop_search(self, init_mem_peak, mem_peak):
        sorted_init_mem_peak = sorted(init_mem_peak)
        if max(mem_peak) < sorted_init_mem_peak[int(len(sorted_init_mem_peak) * 0.5)]:
            return True
        return False
oahzxl's avatar
oahzxl committed
1762

oahzxl's avatar
oahzxl committed
1763
    def search_region(self):
oahzxl's avatar
oahzxl committed
1764
        chunk_infos = []
oahzxl's avatar
oahzxl committed
1765
1766
1767
1768
        (
            init_mem_peak,
            _,
            active_node,
oahzxl's avatar
oahzxl committed
1769
1770
1771
        ) = self.memory_estimator.estimate_chunk_inference_mem(
            self.index_tracer.node_list
        )
oahzxl's avatar
oahzxl committed
1772
        mem_peak = init_mem_peak
oahzxl's avatar
oahzxl committed
1773

oahzxl's avatar
oahzxl committed
1774
        while True:
oahzxl's avatar
oahzxl committed
1775
1776
            chunk_info = self._step_search(mem_peak, active_node, chunk_infos)
            if chunk_info is None:
oahzxl's avatar
oahzxl committed
1777
                break
oahzxl's avatar
oahzxl committed
1778
            chunk_infos.append(chunk_info)
oahzxl's avatar
oahzxl committed
1779

oahzxl's avatar
oahzxl committed
1780
1781
1782
1783
            (
                mem_peak,
                _,
                active_node,
oahzxl's avatar
oahzxl committed
1784
            ) = self.memory_estimator.estimate_chunk_inference_mem(
oahzxl's avatar
oahzxl committed
1785
                self.index_tracer.node_list, chunk_infos
oahzxl's avatar
oahzxl committed
1786
            )
oahzxl's avatar
oahzxl committed
1787
1788
            if self._stop_search(init_mem_peak, mem_peak):
                break
oahzxl's avatar
oahzxl committed
1789
1790
1791
        self.memory_estimator.estimate_chunk_inference_mem(
            self.index_tracer.node_list, chunk_infos, print_mem=True
        )
oahzxl's avatar
oahzxl committed
1792
        return chunk_infos
oahzxl's avatar
oahzxl committed
1793
1794


oahzxl's avatar
oahzxl committed
1795
1796
1797
1798
1799
1800
1801
1802
1803
1804
1805
1806
def _gen_chunk_slice_dim(chunk_dim, chunk_idx_name, shape):
    new_shape = "["
    for idx, i in enumerate(shape):
        if idx == chunk_dim:
            new_shape += "%s:%s + chunk_size" % (chunk_idx_name, chunk_idx_name)
        else:
            new_shape += ":"
        new_shape += ", "
    new_shape = new_shape[:-2] + "]"
    return new_shape


oahzxl's avatar
oahzxl committed
1807
1808
1809
1810
1811
1812
1813
1814
1815
def _gen_loop_start(chunk_input, chunk_output, chunk_ouput_dim, chunk_size=2):
    input_node = chunk_input[0]
    out_shape = _get_node_shape(chunk_output)
    out_str = str(list(out_shape))
    context = (
        "chunk_result = torch.empty(%s, dtype=%s.dtype, device=%s.device); chunk_size = %d\nfor chunk_idx in range"
        % (out_str, input_node.name, input_node.name, chunk_size)
    )
    context += "(0, %d, chunk_size):\n" % (out_shape[chunk_ouput_dim])
oahzxl's avatar
oahzxl committed
1816
1817
1818
    return context


oahzxl's avatar
oahzxl committed
1819
1820
1821
def _gen_loop_end(
    chunk_inputs, chunk_non_compute_inputs, chunk_outputs, chunk_outputs_dim, node_list
):
oahzxl's avatar
oahzxl committed
1822
1823
    chunk_outputs_name = chunk_outputs.name
    chunk_outputs_idx = _find_idx_by_name(chunk_outputs_name, node_list)
oahzxl's avatar
oahzxl committed
1824
    chunk_output_shape = chunk_outputs.meta["tensor_meta"].shape
oahzxl's avatar
oahzxl committed
1825
1826
1827
    chunk_slice = _gen_chunk_slice_dim(
        chunk_outputs_dim, "chunk_idx", chunk_output_shape
    )
oahzxl's avatar
oahzxl committed
1828
1829
1830
1831
1832
    context = "    chunk_result%s = %s;  %s = None\n" % (
        chunk_slice,
        chunk_outputs_name,
        chunk_outputs_name,
    )
oahzxl's avatar
oahzxl committed
1833
1834
1835
    context += (
        chunk_outputs_name + " = chunk_result;  chunk_result = None;  chunk_size = None"
    )
oahzxl's avatar
oahzxl committed
1836

oahzxl's avatar
oahzxl committed
1837
    # determine if its the last use for chunk input
oahzxl's avatar
oahzxl committed
1838
    for chunk_input in chunk_inputs + chunk_non_compute_inputs:
oahzxl's avatar
oahzxl committed
1839
1840
1841
1842
1843
1844
1845
        if all(
            [
                _find_idx_by_name(user.name, node_list) <= chunk_outputs_idx
                for user in chunk_input.users.keys()
            ]
        ):
            context += ";  %s = None" % chunk_input.name
oahzxl's avatar
oahzxl committed
1846
1847

    context += "\n"
oahzxl's avatar
oahzxl committed
1848
1849
    return context

oahzxl's avatar
init  
oahzxl committed
1850

oahzxl's avatar
oahzxl committed
1851
1852
1853
1854
1855
1856
1857
1858
1859
def _find_chunk_all_input_nodes(nodes: List[Node]):
    """
    Find non-compute input and output node names.
    input nodes are nodes used in the list
    output nodes are nodes will use nodes in the list
    """
    input_nodes = []
    for node in nodes:
        for input_node in node._input_nodes.keys():
oahzxl's avatar
oahzxl committed
1860
            if input_node not in nodes and input_node not in input_nodes:
oahzxl's avatar
oahzxl committed
1861
1862
1863
1864
1865
                input_nodes.append(input_node)
    return input_nodes


def _find_chunk_compute_input_and_output_nodes(nodes: List[Node]):
oahzxl's avatar
oahzxl committed
1866
1867
1868
1869
1870
1871
1872
1873
1874
1875
1876
1877
    """
    Find non-compute input and output node names.
    input nodes are nodes used in the list
    output nodes are nodes will use nodes in the list
    """
    input_nodes = []
    output_nodes = []

    # if a node has an input node which is not in the node list
    # we treat that input node as the input of the checkpoint function
    for node in nodes:
        for input_node in node._input_nodes.keys():
oahzxl's avatar
oahzxl committed
1878
1879
1880
1881
1882
            if (
                input_node not in nodes
                and input_node not in input_nodes
                and not _is_non_compute_node_except_placeholder(input_node)
            ):
oahzxl's avatar
oahzxl committed
1883
1884
1885
1886
1887
1888
                input_nodes.append(input_node)

    # if a node has a user node which is not in the node list
    # we treat that user node as the node receiving the current node output
    for node in nodes:
        for output_node in node.users.keys():
oahzxl's avatar
oahzxl committed
1889
1890
1891
            if (
                output_node not in nodes
                and node not in output_nodes
oahzxl's avatar
oahzxl committed
1892
                and not _is_non_compute_node_except_placeholder_output(output_node)
oahzxl's avatar
oahzxl committed
1893
            ):
oahzxl's avatar
oahzxl committed
1894
1895
1896
1897
1898
                output_nodes.append(node)

    return input_nodes, output_nodes


oahzxl's avatar
oahzxl committed
1899
1900
1901
1902
1903
def _find_idx_by_name(name, nodes_list):
    for idx, node in enumerate(nodes_list):
        if node.name == name:
            return idx
    raise RuntimeError("name %s not found in node list" % name)
oahzxl's avatar
init  
oahzxl committed
1904
1905


oahzxl's avatar
oahzxl committed
1906
1907
1908
1909
1910
1911
1912
1913
1914
1915
def _replace_name(context, name_from, name_to):
    patterns = [(" ", " "), (" ", "."), (" ", ","), ("(", ")"), ("(", ",")]
    for p in patterns:
        source = p[0] + name_from + p[1]
        target = p[0] + name_to + p[1]
        if source in context:
            context = context.replace(source, target)
    return context


oahzxl's avatar
oahzxl committed
1916
1917
1918
def _replace_reshape_size(context, node_name, reshape_size_dict):
    if node_name not in reshape_size_dict:
        return context
oahzxl's avatar
oahzxl committed
1919
    for size_name, size_value in reshape_size_dict[node_name].items():
oahzxl's avatar
oahzxl committed
1920
1921
1922
        context = context.replace(size_name, size_value)
    return context

oahzxl's avatar
oahzxl committed
1923

oahzxl's avatar
oahzxl committed
1924
1925
1926
1927
1928
1929
1930
1931
def emit_code_with_chunk(
    body,
    ckpt_func,
    nodes,
    emit_node_func,
    delete_unused_value_func,
    meta_nodes,
    meta_graph,
oahzxl's avatar
oahzxl committed
1932
    max_memory=None,
oahzxl's avatar
oahzxl committed
1933
):
oahzxl's avatar
init  
oahzxl committed
1934
1935
1936
1937
1938
1939
1940
1941
1942
1943
1944
    """Emit code with nested activation checkpoint
    When we detect some of the node.activation_checkpoint is a List, we will use
    this function to emit the activation checkpoint codes.

    Args:
        body: forward code
        ckpt_func: checkpoint functions code
        nodes: graph.nodes
        emit_node_func: function to emit node
        delete_unused_value_func: function to remove the unused value
    """
oahzxl's avatar
oahzxl committed
1945
    node_list = list(nodes)
oahzxl's avatar
init  
oahzxl committed
1946

oahzxl's avatar
oahzxl committed
1947
    # find the chunk regions
oahzxl's avatar
oahzxl committed
1948
    chunk_region_search = ChunkRegionSearch(meta_graph, max_memory)
oahzxl's avatar
oahzxl committed
1949
    chunk_search = chunk_region_search.search_region()
oahzxl's avatar
init  
oahzxl committed
1950

oahzxl's avatar
oahzxl committed
1951
1952
1953
    chunk_regions = [i["region"] for i in chunk_search]
    chunk_starts = [i[0] for i in chunk_regions]
    chunk_ends = [i[1] for i in chunk_regions]
oahzxl's avatar
oahzxl committed
1954

oahzxl's avatar
oahzxl committed
1955
1956
1957
    chunk_inputs = [i["inputs"] for i in chunk_search]
    chunk_inputs_non_chunk = [i["inputs_non_chunk"] for i in chunk_search]
    chunk_inputs_dim = [i["inputs_dim"] for i in chunk_search]
oahzxl's avatar
oahzxl committed
1958
1959
    chunk_inputs_names = [j.name for i in chunk_inputs for j in i] + [
        j.name for i in chunk_inputs_non_chunk for j in i
oahzxl's avatar
oahzxl committed
1960
    ]
oahzxl's avatar
oahzxl committed
1961
1962
1963

    chunk_outputs = [i["outputs"][0] for i in chunk_search]
    chunk_outputs_dim = [i["outputs_dim"] for i in chunk_search]
oahzxl's avatar
oahzxl committed
1964

oahzxl's avatar
oahzxl committed
1965
    node_list = chunk_region_search.index_tracer.reorder_node_list(node_list)
oahzxl's avatar
init  
oahzxl committed
1966
    node_idx = 0
oahzxl's avatar
oahzxl committed
1967
    region_idx = 0
oahzxl's avatar
oahzxl committed
1968
1969
    within_chunk_region = False

oahzxl's avatar
oahzxl committed
1970
    while node_idx < len(node_list):
oahzxl's avatar
oahzxl committed
1971
        node = node_list[node_idx]
oahzxl's avatar
init  
oahzxl committed
1972

oahzxl's avatar
oahzxl committed
1973
1974
        if node_idx in chunk_starts:
            within_chunk_region = True
1975
            region_idx = chunk_starts.index(node_idx)
oahzxl's avatar
oahzxl committed
1976
1977
            body.append(
                _gen_loop_start(
oahzxl's avatar
oahzxl committed
1978
1979
1980
                    chunk_inputs[region_idx],
                    chunk_outputs[region_idx],
                    chunk_outputs_dim[region_idx],
oahzxl's avatar
oahzxl committed
1981
                    chunk_search[region_idx]["chunk_size"],
oahzxl's avatar
oahzxl committed
1982
1983
                )
            )
oahzxl's avatar
init  
oahzxl committed
1984

oahzxl's avatar
oahzxl committed
1985
        if within_chunk_region:
oahzxl's avatar
oahzxl committed
1986
1987
1988
1989
1990
1991
            emit_node_func(node, body)
            # replace input var with chunk var
            for input_node_idx, input_node in enumerate(chunk_inputs[region_idx]):
                for idx, dim in chunk_inputs_dim[region_idx][input_node_idx].items():
                    if idx == node_idx:
                        chunk_slice = _gen_chunk_slice_dim(
oahzxl's avatar
oahzxl committed
1992
                            dim[0], "chunk_idx", _get_node_shape(input_node)
oahzxl's avatar
oahzxl committed
1993
1994
1995
1996
                        )
                        body[-1] = _replace_name(
                            body[-1], input_node.name, input_node.name + chunk_slice
                        )
oahzxl's avatar
oahzxl committed
1997
1998
1999
            body[-1] = _replace_reshape_size(
                body[-1], node.name, chunk_search[region_idx]["reshape_size"]
            )
oahzxl's avatar
oahzxl committed
2000
2001
            body[-1] = "    " + body[-1]
            delete_unused_value_func(node, body, chunk_inputs_names)
oahzxl's avatar
oahzxl committed
2002
2003
2004
2005
        else:
            emit_node_func(node, body)
            if node_idx not in chunk_inputs:
                delete_unused_value_func(node, body, chunk_inputs_names)
oahzxl's avatar
init  
oahzxl committed
2006

oahzxl's avatar
oahzxl committed
2007
        if node_idx in chunk_ends:
oahzxl's avatar
oahzxl committed
2008
2009
            body.append(
                _gen_loop_end(
oahzxl's avatar
oahzxl committed
2010
2011
2012
                    chunk_inputs[region_idx],
                    chunk_inputs_non_chunk[region_idx],
                    chunk_outputs[region_idx],
oahzxl's avatar
oahzxl committed
2013
2014
                    chunk_outputs_dim[region_idx],
                    node_list,
oahzxl's avatar
oahzxl committed
2015
2016
                )
            )
oahzxl's avatar
oahzxl committed
2017
            within_chunk_region = False
oahzxl's avatar
init  
oahzxl committed
2018

oahzxl's avatar
oahzxl committed
2019
        node_idx += 1
oahzxl's avatar
init  
oahzxl committed
2020
2021
2022
2023


if CODEGEN_AVAILABLE:

oahzxl's avatar
oahzxl committed
2024
    class ChunkCodeGen(CodeGen):
oahzxl's avatar
oahzxl committed
2025
        def __init__(self, meta_graph, max_memory=None):
oahzxl's avatar
oahzxl committed
2026
            super().__init__()
oahzxl's avatar
oahzxl committed
2027
            self.meta_graph = meta_graph
oahzxl's avatar
oahzxl committed
2028
            self.max_memory = max_memory
oahzxl's avatar
oahzxl committed
2029
            self.meta_node = list(meta_graph.graph.nodes)
oahzxl's avatar
init  
oahzxl committed
2030

oahzxl's avatar
oahzxl committed
2031
2032
2033
        def _gen_python_code(
            self, nodes, root_module: str, namespace: _Namespace
        ) -> PythonCode:
oahzxl's avatar
init  
oahzxl committed
2034
2035
2036
2037
2038
2039
            free_vars: List[str] = []
            body: List[str] = []
            globals_: Dict[str, Any] = {}
            wrapped_fns: Dict[str, None] = {}

            # Wrap string in list to pass by reference
oahzxl's avatar
oahzxl committed
2040
            maybe_return_annotation: List[str] = [""]
oahzxl's avatar
init  
oahzxl committed
2041
2042
2043
2044
2045
2046
2047
2048
2049

            def add_global(name_hint: str, obj: Any):
                """Add an obj to be tracked as a global.

                We call this for names that reference objects external to the
                Graph, like functions or types.

                Returns: the global name that should be used to reference 'obj' in generated source.
                """
oahzxl's avatar
oahzxl committed
2050
2051
2052
                if (
                    _is_from_torch(obj) and obj != torch.device
                ):  # to support registering torch.device
oahzxl's avatar
init  
oahzxl committed
2053
2054
2055
2056
2057
2058
2059
2060
2061
2062
2063
2064
2065
2066
2067
                    # HACK: workaround for how torch custom ops are registered. We
                    # can't import them like normal modules so they must retain their
                    # fully qualified name.
                    return _get_qualified_name(obj)

                # normalize the name hint to get a proper identifier
                global_name = namespace.create_name(name_hint, obj)

                if global_name in globals_:
                    assert globals_[global_name] is obj
                    return global_name
                globals_[global_name] = obj
                return global_name

            # set _custom_builtins here so that we needn't import colossalai in forward
oahzxl's avatar
oahzxl committed
2068
2069
2070
            _custom_builtins["colossalai"] = _CustomBuiltin(
                "import colossalai", colossalai
            )
oahzxl's avatar
init  
oahzxl committed
2071
2072
2073
2074
2075
2076
2077
2078

            # Pre-fill the globals table with registered builtins.
            for name, (_, obj) in _custom_builtins.items():
                add_global(name, obj)

            def type_repr(o: Any):
                if o == ():
                    # Empty tuple is used for empty tuple type annotation Tuple[()]
oahzxl's avatar
oahzxl committed
2079
                    return "()"
oahzxl's avatar
init  
oahzxl committed
2080
2081
2082

                typename = _type_repr(o)

oahzxl's avatar
oahzxl committed
2083
                if hasattr(o, "__origin__"):
oahzxl's avatar
init  
oahzxl committed
2084
2085
2086
2087
                    # This is a generic type, e.g. typing.List[torch.Tensor]
                    origin_type = _origin_type_map.get(o.__origin__, o.__origin__)
                    origin_typename = add_global(_type_repr(origin_type), origin_type)

oahzxl's avatar
oahzxl committed
2088
                    if hasattr(o, "__args__"):
oahzxl's avatar
init  
oahzxl committed
2089
2090
2091
2092
2093
2094
2095
2096
2097
2098
2099
2100
2101
2102
2103
2104
2105
                        # Assign global names for each of the inner type variables.
                        args = [type_repr(arg) for arg in o.__args__]

                        if len(args) == 0:
                            # Bare type, such as `typing.Tuple` with no subscript
                            # This code-path used in Python < 3.9
                            return origin_typename

                        return f'{origin_typename}[{",".join(args)}]'
                    else:
                        # Bare type, such as `typing.Tuple` with no subscript
                        # This code-path used in Python 3.9+
                        return origin_typename

                # Common case: this is a regular module name like 'foo.bar.baz'
                return add_global(typename, o)

oahzxl's avatar
oahzxl committed
2106
2107
2108
            def _format_args(
                args: Tuple[Argument, ...], kwargs: Dict[str, Argument]
            ) -> str:
oahzxl's avatar
init  
oahzxl committed
2109
2110
                def _get_repr(arg):
                    # Handle NamedTuples (if it has `_fields`) via add_global.
oahzxl's avatar
oahzxl committed
2111
                    if isinstance(arg, tuple) and hasattr(arg, "_fields"):
oahzxl's avatar
init  
oahzxl committed
2112
2113
2114
2115
2116
                        qualified_name = _get_qualified_name(type(arg))
                        global_name = add_global(qualified_name, type(arg))
                        return f"{global_name}{repr(tuple(arg))}"
                    return repr(arg)

oahzxl's avatar
oahzxl committed
2117
2118
                args_s = ", ".join(_get_repr(a) for a in args)
                kwargs_s = ", ".join(f"{k} = {_get_repr(v)}" for k, v in kwargs.items())
oahzxl's avatar
init  
oahzxl committed
2119
                if args_s and kwargs_s:
oahzxl's avatar
oahzxl committed
2120
                    return f"{args_s}, {kwargs_s}"
oahzxl's avatar
init  
oahzxl committed
2121
2122
2123
2124
2125
2126
2127
2128
2129
2130
2131
2132
2133
2134
2135
2136
2137
                return args_s or kwargs_s

            # Run through reverse nodes and record the first instance of a use
            # of a given node. This represents the *last* use of the node in the
            # execution order of the program, which we will use to free unused
            # values
            node_to_last_use: Dict[Node, Node] = {}
            user_to_last_uses: Dict[Node, List[Node]] = {}

            def register_last_uses(n: Node, user: Node):
                if n not in node_to_last_use:
                    node_to_last_use[n] = user
                    user_to_last_uses.setdefault(user, []).append(n)

            for node in reversed(nodes):
                map_arg(node.args, lambda n: register_last_uses(n, node))
                map_arg(node.kwargs, lambda n: register_last_uses(n, node))
oahzxl's avatar
oahzxl committed
2138

oahzxl's avatar
oahzxl committed
2139
            _delete_free_var_from_last_use(user_to_last_uses)
oahzxl's avatar
oahzxl committed
2140

oahzxl's avatar
init  
oahzxl committed
2141
            # NOTE: we add a variable to distinguish body and ckpt_func
oahzxl's avatar
oahzxl committed
2142
            def delete_unused_values(user: Node, body, to_keep=[]):
oahzxl's avatar
init  
oahzxl committed
2143
2144
2145
2146
2147
                """
                Delete values after their last use. This ensures that values that are
                not used in the remainder of the code are freed and the memory usage
                of the code is optimal.
                """
oahzxl's avatar
oahzxl committed
2148
                if user.op == "placeholder":
oahzxl's avatar
init  
oahzxl committed
2149
                    return
oahzxl's avatar
oahzxl committed
2150
2151
                if user.op == "output":
                    body.append("\n")
oahzxl's avatar
init  
oahzxl committed
2152
2153
                    return
                nodes_to_delete = user_to_last_uses.get(user, [])
oahzxl's avatar
oahzxl committed
2154
                nodes_to_delete = [i for i in nodes_to_delete if i.name not in to_keep]
oahzxl's avatar
init  
oahzxl committed
2155
                if len(nodes_to_delete):
oahzxl's avatar
oahzxl committed
2156
2157
2158
2159
                    to_delete_str = " = ".join(
                        [repr(n) for n in nodes_to_delete] + ["None"]
                    )
                    body.append(f";  {to_delete_str}\n")
oahzxl's avatar
init  
oahzxl committed
2160
                else:
oahzxl's avatar
oahzxl committed
2161
                    body.append("\n")
oahzxl's avatar
init  
oahzxl committed
2162
2163
2164

            # NOTE: we add a variable to distinguish body and ckpt_func
            def emit_node(node: Node, body):
oahzxl's avatar
oahzxl committed
2165
2166
2167
2168
                maybe_type_annotation = (
                    "" if node.type is None else f" : {type_repr(node.type)}"
                )
                if node.op == "placeholder":
oahzxl's avatar
init  
oahzxl committed
2169
                    assert isinstance(node.target, str)
oahzxl's avatar
oahzxl committed
2170
2171
2172
2173
2174
2175
2176
                    maybe_default_arg = (
                        "" if not node.args else f" = {repr(node.args[0])}"
                    )
                    free_vars.append(
                        f"{node.target}{maybe_type_annotation}{maybe_default_arg}"
                    )
                    raw_name = node.target.replace("*", "")
oahzxl's avatar
init  
oahzxl committed
2177
                    if raw_name != repr(node):
oahzxl's avatar
oahzxl committed
2178
                        body.append(f"{repr(node)} = {raw_name}\n")
oahzxl's avatar
init  
oahzxl committed
2179
                    return
oahzxl's avatar
oahzxl committed
2180
                elif node.op == "call_method":
oahzxl's avatar
init  
oahzxl committed
2181
2182
                    assert isinstance(node.target, str)
                    body.append(
oahzxl's avatar
oahzxl committed
2183
2184
2185
                        f"{repr(node)}{maybe_type_annotation} = {_format_target(repr(node.args[0]), node.target)}"
                        f"({_format_args(node.args[1:], node.kwargs)})"
                    )
oahzxl's avatar
init  
oahzxl committed
2186
                    return
oahzxl's avatar
oahzxl committed
2187
                elif node.op == "call_function":
oahzxl's avatar
init  
oahzxl committed
2188
2189
                    assert callable(node.target)
                    # pretty print operators
oahzxl's avatar
oahzxl committed
2190
2191
2192
2193
                    if (
                        node.target.__module__ == "_operator"
                        and node.target.__name__ in magic_methods
                    ):
oahzxl's avatar
init  
oahzxl committed
2194
                        assert isinstance(node.args, tuple)
oahzxl's avatar
oahzxl committed
2195
2196
2197
2198
                        body.append(
                            f"{repr(node)}{maybe_type_annotation} = "
                            f"{magic_methods[node.target.__name__].format(*(repr(a) for a in node.args))}"
                        )
oahzxl's avatar
init  
oahzxl committed
2199
2200
2201
2202
                        return

                    # pretty print inplace operators; required for jit.script to work properly
                    # not currently supported in normal FX graphs, but generated by torchdynamo
oahzxl's avatar
oahzxl committed
2203
2204
2205
2206
2207
2208
2209
2210
                    if (
                        node.target.__module__ == "_operator"
                        and node.target.__name__ in inplace_methods
                    ):
                        body.append(
                            f"{inplace_methods[node.target.__name__].format(*(repr(a) for a in node.args))};  "
                            f"{repr(node)}{maybe_type_annotation} = {repr(node.args[0])}"
                        )
oahzxl's avatar
init  
oahzxl committed
2211
2212
2213
2214
2215
2216
                        return

                    qualified_name = _get_qualified_name(node.target)
                    global_name = add_global(qualified_name, node.target)
                    # special case for getattr: node.args could be 2-argument or 3-argument
                    # 2-argument: attribute access; 3-argument: fall through to attrib function call with default value
oahzxl's avatar
oahzxl committed
2217
2218
2219
2220
2221
2222
2223
                    if (
                        global_name == "getattr"
                        and isinstance(node.args, tuple)
                        and isinstance(node.args[1], str)
                        and node.args[1].isidentifier()
                        and len(node.args) == 2
                    ):
oahzxl's avatar
init  
oahzxl committed
2224
                        body.append(
oahzxl's avatar
oahzxl committed
2225
2226
                            f"{repr(node)}{maybe_type_annotation} = {_format_target(repr(node.args[0]), node.args[1])}"
                        )
oahzxl's avatar
init  
oahzxl committed
2227
2228
                        return
                    body.append(
oahzxl's avatar
oahzxl committed
2229
2230
2231
                        f"{repr(node)}{maybe_type_annotation} = {global_name}({_format_args(node.args, node.kwargs)})"
                    )
                    if node.meta.get("is_wrapped", False):
oahzxl's avatar
init  
oahzxl committed
2232
2233
                        wrapped_fns.setdefault(global_name)
                    return
oahzxl's avatar
oahzxl committed
2234
                elif node.op == "call_module":
oahzxl's avatar
init  
oahzxl committed
2235
                    assert isinstance(node.target, str)
oahzxl's avatar
oahzxl committed
2236
2237
2238
2239
                    body.append(
                        f"{repr(node)}{maybe_type_annotation} = "
                        f"{_format_target(root_module, node.target)}({_format_args(node.args, node.kwargs)})"
                    )
oahzxl's avatar
init  
oahzxl committed
2240
                    return
oahzxl's avatar
oahzxl committed
2241
                elif node.op == "get_attr":
oahzxl's avatar
init  
oahzxl committed
2242
                    assert isinstance(node.target, str)
oahzxl's avatar
oahzxl committed
2243
2244
2245
                    body.append(
                        f"{repr(node)}{maybe_type_annotation} = {_format_target(root_module, node.target)}"
                    )
oahzxl's avatar
init  
oahzxl committed
2246
                    return
oahzxl's avatar
oahzxl committed
2247
                elif node.op == "output":
oahzxl's avatar
init  
oahzxl committed
2248
2249
2250
2251
                    if node.type is not None:
                        maybe_return_annotation[0] = f" -> {type_repr(node.type)}"
                    body.append(self.generate_output(node.args[0]))
                    return
oahzxl's avatar
oahzxl committed
2252
                raise NotImplementedError(f"node: {node.op} {node.target}")
oahzxl's avatar
init  
oahzxl committed
2253
2254
2255
2256
2257
2258

            # Modified for activation checkpointing
            ckpt_func = []

            # if any node has a list of labels for activation_checkpoint, we
            # will use nested type of activation checkpoint codegen
oahzxl's avatar
oahzxl committed
2259
2260
2261
2262
2263
2264
2265
2266
            emit_code_with_chunk(
                body,
                ckpt_func,
                nodes,
                emit_node,
                delete_unused_values,
                self.meta_node,
                self.meta_graph,
oahzxl's avatar
oahzxl committed
2267
                self.max_memory,
oahzxl's avatar
oahzxl committed
2268
            )
oahzxl's avatar
init  
oahzxl committed
2269
2270
2271
2272
2273

            if len(body) == 0:
                # If the Graph has no non-placeholder nodes, no lines for the body
                # have been emitted. To continue to have valid Python code, emit a
                # single pass statement
oahzxl's avatar
oahzxl committed
2274
                body.append("pass\n")
oahzxl's avatar
init  
oahzxl committed
2275
2276

            if len(wrapped_fns) > 0:
oahzxl's avatar
oahzxl committed
2277
2278
2279
2280
                wrap_name = add_global("wrap", torch.fx.wrap)
                wrap_stmts = "\n".join(
                    [f'{wrap_name}("{name}")' for name in wrapped_fns]
                )
oahzxl's avatar
init  
oahzxl committed
2281
            else:
oahzxl's avatar
oahzxl committed
2282
                wrap_stmts = ""
oahzxl's avatar
init  
oahzxl committed
2283
2284
2285
2286
2287
2288
2289
2290
2291
2292

            if self._body_transformer:
                body = self._body_transformer(body)

            for name, value in self.additional_globals():
                add_global(name, value)

            # as we need colossalai.utils.checkpoint, we need to import colossalai
            # in forward function
            prologue = self.gen_fn_def(free_vars, maybe_return_annotation[0])
oahzxl's avatar
oahzxl committed
2293
            prologue = "".join(ckpt_func) + prologue
oahzxl's avatar
init  
oahzxl committed
2294
2295
            prologue = prologue

oahzxl's avatar
oahzxl committed
2296
2297
            code = "".join(body)
            code = "\n".join("    " + line for line in code.split("\n"))
oahzxl's avatar
init  
oahzxl committed
2298
2299
2300
2301
            fn_code = f"""
{wrap_stmts}

{prologue}
oahzxl's avatar
oahzxl committed
2302
{code}"""
oahzxl's avatar
oahzxl committed
2303
            # print(fn_code)
oahzxl's avatar
init  
oahzxl committed
2304
            return PythonCode(fn_code, globals_)