// Optimierende Übersetzer WS 2020/21
// Aufgabe 1: Dominator-Analyse
// H. Moritsch

SET

DOMAIN
    LabelSet = set(snum) // power set of signed integers ordered by set inclusion
    LabelLattice = lift(LabelSet) // augmented with top and bottom element
ENDDOMAIN

PROBLEM da
    direction:  forward
    carrier:    LabelLattice
    init_start: lift({})
    init:       top

    equal:      eq
    combine:    comb
    retfunc:    comb
    widening:   wide


TRANSFER

// node types not considered
DeclareStmt(_, _), _: @;
// FILL IN: more node types

// rest of node types is relevant
_, _:
    let dominators <= @;
    in lift(transfer(dominators, label));
    

SUPPORT

transfer :: LabelSet, snum -> LabelSet;
    transfer(a, b) = // FILL IN

eq :: LabelLattice, LabelLattice -> bool;
    eq(a, b) = // FILL IN

comb :: LabelLattice, LabelLattice -> LabelLattice;
    // greatest lower bound in LabelSet is set intersection
    comb(a, b) = // FILL IN

wide(a, b) = b; // no widening used