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.

liveness.rs 25.1 KB
Newer Older
Isaac Oscar Gariano's avatar
Isaac Oscar Gariano committed
1
// Copyright 2017 The Australian National University
2
//
Isaac Oscar Gariano's avatar
Isaac Oscar Gariano committed
3
4
5
// 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
6
//
Isaac Oscar Gariano's avatar
Isaac Oscar Gariano committed
7
//     http://www.apache.org/licenses/LICENSE-2.0
8
//
Isaac Oscar Gariano's avatar
Isaac Oscar Gariano committed
9
10
11
12
13
14
// 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 compiler::machine_code::CompiledFunction;
18
use ast::ir::*;
qinsoon's avatar
qinsoon committed
19
use compiler::backend;
20
use utils::LinkedHashSet;
21
use utils::LinkedHashMap;
qinsoon's avatar
qinsoon committed
22

23
24
25
use compiler::backend::reg_alloc::graph_coloring::petgraph;
use compiler::backend::reg_alloc::graph_coloring::petgraph::Graph;
use compiler::backend::reg_alloc::graph_coloring::petgraph::graph::NodeIndex;
qinsoon's avatar
qinsoon committed
26

qinsoon's avatar
qinsoon committed
27
/// GraphNode represents a node in the interference graph.
28
29
#[derive(Clone, Copy, Debug, PartialEq)]
pub struct GraphNode {
qinsoon's avatar
qinsoon committed
30
    /// temp ID (could be register)
31
    temp: MuID,
qinsoon's avatar
qinsoon committed
32
    /// assigned color
qinsoon's avatar
qinsoon committed
33
    color: Option<MuID>,
qinsoon's avatar
qinsoon committed
34
    /// temp register group (which machine register class we should assign)
35
    group: backend::RegGroup,
qinsoon's avatar
qinsoon committed
36
    /// cost to spill this temp
37
    spill_cost: f32
qinsoon's avatar
qinsoon committed
38
}
39

qinsoon's avatar
qinsoon committed
40
41
/// Move represents a move between two nodes (referred by index)
/// We need to know the moves so that we can coalesce.
qinsoon's avatar
qinsoon committed
42
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
43
44
pub struct Move {
    pub from: NodeIndex,
45
    pub to: NodeIndex
46
}
47

qinsoon's avatar
qinsoon committed
48
49
50
51
/// InterferenceGraph represents the interference graph, including
/// * the graph
/// * all the nodes and its NodeIndex (a node is referred to by NodeIndex)
/// * all the moves
52
pub struct InterferenceGraph {
qinsoon's avatar
qinsoon committed
53
    /// the internal graph
54
    graph: Graph<GraphNode, (), petgraph::Undirected>,
qinsoon's avatar
qinsoon committed
55
56
    /// a map of all nodes (from temp ID to node index)
    /// node index is how nodes are referred to with pet_graph
57
    nodes: LinkedHashMap<MuID, NodeIndex>,
qinsoon's avatar
qinsoon committed
58
    /// a set of all moves
59
    moves: LinkedHashSet<Move>
60
61
62
}

impl InterferenceGraph {
qinsoon's avatar
qinsoon committed
63
    /// creates a new graph
64
    fn new() -> InterferenceGraph {
qinsoon's avatar
qinsoon committed
65
        InterferenceGraph {
66
            graph: Graph::new_undirected(),
67
            nodes: LinkedHashMap::new(),
68
            moves: LinkedHashSet::new()
qinsoon's avatar
qinsoon committed
69
70
        }
    }
qinsoon's avatar
qinsoon committed
71
72
73

    /// creates a new node for a temp (if we already created a temp for the temp, returns the node)
    /// This function will increase spill cost for the node by 1 each tiem it is called for the temp
74
    fn new_node(&mut self, reg_id: MuID, context: &FunctionContext) -> NodeIndex {
qinsoon's avatar
qinsoon committed
75
        let entry = context.get_value(reg_id).unwrap();
qinsoon's avatar
qinsoon committed
76
77

        // if it is the first time, create the node
qinsoon's avatar
qinsoon committed
78
        if !self.nodes.contains_key(&reg_id) {
79
            let node = GraphNode {
80
                temp: reg_id,
81
                color: None,
82
                group: backend::RegGroup::get_from_ty(entry.ty()),
83
                spill_cost: 0.0f32
qinsoon's avatar
qinsoon committed
84
            };
85

qinsoon's avatar
qinsoon committed
86
            // add to the graph
87
            let index = self.graph.add_node(node);
qinsoon's avatar
qinsoon committed
88
            // save index
89
90
            self.nodes.insert(reg_id, index);
        }
qinsoon's avatar
qinsoon committed
91
92

        // get the node index
93
        let node_index = *self.nodes.get(&reg_id).unwrap();
qinsoon's avatar
qinsoon committed
94
        // get node
95
        let node_mut = self.graph.node_weight_mut(node_index).unwrap();
96
        // increase node spill cost
97
        node_mut.spill_cost += 1.0f32;
98

99
        node_index
qinsoon's avatar
qinsoon committed
100
    }
qinsoon's avatar
qinsoon committed
101
102

    /// returns the node index for a temp
103
    pub fn get_node(&self, reg: MuID) -> NodeIndex {
qinsoon's avatar
qinsoon committed
104
        match self.nodes.get(&reg) {
qinsoon's avatar
qinsoon committed
105
            Some(index) => *index,
106
            None => panic!("do not have a node for {}", reg)
qinsoon's avatar
qinsoon committed
107
108
        }
    }
qinsoon's avatar
qinsoon committed
109
110

    /// returns all the nodes in the graph
111
    pub fn nodes(&self) -> Vec<NodeIndex> {
qinsoon's avatar
qinsoon committed
112
        let mut ret = vec![];
113
114
        for index in self.nodes.values() {
            ret.push(*index);
qinsoon's avatar
qinsoon committed
115
116
117
        }
        ret
    }
qinsoon's avatar
qinsoon committed
118
119

    /// returns all the moves in the graph
120
    pub fn moves(&self) -> &LinkedHashSet<Move> {
qinsoon's avatar
qinsoon committed
121
122
        &self.moves
    }
qinsoon's avatar
qinsoon committed
123
124

    /// adds a move edge between two nodes
125
    fn add_move(&mut self, src: NodeIndex, dst: NodeIndex) {
qinsoon's avatar
qinsoon committed
126
127
128
        let src = {
            let temp_src = self.get_temp_of(src);
            if temp_src < MACHINE_ID_END {
qinsoon's avatar
qinsoon committed
129
130
                // get the color for the machine register, e.g. rax for eax/ax/al/ah
                let alias = backend::get_color_for_precolored(temp_src);
qinsoon's avatar
qinsoon committed
131
132
133
134
135
136
137
138
139
                self.get_node(alias)
            } else {
                src
            }
        };

        let dst = {
            let temp_dst = self.get_temp_of(dst);
            if temp_dst < MACHINE_ID_END {
qinsoon's avatar
qinsoon committed
140
                let alias = backend::get_color_for_precolored(temp_dst);
qinsoon's avatar
qinsoon committed
141
142
143
144
145
146
                self.get_node(alias)
            } else {
                dst
            }
        };

147
        self.moves.insert(Move { from: src, to: dst });
148
    }
qinsoon's avatar
qinsoon committed
149
150

    /// adds an interference edge between two nodes
151
    pub fn add_interference_edge(&mut self, from: NodeIndex, to: NodeIndex) {
qinsoon's avatar
qinsoon committed
152
        // adds edge to the internal graph
153
        self.graph.update_edge(from, to, ());
qinsoon's avatar
qinsoon committed
154
155
156

        // if one of the node is machine register, we also add
        // interference edge to its alias
qinsoon's avatar
qinsoon committed
157
158
        // e.g. if we have %a - %edi interfered,
        // we also add %a - %rdi interference
qinsoon's avatar
qinsoon committed
159
160

        let from_tmp = self.graph.node_weight(from).unwrap().temp;
161
        let to_tmp = self.graph.node_weight(to).unwrap().temp;
qinsoon's avatar
qinsoon committed
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176

        if from_tmp < MACHINE_ID_END || to_tmp < MACHINE_ID_END {
            let from_tmp = if from_tmp < MACHINE_ID_END {
                backend::get_color_for_precolored(from_tmp)
            } else {
                from_tmp
            };

            let to_tmp = if to_tmp < MACHINE_ID_END {
                backend::get_color_for_precolored(to_tmp)
            } else {
                to_tmp
            };

            let from_tmp_node = self.get_node(from_tmp);
177
            let to_tmp_node = self.get_node(to_tmp);
qinsoon's avatar
qinsoon committed
178
179
            self.graph.update_edge(from_tmp_node, to_tmp_node, ());
        }
qinsoon's avatar
qinsoon committed
180
181
    }

qinsoon's avatar
qinsoon committed
182
183
    /// is two nodes interfered?
    pub fn is_interfered_with(&self, node1: NodeIndex, node2: NodeIndex) -> bool {
184
185
        let edge = self.graph.find_edge(node1, node2);
        edge.is_some()
qinsoon's avatar
qinsoon committed
186
    }
qinsoon's avatar
qinsoon committed
187
188

    /// set color for a node
189
190
    pub fn color_node(&mut self, node: NodeIndex, color: MuID) {
        self.graph.node_weight_mut(node).unwrap().color = Some(color);
qinsoon's avatar
qinsoon committed
191
    }
qinsoon's avatar
qinsoon committed
192
193

    /// is a node colored yet?
194
195
    pub fn is_colored(&self, node: NodeIndex) -> bool {
        self.graph.node_weight(node).unwrap().color.is_some()
qinsoon's avatar
qinsoon committed
196
    }
qinsoon's avatar
qinsoon committed
197
198

    /// gets the color of a node
199
200
    pub fn get_color_of(&self, node: NodeIndex) -> Option<MuID> {
        self.graph.node_weight(node).unwrap().color
201
    }
qinsoon's avatar
qinsoon committed
202
203

    /// gets the reg group of a node
204
205
    pub fn get_group_of(&self, node: NodeIndex) -> backend::RegGroup {
        self.graph.node_weight(node).unwrap().group
qinsoon's avatar
qinsoon committed
206
    }
qinsoon's avatar
qinsoon committed
207
208

    /// gets the temporary of a node
209
210
    pub fn get_temp_of(&self, node: NodeIndex) -> MuID {
        self.graph.node_weight(node).unwrap().temp
211
    }
qinsoon's avatar
qinsoon committed
212
213

    /// gets the spill cost of a node
214
215
    pub fn get_spill_cost(&self, node: NodeIndex) -> f32 {
        self.graph.node_weight(node).unwrap().spill_cost
216
    }
qinsoon's avatar
qinsoon committed
217
218

    /// are two nodes the same node?
219
    fn is_same_node(&self, node1: NodeIndex, node2: NodeIndex) -> bool {
qinsoon's avatar
qinsoon committed
220
        node1 == node2
qinsoon's avatar
qinsoon committed
221
    }
222

qinsoon's avatar
qinsoon committed
223
    /// are two nodes from the same reg group?
224
225
226
227
228
229
    fn is_same_group(&self, node1: NodeIndex, node2: NodeIndex) -> bool {
        let node1 = self.graph.node_weight(node1).unwrap();
        let node2 = self.graph.node_weight(node2).unwrap();

        node1.group == node2.group
    }
qinsoon's avatar
qinsoon committed
230
231

    /// are two nodes adjacent?
232
    pub fn is_adj(&self, from: NodeIndex, to: NodeIndex) -> bool {
qinsoon's avatar
qinsoon committed
233
        self.is_interfered_with(from, to)
qinsoon's avatar
qinsoon committed
234
    }
qinsoon's avatar
qinsoon committed
235
236
237

    /// gets edges from a node
    pub fn get_edges_of(&self, node: NodeIndex) -> Vec<NodeIndex> {
238
        self.graph.neighbors(node).collect()
239
    }
qinsoon's avatar
qinsoon committed
240
241
242
243

    /// gets degree of a node (number of edges from the node)
    pub fn get_degree_of(&self, node: NodeIndex) -> usize {
        self.get_edges_of(node).len()
qinsoon's avatar
qinsoon committed
244
    }
qinsoon's avatar
qinsoon committed
245
246

    /// prints current graph for debugging (via trace log)
qinsoon's avatar
qinsoon committed
247
    pub fn print(&self, context: &FunctionContext) {
248
249
250
        use compiler::backend::reg_alloc::graph_coloring::petgraph::dot::Dot;
        use compiler::backend::reg_alloc::graph_coloring::petgraph::dot::Config;

251
252
        trace!("");
        trace!("Interference Graph");
253

254
        trace!("nodes:");
qinsoon's avatar
qinsoon committed
255
        for id in self.nodes.keys() {
qinsoon's avatar
qinsoon committed
256
            let val = context.get_value(*id).unwrap().value();
257
            trace!("Reg {} -> {:?}", val, self.nodes.get(&id).unwrap());
qinsoon's avatar
qinsoon committed
258
259
        }

260
        trace!("moves:");
261
        for mov in self.moves.iter() {
262
            trace!("Move {:?} -> {:?}", mov.from, mov.to);
263
        }
qinsoon's avatar
qinsoon committed
264

265
        trace!("graph:");
266
267
268
269
        trace!(
            "\n\n{:?}\n",
            Dot::with_config(&self.graph, &[Config::EdgeNoLabel])
        );
270
        trace!("");
271
    }
qinsoon's avatar
qinsoon committed
272
273
}

qinsoon's avatar
qinsoon committed
274
275
276
277
278
/// prints trace during building liveness for debugging?
const TRACE_LIVENESS: bool = false;

/// builds interference graph based on chaitin briggs algorithms
/// (reference: Tailoring Graph-coloring Register Allocation For Runtime Compilation - CGO'06, Figure 4)
279
280
pub fn build_interference_graph_chaitin_briggs(
    cf: &mut CompiledFunction,
281
    func: &MuFunctionVersion
282
) -> InterferenceGraph {
qinsoon's avatar
qinsoon committed
283
284
285
286
287
288
289
290
    let _p = hprof::enter("regalloc: build global liveness");
    build_global_liveness(cf, func);
    drop(_p);

    let _p = hprof::enter("regalloc: build interference graph");

    info!("---start building interference graph---");
    let mut ig = InterferenceGraph::new();
291

qinsoon's avatar
qinsoon committed
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
    // precolor machine register nodes
    for reg in backend::all_regs().values() {
        let reg_id = reg.extract_ssa_id().unwrap();
        let node = ig.new_node(reg_id, &func.context);
        let precolor = backend::get_color_for_precolored(reg_id);

        ig.color_node(node, precolor);
    }

    // initialize and creates nodes for all the involved temps/regs
    for i in 0..cf.mc().number_of_insts() {
        for reg_id in cf.mc().get_inst_reg_defines(i) {
            ig.new_node(reg_id, &func.context);
        }

        for reg_id in cf.mc().get_inst_reg_uses(i) {
            ig.new_node(reg_id, &func.context);
        }
    }

    // for each basic block, insert interference edge while reversely traversing instructions
    for block in cf.mc().get_all_blocks() {
        // Current_Live(B) = LiveOut(B)
315
316
317
        let mut current_live =
            LinkedHashSet::from_vec(match cf.mc().get_ir_block_liveout(&block) {
                Some(liveout) => liveout.to_vec(),
318
                None => panic!("cannot find liveout for block {}", block)
319
            });
qinsoon's avatar
qinsoon committed
320
321
322
323
324
325
326
327
328
329
330
331
        if TRACE_LIVENESS {
            trace!("Block{}: live out", block);
            for ele in current_live.iter() {
                trace!("{}", func.context.get_temp_display(*ele));
            }
        }

        let range = cf.mc().get_block_range(&block);
        if range.is_none() {
            warn!("Block{}: has no range (no instructions?)", block);
            continue;
        }
332
333
334
335
336
337
        trace_if!(
            TRACE_LIVENESS,
            "Block{}: range = {:?}",
            block,
            range.as_ref().unwrap()
        );
qinsoon's avatar
qinsoon committed
338
339
340

        // for every inst I in reverse order
        for i in range.unwrap().rev() {
341
            if TRACE_LIVENESS {
qinsoon's avatar
qinsoon committed
342
343
344
345
346
347
348
349
                trace!("Block{}: Inst{}", block, i);
                cf.mc().trace_inst(i);
                trace!("current live: ");
                for ele in current_live.iter() {
                    trace!("{}", func.context.get_temp_display(*ele));
                }
            }

350
            let src: Option<MuID> = {
qinsoon's avatar
qinsoon committed
351
352
353
354
355
356
357
358
359
360
361
362
363
                if cf.mc().is_move(i) {
                    let src = cf.mc().get_inst_reg_uses(i);
                    let dst = cf.mc().get_inst_reg_defines(i);

                    // src:  reg/imm/mem
                    // dest: reg/mem
                    // we dont care if src/dest is mem
                    if cf.mc().is_using_mem_op(i) {
                        None
                    } else {
                        if src.len() == 1 {
                            let node1 = ig.get_node(src[0]);
                            let node2 = ig.get_node(dst[0]);
364
365
366
367
368
369
                            trace_if!(
                                TRACE_LIVENESS,
                                "add move between {} and {}",
                                func.context.get_temp_display(src[0]),
                                func.context.get_temp_display(dst[0])
                            );
qinsoon's avatar
qinsoon committed
370
371
372
373
374
375
376
377
378
379
380
                            ig.add_move(node1, node2);

                            Some(src[0])
                        } else {
                            None
                        }
                    }
                } else {
                    None
                }
            };
381
            trace_if!(TRACE_LIVENESS, "Block{}: Inst{}: src={:?}", block, i, src);
qinsoon's avatar
qinsoon committed
382

383
            let defines = cf.mc().get_inst_reg_defines(i);
384
385
386
387
388
389
            for d in defines.iter() {
                current_live.insert(*d);
            }

            // for every definition D in I
            for d in defines {
390
391
392
393
394
395
396
                trace_if!(
                    TRACE_LIVENESS,
                    "Block{}: Inst{}: for definition {}",
                    block,
                    i,
                    func.context.get_temp_display(d)
                );
qinsoon's avatar
qinsoon committed
397
398
399
                // add an interference from D to every element E in Current_Live - {D}
                // creating nodes if necessary
                for e in current_live.iter() {
400
401
402
403
404
405
406
                    trace_if!(
                        TRACE_LIVENESS,
                        "Block{}: Inst{}: for each live {}",
                        block,
                        i,
                        func.context.get_temp_display(*e)
                    );
qinsoon's avatar
qinsoon committed
407
408
409
410
                    if src.is_none() || (src.is_some() && *e != src.unwrap()) {
                        let from = ig.get_node(d);
                        let to = ig.get_node(*e);

411
412
413
                        if !ig.is_same_node(from, to) && ig.is_same_group(from, to) &&
                            !ig.is_adj(from, to)
                        {
qinsoon's avatar
qinsoon committed
414
                            if !ig.is_colored(from) {
415
416
417
418
419
                                trace_if!(
                                    TRACE_LIVENESS,
                                    "Block{}: Inst{}: add interference between {} and {}",
                                    block,
                                    i,
420
                                    func.context.get_temp_display(d),
421
422
                                    func.context.get_temp_display(*e)
                                );
qinsoon's avatar
qinsoon committed
423
424
425
                                ig.add_interference_edge(from, to);
                            }
                            if !ig.is_colored(to) {
426
427
428
429
430
                                trace_if!(
                                    TRACE_LIVENESS,
                                    "Block{}: Inst{}: add interference between {} and {}",
                                    block,
                                    i,
431
                                    func.context.get_temp_display(*e),
432
433
                                    func.context.get_temp_display(d)
                                );
qinsoon's avatar
qinsoon committed
434
435
436
437
438
439
440
441
442
                                ig.add_interference_edge(to, from);
                            }
                        }
                    }
                }
            }

            // for every definition D in I
            for d in cf.mc().get_inst_reg_defines(i) {
443
444
445
446
447
448
449
                trace_if!(
                    TRACE_LIVENESS,
                    "Block{}: Inst{}: remove define {} from current_live",
                    block,
                    i,
                    func.context.get_temp_display(d)
                );
qinsoon's avatar
qinsoon committed
450
451
452
453
454
455
                // remove D from Current_Live
                current_live.remove(&d);
            }

            // for every use U in I
            for u in cf.mc().get_inst_reg_uses(i) {
456
457
458
459
460
461
462
                trace_if!(
                    TRACE_LIVENESS,
                    "Block{}: Inst{}: add use {} to current_live",
                    block,
                    i,
                    func.context.get_temp_display(u)
                );
qinsoon's avatar
qinsoon committed
463
464
465
466
                // add U to Current_live
                current_live.insert(u);
            }

467
468
            if TRACE_LIVENESS {
                trace!("Block{}: Inst{}: done. current_live:", block, i);
qinsoon's avatar
qinsoon committed
469
470
471
472
473
474
475
476
477
478
479
480
481
482
                for ele in current_live.iter() {
                    trace!("{}", func.context.get_temp_display(*ele));
                }
            }
        }
    }

    drop(_p);
    info!("---finish building interference graph---");
    ig
}

/// builds global liveness for a compiled function
fn build_global_liveness(cf: &mut CompiledFunction, func: &MuFunctionVersion) {
qinsoon's avatar
[wip]    
qinsoon committed
483
    info!("---start building live set---");
484

qinsoon's avatar
qinsoon committed
485
486
487
    // build control flow graphs, treat a whole block as one node in the graph
    let cfg = build_cfg_nodes(cf);
    // do liveness analysis
488
489
490
491
492
    global_liveness_analysis(cfg, cf, func);

    info!("---finish building live set---");
}

qinsoon's avatar
qinsoon committed
493
/// CFGBlockNode represents a basic block as a whole for global liveness analysis
494
495
496
497
498
#[derive(Clone, Debug)]
struct CFGBlockNode {
    block: String,
    pred: Vec<String>,
    succ: Vec<String>,
499
    uses: Vec<MuID>,
500
    defs: Vec<MuID>
501
502
}

qinsoon's avatar
qinsoon committed
503
504
505
506
507
508
509
/// builds a LinkedHashMap from basic block names to CFGBlockNode
/// We need to collect for each basic block:
/// * predecessors
/// * successors
/// * uses
/// * defs
fn build_cfg_nodes(cf: &mut CompiledFunction) -> LinkedHashMap<String, CFGBlockNode> {
510
511
    info!("---local liveness analysis---");
    let mc = cf.mc();
512
    let mut ret = LinkedHashMap::new();
513
514
515
    let all_blocks = mc.get_all_blocks();

    // create maps (start_inst -> name) and (end_inst -> name)
qinsoon's avatar
qinsoon committed
516
517
    // we will use it to find basic blocks when given a inst index
    let (start_inst_map, end_inst_map) = {
518
519
        let mut start_inst_map: LinkedHashMap<usize, &str> = LinkedHashMap::new();
        let mut end_inst_map: LinkedHashMap<usize, &str> = LinkedHashMap::new();
qinsoon's avatar
qinsoon committed
520
521
522
        for block in all_blocks.iter() {
            let range = match mc.get_block_range(block) {
                Some(range) => range,
523
                None => panic!("cannot find range for block {}", block)
qinsoon's avatar
qinsoon committed
524
            };
525

qinsoon's avatar
qinsoon committed
526
527
528
529
530
            // start inst
            let first_inst = range.start;
            // last inst (we need to skip symbols)
            let last_inst = match mc.get_last_inst(range.end) {
                Some(last) => last,
531
532
533
534
535
536
                None => {
                    panic!(
                        "cannot find last instruction in block {}, this block contains no instruction?",
                        block
                    )
                }
qinsoon's avatar
qinsoon committed
537
            };
538
539
540
541
542
543
544
            trace_if!(
                TRACE_LIVENESS,
                "Block {}: start_inst={}, end_inst(inclusive)={}",
                block,
                first_inst,
                last_inst
            );
545

qinsoon's avatar
qinsoon committed
546
547
548
549
550
551
            start_inst_map.insert(first_inst, block);
            end_inst_map.insert(last_inst, block);
        }

        (start_inst_map, end_inst_map)
    };
552

qinsoon's avatar
qinsoon committed
553
    // collect info for each basic block
554
    for block in mc.get_all_blocks().iter() {
555
        trace_if!(TRACE_LIVENESS, "---block {}---", block);
556
557
        let range = mc.get_block_range(block).unwrap();
        let start_inst = range.start;
558
        let end = range.end;
559

qinsoon's avatar
qinsoon committed
560
561
562
563
564
565
566
        // livein set of this block is what temps this block uses from other blocks
        // defs is what temps this block defines in the block
        let (livein, defs) = {
            // we gradually build livein
            let mut livein = vec![];
            // we need to know all temporaries defined in the block
            // if a temporary is not defined in this block, it is a livein for this block
567
            let mut all_defined: LinkedHashSet<MuID> = LinkedHashSet::new();
qinsoon's avatar
qinsoon committed
568
569
570
571
572
573
574
575
576
577

            for i in start_inst..end {
                let reg_uses = mc.get_inst_reg_uses(i);

                // if a reg is used but not defined before, it is a live-in
                for reg in reg_uses {
                    if !all_defined.contains(&reg) {
                        livein.push(reg);
                    }
                }
578

qinsoon's avatar
qinsoon committed
579
580
581
                let reg_defs = mc.get_inst_reg_defines(i);
                for reg in reg_defs {
                    all_defined.insert(reg);
582
583
584
                }
            }

585
            let defs: Vec<MuID> = all_defined.iter().map(|x| *x).collect();
586

qinsoon's avatar
qinsoon committed
587
588
            (livein, defs)
        };
589

590
        let preds: Vec<String> = {
591
592
            let mut ret = vec![];

qinsoon's avatar
qinsoon committed
593
            // predecessors of the first instruction is the predecessors of this block
594
595
596
597
598
599
600
601
602
603
            for pred in mc.get_preds(start_inst).into_iter() {
                match end_inst_map.get(pred) {
                    Some(str) => ret.push(String::from(*str)),
                    None => {}
                }
            }

            ret
        };

604
        let succs: Vec<String> = {
605
606
            let mut ret = vec![];

qinsoon's avatar
qinsoon committed
607
            // successors of the last instruction is the successors of this block
608
            for succ in mc.get_succs(mc.get_last_inst(end).unwrap()).into_iter() {
609
610
611
612
613
614
615
616
617
618
619
620
621
622
                match start_inst_map.get(succ) {
                    Some(str) => ret.push(String::from(*str)),
                    None => {}
                }
            }

            ret
        };

        let node = CFGBlockNode {
            block: block.clone(),
            pred: preds,
            succ: succs,
            uses: livein,
623
            defs: defs
624
625
        };

626
        trace_if!(TRACE_LIVENESS, "as CFGNode {:?}", node);
627
628
629
630
631
632
        ret.insert(block.clone(), node);
    }

    ret
}

qinsoon's avatar
qinsoon committed
633
/// global analysis, the iterative algorithm to compute livenss until livein/out reaches a fix point
634
635
636
fn global_liveness_analysis(
    blocks: LinkedHashMap<String, CFGBlockNode>,
    cf: &mut CompiledFunction,
637
    func: &MuFunctionVersion
638
) {
639
640
    info!("---global liveness analysis---");
    info!("{} blocks", blocks.len());
641
642

    // init live in and live out
643
    let mut livein: LinkedHashMap<String, LinkedHashSet<MuID>> = {
644
        let mut ret = LinkedHashMap::new();
645
646
647
648
649
        for name in blocks.keys() {
            ret.insert(name.clone(), LinkedHashSet::new());
        }
        ret
    };
650
    let mut liveout: LinkedHashMap<String, LinkedHashSet<MuID>> = {
651
        let mut ret = LinkedHashMap::new();
652
653
654
655
656
657
        for name in blocks.keys() {
            ret.insert(name.clone(), LinkedHashSet::new());
        }
        ret
    };

qinsoon's avatar
qinsoon committed
658
    // is the result changed in this iteration?
659
    let mut is_changed = true;
qinsoon's avatar
qinsoon committed
660
    // record iteration count
661
662
663
    let mut i = 0;

    while is_changed {
664
        trace_if!(TRACE_LIVENESS, "---iteration {}---", i);
665
666
667
668
669
670
671
672
        i += 1;

        // reset
        is_changed = false;

        for node in blocks.keys() {
            let cfg_node = blocks.get(node).unwrap();

qinsoon's avatar
qinsoon committed
673
            // old livein/out
674
            let in_set_old = livein.get(node).unwrap().clone();
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
            let out_set_old = liveout.get(node).unwrap().clone();

            // in <- use + (out - def)
            {
                let mut inset = livein.get_mut(node).unwrap();

                inset.clear();

                // (1) out - def
                inset.add_all(liveout.get(node).unwrap().clone());
                for def in cfg_node.defs.iter() {
                    inset.remove(def);
                }

                // (2) in + (out - def)
                for in_reg in cfg_node.uses.iter() {
                    inset.insert(*in_reg);
                }
            }

            // out[n] <- union(in[s] for every successor s of n)
            {
                let mut outset = liveout.get_mut(node).unwrap();
                outset.clear();

                for s in cfg_node.succ.iter() {
                    outset.add_all(livein.get(s).unwrap().clone());
                }
            }

            // is in/out changed in this iteration?
706
707
            let n_changed = !in_set_old.equals(livein.get(node).unwrap()) ||
                !out_set_old.equals(liveout.get(node).unwrap());
708

qinsoon's avatar
qinsoon committed
709
            if TRACE_LIVENESS {
710
711
712
713
714
715
716
717
718
719
720
                trace!("block {}", node);
                trace!("in(old)  = {:?}", in_set_old);
                trace!("in(new)  = {:?}", livein.get(node).unwrap());
                trace!("out(old) = {:?}", out_set_old);
                trace!("out(new) = {:?}", liveout.get(node).unwrap());
            }

            is_changed = is_changed || n_changed;
        }
    }

721
722
    info!("finished in {} iterations", i);

qinsoon's avatar
qinsoon committed
723
    // set live in and live out
724
    for block in blocks.keys() {
725
726
727
728
729
730
731
        let livein: Vec<MuID> = livein
            .get(block)
            .unwrap()
            .clone()
            .iter()
            .map(|x| *x)
            .collect();
732
        if TRACE_LIVENESS {
733
734
735
736
            let display_array: Vec<String> = livein
                .iter()
                .map(|x| func.context.get_temp_display(*x))
                .collect();
737
738
739
740
            trace!("livein  for block {}: {:?}", block, display_array);
        }
        cf.mc_mut().set_ir_block_livein(block, livein);

741
742
743
744
745
746
747
        let liveout: Vec<MuID> = liveout
            .get(block)
            .unwrap()
            .clone()
            .iter()
            .map(|x| *x)
            .collect();
748
        if TRACE_LIVENESS {
749
750
751
752
            let display_array: Vec<String> = liveout
                .iter()
                .map(|x| func.context.get_temp_display(*x))
                .collect();
753
754
755
756
            trace!("liveout for block {}: {:?}", block, display_array);
        }
        cf.mc_mut().set_ir_block_liveout(block, liveout);
    }
757
}