Method build

src/memory_coloring.cpp:215–285

Build the allocation_color class from the conflict_table

    // Build the allocation_color class from the conflict_table
    static allocation_segment
    build(const module& m, const instruction_set_map& conflict_table, std::size_t alignment)
    {
        allocation_segment as{};
        std::vector<instruction_ref> conflict_queue;
        // Add all allocations to the conflict_queue
        std::transform(conflict_table.begin(),
                       conflict_table.end(),
                       std::back_inserter(conflict_queue),
                       [](auto&& pp) { return pp.first; });

        auto alloc_index = create_allocation_index(m, conflict_table);

        // Sort the conflict queue so we process the allocation with the most
        // number of adjacent allocations first
        std::sort(conflict_queue.begin(), conflict_queue.end(), by(std::greater<>{}, [&](auto x) {
                      return std::make_tuple(
                          conflict_table.at(x).size(), x->get_shape().bytes(), alloc_index.at(x));
                  }));
        // Process the conflict_queue, we refer to the current allocation as
        // the parent and the adjacent allocations as children
        for(auto parent : conflict_queue)
        {
            // Sort children by size
            std::vector<instruction_ref> children(conflict_table.at(parent).begin(),
                                                  conflict_table.at(parent).end());
            std::sort(children.begin(), children.end(), by(std::less<>{}, [&](auto x) {
                          return std::make_tuple(x->get_shape().bytes(), alloc_index.at(x));
                      }));
            assert(not contains(children, parent));
            // This set is to track the segments already processed
            std::set<segment> segments;
            // Add all segments for the children to the segments already processed
            transform_if(
                children.begin(),
                children.end(),
                std::inserter(segments, segments.begin()),
                [&](auto child) { return as.get_segment(child); },
                [&](auto child) { return *as.get_segment(child); });

            assert(as.get_segment(parent) == nullptr);
            as.add_segment(parent, next_segment(segments, parent, alignment));
        }
        // Reduce the number of segments
        for(std::size_t n = 0; n < 3; n++)
        {
            for(auto parent : conflict_queue)
            {
                auto children = conflict_table.at(parent);
                // This set is to track the segments already processed
                std::set<segment> segments;
                // Add all segments for the children to the segments already processed
                transform_if(
                    children.begin(),
                    children.end(),
                    std::inserter(segments, segments.begin()),
                    [&](auto child) { return as.get_segment(child); },
                    [&](auto child) { return *as.get_segment(child); });