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.

To protect your data, the CISO officer has suggested users to enable 2FA as soon as possible.
Currently 2.6% of users enabled 2FA.

coloring.rs 27.4 KB
Newer Older
Isaac Oscar Gariano's avatar
Isaac Oscar Gariano committed
1 2 3 4 5 6 7 8 9 10 11 12 13 14
// Copyright 2017 The Australian National University
// 
// 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
// 
//     http://www.apache.org/licenses/LICENSE-2.0
// 
// 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
const COALESCING : bool = true;
35
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 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
    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
100
    pub fn start (func: &'a mut MuFunctionVersion, cf: &'a mut CompiledFunction, vm: &'a VM) -> GraphColoring<'a> {
101
        GraphColoring::start_with_spill_history(LinkedHashMap::new(), LinkedHashMap::new(), 0, func, cf, vm)
qinsoon's avatar
qinsoon committed
102 103
    }

qinsoon's avatar
qinsoon committed
104
    /// restarts coloring with spill history
qinsoon's avatar
qinsoon committed
105 106
    fn start_with_spill_history(spill_history: LinkedHashMap<MuID, P<Value>>,
                                spill_scratch_temps: LinkedHashMap<MuID, MuID>,
107
                                iteration_count: usize,
qinsoon's avatar
qinsoon committed
108 109
                                func: &'a mut MuFunctionVersion, cf: &'a mut CompiledFunction, vm: &'a VM) -> GraphColoring<'a>
    {
110 111 112 113 114
        assert!(iteration_count < MAX_REWRITE_ITERATIONS_ALLOWED,
            "reach graph coloring max rewrite iterations ({}), probably something is going wrong",
            MAX_REWRITE_ITERATIONS_ALLOWED);
        let iteration_count = iteration_count + 1;

115
        trace!("Initializing coloring allocator...");
qinsoon's avatar
qinsoon committed
116 117
        cf.mc().trace_mc();

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

120
        let coloring = GraphColoring {
qinsoon's avatar
qinsoon committed
121 122 123 124
            func: func,
            cf: cf,
            vm: vm,
            ig: ig,
125
            iteration_count: iteration_count,
126
            precolored: LinkedHashSet::new(),
127
            colors: {
128
                let mut map = LinkedHashMap::new();
129 130
                map.insert(backend::RegGroup::GPR, LinkedHashSet::new());
                map.insert(backend::RegGroup::FPR, LinkedHashSet::new());
131 132 133
                map
            },
            colored_nodes: Vec::new(),
134
            initial: Vec::new(),
135
            degree: LinkedHashMap::new(),
136
            worklist_moves: Vec::new(),
137
            movelist: LinkedHashMap::new(),
138 139 140 141
            active_moves: LinkedHashSet::new(),
            coalesced_nodes: LinkedHashSet::new(),
            coalesced_moves: LinkedHashSet::new(),
            constrained_moves: LinkedHashSet::new(),
142
            alias: LinkedHashMap::new(),
143
            worklist_spill: Vec::new(),
144
            spilled_nodes: Vec::new(),
qinsoon's avatar
qinsoon committed
145
            spill_history: spill_history,
qinsoon's avatar
qinsoon committed
146
            spill_scratch_temps: spill_scratch_temps,
147 148 149
            worklist_freeze: LinkedHashSet::new(),
            frozen_moves: LinkedHashSet::new(),
            worklist_simplify: LinkedHashSet::new(),
qinsoon's avatar
qinsoon committed
150
            select_stack: Vec::new(),
qinsoon's avatar
qinsoon committed
151
        };
qinsoon's avatar
qinsoon committed
152

qinsoon's avatar
qinsoon committed
153
        coloring.regalloc()
qinsoon's avatar
qinsoon committed
154
    }
qinsoon's avatar
qinsoon committed
155

qinsoon's avatar
qinsoon committed
156
    /// returns formatted string for a node
157
    fn display_node(&self, node: NodeIndex) -> String {
qinsoon's avatar
qinsoon committed
158 159 160 161
        let id = self.ig.get_temp_of(node);
        self.display_id(id)
    }

qinsoon's avatar
qinsoon committed
162
    /// returns formatted string for an ID
qinsoon's avatar
qinsoon committed
163 164 165 166
    fn display_id(&self, id: MuID) -> String {
        self.func.context.get_temp_display(id)
    }

qinsoon's avatar
qinsoon committed
167
    /// returns formatted string for a move
qinsoon's avatar
qinsoon committed
168 169 170
    fn display_move(&self, m: Move) -> String {
        format!("Move: {} -> {}", self.display_node(m.from), self.display_node(m.to))
    }
qinsoon's avatar
qinsoon committed
171 172

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

        // start timing for graph coloring
        let _p = hprof::enter("regalloc: graph coloring");
qinsoon's avatar
qinsoon committed
179
        
qinsoon's avatar
qinsoon committed
180
        // precolor for all machine registers
181
        for reg in backend::all_regs().values() {
182 183 184 185 186
            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
187
        // put usable registers as available colors
188
        for reg in backend::all_usable_regs().iter() {
qinsoon's avatar
qinsoon committed
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);
qinsoon's avatar
qinsoon committed
192
        }
qinsoon's avatar
qinsoon committed
193 194

        // push uncolored nodes to initial work set
qinsoon's avatar
qinsoon committed
195 196
        for node in self.ig.nodes() {
            if !self.ig.is_colored(node) {
197
                self.initial.push(node);
qinsoon's avatar
qinsoon committed
198 199 200
                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
201 202
            }
        }
qinsoon's avatar
qinsoon committed
203 204

        // initialize work
qinsoon's avatar
qinsoon committed
205 206
        self.build();
        self.make_work_list();
qinsoon's avatar
qinsoon committed
207 208

        // main loop
qinsoon's avatar
qinsoon committed
209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224
        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();
            }
            
            ! (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
225 226

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

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

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

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

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

249
        self
qinsoon's avatar
qinsoon committed
250 251 252
    }
    
    fn build(&mut self) {
qinsoon's avatar
qinsoon committed
253 254
        if COALESCING {
            trace!("coalescing enabled, build move list");
qinsoon's avatar
qinsoon committed
255 256
            let ref ig = self.ig;
            let ref mut movelist = self.movelist;
257
            for m in ig.moves().iter() {
qinsoon's avatar
qinsoon committed
258
                trace!("add to movelist: {:?}", m);
259
                self.worklist_moves.push(m.clone());
qinsoon's avatar
qinsoon committed
260 261
                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
262
            }
qinsoon's avatar
qinsoon committed
263 264
        } else {
            trace!("coalescing disabled");
qinsoon's avatar
qinsoon committed
265 266 267 268
        }
    }
    
    fn make_work_list(&mut self) {
269
        trace!("Making work list from initials...");
qinsoon's avatar
qinsoon committed
270
        while !self.initial.is_empty() {
271
            let node = self.initial.pop().unwrap();
qinsoon's avatar
qinsoon committed
272

qinsoon's avatar
qinsoon committed
273 274
            if {
                // condition: degree >= K
qinsoon's avatar
qinsoon committed
275
                let degree = self.ig.get_degree_of(node);
276
                let n_regs = self.n_regs_for_node(node);
qinsoon's avatar
qinsoon committed
277 278 279
                
                degree >= n_regs
            } {
qinsoon's avatar
qinsoon committed
280
                trace!("{} 's degree >= reg number limit (K), push to spill list", self.display_node(node));
281
                self.worklist_spill.push(node);
qinsoon's avatar
qinsoon committed
282
            } else if self.is_move_related(node) {
qinsoon's avatar
qinsoon committed
283
                trace!("{} is move related, push to freeze list", self.display_node(node));
qinsoon's avatar
qinsoon committed
284 285
                self.worklist_freeze.insert(node);
            } else {
qinsoon's avatar
qinsoon committed
286
                trace!("{} has small degree and not move related, push to simplify list", self.display_node(node));
qinsoon's avatar
qinsoon committed
287 288 289 290 291
                self.worklist_simplify.insert(node);
            }
        }
    }
    
292
    fn n_regs_for_node(&self, node: NodeIndex) -> usize {
293
        backend::number_of_usable_regs_in_group(self.ig.get_group_of(node))
294 295
    }
    
296
    fn is_move_related(&mut self, node: NodeIndex) -> bool {
qinsoon's avatar
qinsoon committed
297 298
        !self.node_moves(node).is_empty()
    }
299 300 301 302 303 304 305 306 307 308

    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
309
    
310
    fn node_moves(&mut self, node: NodeIndex) -> LinkedHashSet<Move> {
311
        let mut moves = LinkedHashSet::new();
qinsoon's avatar
qinsoon committed
312 313 314 315 316 317 318 319 320 321 322
        
        // addAll(active_moves)
        for m in self.active_moves.iter() {
            moves.insert(m.clone());
        }
        
        // addAll(worklist_moves)
        for m in self.worklist_moves.iter() {
            moves.insert(m.clone());
        }
        
323
        let mut retained = LinkedHashSet::new();
qinsoon's avatar
qinsoon committed
324
        let movelist = &GraphColoring::movelist_mut(&mut self.movelist, node).borrow();
qinsoon's avatar
qinsoon committed
325
        for m in moves.iter() {
326
            if vec_utils::find_value(movelist, *m).is_some() {
qinsoon's avatar
qinsoon committed
327 328 329 330 331 332 333
                retained.insert(*m);
            }
        }
        
        retained
    }
    
qinsoon's avatar
qinsoon committed
334 335 336
    // 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)
337
    fn movelist_mut(list: &mut LinkedHashMap<NodeIndex, RefCell<Vec<Move>>>, node: NodeIndex) -> &RefCell<Vec<Move>> {
qinsoon's avatar
qinsoon committed
338 339 340 341
        GraphColoring::movelist_check(list, node);
        unsafe {GraphColoring::movelist_nocheck(list, node)}
    }
    
342
    fn movelist_check(list: &mut LinkedHashMap<NodeIndex, RefCell<Vec<Move>>>, node: NodeIndex) {
qinsoon's avatar
qinsoon committed
343
        if !list.contains_key(&node) {
qinsoon's avatar
qinsoon committed
344
            list.insert(node, RefCell::new(Vec::new()));
qinsoon's avatar
qinsoon committed
345
        }
qinsoon's avatar
qinsoon committed
346 347 348
    }
    
    // allows getting the Vec<Move> without a mutable reference of the hashmap
349
    unsafe fn movelist_nocheck(list: &LinkedHashMap<NodeIndex, RefCell<Vec<Move>>>, node: NodeIndex) -> &RefCell<Vec<Move>> {
qinsoon's avatar
qinsoon committed
350
        list.get(&node).unwrap()
qinsoon's avatar
qinsoon committed
351
    }
352 353
    
    fn simplify(&mut self) {
354
        // remove next element from worklist_simplify, we know its not empty
355
        let node = self.worklist_simplify.pop_front().unwrap();
356
        
qinsoon's avatar
qinsoon committed
357
        trace!("Simplifying {}", self.display_node(node));
358 359
        
        self.select_stack.push(node);
360
        for m in self.adjacent(node).iter() {
361
            self.decrement_degree(*m);
362 363 364
        }
    }
    
365
    fn adjacent(&self, n: NodeIndex) -> LinkedHashSet<NodeIndex> {
366
        let mut adj = LinkedHashSet::new();
367 368
        
        // add n's successors
qinsoon's avatar
qinsoon committed
369
        for s in self.ig.get_edges_of(n) {
370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385
            adj.insert(s);
        }
        
        // removeAll(select_stack)
        for s in self.select_stack.iter() {
            adj.remove(s);
        }
        
        // removeAll(coalesced_nodes)
        for s in self.coalesced_nodes.iter() {
            adj.remove(s);
        }
        
        adj
    }
    
386
    fn degree(&self, n: NodeIndex) -> usize {
387 388 389 390 391 392
        match self.degree.get(&n) {
            Some(d) => *d,
            None => 0
        }
    }
    
393
    fn decrement_degree(&mut self, n: NodeIndex) {
394 395 396 397
        if self.precolored.contains(&n) {
            return;
        }
        
qinsoon's avatar
qinsoon committed
398
        trace!("decrement degree of {}", self.display_node(n));
399
        
400
        let d = self.degree(n);
401
        debug_assert!(d != 0);
402 403
        self.degree.insert(n, d - 1);
        
404
        if d == self.n_regs_for_node(n) {
qinsoon's avatar
qinsoon committed
405
            trace!("{}'s degree is K, no longer need to spill it", self.display_node(n));
406 407
            let mut nodes = self.adjacent(n);
            nodes.insert(n);
qinsoon's avatar
qinsoon committed
408
            trace!("enable moves of {:?}", nodes);
409 410 411 412 413
            self.enable_moves(nodes);
            
            vec_utils::remove_value(&mut self.worklist_spill, n);
            
            if self.is_move_related(n) {
qinsoon's avatar
qinsoon committed
414
                trace!("{} is move related, push to freeze list", self.display_node(n));
415 416
                self.worklist_freeze.insert(n);
            } else {
qinsoon's avatar
qinsoon committed
417
                trace!("{} is not move related, push to simplify list", self.display_node(n));
418 419 420 421 422
                self.worklist_simplify.insert(n);
            }
        }
    }
    
423
    fn enable_moves(&mut self, nodes: LinkedHashSet<NodeIndex>) {
424 425 426 427
        for n in nodes.iter() {
            let n = *n;
            for mov in self.node_moves(n).iter() {
                let mov = *mov;
428 429 430 431 432 433 434 435 436
                if self.active_moves.contains(&mov) {
                    self.active_moves.insert(mov);
                    self.worklist_moves.push(mov);
                }
            }
        }
    }
    
    fn coalesce(&mut self) {
qinsoon's avatar
qinsoon committed
437 438
        let m = self.worklist_moves.pop().unwrap();
        
qinsoon's avatar
qinsoon committed
439
        trace!("Coalescing on {}", self.display_move(m));
qinsoon's avatar
qinsoon committed
440 441 442

        // 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) {
qinsoon's avatar
qinsoon committed
443 444 445
            info!("a move instruction of two temporaries of different reigsters group");
            info!("from: {:?}, to: {:?}", m.from, m.to);

qinsoon's avatar
qinsoon committed
446 447
            return;
        }
qinsoon's avatar
qinsoon committed
448
        
qinsoon's avatar
qinsoon committed
449 450
        let x = self.get_alias(m.from);
        let y = self.get_alias(m.to);
qinsoon's avatar
qinsoon committed
451
        trace!("resolve alias: from {} to {}", self.display_node(x), self.display_node(y));
qinsoon's avatar
qinsoon committed
452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469
        
        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);
                
                (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);
                
                (u, v, precolored_u, precolored_v)
            }
        };
qinsoon's avatar
qinsoon committed
470
        trace!("u={}, v={}, precolored_u={}, precolroed_v={}", 
qinsoon's avatar
qinsoon committed
471 472
            self.display_node(u),
            self.display_node(v),
qinsoon's avatar
qinsoon committed
473
            precolored_u, precolored_v);
qinsoon's avatar
qinsoon committed
474 475
        
        if u == v {
qinsoon's avatar
qinsoon committed
476
            trace!("u == v, coalesce the move");
qinsoon's avatar
qinsoon committed
477 478 479 480 481
            self.coalesced_moves.insert(m);
            if !precolored_u {
                self.add_worklist(u);
            }
        } else if precolored_v || self.ig.is_adj(u, v) {
482 483
            trace!("precolored_v: {}", precolored_v);
            trace!("is_adj(u, v): {}", self.ig.is_adj(u, v));
qinsoon's avatar
qinsoon committed
484 485
            trace!("v is precolored or u,v is adjacent, the move is constrained");
            self.constrained_moves.insert(m);
qinsoon's avatar
qinsoon committed
486 487 488 489 490 491 492 493
            if !precolored_u {
                self.add_worklist(u);
            }
            if !precolored_v {
                self.add_worklist(v);
            }
        } else if (precolored_u && self.ok(u, v)) 
          || (!precolored_u && self.conservative(u, v)) {
qinsoon's avatar
qinsoon committed
494 495 496 497
            trace!("ok(u, v) = {}", self.ok(u, v));
            trace!("conservative(u, v) = {}", self.conservative(u, v));

            trace!("precolored_u&&ok(u,v) || !precolored_u&&conserv(u,v), coalesce and combine the move");
qinsoon's avatar
qinsoon committed
498 499 500 501 502 503
            self.coalesced_moves.insert(m);
            self.combine(u, v);
            if !precolored_u {
                self.add_worklist(u);
            }
        } else {
qinsoon's avatar
qinsoon committed
504
            trace!("cannot coalesce the move");
qinsoon's avatar
qinsoon committed
505 506 507 508
            self.active_moves.insert(m);
        }
    }
    
509
    pub fn get_alias(&self, node: NodeIndex) -> NodeIndex {
qinsoon's avatar
qinsoon committed
510 511 512 513 514 515 516
        if self.coalesced_nodes.contains(&node) {
            self.get_alias(*self.alias.get(&node).unwrap())
        } else {
            node
        }
    }
    
517
    fn add_worklist(&mut self, node: NodeIndex) {
518
        if !self.is_move_related(node) && self.degree(node) < self.n_regs_for_node(node) {
qinsoon's avatar
qinsoon committed
519 520 521 522 523
            self.worklist_freeze.remove(&node);
            self.worklist_simplify.insert(node);
        }
    }
    
524
    fn ok(&self, u: NodeIndex, v: NodeIndex) -> bool {
525 526
        for t in self.adjacent(v).iter() {
            let t = *t;
527 528 529
            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
530
                return false;
531
            }
qinsoon's avatar
qinsoon committed
532 533 534 535 536
        }
        
        true
    }
    
537
    fn conservative(&self, u: NodeIndex, v: NodeIndex) -> bool {
qinsoon's avatar
qinsoon committed
538 539
        let adj_u = self.adjacent(u);
        let adj_v = self.adjacent(v);
540 541 542 543 544
        let nodes = {
            let mut ret = adj_u;
            ret.add_all(adj_v);
            ret
        };
qinsoon's avatar
qinsoon committed
545 546
        
        let mut k = 0;
547
        for n in nodes.iter() {
qinsoon's avatar
qinsoon committed
548
            if self.precolored.contains(n) || self.degree(*n) >= self.n_regs_for_node(*n) {
qinsoon's avatar
qinsoon committed
549 550 551 552
                k += 1;
            }
        }
        
qinsoon's avatar
qinsoon committed
553
        k < self.n_regs_for_node(u) && k < self.n_regs_for_node(v)
qinsoon's avatar
qinsoon committed
554 555
    }
    
556
    fn combine(&mut self, u: NodeIndex, v: NodeIndex) {
qinsoon's avatar
qinsoon committed
557 558 559 560 561 562 563 564 565 566 567 568 569 570 571 572 573 574 575 576 577 578 579 580
        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);
        }
        
        self.alias.insert(v, u); 
        
        {
            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
            let movelist_u = &mut unsafe {GraphColoring::movelist_nocheck(movelist, u)}.borrow_mut();
            let movelist_v = &mut unsafe {GraphColoring::movelist_nocheck(movelist, v)}.borrow_mut();
            
            // addAll()
            movelist_u.extend_from_slice(movelist_v.as_slice());
        }
        
581
        let mut nodes = LinkedHashSet::new();
qinsoon's avatar
qinsoon committed
582 583 584
        nodes.insert(v);
        self.enable_moves(nodes);
        
585 586
        for t in self.adjacent(v).iter() {
            let t = *t;
qinsoon's avatar
qinsoon committed
587 588 589 590 591
            self.add_edge(t, u);
            self.decrement_degree(t);
        }
        
        if self.worklist_freeze.contains(&u)
592
          && self.degree(u) >= self.n_regs_for_node(u) {
qinsoon's avatar
qinsoon committed
593 594 595 596 597
            self.worklist_freeze.remove(&u);
            self.worklist_spill.push(u);
        }
    }
    
598
    fn add_edge(&mut self, u: NodeIndex, v: NodeIndex) {
qinsoon's avatar
qinsoon committed
599 600 601 602 603 604 605 606 607 608 609 610
        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);
            }
        }
611 612 613
    }
    
    fn freeze(&mut self) {
qinsoon's avatar
qinsoon committed
614
        // it is not empty (checked before)
615
        let node = self.worklist_freeze.pop_front().unwrap();
qinsoon's avatar
qinsoon committed
616
        trace!("Freezing {}...", self.display_node(node));
qinsoon's avatar
qinsoon committed
617 618 619 620 621
        
        self.worklist_simplify.insert(node);
        self.freeze_moves(node);
    }
    
622
    fn freeze_moves(&mut self, u: NodeIndex) {
623 624
        for m in self.node_moves(u).iter() {
            let m = *m;
qinsoon's avatar
qinsoon committed
625 626 627 628 629 630 631 632 633 634
            let mut v = self.get_alias(m.from);
            if v == self.get_alias(u) {
                v = self.get_alias(m.to);
            }
            
            self.active_moves.remove(&m);
            self.frozen_moves.insert(m);
            
            if !self.precolored.contains(&v) 
               && self.node_moves(v).is_empty()
635
               && self.degree(v) < self.n_regs_for_node(v) {
qinsoon's avatar
qinsoon committed
636 637 638 639
                self.worklist_freeze.remove(&v);
                self.worklist_simplify.insert(v);
            }
        }
640 641 642
    }
    
    fn select_spill(&mut self) {
qinsoon's avatar
qinsoon committed
643
        trace!("Selecting a node to spill...");
644
        let mut m : Option<NodeIndex> = None;
645 646 647 648 649 650 651 652
        
        for n in self.worklist_spill.iter() {
            let n = *n;
            if m.is_none() {
                m = Some(n);
            } else if {
                // m is not none
                let temp = self.ig.get_temp_of(m.unwrap());
653
                !self.is_spillable(temp)
654 655 656 657 658 659 660 661 662 663
            } {
                m = Some(n);
            } 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)) {
                m = Some(n);
            }
        }
        
        // m is not none
        let m = m.unwrap();
qinsoon's avatar
qinsoon committed
664
        trace!("Spilling {}...", self.display_node(m));
qinsoon's avatar
qinsoon committed
665
        
666 667 668
        vec_utils::remove_value(&mut self.worklist_spill, m);
        self.worklist_simplify.insert(m);
        self.freeze_moves(m);
669 670
    }
    
671
    fn assign_colors(&mut self) {
qinsoon's avatar
qinsoon committed
672
        trace!("---coloring done---");
673 674
        while !self.select_stack.is_empty() {
            let n = self.select_stack.pop().unwrap();
qinsoon's avatar
qinsoon committed
675
            trace!("Assigning color to {}", self.display_node(n));
676
            
677
            let mut ok_colors : LinkedHashSet<MuID> = self.colors.get(&self.ig.get_group_of(n)).unwrap().clone();
qinsoon's avatar
qinsoon committed
678 679 680

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

qinsoon's avatar
qinsoon committed
681
            for w in self.ig.get_edges_of(n) {
qinsoon's avatar
qinsoon committed
682 683
                let w_alias = self.get_alias(w);
                match self.ig.get_color_of(w_alias) {
684
                    None => {}, // do nothing
qinsoon's avatar
qinsoon committed
685 686 687 688
                    Some(color) => {
                        trace!("color {} is used for its neighbor {:?} (aliasing to {:?})", color, self.display_node(w), self.display_node(w_alias));
                        ok_colors.remove(&color);
                    }
689 690
                }
            }
qinsoon's avatar
qinsoon committed
691
            trace!("available colors: {:?}", ok_colors);
692 693
            
            if ok_colors.is_empty() {
qinsoon's avatar
qinsoon committed
694
                trace!("{} is a spilled node", self.display_node(n));
695 696
                self.spilled_nodes.push(n);
            } else {
697
                let first_available_color = ok_colors.pop_front().unwrap();
qinsoon's avatar
qinsoon committed
698
                trace!("Color {} as {}", self.display_node(n), first_available_color);
699 700
                
                if !backend::is_callee_saved(first_available_color) {
qinsoon's avatar
qinsoon committed
701
                    trace!("Use caller saved register {}", first_available_color);
702 703
                }
                
704
                self.colored_nodes.push(n);
qinsoon's avatar
qinsoon committed
705
                self.ig.color_node(n, first_available_color);
706 707 708
            }
        }
        
qinsoon's avatar
qinsoon committed
709
        for n in self.colored_nodes.iter() {
710 711 712
            let n = *n;
            let alias = self.get_alias(n);
            let alias_color = self.ig.get_color_of(alias).unwrap();
qinsoon's avatar
qinsoon committed
713
            
qinsoon's avatar
qinsoon committed
714 715
            trace!("Assign color to {} based on aliased {}", self.display_node(n), self.display_node(alias));
            trace!("Color {} as {}", self.display_node(n), alias_color);
716 717 718
            self.ig.color_node(n, alias_color);
        }
    }
qinsoon's avatar
qinsoon committed
719

qinsoon's avatar
qinsoon committed
720
    fn rewrite_program(&mut self) {
qinsoon's avatar
qinsoon committed
721 722
        let spills = self.spills();

723
        let mut spilled_mem = LinkedHashMap::new();
qinsoon's avatar
qinsoon committed
724 725 726

        // allocating frame slots for every spilled temp
        for reg_id in spills.iter() {
qinsoon's avatar
qinsoon committed
727
            let ssa_entry = match self.func.context.get_value(*reg_id) {
qinsoon's avatar
qinsoon committed
728 729 730
                Some(entry) => entry,
                None => panic!("The spilled register {} is not in func context", reg_id)
            };
qinsoon's avatar
qinsoon committed
731
            let mem = self.cf.frame.alloc_slot_for_spilling(ssa_entry.value().clone(), self.vm);
qinsoon's avatar
qinsoon committed
732

qinsoon's avatar
qinsoon committed
733 734
            spilled_mem.insert(*reg_id, mem.clone());
            self.spill_history.insert(*reg_id, mem);
qinsoon's avatar
qinsoon committed
735 736
        }

qinsoon's avatar
qinsoon committed
737 738 739 740
        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
741
    }
742 743 744 745 746 747 748 749 750 751 752 753
    
    pub fn spills(&self) -> Vec<MuID> {
        let mut spills = vec![];
        
        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));
            }
        }
        
        spills
754
    }
755 756 757 758 759 760 761 762 763 764 765 766 767 768 769 770 771 772 773 774 775 776 777 778 779 780

    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,
                    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)
                };

                ret.insert(temp, machine_reg);
            }
        }
        
        ret
    }

qinsoon's avatar
qinsoon committed
781 782 783
    pub fn get_spill_scratch_temps(&self) -> LinkedHashMap<MuID, MuID> {
        self.spill_scratch_temps.clone()
    }
784
}