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 22 KB
Newer Older
qinsoon's avatar
qinsoon committed
1
2
3
use ast::ir::*;
use compiler::backend;
use compiler::backend::reg_alloc::graph_coloring;
4
use compiler::backend::reg_alloc::graph_coloring::liveness::InterferenceGraph;
qinsoon's avatar
qinsoon committed
5
6
use compiler::machine_code::CompiledFunction;
use vm::VM;
7

8
use utils::vec_utils;
9
use utils::LinkedHashSet;
qinsoon's avatar
qinsoon committed
10

qinsoon's avatar
qinsoon committed
11
use std::cell::RefCell;
qinsoon's avatar
qinsoon committed
12
13
use std::collections::HashMap;

14
15
16
use compiler::backend::reg_alloc::graph_coloring::liveness::Move;
use compiler::backend::reg_alloc::graph_coloring::petgraph::graph::NodeIndex;

qinsoon's avatar
qinsoon committed
17
const COALESCING : bool = true;
18

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

24
    pub ig: InterferenceGraph,
qinsoon's avatar
qinsoon committed
25

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

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

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

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

            ig: ig,
qinsoon's avatar
qinsoon committed
65

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

100
    fn display_node(&self, node: NodeIndex) -> String {
qinsoon's avatar
qinsoon committed
101
102
103
104
105
106
107
108
109
110
111
        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
112
    
113
    fn regalloc(mut self) -> GraphColoring<'a> {
qinsoon's avatar
qinsoon committed
114
        trace!("---InterenceGraph---");
qinsoon's avatar
qinsoon committed
115
        self.ig.print(&self.func.context);
qinsoon's avatar
qinsoon committed
116
        
qinsoon's avatar
qinsoon committed
117
        // precolor for all machine registers
118
        for reg in backend::all_regs().values() {
119
120
121
122
123
            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
124
        // put usable registers as available colors
125
        for reg in backend::all_usable_regs().iter() {
qinsoon's avatar
qinsoon committed
126
            let reg_id = reg.extract_ssa_id().unwrap();
qinsoon's avatar
qinsoon committed
127
128
            let group = backend::pick_group_for_reg(reg_id);
            self.colors.get_mut(&group).unwrap().insert(reg_id);
qinsoon's avatar
qinsoon committed
129
130
131
132
        }
        
        for node in self.ig.nodes() {
            if !self.ig.is_colored(node) {
133
                self.initial.push(node);
134
                let outdegree = self.ig.outdegree_of(node);
135
                self.degree.insert(node, outdegree);
qinsoon's avatar
qinsoon committed
136

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

        if !self.spilled_nodes.is_empty() {
            trace!("spill required");
qinsoon's avatar
qinsoon committed
165
166
167
            if cfg!(debug_assertions) {
                trace!("nodes to be spilled:");
                for node in self.spilled_nodes.iter() {
qinsoon's avatar
qinsoon committed
168
                    trace!("{}", self.display_node(*node));
qinsoon's avatar
qinsoon committed
169
170
171
                }
            }

qinsoon's avatar
qinsoon committed
172
            self.rewrite_program();
qinsoon's avatar
qinsoon committed
173

qinsoon's avatar
qinsoon committed
174
            return GraphColoring::start(self.func, self.cf, self.vm);
qinsoon's avatar
qinsoon committed
175
176
        }

177
        self
qinsoon's avatar
qinsoon committed
178
179
180
    }
    
    fn build(&mut self) {
qinsoon's avatar
qinsoon committed
181
182
        if COALESCING {
            trace!("coalescing enabled, build move list");
qinsoon's avatar
qinsoon committed
183
184
185
            let ref ig = self.ig;
            let ref mut movelist = self.movelist;
            for m in ig.moves() {
qinsoon's avatar
qinsoon committed
186
                trace!("add to movelist: {:?}", m);
187
                self.worklist_moves.push(m.clone());
qinsoon's avatar
qinsoon committed
188
189
                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
190
            }
qinsoon's avatar
qinsoon committed
191
192
        } else {
            trace!("coalescing disabled");
qinsoon's avatar
qinsoon committed
193
194
195
196
        }
    }
    
    fn make_work_list(&mut self) {
197
        trace!("Making work list from initials...");
qinsoon's avatar
qinsoon committed
198
        while !self.initial.is_empty() {
199
            let node = self.initial.pop().unwrap();
qinsoon's avatar
qinsoon committed
200
201
202
203
            
            if {
                // condition: degree >= K
                let degree = self.ig.degree_of(node); 
204
                let n_regs = self.n_regs_for_node(node);
qinsoon's avatar
qinsoon committed
205
206
207
                
                degree >= n_regs
            } {
qinsoon's avatar
qinsoon committed
208
                trace!("{} 's degree >= reg number limit (K), push to spill list", self.display_node(node));
209
                self.worklist_spill.push(node);
qinsoon's avatar
qinsoon committed
210
            } else if self.is_move_related(node) {
qinsoon's avatar
qinsoon committed
211
                trace!("{} is move related, push to freeze list", self.display_node(node));
qinsoon's avatar
qinsoon committed
212
213
                self.worklist_freeze.insert(node);
            } else {
qinsoon's avatar
qinsoon committed
214
                trace!("{} has small degree and not move related, push to simplify list", self.display_node(node));
qinsoon's avatar
qinsoon committed
215
216
217
218
219
                self.worklist_simplify.insert(node);
            }
        }
    }
    
220
    fn n_regs_for_node(&self, node: NodeIndex) -> usize {
221
222
223
        backend::number_of_regs_in_group(self.ig.get_group_of(node))
    }
    
224
    fn is_move_related(&mut self, node: NodeIndex) -> bool {
qinsoon's avatar
qinsoon committed
225
226
227
        !self.node_moves(node).is_empty()
    }
    
228
    fn node_moves(&mut self, node: NodeIndex) -> LinkedHashSet<Move> {
229
        let mut moves = LinkedHashSet::new();
qinsoon's avatar
qinsoon committed
230
231
232
233
234
235
236
237
238
239
240
        
        // 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());
        }
        
241
        let mut retained = LinkedHashSet::new();
qinsoon's avatar
qinsoon committed
242
        let movelist = &GraphColoring::movelist_mut(&mut self.movelist, node).borrow();
qinsoon's avatar
qinsoon committed
243
        for m in moves.iter() {
244
            if vec_utils::find_value(movelist, *m).is_some() {
qinsoon's avatar
qinsoon committed
245
246
247
248
249
250
251
                retained.insert(*m);
            }
        }
        
        retained
    }
    
qinsoon's avatar
qinsoon committed
252
253
254
    // 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)
255
    fn movelist_mut(list: &mut HashMap<NodeIndex, RefCell<Vec<Move>>>, node: NodeIndex) -> &RefCell<Vec<Move>> {
qinsoon's avatar
qinsoon committed
256
257
258
259
        GraphColoring::movelist_check(list, node);
        unsafe {GraphColoring::movelist_nocheck(list, node)}
    }
    
260
    fn movelist_check(list: &mut HashMap<NodeIndex, RefCell<Vec<Move>>>, node: NodeIndex) {
qinsoon's avatar
qinsoon committed
261
        if !list.contains_key(&node) {
qinsoon's avatar
qinsoon committed
262
            list.insert(node, RefCell::new(Vec::new()));
qinsoon's avatar
qinsoon committed
263
        }
qinsoon's avatar
qinsoon committed
264
265
266
    }
    
    // allows getting the Vec<Move> without a mutable reference of the hashmap
267
    unsafe fn movelist_nocheck(list: &HashMap<NodeIndex, RefCell<Vec<Move>>>, node: NodeIndex) -> &RefCell<Vec<Move>> {
qinsoon's avatar
qinsoon committed
268
        list.get(&node).unwrap()
qinsoon's avatar
qinsoon committed
269
    }
270
271
    
    fn simplify(&mut self) {
272
        // remove next element from worklist_simplify, we know its not empty
273
        let node = self.worklist_simplify.pop_front().unwrap();
274
        
qinsoon's avatar
qinsoon committed
275
        trace!("Simplifying {}", self.display_node(node));
276
277
278
        
        self.select_stack.push(node);
        
279
        for m in self.adjacent(node).iter() {
280
            self.decrement_degree(*m);
281
282
283
        }
    }
    
284
    fn adjacent(&self, n: NodeIndex) -> LinkedHashSet<NodeIndex> {
285
        let mut adj = LinkedHashSet::new();
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
        
        // 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
    }
    
305
    fn degree(&self, n: NodeIndex) -> usize {
306
307
308
309
310
311
        match self.degree.get(&n) {
            Some(d) => *d,
            None => 0
        }
    }
    
312
    fn decrement_degree(&mut self, n: NodeIndex) {
313
314
315
316
        if self.precolored.contains(&n) {
            return;
        }
        
qinsoon's avatar
qinsoon committed
317
        trace!("decrement degree of {}", self.display_node(n));
318
        
319
        let d = self.degree(n);
320
        debug_assert!(d != 0);
321
322
        self.degree.insert(n, d - 1);
        
323
        if d == self.n_regs_for_node(n) {
qinsoon's avatar
qinsoon committed
324
            trace!("{}'s degree is K, no longer need to spill it", self.display_node(n));
325
326
            let mut nodes = self.adjacent(n);
            nodes.insert(n);
qinsoon's avatar
qinsoon committed
327
            trace!("enable moves of {:?}", nodes);
328
329
330
331
332
            self.enable_moves(nodes);
            
            vec_utils::remove_value(&mut self.worklist_spill, n);
            
            if self.is_move_related(n) {
qinsoon's avatar
qinsoon committed
333
                trace!("{} is move related, push to freeze list", self.display_node(n));
334
335
                self.worklist_freeze.insert(n);
            } else {
qinsoon's avatar
qinsoon committed
336
                trace!("{} is not move related, push to simplify list", self.display_node(n));
337
338
339
340
341
                self.worklist_simplify.insert(n);
            }
        }
    }
    
342
    fn enable_moves(&mut self, nodes: LinkedHashSet<NodeIndex>) {
343
344
345
346
        for n in nodes.iter() {
            let n = *n;
            for mov in self.node_moves(n).iter() {
                let mov = *mov;
347
348
349
350
351
352
353
354
355
                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
356
357
        let m = self.worklist_moves.pop().unwrap();
        
qinsoon's avatar
qinsoon committed
358
        trace!("Coalescing on {}", self.display_move(m));
qinsoon's avatar
qinsoon committed
359
        
qinsoon's avatar
qinsoon committed
360
361
        let x = self.get_alias(m.from);
        let y = self.get_alias(m.to);
qinsoon's avatar
qinsoon committed
362
        trace!("resolve alias: from {} to {}", self.display_node(x), self.display_node(y));
qinsoon's avatar
qinsoon committed
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
        
        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
381
        trace!("u={}, v={}, precolored_u={}, precolroed_v={}", 
qinsoon's avatar
qinsoon committed
382
383
            self.display_node(u),
            self.display_node(v),
qinsoon's avatar
qinsoon committed
384
            precolored_u, precolored_v);
qinsoon's avatar
qinsoon committed
385
386
        
        if u == v {
qinsoon's avatar
qinsoon committed
387
            trace!("u == v, coalesce the move");
qinsoon's avatar
qinsoon committed
388
389
390
391
392
            self.coalesced_moves.insert(m);
            if !precolored_u {
                self.add_worklist(u);
            }
        } else if precolored_v || self.ig.is_adj(u, v) {
qinsoon's avatar
qinsoon committed
393
394
            trace!("v is precolored or u,v is adjacent, the move is constrained");
            self.constrained_moves.insert(m);
qinsoon's avatar
qinsoon committed
395
396
397
398
399
400
401
402
            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
403
            trace!("precolored_u&&ok(u,v) || !precolored_u&&conserv(u,v), coalesce and combine the move");  
qinsoon's avatar
qinsoon committed
404
405
406
407
408
409
            self.coalesced_moves.insert(m);
            self.combine(u, v);
            if !precolored_u {
                self.add_worklist(u);
            }
        } else {
qinsoon's avatar
qinsoon committed
410
            trace!("cannot coalesce the move");
qinsoon's avatar
qinsoon committed
411
412
413
414
            self.active_moves.insert(m);
        }
    }
    
415
    pub fn get_alias(&self, node: NodeIndex) -> NodeIndex {
qinsoon's avatar
qinsoon committed
416
417
418
419
420
421
422
        if self.coalesced_nodes.contains(&node) {
            self.get_alias(*self.alias.get(&node).unwrap())
        } else {
            node
        }
    }
    
423
    fn add_worklist(&mut self, node: NodeIndex) {
424
        if !self.is_move_related(node) && self.degree(node) < self.n_regs_for_node(node) {
qinsoon's avatar
qinsoon committed
425
426
427
428
429
            self.worklist_freeze.remove(&node);
            self.worklist_simplify.insert(node);
        }
    }
    
430
    fn ok(&self, u: NodeIndex, v: NodeIndex) -> bool {
431
432
        for t in self.adjacent(v).iter() {
            let t = *t;
qinsoon's avatar
qinsoon committed
433
            if !self.precolored.contains(&t) 
434
              || self.degree(t) < self.n_regs_for_node(t)
qinsoon's avatar
qinsoon committed
435
436
437
438
439
440
441
442
              || self.ig.is_adj(t, u) {
                return false;
            } 
        }
        
        true
    }
    
443
    fn conservative(&self, u: NodeIndex, v: NodeIndex) -> bool {
qinsoon's avatar
qinsoon committed
444
445
446
447
        debug_assert!(self.ig.get_group_of(u) == self.ig.get_group_of(v));
        
        let adj_u = self.adjacent(u);
        let adj_v = self.adjacent(v);
448
449
450
451
452
        let nodes = {
            let mut ret = adj_u;
            ret.add_all(adj_v);
            ret
        };
qinsoon's avatar
qinsoon committed
453
454
        
        let mut k = 0;
455
        for n in nodes.iter() {
456
            if self.precolored.contains(n) || self.degree(*n) >= self.n_regs_for_node(*n) {
qinsoon's avatar
qinsoon committed
457
458
459
460
461
462
463
                k += 1;
            }
        }
        
        k < self.n_regs_for_node(u)
    }
    
464
    fn combine(&mut self, u: NodeIndex, v: NodeIndex) {
qinsoon's avatar
qinsoon committed
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
        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());
        }
        
489
        let mut nodes = LinkedHashSet::new();
qinsoon's avatar
qinsoon committed
490
491
492
        nodes.insert(v);
        self.enable_moves(nodes);
        
493
494
        for t in self.adjacent(v).iter() {
            let t = *t;
qinsoon's avatar
qinsoon committed
495
496
497
498
499
            self.add_edge(t, u);
            self.decrement_degree(t);
        }
        
        if self.worklist_freeze.contains(&u)
500
          && self.degree(u) >= self.n_regs_for_node(u) {
qinsoon's avatar
qinsoon committed
501
502
503
504
505
            self.worklist_freeze.remove(&u);
            self.worklist_spill.push(u);
        }
    }
    
506
    fn add_edge(&mut self, u: NodeIndex, v: NodeIndex) {
qinsoon's avatar
qinsoon committed
507
508
509
510
511
512
513
514
515
516
517
518
        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);
            }
        }
519
520
521
    }
    
    fn freeze(&mut self) {
qinsoon's avatar
qinsoon committed
522
        // it is not empty (checked before)
523
        let node = self.worklist_freeze.pop_front().unwrap();
qinsoon's avatar
qinsoon committed
524
        trace!("Freezing {}...", self.display_node(node));
qinsoon's avatar
qinsoon committed
525
526
527
528
529
        
        self.worklist_simplify.insert(node);
        self.freeze_moves(node);
    }
    
530
    fn freeze_moves(&mut self, u: NodeIndex) {
531
532
        for m in self.node_moves(u).iter() {
            let m = *m;
qinsoon's avatar
qinsoon committed
533
534
535
536
537
538
539
540
541
542
            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()
543
               && self.degree(v) < self.n_regs_for_node(v) {
qinsoon's avatar
qinsoon committed
544
545
546
547
                self.worklist_freeze.remove(&v);
                self.worklist_simplify.insert(v);
            }
        }
548
549
550
    }
    
    fn select_spill(&mut self) {
qinsoon's avatar
qinsoon committed
551
        trace!("Selecting a node to spill...");
552
        let mut m : Option<NodeIndex> = None;
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
        
        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
580
        trace!("Spilling {}...", self.display_node(m));
qinsoon's avatar
qinsoon committed
581
        
582
583
584
        vec_utils::remove_value(&mut self.worklist_spill, m);
        self.worklist_simplify.insert(m);
        self.freeze_moves(m);
585
586
    }
    
587
    fn assign_colors(&mut self) {
qinsoon's avatar
qinsoon committed
588
        trace!("---coloring done---");
589
590
        while !self.select_stack.is_empty() {
            let n = self.select_stack.pop().unwrap();
qinsoon's avatar
qinsoon committed
591
            trace!("Assigning color to {}", self.display_node(n));
592
            
593
            let mut ok_colors : LinkedHashSet<MuID> = self.colors.get(&self.ig.get_group_of(n)).unwrap().clone();
594
595
596
597
598
599
600
            for w in self.ig.outedges_of(n) {
                let w = self.get_alias(w);
                match self.ig.get_color_of(w) {
                    None => {}, // do nothing
                    Some(color) => {ok_colors.remove(&color);}
                }
            }
qinsoon's avatar
qinsoon committed
601
            trace!("available colors: {:?}", ok_colors);
602
603
            
            if ok_colors.is_empty() {
qinsoon's avatar
qinsoon committed
604
                trace!("{} is a spilled node", self.display_node(n));
605
606
                self.spilled_nodes.push(n);
            } else {
607
                let first_available_color = ok_colors.pop_front().unwrap();
qinsoon's avatar
qinsoon committed
608
                trace!("Color {} as {}", self.display_node(n), first_available_color);
609
610
                
                if !backend::is_callee_saved(first_available_color) {
611
                    warn!("Use caller saved register {}", first_available_color);
612
613
                }
                
614
                self.colored_nodes.push(n);
qinsoon's avatar
qinsoon committed
615
                self.ig.color_node(n, first_available_color);
616
617
618
            }
        }
        
qinsoon's avatar
qinsoon committed
619
        for n in self.colored_nodes.iter() {
620
621
622
            let n = *n;
            let alias = self.get_alias(n);
            let alias_color = self.ig.get_color_of(alias).unwrap();
qinsoon's avatar
qinsoon committed
623
            
qinsoon's avatar
qinsoon committed
624
625
            trace!("Assign color to {} based on aliased {}", self.display_node(n), self.display_node(alias));
            trace!("Color {} as {}", self.display_node(n), alias_color);
626
627
628
            self.ig.color_node(n, alias_color);
        }
    }
qinsoon's avatar
qinsoon committed
629

qinsoon's avatar
qinsoon committed
630
    #[allow(unused_variables)]
qinsoon's avatar
qinsoon committed
631
    fn rewrite_program(&mut self) {
qinsoon's avatar
qinsoon committed
632
633
634
635
636
637
        let spills = self.spills();

        let mut spilled_mem = HashMap::new();

        // allocating frame slots for every spilled temp
        for reg_id in spills.iter() {
qinsoon's avatar
qinsoon committed
638
            let ssa_entry = match self.func.context.get_value(*reg_id) {
qinsoon's avatar
qinsoon committed
639
640
641
                Some(entry) => entry,
                None => panic!("The spilled register {} is not in func context", reg_id)
            };
qinsoon's avatar
qinsoon committed
642
            let mem = self.cf.frame.alloc_slot_for_spilling(ssa_entry.value().clone(), self.vm);
qinsoon's avatar
qinsoon committed
643
644
645
646

            spilled_mem.insert(*reg_id, mem);
        }

qinsoon's avatar
qinsoon committed
647
        // though we are not using this right now
qinsoon's avatar
qinsoon committed
648
        let new_temps = backend::spill_rewrite(&spilled_mem, self.func, self.cf, self.vm);
qinsoon's avatar
qinsoon committed
649
    }
650
651
652
653
654
655
656
657
658
659
660
661
    
    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
662
    }
663
}