coloring.rs 28.8 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

25
use utils::vec_utils;
26
use utils::LinkedHashSet;
27
use utils::LinkedHashMap;
28

qinsoon's avatar
qinsoon committed
29
use std::cell::RefCell;
30

31 32 33
use compiler::backend::reg_alloc::graph_coloring::liveness::Move;
use compiler::backend::reg_alloc::graph_coloring::petgraph::graph::NodeIndex;

qinsoon's avatar
qinsoon committed
34 35
const COALESCING: bool = true;
const MAX_REWRITE_ITERATIONS_ALLOWED: usize = 10;
36

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

46 47 48 49
    /// 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
50
    /// machine registers, preassigned a color
51
    precolored: LinkedHashSet<NodeIndex>,
qinsoon's avatar
qinsoon committed
52
    /// all colors available
53
    colors: LinkedHashMap<backend::RegGroup, LinkedHashSet<MuID>>,
qinsoon's avatar
qinsoon committed
54
    /// temporaries, not precolored and not yet processed
55
    initial: Vec<NodeIndex>,
qinsoon's avatar
qinsoon committed
56 57 58 59 60 61 62 63 64 65 66

    /// list of low-degree non-move-related nodes
    worklist_simplify: LinkedHashSet<NodeIndex>,
    /// low-degree move related nodes
    worklist_freeze: LinkedHashSet<NodeIndex>,
    /// nodes marked for spilling during this round
    worklist_spill: Vec<NodeIndex>,
    /// nodes marked for spilling during this round
    spilled_nodes: Vec<NodeIndex>,
    /// temps that have been coalesced
    /// when u <- v is coalesced, v is added to this set and u put back on some work list
67
    coalesced_nodes: LinkedHashSet<NodeIndex>,
qinsoon's avatar
qinsoon committed
68 69 70 71 72 73
    /// nodes successfully colored
    colored_nodes: Vec<NodeIndex>,
    /// stack containing temporaries removed from the graph
    select_stack: Vec<NodeIndex>,

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

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

qinsoon's avatar
qinsoon committed
91 92 93 94
    // 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
95
    spill_scratch_temps: LinkedHashMap<MuID, MuID>
qinsoon's avatar
qinsoon committed
96 97
}

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

qinsoon's avatar
qinsoon committed
115
    /// restarts coloring with spill history
qinsoon's avatar
qinsoon committed
116 117 118 119 120 121
    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,
122
        vm: &'a VM
qinsoon's avatar
qinsoon committed
123 124 125
    ) -> GraphColoring<'a> {
        assert!(
            iteration_count < MAX_REWRITE_ITERATIONS_ALLOWED,
126
            "reach graph coloring max rewrite iterations ({}), probably something is going wrong",
qinsoon's avatar
qinsoon committed
127 128
            MAX_REWRITE_ITERATIONS_ALLOWED
        );
129 130
        let iteration_count = iteration_count + 1;

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

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

136
        let coloring = GraphColoring {
qinsoon's avatar
qinsoon committed
137 138 139 140
            func: func,
            cf: cf,
            vm: vm,
            ig: ig,
141
            iteration_count: iteration_count,
142
            precolored: LinkedHashSet::new(),
143
            colors: {
144
                let mut map = LinkedHashMap::new();
145 146
                map.insert(backend::RegGroup::GPR, LinkedHashSet::new());
                map.insert(backend::RegGroup::FPR, LinkedHashSet::new());
147 148 149
                map
            },
            colored_nodes: Vec::new(),
150
            initial: Vec::new(),
151
            degree: LinkedHashMap::new(),
152
            worklist_moves: Vec::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(),
159
            worklist_spill: Vec::new(),
160
            spilled_nodes: Vec::new(),
qinsoon's avatar
qinsoon committed
161
            spill_history: spill_history,
qinsoon's avatar
qinsoon committed
162
            spill_scratch_temps: spill_scratch_temps,
163 164 165
            worklist_freeze: LinkedHashSet::new(),
            frozen_moves: LinkedHashSet::new(),
            worklist_simplify: LinkedHashSet::new(),
166
            select_stack: Vec::new()
qinsoon's avatar
qinsoon committed
167
        };
qinsoon's avatar
qinsoon committed
168

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

qinsoon's avatar
qinsoon committed
172
    /// returns formatted string for a node
173
    fn display_node(&self, node: NodeIndex) -> String {
qinsoon's avatar
qinsoon committed
174 175 176 177
        let id = self.ig.get_temp_of(node);
        self.display_id(id)
    }

qinsoon's avatar
qinsoon committed
178
    /// returns formatted string for an ID
qinsoon's avatar
qinsoon committed
179 180 181 182
    fn display_id(&self, id: MuID) -> String {
        self.func.context.get_temp_display(id)
    }

qinsoon's avatar
qinsoon committed
183
    /// returns formatted string for a move
qinsoon's avatar
qinsoon committed
184
    fn display_move(&self, m: Move) -> String {
qinsoon's avatar
qinsoon committed
185 186 187 188 189
        format!(
            "Move: {} -> {}",
            self.display_node(m.from),
            self.display_node(m.to)
        )
qinsoon's avatar
qinsoon committed
190
    }
qinsoon's avatar
qinsoon committed
191 192

    /// does coloring register allocation
193
    fn regalloc(mut self) -> GraphColoring<'a> {
194
        trace!("---InterenceGraph---");
qinsoon's avatar
qinsoon committed
195
        self.ig.print(&self.func.context);
qinsoon's avatar
qinsoon committed
196 197 198

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

qinsoon's avatar
qinsoon committed
200
        // precolor for all machine registers
201
        for reg in backend::all_regs().values() {
202 203 204 205
            let reg_id = reg.extract_ssa_id().unwrap();
            let node = self.ig.get_node(reg_id);
            self.precolored.insert(node);
        }
qinsoon's avatar
qinsoon committed
206

qinsoon's avatar
qinsoon committed
207
        // put usable registers as available colors
208
        for reg in backend::all_usable_regs().iter() {
209
            let reg_id = reg.extract_ssa_id().unwrap();
qinsoon's avatar
qinsoon committed
210 211
            let group = backend::pick_group_for_reg(reg_id);
            self.colors.get_mut(&group).unwrap().insert(reg_id);
212
        }
qinsoon's avatar
qinsoon committed
213 214

        // push uncolored nodes to initial work set
215 216
        for node in self.ig.nodes() {
            if !self.ig.is_colored(node) {
217
                self.initial.push(node);
qinsoon's avatar
qinsoon committed
218 219 220
                let degree = self.ig.get_degree_of(node);
                self.degree.insert(node, degree);
                trace!("{} has a degree of {}", self.display_node(node), degree);
221 222
            }
        }
qinsoon's avatar
qinsoon committed
223 224

        // initialize work
225 226
        self.build();
        self.make_work_list();
qinsoon's avatar
qinsoon committed
227 228

        // main loop
229 230 231 232 233 234 235 236 237 238
        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
239 240 241

            !(self.worklist_simplify.is_empty() && self.worklist_moves.is_empty() &&
                  self.worklist_freeze.is_empty() && self.worklist_spill.is_empty())
242
        } {}
qinsoon's avatar
qinsoon committed
243 244

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

qinsoon's avatar
qinsoon committed
247
        // finish
248 249
        drop(_p);

qinsoon's avatar
qinsoon committed
250
        // if we need to spill
qinsoon's avatar
qinsoon committed
251 252
        if !self.spilled_nodes.is_empty() {
            trace!("spill required");
253 254 255
            if cfg!(debug_assertions) {
                trace!("nodes to be spilled:");
                for node in self.spilled_nodes.iter() {
qinsoon's avatar
qinsoon committed
256
                    trace!("{}", self.display_node(*node));
257 258 259
                }
            }

qinsoon's avatar
qinsoon committed
260
            // rewrite program to insert spilling code
qinsoon's avatar
qinsoon committed
261
            self.rewrite_program();
qinsoon's avatar
qinsoon committed
262

qinsoon's avatar
qinsoon committed
263
            // recursively redo graph coloring
qinsoon's avatar
qinsoon committed
264 265 266 267 268 269
            return GraphColoring::start_with_spill_history(
                self.spill_history.clone(),
                self.spill_scratch_temps.clone(),
                self.iteration_count,
                self.func,
                self.cf,
270
                self.vm
qinsoon's avatar
qinsoon committed
271
            );
qinsoon's avatar
qinsoon committed
272 273
        }

274
        self
275
    }
qinsoon's avatar
qinsoon committed
276

277
    fn build(&mut self) {
278 279
        if COALESCING {
            trace!("coalescing enabled, build move list");
280 281
            let ref ig = self.ig;
            let ref mut movelist = self.movelist;
282
            for m in ig.moves().iter() {
qinsoon's avatar
qinsoon committed
283
                trace!("add to movelist: {:?}", m);
284
                self.worklist_moves.push(m.clone());
qinsoon's avatar
qinsoon committed
285 286 287 288 289 290
                GraphColoring::movelist_mut(movelist, m.from)
                    .borrow_mut()
                    .push(m.clone());
                GraphColoring::movelist_mut(movelist, m.to)
                    .borrow_mut()
                    .push(m.clone());
291
            }
292 293
        } else {
            trace!("coalescing disabled");
294 295
        }
    }
qinsoon's avatar
qinsoon committed
296

297
    fn make_work_list(&mut self) {
298
        trace!("Making work list from initials...");
299
        while !self.initial.is_empty() {
300
            let node = self.initial.pop().unwrap();
qinsoon's avatar
qinsoon committed
301

302 303
            if {
                // condition: degree >= K
qinsoon's avatar
qinsoon committed
304
                let degree = self.ig.get_degree_of(node);
305
                let n_regs = self.n_regs_for_node(node);
qinsoon's avatar
qinsoon committed
306

307 308
                degree >= n_regs
            } {
qinsoon's avatar
qinsoon committed
309 310 311 312
                trace!(
                    "{} 's degree >= reg number limit (K), push to spill list",
                    self.display_node(node)
                );
313
                self.worklist_spill.push(node);
314
            } else if self.is_move_related(node) {
qinsoon's avatar
qinsoon committed
315 316 317 318
                trace!(
                    "{} is move related, push to freeze list",
                    self.display_node(node)
                );
319 320
                self.worklist_freeze.insert(node);
            } else {
qinsoon's avatar
qinsoon committed
321 322 323 324
                trace!(
                    "{} has small degree and not move related, push to simplify list",
                    self.display_node(node)
                );
325 326 327 328
                self.worklist_simplify.insert(node);
            }
        }
    }
qinsoon's avatar
qinsoon committed
329

330
    fn n_regs_for_node(&self, node: NodeIndex) -> usize {
331
        backend::number_of_usable_regs_in_group(self.ig.get_group_of(node))
332
    }
qinsoon's avatar
qinsoon committed
333

334
    fn is_move_related(&mut self, node: NodeIndex) -> bool {
335 336
        !self.node_moves(node).is_empty()
    }
337 338 339 340 341 342 343 344 345 346

    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
347

348
    fn node_moves(&mut self, node: NodeIndex) -> LinkedHashSet<Move> {
349
        let mut moves = LinkedHashSet::new();
qinsoon's avatar
qinsoon committed
350

351 352 353 354
        // addAll(active_moves)
        for m in self.active_moves.iter() {
            moves.insert(m.clone());
        }
qinsoon's avatar
qinsoon committed
355

356 357 358 359
        // addAll(worklist_moves)
        for m in self.worklist_moves.iter() {
            moves.insert(m.clone());
        }
qinsoon's avatar
qinsoon committed
360

361
        let mut retained = LinkedHashSet::new();
qinsoon's avatar
qinsoon committed
362
        let movelist = &GraphColoring::movelist_mut(&mut self.movelist, node).borrow();
363
        for m in moves.iter() {
364
            if vec_utils::find_value(movelist, *m).is_some() {
365 366 367
                retained.insert(*m);
            }
        }
qinsoon's avatar
qinsoon committed
368

369 370
        retained
    }
qinsoon's avatar
qinsoon committed
371

qinsoon's avatar
qinsoon committed
372 373 374
    // avoid using &mut self as argument
    // in build(), we will need to mutate on self.movelist while
    // holding an immmutable reference of self(self.ig)
qinsoon's avatar
qinsoon committed
375 376
    fn movelist_mut(
        list: &mut LinkedHashMap<NodeIndex, RefCell<Vec<Move>>>,
377
        node: NodeIndex
qinsoon's avatar
qinsoon committed
378
    ) -> &RefCell<Vec<Move>> {
qinsoon's avatar
qinsoon committed
379
        GraphColoring::movelist_check(list, node);
qinsoon's avatar
qinsoon committed
380
        unsafe { GraphColoring::movelist_nocheck(list, node) }
qinsoon's avatar
qinsoon committed
381
    }
qinsoon's avatar
qinsoon committed
382

383
    fn movelist_check(list: &mut LinkedHashMap<NodeIndex, RefCell<Vec<Move>>>, node: NodeIndex) {
384
        if !list.contains_key(&node) {
qinsoon's avatar
qinsoon committed
385
            list.insert(node, RefCell::new(Vec::new()));
386
        }
qinsoon's avatar
qinsoon committed
387
    }
qinsoon's avatar
qinsoon committed
388

qinsoon's avatar
qinsoon committed
389
    // allows getting the Vec<Move> without a mutable reference of the hashmap
qinsoon's avatar
qinsoon committed
390 391
    unsafe fn movelist_nocheck(
        list: &LinkedHashMap<NodeIndex, RefCell<Vec<Move>>>,
392
        node: NodeIndex
qinsoon's avatar
qinsoon committed
393
    ) -> &RefCell<Vec<Move>> {
qinsoon's avatar
qinsoon committed
394
        list.get(&node).unwrap()
qinsoon's avatar
qinsoon committed
395
    }
qinsoon's avatar
qinsoon committed
396

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

qinsoon's avatar
qinsoon committed
401
        trace!("Simplifying {}", self.display_node(node));
qinsoon's avatar
qinsoon committed
402

403
        self.select_stack.push(node);
404
        for m in self.adjacent(node).iter() {
405
            self.decrement_degree(*m);
406 407
        }
    }
qinsoon's avatar
qinsoon committed
408

409
    fn adjacent(&self, n: NodeIndex) -> LinkedHashSet<NodeIndex> {
410
        let mut adj = LinkedHashSet::new();
qinsoon's avatar
qinsoon committed
411

412
        // add n's successors
qinsoon's avatar
qinsoon committed
413
        for s in self.ig.get_edges_of(n) {
414 415
            adj.insert(s);
        }
qinsoon's avatar
qinsoon committed
416

417 418 419 420
        // removeAll(select_stack)
        for s in self.select_stack.iter() {
            adj.remove(s);
        }
qinsoon's avatar
qinsoon committed
421

422 423 424 425
        // removeAll(coalesced_nodes)
        for s in self.coalesced_nodes.iter() {
            adj.remove(s);
        }
qinsoon's avatar
qinsoon committed
426

427 428
        adj
    }
qinsoon's avatar
qinsoon committed
429

430
    fn degree(&self, n: NodeIndex) -> usize {
431 432
        match self.degree.get(&n) {
            Some(d) => *d,
433
            None => 0
434 435
        }
    }
qinsoon's avatar
qinsoon committed
436

437
    fn decrement_degree(&mut self, n: NodeIndex) {
438 439 440
        if self.precolored.contains(&n) {
            return;
        }
qinsoon's avatar
qinsoon committed
441

qinsoon's avatar
qinsoon committed
442
        trace!("decrement degree of {}", self.display_node(n));
qinsoon's avatar
qinsoon committed
443

444
        let d = self.degree(n);
445
        debug_assert!(d != 0);
446
        self.degree.insert(n, d - 1);
qinsoon's avatar
qinsoon committed
447

448
        if d == self.n_regs_for_node(n) {
qinsoon's avatar
qinsoon committed
449 450 451 452
            trace!(
                "{}'s degree is K, no longer need to spill it",
                self.display_node(n)
            );
453 454
            let mut nodes = self.adjacent(n);
            nodes.insert(n);
455
            trace!("enable moves of {:?}", nodes);
456
            self.enable_moves(nodes);
qinsoon's avatar
qinsoon committed
457

458
            vec_utils::remove_value(&mut self.worklist_spill, n);
qinsoon's avatar
qinsoon committed
459

460
            if self.is_move_related(n) {
qinsoon's avatar
qinsoon committed
461 462 463 464
                trace!(
                    "{} is move related, push to freeze list",
                    self.display_node(n)
                );
465 466
                self.worklist_freeze.insert(n);
            } else {
qinsoon's avatar
qinsoon committed
467 468 469 470
                trace!(
                    "{} is not move related, push to simplify list",
                    self.display_node(n)
                );
471 472 473 474
                self.worklist_simplify.insert(n);
            }
        }
    }
qinsoon's avatar
qinsoon committed
475

476
    fn enable_moves(&mut self, nodes: LinkedHashSet<NodeIndex>) {
477 478 479 480
        for n in nodes.iter() {
            let n = *n;
            for mov in self.node_moves(n).iter() {
                let mov = *mov;
481 482 483 484 485 486 487
                if self.active_moves.contains(&mov) {
                    self.active_moves.insert(mov);
                    self.worklist_moves.push(mov);
                }
            }
        }
    }
qinsoon's avatar
qinsoon committed
488

489
    fn coalesce(&mut self) {
qinsoon's avatar
qinsoon committed
490
        let m = self.worklist_moves.pop().unwrap();
qinsoon's avatar
qinsoon committed
491

qinsoon's avatar
qinsoon committed
492
        trace!("Coalescing on {}", self.display_move(m));
qinsoon's avatar
qinsoon committed
493 494 495

        // if they are not from the same register group, we cannot coalesce them
        if self.ig.get_group_of(m.from) != self.ig.get_group_of(m.to) {
496
            info!("a move instruction of two temporaries of different register groups");
qinsoon's avatar
qinsoon committed
497 498
            info!("from: {:?}, to: {:?}", m.from, m.to);

qinsoon's avatar
qinsoon committed
499 500
            return;
        }
qinsoon's avatar
qinsoon committed
501

qinsoon's avatar
qinsoon committed
502 503
        let x = self.get_alias(m.from);
        let y = self.get_alias(m.to);
qinsoon's avatar
qinsoon committed
504 505 506 507 508 509
        trace!(
            "resolve alias: from {} to {}",
            self.display_node(x),
            self.display_node(y)
        );

qinsoon's avatar
qinsoon committed
510 511 512 513 514 515
        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
516

qinsoon's avatar
qinsoon committed
517 518 519 520 521 522
                (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
523

qinsoon's avatar
qinsoon committed
524 525 526
                (u, v, precolored_u, precolored_v)
            }
        };
qinsoon's avatar
qinsoon committed
527 528
        trace!(
            "u={}, v={}, precolored_u={}, precolroed_v={}",
qinsoon's avatar
qinsoon committed
529 530
            self.display_node(u),
            self.display_node(v),
qinsoon's avatar
qinsoon committed
531 532 533 534
            precolored_u,
            precolored_v
        );

535 536 537 538 539 540 541 542 543 544 545 546 547 548 549 550
        // if u or v is a machine register that is not usable/not a color, we cannot coalesce
        if self.precolored.contains(&u) {
            let reg_u = self.ig.get_temp_of(u);
            let group = backend::pick_group_for_reg(reg_u);
            if !self.colors.get(&group).unwrap().contains(&reg_u) {
                return;
            }
        }
        if self.precolored.contains(&v) {
            let reg_v = self.ig.get_temp_of(v);
            let group = backend::pick_group_for_reg(reg_v);
            if !self.colors.get(&group).unwrap().contains(&reg_v) {
                return;
            }
        }

qinsoon's avatar
qinsoon committed
551
        if u == v {
552
            trace!("u == v, coalesce the move");
qinsoon's avatar
qinsoon committed
553 554 555 556 557
            self.coalesced_moves.insert(m);
            if !precolored_u {
                self.add_worklist(u);
            }
        } else if precolored_v || self.ig.is_adj(u, v) {
558 559
            trace!("precolored_v: {}", precolored_v);
            trace!("is_adj(u, v): {}", self.ig.is_adj(u, v));
560 561
            trace!("v is precolored or u,v is adjacent, the move is constrained");
            self.constrained_moves.insert(m);
qinsoon's avatar
qinsoon committed
562 563 564 565 566 567
            if !precolored_u {
                self.add_worklist(u);
            }
            if !precolored_v {
                self.add_worklist(v);
            }
qinsoon's avatar
qinsoon committed
568
        } else if (precolored_u && self.ok(u, v)) || (!precolored_u && self.conservative(u, v)) {
qinsoon's avatar
qinsoon committed
569 570 571
            trace!("ok(u, v) = {}", self.ok(u, v));
            trace!("conservative(u, v) = {}", self.conservative(u, v));

qinsoon's avatar
qinsoon committed
572 573 574 575
            trace!(
                "precolored_u&&ok(u,v) || !precolored_u&&conserv(u,v), \
                 coalesce and combine the move"
            );
qinsoon's avatar
qinsoon committed
576 577 578 579 580 581
            self.coalesced_moves.insert(m);
            self.combine(u, v);
            if !precolored_u {
                self.add_worklist(u);
            }
        } else {
582
            trace!("cannot coalesce the move");
qinsoon's avatar
qinsoon committed
583 584 585
            self.active_moves.insert(m);
        }
    }
qinsoon's avatar
qinsoon committed
586

587
    pub fn get_alias(&self, node: NodeIndex) -> NodeIndex {
qinsoon's avatar
qinsoon committed
588 589 590 591 592 593
        if self.coalesced_nodes.contains(&node) {
            self.get_alias(*self.alias.get(&node).unwrap())
        } else {
            node
        }
    }
qinsoon's avatar
qinsoon committed
594

595
    fn add_worklist(&mut self, node: NodeIndex) {
596
        if !self.is_move_related(node) && self.degree(node) < self.n_regs_for_node(node) {
qinsoon's avatar
qinsoon committed
597 598 599 600
            self.worklist_freeze.remove(&node);
            self.worklist_simplify.insert(node);
        }
    }
qinsoon's avatar
qinsoon committed
601

602
    fn ok(&self, u: NodeIndex, v: NodeIndex) -> bool {
603 604
        for t in self.adjacent(v).iter() {
            let t = *t;
qinsoon's avatar
qinsoon committed
605 606 607
            if !(self.degree(t) < self.n_regs_for_node(t) || self.precolored.contains(&t) ||
                     self.ig.is_adj(t, u))
            {
qinsoon's avatar
qinsoon committed
608
                return false;
609
            }
qinsoon's avatar
qinsoon committed
610
        }
qinsoon's avatar
qinsoon committed
611

qinsoon's avatar
qinsoon committed
612 613
        true
    }
qinsoon's avatar
qinsoon committed
614

615
    fn conservative(&self, u: NodeIndex, v: NodeIndex) -> bool {
qinsoon's avatar
qinsoon committed
616 617
        let adj_u = self.adjacent(u);
        let adj_v = self.adjacent(v);
618 619 620 621 622
        let nodes = {
            let mut ret = adj_u;
            ret.add_all(adj_v);
            ret
        };
qinsoon's avatar
qinsoon committed
623

qinsoon's avatar
qinsoon committed
624
        let mut k = 0;
625
        for n in nodes.iter() {
qinsoon's avatar
qinsoon committed
626
            if self.precolored.contains(n) || self.degree(*n) >= self.n_regs_for_node(*n) {
qinsoon's avatar
qinsoon committed
627 628 629
                k += 1;
            }
        }
qinsoon's avatar
qinsoon committed
630

qinsoon's avatar
qinsoon committed
631
        k < self.n_regs_for_node(u) && k < self.n_regs_for_node(v)
qinsoon's avatar
qinsoon committed
632
    }
qinsoon's avatar
qinsoon committed
633

634
    fn combine(&mut self, u: NodeIndex, v: NodeIndex) {
qinsoon's avatar
qinsoon committed
635 636 637 638 639 640 641
        if self.worklist_freeze.contains(&v) {
            self.worklist_freeze.remove(&v);
            self.coalesced_nodes.insert(v);
        } else {
            vec_utils::remove_value(&mut self.worklist_spill, v);
            self.coalesced_nodes.insert(v);
        }
qinsoon's avatar
qinsoon committed
642 643 644

        self.alias.insert(v, u);

qinsoon's avatar
qinsoon committed
645 646 647 648 649 650 651
        {
            let ref mut movelist = self.movelist;
            GraphColoring::movelist_check(movelist, u);
            GraphColoring::movelist_check(movelist, v);
            // we checked before getting the movelist, its safe
            // use nocheck version which requires only immutable references of movelist
            // avoid maintaining a mutable reference of movelist alive
qinsoon's avatar
qinsoon committed
652 653 654 655 656
            let movelist_u =
                &mut unsafe { GraphColoring::movelist_nocheck(movelist, u) }.borrow_mut();
            let movelist_v =
                &mut unsafe { GraphColoring::movelist_nocheck(movelist, v) }.borrow_mut();

qinsoon's avatar
qinsoon committed
657 658 659
            // addAll()
            movelist_u.extend_from_slice(movelist_v.as_slice());
        }
qinsoon's avatar
qinsoon committed
660

661
        let mut nodes = LinkedHashSet::new();
qinsoon's avatar
qinsoon committed
662 663
        nodes.insert(v);
        self.enable_moves(nodes);
qinsoon's avatar
qinsoon committed
664

665 666
        for t in self.adjacent(v).iter() {
            let t = *t;
qinsoon's avatar
qinsoon committed
667 668 669
            self.add_edge(t, u);
            self.decrement_degree(t);
        }
qinsoon's avatar
qinsoon committed
670 671

        if self.worklist_freeze.contains(&u) && self.degree(u) >= self.n_regs_for_node(u) {
qinsoon's avatar
qinsoon committed
672 673 674 675
            self.worklist_freeze.remove(&u);
            self.worklist_spill.push(u);
        }
    }
qinsoon's avatar
qinsoon committed
676

677
    fn add_edge(&mut self, u: NodeIndex, v: NodeIndex) {
qinsoon's avatar
qinsoon committed
678 679 680 681 682 683 684 685 686 687 688 689
        if u != v && !self.ig.is_adj(u, v) {
            if !self.precolored.contains(&u) {
                self.ig.add_interference_edge(u, v);
                let degree_u = self.degree(u);
                self.degree.insert(u, degree_u + 1);
            }
            if !self.precolored.contains(&v) {
                self.ig.add_interference_edge(v, u);
                let degree_v = self.degree(v);
                self.degree.insert(v, degree_v + 1);
            }
        }
690
    }
qinsoon's avatar
qinsoon committed
691

692
    fn freeze(&mut self) {
693
        // it is not empty (checked before)
694
        let node = self.worklist_freeze.pop_front().unwrap();
qinsoon's avatar
qinsoon committed
695
        trace!("Freezing {}...", self.display_node(node));
qinsoon's avatar
qinsoon committed
696

qinsoon's avatar
qinsoon committed
697 698 699
        self.worklist_simplify.insert(node);
        self.freeze_moves(node);
    }
qinsoon's avatar
qinsoon committed
700

701
    fn freeze_moves(&mut self, u: NodeIndex) {
702 703
        for m in self.node_moves(u).iter() {
            let m = *m;
qinsoon's avatar
qinsoon committed
704 705 706 707
            let mut v = self.get_alias(m.from);
            if v == self.get_alias(u) {
                v = self.get_alias(m.to);
            }
qinsoon's avatar
qinsoon committed
708

qinsoon's avatar
qinsoon committed
709 710
            self.active_moves.remove(&m);
            self.frozen_moves.insert(m);
qinsoon's avatar
qinsoon committed
711 712 713 714

            if !self.precolored.contains(&v) && self.node_moves(v).is_empty() &&
                self.degree(v) < self.n_regs_for_node(v)
            {
qinsoon's avatar
qinsoon committed
715 716 717 718
                self.worklist_freeze.remove(&v);
                self.worklist_simplify.insert(v);
            }
        }
719
    }
qinsoon's avatar
qinsoon committed
720

721
    fn select_spill(&mut self) {
722
        trace!("Selecting a node to spill...");
qinsoon's avatar
qinsoon committed
723 724
        let mut m: Option<NodeIndex> = None;

725 726 727 728 729
        for n in self.worklist_spill.iter() {
            let n = *n;
            if m.is_none() {
                m = Some(n);
            } else if {
qinsoon's avatar
qinsoon committed
730 731 732 733
                       // m is not none
                       let temp = self.ig.get_temp_of(m.unwrap());
                       !self.is_spillable(temp)
                   } {
734
                m = Some(n);
qinsoon's avatar
qinsoon committed
735 736 737
            } else if (self.ig.get_spill_cost(n) / (self.degree(n) as f32)) <
                       (self.ig.get_spill_cost(m.unwrap()) / (self.degree(m.unwrap()) as f32))
            {
738 739 740
                m = Some(n);
            }
        }
qinsoon's avatar
qinsoon committed
741

742 743
        // m is not none
        let m = m.unwrap();
qinsoon's avatar
qinsoon committed
744
        trace!("Spilling {}...", self.display_node(m));
qinsoon's avatar
qinsoon committed
745

746 747 748
        vec_utils::remove_value(&mut self.worklist_spill, m);
        self.worklist_simplify.insert(m);
        self.freeze_moves(m);
749
    }
qinsoon's avatar
qinsoon committed
750

751
    fn assign_colors(&mut self) {
752
        trace!("---coloring done---");
753 754
        while !self.select_stack.is_empty() {
            let n = self.select_stack.pop().unwrap();
qinsoon's avatar
qinsoon committed
755
            trace!("Assigning color to {}", self.display_node(n));
qinsoon's avatar
qinsoon committed
756 757 758

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

            trace!("all the colors for this temp: {:?}", ok_colors);

qinsoon's avatar
qinsoon committed
762
            for w in self.ig.get_edges_of(n) {
qinsoon's avatar
qinsoon committed
763 764
                let w_alias = self.get_alias(w);
                match self.ig.get_color_of(w_alias) {
qinsoon's avatar
qinsoon committed
765
                    None => {} // do nothing
qinsoon's avatar
qinsoon committed
766
                    Some(color) => {
qinsoon's avatar
qinsoon committed
767 768 769 770 771 772
                        trace!(
                            "color {} is used for its neighbor {:?} (aliasing to {:?})",
                            color,
                            self.display_node(w),
                            self.display_node(w_alias)
                        );
qinsoon's avatar
qinsoon committed
773 774
                        ok_colors.remove(&color);
                    }
775 776
                }
            }
777
            trace!("available colors: {:?}", ok_colors);
qinsoon's avatar
qinsoon committed
778

779
            if ok_colors.is_empty() {
qinsoon's avatar
qinsoon committed
780
                trace!("{} is a spilled node", self.display_node(n));
781 782
                self.spilled_nodes.push(n);
            } else {
783
                let first_available_color = ok_colors.pop_front().unwrap();
qinsoon's avatar
qinsoon committed
784 785 786 787 788 789
                trace!(
                    "Color {} as {}",
                    self.display_node(n),
                    first_available_color
                );

790
                if !backend::is_callee_saved(first_available_color) {
791
                    trace!("Use caller saved register {}", first_available_color);
792
                }
qinsoon's avatar
qinsoon committed
793

794
                self.colored_nodes.push(n);
795
                self.ig.color_node(n, first_available_color);
796 797
            }
        }
qinsoon's avatar
qinsoon committed
798

qinsoon's avatar
qinsoon committed
799
        for n in self.colored_nodes.iter() {
800 801 802
            let n = *n;
            let alias = self.get_alias(n);
            let alias_color = self.ig.get_color_of(alias).unwrap();
qinsoon's avatar
qinsoon committed
803 804 805 806 807 808

            trace!(
                "Assign color to {} based on aliased {}",
                self.display_node(n),
                self.display_node(alias)
            );
qinsoon's avatar
qinsoon committed
809
            trace!("Color {} as {}", self.display_node(n), alias_color);
810 811 812
            self.ig.color_node(n, alias_color);
        }
    }
qinsoon's avatar
qinsoon committed
813

qinsoon's avatar
qinsoon committed
814
    fn rewrite_program(&mut self) {
qinsoon's avatar
qinsoon committed
815 816
        let spills = self.spills();

817
        let mut spilled_mem = LinkedHashMap::new();
qinsoon's avatar
qinsoon committed
818 819 820

        // allocating frame slots for every spilled temp
        for reg_id in spills.iter() {
qinsoon's avatar
qinsoon committed
821
            let ssa_entry = match self.func.context.get_value(*reg_id) {
qinsoon's avatar
qinsoon committed
822
                Some(entry) => entry,
823
                None => panic!("The spilled register {} is not in func context", reg_id)
qinsoon's avatar
qinsoon committed
824
            };
qinsoon's avatar
qinsoon committed
825 826 827
            let mem = self.cf
                .frame
                .alloc_slot_for_spilling(ssa_entry.value().clone(), self.vm);
qinsoon's avatar
qinsoon committed
828

qinsoon's avatar
qinsoon committed
829 830
            spilled_mem.insert(*reg_id, mem.clone());
            self.spill_history.insert(*reg_id, mem);
qinsoon's avatar
qinsoon committed
831 832
        }

qinsoon's avatar
qinsoon committed
833 834 835 836
        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
837
    }
qinsoon's avatar
qinsoon committed
838

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

842 843 844 845 846 847
        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
848

849
        spills
850
    }
851 852 853 854 855 856 857 858 859 860 861 862 863

    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
864 865 866 867 868 869 870 871 872
                    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
                        )
                    }
873 874 875 876 877
                };

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

879 880 881
        ret
    }

qinsoon's avatar
qinsoon committed
882 883 884
    pub fn get_spill_scratch_temps(&self) -> LinkedHashMap<MuID, MuID> {
        self.spill_scratch_temps.clone()
    }
885
}