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.7% of users enabled 2FA.

coloring.rs 26.8 KB
Newer Older
1
2
extern crate hprof;

qinsoon's avatar
qinsoon committed
3
use ast::ptr::*;
qinsoon's avatar
qinsoon committed
4
5
6
use ast::ir::*;
use compiler::backend;
use compiler::backend::reg_alloc::graph_coloring;
7
use compiler::backend::reg_alloc::graph_coloring::liveness::InterferenceGraph;
qinsoon's avatar
qinsoon committed
8
9
use compiler::machine_code::CompiledFunction;
use vm::VM;
10

11
use utils::vec_utils;
12
use utils::LinkedHashSet;
13
use utils::LinkedHashMap;
qinsoon's avatar
qinsoon committed
14

qinsoon's avatar
qinsoon committed
15
use std::cell::RefCell;
qinsoon's avatar
qinsoon committed
16

17
18
19
use compiler::backend::reg_alloc::graph_coloring::liveness::Move;
use compiler::backend::reg_alloc::graph_coloring::petgraph::graph::NodeIndex;

qinsoon's avatar
qinsoon committed
20
const COALESCING : bool = true;
21

qinsoon's avatar
qinsoon committed
22
23
/// GraphColoring algorithm
/// based on Appel's book section 11.4
qinsoon's avatar
qinsoon committed
24
pub struct GraphColoring<'a> {
qinsoon's avatar
qinsoon committed
25
    // context
qinsoon's avatar
qinsoon committed
26
27
28
    pub func: &'a mut MuFunctionVersion,
    pub cf: &'a mut CompiledFunction,
    pub vm: &'a VM,
29
    pub ig: InterferenceGraph,
qinsoon's avatar
qinsoon committed
30

qinsoon's avatar
qinsoon committed
31
    /// machine registers, preassigned a color
32
    precolored: LinkedHashSet<NodeIndex>,
qinsoon's avatar
qinsoon committed
33
    /// all colors available
34
    colors: LinkedHashMap<backend::RegGroup, LinkedHashSet<MuID>>,
qinsoon's avatar
qinsoon committed
35
    /// temporaries, not precolored and not yet processed
36
    initial: Vec<NodeIndex>,
qinsoon's avatar
qinsoon committed
37
38
39
40
41
42
43
44
45
46
47
48
49
50
    /// whether a temp is spillable
    // FIXME: not used
    spillable: LinkedHashMap<MuID, bool>,

    /// 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
51
    coalesced_nodes: LinkedHashSet<NodeIndex>,
qinsoon's avatar
qinsoon committed
52
53
54
55
56
57
    /// nodes successfully colored
    colored_nodes: Vec<NodeIndex>,
    /// stack containing temporaries removed from the graph
    select_stack: Vec<NodeIndex>,

    /// moves that have been coalesced
58
    coalesced_moves: LinkedHashSet<Move>,
qinsoon's avatar
qinsoon committed
59
    /// moves whose source and target interfere
60
    constrained_moves: LinkedHashSet<Move>,
qinsoon's avatar
qinsoon committed
61
62
63
64
65
66
67
68
69
70
71
72
    /// 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
73
    alias: LinkedHashMap<NodeIndex, NodeIndex>,
qinsoon's avatar
qinsoon committed
74

qinsoon's avatar
qinsoon committed
75
76
77
78
79
    // 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
80
81
}

qinsoon's avatar
qinsoon committed
82
impl <'a> GraphColoring<'a> {
qinsoon's avatar
qinsoon committed
83
    /// starts coloring
84
    pub fn start (func: &'a mut MuFunctionVersion, cf: &'a mut CompiledFunction, vm: &'a VM) -> GraphColoring<'a> {
qinsoon's avatar
qinsoon committed
85
        GraphColoring::start_with_spill_history(LinkedHashMap::new(), LinkedHashMap::new(), func, cf, vm)
qinsoon's avatar
qinsoon committed
86
87
    }

qinsoon's avatar
qinsoon committed
88
    /// restarts coloring with spill history
qinsoon's avatar
qinsoon committed
89
90
91
92
    fn start_with_spill_history(spill_history: LinkedHashMap<MuID, P<Value>>,
                                spill_scratch_temps: LinkedHashMap<MuID, MuID>,
                                func: &'a mut MuFunctionVersion, cf: &'a mut CompiledFunction, vm: &'a VM) -> GraphColoring<'a>
    {
93
        trace!("Initializing coloring allocator...");
qinsoon's avatar
qinsoon committed
94
95
        cf.mc().trace_mc();

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

98
        let coloring = GraphColoring {
qinsoon's avatar
qinsoon committed
99
100
101
102
            func: func,
            cf: cf,
            vm: vm,
            ig: ig,
103
            precolored: LinkedHashSet::new(),
104
            colors: {
105
                let mut map = LinkedHashMap::new();
106
107
                map.insert(backend::RegGroup::GPR, LinkedHashSet::new());
                map.insert(backend::RegGroup::FPR, LinkedHashSet::new());
108
109
110
                map
            },
            colored_nodes: Vec::new(),
111
            initial: Vec::new(),
112
            degree: LinkedHashMap::new(),
113
            worklist_moves: Vec::new(),
114
            movelist: LinkedHashMap::new(),
115
116
117
118
            active_moves: LinkedHashSet::new(),
            coalesced_nodes: LinkedHashSet::new(),
            coalesced_moves: LinkedHashSet::new(),
            constrained_moves: LinkedHashSet::new(),
119
            alias: LinkedHashMap::new(),
120
            worklist_spill: Vec::new(),
121
            spillable: LinkedHashMap::new(),
122
            spilled_nodes: Vec::new(),
qinsoon's avatar
qinsoon committed
123
            spill_history: spill_history,
qinsoon's avatar
qinsoon committed
124
            spill_scratch_temps: spill_scratch_temps,
125
126
127
            worklist_freeze: LinkedHashSet::new(),
            frozen_moves: LinkedHashSet::new(),
            worklist_simplify: LinkedHashSet::new(),
qinsoon's avatar
qinsoon committed
128
            select_stack: Vec::new(),
qinsoon's avatar
qinsoon committed
129
        };
qinsoon's avatar
qinsoon committed
130

qinsoon's avatar
qinsoon committed
131
        coloring.regalloc()
qinsoon's avatar
qinsoon committed
132
    }
qinsoon's avatar
qinsoon committed
133

qinsoon's avatar
qinsoon committed
134
    /// returns formatted string for a node
135
    fn display_node(&self, node: NodeIndex) -> String {
qinsoon's avatar
qinsoon committed
136
137
138
139
        let id = self.ig.get_temp_of(node);
        self.display_id(id)
    }

qinsoon's avatar
qinsoon committed
140
    /// returns formatted string for an ID
qinsoon's avatar
qinsoon committed
141
142
143
144
    fn display_id(&self, id: MuID) -> String {
        self.func.context.get_temp_display(id)
    }

qinsoon's avatar
qinsoon committed
145
    /// returns formatted string for a move
qinsoon's avatar
qinsoon committed
146
147
148
    fn display_move(&self, m: Move) -> String {
        format!("Move: {} -> {}", self.display_node(m.from), self.display_node(m.to))
    }
qinsoon's avatar
qinsoon committed
149
150

    /// does coloring register allocation
151
    fn regalloc(mut self) -> GraphColoring<'a> {
qinsoon's avatar
qinsoon committed
152
        trace!("---InterenceGraph---");
qinsoon's avatar
qinsoon committed
153
        self.ig.print(&self.func.context);
qinsoon's avatar
qinsoon committed
154
155
156

        // start timing for graph coloring
        let _p = hprof::enter("regalloc: graph coloring");
qinsoon's avatar
qinsoon committed
157
        
qinsoon's avatar
qinsoon committed
158
        // precolor for all machine registers
159
        for reg in backend::all_regs().values() {
160
161
162
163
164
            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
165
        // put usable registers as available colors
166
        for reg in backend::all_usable_regs().iter() {
qinsoon's avatar
qinsoon committed
167
            let reg_id = reg.extract_ssa_id().unwrap();
qinsoon's avatar
qinsoon committed
168
169
            let group = backend::pick_group_for_reg(reg_id);
            self.colors.get_mut(&group).unwrap().insert(reg_id);
qinsoon's avatar
qinsoon committed
170
        }
qinsoon's avatar
qinsoon committed
171
172

        // push uncolored nodes to initial work set
qinsoon's avatar
qinsoon committed
173
174
        for node in self.ig.nodes() {
            if !self.ig.is_colored(node) {
175
                self.initial.push(node);
qinsoon's avatar
qinsoon committed
176
177
178
                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
179
180
            }
        }
qinsoon's avatar
qinsoon committed
181
182

        // initialize work
qinsoon's avatar
qinsoon committed
183
184
        self.build();
        self.make_work_list();
qinsoon's avatar
qinsoon committed
185
186

        // main loop
qinsoon's avatar
qinsoon committed
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
        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
203
204

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

qinsoon's avatar
qinsoon committed
207
        // finish
208
209
        drop(_p);

qinsoon's avatar
qinsoon committed
210
        // if we need to spill
qinsoon's avatar
qinsoon committed
211
212
        if !self.spilled_nodes.is_empty() {
            trace!("spill required");
qinsoon's avatar
qinsoon committed
213
214
215
            if cfg!(debug_assertions) {
                trace!("nodes to be spilled:");
                for node in self.spilled_nodes.iter() {
qinsoon's avatar
qinsoon committed
216
                    trace!("{}", self.display_node(*node));
qinsoon's avatar
qinsoon committed
217
218
219
                }
            }

qinsoon's avatar
qinsoon committed
220
            // rewrite program to insert spilling code
qinsoon's avatar
qinsoon committed
221
            self.rewrite_program();
qinsoon's avatar
qinsoon committed
222

qinsoon's avatar
qinsoon committed
223
            // recursively redo graph coloring
qinsoon's avatar
qinsoon committed
224
            return GraphColoring::start_with_spill_history(self.spill_history.clone(), self.spill_scratch_temps.clone(), self.func, self.cf, self.vm);
qinsoon's avatar
qinsoon committed
225
226
        }

227
        self
qinsoon's avatar
qinsoon committed
228
229
230
    }
    
    fn build(&mut self) {
qinsoon's avatar
qinsoon committed
231
232
        if COALESCING {
            trace!("coalescing enabled, build move list");
qinsoon's avatar
qinsoon committed
233
234
            let ref ig = self.ig;
            let ref mut movelist = self.movelist;
235
            for m in ig.moves().iter() {
qinsoon's avatar
qinsoon committed
236
                trace!("add to movelist: {:?}", m);
237
                self.worklist_moves.push(m.clone());
qinsoon's avatar
qinsoon committed
238
239
                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
240
            }
qinsoon's avatar
qinsoon committed
241
242
        } else {
            trace!("coalescing disabled");
qinsoon's avatar
qinsoon committed
243
244
245
246
        }
    }
    
    fn make_work_list(&mut self) {
247
        trace!("Making work list from initials...");
qinsoon's avatar
qinsoon committed
248
        while !self.initial.is_empty() {
249
            let node = self.initial.pop().unwrap();
qinsoon's avatar
qinsoon committed
250
251
252
            
            if {
                // condition: degree >= K
qinsoon's avatar
qinsoon committed
253
                let degree = self.ig.get_degree_of(node);
254
                let n_regs = self.n_regs_for_node(node);
qinsoon's avatar
qinsoon committed
255
256
257
                
                degree >= n_regs
            } {
qinsoon's avatar
qinsoon committed
258
                trace!("{} 's degree >= reg number limit (K), push to spill list", self.display_node(node));
259
                self.worklist_spill.push(node);
qinsoon's avatar
qinsoon committed
260
            } else if self.is_move_related(node) {
qinsoon's avatar
qinsoon committed
261
                trace!("{} is move related, push to freeze list", self.display_node(node));
qinsoon's avatar
qinsoon committed
262
263
                self.worklist_freeze.insert(node);
            } else {
qinsoon's avatar
qinsoon committed
264
                trace!("{} has small degree and not move related, push to simplify list", self.display_node(node));
qinsoon's avatar
qinsoon committed
265
266
267
268
269
                self.worklist_simplify.insert(node);
            }
        }
    }
    
270
    fn n_regs_for_node(&self, node: NodeIndex) -> usize {
271
272
273
        backend::number_of_regs_in_group(self.ig.get_group_of(node))
    }
    
274
    fn is_move_related(&mut self, node: NodeIndex) -> bool {
qinsoon's avatar
qinsoon committed
275
276
277
        !self.node_moves(node).is_empty()
    }
    
278
    fn node_moves(&mut self, node: NodeIndex) -> LinkedHashSet<Move> {
279
        let mut moves = LinkedHashSet::new();
qinsoon's avatar
qinsoon committed
280
281
282
283
284
285
286
287
288
289
290
        
        // 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());
        }
        
291
        let mut retained = LinkedHashSet::new();
qinsoon's avatar
qinsoon committed
292
        let movelist = &GraphColoring::movelist_mut(&mut self.movelist, node).borrow();
qinsoon's avatar
qinsoon committed
293
        for m in moves.iter() {
294
            if vec_utils::find_value(movelist, *m).is_some() {
qinsoon's avatar
qinsoon committed
295
296
297
298
299
300
301
                retained.insert(*m);
            }
        }
        
        retained
    }
    
qinsoon's avatar
qinsoon committed
302
303
304
    // 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)
305
    fn movelist_mut(list: &mut LinkedHashMap<NodeIndex, RefCell<Vec<Move>>>, node: NodeIndex) -> &RefCell<Vec<Move>> {
qinsoon's avatar
qinsoon committed
306
307
308
309
        GraphColoring::movelist_check(list, node);
        unsafe {GraphColoring::movelist_nocheck(list, node)}
    }
    
310
    fn movelist_check(list: &mut LinkedHashMap<NodeIndex, RefCell<Vec<Move>>>, node: NodeIndex) {
qinsoon's avatar
qinsoon committed
311
        if !list.contains_key(&node) {
qinsoon's avatar
qinsoon committed
312
            list.insert(node, RefCell::new(Vec::new()));
qinsoon's avatar
qinsoon committed
313
        }
qinsoon's avatar
qinsoon committed
314
315
316
    }
    
    // allows getting the Vec<Move> without a mutable reference of the hashmap
317
    unsafe fn movelist_nocheck(list: &LinkedHashMap<NodeIndex, RefCell<Vec<Move>>>, node: NodeIndex) -> &RefCell<Vec<Move>> {
qinsoon's avatar
qinsoon committed
318
        list.get(&node).unwrap()
qinsoon's avatar
qinsoon committed
319
    }
320
321
    
    fn simplify(&mut self) {
322
        // remove next element from worklist_simplify, we know its not empty
323
        let node = self.worklist_simplify.pop_front().unwrap();
324
        
qinsoon's avatar
qinsoon committed
325
        trace!("Simplifying {}", self.display_node(node));
326
327
328
        
        self.select_stack.push(node);
        
329
        for m in self.adjacent(node).iter() {
330
            self.decrement_degree(*m);
331
332
333
        }
    }
    
334
    fn adjacent(&self, n: NodeIndex) -> LinkedHashSet<NodeIndex> {
335
        let mut adj = LinkedHashSet::new();
336
337
        
        // add n's successors
qinsoon's avatar
qinsoon committed
338
        for s in self.ig.get_edges_of(n) {
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
            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
    }
    
355
    fn degree(&self, n: NodeIndex) -> usize {
356
357
358
359
360
361
        match self.degree.get(&n) {
            Some(d) => *d,
            None => 0
        }
    }
    
362
    fn decrement_degree(&mut self, n: NodeIndex) {
363
364
365
366
        if self.precolored.contains(&n) {
            return;
        }
        
qinsoon's avatar
qinsoon committed
367
        trace!("decrement degree of {}", self.display_node(n));
368
        
369
        let d = self.degree(n);
370
        debug_assert!(d != 0);
371
372
        self.degree.insert(n, d - 1);
        
373
        if d == self.n_regs_for_node(n) {
qinsoon's avatar
qinsoon committed
374
            trace!("{}'s degree is K, no longer need to spill it", self.display_node(n));
375
376
            let mut nodes = self.adjacent(n);
            nodes.insert(n);
qinsoon's avatar
qinsoon committed
377
            trace!("enable moves of {:?}", nodes);
378
379
380
381
382
            self.enable_moves(nodes);
            
            vec_utils::remove_value(&mut self.worklist_spill, n);
            
            if self.is_move_related(n) {
qinsoon's avatar
qinsoon committed
383
                trace!("{} is move related, push to freeze list", self.display_node(n));
384
385
                self.worklist_freeze.insert(n);
            } else {
qinsoon's avatar
qinsoon committed
386
                trace!("{} is not move related, push to simplify list", self.display_node(n));
387
388
389
390
391
                self.worklist_simplify.insert(n);
            }
        }
    }
    
392
    fn enable_moves(&mut self, nodes: LinkedHashSet<NodeIndex>) {
393
394
395
396
        for n in nodes.iter() {
            let n = *n;
            for mov in self.node_moves(n).iter() {
                let mov = *mov;
397
398
399
400
401
402
403
404
405
                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
406
407
        let m = self.worklist_moves.pop().unwrap();
        
qinsoon's avatar
qinsoon committed
408
        trace!("Coalescing on {}", self.display_move(m));
qinsoon's avatar
qinsoon committed
409
410
411

        // 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
412
413
414
            info!("a move instruction of two temporaries of different reigsters group");
            info!("from: {:?}, to: {:?}", m.from, m.to);

qinsoon's avatar
qinsoon committed
415
416
            return;
        }
qinsoon's avatar
qinsoon committed
417
        
qinsoon's avatar
qinsoon committed
418
419
        let x = self.get_alias(m.from);
        let y = self.get_alias(m.to);
qinsoon's avatar
qinsoon committed
420
        trace!("resolve alias: from {} to {}", self.display_node(x), self.display_node(y));
qinsoon's avatar
qinsoon committed
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
        
        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
439
        trace!("u={}, v={}, precolored_u={}, precolroed_v={}", 
qinsoon's avatar
qinsoon committed
440
441
            self.display_node(u),
            self.display_node(v),
qinsoon's avatar
qinsoon committed
442
            precolored_u, precolored_v);
qinsoon's avatar
qinsoon committed
443
444
        
        if u == v {
qinsoon's avatar
qinsoon committed
445
            trace!("u == v, coalesce the move");
qinsoon's avatar
qinsoon committed
446
447
448
449
450
            self.coalesced_moves.insert(m);
            if !precolored_u {
                self.add_worklist(u);
            }
        } else if precolored_v || self.ig.is_adj(u, v) {
451
452
            trace!("precolored_v: {}", precolored_v);
            trace!("is_adj(u, v): {}", self.ig.is_adj(u, v));
qinsoon's avatar
qinsoon committed
453
454
            trace!("v is precolored or u,v is adjacent, the move is constrained");
            self.constrained_moves.insert(m);
qinsoon's avatar
qinsoon committed
455
456
457
458
459
460
461
462
            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
463
464
465
466
            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
467
468
469
470
471
472
            self.coalesced_moves.insert(m);
            self.combine(u, v);
            if !precolored_u {
                self.add_worklist(u);
            }
        } else {
qinsoon's avatar
qinsoon committed
473
            trace!("cannot coalesce the move");
qinsoon's avatar
qinsoon committed
474
475
476
477
            self.active_moves.insert(m);
        }
    }
    
478
    pub fn get_alias(&self, node: NodeIndex) -> NodeIndex {
qinsoon's avatar
qinsoon committed
479
480
481
482
483
484
485
        if self.coalesced_nodes.contains(&node) {
            self.get_alias(*self.alias.get(&node).unwrap())
        } else {
            node
        }
    }
    
486
    fn add_worklist(&mut self, node: NodeIndex) {
487
        if !self.is_move_related(node) && self.degree(node) < self.n_regs_for_node(node) {
qinsoon's avatar
qinsoon committed
488
489
490
491
492
            self.worklist_freeze.remove(&node);
            self.worklist_simplify.insert(node);
        }
    }
    
493
    fn ok(&self, u: NodeIndex, v: NodeIndex) -> bool {
494
495
        for t in self.adjacent(v).iter() {
            let t = *t;
496
497
498
            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
499
                return false;
500
            }
qinsoon's avatar
qinsoon committed
501
502
503
504
505
        }
        
        true
    }
    
506
    fn conservative(&self, u: NodeIndex, v: NodeIndex) -> bool {
qinsoon's avatar
qinsoon committed
507
508
        let adj_u = self.adjacent(u);
        let adj_v = self.adjacent(v);
509
510
511
512
513
        let nodes = {
            let mut ret = adj_u;
            ret.add_all(adj_v);
            ret
        };
qinsoon's avatar
qinsoon committed
514
515
        
        let mut k = 0;
516
        for n in nodes.iter() {
qinsoon's avatar
qinsoon committed
517
            if self.precolored.contains(n) || self.degree(*n) >= self.n_regs_for_node(*n) {
qinsoon's avatar
qinsoon committed
518
519
520
521
                k += 1;
            }
        }
        
qinsoon's avatar
qinsoon committed
522
        k < self.n_regs_for_node(u) && k < self.n_regs_for_node(v)
qinsoon's avatar
qinsoon committed
523
524
    }
    
525
    fn combine(&mut self, u: NodeIndex, v: NodeIndex) {
qinsoon's avatar
qinsoon committed
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
        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());
        }
        
550
        let mut nodes = LinkedHashSet::new();
qinsoon's avatar
qinsoon committed
551
552
553
        nodes.insert(v);
        self.enable_moves(nodes);
        
554
555
        for t in self.adjacent(v).iter() {
            let t = *t;
qinsoon's avatar
qinsoon committed
556
557
558
559
560
            self.add_edge(t, u);
            self.decrement_degree(t);
        }
        
        if self.worklist_freeze.contains(&u)
561
          && self.degree(u) >= self.n_regs_for_node(u) {
qinsoon's avatar
qinsoon committed
562
563
564
565
566
            self.worklist_freeze.remove(&u);
            self.worklist_spill.push(u);
        }
    }
    
567
    fn add_edge(&mut self, u: NodeIndex, v: NodeIndex) {
qinsoon's avatar
qinsoon committed
568
569
570
571
572
573
574
575
576
577
578
579
        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);
            }
        }
580
581
582
    }
    
    fn freeze(&mut self) {
qinsoon's avatar
qinsoon committed
583
        // it is not empty (checked before)
584
        let node = self.worklist_freeze.pop_front().unwrap();
qinsoon's avatar
qinsoon committed
585
        trace!("Freezing {}...", self.display_node(node));
qinsoon's avatar
qinsoon committed
586
587
588
589
590
        
        self.worklist_simplify.insert(node);
        self.freeze_moves(node);
    }
    
591
    fn freeze_moves(&mut self, u: NodeIndex) {
592
593
        for m in self.node_moves(u).iter() {
            let m = *m;
qinsoon's avatar
qinsoon committed
594
595
596
597
598
599
600
601
602
603
            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()
604
               && self.degree(v) < self.n_regs_for_node(v) {
qinsoon's avatar
qinsoon committed
605
606
607
608
                self.worklist_freeze.remove(&v);
                self.worklist_simplify.insert(v);
            }
        }
609
610
611
    }
    
    fn select_spill(&mut self) {
qinsoon's avatar
qinsoon committed
612
        trace!("Selecting a node to spill...");
613
        let mut m : Option<NodeIndex> = None;
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
        
        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());
                let spillable = {match self.spillable.get(&temp) {
                    None => {
                        //by default, its spillable
                        true
                    },
                    Some(b) => *b
                }};
                
                !spillable
            } {
                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
641
        trace!("Spilling {}...", self.display_node(m));
qinsoon's avatar
qinsoon committed
642
        
643
644
645
        vec_utils::remove_value(&mut self.worklist_spill, m);
        self.worklist_simplify.insert(m);
        self.freeze_moves(m);
646
647
    }
    
648
    fn assign_colors(&mut self) {
qinsoon's avatar
qinsoon committed
649
        trace!("---coloring done---");
650
651
        while !self.select_stack.is_empty() {
            let n = self.select_stack.pop().unwrap();
qinsoon's avatar
qinsoon committed
652
            trace!("Assigning color to {}", self.display_node(n));
653
            
654
            let mut ok_colors : LinkedHashSet<MuID> = self.colors.get(&self.ig.get_group_of(n)).unwrap().clone();
qinsoon's avatar
qinsoon committed
655
656
657

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

qinsoon's avatar
qinsoon committed
658
            for w in self.ig.get_edges_of(n) {
qinsoon's avatar
qinsoon committed
659
660
                let w_alias = self.get_alias(w);
                match self.ig.get_color_of(w_alias) {
661
                    None => {}, // do nothing
qinsoon's avatar
qinsoon committed
662
663
664
665
                    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);
                    }
666
667
                }
            }
qinsoon's avatar
qinsoon committed
668
            trace!("available colors: {:?}", ok_colors);
669
670
            
            if ok_colors.is_empty() {
qinsoon's avatar
qinsoon committed
671
                trace!("{} is a spilled node", self.display_node(n));
672
673
                self.spilled_nodes.push(n);
            } else {
674
                let first_available_color = ok_colors.pop_front().unwrap();
qinsoon's avatar
qinsoon committed
675
                trace!("Color {} as {}", self.display_node(n), first_available_color);
676
677
                
                if !backend::is_callee_saved(first_available_color) {
qinsoon's avatar
qinsoon committed
678
                    trace!("Use caller saved register {}", first_available_color);
679
680
                }
                
681
                self.colored_nodes.push(n);
qinsoon's avatar
qinsoon committed
682
                self.ig.color_node(n, first_available_color);
683
684
685
            }
        }
        
qinsoon's avatar
qinsoon committed
686
        for n in self.colored_nodes.iter() {
687
688
689
            let n = *n;
            let alias = self.get_alias(n);
            let alias_color = self.ig.get_color_of(alias).unwrap();
qinsoon's avatar
qinsoon committed
690
            
qinsoon's avatar
qinsoon committed
691
692
            trace!("Assign color to {} based on aliased {}", self.display_node(n), self.display_node(alias));
            trace!("Color {} as {}", self.display_node(n), alias_color);
693
694
695
            self.ig.color_node(n, alias_color);
        }
    }
qinsoon's avatar
qinsoon committed
696

qinsoon's avatar
qinsoon committed
697
    fn rewrite_program(&mut self) {
qinsoon's avatar
qinsoon committed
698
699
        let spills = self.spills();

700
        let mut spilled_mem = LinkedHashMap::new();
qinsoon's avatar
qinsoon committed
701
702
703

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

qinsoon's avatar
qinsoon committed
710
711
            spilled_mem.insert(*reg_id, mem.clone());
            self.spill_history.insert(*reg_id, mem);
qinsoon's avatar
qinsoon committed
712
713
        }

qinsoon's avatar
qinsoon committed
714
715
716
717
        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
718
    }
719
720
721
722
723
724
725
726
727
728
729
730
    
    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
731
    }
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760

    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
    }

    pub fn get_spill_history(&self) -> LinkedHashMap<MuID, P<Value>> {
        self.spill_history.clone()
    }
761

qinsoon's avatar
qinsoon committed
762
763
764
765
    pub fn get_spill_scratch_temps(&self) -> LinkedHashMap<MuID, MuID> {
        self.spill_scratch_temps.clone()
    }

766
767
768
769
770
771
772
773
774
775
776
777
778
    pub fn get_coalesced(&self) -> LinkedHashMap<MuID, MuID> {
        let mut ret = LinkedHashMap::new();

        for mov in self.coalesced_moves.iter() {
            let from = self.ig.get_temp_of(mov.from);
            let to   = self.ig.get_temp_of(mov.to);

            ret.insert(from, to);
            ret.insert(to  , from);
        }

        ret
    }
779
}