WARNING! Access to this system is limited to authorised users only.
Unauthorised users may be subject to prosecution.
Unauthorised access to this system is a criminal offence under Australian law (Federal Crimes Act 1914 Part VIA)
It is a criminal offence to:
(1) Obtain access to data without authority. -Penalty 2 years imprisonment.
(2) Damage, delete, alter or insert data without authority. -Penalty 10 years imprisonment.
User activity is monitored and recorded. Anyone using this system expressly consents to such monitoring and recording.

coloring.rs 28.8 KB
Newer Older
Isaac Oscar Gariano's avatar
Isaac Oscar Gariano committed
1
// Copyright 2017 The Australian National University
qinsoon's avatar
qinsoon committed
2
//
Isaac Oscar Gariano's avatar
Isaac Oscar Gariano committed
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
//
Isaac Oscar Gariano's avatar
Isaac Oscar Gariano committed
7
//     http://www.apache.org/licenses/LICENSE-2.0
qinsoon's avatar
qinsoon committed
8
//
Isaac Oscar Gariano's avatar
Isaac Oscar Gariano committed
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;
qinsoon's avatar
qinsoon committed
28

qinsoon's avatar
qinsoon committed
29
use std::cell::RefCell;
qinsoon's avatar
qinsoon committed
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...");
qinsoon's avatar
qinsoon committed
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> {
qinsoon's avatar
qinsoon committed
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() {
qinsoon's avatar
qinsoon committed
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);
qinsoon's avatar
qinsoon committed
212
        }
qinsoon's avatar
qinsoon committed
213 214

        // push uncolored nodes to initial work set
qinsoon's avatar
qinsoon committed
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);
qinsoon's avatar
qinsoon committed
221 222
            }
        }
qinsoon's avatar
qinsoon committed
223 224

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

        // main loop
qinsoon's avatar
qinsoon committed
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())
qinsoon's avatar
qinsoon committed
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");
qinsoon's avatar
qinsoon committed
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));
qinsoon's avatar
qinsoon committed
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
qinsoon's avatar
qinsoon committed
275
    }
qinsoon's avatar
qinsoon committed
276

qinsoon's avatar
qinsoon committed
277
    fn build(&mut self) {
qinsoon's avatar
qinsoon committed
278 279
        if COALESCING {
            trace!("coalescing enabled, build move list");
qinsoon's avatar
qinsoon committed
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());
qinsoon's avatar
qinsoon committed
291
            }
qinsoon's avatar
qinsoon committed
292 293
        } else {
            trace!("coalescing disabled");
qinsoon's avatar
qinsoon committed
294 295
        }
    }
qinsoon's avatar
qinsoon committed
296

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

qinsoon's avatar
qinsoon committed
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

qinsoon's avatar
qinsoon committed
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);
qinsoon's avatar
qinsoon committed
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)
                );
qinsoon's avatar
qinsoon committed
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)
                );
qinsoon's avatar
qinsoon committed
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 {
qinsoon's avatar
qinsoon committed
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

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

qinsoon's avatar
qinsoon committed
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();
qinsoon's avatar
qinsoon committed
363
        for m in moves.iter() {
364
            if vec_utils::find_value(movelist, *m).is_some() {
qinsoon's avatar
qinsoon committed
365 366 367
                retained.insert(*m);
            }
        }
qinsoon's avatar
qinsoon committed
368

qinsoon's avatar
qinsoon committed
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) {
qinsoon's avatar
qinsoon committed
384
        if !list.contains_key(&node) {
qinsoon's avatar
qinsoon committed
385
            list.insert(node, RefCell::new(Vec::new()));
qinsoon's avatar
qinsoon committed
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);
qinsoon's avatar
qinsoon committed
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 {
qinsoon's avatar
qinsoon committed
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));
qinsoon's avatar
qinsoon committed
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 {
qinsoon's avatar
qinsoon committed
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) {
qinsoon's avatar
qinsoon committed
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) {
qinsoon's avatar
qinsoon committed
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) {
qinsoon's avatar
qinsoon committed
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
                }
            }
qinsoon's avatar
qinsoon committed
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