// SPDX-License-Identifier: MIT
//
// Various utilities for flowgraphs.
//
// Copyright (c) 2017 Luc Van Oostenryck.
//

#include "flowgraph.h"
#include "linearize.h"
#include "flow.h"                       // for bb_generation
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>


struct cfg_info {
        struct basic_block_list *list;
        unsigned long gen;
        unsigned int nr;
};


static void label_postorder(struct basic_block *bb, struct cfg_info *info)
{
        struct basic_block *child;

        if (bb->generation == info->gen)
                return;

        bb->generation = info->gen;
        FOR_EACH_PTR_REVERSE(bb->children, child) {
                label_postorder(child, info);
        } END_FOR_EACH_PTR_REVERSE(child);

        bb->postorder_nr = info->nr++;
        add_bb(&info->list, bb);
}

static void reverse_bbs(struct basic_block_list **dst, struct basic_block_list *src)
{
        struct basic_block *bb;
        FOR_EACH_PTR_REVERSE(src, bb) {
                add_bb(dst, bb);
        } END_FOR_EACH_PTR_REVERSE(bb);
}

static void debug_postorder(struct entrypoint *ep)
{
        struct basic_block *bb;

        printf("%s's reverse postorder:\n", show_ident(ep->name->ident));
        FOR_EACH_PTR(ep->bbs, bb) {
                printf("\t.L%u: %u\n", bb->nr, bb->postorder_nr);
        } END_FOR_EACH_PTR(bb);
}

//
// cfg_postorder - Set the BB's reverse postorder links
//
// Do a postorder DFS walk and set the links
// (which will do the reverse part).
//
int cfg_postorder(struct entrypoint *ep)
{
        struct cfg_info info = {
                .gen = ++bb_generation,
        };

        label_postorder(ep->entry->bb, &info);

        // OK, now info.list contains the node in postorder
        // Reuse ep->bbs for the reverse postorder.
        free_ptr_list(&ep->bbs);
        ep->bbs = NULL;
        reverse_bbs(&ep->bbs, info.list);
        free_ptr_list(&info.list);
        if (dbg_postorder)
                debug_postorder(ep);
        return info.nr;
}

//
// Calculate the dominance tree following:
//      "A simple, fast dominance algorithm"
//      by K. D. Cooper, T. J. Harvey, and K. Kennedy.
//      cfr. http://www.cs.rice.edu/∼keith/EMBED/dom.pdf
//
static struct basic_block *intersect_dom(struct basic_block *doms[],
                struct basic_block *b1, struct basic_block *b2)
{
        int f1 = b1->postorder_nr, f2 = b2->postorder_nr;
        while (f1 != f2) {
                while (f1 < f2) {
                        b1 = doms[f1];
                        f1 = b1->postorder_nr;
                }
                while (f2 < f1) {
                        b2 = doms[f2];
                        f2 = b2->postorder_nr;
                }
        }
        return b1;
}

static void debug_domtree(struct entrypoint *ep)
{
        struct basic_block *bb = ep->entry->bb;

        printf("%s's idoms:\n", show_ident(ep->name->ident));
        FOR_EACH_PTR(ep->bbs, bb) {
                if (bb == ep->entry->bb)
                        continue;       // entry node has no idom
                printf("\t%s    <- %s\n", show_label(bb), show_label(bb->idom));
        } END_FOR_EACH_PTR(bb);
}

void domtree_build(struct entrypoint *ep)
{
        struct basic_block *entry = ep->entry->bb;
        struct basic_block **doms;
        struct basic_block *bb;
        unsigned int size;
        int max_level = 0;
        int changed;

        // First calculate the (reverse) postorder.
        // This will give use us:
        //      - the links to do a reverse postorder traversal
        //      - the order number for each block
        size = cfg_postorder(ep);

        // initialize the dominators array
        doms = calloc(size, sizeof(*doms));
        assert(entry->postorder_nr == size-1);
        doms[size-1] = entry;

        do {
                struct basic_block *b;

                changed = 0;
                FOR_EACH_PTR(ep->bbs, b) {
                        struct basic_block *p;
                        int bnr = b->postorder_nr;
                        struct basic_block *new_idom = NULL;

                        if (b == entry)
                                continue;       // ignore entry node

                        FOR_EACH_PTR(b->parents, p) {
                                unsigned int pnr = p->postorder_nr;
                                if (!doms[pnr])
                                        continue;
                                if (!new_idom) {
                                        new_idom = p;
                                        continue;
                                }

                                new_idom = intersect_dom(doms, p, new_idom);
                        } END_FOR_EACH_PTR(p);

                        assert(new_idom);
                        if (doms[bnr] != new_idom) {
                                doms[bnr] = new_idom;
                                changed = 1;
                        }
                } END_FOR_EACH_PTR(b);
        } while (changed);

        // set the idom links
        FOR_EACH_PTR(ep->bbs, bb) {
                struct basic_block *idom = doms[bb->postorder_nr];

                if (bb == entry)
                        continue;       // ignore entry node

                bb->idom = idom;
                add_bb(&idom->doms, bb);
        } END_FOR_EACH_PTR(bb);
        entry->idom = NULL;

        // set the dominance levels
        FOR_EACH_PTR(ep->bbs, bb) {
                struct basic_block *idom = bb->idom;
                int level = idom ? idom->dom_level + 1 : 0;

                bb->dom_level = level;
                if (max_level < level)
                        max_level = level;
        } END_FOR_EACH_PTR(bb);
        ep->dom_levels = max_level + 1;

        free(doms);
        if (dbg_domtree)
                debug_domtree(ep);
}

// dt_dominates - does BB a dominates BB b?
bool domtree_dominates(struct basic_block *a, struct basic_block *b)
{
        if (a == b)                     // dominance is reflexive
                return true;
        if (a == b->idom)
                return true;
        if (b == a->idom)
                return false;

        // can't dominate if deeper in the DT
        if (a->dom_level >= b->dom_level)
                return false;

        // FIXME: can be faster if we have the DFS in-out numbers

        // walk up the dominator tree
        for (b = b->idom; b; b = b->idom) {
                if (b == a)
                        return true;
        }
        return false;
}