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.9 KB
Newer Older
Isaac Oscar Gariano's avatar
Isaac Oscar Gariano committed
1
2
3
4
5
6
7
8
9
10
11
12
13
14
// Copyright 2017 The Australian National University
// 
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
// 
//     http://www.apache.org/licenses/LICENSE-2.0
// 
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

15
16
extern crate hprof;

qinsoon's avatar
qinsoon committed
17
use ast::ptr::*;
qinsoon's avatar
qinsoon committed
18
19
20
use ast::ir::*;
use compiler::backend;
use compiler::backend::reg_alloc::graph_coloring;
21
use compiler::backend::reg_alloc::graph_coloring::liveness::InterferenceGraph;
qinsoon's avatar
qinsoon committed
22
23
use compiler::machine_code::CompiledFunction;
use vm::VM;
24

25
use utils::vec_utils;
26
use utils::LinkedHashSet;
27
use utils::LinkedHashMap;
qinsoon's avatar
qinsoon committed
28

qinsoon's avatar
qinsoon committed
29
use std::cell::RefCell;
qinsoon's avatar
qinsoon committed
30

31
32
33
use compiler::backend::reg_alloc::graph_coloring::liveness::Move;
use compiler::backend::reg_alloc::graph_coloring::petgraph::graph::NodeIndex;

qinsoon's avatar
qinsoon committed
34
const COALESCING : bool = true;
35

qinsoon's avatar
qinsoon committed
36
37
/// GraphColoring algorithm
/// based on Appel's book section 11.4
qinsoon's avatar
qinsoon committed
38
pub struct GraphColoring<'a> {
qinsoon's avatar
qinsoon committed
39
    // context
qinsoon's avatar
qinsoon committed
40
41
42
    pub func: &'a mut MuFunctionVersion,
    pub cf: &'a mut CompiledFunction,
    pub vm: &'a VM,
43
    pub ig: InterferenceGraph,
qinsoon's avatar
qinsoon committed
44

qinsoon's avatar
qinsoon committed
45
    /// machine registers, preassigned a color
46
    precolored: LinkedHashSet<NodeIndex>,
qinsoon's avatar
qinsoon committed
47
    /// all colors available
48
    colors: LinkedHashMap<backend::RegGroup, LinkedHashSet<MuID>>,
qinsoon's avatar
qinsoon committed
49
    /// temporaries, not precolored and not yet processed
50
    initial: Vec<NodeIndex>,
qinsoon's avatar
qinsoon committed
51
    /// whether a temp is spillable
qinsoon's avatar
qinsoon committed
52
    // FIXME: not used at the moment
qinsoon's avatar
qinsoon committed
53
54
55
56
57
58
59
60
61
62
63
64
    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
65
    coalesced_nodes: LinkedHashSet<NodeIndex>,
qinsoon's avatar
qinsoon committed
66
67
68
69
70
71
    /// nodes successfully colored
    colored_nodes: Vec<NodeIndex>,
    /// stack containing temporaries removed from the graph
    select_stack: Vec<NodeIndex>,

    /// moves that have been coalesced
72
    coalesced_moves: LinkedHashSet<Move>,
qinsoon's avatar
qinsoon committed
73
    /// moves whose source and target interfere
74
    constrained_moves: LinkedHashSet<Move>,
qinsoon's avatar
qinsoon committed
75
76
77
78
79
80
81
82
83
84
85
86
    /// 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
87
    alias: LinkedHashMap<NodeIndex, NodeIndex>,
qinsoon's avatar
qinsoon committed
88

qinsoon's avatar
qinsoon committed
89
90
91
92
93
    // 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
94
95
}

qinsoon's avatar
qinsoon committed
96
impl <'a> GraphColoring<'a> {
qinsoon's avatar
qinsoon committed
97
    /// starts coloring
98
    pub fn start (func: &'a mut MuFunctionVersion, cf: &'a mut CompiledFunction, vm: &'a VM) -> GraphColoring<'a> {
qinsoon's avatar
qinsoon committed
99
        GraphColoring::start_with_spill_history(LinkedHashMap::new(), LinkedHashMap::new(), func, cf, vm)
qinsoon's avatar
qinsoon committed
100
101
    }

qinsoon's avatar
qinsoon committed
102
    /// restarts coloring with spill history
qinsoon's avatar
qinsoon committed
103
104
105
106
    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>
    {
107
        trace!("Initializing coloring allocator...");
qinsoon's avatar
qinsoon committed
108
109
        cf.mc().trace_mc();

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

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

qinsoon's avatar
qinsoon committed
145
        coloring.regalloc()
qinsoon's avatar
qinsoon committed
146
    }
qinsoon's avatar
qinsoon committed
147

qinsoon's avatar
qinsoon committed
148
    /// returns formatted string for a node
149
    fn display_node(&self, node: NodeIndex) -> String {
qinsoon's avatar
qinsoon committed
150
151
152
153
        let id = self.ig.get_temp_of(node);
        self.display_id(id)
    }

qinsoon's avatar
qinsoon committed
154
    /// returns formatted string for an ID
qinsoon's avatar
qinsoon committed
155
156
157
158
    fn display_id(&self, id: MuID) -> String {
        self.func.context.get_temp_display(id)
    }

qinsoon's avatar
qinsoon committed
159
    /// returns formatted string for a move
qinsoon's avatar
qinsoon committed
160
161
162
    fn display_move(&self, m: Move) -> String {
        format!("Move: {} -> {}", self.display_node(m.from), self.display_node(m.to))
    }
qinsoon's avatar
qinsoon committed
163
164

    /// does coloring register allocation
165
    fn regalloc(mut self) -> GraphColoring<'a> {
qinsoon's avatar
qinsoon committed
166
        trace!("---InterenceGraph---");
qinsoon's avatar
qinsoon committed
167
        self.ig.print(&self.func.context);
qinsoon's avatar
qinsoon committed
168
169
170

        // start timing for graph coloring
        let _p = hprof::enter("regalloc: graph coloring");
qinsoon's avatar
qinsoon committed
171
        
qinsoon's avatar
qinsoon committed
172
        // precolor for all machine registers
173
        for reg in backend::all_regs().values() {
174
175
176
177
178
            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
179
        // put usable registers as available colors
180
        for reg in backend::all_usable_regs().iter() {
qinsoon's avatar
qinsoon committed
181
            let reg_id = reg.extract_ssa_id().unwrap();
qinsoon's avatar
qinsoon committed
182
183
            let group = backend::pick_group_for_reg(reg_id);
            self.colors.get_mut(&group).unwrap().insert(reg_id);
qinsoon's avatar
qinsoon committed
184
        }
qinsoon's avatar
qinsoon committed
185
186

        // push uncolored nodes to initial work set
qinsoon's avatar
qinsoon committed
187
188
        for node in self.ig.nodes() {
            if !self.ig.is_colored(node) {
189
                self.initial.push(node);
qinsoon's avatar
qinsoon committed
190
191
192
                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
193
194
            }
        }
qinsoon's avatar
qinsoon committed
195
196

        // initialize work
qinsoon's avatar
qinsoon committed
197
198
        self.build();
        self.make_work_list();
qinsoon's avatar
qinsoon committed
199
200

        // main loop
qinsoon's avatar
qinsoon committed
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
        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
217
218

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

qinsoon's avatar
qinsoon committed
221
        // finish
222
223
        drop(_p);

qinsoon's avatar
qinsoon committed
224
        // if we need to spill
qinsoon's avatar
qinsoon committed
225
226
        if !self.spilled_nodes.is_empty() {
            trace!("spill required");
qinsoon's avatar
qinsoon committed
227
228
229
            if cfg!(debug_assertions) {
                trace!("nodes to be spilled:");
                for node in self.spilled_nodes.iter() {
qinsoon's avatar
qinsoon committed
230
                    trace!("{}", self.display_node(*node));
qinsoon's avatar
qinsoon committed
231
232
233
                }
            }

qinsoon's avatar
qinsoon committed
234
            // rewrite program to insert spilling code
qinsoon's avatar
qinsoon committed
235
            self.rewrite_program();
qinsoon's avatar
qinsoon committed
236

qinsoon's avatar
qinsoon committed
237
            // recursively redo graph coloring
qinsoon's avatar
qinsoon committed
238
            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
239
240
        }

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

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

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

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

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

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

qinsoon's avatar
qinsoon committed
710
    fn rewrite_program(&mut self) {
qinsoon's avatar
qinsoon committed
711
712
        let spills = self.spills();

713
        let mut spilled_mem = LinkedHashMap::new();
qinsoon's avatar
qinsoon committed
714
715
716

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

qinsoon's avatar
qinsoon committed
723
724
            spilled_mem.insert(*reg_id, mem.clone());
            self.spill_history.insert(*reg_id, mem);
qinsoon's avatar
qinsoon committed
725
726
        }

qinsoon's avatar
qinsoon committed
727
728
729
730
        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
731
    }
732
733
734
735
736
737
738
739
740
741
742
743
    
    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
744
    }
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770

    pub fn get_assignments(&self) -> LinkedHashMap<MuID, MuID> {
        let mut ret = LinkedHashMap::new();

        for node in self.ig.nodes() {
            let temp = self.ig.get_temp_of(node);

            if temp < MACHINE_ID_END {
                continue;
            } else {
                let alias = self.get_alias(node);
                let machine_reg = match self.ig.get_color_of(alias) {
                    Some(reg) => reg,
                    None => panic!(
                        "Reg{}/{:?} (aliased as Reg{}/{:?}) is not assigned with a color",
                        self.ig.get_temp_of(node), node,
                        self.ig.get_temp_of(alias), alias)
                };

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

qinsoon's avatar
qinsoon committed
771
772
773
    pub fn get_spill_scratch_temps(&self) -> LinkedHashMap<MuID, MuID> {
        self.spill_scratch_temps.clone()
    }
774
}