coalesce.hpp revision 0:a61af66fc99e 
1133359Sobrien/*
2133359Sobrien * Copyright 1997-2003 Sun Microsystems, Inc.  All Rights Reserved.
3226048Sobrien * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4133359Sobrien *
5133359Sobrien * This code is free software; you can redistribute it and/or modify it
6133359Sobrien * under the terms of the GNU General Public License version 2 only, as
7133359Sobrien * published by the Free Software Foundation.
8133359Sobrien *
9133359Sobrien * This code is distributed in the hope that it will be useful, but WITHOUT
10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
11 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
12 * version 2 for more details (a copy is included in the LICENSE file that
13 * accompanied this code).
14 *
15 * You should have received a copy of the GNU General Public License version
16 * 2 along with this work; if not, write to the Free Software Foundation,
17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
18 *
19 * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
20 * CA 95054 USA or visit www.sun.com if you need additional information or
21 * have any questions.
22 *
23 */
24
25class LoopTree;
26class LRG;
27class LRG_List;
28class Matcher;
29class PhaseIFG;
30class PhaseCFG;
31
32//------------------------------PhaseCoalesce----------------------------------
33class PhaseCoalesce : public Phase {
34protected:
35  PhaseChaitin &_phc;
36
37public:
38  // Coalesce copies
39  PhaseCoalesce( PhaseChaitin &chaitin ) : Phase(Coalesce), _phc(chaitin) { }
40
41  virtual void verify() = 0;
42
43  // Coalesce copies
44  void coalesce_driver( );
45
46  // Coalesce copies in this block
47  virtual void coalesce( Block *b ) = 0;
48
49  // Attempt to coalesce live ranges defined by these 2
50  void combine_these_two( Node *n1, Node *n2 );
51
52  LRG &lrgs( uint lidx ) { return _phc.lrgs(lidx); }
53#ifndef PRODUCT
54  // Dump internally name
55  void dump( Node *n ) const;
56  // Dump whole shebang
57  void dump() const;
58#endif
59};
60
61//------------------------------PhaseAggressiveCoalesce------------------------
62// Aggressively, pessimistic coalesce copies.  Aggressive means ignore graph
63// colorability; perhaps coalescing to the point of forcing a spill.
64// Pessimistic means we cannot coalesce if 2 live ranges interfere.  This
65// implies we do not hit a fixed point right away.
66class PhaseAggressiveCoalesce : public PhaseCoalesce {
67  uint _unique;
68public:
69  // Coalesce copies
70  PhaseAggressiveCoalesce( PhaseChaitin &chaitin ) : PhaseCoalesce(chaitin) {}
71
72  virtual void verify() { };
73
74  // Aggressively coalesce copies in this block
75  virtual void coalesce( Block *b );
76
77  // Where I fail to coalesce, manifest virtual copies as the Real Thing
78  void insert_copies( Matcher &matcher );
79
80  // Copy insertion needs some smarts in case live ranges overlap
81  void insert_copy_with_overlap( Block *b, Node *copy, uint dst_name, uint src_name );
82};
83
84
85//------------------------------PhaseConservativeCoalesce----------------------
86// Conservatively, pessimistic coalesce copies.  Conservative means do not
87// coalesce if the resultant live range will be uncolorable.  Pessimistic
88// means we cannot coalesce if 2 live ranges interfere.  This implies we do
89// not hit a fixed point right away.
90class PhaseConservativeCoalesce : public PhaseCoalesce {
91  IndexSet _ulr;               // Union live range interferences
92public:
93  // Coalesce copies
94  PhaseConservativeCoalesce( PhaseChaitin &chaitin );
95
96  virtual void verify();
97
98  // Conservatively coalesce copies in this block
99  virtual void coalesce( Block *b );
100
101  // Coalesce this chain of copies away
102  bool copy_copy( Node *dst_copy, Node *src_copy, Block *b, uint bindex );
103
104  void union_helper( Node *lr1_node, Node *lr2_node, uint lr1, uint lr2, Node *src_def, Node *dst_copy, Node *src_copy, Block *b, uint bindex );
105
106  uint compute_separating_interferences(Node *dst_copy, Node *src_copy, Block *b, uint bindex, RegMask &rm, uint rm_size, uint reg_degree, uint lr1, uint lr2);
107
108  void update_ifg(uint lr1, uint lr2, IndexSet *n_lr1, IndexSet *n_lr2);
109};
110