interference-graph ( intervals -- graph )

Vocabulary

compiler.cfg.register-allocation.chordal

Inputs

intervals

an object

Outputs

graph

an object

Definition

USING: accessors assocs compiler.cfg.linear-scan.live-intervals
kernel math sequences sorting ;

IN: compiler.cfg.register-allocation.chordal

:: interference-graph ( intervals -- graph )
    intervals [ vreg>> V{ } clone ] H{ } map>assoc
    :> graph intervals [ live-interval-start ] sort-by
    :> ordered ordered [| a i |
        ordered i 1 + tail-slice :> later later
        [ live-interval-start a live-interval-end > ] find drop
        later length or later swap head-slice [| b |
            a interval-reg-class b interval-reg-class = [
                a b intervals-intersect? [
                    b vreg>> a vreg>> graph at push
                    a vreg>> b vreg>> graph at push
                ] when
            ] when
        ] each
    ] each-index graph ;