program.cpp 39 KB
Newer Older
1
#include "migraphx/instruction_ref.hpp"
2
#include <functional>
Paul's avatar
Paul committed
3
4
5
#include <migraphx/program.hpp>
#include <migraphx/stringutils.hpp>
#include <migraphx/instruction.hpp>
6
#include <migraphx/op/identity.hpp>
Paul's avatar
Paul committed
7
#include <migraphx/target.hpp>
Paul's avatar
Paul committed
8
9
10
#include <migraphx/env.hpp>
#include <migraphx/ranges.hpp>
#include <migraphx/time.hpp>
11
#include <migraphx/pass_manager.hpp>
12
#include <migraphx/register_target.hpp>
Shucai Xiao's avatar
Shucai Xiao committed
13
#include <migraphx/iterator_for.hpp>
14
#include <migraphx/iterator.hpp>
15
#include <migraphx/algorithm.hpp>
16
#include <migraphx/output_iterator.hpp>
Shucai Xiao's avatar
Shucai Xiao committed
17
#include <migraphx/make_op.hpp>
18
#include <migraphx/marker.hpp>
Paul's avatar
Paul committed
19
#include <iostream>
20
#include <numeric>
Paul's avatar
Paul committed
21
#include <sstream>
Paul's avatar
Paul committed
22
#include <algorithm>
23
#include <set>
Paul's avatar
Paul committed
24
#include <utility>
25
#include <iomanip>
26

27
#include <unordered_set>
Shucai Xiao's avatar
Shucai Xiao committed
28
29
#include <map>
#include <cassert>
Paul's avatar
Paul committed
30

Paul's avatar
Paul committed
31
namespace migraphx {
Paul's avatar
Paul committed
32
inline namespace MIGRAPHX_INLINE_NS {
Paul's avatar
Paul committed
33

34
35
using milliseconds = std::chrono::duration<double, std::milli>;

Paul's avatar
Paul committed
36
37
struct program_impl
{
Shucai Xiao's avatar
Shucai Xiao committed
38
    // A map is used to keep references to modules of the program
39
    std::unordered_map<std::string, module> modules;
Paul's avatar
Paul committed
40
    context ctx;
41
    std::string target_name;
Paul's avatar
Paul committed
42
43
};

44
program::program() : impl(std::make_unique<program_impl>()) { this->create_module("main"); }
Paul's avatar
Paul committed
45

Paul's avatar
Paul committed
46
program::program(program&&) noexcept = default;
Shucai Xiao's avatar
Shucai Xiao committed
47
program::~program() noexcept         = default;
Paul's avatar
Paul committed
48

49
// copy constructor
Shucai Xiao's avatar
Shucai Xiao committed
50
program::program(const program& p) { assign(p); }
51
52

// copy assignment operator
Shucai Xiao's avatar
Shucai Xiao committed
53
program& program::operator=(program p)
54
{
Shucai Xiao's avatar
Shucai Xiao committed
55
    std::swap(p.impl, this->impl);
56
57
58
    return *this;
}

Shucai Xiao's avatar
Shucai Xiao committed
59
void program::assign(const program& p)
60
{
Shucai Xiao's avatar
Shucai Xiao committed
61
    if(!impl)
62
63
64
    {
        impl = std::make_unique<program_impl>();
    }
Shucai Xiao's avatar
Shucai Xiao committed
65
    else if(!impl->modules.empty())
66
    {
Shucai Xiao's avatar
Shucai Xiao committed
67
        impl->modules.clear();
68
    }
Shucai Xiao's avatar
Shucai Xiao committed
69

70
    impl->ctx         = p.impl->ctx;
Shucai Xiao's avatar
Shucai Xiao committed
71
72
    impl->target_name = p.impl->target_name;
    impl->modules     = p.impl->modules;
Shucai Xiao's avatar
Shucai Xiao committed
73
74
75
76

    // build a map from old ins to new ins
    // Build a map from old module to new module
    std::unordered_map<module_ref, module_ref> mod_map;
Paul's avatar
Paul committed
77
78
79
80
81
    std::transform(
        impl->modules.begin(),
        impl->modules.end(),
        std::inserter(mod_map, mod_map.begin()),
        [&](auto&& xp) { return std::make_pair(&p.impl->modules.at(xp.first), &xp.second); });
Shucai Xiao's avatar
Shucai Xiao committed
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97

    std::unordered_map<instruction_ref, instruction_ref> ins_map;
    for(auto&& pp : mod_map)
    {
        auto old_ins = iterator_for(*pp.first);
        auto new_ins = iterator_for(*pp.second);
        std::transform(old_ins.begin(),
                       old_ins.end(),
                       new_ins.begin(),
                       std::inserter(ins_map, ins_map.begin()),
                       [](auto x, auto y) { return std::make_pair(x, y); });
    }

    // Update all references from all modules
    for(auto&& mp : impl->modules)
    {
98
        for(auto ins : iterator_for(mp.second))
Shucai Xiao's avatar
Shucai Xiao committed
99
100
            instruction::replace_refs(ins, ins_map, mod_map);
    }
101
102
}

Paul's avatar
Paul committed
103
shape program::get_parameter_shape(std::string name) const
Paul's avatar
Paul committed
104
{
Shucai Xiao's avatar
Shucai Xiao committed
105
106
    const auto* mm = this->get_main_module();
    return mm->get_parameter_shape(std::move(name));
Paul's avatar
Paul committed
107
108
}

109
110
std::vector<std::string> program::get_parameter_names() const
{
Shucai Xiao's avatar
Shucai Xiao committed
111
112
    const auto* mm = this->get_main_module();
    return mm->get_parameter_names();
113
114
}

mei-ye's avatar
mei-ye committed
115
116
instruction_ref program::get_parameter(std::string name) const
{
Shucai Xiao's avatar
Shucai Xiao committed
117
118
    const auto* mm = this->get_main_module();
    return mm->get_parameter(std::move(name));
mei-ye's avatar
mei-ye committed
119
120
}

Paul's avatar
Paul committed
121
122
std::unordered_map<std::string, shape> program::get_parameter_shapes() const
{
Shucai Xiao's avatar
Shucai Xiao committed
123
124
    const auto* mm = this->get_main_module();
    return mm->get_parameter_shapes();
Paul's avatar
Paul committed
125
126
}

Shucai Xiao's avatar
Shucai Xiao committed
127
std::size_t program::size() const { return impl->modules.size(); }
128

129
130
std::vector<shape> program::get_output_shapes() const
{
Shucai Xiao's avatar
Shucai Xiao committed
131
132
    const auto* mm = this->get_main_module();
    return mm->get_output_shapes();
133
}
Paul's avatar
Paul committed
134

Paul's avatar
Paul committed
135
136
context& program::get_context() const { return impl->ctx; }

Paul's avatar
Paul committed
137
138
instruction_ref program::validate() const
{
Shucai Xiao's avatar
Shucai Xiao committed
139
140
    const auto* mm = this->get_main_module();
    return mm->validate();
Paul's avatar
Paul committed
141
142
}

143
144
bool program::is_compiled() const { return not this->impl->target_name.empty(); }

145
void program::compile(const target& t, compile_options options)
Paul's avatar
Paul committed
146
{
147
148
149
    assert(not this->is_compiled());
    this->impl->target_name = t.name();
    this->impl->ctx         = t.get_context();
Paul's avatar
Paul committed
150
    if(enabled(MIGRAPHX_TRACE_COMPILE{}))
151
        options.trace = tracer{std::cout};
Shucai Xiao's avatar
Shucai Xiao committed
152

153
154
    options.trace(*this);
    options.trace();
Shucai Xiao's avatar
Shucai Xiao committed
155

Shucai Xiao's avatar
Shucai Xiao committed
156
    auto&& passes = t.get_passes(this->impl->ctx, options);
157
158
159
    run_passes(*this, passes, options.trace);

    auto mods = this->get_modules();
Shucai Xiao's avatar
Shucai Xiao committed
160

161
162
    // Validate and finalize
    for(const auto& mod : reverse(mods))
Paul's avatar
Paul committed
163
    {
Shucai Xiao's avatar
Shucai Xiao committed
164
165
166
167
168
169
        auto invalid = mod->validate();
        if(invalid != mod->end())
        {
            MIGRAPHX_THROW("Invalid module " + mod->name() + " from compilation at instruction " +
                           std::to_string(std::distance(mod->begin(), invalid)));
        }
170
171
172
173
174
        auto dangling = mod->find_dangling_reference();
        if(dangling != mod->end())
        {
            auto index = std::distance(mod->begin(), dangling);
            MIGRAPHX_THROW("Dangling reference in module " + mod->name() + " from instruction " +
175
                           std::to_string(index) + ", (" + dangling->name() + ")");
176
        }
Shucai Xiao's avatar
Shucai Xiao committed
177
        mod->finalize(this->impl->ctx);
Paul's avatar
Paul committed
178
    }
Paul's avatar
Paul committed
179
180
181
182
}

void program::finalize()
{
Shucai Xiao's avatar
Shucai Xiao committed
183
184
    auto* mm = this->get_main_module();
    mm->finalize(this->impl->ctx);
Paul's avatar
Paul committed
185
186
}

187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
template <class T>
std::string classify(T x)
{
    switch(std::fpclassify(x))
    {
    case FP_INFINITE: return "inf";
    case FP_NAN: return "nan";
    case FP_NORMAL: return "normal";
    case FP_SUBNORMAL: return "subnormal";
    case FP_ZERO: return "zero";
    default: return "unknown";
    }
}

std::unordered_set<std::string> classify_argument(const argument& a)
{
    std::unordered_set<std::string> result;
    a.visit(
        [&](auto t) {
            for(const auto& x : t)
                result.insert(classify(x));
        },
        [&](const auto& xs) {
            for(const auto& x : xs)
            {
                auto r = classify_argument(x);
                result.insert(r.begin(), r.end());
            }
        });
    return result;
}

void preview_argument(std::ostream& os, const argument& a)
{
    a.visit(
        [&](auto t) {
            if(t.size() <= 10)
            {
                os << t;
            }
            else
            {
                os << to_string_range(t.begin(), t.begin() + 5);
                os << ", ..., ";
                os << to_string_range(t.end() - 5, t.end());
            }
        },
        [&](const auto& xs) {
            for(const auto& x : xs)
            {
                os << '{';
                preview_argument(os, x);
                os << '}';
            }
        });
}

Paul's avatar
Paul committed
244
template <class F>
Shucai Xiao's avatar
Shucai Xiao committed
245
std::vector<argument> generic_eval(const module* mod,
246
247
                                   context& ctx,
                                   std::unordered_map<std::string, argument> params,
Shucai Xiao's avatar
Shucai Xiao committed
248
                                   std::unordered_map<instruction_ref, argument> results,
249
                                   F make_trace)
Paul's avatar
Paul committed
250
{
Shucai Xiao's avatar
Shucai Xiao committed
251
252
    assert(mod->validate() == mod->end());
    results.reserve(mod->size() * 2);
Paul's avatar
Paul committed
253
254
    std::vector<argument> values;
    values.reserve(16);
255
    auto trace = make_trace(mod);
Shucai Xiao's avatar
Shucai Xiao committed
256
    for(auto ins : iterator_for(*mod))
Paul's avatar
Paul committed
257
    {
258
        assert(results.find(ins) == results.end());
259
260
        const auto& name = ins->name();
        if(name == "@literal")
Paul's avatar
Paul committed
261
        {
Paul's avatar
Paul committed
262
            results.emplace(ins, trace(ins, [&] { return ins->get_literal().get_argument(); }));
Paul's avatar
Paul committed
263
        }
264
        else if(name == "@param")
Paul's avatar
Paul committed
265
        {
Paul's avatar
Paul committed
266
267
268
269
270
            results.emplace(
                ins, trace(ins, [&] {
                    auto param_name = any_cast<builtin::param>(ins->get_operator()).parameter;
                    if(not contains(params, param_name))
                        MIGRAPHX_THROW("Parameter not found: " + param_name);
271
                    auto param = params[param_name];
Paul's avatar
Paul committed
272
273
274
275
276
                    if(param.get_shape() != ins->get_shape())
                        MIGRAPHX_THROW("Incorrect shape {" + to_string(param.get_shape()) +
                                       "} for parameter: " + param_name);
                    return param;
                }));
Paul's avatar
Paul committed
277
        }
278
        else if(name == "@outline")
Paul's avatar
Paul committed
279
        {
Paul's avatar
Paul committed
280
            results.emplace(ins, trace(ins, [&] { return argument{ins->get_shape(), nullptr}; }));
Paul's avatar
Paul committed
281
        }
282
283
284
285
286
287
288
289
290
291
292
293
294
        else if(name == "@return")
        {
            std::vector<argument> prog_outputs;
            std::transform(ins->inputs().begin(),
                           ins->inputs().end(),
                           std::back_inserter(prog_outputs),
                           [&](instruction_ref i) {
                               assert(results.find(i) != results.end());
                               return results[i];
                           });

            return prog_outputs;
        }
Paul's avatar
Paul committed
295
296
        else
        {
Paul's avatar
Paul committed
297
            values.resize(ins->inputs().size());
Paul's avatar
Paul committed
298
299
300
301
302
            std::transform(
                ins->inputs().begin(), ins->inputs().end(), values.begin(), [&](instruction_ref i) {
                    assert(results.find(i) != results.end());
                    return results[i];
                });
Shucai Xiao's avatar
Shucai Xiao committed
303
304
305
306

            const auto& mod_args = ins->module_inputs();
            auto module_eval     = [&](module_ref smod,
                                   const std::unordered_map<std::string, argument>& inputs) {
Shucai Xiao's avatar
Shucai Xiao committed
307
308
                auto ssctx = ctx;
                return generic_eval(smod, ssctx, inputs, results, make_trace);
Shucai Xiao's avatar
Shucai Xiao committed
309
310
            };

Shucai Xiao's avatar
Shucai Xiao committed
311
312
313
314
            results.emplace(ins, trace(ins, [&] {
                                return ins->normalized_operator().compute(
                                    ctx, ins->get_shape(), values, mod_args, module_eval);
                            }));
Paul's avatar
Paul committed
315
        }
316
        assert(results.find(ins) != results.end());
317
        assert(results.at(ins).get_shape() == ins->get_shape());
Paul's avatar
Paul committed
318
    }
Shucai Xiao's avatar
Shucai Xiao committed
319
    return {results.at(std::prev(mod->end()))};
Paul's avatar
Paul committed
320
321
}

Shucai Xiao's avatar
Shucai Xiao committed
322
323
324
325
template <class F>
std::vector<argument> generic_eval(const program& p,
                                   context& ctx,
                                   std::unordered_map<std::string, argument> params,
326
                                   F make_trace)
Shucai Xiao's avatar
Shucai Xiao committed
327
{
Shucai Xiao's avatar
Shucai Xiao committed
328
    const module* mm = p.get_main_module();
329
    return generic_eval(mm, ctx, params, {}, make_trace);
Shucai Xiao's avatar
Shucai Xiao committed
330
331
}

Shucai Xiao's avatar
Shucai Xiao committed
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
static void print_space(std::ostream& os, int n)
{
    for(int i = 0; i < n; ++i)
    {
        os << ' ';
    }
}

using op_flops = std::function<double(const std::vector<shape>& vec_ss)>;
auto& get_flops_funcs()
{
    static std::unordered_map<std::string, op_flops> op_funcs;
    op_funcs.emplace("gemm", [&](const std::vector<shape>& vec_ss) {
        assert(vec_ss.size() >= 2);
        auto sa     = vec_ss.front();
        auto sb     = vec_ss.at(1);
        auto batch  = 1;
        auto lens_a = sa.lens();
        batch =
            std::accumulate(lens_a.rbegin() + 2, lens_a.rend(), 1, std::multiplies<std::size_t>{});
        auto m      = lens_a[lens_a.size() - 2];
        auto k      = lens_a.back();
        auto lens_b = sb.lens();
        assert(k == lens_b[lens_b.size() - 2]);
        auto n = lens_b.back();

        return 2.0 * m * n * k * batch;
    });

    op_funcs.emplace("convolution", [&](const std::vector<shape>& vec_ss) {
        assert(vec_ss.size() >= 2);
        auto alens = vec_ss.front().lens();
        auto blens = vec_ss.at(1).lens();
        auto olens = vec_ss.back().lens();

        auto n  = alens.front();
        auto k  = blens.front();
        auto c  = alens.at(1);
        auto y  = blens.at(2);
        auto x  = blens.back();
        auto ho = olens.at(2);
        auto wo = olens.back();

        return 2.0 * n * k * ho * wo * c * y * x;
    });

    return op_funcs;
}

int program::max_ins_length() const
{
    std::unordered_map<instruction_ref, std::string> names;
    int max_ins_len = 0;

    this->print(names, [&](auto ins, auto ins_names) {
        std::stringstream ss;
        instruction::print(ss, ins, ins_names);
        if(max_ins_len < ss.str().length())
        {
            max_ins_len = ss.str().length();
        }

        // skip return instruction
        if(ins->name() == "@return")
            return;
    });

    return max_ins_len;
}

static auto& get_titles()
{
    static std::vector<std::string> titles = {"Instructions",
405
406
407
408
                                              "Time(ms)     ",
                                              "Percentage   ",
                                              "(b, m, n, k)                    ",
                                              "Flops(TFlops/s)  ",
Shucai Xiao's avatar
Shucai Xiao committed
409
410
411
412
413
                                              "Throughput(GB/s)"};

    return titles;
}

414
static void print_title(std::ostream& os, std::size_t max_ins_len, bool print_percentage = true)
Shucai Xiao's avatar
Shucai Xiao committed
415
416
417
418
419
{
    auto titles      = get_titles();
    std::string& str = titles.front();
    str.append(max_ins_len + 1 - str.length(), ' ');
    str.append(1, '\t');
420
421
422
423
    os << str;
    if (not print_percentage) titles.erase(titles.begin() + 2);
    int i = 1;
    for (; i < titles.size(); ++i)
Shucai Xiao's avatar
Shucai Xiao committed
424
    {
425
        os << titles[i];
Shucai Xiao's avatar
Shucai Xiao committed
426
427
428
429
430
431
432
433
    }
    os << std::endl;
}

static void print_ins_perf(std::ostream& os,
                           const std::vector<std::string>& titles,
                           instruction_ref ins,
                           double t,
434
435
                           double total_t,
                           bool print_percentage = true)
Shucai Xiao's avatar
Shucai Xiao committed
436
437
438
439
440
441
442
443
444
445
{
    auto& time_str  = titles.at(1);
    auto& time_per  = titles.at(2);
    auto& size_str  = titles.at(3);
    auto& flops_str = titles.at(4);
    auto& thrpt_str = titles.at(5);

    auto& flops_funcs = get_flops_funcs();
    std::string tms   = std::to_string(t);
    tms.append(time_str.length() - tms.length(), ' ');
446
447
448

    std::string pers;
    if (print_percentage)
Shucai Xiao's avatar
Shucai Xiao committed
449
    {
450
451
452
453
454
455
456
457
        double percent   = 100.0 * t / total_t;
        pers = std::to_string(percent);
        auto loc         = pers.find('.');
        if(loc != std::string::npos)
        {
            pers.erase(pers.begin() + loc + 6, pers.end());
        }
        pers.append(time_per.length() - pers.length(), ' ');
Shucai Xiao's avatar
Shucai Xiao committed
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
    }

    // calculate flops
    std::string szs;
    std::string flps;
    std::string op_name = ins->name();
    auto nloc           = op_name.find("::");
    op_name.erase(op_name.begin(), op_name.begin() + nloc + 2);
    auto inss = to_shapes(ins->inputs());
    if(contains(flops_funcs, op_name))
    {
        // print size
        auto alens = inss.front().lens();
        auto blens = inss.at(1).lens();
        auto mb =
            std::accumulate(alens.rbegin() + 2, alens.rend(), 1, std::multiplies<std::size_t>{});
        int mm = alens[alens.size() - 2];
        int mk = alens.back();
        int mn = blens.back();

        szs = "{";
        szs.append(std::to_string(mb));
        szs.append(1, ',');
        szs.append(std::to_string(mm));
        szs.append(1, ',');
        szs.append(std::to_string(mk));
        szs.append(1, ',');
        szs.append(std::to_string(mn));
        szs.append("}");
        szs.append(size_str.length() - szs.length(), ' ');

        auto op_flop_func = flops_funcs.at(op_name);
        double flops      = op_flop_func(inss);
        flops /= t;
        // convert to GFlops
        flops /= 1.0e9;
        flps      = std::to_string(flops);
        auto floc = flps.find('.');
        if(floc != std::string::npos)
        {
            flps.erase(flps.begin() + floc + 4, flps.end());
        }
    }
    szs.append(size_str.length() - szs.length(), ' ');
    flps.append(flops_str.length() - flps.length(), ' ');

    // print throughput for pointwise instruction
    auto alias_num = ins->get_operator().output_alias({});
    std::string thrpt;
    if(alias_num != 0)
    {
        auto size =
            std::accumulate(inss.begin(), inss.end(), std::size_t{0}, [&](auto init, auto s) {
                return init + s.bytes();
            });

        double throughput = size / t;
        // convert to GB/s
        throughput /= 1.0e6;
        thrpt     = std::to_string(throughput);
        auto floc = flps.find('.');
        if(floc != std::string::npos)
        {
            thrpt.erase(thrpt.begin() + floc + 4, thrpt.end());
        }
    }
    thrpt.append(thrpt_str.length() - thrpt.length(), ' ');

    os << tms << pers << szs << flps << thrpt << std::endl;
}

529
std::vector<argument> program::eval(parameter_map params) const
Paul's avatar
Paul committed
530
{
Paul's avatar
Paul committed
531
532
    auto& ctx = this->impl->ctx;
#ifndef NDEBUG
533
534
535
536
537
538
539
540
541
542
543
    auto with_check_context = [&](auto f) {
        return [=, &ctx](auto&&) {
            auto sctx          = std::make_shared<context>(ctx);
            auto check_context = [=, &ctx](auto g) {
                assert(is_shared(ctx, *sctx));
                auto x = g();
                *sctx  = ctx;
                return x;
            };
            return [=](auto&&... xs) { return f(xs..., check_context); };
        };
Paul's avatar
Paul committed
544
545
    };
#else
546
547
548
549
550
    auto with_check_context = [](auto f) {
        return [=](auto&&) {
            return [=](auto&&... xs) { return f(xs..., [](auto g) { return g(); }); };
        };
    };
Paul's avatar
Paul committed
551
#endif
Paul's avatar
Paul committed
552
553
554
555

    auto trace_level = value_of(MIGRAPHX_TRACE_EVAL{});

    if(trace_level > 0)
Paul's avatar
Paul committed
556
    {
557
        auto max_ins_len = max_ins_length();
Shucai Xiao's avatar
Shucai Xiao committed
558
        std::unordered_map<instruction_ref, std::string> ins_names;
Shucai Xiao's avatar
Shucai Xiao committed
559
        this->print(ins_names, [&](auto, auto) {});
560
561
562
563
564
565
566
        if (trace_level == 3)
        {
            std::string prefix = "Run instruction: ";
            max_ins_len += prefix.length();
            print_title(std::cout, max_ins_len, false);
        }

567
568
569
570
571
        return generic_eval(*this,
                            ctx,
                            std::move(params),
                            with_check_context([&](auto& ins, auto f, auto&& check_context) {
                                ctx.finish();
572
573
574
575
                                std::stringstream ss;
                                ss << "Run instruction: ";
                                this->debug_print(ss, ins, ins_names);

576
577
578
579
580
                                timer t{};
                                auto result = check_context(f);
                                double t1   = t.record<milliseconds>();
                                ctx.finish();
                                double t2 = t.record<milliseconds>();
581
                                if (trace_level < 3)
Shucai Xiao's avatar
Shucai Xiao committed
582
                                {
583
584
585
586
587
                                    std::cout << ss.str() << std::endl;
                                    std::cout << "Time: " << t1 << "ms, " << t2
                                            << "ms, execution time:\t";
                                    if(trace_level == 2 and ins->name().front() != '@' and
                                    ins->name() != "load" and not result.empty())
588
                                    {
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
                                        target tgt  = make_target(this->impl->target_name);
                                        auto buffer = tgt.copy_from(result);
                                        if(trace_level == 2)
                                        {
                                            std::cout << "Output has "
                                                    << to_string_range(classify_argument(buffer))
                                                    << std::endl;
                                            std::cout << "Output: ";
                                            preview_argument(std::cout, buffer);
                                            std::cout << std::endl;
                                        }
                                        else
                                        {
                                            std::cout << "Output: " << buffer << std::endl;
                                        }
604
                                    }
Shucai Xiao's avatar
Shucai Xiao committed
605
                                }
Shucai Xiao's avatar
Shucai Xiao committed
606
                                else if(trace_level == 3)
Shucai Xiao's avatar
Shucai Xiao committed
607
608
                                {
                                    // count max instruction length
609
610
611
612
613
614
615
616
617
                                    if (ins->get_operator().output_alias({}) == 0)
                                    {
                                        std::cout << ss.str() << std::endl;
                                        return result;
                                    }
                                    
                                    print_space(ss, max_ins_len - ss.str().length());
                                    ss << '\t';
                                    std::cout << ss.str();
Shucai Xiao's avatar
Shucai Xiao committed
618
                                    auto titles   = get_titles();
Shucai Xiao's avatar
Shucai Xiao committed
619
                                    double exec_t = t2 - t1;
620
                                    print_ins_perf(std::cout, titles, ins, exec_t, exec_t, false);
Shucai Xiao's avatar
Shucai Xiao committed
621
                                }
622
623
                                return result;
                            }));
Paul's avatar
Paul committed
624
625
626
    }
    else
    {
627
628
629
630
631
632
        return generic_eval(*this,
                            ctx,
                            std::move(params),
                            with_check_context([&](auto&, auto f, auto&& check_context) {
                                return check_context(f);
                            }));
Paul's avatar
Paul committed
633
    }
Paul's avatar
Paul committed
634
635
}

636
const int program_file_version = 5;
637
638
639
640
641
642
643
644

value program::to_value() const
{
    value result;
    result["version"] = program_file_version;
    result["target"]  = this->impl->target_name;
    if(not this->impl->target_name.empty())
        result["context"] = this->impl->ctx.to_value();
Shucai Xiao's avatar
Shucai Xiao committed
645

646
    value module_vals = value::object{};
Shucai Xiao's avatar
Shucai Xiao committed
647
    std::unordered_map<instruction_ref, std::string> names;
648
    for(auto& mod : this->get_modules())
Shucai Xiao's avatar
Shucai Xiao committed
649
    {
Shucai Xiao's avatar
Shucai Xiao committed
650
651
        value mod_val;
        value nodes;
652
653
        mod_val["name"] = mod->name();
        names           = mod->print(
Shucai Xiao's avatar
Shucai Xiao committed
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
            [&](auto ins, auto ins_names) {
                value node;
                node["output"]     = ins_names.at(ins);
                node["name"]       = ins->name();
                node["shape"]      = migraphx::to_value(ins->get_shape());
                node["normalized"] = ins->is_normalized();
                if(ins->name() == "@literal")
                    node["literal"] = migraphx::to_value(ins->get_literal());
                node["operator"] = ins->get_operator().to_value();
                std::vector<std::string> inputs;
                std::transform(ins->inputs().begin(),
                               ins->inputs().end(),
                               std::back_inserter(inputs),
                               [&](auto i) {
                                   assert(contains(ins_names, i));
                                   return ins_names.at(i);
                               });
                node["inputs"]   = inputs;
                auto module_args = ins->module_inputs();
                if(not module_args.empty())
                {
                    std::vector<std::string> module_inputs;
                    std::transform(module_args.begin(),
                                   module_args.end(),
                                   std::back_inserter(module_inputs),
                                   [&](auto mod_ref) { return mod_ref->name(); });
                    node["module_inputs"] = module_inputs;
                }

                nodes.push_back(node);
            },
            names);
        mod_val["nodes"] = nodes;

688
        module_vals[mod->name()] = mod_val;
Shucai Xiao's avatar
Shucai Xiao committed
689
    }
Shucai Xiao's avatar
Shucai Xiao committed
690
691
692

    result["modules"] = module_vals;

693
694
    return result;
}
Shucai Xiao's avatar
Shucai Xiao committed
695

Shucai Xiao's avatar
Shucai Xiao committed
696
697
698
699
700
static void mod_from_val(module_ref mod,
                         const value& v,
                         std::unordered_map<std::string, instruction_ref>& instructions,
                         const std::unordered_map<std::string, module_ref>& map_mods)
{
701
    const auto& module_val = v.at(mod->name());
Shucai Xiao's avatar
Shucai Xiao committed
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
    for(const value& node : module_val.at("nodes"))
    {
        instruction_ref output;
        auto name       = node.at("name").to<std::string>();
        auto fields     = node.at("operator");
        auto normalized = node.at("normalized").to<bool>();

        if(name == "@param")
        {
            output = mod->add_parameter(fields["parameter"].to<std::string>(),
                                        migraphx::from_value<shape>(node.at("shape")));
        }
        else if(name == "@literal")
        {
            output = mod->add_literal(migraphx::from_value<literal>(node.at("literal")));
        }
        else
        {
            auto op = make_op(name, fields);
            std::vector<instruction_ref> inputs;
            std::transform(node.at("inputs").begin(),
                           node.at("inputs").end(),
                           std::back_inserter(inputs),
                           [&](const value& i) {
                               auto i_name = i.to<std::string>();
                               assert(contains(instructions, i_name));
                               return instructions.at(i_name);
                           });

            std::vector<module_ref> module_inputs;
            if(node.contains("module_inputs"))
            {
                std::transform(node.at("module_inputs").begin(),
                               node.at("module_inputs").end(),
                               std::back_inserter(module_inputs),
                               [&](const value& i) { return map_mods.at(i.to<std::string>()); });

                for(auto& smod : module_inputs)
                {
                    mod_from_val(smod, v, instructions, map_mods);
                }
            }

            if(name == "@return")
            {
                output = mod->add_return(inputs);
            }
            else if(module_inputs.empty())
            {
                output = mod->add_instruction(op, inputs);
            }
            else
            {
                output = mod->add_instruction(op, inputs, module_inputs);
            }
        }
        output->set_normalized(normalized);
        instructions[node.at("output").to<std::string>()] = output;
    }
}

763
764
765
766
void program::from_value(const value& v)
{
    auto version = v.at("version").to<int>();
    if(version != program_file_version)
Shucai Xiao's avatar
Shucai Xiao committed
767
768
769
770
    {
        MIGRAPHX_THROW("Warning: Program version mismatch");
    }

771
772
773
774
775
776
777
778
    this->impl->target_name = v.at("target").to<std::string>();
    if(not this->impl->target_name.empty())
    {
        target t        = make_target(this->impl->target_name);
        this->impl->ctx = t.get_context();
        this->impl->ctx.from_value(v.at("context"));
    }

Shucai Xiao's avatar
Shucai Xiao committed
779
780
    auto module_vals = v.at("modules");
    for(const auto& vv : module_vals)
781
    {
782
        const auto& name = vv.get_key();
Shucai Xiao's avatar
Shucai Xiao committed
783
784
        if(name == "main")
            continue;
785
        impl->modules.emplace(name, name);
786
    }
787
    std::unordered_map<std::string, module_ref> map_mods;
Paul's avatar
Paul committed
788
789
790
791
    std::transform(impl->modules.begin(),
                   impl->modules.end(),
                   std::inserter(map_mods, map_mods.end()),
                   [&](auto&& pp) { return std::make_pair(pp.first, &pp.second); });
Shucai Xiao's avatar
Shucai Xiao committed
792
793
794
795
796

    std::unordered_map<std::string, instruction_ref> map_insts;
    auto* mm = get_main_module();
    mod_from_val(mm, module_vals, map_insts, map_mods);

797
798
799
    this->finalize();
}

Paul's avatar
Paul committed
800
801
802
double common_average(const std::vector<double>& v)
{
    std::size_t n = v.size() / 4;
Paul's avatar
Paul committed
803
804
    double total  = std::accumulate(v.begin() + n, v.end() - n, 0.0);
    return total / std::distance(v.begin() + n, v.end() - n);
Paul's avatar
Paul committed
805
806
}

Paul Fultz II's avatar
Paul Fultz II committed
807
808
809
810
811
812
813
814
std::string perf_group(const operation& op)
{
    auto attr = op.attributes();
    if(attr.contains("group"))
        return attr.at("group").to<std::string>();
    return op.name();
}

815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
void program::mark(const parameter_map& params, marker&& m)
{
    auto& ctx = this->impl->ctx;
    // Run once by itself
    eval(params);
    ctx.finish();
    // Start marking
    m.mark_start(*this);
    generic_eval(*this, ctx, params, always([&](auto ins, auto f) {
        argument result;
        m.mark_start(ins);
        result = f();
        m.mark_stop(ins);
        return result;
    }));
    m.mark_stop(*this);
}

833
834
835
836
void program::perf_report(std::ostream& os,
                          std::size_t n,
                          parameter_map params,
                          std::size_t batch) const
Paul's avatar
Paul committed
837
{
838
    auto& ctx = this->impl->ctx;
Paul's avatar
Paul committed
839
840
    // Run once by itself
    eval(params);
Paul's avatar
Paul committed
841
    ctx.finish();
Paul's avatar
Paul committed
842
    // Run and time entire program
Paul's avatar
Paul committed
843
844
    std::vector<double> total_vec;
    total_vec.reserve(n);
Paul's avatar
Paul committed
845
    for(std::size_t i = 0; i < n; i++)
Paul's avatar
Paul committed
846
    {
Paul's avatar
Paul committed
847
848
849
850
        total_vec.push_back(time<milliseconds>([&] {
            eval(params);
            ctx.finish();
        }));
Paul's avatar
Paul committed
851
    }
Paul's avatar
Paul committed
852
853
    std::sort(total_vec.begin(), total_vec.end());
    std::unordered_map<instruction_ref, std::vector<double>> ins_vec;
Paul's avatar
Paul committed
854
    // Fill the map
855
    generic_eval(*this, ctx, params, always([&](auto ins, auto) {
Paul's avatar
Paul committed
856
        ins_vec[ins].reserve(n);
857
        return argument{ins->get_shape(), nullptr};
858
    }));
859

Paul's avatar
Paul committed
860
    // Run and time each instruction
Paul's avatar
Paul committed
861
    for(std::size_t i = 0; i < n; i++)
Paul's avatar
Paul committed
862
    {
863
        generic_eval(*this, ctx, params, always([&](auto ins, auto f) {
864
            argument result;
Paul's avatar
Paul committed
865
866
867
868
            ins_vec[ins].push_back(time<milliseconds>([&] {
                result = f();
                ctx.finish();
            }));
869
            return result;
870
        }));
Paul's avatar
Paul committed
871
    }
Paul's avatar
Paul committed
872
873
    for(auto&& p : ins_vec)
        std::sort(p.second.begin(), p.second.end());
Paul's avatar
Paul committed
874
    // Run and time implicit overhead
Paul's avatar
Paul committed
875
876
    std::vector<double> overhead_vec;
    overhead_vec.reserve(n);
Paul's avatar
Paul committed
877
    for(std::size_t i = 0; i < n; i++)
Paul's avatar
Paul committed
878
    {
Paul's avatar
Paul committed
879
        overhead_vec.push_back(time<milliseconds>([&] { dry_run(params); }));
Paul's avatar
Paul committed
880
881
    }

Paul's avatar
Paul committed
882
    double total_time             = common_average(total_vec);
Paul's avatar
Paul committed
883
    double rate                   = 1000.0 / total_time;
Paul's avatar
Paul committed
884
    double overhead_time          = common_average(overhead_vec);
Paul's avatar
Paul committed
885
    double overhead_percent       = overhead_time * 100.0 / total_time;
Paul's avatar
Paul committed
886
    double total_instruction_time = 0.0;
Paul's avatar
Paul committed
887
    std::unordered_map<std::string, double> op_times;
Paul's avatar
Paul committed
888
    for(auto&& p : ins_vec)
Paul's avatar
Paul committed
889
890
    {
        double avg = common_average(p.second);
Paul Fultz II's avatar
Paul Fultz II committed
891
        op_times[perf_group(p.first->get_operator())] += avg;
Paul's avatar
Paul committed
892
893
        total_instruction_time += avg;
    }
Paul's avatar
Paul committed
894
895
    double calculate_overhead_time    = total_time - total_instruction_time;
    double calculate_overhead_percent = calculate_overhead_time * 100.0 / total_time;
Paul's avatar
Paul committed
896

Shucai Xiao's avatar
Shucai Xiao committed
897
    std::unordered_map<instruction_ref, std::string> names;
898
899

    // count max instruction length
Shucai Xiao's avatar
Shucai Xiao committed
900
    auto titles           = get_titles();
901
902
    const int max_ins_len = max_ins_length();
    print_title(os, max_ins_len);
903

Shucai Xiao's avatar
Shucai Xiao committed
904
    this->print(names, [&](auto ins, auto ins_names) {
905
906
907
        std::stringstream ss;
        instruction::print(ss, ins, ins_names);
        os << ss.str();
908
909
910
911
912

        // skip return instruction
        if(ins->name() == "@return")
            return;

913
914
        // insert space to align
        print_space(os, max_ins_len - ss.str().length());
Shucai Xiao's avatar
Shucai Xiao committed
915
        os << "\t";
Shucai Xiao's avatar
Shucai Xiao committed
916
        double avg = common_average(ins_vec[ins]);
917
        print_ins_perf(os, titles, ins, avg, total_instruction_time);
Paul's avatar
Paul committed
918
    });
Paul's avatar
Paul committed
919
920
921

    os << std::endl;
    os << "Summary:" << std::endl;
922
923
924
925
926
927
928
    std::vector<std::pair<double, std::string>> op_times_sorted;
    std::transform(op_times.begin(),
                   op_times.end(),
                   std::back_inserter(op_times_sorted),
                   [](auto p) { return std::make_pair(p.second, p.first); });
    std::sort(op_times_sorted.begin(), op_times_sorted.end(), std::greater<>{});
    for(auto&& p : op_times_sorted)
Paul's avatar
Paul committed
929
    {
930
931
        auto&& name    = p.second;
        double avg     = p.first;
Paul's avatar
Paul committed
932
933
934
935
936
        double percent = std::ceil(100.0 * avg / total_instruction_time);
        os << name << ": " << avg << "ms, " << percent << "%" << std::endl;
    }

    os << std::endl;
Paul's avatar
Paul committed
937

938
939
    os << "Batch size: " << batch << std::endl;
    os << "Rate: " << rate * batch << "/sec" << std::endl;
Paul's avatar
Paul committed
940
941
    os << "Total time: " << total_time << "ms" << std::endl;
    os << "Total instructions time: " << total_instruction_time << "ms" << std::endl;
Paul's avatar
Paul committed
942
943
944
945
    os << "Overhead time: " << overhead_time << "ms"
       << ", " << calculate_overhead_time << "ms" << std::endl;
    os << "Overhead: " << std::round(overhead_percent) << "%"
       << ", " << std::round(calculate_overhead_percent) << "%" << std::endl;
Paul's avatar
Paul committed
946
947
}

Paul's avatar
Paul committed
948
949
void program::debug_print() const { std::cout << *this << std::endl; }
void program::debug_print(instruction_ref ins) const
Paul's avatar
Paul committed
950
{
Shucai Xiao's avatar
Shucai Xiao committed
951
    std::unordered_map<instruction_ref, std::string> names;
952
    if(std::any_of(this->impl->modules.begin(), this->impl->modules.end(), [&](const auto& pp) {
953
           return is_end(pp.second.end(), ins);
Shucai Xiao's avatar
Shucai Xiao committed
954
       }))
Paul's avatar
Paul committed
955
956
957
958
    {
        std::cout << "End instruction" << std::endl;
        return;
    }
959
960
    else if(std::none_of(this->impl->modules.begin(),
                         this->impl->modules.end(),
961
                         [&](const auto& pp) { return pp.second.has_instruction(ins); }))
Paul's avatar
Paul committed
962
963
964
965
    {
        std::cout << "Instruction not part of program" << std::endl;
        return;
    }
Shucai Xiao's avatar
Shucai Xiao committed
966

Paul's avatar
Paul committed
967
    std::stringstream ss;
Shucai Xiao's avatar
Shucai Xiao committed
968
    this->print(names, [&](auto x, auto ins_names) {
Paul's avatar
Paul committed
969
        if(x == ins)
Paul's avatar
Paul committed
970
        {
Shucai Xiao's avatar
Shucai Xiao committed
971
            instruction::print(std::cout, x, ins_names);
Paul's avatar
Paul committed
972
973
974
975
976
            std::cout << std::endl;
        }
    });
}

977
978
void program::debug_print(std::ostream& os,
                          instruction_ref ins,
Shucai Xiao's avatar
Shucai Xiao committed
979
                          const std::unordered_map<instruction_ref, std::string>& names) const
Shucai Xiao's avatar
Shucai Xiao committed
980
981
982
983
984
{
    if(std::any_of(this->impl->modules.begin(), this->impl->modules.end(), [&](const auto& pp) {
           return is_end(pp.second.end(), ins);
       }))
    {
985
        os << "End instruction" << std::endl;
Shucai Xiao's avatar
Shucai Xiao committed
986
987
988
989
990
991
        return;
    }
    else if(std::none_of(this->impl->modules.begin(),
                         this->impl->modules.end(),
                         [&](const auto& pp) { return pp.second.has_instruction(ins); }))
    {
992
        os << "Instruction not part of program" << std::endl;
Shucai Xiao's avatar
Shucai Xiao committed
993
994
995
        return;
    }

Shucai Xiao's avatar
Shucai Xiao committed
996
    if(contains(names, ins))
Shucai Xiao's avatar
Shucai Xiao committed
997
    {
998
        instruction::print(os, ins, names);
Shucai Xiao's avatar
Shucai Xiao committed
999
1000
1001
    }
}

Shucai Xiao's avatar
Shucai Xiao committed
1002
1003
1004
1005
void program::print(
    std::unordered_map<instruction_ref, std::string>& names,
    const std::function<void(instruction_ref, std::unordered_map<instruction_ref, std::string>)>&
        print_func) const
1006
{
1007
    for(const auto& pp : this->impl->modules)
1008
    {
1009
        names = pp.second.print(print_func, names);
1010
1011
1012
    }
}

Shucai Xiao's avatar
Shucai Xiao committed
1013
void program::print_graph(std::ostream& os, bool brief) const
1014
{
Shucai Xiao's avatar
Shucai Xiao committed
1015
1016
    const auto* mm = this->get_main_module();
    mm->print_graph(os, brief);
1017
1018
1019
1020
}

void program::print_cpp(std::ostream& os) const
{
Shucai Xiao's avatar
Shucai Xiao committed
1021
1022
1023
1024
1025
1026
1027
1028
    auto vec_modules = this->get_modules();
    std::unordered_map<instruction_ref, std::string> names;
    for(auto& mod : vec_modules)
    {
        os << "module: \"" << mod->name() << "\"" << std::endl;
        names = mod->print_cpp(os, names);
        os << std::endl;
    }
1029
1030
}

Paul's avatar
Paul committed
1031
1032
void program::dry_run(std::unordered_map<std::string, argument> params) const
{
Paul's avatar
Paul committed
1033
    auto& ctx = this->impl->ctx;
1034
1035
1036
    generic_eval(*this, ctx, std::move(params), always([](auto ins, auto&&...) {
        return argument{ins->get_shape(), nullptr};
    }));
Paul's avatar
Paul committed
1037
1038
}

Shucai Xiao's avatar
Shucai Xiao committed
1039
void program::annotate(std::ostream& os, const std::function<void(instruction_ref)>& a) const
Paul's avatar
Paul committed
1040
{
1041
    for(auto& pp : this->impl->modules)
Shucai Xiao's avatar
Shucai Xiao committed
1042
    {
1043
1044
        std::cout << pp.first << ":" << std::endl;
        pp.second.annotate(os, a);
Shucai Xiao's avatar
Shucai Xiao committed
1045
    }
Paul's avatar
Paul committed
1046
1047
}

Paul's avatar
Paul committed
1048
const module* program::get_module(const std::string& name) const { return &impl->modules.at(name); }
Shucai Xiao's avatar
Shucai Xiao committed
1049
1050
1051

module* program::create_module(const std::string& name)
{
1052
    assert(not contains(impl->modules, name));
1053
1054
    auto r = impl->modules.emplace(name, name);
    return &(r.first->second);
Shucai Xiao's avatar
Shucai Xiao committed
1055
1056
}

Paul's avatar
Paul committed
1057
module* program::get_module(const std::string& name) { return &impl->modules.at(name); }
Shucai Xiao's avatar
Shucai Xiao committed
1058
1059
1060
1061
1062

module* program::get_main_module() { return get_module("main"); }

const module* program::get_main_module() const { return get_module("main"); }

Paul's avatar
Paul committed
1063
template <class T>
1064
std::vector<T*> generic_get_modules(T* mm)
Shucai Xiao's avatar
Shucai Xiao committed
1065
{
1066
    std::vector<T*> vec_modules;
Shucai Xiao's avatar
Shucai Xiao committed
1067
1068
1069
1070
1071
    vec_modules.push_back(mm);
    auto sub_modules = mm->get_sub_modules();
    vec_modules.insert(vec_modules.end(), sub_modules.begin(), sub_modules.end());
    return vec_modules;
}
Shucai Xiao's avatar
Shucai Xiao committed
1072

Paul's avatar
Paul committed
1073
template <class Map, class T, class OutputIterator>
1074
void generic_get_unused_modules(Map& m, const std::vector<T*>& mods, OutputIterator out)
Shucai Xiao's avatar
Shucai Xiao committed
1075
{
1076
1077
1078
1079
    std::unordered_set<std::string> used;
    std::transform(mods.begin(), mods.end(), std::inserter(used, used.end()), [](auto&& mod) {
        return mod->name();
    });
Paul's avatar
Paul committed
1080
1081
1082
1083
1084
    transform_if(m.begin(),
                 m.end(),
                 out,
                 [&](auto&& pp) { return not contains(used, pp.first); },
                 [](auto&& pp) { return &pp.second; });
1085
}
Shucai Xiao's avatar
Shucai Xiao committed
1086

1087
1088
1089
1090
1091
1092
1093
1094
1095
1096
1097
1098
std::vector<const module*> program::get_modules() const
{
    auto result = generic_get_modules(this->get_main_module());
    generic_get_unused_modules(impl->modules, result, std::back_inserter(result));
    return result;
}

std::vector<module*> program::get_modules()
{
    auto result = generic_get_modules(this->get_main_module());
    generic_get_unused_modules(impl->modules, result, std::back_inserter(result));
    return result;
Shucai Xiao's avatar
Shucai Xiao committed
1099
1100
}

1101
1102
1103
1104
1105
1106
1107
1108
1109
1110
1111
1112
1113
1114
1115
1116
1117
1118
1119
1120
1121
1122
1123
1124
1125
1126
1127
1128
1129
1130
1131
1132
1133
1134
1135
template <class Map, class T>
bool is_unused_module(Map& m, const std::vector<T*>& mods, const std::string& name)
{
    bool is_unused = false;
    generic_get_unused_modules(m, mods, make_function_output_iterator([&](auto* mod) {
                                   if(mod->name() == name)
                                       is_unused = true;
                               }));
    return is_unused;
}

template <class Map>
bool references_instruction(Map& m, const instruction& ins, const std::string& name)
{
    return std::any_of(m.begin(), m.end(), [&](auto&& p) {
        if(p.first == name)
            return false;
        return std::any_of(p.second.begin(), p.second.end(), [&](auto&& i) {
            return std::any_of(i.inputs().begin(), i.inputs().end(), [&](auto&& j) {
                return std::addressof(*j) == std::addressof(ins);
            });
        });
    });
}

void program::remove_module(const std::string& name)
{
    // cppcheck-suppress assertWithSideEffect
    assert(is_unused_module(impl->modules, generic_get_modules(this->get_main_module()), name) &&
           "Module used in program");
    assert(std::none_of(
               impl->modules.at(name).begin(),
               impl->modules.at(name).end(),
               [&](auto&& ins) { return references_instruction(impl->modules, ins, name); }) &&
           "Instruction referenced in another module");
1136
1137
1138
1139
1140
1141
1142
1143
1144
1145
1146
1147
1148
1149
1150
1151

    // if an instruction has an input out side of the current module, need to remove
    // the instruction from its input's outputs
    auto& mod = impl->modules.at(name);
    for(auto ins : iterator_for(mod))
    {
        auto inputs = ins->inputs();
        for(auto in : inputs)
        {
            if(not mod.has_instruction(in))
            {
                in->remove_output(ins);
            }
        }
    }

1152
1153
1154
1155
1156
1157
1158
1159
1160
1161
1162
1163
    impl->modules.erase(name);
}

void program::remove_unused_modules()
{
    std::vector<module*> unused;
    generic_get_unused_modules(
        impl->modules, generic_get_modules(this->get_main_module()), std::back_inserter(unused));
    for(auto* m : unused)
        this->remove_module(m->name());
}

1164
1165
program& program::sort()
{
1166
    for(auto& pp : this->impl->modules)
Shucai Xiao's avatar
Shucai Xiao committed
1167
    {
1168
        pp.second.sort();
Shucai Xiao's avatar
Shucai Xiao committed
1169
1170
    }

1171
1172
1173
    return *this;
}

Paul's avatar
Paul committed
1174
bool operator==(const program& x, const program& y) { return to_string(x) == to_string(y); }
Paul's avatar
Paul committed
1175

Paul's avatar
Paul committed
1176
std::ostream& operator<<(std::ostream& os, const program& p)
Paul's avatar
Paul committed
1177
{
Shucai Xiao's avatar
Shucai Xiao committed
1178
1179
1180
    auto vec_modules = p.get_modules();
    std::unordered_map<instruction_ref, std::string> names;
    for(auto& mod : vec_modules)
Shucai Xiao's avatar
Shucai Xiao committed
1181
    {
Shucai Xiao's avatar
Shucai Xiao committed
1182
1183
1184
1185
1186
1187
1188
        os << "module: \"" << mod->name() << "\"" << std::endl;
        names = mod->print(
            [&](auto ins, auto ins_names) {
                instruction::print(os, ins, ins_names);
                os << std::endl;
            },
            names);
1189
        os << std::endl;
Shucai Xiao's avatar
Shucai Xiao committed
1190
1191
    }

Paul's avatar
Paul committed
1192
    return os;
Paul's avatar
Paul committed
1193
}
Paul's avatar
Paul committed
1194

Paul's avatar
Paul committed
1195
} // namespace MIGRAPHX_INLINE_NS
Paul's avatar
Paul committed
1196
} // namespace migraphx