1 /*

     2  * Copyright 1997-2003 Sun Microsystems, Inc.  All Rights Reserved.

     3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.

     4  *

     5  * This code is free software; you can redistribute it and/or modify it

     6  * under the terms of the GNU General Public License version 2 only, as

     7  * published by the Free Software Foundation.

     8  *

     9  * 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 

    25 class LoopTree;

    26 class LRG;

    27 class LRG_List;

    28 class Matcher;

    29 class PhaseIFG;

    30 class PhaseCFG;

    31 

    32 //------------------------------PhaseCoalesce----------------------------------

    33 class PhaseCoalesce : public Phase {

    34 protected:

    35   PhaseChaitin &_phc;

    36 

    37 public:

    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.

    66 class PhaseAggressiveCoalesce : public PhaseCoalesce {

    67   uint _unique;

    68 public:

    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.

    90 class PhaseConservativeCoalesce : public PhaseCoalesce {

    91   IndexSet _ulr;               // Union live range interferences

    92 public:

    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 };