coloring.rs 38.6 KB
Newer Older
1
// Copyright 2017 The Australian National University
qinsoon's avatar
qinsoon committed
2
//
3 4 5
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
qinsoon's avatar
qinsoon committed
6
//
7
//     http://www.apache.org/licenses/LICENSE-2.0
qinsoon's avatar
qinsoon committed
8
//
9 10 11 12 13 14
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

15 16
extern crate hprof;

qinsoon's avatar
qinsoon committed
17
use ast::ptr::*;
qinsoon's avatar
qinsoon committed
18 19 20
use ast::ir::*;
use compiler::backend;
use compiler::backend::reg_alloc::graph_coloring;
21
use compiler::backend::reg_alloc::graph_coloring::liveness::InterferenceGraph;
qinsoon's avatar
qinsoon committed
22 23
use compiler::machine_code::CompiledFunction;
use vm::VM;
24
use utils::LinkedHashSet;
25
use utils::LinkedHashMap;
26 27
use compiler::backend::reg_alloc::graph_coloring::liveness::Move;

28
/// allows coalescing
qinsoon's avatar
qinsoon committed
29
const COALESCING: bool = true;
30 31 32 33 34 35 36
/// abort after N rewrite iterations
/// (this is used to detect any possible infinite loop due to bugs)
const MAX_REWRITE_ITERATIONS_ALLOWED: usize = 50;
/// check invariants in every loop
/// (this will make register allocation run extremely slow - be careful
/// when using this with large workloads)
const CHECK_INVARIANTS: bool = false;
37

qinsoon's avatar
qinsoon committed
38 39
/// GraphColoring algorithm
/// based on Appel's book section 11.4
qinsoon's avatar
qinsoon committed
40
pub struct GraphColoring<'a> {
qinsoon's avatar
qinsoon committed
41
    // context
qinsoon's avatar
qinsoon committed
42 43 44
    pub func: &'a mut MuFunctionVersion,
    pub cf: &'a mut CompiledFunction,
    pub vm: &'a VM,
45
    pub ig: InterferenceGraph,
qinsoon's avatar
qinsoon committed
46

47 48 49 50
    /// how many coloring iteration have we done?
    /// In case that a bug may trigger the coloring iterate endlessly, we use this count to stop
    iteration_count: usize,

qinsoon's avatar
qinsoon committed
51
    /// machine registers, preassigned a color
52
    precolored: LinkedHashSet<MuID>,
qinsoon's avatar
qinsoon committed
53
    /// all colors available
54
    colors: LinkedHashMap<backend::RegGroup, LinkedHashSet<MuID>>,
qinsoon's avatar
qinsoon committed
55
    /// temporaries, not precolored and not yet processed
qinsoon's avatar
qinsoon committed
56
    initial: LinkedHashSet<MuID>,
qinsoon's avatar
qinsoon committed
57 58

    /// list of low-degree non-move-related nodes
59
    worklist_simplify: LinkedHashSet<MuID>,
qinsoon's avatar
qinsoon committed
60
    /// low-degree move related nodes
61
    worklist_freeze: LinkedHashSet<MuID>,
qinsoon's avatar
qinsoon committed
62 63 64 65
    /// nodes marked for possible spilling during this round
    worklist_spill: LinkedHashSet<MuID>,
    /// nodes that are selected for spilling, but not yet spilled (select_spill() is called on it)
    waiting_for_spill: LinkedHashSet<MuID>,
qinsoon's avatar
qinsoon committed
66
    /// nodes marked for spilling during this round
qinsoon's avatar
qinsoon committed
67
    spilled_nodes: LinkedHashSet<MuID>,
qinsoon's avatar
qinsoon committed
68 69
    /// temps that have been coalesced
    /// when u <- v is coalesced, v is added to this set and u put back on some work list
70
    coalesced_nodes: LinkedHashSet<MuID>,
qinsoon's avatar
qinsoon committed
71
    /// nodes successfully colored
qinsoon's avatar
qinsoon committed
72
    colored_nodes: LinkedHashSet<MuID>,
qinsoon's avatar
qinsoon committed
73
    /// stack containing temporaries removed from the graph
74
    select_stack: Vec<MuID>,
qinsoon's avatar
qinsoon committed
75 76

    /// moves that have been coalesced
77
    coalesced_moves: LinkedHashSet<Move>,
qinsoon's avatar
qinsoon committed
78
    /// moves whose source and target interfere
79
    constrained_moves: LinkedHashSet<Move>,
qinsoon's avatar
qinsoon committed
80 81 82
    /// moves that will no longer be considered for coalescing
    frozen_moves: LinkedHashSet<Move>,
    /// moves enabled for possible coalescing
qinsoon's avatar
qinsoon committed
83
    worklist_moves: LinkedHashSet<Move>,
qinsoon's avatar
qinsoon committed
84 85 86 87
    /// moves not yet ready for coalescing
    active_moves: LinkedHashSet<Move>,

    /// a mapping from a node to the list of moves it is associated with
88
    movelist: LinkedHashMap<MuID, LinkedHashSet<Move>>,
qinsoon's avatar
qinsoon committed
89
    /// when a move (u, v) has been coalesced, and v put in coalescedNodes, then alias(v) = u
90
    alias: LinkedHashMap<MuID, MuID>,
qinsoon's avatar
qinsoon committed
91

qinsoon's avatar
qinsoon committed
92 93 94 95
    // for validation use
    /// we need to log all registers get spilled with their spill location
    spill_history: LinkedHashMap<MuID, P<Value>>,
    /// we need to know the mapping between scratch temp -> original temp
96
    spill_scratch_temps: LinkedHashMap<MuID, MuID>
qinsoon's avatar
qinsoon committed
97 98
}

qinsoon's avatar
qinsoon committed
99
impl<'a> GraphColoring<'a> {
qinsoon's avatar
qinsoon committed
100
    /// starts coloring
qinsoon's avatar
qinsoon committed
101 102 103
    pub fn start(
        func: &'a mut MuFunctionVersion,
        cf: &'a mut CompiledFunction,
104
        vm: &'a VM
qinsoon's avatar
qinsoon committed
105 106 107 108 109 110 111
    ) -> GraphColoring<'a> {
        GraphColoring::start_with_spill_history(
            LinkedHashMap::new(),
            LinkedHashMap::new(),
            0,
            func,
            cf,
112
            vm
qinsoon's avatar
qinsoon committed
113
        )
qinsoon's avatar
qinsoon committed
114 115
    }

qinsoon's avatar
qinsoon committed
116
    /// restarts coloring with spill history
qinsoon's avatar
qinsoon committed
117 118 119 120 121 122
    fn start_with_spill_history(
        spill_history: LinkedHashMap<MuID, P<Value>>,
        spill_scratch_temps: LinkedHashMap<MuID, MuID>,
        iteration_count: usize,
        func: &'a mut MuFunctionVersion,
        cf: &'a mut CompiledFunction,
123
        vm: &'a VM
qinsoon's avatar
qinsoon committed
124 125 126
    ) -> GraphColoring<'a> {
        assert!(
            iteration_count < MAX_REWRITE_ITERATIONS_ALLOWED,
127
            "reach graph coloring max rewrite iterations ({}), probably something is going wrong",
qinsoon's avatar
qinsoon committed
128 129
            MAX_REWRITE_ITERATIONS_ALLOWED
        );
130 131
        let iteration_count = iteration_count + 1;

132
        trace!("Initializing coloring allocator...");
133 134
        cf.mc().trace_mc();

qinsoon's avatar
qinsoon committed
135 136
        let ig = graph_coloring::build_inteference_graph(cf, func);

137
        let coloring = GraphColoring {
qinsoon's avatar
qinsoon committed
138 139 140 141
            func: func,
            cf: cf,
            vm: vm,
            ig: ig,
142
            iteration_count: iteration_count,
143
            precolored: LinkedHashSet::new(),
144
            colors: {
145
                let mut map = LinkedHashMap::new();
146 147
                map.insert(backend::RegGroup::GPR, LinkedHashSet::new());
                map.insert(backend::RegGroup::FPR, LinkedHashSet::new());
148 149
                map
            },
qinsoon's avatar
qinsoon committed
150 151 152
            colored_nodes: LinkedHashSet::new(),
            initial: LinkedHashSet::new(),
            worklist_moves: LinkedHashSet::new(),
153
            movelist: LinkedHashMap::new(),
154 155 156 157
            active_moves: LinkedHashSet::new(),
            coalesced_nodes: LinkedHashSet::new(),
            coalesced_moves: LinkedHashSet::new(),
            constrained_moves: LinkedHashSet::new(),
158
            alias: LinkedHashMap::new(),
qinsoon's avatar
qinsoon committed
159 160 161
            worklist_spill: LinkedHashSet::new(),
            waiting_for_spill: LinkedHashSet::new(),
            spilled_nodes: LinkedHashSet::new(),
qinsoon's avatar
qinsoon committed
162
            spill_history: spill_history,
qinsoon's avatar
qinsoon committed
163
            spill_scratch_temps: spill_scratch_temps,
164 165 166
            worklist_freeze: LinkedHashSet::new(),
            frozen_moves: LinkedHashSet::new(),
            worklist_simplify: LinkedHashSet::new(),
167
            select_stack: Vec::new()
qinsoon's avatar
qinsoon committed
168
        };
qinsoon's avatar
qinsoon committed
169

qinsoon's avatar
qinsoon committed
170
        coloring.regalloc()
qinsoon's avatar
qinsoon committed
171
    }
qinsoon's avatar
qinsoon committed
172

qinsoon's avatar
qinsoon committed
173
    /// does coloring register allocation
174
    fn regalloc(mut self) -> GraphColoring<'a> {
175
        trace!("---InterenceGraph---");
qinsoon's avatar
qinsoon committed
176
        self.ig.print(&self.func.context);
qinsoon's avatar
qinsoon committed
177 178 179

        // start timing for graph coloring
        let _p = hprof::enter("regalloc: graph coloring");
qinsoon's avatar
qinsoon committed
180

qinsoon's avatar
qinsoon committed
181
        // precolor for all machine registers
182
        for reg in backend::all_regs().values() {
183
            let reg_id = reg.extract_ssa_id().unwrap();
184
            self.precolored.insert(reg_id);
185
        }
qinsoon's avatar
qinsoon committed
186

qinsoon's avatar
qinsoon committed
187
        // put usable registers as available colors
188
        for reg in backend::all_usable_regs().iter() {
189
            let reg_id = reg.extract_ssa_id().unwrap();
qinsoon's avatar
qinsoon committed
190 191
            let group = backend::pick_group_for_reg(reg_id);
            self.colors.get_mut(&group).unwrap().insert(reg_id);
192
        }
qinsoon's avatar
qinsoon committed
193 194

        // push uncolored nodes to initial work set
195 196
        for node in self.ig.nodes() {
            if !self.ig.is_colored(node) {
qinsoon's avatar
qinsoon committed
197
                self.initial.insert(node);
198 199
            }
        }
qinsoon's avatar
qinsoon committed
200 201

        // initialize work
202 203
        self.build();
        self.make_work_list();
qinsoon's avatar
qinsoon committed
204 205

        // main loop
206 207 208 209 210 211 212 213 214 215
        while {
            if !self.worklist_simplify.is_empty() {
                self.simplify();
            } else if !self.worklist_moves.is_empty() {
                self.coalesce();
            } else if !self.worklist_freeze.is_empty() {
                self.freeze();
            } else if !self.worklist_spill.is_empty() {
                self.select_spill();
            }
qinsoon's avatar
qinsoon committed
216

qinsoon's avatar
qinsoon committed
217 218 219 220
            if CHECK_INVARIANTS {
                self.check_invariants();
            }

qinsoon's avatar
qinsoon committed
221 222
            !(self.worklist_simplify.is_empty() && self.worklist_moves.is_empty() &&
                  self.worklist_freeze.is_empty() && self.worklist_spill.is_empty())
223
        } {}
qinsoon's avatar
qinsoon committed
224 225

        // pick color for nodes
qinsoon's avatar
qinsoon committed
226 227
        self.assign_colors();

qinsoon's avatar
qinsoon committed
228
        // finish
229 230
        drop(_p);

qinsoon's avatar
qinsoon committed
231
        // if we need to spill
qinsoon's avatar
qinsoon committed
232 233
        if !self.spilled_nodes.is_empty() {
            trace!("spill required");
234 235 236
            if cfg!(debug_assertions) {
                trace!("nodes to be spilled:");
                for node in self.spilled_nodes.iter() {
237
                    trace!("{}", *node);
238 239 240
                }
            }

qinsoon's avatar
qinsoon committed
241
            // rewrite program to insert spilling code
qinsoon's avatar
qinsoon committed
242
            self.rewrite_program();
qinsoon's avatar
qinsoon committed
243

qinsoon's avatar
qinsoon committed
244
            // recursively redo graph coloring
qinsoon's avatar
qinsoon committed
245 246 247 248 249 250
            return GraphColoring::start_with_spill_history(
                self.spill_history.clone(),
                self.spill_scratch_temps.clone(),
                self.iteration_count,
                self.func,
                self.cf,
251
                self.vm
qinsoon's avatar
qinsoon committed
252
            );
qinsoon's avatar
qinsoon committed
253 254
        }

255
        self
256
    }
qinsoon's avatar
qinsoon committed
257

qinsoon's avatar
qinsoon committed
258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 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 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419
    fn check_invariants(&self) {
        self.checkinv_degree();
        self.checkinv_simplify_worklist();
        self.checkinv_freeze_worklist();
        self.checkinv_spill_worklist();
    }

    fn checkinv_degree(&self) {
        trace!("Check invariant: degree...");
        // degree invariant
        // for u in simplifyWorklist \/ freezeWorklist \/ spillWorklist =>
        //   degree(u) = |adjList(u) /\
        //               (precolored \/ simplifyWorklist \/ freezeWorklist \/ spillWorklist)|

        let union = {
            let mut ret = LinkedHashSet::new();
            ret.add_all(self.worklist_simplify.clone());
            ret.add_all(self.worklist_freeze.clone());
            ret.add_all(self.worklist_spill.clone());
            ret
        };

        for u in union.iter() {
            let degree_u = self.ig.get_degree_of(*u);

            let set: LinkedHashSet<MuID> = {
                let adj: LinkedHashSet<MuID> = self.ig.get_adj_list(*u).clone();

                let mut union_: LinkedHashSet<MuID> = LinkedHashSet::new();
                union_.add_all(self.precolored.clone());
                union_.add_all(union.clone());

                {
                    let mut intersect: LinkedHashSet<MuID> = LinkedHashSet::new();
                    for item in adj.iter() {
                        if union_.contains(item) {
                            intersect.insert(*item);
                        }
                    }
                    intersect
                }
            };

            self.checkinv_assert(
                degree_u == set.len(),
                format!("degree({})={} != set(len)={}", u, degree_u, set.len())
            );
        }
    }

    fn checkinv_simplify_worklist(&self) {
        trace!("Check invariant: worklistSimplify...");
        // for u in simplifyWorkList
        //   either u is 'selected for spilling', otherwise
        //   degree(u) < K &&
        //   movelist(u) /\ (activeMoves \/ worklistMoves) = {} (emtpy)
        for u in self.worklist_simplify.iter() {
            if self.waiting_for_spill.contains(&u) {
                // no longer needs to check
                return;
            } else {
                // 1st cond: degree(u) < K
                let degree = self.ig.get_degree_of(*u);
                self.checkinv_assert(
                    degree < self.n_regs_for_node(*u),
                    format!("degree({})={} < K fails", u, degree)
                );

                // 2nd cond
                let movelist = self.get_movelist(*u);
                let union = {
                    let mut ret = self.active_moves.clone();
                    ret.add_all(self.worklist_moves.clone());
                    ret
                };
                let intersect = {
                    let mut ret = LinkedHashSet::new();
                    for m in movelist.iter() {
                        if union.contains(m) {
                            ret.insert(*m);
                        }
                    }
                    ret
                };

                self.checkinv_assert(
                    intersect.len() == 0,
                    format!("intersect({}) is not empty", u)
                );
            }
        }
    }

    fn checkinv_freeze_worklist(&self) {
        trace!("Check invariant: worklistFreeze...");
        // for u in freezeWorklist
        //   degree(u) < K &&
        //   moveList(u) /\ (activeMoves \/ worklistMoves) != {} (non empty)
        for u in self.worklist_freeze.iter() {
            // 1st cond: degree(u) < K
            let degree = self.ig.get_degree_of(*u);
            self.checkinv_assert(
                degree < self.n_regs_for_node(*u),
                format!("degree({})={} < K fails", u, degree)
            );

            // 2nd cond
            // 2nd cond
            let movelist = self.get_movelist(*u);
            let union = {
                let mut ret = self.active_moves.clone();
                ret.add_all(self.worklist_moves.clone());
                ret
            };
            let intersect = {
                let mut ret = LinkedHashSet::new();
                for m in movelist.iter() {
                    if union.contains(m) {
                        ret.insert(*m);
                    }
                }
                ret
            };
            self.checkinv_assert(intersect.len() != 0, format!("intersect({}) is empty", u));
        }
    }

    fn checkinv_spill_worklist(&self) {
        trace!("Check invariant: worklistSpill...");
        // for u in spillWorklist
        //    degree(u) >= K
        for u in self.worklist_spill.iter() {
            let degree = self.ig.get_degree_of(*u);
            self.checkinv_assert(
                degree >= self.n_regs_for_node(*u),
                format!("degree({})={} >= K fails", u, degree)
            );
        }
    }

    fn checkinv_assert(&self, cond: bool, msg: String) {
        if !cond {
            error!("{}", msg);

            // dump current state
            trace!("Current state:");

            trace!("simplifyWorklist: {:?}", self.worklist_simplify);
            trace!("freezeWorklist: {:?}", self.worklist_freeze);
            trace!("spillWorklist: {:?}", self.worklist_spill);
            trace!("worklistMoves: {:?}", self.worklist_moves);

            for node in self.ig.nodes() {
                trace!("Node {}: degree={}", node, self.ig.get_degree_of(node));
                trace!("         adjList={:?}", self.ig.get_adj_list(node));
                trace!("         moveList={:?}", self.get_movelist(node));
            }

            panic!()
        }
    }

420 421 422 423 424
    fn add_to_movelist(
        movelist: &mut LinkedHashMap<MuID, LinkedHashSet<Move>>,
        reg: MuID,
        mov: Move
    ) {
425
        trace!("  add {:?} to movelist[{}]", mov, reg);
426
        if movelist.contains_key(&reg) {
427
            let list = movelist.get_mut(&reg).unwrap();
428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443
            list.insert(mov);
        } else {
            let mut list = LinkedHashSet::new();
            list.insert(mov);
            movelist.insert(reg, list);
        }
    }

    fn get_movelist(&self, reg: MuID) -> LinkedHashSet<Move> {
        if let Some(list) = self.movelist.get(&reg) {
            list.clone()
        } else {
            LinkedHashSet::new()
        }
    }

444
    fn build(&mut self) {
445
        if COALESCING {
qinsoon's avatar
qinsoon committed
446
            trace!("Coalescing enabled, build move list...");
447
            let ref ig = self.ig;
448
            for m in ig.moves().iter() {
449
                trace!("  add {:?} to worklistMoves", m);
qinsoon's avatar
qinsoon committed
450
                self.worklist_moves.insert(*m);
451 452
                GraphColoring::add_to_movelist(&mut self.movelist, m.from, *m);
                GraphColoring::add_to_movelist(&mut self.movelist, m.to, *m);
453
            }
454
        } else {
qinsoon's avatar
qinsoon committed
455
            trace!("Coalescing disabled...");
456
        }
457 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

        trace!("Build freeze cost for each node...");
        // we try to avoid freeze a node that is involved in many moves
        for n in self.ig.nodes() {
            // freeze_cost(n) = SUM ((spill_cost(src) + spill_cost(dst)) for m (mov src->dst)
            // in movelist[n])
            let closure = {
                let mut ret = LinkedHashSet::new();
                let mut worklist = LinkedHashSet::new();
                worklist.insert(n);

                while !worklist.is_empty() {
                    let n = worklist.pop_front().unwrap();
                    for m in self.get_movelist(n).iter() {
                        if !ret.contains(&m.from) {
                            ret.insert(m.from);
                            worklist.insert(m.from);
                        }
                        if !ret.contains(&m.to) {
                            ret.insert(m.to);
                            worklist.insert(m.to);
                        }
                    }
                }

                ret
            };

            let mut freeze_cost = 0f32;
            for related_node in closure.iter() {
                freeze_cost += self.ig.get_spill_cost(*related_node);
            }

            self.ig.set_freeze_cost(n, freeze_cost);
            trace!("  {} closure: {:?}", n, closure);
            trace!("     freeze cost = {}", freeze_cost);
        }
494
    }
qinsoon's avatar
qinsoon committed
495

496
    fn make_work_list(&mut self) {
497
        trace!("Making work list from initials...");
498
        while !self.initial.is_empty() {
qinsoon's avatar
qinsoon committed
499
            let node = self.initial.pop_front().unwrap();
qinsoon's avatar
qinsoon committed
500

qinsoon's avatar
qinsoon committed
501 502
            // degree >= K
            if self.ig.get_degree_of(node) >= self.n_regs_for_node(node) {
qinsoon's avatar
qinsoon committed
503
                trace!(
504
                    "  {} 's degree >= reg number limit (K), push to worklistSpill",
505
                    node
qinsoon's avatar
qinsoon committed
506
                );
qinsoon's avatar
qinsoon committed
507
                self.worklist_spill.insert(node);
508
            } else if self.is_move_related(node) {
509
                trace!("  {} is move related, push to worklistFreeze", node);
510 511
                self.worklist_freeze.insert(node);
            } else {
qinsoon's avatar
qinsoon committed
512
                trace!(
513
                    "  {} has small degree and not move related, push to worklistSimplify",
514
                    node
qinsoon's avatar
qinsoon committed
515
                );
516 517 518 519
                self.worklist_simplify.insert(node);
            }
        }
    }
qinsoon's avatar
qinsoon committed
520

521
    fn n_regs_for_node(&self, node: MuID) -> usize {
522
        backend::number_of_usable_regs_in_group(self.ig.get_group_of(node))
523
    }
qinsoon's avatar
qinsoon committed
524

525
    fn is_move_related(&mut self, node: MuID) -> bool {
526 527
        !self.node_moves(node).is_empty()
    }
528 529 530 531 532 533 534 535 536 537

    fn is_spillable(&self, temp: MuID) -> bool {
        // if a temporary is created as scratch temp for a spilled temporary, we
        // should not spill it again (infinite loop otherwise)
        if self.spill_scratch_temps.contains_key(&temp) {
            false
        } else {
            true
        }
    }
qinsoon's avatar
qinsoon committed
538

539
    fn node_moves(&mut self, node: MuID) -> LinkedHashSet<Move> {
540
        let mut moves = LinkedHashSet::new();
qinsoon's avatar
qinsoon committed
541

542 543 544 545
        // addAll(active_moves)
        for m in self.active_moves.iter() {
            moves.insert(m.clone());
        }
qinsoon's avatar
qinsoon committed
546

547 548 549 550
        // addAll(worklist_moves)
        for m in self.worklist_moves.iter() {
            moves.insert(m.clone());
        }
qinsoon's avatar
qinsoon committed
551

552
        let mut retained = LinkedHashSet::new();
553
        let movelist = self.get_movelist(node);
554
        for m in moves.iter() {
555
            if movelist.contains(m) {
556 557 558
                retained.insert(*m);
            }
        }
qinsoon's avatar
qinsoon committed
559

560 561
        retained
    }
qinsoon's avatar
qinsoon committed
562

563
    fn simplify(&mut self) {
564
        // remove next element from worklist_simplify, we know its not empty
565
        let node = self.worklist_simplify.pop_front().unwrap();
qinsoon's avatar
qinsoon committed
566

567
        trace!("Simplifying {}", node);
qinsoon's avatar
qinsoon committed
568

569
        self.select_stack.push(node);
570
        for m in self.adjacent(node).iter() {
571
            self.decrement_degree(*m);
572 573
        }
    }
qinsoon's avatar
qinsoon committed
574

575
    fn adjacent(&self, n: MuID) -> LinkedHashSet<MuID> {
576
        let mut adj = LinkedHashSet::new();
qinsoon's avatar
qinsoon committed
577

578
        // add n's successors
579 580
        for s in self.ig.get_adj_list(n).iter() {
            adj.insert(*s);
581
        }
qinsoon's avatar
qinsoon committed
582

583 584 585 586
        // removeAll(select_stack)
        for s in self.select_stack.iter() {
            adj.remove(s);
        }
qinsoon's avatar
qinsoon committed
587

588 589 590 591
        // removeAll(coalesced_nodes)
        for s in self.coalesced_nodes.iter() {
            adj.remove(s);
        }
qinsoon's avatar
qinsoon committed
592

593 594
        adj
    }
qinsoon's avatar
qinsoon committed
595

596
    fn decrement_degree(&mut self, n: MuID) {
597 598 599
        if self.precolored.contains(&n) {
            return;
        }
qinsoon's avatar
qinsoon committed
600

601
        let d = self.ig.get_degree_of(n);
602
        debug_assert!(d != 0);
603
        self.ig.set_degree_of(n, d - 1);
604
        trace!("  decrement degree of {} from {} to {}", n, d, d - 1);
qinsoon's avatar
qinsoon committed
605

606
        if d == self.n_regs_for_node(n) {
607
            trace!("  {}'s degree is K, no longer need to spill it", n);
608 609 610
            let mut nodes = self.adjacent(n);
            nodes.insert(n);
            self.enable_moves(nodes);
qinsoon's avatar
qinsoon committed
611

612
            trace!("  remove {} from worklistSpill", n);
qinsoon's avatar
qinsoon committed
613
            self.worklist_spill.remove(&n);
qinsoon's avatar
qinsoon committed
614

615
            if self.is_move_related(n) {
616
                trace!("  {} is move related, push to worklistFreeze", n);
617 618
                self.worklist_freeze.insert(n);
            } else {
619
                trace!("  {} is not move related, push to worklistSimplify", n);
620 621 622 623
                self.worklist_simplify.insert(n);
            }
        }
    }
qinsoon's avatar
qinsoon committed
624

625
    fn enable_moves(&mut self, nodes: LinkedHashSet<MuID>) {
626
        trace!("  enable moves of: {:?}", nodes);
627 628 629 630
        for n in nodes.iter() {
            let n = *n;
            for mov in self.node_moves(n).iter() {
                let mov = *mov;
631
                if self.active_moves.contains(&mov) {
632
                    trace!("  move {:?} from activeMoves to worklistMoves", mov);
qinsoon's avatar
qinsoon committed
633
                    self.active_moves.remove(&mov);
qinsoon's avatar
qinsoon committed
634
                    self.worklist_moves.insert(mov);
635 636 637 638
                }
            }
        }
    }
qinsoon's avatar
qinsoon committed
639

640
    fn coalesce(&mut self) {
qinsoon's avatar
qinsoon committed
641
        let m = self.worklist_moves.pop_front().unwrap();
qinsoon's avatar
qinsoon committed
642

qinsoon's avatar
qinsoon committed
643
        trace!("Coalescing on {:?}...", m);
644
        trace!("  (pop {:?} form worklistMoves)", m);
qinsoon's avatar
qinsoon committed
645

qinsoon's avatar
qinsoon committed
646 647
        let x = self.get_alias(m.from);
        let y = self.get_alias(m.to);
648 649
        trace!("  resolve alias: {} -> {}", m.from, x);
        trace!("  resolve alias: {} -> {}", m.to, y);
qinsoon's avatar
qinsoon committed
650

qinsoon's avatar
qinsoon committed
651 652 653 654 655 656
        let (u, v, precolored_u, precolored_v) = {
            if self.precolored.contains(&y) {
                let u = y;
                let v = x;
                let precolored_u = true;
                let precolored_v = self.precolored.contains(&v);
qinsoon's avatar
qinsoon committed
657

qinsoon's avatar
qinsoon committed
658 659 660 661 662 663
                (u, v, precolored_u, precolored_v)
            } else {
                let u = x;
                let v = y;
                let precolored_u = self.precolored.contains(&u);
                let precolored_v = self.precolored.contains(&v);
qinsoon's avatar
qinsoon committed
664

qinsoon's avatar
qinsoon committed
665 666 667
                (u, v, precolored_u, precolored_v)
            }
        };
qinsoon's avatar
qinsoon committed
668
        trace!(
669
            "  u={}, v={}, precolored_u={}, precolroed_v={}",
670 671
            u,
            v,
qinsoon's avatar
qinsoon committed
672 673 674 675
            precolored_u,
            precolored_v
        );

qinsoon's avatar
qinsoon committed
676 677 678 679 680 681 682 683 684 685
        // if they are not from the same register group, we cannot coalesce them
        if self.ig.get_group_of(u) != self.ig.get_group_of(v) {
            if !precolored_v {
                self.add_worklist(v);
            }
            if !precolored_u {
                self.add_worklist(u);
            }
            self.constrained_moves.insert(m);
            info!(
686
                "  u and v are temporaries of different register groups, cannot coalesce: {:?}",
qinsoon's avatar
qinsoon committed
687 688 689 690 691
                m
            );
            return;
        }

692
        // if u or v is a machine register that is not usable/not a color, we cannot coalesce
qinsoon's avatar
qinsoon committed
693 694 695 696 697 698 699
        if precolored_u {
            let group = backend::pick_group_for_reg(u);
            if !self.colors.get(&group).unwrap().contains(&u) {
                if !precolored_v {
                    self.add_worklist(v);
                }
                self.constrained_moves.insert(m);
700
                trace!("  u is precolored but not a usable color, cannot coalesce");
701 702 703
                return;
            }
        }
qinsoon's avatar
qinsoon committed
704 705 706 707 708 709 710
        if precolored_v {
            let group = backend::pick_group_for_reg(v);
            if !self.colors.get(&group).unwrap().contains(&v) {
                if !precolored_u {
                    self.add_worklist(u);
                }
                self.constrained_moves.insert(m);
711
                trace!("  v is precolored but not a usable color, cannot coalesce");
712 713 714 715
                return;
            }
        }

qinsoon's avatar
qinsoon committed
716
        if u == v {
717
            trace!("  u == v, coalesce the move");
qinsoon's avatar
qinsoon committed
718 719 720 721
            self.coalesced_moves.insert(m);
            if !precolored_u {
                self.add_worklist(u);
            }
722
        } else if precolored_v || self.ig.is_in_adj_set(u, v) {
723 724 725
            trace!("  precolored_v: {}", precolored_v);
            trace!("  is_adj(u, v): {}", self.ig.is_in_adj_set(u, v));
            trace!("  v is precolored or u,v is adjacent, the move is constrained");
726
            self.constrained_moves.insert(m);
qinsoon's avatar
qinsoon committed
727 728 729 730 731 732
            if !precolored_u {
                self.add_worklist(u);
            }
            if !precolored_v {
                self.add_worklist(v);
            }
733 734 735
        } else if (precolored_u && self.check_ok(u, v)) ||
                   (!precolored_u && self.check_conservative(u, v))
        {
736 737
            trace!("  ok(u, v) = {}", self.check_ok(u, v));
            trace!("  conservative(u, v) = {}", self.check_conservative(u, v));
qinsoon's avatar
qinsoon committed
738

qinsoon's avatar
qinsoon committed
739
            trace!(
740
                "  precolored_u&&ok(u,v) || !precolored_u&&conserv(u,v), \
qinsoon's avatar
qinsoon committed
741 742
                 coalesce and combine the move"
            );
qinsoon's avatar
qinsoon committed
743 744 745 746 747 748
            self.coalesced_moves.insert(m);
            self.combine(u, v);
            if !precolored_u {
                self.add_worklist(u);
            }
        } else {
749 750
            trace!("  cannot coalesce the move");
            trace!("  insert {:?} to activeMoves", m);
qinsoon's avatar
qinsoon committed
751 752 753
            self.active_moves.insert(m);
        }
    }
qinsoon's avatar
qinsoon committed
754

755
    pub fn get_alias(&self, node: MuID) -> MuID {
qinsoon's avatar
qinsoon committed
756 757 758 759 760 761
        if self.coalesced_nodes.contains(&node) {
            self.get_alias(*self.alias.get(&node).unwrap())
        } else {
            node
        }
    }
qinsoon's avatar
qinsoon committed
762

763 764
    fn add_worklist(&mut self, node: MuID) {
        if !self.is_move_related(node) && self.ig.get_degree_of(node) < self.n_regs_for_node(node) {
765
            trace!("  move {} from worklistFreeze to worklistSimplify", node);
qinsoon's avatar
qinsoon committed
766 767 768 769
            self.worklist_freeze.remove(&node);
            self.worklist_simplify.insert(node);
        }
    }
qinsoon's avatar
qinsoon committed
770

771
    fn check_ok(&self, u: MuID, v: MuID) -> bool {
772 773
        for t in self.adjacent(v).iter() {
            let t = *t;
774
            if !self.ok(t, u) {
qinsoon's avatar
qinsoon committed
775
                return false;
776
            }
qinsoon's avatar
qinsoon committed
777
        }
qinsoon's avatar
qinsoon committed
778

qinsoon's avatar
qinsoon committed
779 780
        true
    }
qinsoon's avatar
qinsoon committed
781

782 783 784 785 786 787 788 789
    fn ok(&self, t: MuID, r: MuID) -> bool {
        let degree_t = self.ig.get_degree_of(t);
        let k = self.n_regs_for_node(t);

        degree_t < k || self.precolored.contains(&t) || self.ig.is_in_adj_set(t, r)
    }

    fn check_conservative(&self, u: MuID, v: MuID) -> bool {
qinsoon's avatar
qinsoon committed
790 791
        let adj_u = self.adjacent(u);
        let adj_v = self.adjacent(v);
792 793 794 795 796
        let nodes = {
            let mut ret = adj_u;
            ret.add_all(adj_v);
            ret
        };
qinsoon's avatar
qinsoon committed
797

798 799 800
        let n_regs_for_group = self.n_regs_for_node(u);
        self.conservative(nodes, n_regs_for_group)
    }
qinsoon's avatar
qinsoon committed
801

802
    fn conservative(&self, nodes: LinkedHashSet<MuID>, n_regs_for_group: usize) -> bool {
qinsoon's avatar
qinsoon committed
803
        let mut k = 0;
804
        for n in nodes.iter() {
805 806
            // TODO: do we check if n is precolored?
            if self.precolored.contains(n) || self.ig.get_degree_of(*n) >= n_regs_for_group {
qinsoon's avatar
qinsoon committed
807 808 809
                k += 1;
            }
        }
810
        k < n_regs_for_group
qinsoon's avatar
qinsoon committed
811
    }
qinsoon's avatar
qinsoon committed
812

813
    fn combine(&mut self, u: MuID, v: MuID) {
814
        trace!("  Combine temps {} and {}...", u, v);
qinsoon's avatar
qinsoon committed
815
        if self.worklist_freeze.contains(&v) {
816
            trace!("  remove {} from worklistFreeze", v);
qinsoon's avatar
qinsoon committed
817 818
            self.worklist_freeze.remove(&v);
        } else {
819
            trace!("  remove {} from worklistSpill", v);
qinsoon's avatar
qinsoon committed
820
            self.worklist_spill.remove(&v);
qinsoon's avatar
qinsoon committed
821
        }
qinsoon's avatar
qinsoon committed
822
        self.coalesced_nodes.insert(v);
qinsoon's avatar
qinsoon committed
823 824 825

        self.alias.insert(v, u);

qinsoon's avatar
qinsoon committed
826
        {
827 828
            // movelist[u] <- movelist[u] + movelist[v]
            let movelist_v = self.get_movelist(v);
qinsoon's avatar
qinsoon committed
829

830 831 832
            for m in movelist_v.iter() {
                GraphColoring::add_to_movelist(&mut self.movelist, u, *m)
            }
qinsoon's avatar
qinsoon committed
833
        }
qinsoon's avatar
qinsoon committed
834

835
        let mut nodes = LinkedHashSet::new();
qinsoon's avatar
qinsoon committed
836 837
        nodes.insert(v);
        self.enable_moves(nodes);
qinsoon's avatar
qinsoon committed
838

839 840
        for t in self.adjacent(v).iter() {
            let t = *t;
qinsoon's avatar
qinsoon committed
841 842 843
            self.add_edge(t, u);
            self.decrement_degree(t);
        }
qinsoon's avatar
qinsoon committed
844

845 846 847
        if self.worklist_freeze.contains(&u) &&
            self.ig.get_degree_of(u) >= self.n_regs_for_node(u)
        {
848
            trace!("  move {} from worklistFreeze to worklistSpill", u);
qinsoon's avatar
qinsoon committed
849
            self.worklist_freeze.remove(&u);
qinsoon's avatar
qinsoon committed
850
            self.worklist_spill.insert(u);
qinsoon's avatar
qinsoon committed
851 852
        }
    }
qinsoon's avatar
qinsoon committed
853

854
    fn add_edge(&mut self, u: MuID, v: MuID) {
qinsoon's avatar
qinsoon committed
855
        self.ig.add_edge(u, v);
856
    }
qinsoon's avatar
qinsoon committed
857

858
    fn freeze(&mut self) {
859
        // it is not empty (checked before)
860
        let node = self.freeze_heuristics();
861
        trace!("Freezing {}...", node);
qinsoon's avatar
qinsoon committed
862

863 864
        trace!("  move {} from worklistFreeze to worklistSimplify", node);
        self.worklist_freeze.remove(&node);
qinsoon's avatar
qinsoon committed
865 866 867
        self.worklist_simplify.insert(node);
        self.freeze_moves(node);
    }
qinsoon's avatar
qinsoon committed
868

869 870 871 872 873 874 875
    fn freeze_heuristics(&mut self) -> MuID {
        use std::f32;
        // we try to freeze a node that appears less frequently
        // we compute freeze cost based on all the moves related with this node
        let mut candidate = None;
        let mut candidate_cost = f32::MAX;
        for &n in self.worklist_freeze.iter() {
876
            let freeze_cost = self.ig.get_freeze_cost(n);
877 878 879 880 881 882 883 884 885 886 887

            if freeze_cost < candidate_cost {
                candidate = Some(n);
                candidate_cost = freeze_cost;
            }
        }

        assert!(candidate.is_some());
        candidate.unwrap()
    }

888
    fn freeze_moves(&mut self, u: MuID) {
889
        trace!("  freeze moves for {}", u);
890 891
        for m in self.node_moves(u).iter() {
            let m = *m;
892 893 894 895 896 897 898 899 900 901 902
            //            let mut v = self.get_alias(m.from);
            //            if v == self.get_alias(u) {
            //                v = self.get_alias(m.to);
            //            }
            let x = m.from;
            let y = m.to;
            let v = if self.get_alias(y) == self.get_alias(u) {
                self.get_alias(x)
            } else {
                self.get_alias(y)
            };
qinsoon's avatar
qinsoon committed
903

904
            trace!("  move {:?} from activeMoves to frozenMoves", m);
qinsoon's avatar
qinsoon committed
905 906
            self.active_moves.remove(&m);
            self.frozen_moves.insert(m);
qinsoon's avatar
qinsoon committed
907

908 909 910 911
            //            if !self.precolored.contains(&v) && self.node_moves(v).is_empty() &&
            //                self.ig.get_degree_of(v) < self.n_regs_for_node(v)
            if self.worklist_freeze.contains(&v) && self.node_moves(v).is_empty() {
                trace!("  move {} from worklistFreeze to worklistSimplify", v);
qinsoon's avatar
qinsoon committed
912 913 914 915
                self.worklist_freeze.remove(&v);
                self.worklist_simplify.insert(v);
            }
        }
916
    }
qinsoon's avatar
qinsoon committed
917

918
    fn select_spill(&mut self) {
919
        trace!("Selecting a node to spill...");
920
        let mut m: Option<MuID> = None;
qinsoon's avatar
qinsoon committed
921

922 923
        for n in self.worklist_spill.iter() {
            let n = *n;
924 925
            // if a node is not spillable, we guarantee that we do not spill it
            if !self.is_spillable(n) {
926
                trace!("  {} is not spillable", n);
927 928 929
                continue;
            }

930
            if m.is_none() {
931
                trace!("  {} is the initial choice", n);
932
                m = Some(n);
933 934
            } else {
                let cur_m = m.unwrap();
935 936 937
                let cost_m = self.ig.get_spill_cost(cur_m);
                let cost_n = self.ig.get_spill_cost(n);
                if cost_n < cost_m {
938
                    trace!("  {} is preferred: ({} < {})", n, cost_n, cost_m);
939 940
                    m = Some(n);
                }
941 942
            }
        }
qinsoon's avatar
qinsoon committed
943

944
        // m is not none
945
        assert!(m.is_some(), "failed to select any node to spill");
946
        let m = m.unwrap();
947 948
        trace!("  Spilling {}...", m);
        trace!("  move {:?} from worklistSpill to worklistSimplify", m);
qinsoon's avatar
qinsoon committed
949 950
        self.waiting_for_spill.insert(m);
        self.worklist_spill.remove(&m);
951 952
        self.worklist_simplify.insert(m);
        self.freeze_moves(m);
953
    }
qinsoon's avatar
qinsoon committed
954

955
    fn assign_colors(&mut self) {
956
        trace!("---coloring done---");
957 958 959 960

        let mut coloring_queue: Vec<MuID> = self.coloring_queue_heuristic();
        while !coloring_queue.is_empty() {
            let n = coloring_queue.pop().unwrap();
961
            trace!("Assigning color to {}", n);
qinsoon's avatar
qinsoon committed
962 963 964

            let mut ok_colors: LinkedHashSet<MuID> =
                self.colors.get(&self.ig.get_group_of(n)).unwrap().clone();
qinsoon's avatar
qinsoon committed
965

966
            trace!("  all the colors for this temp: {:?}", ok_colors);
qinsoon's avatar
qinsoon committed
967

968 969
            for w in self.ig.get_adj_list(n).iter() {
                let w_alias = self.get_alias(*w);
qinsoon's avatar
qinsoon committed
970
                match self.ig.get_color_of(w_alias) {
qinsoon's avatar
qinsoon committed
971
                    None => {} // do nothing
qinsoon's avatar
qinsoon committed
972
                    Some(color) => {
qinsoon's avatar
qinsoon committed
973
                        trace!(
974
                            "  color {} is used for its neighbor {:?} (aliasing to {:?})",
qinsoon's avatar
qinsoon committed
975
                            color,
976 977
                            w,
                            w_alias
qinsoon's avatar
qinsoon committed
978
                        );
qinsoon's avatar
qinsoon committed
979 980
                        ok_colors.remove(&color);
                    }
981 982
                }
            }
983
            trace!("  available colors: {:?}", ok_colors);
qinsoon's avatar
qinsoon committed
984

985
            if ok_colors.is_empty() {
986
                trace!("  {} is a spilled node", n);
qinsoon's avatar
qinsoon committed
987
                self.spilled_nodes.insert(n);
988
            } else {
989
                let color = self.color_heuristic(n, &mut ok_colors);
990
                trace!("  Color {} as {}", n, color);
qinsoon's avatar
qinsoon committed
991

qinsoon's avatar
qinsoon committed
992
                self.colored_nodes.insert(n);
993
                self.ig.color_node(n, color);
994 995
            }
        }
qinsoon's avatar
qinsoon committed
996

qinsoon's avatar
qinsoon committed
997
        for n in self.coalesced_nodes.iter() {
998 999
            let n = *n;
            let alias = self.get_alias(n);
qinsoon's avatar
qinsoon committed
1000
            if let Some(alias_color) = self.ig.get_color_of(alias) {
1001 1002
                trace!("  Assign color to {} based on aliased {}", n, alias);
                trace!("  Color {} as {}", n, alias_color);
qinsoon's avatar
qinsoon committed
1003 1004
                self.ig.color_node(n, alias_color);
            }
1005 1006
        }
    }
qinsoon's avatar
qinsoon committed
1007

1008 1009 1010 1011 1012 1013 1014 1015 1016 1017 1018 1019 1020 1021
    //    /// we pick colors for node that has higher weight (higher spill cost)
    //    fn coloring_queue_heuristic(&self) -> Vec<MuID> {
    //        let mut ret = self.select_stack.clone();
    //        ret.sort_by_key(|x| self.ig.get_spill_cost(*x));
    //        ret.reverse();
    //        ret
    //    }

    fn coloring_queue_heuristic(&self) -> Vec<MuID> {
        self.select_stack.clone()
    }

    /// we favor choosing colors that will make any frozen moves able to be eliminated
    fn color_heuristic(&self, reg: MuID, available_colors: &mut LinkedHashSet<MuID>) -> MuID {
1022
        trace!("  Find color for {} in {:?}", reg, available_colors);
1023 1024 1025 1026 1027 1028 1029 1030 1031 1032 1033 1034 1035 1036 1037 1038 1039 1040 1041 1042 1043 1044 1045

        // we use spill cost as weight.
        // A node that has higher spill cost is used more frequently, and has a higher weight
        // we favor choosing color that has a higher weight
        let mut candidate_weight: LinkedHashMap<MuID, f32> = LinkedHashMap::new();

        for mov in self.frozen_moves.iter() {
            // find the other part of the mov
            let other = if mov.from == reg { mov.to } else { mov.from };
            let alias = self.get_alias(other);
            let other_color = self.ig.get_color_of(alias);
            let other_weight = self.ig.get_spill_cost(alias);
            // if the other part is colored and that color is available,
            // we will favor the choice of the color
            if let Some(other_color) = other_color {
                if available_colors.contains(&other_color) {
                    let total_weight = if candidate_weight.contains_key(&other_color) {
                        candidate_weight.get(&other_color).unwrap() + other_weight
                    } else {
                        other_weight
                    };
                    candidate_weight.insert(other_color, total_weight);
                    trace!(
1046
                        "    favor {} to eliminate {:?} (weight={})",
1047 1048 1049 1050 1051 1052 1053 1054 1055
                        other_color,
                        mov,
                        total_weight
                    );
                }
            }
        }

        if candidate_weight.is_empty() {
1056
            trace!("    no candidate, use first avaiable color");
1057 1058 1059 1060 1061 1062 1063 1064 1065 1066 1067
            available_colors.pop_front().unwrap()
        } else {
            let mut c = None;
            let mut c_weight = 0f32;
            for (&id, &weight) in candidate_weight.iter() {
                if c.is_none() || (c.is_some() && c_weight < weight) {
                    c = Some(id);
                    c_weight = weight;
                }
            }
            assert!(c.is_some());
1068 1069 1070 1071
            let color = c.unwrap();
            assert!(available_colors.contains(&color));
            trace!("    pick candidate of most weight: {}", color);
            color
1072 1073 1074
        }
    }

qinsoon's avatar
qinsoon committed
1075
    fn rewrite_program(&mut self) {
qinsoon's avatar
qinsoon committed
1076 1077
        let spills = self.spills();

1078
        let mut spilled_mem = LinkedHashMap::new();
qinsoon's avatar
qinsoon committed
1079 1080 1081

        // allocating frame slots for every spilled temp
        for reg_id in spills.iter() {
qinsoon's avatar
qinsoon committed
1082
            let ssa_entry = match self.func.context.get_value(*reg_id) {
qinsoon's avatar
qinsoon committed
1083
                Some(entry) => entry,
1084
                None => panic!("The spilled register {} is not in func context", reg_id)
qinsoon's avatar
qinsoon committed
1085
            };
qinsoon's avatar
qinsoon committed
1086 1087 1088
            let mem = self.cf
                .frame
                .alloc_slot_for_spilling(ssa_entry.value().clone(), self.vm);
qinsoon's avatar
qinsoon committed
1089

qinsoon's avatar
qinsoon committed
1090 1091
            spilled_mem.insert(*reg_id, mem.clone());
            self.spill_history.insert(*reg_id, mem);
qinsoon's avatar
qinsoon committed
1092 1093
        }

qinsoon's avatar
qinsoon committed
1094 1095 1096 1097
        let scratch_temps = backend::spill_rewrite(&spilled_mem, self.func, self.cf, self.vm);
        for (k, v) in scratch_temps {
            self.spill_scratch_temps.insert(k, v);
        }
qinsoon's avatar
qinsoon committed
1098
    }
qinsoon's avatar
qinsoon committed
1099

1100 1101
    pub fn spills(&self) -> Vec<MuID> {
        let mut spills = vec![];
qinsoon's avatar
qinsoon committed
1102

1103 1104 1105 1106 1107 1108
        let spill_count = self.spilled_nodes.len();
        if spill_count > 0 {
            for n in self.spilled_nodes.iter() {
                spills.push(self.ig.get_temp_of(*n));
            }
        }
qinsoon's avatar
qinsoon committed
1109

1110
        spills
1111
    }
1112 1113 1114 1115 1116 1117 1118 1119 1120 1121 1122 1123 1124

    pub fn get_assignments(&self) -> LinkedHashMap<MuID, MuID> {
        let mut ret = LinkedHashMap::new();

        for node in self.ig.nodes() {
            let temp = self.ig.get_temp_of(node);

            if temp < MACHINE_ID_END {
                continue;
            } else {
                let alias = self.get_alias(node);
                let machine_reg = match self.ig.get_color_of(alias) {
                    Some(reg) => reg,
qinsoon's avatar
qinsoon committed
1125 1126 1127 1128 1129 1130 1131 1132 1133
                    None => {
                        panic!(
                            "Reg{}/{:?} (aliased as Reg{}/{:?}) is not assigned with a color",
                            self.ig.get_temp_of(node),
                            node,
                            self.ig.get_temp_of(alias),
                            alias
                        )
                    }
1134 1135 1136 1137 1138
                };

                ret.insert(temp, machine_reg);
            }
        }
qinsoon's avatar
qinsoon committed
1139

1140 1141 1142
        ret
    }

qinsoon's avatar
qinsoon committed
1143 1144 1145
    pub fn get_spill_scratch_temps(&self) -> LinkedHashMap<MuID, MuID> {
        self.spill_scratch_temps.clone()
    }
1146
}