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 23 KB
Newer Older
1
2
extern crate hprof;

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

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

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

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

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

qinsoon's avatar
qinsoon committed
21
22
23
24
25
pub struct GraphColoring<'a> {
    pub func: &'a mut MuFunctionVersion,
    pub cf: &'a mut CompiledFunction,
    pub vm: &'a VM,

26
    pub ig: InterferenceGraph,
qinsoon's avatar
qinsoon committed
27

28
    precolored: LinkedHashSet<NodeIndex>,
29
    colors: LinkedHashMap<backend::RegGroup, LinkedHashSet<MuID>>,
30
    pub colored_nodes: Vec<NodeIndex>,
qinsoon's avatar
qinsoon committed
31
    
32
    initial: Vec<NodeIndex>,
33
    degree: LinkedHashMap<NodeIndex, usize>,
qinsoon's avatar
qinsoon committed
34
    
35
    worklist_moves: Vec<Move>,
36
    movelist: LinkedHashMap<NodeIndex, RefCell<Vec<Move>>>,
37
    active_moves: LinkedHashSet<Move>,
38
    coalesced_nodes: LinkedHashSet<NodeIndex>,
39
40
    coalesced_moves: LinkedHashSet<Move>,
    constrained_moves: LinkedHashSet<Move>,
41
    alias: LinkedHashMap<NodeIndex, NodeIndex>,
qinsoon's avatar
qinsoon committed
42
    
43
    worklist_spill: Vec<NodeIndex>,
44
    spillable: LinkedHashMap<MuID, bool>,
45
    spilled_nodes: Vec<NodeIndex>,
46
    
47
    worklist_freeze: LinkedHashSet<NodeIndex>,
48
    frozen_moves: LinkedHashSet<Move>,
49
    
50
51
    worklist_simplify: LinkedHashSet<NodeIndex>,
    select_stack: Vec<NodeIndex>
qinsoon's avatar
qinsoon committed
52
53
}

qinsoon's avatar
qinsoon committed
54
impl <'a> GraphColoring<'a> {
55
    pub fn start (func: &'a mut MuFunctionVersion, cf: &'a mut CompiledFunction, vm: &'a VM) -> GraphColoring<'a> {
56
        trace!("Initializing coloring allocator...");
qinsoon's avatar
qinsoon committed
57
58
        cf.mc().trace_mc();

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

61
        let coloring = GraphColoring {
qinsoon's avatar
qinsoon committed
62
63
64
65
66
            func: func,
            cf: cf,
            vm: vm,

            ig: ig,
qinsoon's avatar
qinsoon committed
67

68
            precolored: LinkedHashSet::new(),
69
            colors: {
70
                let mut map = LinkedHashMap::new();
71
72
                map.insert(backend::RegGroup::GPR, LinkedHashSet::new());
                map.insert(backend::RegGroup::FPR, LinkedHashSet::new());
73
74
75
                map
            },
            colored_nodes: Vec::new(),
qinsoon's avatar
qinsoon committed
76
            
77
            initial: Vec::new(),
78
            degree: LinkedHashMap::new(),
qinsoon's avatar
qinsoon committed
79
            
80
            worklist_moves: Vec::new(),
81
            movelist: LinkedHashMap::new(),
82
83
84
85
            active_moves: LinkedHashSet::new(),
            coalesced_nodes: LinkedHashSet::new(),
            coalesced_moves: LinkedHashSet::new(),
            constrained_moves: LinkedHashSet::new(),
86
            alias: LinkedHashMap::new(),
qinsoon's avatar
qinsoon committed
87
            
88
            worklist_spill: Vec::new(),
89
            spillable: LinkedHashMap::new(),
90
91
            spilled_nodes: Vec::new(),
            
92
93
            worklist_freeze: LinkedHashSet::new(),
            frozen_moves: LinkedHashSet::new(),
94
            
95
            worklist_simplify: LinkedHashSet::new(),
96
            select_stack: Vec::new()
qinsoon's avatar
qinsoon committed
97
98
        };
        
qinsoon's avatar
qinsoon committed
99
        coloring.regalloc()
qinsoon's avatar
qinsoon committed
100
    }
qinsoon's avatar
qinsoon committed
101

102
    fn display_node(&self, node: NodeIndex) -> String {
qinsoon's avatar
qinsoon committed
103
104
105
106
107
108
109
110
111
112
113
        let id = self.ig.get_temp_of(node);
        self.display_id(id)
    }

    fn display_id(&self, id: MuID) -> String {
        self.func.context.get_temp_display(id)
    }

    fn display_move(&self, m: Move) -> String {
        format!("Move: {} -> {}", self.display_node(m.from), self.display_node(m.to))
    }
qinsoon's avatar
qinsoon committed
114
    
115
    fn regalloc(mut self) -> GraphColoring<'a> {
qinsoon's avatar
qinsoon committed
116
        trace!("---InterenceGraph---");
117
118
        let _p = hprof::enter("regalloc: graph coloring");

qinsoon's avatar
qinsoon committed
119
        self.ig.print(&self.func.context);
qinsoon's avatar
qinsoon committed
120
        
qinsoon's avatar
qinsoon committed
121
        // precolor for all machine registers
122
        for reg in backend::all_regs().values() {
123
124
125
126
127
            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
128
        // put usable registers as available colors
129
        for reg in backend::all_usable_regs().iter() {
qinsoon's avatar
qinsoon committed
130
            let reg_id = reg.extract_ssa_id().unwrap();
qinsoon's avatar
qinsoon committed
131
132
            let group = backend::pick_group_for_reg(reg_id);
            self.colors.get_mut(&group).unwrap().insert(reg_id);
qinsoon's avatar
qinsoon committed
133
134
135
136
        }
        
        for node in self.ig.nodes() {
            if !self.ig.is_colored(node) {
137
                self.initial.push(node);
138
                let outdegree = self.ig.outdegree_of(node);
139
                self.degree.insert(node, outdegree);
qinsoon's avatar
qinsoon committed
140

qinsoon's avatar
qinsoon committed
141
                trace!("{} has a degree of {}", self.display_node(node), outdegree);
qinsoon's avatar
qinsoon committed
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
            }
        }
        
        self.build();
        self.make_work_list();
        
        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
165
166
        self.assign_colors();

167
168
        drop(_p);

qinsoon's avatar
qinsoon committed
169
170
        if !self.spilled_nodes.is_empty() {
            trace!("spill required");
qinsoon's avatar
qinsoon committed
171
172
173
            if cfg!(debug_assertions) {
                trace!("nodes to be spilled:");
                for node in self.spilled_nodes.iter() {
qinsoon's avatar
qinsoon committed
174
                    trace!("{}", self.display_node(*node));
qinsoon's avatar
qinsoon committed
175
176
177
                }
            }

qinsoon's avatar
qinsoon committed
178
            self.rewrite_program();
qinsoon's avatar
qinsoon committed
179

qinsoon's avatar
qinsoon committed
180
            return GraphColoring::start(self.func, self.cf, self.vm);
qinsoon's avatar
qinsoon committed
181
182
        }

183
        self
qinsoon's avatar
qinsoon committed
184
185
186
    }
    
    fn build(&mut self) {
qinsoon's avatar
qinsoon committed
187
188
        if COALESCING {
            trace!("coalescing enabled, build move list");
qinsoon's avatar
qinsoon committed
189
190
            let ref ig = self.ig;
            let ref mut movelist = self.movelist;
191
            for m in ig.moves().iter() {
qinsoon's avatar
qinsoon committed
192
                trace!("add to movelist: {:?}", m);
193
                self.worklist_moves.push(m.clone());
qinsoon's avatar
qinsoon committed
194
195
                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
196
            }
qinsoon's avatar
qinsoon committed
197
198
        } else {
            trace!("coalescing disabled");
qinsoon's avatar
qinsoon committed
199
200
201
202
        }
    }
    
    fn make_work_list(&mut self) {
203
        trace!("Making work list from initials...");
qinsoon's avatar
qinsoon committed
204
        while !self.initial.is_empty() {
205
            let node = self.initial.pop().unwrap();
qinsoon's avatar
qinsoon committed
206
207
208
209
            
            if {
                // condition: degree >= K
                let degree = self.ig.degree_of(node); 
210
                let n_regs = self.n_regs_for_node(node);
qinsoon's avatar
qinsoon committed
211
212
213
                
                degree >= n_regs
            } {
qinsoon's avatar
qinsoon committed
214
                trace!("{} 's degree >= reg number limit (K), push to spill list", self.display_node(node));
215
                self.worklist_spill.push(node);
qinsoon's avatar
qinsoon committed
216
            } else if self.is_move_related(node) {
qinsoon's avatar
qinsoon committed
217
                trace!("{} is move related, push to freeze list", self.display_node(node));
qinsoon's avatar
qinsoon committed
218
219
                self.worklist_freeze.insert(node);
            } else {
qinsoon's avatar
qinsoon committed
220
                trace!("{} has small degree and not move related, push to simplify list", self.display_node(node));
qinsoon's avatar
qinsoon committed
221
222
223
224
225
                self.worklist_simplify.insert(node);
            }
        }
    }
    
226
    fn n_regs_for_node(&self, node: NodeIndex) -> usize {
227
228
229
        backend::number_of_regs_in_group(self.ig.get_group_of(node))
    }
    
230
    fn is_move_related(&mut self, node: NodeIndex) -> bool {
qinsoon's avatar
qinsoon committed
231
232
233
        !self.node_moves(node).is_empty()
    }
    
234
    fn node_moves(&mut self, node: NodeIndex) -> LinkedHashSet<Move> {
235
        let mut moves = LinkedHashSet::new();
qinsoon's avatar
qinsoon committed
236
237
238
239
240
241
242
243
244
245
246
        
        // 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());
        }
        
247
        let mut retained = LinkedHashSet::new();
qinsoon's avatar
qinsoon committed
248
        let movelist = &GraphColoring::movelist_mut(&mut self.movelist, node).borrow();
qinsoon's avatar
qinsoon committed
249
        for m in moves.iter() {
250
            if vec_utils::find_value(movelist, *m).is_some() {
qinsoon's avatar
qinsoon committed
251
252
253
254
255
256
257
                retained.insert(*m);
            }
        }
        
        retained
    }
    
qinsoon's avatar
qinsoon committed
258
259
260
    // 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)
261
    fn movelist_mut(list: &mut LinkedHashMap<NodeIndex, RefCell<Vec<Move>>>, node: NodeIndex) -> &RefCell<Vec<Move>> {
qinsoon's avatar
qinsoon committed
262
263
264
265
        GraphColoring::movelist_check(list, node);
        unsafe {GraphColoring::movelist_nocheck(list, node)}
    }
    
266
    fn movelist_check(list: &mut LinkedHashMap<NodeIndex, RefCell<Vec<Move>>>, node: NodeIndex) {
qinsoon's avatar
qinsoon committed
267
        if !list.contains_key(&node) {
qinsoon's avatar
qinsoon committed
268
            list.insert(node, RefCell::new(Vec::new()));
qinsoon's avatar
qinsoon committed
269
        }
qinsoon's avatar
qinsoon committed
270
271
272
    }
    
    // allows getting the Vec<Move> without a mutable reference of the hashmap
273
    unsafe fn movelist_nocheck(list: &LinkedHashMap<NodeIndex, RefCell<Vec<Move>>>, node: NodeIndex) -> &RefCell<Vec<Move>> {
qinsoon's avatar
qinsoon committed
274
        list.get(&node).unwrap()
qinsoon's avatar
qinsoon committed
275
    }
276
277
    
    fn simplify(&mut self) {
278
        // remove next element from worklist_simplify, we know its not empty
279
        let node = self.worklist_simplify.pop_front().unwrap();
280
        
qinsoon's avatar
qinsoon committed
281
        trace!("Simplifying {}", self.display_node(node));
282
283
284
        
        self.select_stack.push(node);
        
285
        for m in self.adjacent(node).iter() {
286
            self.decrement_degree(*m);
287
288
289
        }
    }
    
290
    fn adjacent(&self, n: NodeIndex) -> LinkedHashSet<NodeIndex> {
291
        let mut adj = LinkedHashSet::new();
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
        
        // add n's successors
        for s in self.ig.outedges_of(n) {
            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
    }
    
311
    fn degree(&self, n: NodeIndex) -> usize {
312
313
314
315
316
317
        match self.degree.get(&n) {
            Some(d) => *d,
            None => 0
        }
    }
    
318
    fn decrement_degree(&mut self, n: NodeIndex) {
319
320
321
322
        if self.precolored.contains(&n) {
            return;
        }
        
qinsoon's avatar
qinsoon committed
323
        trace!("decrement degree of {}", self.display_node(n));
324
        
325
        let d = self.degree(n);
326
        debug_assert!(d != 0);
327
328
        self.degree.insert(n, d - 1);
        
329
        if d == self.n_regs_for_node(n) {
qinsoon's avatar
qinsoon committed
330
            trace!("{}'s degree is K, no longer need to spill it", self.display_node(n));
331
332
            let mut nodes = self.adjacent(n);
            nodes.insert(n);
qinsoon's avatar
qinsoon committed
333
            trace!("enable moves of {:?}", nodes);
334
335
336
337
338
            self.enable_moves(nodes);
            
            vec_utils::remove_value(&mut self.worklist_spill, n);
            
            if self.is_move_related(n) {
qinsoon's avatar
qinsoon committed
339
                trace!("{} is move related, push to freeze list", self.display_node(n));
340
341
                self.worklist_freeze.insert(n);
            } else {
qinsoon's avatar
qinsoon committed
342
                trace!("{} is not move related, push to simplify list", self.display_node(n));
343
344
345
346
347
                self.worklist_simplify.insert(n);
            }
        }
    }
    
348
    fn enable_moves(&mut self, nodes: LinkedHashSet<NodeIndex>) {
349
350
351
352
        for n in nodes.iter() {
            let n = *n;
            for mov in self.node_moves(n).iter() {
                let mov = *mov;
353
354
355
356
357
358
359
360
361
                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
362
363
        let m = self.worklist_moves.pop().unwrap();
        
qinsoon's avatar
qinsoon committed
364
        trace!("Coalescing on {}", self.display_move(m));
qinsoon's avatar
qinsoon committed
365
366
367

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

qinsoon's avatar
qinsoon committed
371
372
            return;
        }
qinsoon's avatar
qinsoon committed
373
        
qinsoon's avatar
qinsoon committed
374
375
        let x = self.get_alias(m.from);
        let y = self.get_alias(m.to);
qinsoon's avatar
qinsoon committed
376
        trace!("resolve alias: from {} to {}", self.display_node(x), self.display_node(y));
qinsoon's avatar
qinsoon committed
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
        
        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
395
        trace!("u={}, v={}, precolored_u={}, precolroed_v={}", 
qinsoon's avatar
qinsoon committed
396
397
            self.display_node(u),
            self.display_node(v),
qinsoon's avatar
qinsoon committed
398
            precolored_u, precolored_v);
qinsoon's avatar
qinsoon committed
399
400
        
        if u == v {
qinsoon's avatar
qinsoon committed
401
            trace!("u == v, coalesce the move");
qinsoon's avatar
qinsoon committed
402
403
404
405
406
            self.coalesced_moves.insert(m);
            if !precolored_u {
                self.add_worklist(u);
            }
        } else if precolored_v || self.ig.is_adj(u, v) {
407
408
            trace!("precolored_v: {}", precolored_v);
            trace!("is_adj(u, v): {}", self.ig.is_adj(u, v));
qinsoon's avatar
qinsoon committed
409
410
            trace!("v is precolored or u,v is adjacent, the move is constrained");
            self.constrained_moves.insert(m);
qinsoon's avatar
qinsoon committed
411
412
413
414
415
416
417
418
            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
419
420
421
422
            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
423
424
425
426
427
428
            self.coalesced_moves.insert(m);
            self.combine(u, v);
            if !precolored_u {
                self.add_worklist(u);
            }
        } else {
qinsoon's avatar
qinsoon committed
429
            trace!("cannot coalesce the move");
qinsoon's avatar
qinsoon committed
430
431
432
433
            self.active_moves.insert(m);
        }
    }
    
434
    pub fn get_alias(&self, node: NodeIndex) -> NodeIndex {
qinsoon's avatar
qinsoon committed
435
436
437
438
439
440
441
        if self.coalesced_nodes.contains(&node) {
            self.get_alias(*self.alias.get(&node).unwrap())
        } else {
            node
        }
    }
    
442
    fn add_worklist(&mut self, node: NodeIndex) {
443
        if !self.is_move_related(node) && self.degree(node) < self.n_regs_for_node(node) {
qinsoon's avatar
qinsoon committed
444
445
446
447
448
            self.worklist_freeze.remove(&node);
            self.worklist_simplify.insert(node);
        }
    }
    
449
    fn ok(&self, u: NodeIndex, v: NodeIndex) -> bool {
450
451
        for t in self.adjacent(v).iter() {
            let t = *t;
452
453
454
            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
455
                return false;
456
            }
qinsoon's avatar
qinsoon committed
457
458
459
460
461
        }
        
        true
    }
    
462
    fn conservative(&self, u: NodeIndex, v: NodeIndex) -> bool {
qinsoon's avatar
qinsoon committed
463
464
        let adj_u = self.adjacent(u);
        let adj_v = self.adjacent(v);
465
466
467
468
469
        let nodes = {
            let mut ret = adj_u;
            ret.add_all(adj_v);
            ret
        };
qinsoon's avatar
qinsoon committed
470
471
        
        let mut k = 0;
472
        for n in nodes.iter() {
qinsoon's avatar
qinsoon committed
473
            if self.precolored.contains(n) || self.degree(*n) >= self.n_regs_for_node(*n) {
qinsoon's avatar
qinsoon committed
474
475
476
477
                k += 1;
            }
        }
        
qinsoon's avatar
qinsoon committed
478
        k < self.n_regs_for_node(u) && k < self.n_regs_for_node(v)
qinsoon's avatar
qinsoon committed
479
480
    }
    
481
    fn combine(&mut self, u: NodeIndex, v: NodeIndex) {
qinsoon's avatar
qinsoon committed
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
        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());
        }
        
506
        let mut nodes = LinkedHashSet::new();
qinsoon's avatar
qinsoon committed
507
508
509
        nodes.insert(v);
        self.enable_moves(nodes);
        
510
511
        for t in self.adjacent(v).iter() {
            let t = *t;
qinsoon's avatar
qinsoon committed
512
513
514
515
516
            self.add_edge(t, u);
            self.decrement_degree(t);
        }
        
        if self.worklist_freeze.contains(&u)
517
          && self.degree(u) >= self.n_regs_for_node(u) {
qinsoon's avatar
qinsoon committed
518
519
520
521
522
            self.worklist_freeze.remove(&u);
            self.worklist_spill.push(u);
        }
    }
    
523
    fn add_edge(&mut self, u: NodeIndex, v: NodeIndex) {
qinsoon's avatar
qinsoon committed
524
525
526
527
528
529
530
531
532
533
534
535
        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);
            }
        }
536
537
538
    }
    
    fn freeze(&mut self) {
qinsoon's avatar
qinsoon committed
539
        // it is not empty (checked before)
540
        let node = self.worklist_freeze.pop_front().unwrap();
qinsoon's avatar
qinsoon committed
541
        trace!("Freezing {}...", self.display_node(node));
qinsoon's avatar
qinsoon committed
542
543
544
545
546
        
        self.worklist_simplify.insert(node);
        self.freeze_moves(node);
    }
    
547
    fn freeze_moves(&mut self, u: NodeIndex) {
548
549
        for m in self.node_moves(u).iter() {
            let m = *m;
qinsoon's avatar
qinsoon committed
550
551
552
553
554
555
556
557
558
559
            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()
560
               && self.degree(v) < self.n_regs_for_node(v) {
qinsoon's avatar
qinsoon committed
561
562
563
564
                self.worklist_freeze.remove(&v);
                self.worklist_simplify.insert(v);
            }
        }
565
566
567
    }
    
    fn select_spill(&mut self) {
qinsoon's avatar
qinsoon committed
568
        trace!("Selecting a node to spill...");
569
        let mut m : Option<NodeIndex> = None;
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
        
        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
597
        trace!("Spilling {}...", self.display_node(m));
qinsoon's avatar
qinsoon committed
598
        
599
600
601
        vec_utils::remove_value(&mut self.worklist_spill, m);
        self.worklist_simplify.insert(m);
        self.freeze_moves(m);
602
603
    }
    
604
    fn assign_colors(&mut self) {
qinsoon's avatar
qinsoon committed
605
        trace!("---coloring done---");
606
607
        while !self.select_stack.is_empty() {
            let n = self.select_stack.pop().unwrap();
qinsoon's avatar
qinsoon committed
608
            trace!("Assigning color to {}", self.display_node(n));
609
            
610
            let mut ok_colors : LinkedHashSet<MuID> = self.colors.get(&self.ig.get_group_of(n)).unwrap().clone();
qinsoon's avatar
qinsoon committed
611
612
613

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

614
            for w in self.ig.outedges_of(n) {
qinsoon's avatar
qinsoon committed
615
616
                let w_alias = self.get_alias(w);
                match self.ig.get_color_of(w_alias) {
617
                    None => {}, // do nothing
qinsoon's avatar
qinsoon committed
618
619
620
621
                    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);
                    }
622
623
                }
            }
qinsoon's avatar
qinsoon committed
624
            trace!("available colors: {:?}", ok_colors);
625
626
            
            if ok_colors.is_empty() {
qinsoon's avatar
qinsoon committed
627
                trace!("{} is a spilled node", self.display_node(n));
628
629
                self.spilled_nodes.push(n);
            } else {
630
                let first_available_color = ok_colors.pop_front().unwrap();
qinsoon's avatar
qinsoon committed
631
                trace!("Color {} as {}", self.display_node(n), first_available_color);
632
633
                
                if !backend::is_callee_saved(first_available_color) {
634
                    warn!("Use caller saved register {}", first_available_color);
635
636
                }
                
637
                self.colored_nodes.push(n);
qinsoon's avatar
qinsoon committed
638
                self.ig.color_node(n, first_available_color);
639
640
641
            }
        }
        
qinsoon's avatar
qinsoon committed
642
        for n in self.colored_nodes.iter() {
643
644
645
            let n = *n;
            let alias = self.get_alias(n);
            let alias_color = self.ig.get_color_of(alias).unwrap();
qinsoon's avatar
qinsoon committed
646
            
qinsoon's avatar
qinsoon committed
647
648
            trace!("Assign color to {} based on aliased {}", self.display_node(n), self.display_node(alias));
            trace!("Color {} as {}", self.display_node(n), alias_color);
649
650
651
            self.ig.color_node(n, alias_color);
        }
    }
qinsoon's avatar
qinsoon committed
652

qinsoon's avatar
qinsoon committed
653
    #[allow(unused_variables)]
qinsoon's avatar
qinsoon committed
654
    fn rewrite_program(&mut self) {
qinsoon's avatar
qinsoon committed
655
656
        let spills = self.spills();

657
        let mut spilled_mem = LinkedHashMap::new();
qinsoon's avatar
qinsoon committed
658
659
660

        // allocating frame slots for every spilled temp
        for reg_id in spills.iter() {
qinsoon's avatar
qinsoon committed
661
            let ssa_entry = match self.func.context.get_value(*reg_id) {
qinsoon's avatar
qinsoon committed
662
663
664
                Some(entry) => entry,
                None => panic!("The spilled register {} is not in func context", reg_id)
            };
qinsoon's avatar
qinsoon committed
665
            let mem = self.cf.frame.alloc_slot_for_spilling(ssa_entry.value().clone(), self.vm);
qinsoon's avatar
qinsoon committed
666
667
668
669

            spilled_mem.insert(*reg_id, mem);
        }

qinsoon's avatar
qinsoon committed
670
        // though we are not using this right now
qinsoon's avatar
qinsoon committed
671
        let new_temps = backend::spill_rewrite(&spilled_mem, self.func, self.cf, self.vm);
qinsoon's avatar
qinsoon committed
672
    }
673
674
675
676
677
678
679
680
681
682
683
684
    
    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
685
    }
686
}