chunk_codegen.py 87.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
1043
1044
1045
1046
1047
1048
1049
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
    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],
        )
        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
            chunk_info["inputs_dim"][idx] = new_input_dim
        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
1099

oahzxl's avatar
oahzxl committed
1100
class MemoryEstimator(object):
oahzxl's avatar
oahzxl committed
1101
1102
    def __init__(self, index_tracer: IndexTracer) -> None:
        self.index_tracer = index_tracer
oahzxl's avatar
oahzxl committed
1103

oahzxl's avatar
oahzxl committed
1104
    def _get_meta_node_size(self, x):
oahzxl's avatar
oahzxl committed
1105
        x = x.meta["tensor_meta"]
oahzxl's avatar
oahzxl committed
1106
1107
        x = x.numel * torch.tensor([], dtype=x.dtype).element_size()
        return x
oahzxl's avatar
oahzxl committed
1108

oahzxl's avatar
oahzxl committed
1109
    def _get_output_node(self, n):
oahzxl's avatar
oahzxl committed
1110
1111
1112
1113
1114
        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
1115
1116
        out_size = activation_size(fwd_out)
        out_node = [n.name] if out_size > 0 else []
oahzxl's avatar
oahzxl committed
1117
1118
        # if any(i in n.name for i in ['transpose', 'permute', 'view']):
        #     out_size = 0
oahzxl's avatar
oahzxl committed
1119
        return out_size, out_node
oahzxl's avatar
oahzxl committed
1120

oahzxl's avatar
oahzxl committed
1121
1122
    def _get_output_node_size(self, n):
        return self._get_output_node(n)[0]
oahzxl's avatar
oahzxl committed
1123

oahzxl's avatar
oahzxl committed
1124
1125
    def _add_active_node(self, n, active_list):
        new_active = self._get_output_node(n)[1]
oahzxl's avatar
oahzxl committed
1126
        if n.op == "placeholder":
oahzxl's avatar
oahzxl committed
1127
            new_active.append(n.name)
oahzxl's avatar
oahzxl committed
1128
1129
1130
        for i in new_active:
            if i not in active_list:
                active_list.append(i)
oahzxl's avatar
oahzxl committed
1131

oahzxl's avatar
oahzxl committed
1132
    def _get_delete_node(self, user, user_to_last_uses, to_keep=None):
oahzxl's avatar
oahzxl committed
1133
1134
        delete_size = 0
        delete_node = []
oahzxl's avatar
oahzxl committed
1135
        if user.op not in ("output",):
oahzxl's avatar
oahzxl committed
1136
            nodes_to_delete = user_to_last_uses.get(user, [])
oahzxl's avatar
oahzxl committed
1137
1138
1139
1140
1141
1142
1143
1144
            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
1145
1146
1147
1148
1149
1150
            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
1151
                    elif nodes_to_delete[i].op == "placeholder":
oahzxl's avatar
oahzxl committed
1152
                        delete_node.append(nodes_to_delete[i].name)
oahzxl's avatar
oahzxl committed
1153
1154
                    # 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
1155
        return delete_size, delete_node
oahzxl's avatar
oahzxl committed
1156

oahzxl's avatar
oahzxl committed
1157
1158
    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
1159

oahzxl's avatar
oahzxl committed
1160
    def _remove_deactive_node(self, user, user_to_last_uses, active_list):
oahzxl's avatar
oahzxl committed
1161
1162
        delete_node = self._get_delete_node(user, user_to_last_uses)[1]
        for i in delete_node:
oahzxl's avatar
oahzxl committed
1163
1164
            if i in active_list:
                active_list.remove(i)
oahzxl's avatar
oahzxl committed
1165
1166
1167
1168

    def _get_chunk_inputs_size(
        self, chunk_inputs, chunk_inputs_non_chunk, node_list, chunk_end_idx
    ):
oahzxl's avatar
oahzxl committed
1169
1170
1171
        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
1172
1173
1174
            chunk_input_users_idx = [
                _find_idx_by_name(i.name, node_list) for i in chunk_input_users
            ]
oahzxl's avatar
oahzxl committed
1175
1176
1177
1178
1179
1180
            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
1181

oahzxl's avatar
oahzxl committed
1182
1183
1184
1185
1186
1187
1188
1189
1190
1191
1192
1193
1194
1195
1196
1197
    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
1198
1199
        not_contiguous_ops = ["permute"]
        inherit_contiguous_ops = ["transpose", "view"]
oahzxl's avatar
oahzxl committed
1200

oahzxl's avatar
oahzxl committed
1201
1202
1203
        if node.op == "call_function" and any(
            n in node.name for n in ["matmul", "reshape"]
        ):
oahzxl's avatar
oahzxl committed
1204
1205
1206
1207
            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
1208
        elif node.op == "call_module":
oahzxl's avatar
oahzxl committed
1209
1210
1211
1212
1213
            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
1214
1215
1216
        elif node.op == "call_method" and any(
            i in node.name for i in not_contiguous_ops
        ):
oahzxl's avatar
oahzxl committed
1217
1218
1219
1220
            if node not in not_contiguous_list:
                not_contiguous_list.append(node)
        return mem

oahzxl's avatar
oahzxl committed
1221
1222
1223
    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
1224
        node_shape = _get_node_shape(node)
oahzxl's avatar
oahzxl committed
1225
        chunk_dim = chunk_node_dim[node]["chunk_dim"]
oahzxl's avatar
oahzxl committed
1226
1227
1228
1229
        if chunk_dim is None:
            return 1.0
        else:
            return float(chunk_size) / node_shape[chunk_dim]
oahzxl's avatar
oahzxl committed
1230

oahzxl's avatar
oahzxl committed
1231
    def _get_chunk_delete_node_size(
oahzxl's avatar
oahzxl committed
1232
        self, user, user_to_last_uses, chunk_ratio, chunk_inputs_names
oahzxl's avatar
oahzxl committed
1233
    ):
oahzxl's avatar
oahzxl committed
1234
1235
        # if any(j in user.name for j in ['transpose', 'permute', 'view']):
        #     return 0
oahzxl's avatar
oahzxl committed
1236
        if user.op in ("placeholder", "output"):
oahzxl's avatar
oahzxl committed
1237
1238
1239
1240
            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
1241
1242
1243
            if n.name in chunk_inputs_names:
                continue
            delete_size += self._get_output_node_size(n) * chunk_ratio
oahzxl's avatar
oahzxl committed
1244
        return delete_size
oahzxl's avatar
oahzxl committed
1245

oahzxl's avatar
oahzxl committed
1246
1247
1248
1249
    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
1250
            print("%s:%.2f \t" % (n.name, l), end="")
oahzxl's avatar
oahzxl committed
1251
1252
1253
1254
            if (idx + 1) % 3 == 0:
                print("")
        print("\n")

oahzxl's avatar
oahzxl committed
1255
1256
1257
1258
    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
1259
            if n.op in ["placeholder", "get_attr", "output"]:
oahzxl's avatar
oahzxl committed
1260
                continue
oahzxl's avatar
oahzxl committed
1261
            if any(i in n.name for i in ["getitem", "getattr"]):
oahzxl's avatar
oahzxl committed
1262
                continue
oahzxl's avatar
oahzxl committed
1263
            print("%s:%.2f \t" % (n.name, l), end="")
oahzxl's avatar
oahzxl committed
1264
1265
1266
            if (idx + 1) % 3 == 0:
                print("")
        print("\n")
oahzxl's avatar
oahzxl committed
1267
1268
1269

    def estimate_chunk_inference_mem(
        self,
oahzxl's avatar
oahzxl committed
1270
        node_list,
oahzxl's avatar
oahzxl committed
1271
        chunk_infos=None,
oahzxl's avatar
oahzxl committed
1272
        print_mem=False,
oahzxl's avatar
oahzxl committed
1273
    ):
oahzxl's avatar
oahzxl committed
1274
1275
1276
        act_memory = 0.0
        act_memory_peak_log = []
        act_memory_after_node_log = []
oahzxl's avatar
oahzxl committed
1277
1278
        active_node_list = []
        active_node_list_log = []
oahzxl's avatar
oahzxl committed
1279
        not_contiguous_list = []
oahzxl's avatar
oahzxl committed
1280
1281
1282
        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
1283

oahzxl's avatar
oahzxl committed
1284
        use_chunk = True if chunk_infos is not None else False
oahzxl's avatar
oahzxl committed
1285
        chunk_within = False
oahzxl's avatar
oahzxl committed
1286
        chunk_region_idx = None
oahzxl's avatar
oahzxl committed
1287
        chunk_ratio = 1  # use it to estimate chunk mem
oahzxl's avatar
oahzxl committed
1288
        chunk_inputs_names = []
oahzxl's avatar
oahzxl committed
1289

oahzxl's avatar
oahzxl committed
1290
1291
1292
1293
1294
1295
1296
1297
1298
1299
        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
1300
            chunk_node_dim = [i["node_chunk_dim"] for i in chunk_infos]
1301
1302
1303
            chunk_sizes = [
                i["chunk_size"] if "chunk_size" in i else 1 for i in chunk_infos
            ]
oahzxl's avatar
oahzxl committed
1304
1305
1306

        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
1307
            if use_chunk and idx in chunk_starts:
oahzxl's avatar
oahzxl committed
1308
                chunk_within = True
oahzxl's avatar
oahzxl committed
1309
                chunk_region_idx = chunk_starts.index(idx)
oahzxl's avatar
oahzxl committed
1310
1311
1312
                act_memory += self._get_output_node_size(
                    chunk_outputs[chunk_region_idx]
                ) / (1024**2)
oahzxl's avatar
oahzxl committed
1313
1314
1315

            # determine chunk ratio for current node
            if chunk_within:
oahzxl's avatar
oahzxl committed
1316
                chunk_ratio = self._get_chunk_ratio(
oahzxl's avatar
oahzxl committed
1317
                    node,
oahzxl's avatar
oahzxl committed
1318
                    chunk_node_dim[chunk_region_idx],
1319
                    chunk_sizes[chunk_region_idx],
oahzxl's avatar
oahzxl committed
1320
1321
                )

oahzxl's avatar
oahzxl committed
1322
            # if node is placeholder, just add the size of the node
oahzxl's avatar
oahzxl committed
1323
1324
            if node.op == "placeholder":
                act_memory += self._get_meta_node_size(node) * chunk_ratio / (1024**2)
oahzxl's avatar
oahzxl committed
1325
1326
                act_memory_peak_log.append(act_memory)
            # skip output
oahzxl's avatar
oahzxl committed
1327
            elif node.op == "output":
oahzxl's avatar
oahzxl committed
1328
                continue
oahzxl's avatar
oahzxl committed
1329
1330
1331
1332
1333
            # 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
1334
            else:
oahzxl's avatar
oahzxl committed
1335
                # forward memory
oahzxl's avatar
oahzxl committed
1336
                # TODO: contiguous_memory still not accurate for matmul, view, reshape and transpose
oahzxl's avatar
oahzxl committed
1337
1338
1339
1340
1341
1342
1343
1344
                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
1345
1346
1347
                # record max act memory
                act_memory_peak_log.append(act_memory)
                # delete useless memory
oahzxl's avatar
oahzxl committed
1348
1349
1350
1351
1352
                act_memory -= (
                    self._get_contiguous_memory(node, not_contiguous_list, delete=True)
                    * chunk_ratio
                    / (1024**2)
                )
oahzxl's avatar
oahzxl committed
1353
                # delete unused vars not in chunk_input_list
oahzxl's avatar
oahzxl committed
1354
                # we can't delete input nodes until chunk ends
oahzxl's avatar
oahzxl committed
1355
                if chunk_within:
oahzxl's avatar
oahzxl committed
1356
                    act_memory -= self._get_chunk_delete_node_size(
oahzxl's avatar
oahzxl committed
1357
1358
1359
                        node,
                        user_to_last_uses_no_free_var,
                        chunk_ratio,
oahzxl's avatar
oahzxl committed
1360
                        chunk_inputs_names,
oahzxl's avatar
oahzxl committed
1361
                    ) / (1024**2)
oahzxl's avatar
oahzxl committed
1362
                else:
oahzxl's avatar
oahzxl committed
1363
                    act_memory -= self._get_delete_node_size(
oahzxl's avatar
oahzxl committed
1364
                        node, user_to_last_uses_no_free_var, chunk_inputs_names
oahzxl's avatar
oahzxl committed
1365
                    ) / (1024**2)
oahzxl's avatar
oahzxl committed
1366

oahzxl's avatar
oahzxl committed
1367
            # log active node, only effective without chunk
oahzxl's avatar
oahzxl committed
1368
1369
1370
1371
            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
1372
            if use_chunk and idx in chunk_ends:
oahzxl's avatar
oahzxl committed
1373
1374
1375
                act_memory -= (
                    self._get_output_node_size(node) * chunk_ratio / (1024**2)
                )
oahzxl's avatar
oahzxl committed
1376
                act_memory -= self._get_chunk_inputs_size(
oahzxl's avatar
oahzxl committed
1377
1378
                    chunk_inputs[chunk_region_idx],
                    chunk_inputs_non_chunk[chunk_region_idx],
oahzxl's avatar
oahzxl committed
1379
                    node_list,
oahzxl's avatar
oahzxl committed
1380
1381
                    chunk_regions[chunk_region_idx][1],
                ) / (1024**2)
oahzxl's avatar
oahzxl committed
1382
                chunk_within = False
oahzxl's avatar
oahzxl committed
1383
                chunk_ratio = 1
oahzxl's avatar
oahzxl committed
1384
                chunk_region_idx = None
oahzxl's avatar
oahzxl committed
1385

oahzxl's avatar
oahzxl committed
1386
            act_memory_after_node_log.append(act_memory)
oahzxl's avatar
oahzxl committed
1387
            active_node_list_log.append(copy.deepcopy(active_node_list))
oahzxl's avatar
oahzxl committed
1388

oahzxl's avatar
oahzxl committed
1389
1390
1391
1392
1393
        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
1394
1395
1396
            self._print_compute_op_mem_log(
                act_memory_after_node_log, node_list, "after"
            )
oahzxl's avatar
oahzxl committed
1397

oahzxl's avatar
oahzxl committed
1398
1399
1400
1401
1402
        # 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
1403
class ChunkSelector(object):
oahzxl's avatar
oahzxl committed
1404
    def __init__(
oahzxl's avatar
oahzxl committed
1405
1406
1407
1408
        self,
        index_tracer: IndexTracer,
        memory_estimator: MemoryEstimator,
        max_memory=None,
oahzxl's avatar
oahzxl committed
1409
    ):
oahzxl's avatar
oahzxl committed
1410
        self.index_tracer = index_tracer
oahzxl's avatar
oahzxl committed
1411
        self.memory_estimator = memory_estimator
oahzxl's avatar
oahzxl committed
1412
1413
1414
1415
1416
        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
1417
1418
1419
1420
1421
1422
1423
1424
1425

    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
1426
            best_region = self._select_fit_memory_chunk_region(
oahzxl's avatar
oahzxl committed
1427
1428
1429
1430
1431
1432
                possible_chunk_regions,
                chunk_infos,
                peak_node,
                max_chunk_region,
                mem_peak,
            )
oahzxl's avatar
oahzxl committed
1433
1434
1435
        else:
            raise RuntimeError()
        return best_region
oahzxl's avatar
oahzxl committed
1436
1437
1438
1439

    def _select_fit_memory_chunk_region(
        self, possible_chunk_regions, chunk_infos, peak_node, max_chunk_region, mem_peak
    ):
oahzxl's avatar
oahzxl committed
1440
1441
1442
        # stop chunk if max memory satisfy memory limit
        if max(mem_peak) < self.max_memory:
            return None
oahzxl's avatar
oahzxl committed
1443

oahzxl's avatar
oahzxl committed
1444
1445
1446
1447
1448
1449
1450
1451
        # 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
1452

oahzxl's avatar
oahzxl committed
1453
1454
1455
1456
1457
        # get mem for chunk region
        regions_dict = []
        for region in possible_chunk_regions:
            cur_chunk_infos = chunk_infos + [region]
            cur_mem_peak = self.memory_estimator.estimate_chunk_inference_mem(
oahzxl's avatar
oahzxl committed
1458
1459
1460
1461
1462
                self.index_tracer.node_list, cur_chunk_infos
            )[0]
            cur_chunk_region_peak = cur_mem_peak[
                max_chunk_region[0] : max_chunk_region[1] + 1
            ]
oahzxl's avatar
oahzxl committed
1463
1464
            cur_chunk_region_max_peak = max(cur_chunk_region_peak)
            if cur_chunk_region_max_peak < self.max_memory:
oahzxl's avatar
oahzxl committed
1465
1466
1467
1468
1469
1470
1471
1472
1473
                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
1474
1475
1476
        # no region found
        if len(regions_dict) == 0:
            return None
oahzxl's avatar
oahzxl committed
1477

oahzxl's avatar
oahzxl committed
1478
1479
1480
1481
        # 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"]
1482
1483
1484

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

1487
1488
1489
1490
1491
1492
1493
1494
1495
1496
1497
1498
1499
1500
1501
1502
1503
1504
1505
1506
1507
1508
1509
1510
1511
1512
1513
    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
            cur_chunk_infos = chunk_infos + [chunk_info]
            cur_mem_peak = self.memory_estimator.estimate_chunk_inference_mem(
                self.index_tracer.node_list, cur_chunk_infos
            )[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
1514
            mid = int(l + (r - l) / 2)
1515
1516
1517
1518
1519
1520
1521
1522
1523
1524
1525
1526
1527
1528
            chunk_info["chunk_size"] = mid
            cur_chunk_infos = chunk_infos + [chunk_info]
            cur_mem_peak = self.memory_estimator.estimate_chunk_inference_mem(
                self.index_tracer.node_list, cur_chunk_infos
            )[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
1529
1530
    def _get_compute_node_num(self, start, end):
        count = 0
oahzxl's avatar
oahzxl committed
1531
        for i in self.index_tracer.node_list[start : end + 1]:
oahzxl's avatar
oahzxl committed
1532
1533
1534
            if _is_non_compute_node(i):
                count += 1
        return count
oahzxl's avatar
oahzxl committed
1535

oahzxl's avatar
oahzxl committed
1536
1537
1538
1539
1540
1541
1542
1543
1544
1545
1546
1547
1548
    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
1549
1550
        if best_region is not None:
            best_region["chunk_size"] = 2
oahzxl's avatar
oahzxl committed
1551
1552
1553
1554
1555
1556
1557
1558
1559
1560
1561
1562
1563
1564
1565
1566
1567
1568
        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
1569
class ChunkRegionSearch(object):
oahzxl's avatar
oahzxl committed
1570
    def __init__(self, gm, max_memory=None) -> None:
oahzxl's avatar
oahzxl committed
1571
        self.gm = gm
oahzxl's avatar
oahzxl committed
1572
        self.index_tracer = IndexTracer(list(gm.graph.nodes))
oahzxl's avatar
oahzxl committed
1573
        self.index_tracer.trace_index()
oahzxl's avatar
oahzxl committed
1574
        self.memory_estimator = MemoryEstimator(self.index_tracer)
oahzxl's avatar
oahzxl committed
1575
        self.chunk_selector = ChunkSelector(
oahzxl's avatar
oahzxl committed
1576
            self.index_tracer, self.memory_estimator, max_memory=max_memory
oahzxl's avatar
oahzxl committed
1577
        )
oahzxl's avatar
oahzxl committed
1578
1579
1580

    def _find_peak_node(self, mem_peak):
        max_value = max(mem_peak)
oahzxl's avatar
oahzxl committed
1581
        max_idx = mem_peak.index(max_value)
oahzxl's avatar
oahzxl committed
1582
        return max_idx
oahzxl's avatar
oahzxl committed
1583

oahzxl's avatar
oahzxl committed
1584
1585
    def _get_free_var(self):
        free_var_idx = []
oahzxl's avatar
oahzxl committed
1586
        for idx, n in enumerate(self.index_tracer.node_list):
oahzxl's avatar
oahzxl committed
1587
            if n.op == "placeholder":
oahzxl's avatar
oahzxl committed
1588
1589
                free_var_idx.append(idx)
        return free_var_idx
oahzxl's avatar
oahzxl committed
1590

oahzxl's avatar
oahzxl committed
1591
1592
1593
1594
1595
1596
1597
1598
    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
1599

1600
    def _search_max_chunk_region(self, active_node, peak_node, chunk_regions):
oahzxl's avatar
oahzxl committed
1601
        free_vars = self._get_free_var()
oahzxl's avatar
oahzxl committed
1602
1603
1604
1605
        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
1606

oahzxl's avatar
oahzxl committed
1607
        # from peak_node to free_var
oahzxl's avatar
oahzxl committed
1608
1609
        inside_flag = False
        chunk_region_start = free_var_num
oahzxl's avatar
oahzxl committed
1610
        for i in range(peak_node, -1, -1):
oahzxl's avatar
oahzxl committed
1611
1612
1613
            if active_node_num[i] <= threshold:
                inside_flag = True
            if inside_flag and active_node_num[i] > threshold:
oahzxl's avatar
oahzxl committed
1614
1615
                chunk_region_start = i + 1
                break
oahzxl's avatar
oahzxl committed
1616

oahzxl's avatar
oahzxl committed
1617
        # from peak_node to len-2
oahzxl's avatar
oahzxl committed
1618
        inside_flag = False
oahzxl's avatar
oahzxl committed
1619
        chunk_region_end = len(active_node) - 1
oahzxl's avatar
oahzxl committed
1620
        for i in range(peak_node, len(active_node)):
oahzxl's avatar
oahzxl committed
1621
1622
1623
            if active_node_num[i] <= threshold:
                inside_flag = True
            if inside_flag and active_node_num[i] > threshold:
oahzxl's avatar
oahzxl committed
1624
                chunk_region_end = i
oahzxl's avatar
oahzxl committed
1625
                break
1626
1627
1628
1629
1630
1631
1632
1633
1634
1635
1636
1637
1638
1639
1640

        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
1641
        return chunk_region_start, chunk_region_end
oahzxl's avatar
oahzxl committed
1642

oahzxl's avatar
oahzxl committed
1643
    def _is_not_compute(self, trace, chunk_range, dim_idx):
oahzxl's avatar
oahzxl committed
1644
        if trace["idx"][dim_idx] not in trace["compute"]:
oahzxl's avatar
oahzxl committed
1645
            return True
oahzxl's avatar
oahzxl committed
1646
1647
1648
1649
        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
1650
1651
            return True
        return False
oahzxl's avatar
oahzxl committed
1652

oahzxl's avatar
oahzxl committed
1653
    def _find_free_dim(self, input_trace, output_trace, start_idx, end_idx):
oahzxl's avatar
oahzxl committed
1654
1655
        start_traces = input_trace[start_idx]
        end_trace = output_trace[end_idx]
oahzxl's avatar
oahzxl committed
1656
        end_node = self.index_tracer.node_list[end_idx]
oahzxl's avatar
oahzxl committed
1657
        chunk_infos = []
oahzxl's avatar
oahzxl committed
1658
        for end_dim, _ in enumerate(end_trace["idx"]):
oahzxl's avatar
oahzxl committed
1659
            if len(start_traces) > 1:
1660
                continue
oahzxl's avatar
oahzxl committed
1661
            for start_node, start_trace in start_traces.items():
oahzxl's avatar
oahzxl committed
1662
                for start_dim, _ in enumerate(start_trace["idx"]):
oahzxl's avatar
oahzxl committed
1663
                    # dim size cannot be 1
oahzxl's avatar
oahzxl committed
1664
1665
1666
1667
                    if (
                        _get_node_shape(end_node)[end_dim] == 1
                        or _get_node_shape(start_node)[start_dim] == 1
                    ):
oahzxl's avatar
oahzxl committed
1668
1669
1670
                        continue
                    # check index source align
                    if not self.index_tracer.check_index_source(
oahzxl's avatar
oahzxl committed
1671
1672
                        start_dim, start_node, start_idx, end_dim, end_node
                    ):
oahzxl's avatar
oahzxl committed
1673
1674
1675
                        continue
                    # check index copmute
                    if not self.index_tracer.check_index_compute(
oahzxl's avatar
oahzxl committed
1676
1677
                        start_idx, end_dim, end_node, end_idx
                    ):
oahzxl's avatar
oahzxl committed
1678
                        continue
oahzxl's avatar
oahzxl committed
1679
                    # flow search
oahzxl's avatar
oahzxl committed
1680
1681
                    chunk_info = self.index_tracer.flow_search(
                        start_idx, start_dim, end_idx, end_dim
oahzxl's avatar
oahzxl committed
1682
                    )
oahzxl's avatar
oahzxl committed
1683
                    if chunk_info is None:
oahzxl's avatar
oahzxl committed
1684
                        continue
1685
1686
1687
                    # check index copmute
                    if not self.index_tracer.check_index_duplicate(chunk_info):
                        continue
oahzxl's avatar
oahzxl committed
1688
1689
                    chunk_infos.append(chunk_info)
        return chunk_infos
oahzxl's avatar
oahzxl committed
1690

oahzxl's avatar
oahzxl committed
1691
1692
    def _search_possible_chunk_regions(self, max_chunk_region, peak_node):
        possible_chunk_region = []
oahzxl's avatar
oahzxl committed
1693
        output_trace = copy.deepcopy(self.index_tracer.idx_trace_list)
oahzxl's avatar
oahzxl committed
1694
        input_trace = []  # trace of a node's input nodes
oahzxl's avatar
oahzxl committed
1695
        for _, n in enumerate(self.index_tracer.node_list):
oahzxl's avatar
oahzxl committed
1696
1697
            cur_trace = {}
            for arg in n.args:
oahzxl's avatar
oahzxl committed
1698
1699
1700
                if type(arg) == type(n) and not _is_non_compute_node_except_placeholder(
                    arg
                ):
oahzxl's avatar
oahzxl committed
1701
1702
1703
1704
                    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
1705
            for end_idx in range(peak_node, max_chunk_region[1] + 1):
oahzxl's avatar
oahzxl committed
1706
                # skip non compute nodes
oahzxl's avatar
oahzxl committed
1707
                if _is_non_compute_node(
oahzxl's avatar
oahzxl committed
1708
1709
                    self.index_tracer.node_list[start_idx]
                ) or _is_non_compute_node(self.index_tracer.node_list[end_idx]):
oahzxl's avatar
oahzxl committed
1710
                    continue
oahzxl's avatar
oahzxl committed
1711

oahzxl's avatar
oahzxl committed
1712
                # select free dim
oahzxl's avatar
oahzxl committed
1713
1714
1715
                chunk_info = self._find_free_dim(
                    input_trace, output_trace, start_idx, end_idx
                )
oahzxl's avatar
oahzxl committed
1716
1717
                if len(chunk_info) > 0:
                    possible_chunk_region.extend(chunk_info)
oahzxl's avatar
oahzxl committed
1718
        return possible_chunk_region
oahzxl's avatar
oahzxl committed
1719

1720
    def _step_search(self, mem_peak, active_node, chunk_regions):
oahzxl's avatar
oahzxl committed
1721
        peak_node = self._find_peak_node(mem_peak)
1722
1723
1724
1725
1726
        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
1727
1728
1729
        possible_chunk_regions = self._search_possible_chunk_regions(
            max_chunk_region, peak_node
        )
oahzxl's avatar
oahzxl committed
1730
        best_chunk_region = self.chunk_selector._select_best_chunk_region(
oahzxl's avatar
oahzxl committed
1731
            possible_chunk_regions, chunk_regions, peak_node, max_chunk_region, mem_peak
oahzxl's avatar
oahzxl committed
1732
        )
oahzxl's avatar
oahzxl committed
1733
        best_chunk_region = self.index_tracer.reorder_all(best_chunk_region)
oahzxl's avatar
oahzxl committed
1734
        return best_chunk_region
oahzxl's avatar
oahzxl committed
1735

oahzxl's avatar
oahzxl committed
1736
1737
1738
1739
1740
    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
1741

oahzxl's avatar
oahzxl committed
1742
    def search_region(self):
oahzxl's avatar
oahzxl committed
1743
        chunk_infos = []
oahzxl's avatar
oahzxl committed
1744
1745
1746
1747
        (
            init_mem_peak,
            _,
            active_node,
oahzxl's avatar
oahzxl committed
1748
1749
1750
        ) = self.memory_estimator.estimate_chunk_inference_mem(
            self.index_tracer.node_list
        )
oahzxl's avatar
oahzxl committed
1751
        mem_peak = init_mem_peak
oahzxl's avatar
oahzxl committed
1752

oahzxl's avatar
oahzxl committed
1753
        while True:
oahzxl's avatar
oahzxl committed
1754
1755
            chunk_info = self._step_search(mem_peak, active_node, chunk_infos)
            if chunk_info is None:
oahzxl's avatar
oahzxl committed
1756
                break
oahzxl's avatar
oahzxl committed
1757
            chunk_infos.append(chunk_info)
oahzxl's avatar
oahzxl committed
1758

oahzxl's avatar
oahzxl committed
1759
1760
1761
1762
            (
                mem_peak,
                _,
                active_node,
oahzxl's avatar
oahzxl committed
1763
            ) = self.memory_estimator.estimate_chunk_inference_mem(
oahzxl's avatar
oahzxl committed
1764
                self.index_tracer.node_list, chunk_infos
oahzxl's avatar
oahzxl committed
1765
            )
oahzxl's avatar
oahzxl committed
1766
1767
            if self._stop_search(init_mem_peak, mem_peak):
                break
oahzxl's avatar
oahzxl committed
1768
1769
1770
        self.memory_estimator.estimate_chunk_inference_mem(
            self.index_tracer.node_list, chunk_infos, print_mem=True
        )
oahzxl's avatar
oahzxl committed
1771
        return chunk_infos
oahzxl's avatar
oahzxl committed
1772
1773


oahzxl's avatar
oahzxl committed
1774
1775
1776
1777
1778
1779
1780
1781
1782
1783
1784
1785
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
1786
1787
1788
1789
1790
1791
1792
1793
1794
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
1795
1796
1797
    return context


oahzxl's avatar
oahzxl committed
1798
1799
1800
def _gen_loop_end(
    chunk_inputs, chunk_non_compute_inputs, chunk_outputs, chunk_outputs_dim, node_list
):
oahzxl's avatar
oahzxl committed
1801
1802
    chunk_outputs_name = chunk_outputs.name
    chunk_outputs_idx = _find_idx_by_name(chunk_outputs_name, node_list)
oahzxl's avatar
oahzxl committed
1803
    chunk_output_shape = chunk_outputs.meta["tensor_meta"].shape
oahzxl's avatar
oahzxl committed
1804
1805
1806
    chunk_slice = _gen_chunk_slice_dim(
        chunk_outputs_dim, "chunk_idx", chunk_output_shape
    )
oahzxl's avatar
oahzxl committed
1807
1808
1809
1810
1811
    context = "    chunk_result%s = %s;  %s = None\n" % (
        chunk_slice,
        chunk_outputs_name,
        chunk_outputs_name,
    )
oahzxl's avatar
oahzxl committed
1812
1813
1814
    context += (
        chunk_outputs_name + " = chunk_result;  chunk_result = None;  chunk_size = None"
    )
oahzxl's avatar
oahzxl committed
1815

oahzxl's avatar
oahzxl committed
1816
    # determine if its the last use for chunk input
oahzxl's avatar
oahzxl committed
1817
    for chunk_input in chunk_inputs + chunk_non_compute_inputs:
oahzxl's avatar
oahzxl committed
1818
1819
1820
1821
1822
1823
1824
        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
1825
1826

    context += "\n"
oahzxl's avatar
oahzxl committed
1827
1828
    return context

oahzxl's avatar
init  
oahzxl committed
1829

oahzxl's avatar
oahzxl committed
1830
1831
1832
1833
1834
1835
1836
1837
1838
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
1839
            if input_node not in nodes and input_node not in input_nodes:
oahzxl's avatar
oahzxl committed
1840
1841
1842
1843
1844
                input_nodes.append(input_node)
    return input_nodes


def _find_chunk_compute_input_and_output_nodes(nodes: List[Node]):
oahzxl's avatar
oahzxl committed
1845
1846
1847
1848
1849
1850
1851
1852
1853
1854
1855
1856
    """
    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
1857
1858
1859
1860
1861
            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
1862
1863
1864
1865
1866
1867
                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
1868
1869
1870
            if (
                output_node not in nodes
                and node not in output_nodes
oahzxl's avatar
oahzxl committed
1871
                and not _is_non_compute_node_except_placeholder_output(output_node)
oahzxl's avatar
oahzxl committed
1872
            ):
oahzxl's avatar
oahzxl committed
1873
1874
1875
1876
1877
                output_nodes.append(node)

    return input_nodes, output_nodes


oahzxl's avatar
oahzxl committed
1878
1879
1880
1881
1882
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
1883
1884


oahzxl's avatar
oahzxl committed
1885
1886
1887
1888
1889
1890
1891
1892
1893
1894
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
1895
1896
1897
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
1898
    for size_name, size_value in reshape_size_dict[node_name].items():
oahzxl's avatar
oahzxl committed
1899
1900
1901
        context = context.replace(size_name, size_value)
    return context

oahzxl's avatar
oahzxl committed
1902

oahzxl's avatar
oahzxl committed
1903
1904
1905
1906
1907
1908
1909
1910
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
1911
    max_memory=None,
oahzxl's avatar
oahzxl committed
1912
):
oahzxl's avatar
init  
oahzxl committed
1913
1914
1915
1916
1917
1918
1919
1920
1921
1922
1923
    """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
1924
    node_list = list(nodes)
oahzxl's avatar
init  
oahzxl committed
1925

oahzxl's avatar
oahzxl committed
1926
    # find the chunk regions
oahzxl's avatar
oahzxl committed
1927
    chunk_region_search = ChunkRegionSearch(meta_graph, max_memory)
oahzxl's avatar
oahzxl committed
1928
    chunk_search = chunk_region_search.search_region()
oahzxl's avatar
init  
oahzxl committed
1929

oahzxl's avatar
oahzxl committed
1930
1931
1932
    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
1933

oahzxl's avatar
oahzxl committed
1934
1935
1936
    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
1937
1938
    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
1939
    ]
oahzxl's avatar
oahzxl committed
1940
1941
1942

    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
1943

oahzxl's avatar
oahzxl committed
1944
    node_list = chunk_region_search.index_tracer.reorder_node_list(node_list)
oahzxl's avatar
init  
oahzxl committed
1945
    node_idx = 0
oahzxl's avatar
oahzxl committed
1946
    region_idx = 0
oahzxl's avatar
oahzxl committed
1947
1948
    within_chunk_region = False

oahzxl's avatar
oahzxl committed
1949
    while node_idx < len(node_list):
oahzxl's avatar
oahzxl committed
1950
        node = node_list[node_idx]
oahzxl's avatar
init  
oahzxl committed
1951

oahzxl's avatar
oahzxl committed
1952
1953
        if node_idx in chunk_starts:
            within_chunk_region = True
1954
            region_idx = chunk_starts.index(node_idx)
oahzxl's avatar
oahzxl committed
1955
1956
            body.append(
                _gen_loop_start(
oahzxl's avatar
oahzxl committed
1957
1958
1959
                    chunk_inputs[region_idx],
                    chunk_outputs[region_idx],
                    chunk_outputs_dim[region_idx],
oahzxl's avatar
oahzxl committed
1960
                    chunk_search[region_idx]["chunk_size"],
oahzxl's avatar
oahzxl committed
1961
1962
                )
            )
oahzxl's avatar
init  
oahzxl committed
1963

oahzxl's avatar
oahzxl committed
1964
        if within_chunk_region:
oahzxl's avatar
oahzxl committed
1965
1966
1967
1968
1969
1970
            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
1971
                            dim[0], "chunk_idx", _get_node_shape(input_node)
oahzxl's avatar
oahzxl committed
1972
1973
1974
1975
                        )
                        body[-1] = _replace_name(
                            body[-1], input_node.name, input_node.name + chunk_slice
                        )
oahzxl's avatar
oahzxl committed
1976
1977
1978
            body[-1] = _replace_reshape_size(
                body[-1], node.name, chunk_search[region_idx]["reshape_size"]
            )
oahzxl's avatar
oahzxl committed
1979
1980
            body[-1] = "    " + body[-1]
            delete_unused_value_func(node, body, chunk_inputs_names)
oahzxl's avatar
oahzxl committed
1981
1982
1983
1984
        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
1985

oahzxl's avatar
oahzxl committed
1986
        if node_idx in chunk_ends:
oahzxl's avatar
oahzxl committed
1987
1988
            body.append(
                _gen_loop_end(
oahzxl's avatar
oahzxl committed
1989
1990
1991
                    chunk_inputs[region_idx],
                    chunk_inputs_non_chunk[region_idx],
                    chunk_outputs[region_idx],
oahzxl's avatar
oahzxl committed
1992
1993
                    chunk_outputs_dim[region_idx],
                    node_list,
oahzxl's avatar
oahzxl committed
1994
1995
                )
            )
oahzxl's avatar
oahzxl committed
1996
            within_chunk_region = False
oahzxl's avatar
init  
oahzxl committed
1997

oahzxl's avatar
oahzxl committed
1998
        node_idx += 1
oahzxl's avatar
init  
oahzxl committed
1999
2000
2001
2002


if CODEGEN_AVAILABLE:

oahzxl's avatar
oahzxl committed
2003
    class ChunkCodeGen(CodeGen):
oahzxl's avatar
oahzxl committed
2004
        def __init__(self, meta_graph, max_memory=None):
oahzxl's avatar
oahzxl committed
2005
            super().__init__()
oahzxl's avatar
oahzxl committed
2006
            self.meta_graph = meta_graph
oahzxl's avatar
oahzxl committed
2007
            self.max_memory = max_memory
oahzxl's avatar
oahzxl committed
2008
            self.meta_node = list(meta_graph.graph.nodes)
oahzxl's avatar
init  
oahzxl committed
2009

oahzxl's avatar
oahzxl committed
2010
2011
2012
        def _gen_python_code(
            self, nodes, root_module: str, namespace: _Namespace
        ) -> PythonCode:
oahzxl's avatar
init  
oahzxl committed
2013
2014
2015
2016
2017
2018
            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
2019
            maybe_return_annotation: List[str] = [""]
oahzxl's avatar
init  
oahzxl committed
2020
2021
2022
2023
2024
2025
2026
2027
2028

            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
2029
2030
2031
                if (
                    _is_from_torch(obj) and obj != torch.device
                ):  # to support registering torch.device
oahzxl's avatar
init  
oahzxl committed
2032
2033
2034
2035
2036
2037
2038
2039
2040
2041
2042
2043
2044
2045
2046
                    # 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
2047
2048
2049
            _custom_builtins["colossalai"] = _CustomBuiltin(
                "import colossalai", colossalai
            )
oahzxl's avatar
init  
oahzxl committed
2050
2051
2052
2053
2054
2055
2056
2057

            # 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
2058
                    return "()"
oahzxl's avatar
init  
oahzxl committed
2059
2060
2061

                typename = _type_repr(o)

oahzxl's avatar
oahzxl committed
2062
                if hasattr(o, "__origin__"):
oahzxl's avatar
init  
oahzxl committed
2063
2064
2065
2066
                    # 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
2067
                    if hasattr(o, "__args__"):
oahzxl's avatar
init  
oahzxl committed
2068
2069
2070
2071
2072
2073
2074
2075
2076
2077
2078
2079
2080
2081
2082
2083
2084
                        # 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
2085
2086
2087
            def _format_args(
                args: Tuple[Argument, ...], kwargs: Dict[str, Argument]
            ) -> str:
oahzxl's avatar
init  
oahzxl committed
2088
2089
                def _get_repr(arg):
                    # Handle NamedTuples (if it has `_fields`) via add_global.
oahzxl's avatar
oahzxl committed
2090
                    if isinstance(arg, tuple) and hasattr(arg, "_fields"):
oahzxl's avatar
init  
oahzxl committed
2091
2092
2093
2094
2095
                        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
2096
2097
                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
2098
                if args_s and kwargs_s:
oahzxl's avatar
oahzxl committed
2099
                    return f"{args_s}, {kwargs_s}"
oahzxl's avatar
init  
oahzxl committed
2100
2101
2102
2103
2104
2105
2106
2107
2108
2109
2110
2111
2112
2113
2114
2115
2116
                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
2117

oahzxl's avatar
oahzxl committed
2118
            _delete_free_var_from_last_use(user_to_last_uses)
oahzxl's avatar
oahzxl committed
2119

oahzxl's avatar
init  
oahzxl committed
2120
            # NOTE: we add a variable to distinguish body and ckpt_func
oahzxl's avatar
oahzxl committed
2121
            def delete_unused_values(user: Node, body, to_keep=[]):
oahzxl's avatar
init  
oahzxl committed
2122
2123
2124
2125
2126
                """
                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
2127
                if user.op == "placeholder":
oahzxl's avatar
init  
oahzxl committed
2128
                    return
oahzxl's avatar
oahzxl committed
2129
2130
                if user.op == "output":
                    body.append("\n")
oahzxl's avatar
init  
oahzxl committed
2131
2132
                    return
                nodes_to_delete = user_to_last_uses.get(user, [])
oahzxl's avatar
oahzxl committed
2133
                nodes_to_delete = [i for i in nodes_to_delete if i.name not in to_keep]
oahzxl's avatar
init  
oahzxl committed
2134
                if len(nodes_to_delete):
oahzxl's avatar
oahzxl committed
2135
2136
2137
2138
                    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
2139
                else:
oahzxl's avatar
oahzxl committed
2140
                    body.append("\n")
oahzxl's avatar
init  
oahzxl committed
2141
2142
2143

            # NOTE: we add a variable to distinguish body and ckpt_func
            def emit_node(node: Node, body):
oahzxl's avatar
oahzxl committed
2144
2145
2146
2147
                maybe_type_annotation = (
                    "" if node.type is None else f" : {type_repr(node.type)}"
                )
                if node.op == "placeholder":
oahzxl's avatar
init  
oahzxl committed
2148
                    assert isinstance(node.target, str)
oahzxl's avatar
oahzxl committed
2149
2150
2151
2152
2153
2154
2155
                    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
2156
                    if raw_name != repr(node):
oahzxl's avatar
oahzxl committed
2157
                        body.append(f"{repr(node)} = {raw_name}\n")
oahzxl's avatar
init  
oahzxl committed
2158
                    return
oahzxl's avatar
oahzxl committed
2159
                elif node.op == "call_method":
oahzxl's avatar
init  
oahzxl committed
2160
2161
                    assert isinstance(node.target, str)
                    body.append(
oahzxl's avatar
oahzxl committed
2162
2163
2164
                        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
2165
                    return
oahzxl's avatar
oahzxl committed
2166
                elif node.op == "call_function":
oahzxl's avatar
init  
oahzxl committed
2167
2168
                    assert callable(node.target)
                    # pretty print operators
oahzxl's avatar
oahzxl committed
2169
2170
2171
2172
                    if (
                        node.target.__module__ == "_operator"
                        and node.target.__name__ in magic_methods
                    ):
oahzxl's avatar
init  
oahzxl committed
2173
                        assert isinstance(node.args, tuple)
oahzxl's avatar
oahzxl committed
2174
2175
2176
2177
                        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
2178
2179
2180
2181
                        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
2182
2183
2184
2185
2186
2187
2188
2189
                    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
2190
2191
2192
2193
2194
2195
                        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
2196
2197
2198
2199
2200
2201
2202
                    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
2203
                        body.append(
oahzxl's avatar
oahzxl committed
2204
2205
                            f"{repr(node)}{maybe_type_annotation} = {_format_target(repr(node.args[0]), node.args[1])}"
                        )
oahzxl's avatar
init  
oahzxl committed
2206
2207
                        return
                    body.append(
oahzxl's avatar
oahzxl committed
2208
2209
2210
                        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
2211
2212
                        wrapped_fns.setdefault(global_name)
                    return
oahzxl's avatar
oahzxl committed
2213
                elif node.op == "call_module":
oahzxl's avatar
init  
oahzxl committed
2214
                    assert isinstance(node.target, str)
oahzxl's avatar
oahzxl committed
2215
2216
2217
2218
                    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
2219
                    return
oahzxl's avatar
oahzxl committed
2220
                elif node.op == "get_attr":
oahzxl's avatar
init  
oahzxl committed
2221
                    assert isinstance(node.target, str)
oahzxl's avatar
oahzxl committed
2222
2223
2224
                    body.append(
                        f"{repr(node)}{maybe_type_annotation} = {_format_target(root_module, node.target)}"
                    )
oahzxl's avatar
init  
oahzxl committed
2225
                    return
oahzxl's avatar
oahzxl committed
2226
                elif node.op == "output":
oahzxl's avatar
init  
oahzxl committed
2227
2228
2229
2230
                    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
2231
                raise NotImplementedError(f"node: {node.op} {node.target}")
oahzxl's avatar
init  
oahzxl committed
2232
2233
2234
2235
2236
2237

            # 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
2238
2239
2240
2241
2242
2243
2244
2245
            emit_code_with_chunk(
                body,
                ckpt_func,
                nodes,
                emit_node,
                delete_unused_values,
                self.meta_node,
                self.meta_graph,
oahzxl's avatar
oahzxl committed
2246
                self.max_memory,
oahzxl's avatar
oahzxl committed
2247
            )
oahzxl's avatar
init  
oahzxl committed
2248
2249
2250
2251
2252

            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
2253
                body.append("pass\n")
oahzxl's avatar
init  
oahzxl committed
2254
2255

            if len(wrapped_fns) > 0:
oahzxl's avatar
oahzxl committed
2256
2257
2258
2259
                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
2260
            else:
oahzxl's avatar
oahzxl committed
2261
                wrap_stmts = ""
oahzxl's avatar
init  
oahzxl committed
2262
2263
2264
2265
2266
2267
2268
2269
2270
2271

            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
2272
            prologue = "".join(ckpt_func) + prologue
oahzxl's avatar
init  
oahzxl committed
2273
2274
            prologue = prologue

oahzxl's avatar
oahzxl committed
2275
2276
            code = "".join(body)
            code = "\n".join("    " + line for line in code.split("\n"))
oahzxl's avatar
init  
oahzxl committed
2277
2278
2279
2280
            fn_code = f"""
{wrap_stmts}

{prologue}
oahzxl's avatar
oahzxl committed
2281
{code}"""
oahzxl's avatar
oahzxl committed
2282
            # print(fn_code)
oahzxl's avatar
init  
oahzxl committed
2283
            return PythonCode(fn_code, globals_)