gcc/lcm.c

   1 /* Generic partial redundancy elimination with lazy code motion support.
   2    Copyright (C) 1998, 1999, 2000, 2001 Free Software Foundation, Inc.
   3
   4 This file is part of GCC.
   5
   6 GCC is free software; you can redistribute it and/or modify it under
   7 the terms of the GNU General Public License as published by the Free
   8 Software Foundation; either version 2, or (at your option) any later
   9 version.
  10
  11 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  12 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  13 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  14 for more details.
  15
  16 You should have received a copy of the GNU General Public License
  17 along with GCC; see the file COPYING.  If not, write to the Free
  18 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
  19 02111-1307, USA.  */
  20
  21 /* These routines are meant to be used by various optimization
  22    passes which can be modeled as lazy code motion problems.
  23    Including, but not limited to:
  24
  25         * Traditional partial redundancy elimination.
  26
  27         * Placement of caller/caller register save/restores.
  28
  29         * Load/store motion.
  30
  31         * Copy motion.
  32
  33         * Conversion of flat register files to a stacked register
  34         model.
  35
  36         * Dead load/store elimination.
  37
  38   These routines accept as input:
  39
  40         * Basic block information (number of blocks, lists of
  41         predecessors and successors).  Note the granularity
  42         does not need to be basic block, they could be statements
  43         or functions.
  44
  45         * Bitmaps of local properties (computed, transparent and
  46         anticipatable expressions).
  47
  48   The output of these routines is bitmap of redundant computations
  49   and a bitmap of optimal placement points.  */
  50
  51
  52 #include "config.h"
  53 #include "system.h"
  54 #include "rtl.h"
  55 #include "regs.h"
  56 #include "hard-reg-set.h"
  57 #include "flags.h"
  58 #include "real.h"
  59 #include "insn-config.h"
  60 #include "recog.h"
  61 #include "basic-block.h"
  62 #include "tm_p.h"
  63
  64 /* We want target macros for the mode switching code to be able to refer
  65    to instruction attribute values.  */
  66 #include "insn-attr.h"
  67
  68 /* Edge based LCM routines.  */
  69 static void compute_antinout_edge       PARAMS ((sbitmap *, sbitmap *,
  70                                                  sbitmap *, sbitmap *));
  71 static void compute_earliest            PARAMS ((struct edge_list *, int,
  72                                                  sbitmap *, sbitmap *,
  73                                                  sbitmap *, sbitmap *,
  74                                                  sbitmap *));
  75 static void compute_laterin             PARAMS ((struct edge_list *, sbitmap *,
  76                                                  sbitmap *, sbitmap *,
  77                                                  sbitmap *));
  78 static void compute_insert_delete       PARAMS ((struct edge_list *edge_list,
  79                                                  sbitmap *, sbitmap *,
  80                                                  sbitmap *, sbitmap *,
  81                                                  sbitmap *));
  82
  83 /* Edge based LCM routines on a reverse flowgraph.  */
  84 static void compute_farthest            PARAMS ((struct edge_list *, int,
  85                                                  sbitmap *, sbitmap *,
  86                                                  sbitmap*, sbitmap *,
  87                                                  sbitmap *));
  88 static void compute_nearerout           PARAMS ((struct edge_list *, sbitmap *,
  89                                                  sbitmap *, sbitmap *,
  90                                                  sbitmap *));
  91 static void compute_rev_insert_delete   PARAMS ((struct edge_list *edge_list,
  92                                                  sbitmap *, sbitmap *,
  93                                                  sbitmap *, sbitmap *,
  94                                                  sbitmap *));
  95 \f
  96 /* Edge based lcm routines.  */
  97
  98 /* Compute expression anticipatability at entrance and exit of each block.
  99    This is done based on the flow graph, and not on the pred-succ lists.
 100    Other than that, its pretty much identical to compute_antinout.  */
 101
 102 static void
 103 compute_antinout_edge (antloc, transp, antin, antout)
 104      sbitmap *antloc;
 105      sbitmap *transp;
 106      sbitmap *antin;
 107      sbitmap *antout;
 108 {
 109   int bb;
 110   edge e;
 111   basic_block *worklist, *qin, *qout, *qend;
 112   unsigned int qlen;
 113
 114   /* Allocate a worklist array/queue.  Entries are only added to the
 115      list if they were not already on the list.  So the size is
 116      bounded by the number of basic blocks.  */
 117   qin = qout = worklist
 118     = (basic_block *) xmalloc (sizeof (basic_block) * n_basic_blocks);
 119
 120   /* We want a maximal solution, so make an optimistic initialization of
 121      ANTIN.  */
 122   sbitmap_vector_ones (antin, n_basic_blocks);
 123
 124   /* Put every block on the worklist; this is necessary because of the
 125      optimistic initialization of ANTIN above.  */
 126   for (bb = n_basic_blocks - 1; bb >= 0; bb--)
 127     {
 128       *qin++ = BASIC_BLOCK (bb);
 129       BASIC_BLOCK (bb)->aux = BASIC_BLOCK (bb);
 130     }
 131
 132   qin = worklist;
 133   qend = &worklist[n_basic_blocks];
 134   qlen = n_basic_blocks;
 135
 136   /* Mark blocks which are predecessors of the exit block so that we
 137      can easily identify them below.  */
 138   for (e = EXIT_BLOCK_PTR->pred; e; e = e->pred_next)
 139     e->src->aux = EXIT_BLOCK_PTR;
 140
 141   /* Iterate until the worklist is empty.  */
 142   while (qlen)
 143     {
 144       /* Take the first entry off the worklist.  */
 145       basic_block b = *qout++;
 146       bb = b->index;
 147       qlen--;
 148
 149       if (qout >= qend)
 150         qout = worklist;
 151
 152       if (b->aux == EXIT_BLOCK_PTR)
 153         /* Do not clear the aux field for blocks which are predecessors of
 154            the EXIT block.  That way we never add then to the worklist
 155            again.  */
 156         sbitmap_zero (antout[bb]);
 157       else
 158         {
 159           /* Clear the aux field of this block so that it can be added to
 160              the worklist again if necessary.  */
 161           b->aux = NULL;
 162           sbitmap_intersection_of_succs (antout[bb], antin, bb);
 163         }
 164
 165       if (sbitmap_a_or_b_and_c (antin[bb], antloc[bb], transp[bb], antout[bb]))
 166         /* If the in state of this block changed, then we need
 167            to add the predecessors of this block to the worklist
 168            if they are not already on the worklist.  */
 169         for (e = b->pred; e; e = e->pred_next)
 170           if (!e->src->aux && e->src != ENTRY_BLOCK_PTR)
 171             {
 172               *qin++ = e->src;
 173               e->src->aux = e;
 174               qlen++;
 175               if (qin >= qend)
 176                 qin = worklist;
 177             }
 178     }
 179
 180   clear_aux_for_edges ();
 181   clear_aux_for_blocks ();
 182   free (worklist);
 183 }
 184
 185 /* Compute the earliest vector for edge based lcm.  */
 186
 187 static void
 188 compute_earliest (edge_list, n_exprs, antin, antout, avout, kill, earliest)
 189      struct edge_list *edge_list;
 190      int n_exprs;
 191      sbitmap *antin, *antout, *avout, *kill, *earliest;
 192 {
 193   sbitmap difference, temp_bitmap;
 194   int x, num_edges;
 195   basic_block pred, succ;
 196
 197   num_edges = NUM_EDGES (edge_list);
 198
 199   difference = sbitmap_alloc (n_exprs);
 200   temp_bitmap = sbitmap_alloc (n_exprs);
 201
 202   for (x = 0; x < num_edges; x++)
 203     {
 204       pred = INDEX_EDGE_PRED_BB (edge_list, x);
 205       succ = INDEX_EDGE_SUCC_BB (edge_list, x);
 206       if (pred == ENTRY_BLOCK_PTR)
 207         sbitmap_copy (earliest[x], antin[succ->index]);
 208       else
 209         {
 210           /* We refer to the EXIT_BLOCK index, instead of testing for
 211              EXIT_BLOCK_PTR, so that EXIT_BLOCK_PTR's index can be
 212              changed so as to pretend it's a regular block, so that
 213              its antin can be taken into account.  */
 214           if (succ->index == EXIT_BLOCK)
 215             sbitmap_zero (earliest[x]);
 216           else
 217             {
 218               sbitmap_difference (difference, antin[succ->index],
 219                                   avout[pred->index]);
 220               sbitmap_not (temp_bitmap, antout[pred->index]);
 221               sbitmap_a_and_b_or_c (earliest[x], difference,
 222                                     kill[pred->index], temp_bitmap);
 223             }
 224         }
 225     }
 226
 227   sbitmap_free (temp_bitmap);
 228   sbitmap_free (difference);
 229 }
 230
 231 /* later(p,s) is dependent on the calculation of laterin(p).
 232    laterin(p) is dependent on the calculation of later(p2,p).
 233
 234      laterin(ENTRY) is defined as all 0's
 235      later(ENTRY, succs(ENTRY)) are defined using laterin(ENTRY)
 236      laterin(succs(ENTRY)) is defined by later(ENTRY, succs(ENTRY)).
 237
 238    If we progress in this manner, starting with all basic blocks
 239    in the work list, anytime we change later(bb), we need to add
 240    succs(bb) to the worklist if they are not already on the worklist.
 241
 242    Boundary conditions:
 243
 244      We prime the worklist all the normal basic blocks.   The ENTRY block can
 245      never be added to the worklist since it is never the successor of any
 246      block.  We explicitly prevent the EXIT block from being added to the
 247      worklist.
 248
 249      We optimistically initialize LATER.  That is the only time this routine
 250      will compute LATER for an edge out of the entry block since the entry
 251      block is never on the worklist.  Thus, LATERIN is neither used nor
 252      computed for the ENTRY block.
 253
 254      Since the EXIT block is never added to the worklist, we will neither
 255      use nor compute LATERIN for the exit block.  Edges which reach the
 256      EXIT block are handled in the normal fashion inside the loop.  However,
 257      the insertion/deletion computation needs LATERIN(EXIT), so we have
 258      to compute it.  */
 259
 260 static void
 261 compute_laterin (edge_list, earliest, antloc, later, laterin)
 262      struct edge_list *edge_list;
 263      sbitmap *earliest, *antloc, *later, *laterin;
 264 {
 265   int bb, num_edges, i;
 266   edge e;
 267   basic_block *worklist, *qin, *qout, *qend;
 268   unsigned int qlen;
 269
 270   num_edges = NUM_EDGES (edge_list);
 271
 272   /* Allocate a worklist array/queue.  Entries are only added to the
 273      list if they were not already on the list.  So the size is
 274      bounded by the number of basic blocks.  */
 275   qin = qout = worklist
 276     = (basic_block *) xmalloc (sizeof (basic_block) * (n_basic_blocks + 1));
 277
 278   /* Initialize a mapping from each edge to its index.  */
 279   for (i = 0; i < num_edges; i++)
 280     INDEX_EDGE (edge_list, i)->aux = (void *) (size_t) i;
 281
 282   /* We want a maximal solution, so initially consider LATER true for
 283      all edges.  This allows propagation through a loop since the incoming
 284      loop edge will have LATER set, so if all the other incoming edges
 285      to the loop are set, then LATERIN will be set for the head of the
 286      loop.
 287
 288      If the optimistic setting of LATER on that edge was incorrect (for
 289      example the expression is ANTLOC in a block within the loop) then
 290      this algorithm will detect it when we process the block at the head
 291      of the optimistic edge.  That will requeue the affected blocks.  */
 292   sbitmap_vector_ones (later, num_edges);
 293
 294   /* Note that even though we want an optimistic setting of LATER, we
 295      do not want to be overly optimistic.  Consider an outgoing edge from
 296      the entry block.  That edge should always have a LATER value the
 297      same as EARLIEST for that edge.  */
 298   for (e = ENTRY_BLOCK_PTR->succ; e; e = e->succ_next)
 299     sbitmap_copy (later[(size_t) e->aux], earliest[(size_t) e->aux]);
 300
 301   /* Add all the blocks to the worklist.  This prevents an early exit from
 302      the loop given our optimistic initialization of LATER above.  */
 303   for (bb = 0; bb < n_basic_blocks; bb++)
 304     {
 305       basic_block b = BASIC_BLOCK (bb);
 306       *qin++ = b;
 307       b->aux = b;
 308     }
 309   qin = worklist;
 310   /* Note that we do not use the last allocated element for our queue,
 311      as EXIT_BLOCK is never inserted into it. In fact the above allocation
 312      of n_basic_blocks + 1 elements is not encessary.  */
 313   qend = &worklist[n_basic_blocks];
 314   qlen = n_basic_blocks;
 315
 316   /* Iterate until the worklist is empty.  */
 317   while (qlen)
 318     {
 319       /* Take the first entry off the worklist.  */
 320       basic_block b = *qout++;
 321       b->aux = NULL;
 322       qlen--;
 323       if (qout >= qend)
 324         qout = worklist;
 325
 326       /* Compute the intersection of LATERIN for each incoming edge to B.  */
 327       bb = b->index;
 328       sbitmap_ones (laterin[bb]);
 329       for (e = b->pred; e != NULL; e = e->pred_next)
 330         sbitmap_a_and_b (laterin[bb], laterin[bb], later[(size_t)e->aux]);
 331
 332       /* Calculate LATER for all outgoing edges.  */
 333       for (e = b->succ; e != NULL; e = e->succ_next)
 334         if (sbitmap_union_of_diff (later[(size_t) e->aux],
 335                                    earliest[(size_t) e->aux],
 336                                    laterin[e->src->index],
 337                                    antloc[e->src->index])
 338             /* If LATER for an outgoing edge was changed, then we need
 339                to add the target of the outgoing edge to the worklist.  */
 340             && e->dest != EXIT_BLOCK_PTR && e->dest->aux == 0)
 341           {
 342             *qin++ = e->dest;
 343             e->dest->aux = e;
 344             qlen++;
 345             if (qin >= qend)
 346               qin = worklist;
 347           }
 348     }
 349
 350   /* Computation of insertion and deletion points requires computing LATERIN
 351      for the EXIT block.  We allocated an extra entry in the LATERIN array
 352      for just this purpose.  */
 353   sbitmap_ones (laterin[n_basic_blocks]);
 354   for (e = EXIT_BLOCK_PTR->pred; e != NULL; e = e->pred_next)
 355     sbitmap_a_and_b (laterin[n_basic_blocks],
 356                      laterin[n_basic_blocks],
 357                      later[(size_t) e->aux]);
 358
 359   clear_aux_for_edges ();
 360   free (worklist);
 361 }
 362
 363 /* Compute the insertion and deletion points for edge based LCM.  */
 364
 365 static void
 366 compute_insert_delete (edge_list, antloc, later, laterin,
 367                        insert, delete)
 368      struct edge_list *edge_list;
 369      sbitmap *antloc, *later, *laterin, *insert, *delete;
 370 {
 371   int x;
 372
 373   for (x = 0; x < n_basic_blocks; x++)
 374     sbitmap_difference (delete[x], antloc[x], laterin[x]);
 375
 376   for (x = 0; x < NUM_EDGES (edge_list); x++)
 377     {
 378       basic_block b = INDEX_EDGE_SUCC_BB (edge_list, x);
 379
 380       if (b == EXIT_BLOCK_PTR)
 381         sbitmap_difference (insert[x], later[x], laterin[n_basic_blocks]);
 382       else
 383         sbitmap_difference (insert[x], later[x], laterin[b->index]);
 384     }
 385 }
 386
 387 /* Given local properties TRANSP, ANTLOC, AVOUT, KILL return the insert and
 388    delete vectors for edge based LCM.  Returns an edgelist which is used to
 389    map the insert vector to what edge an expression should be inserted on.  */
 390
 391 struct edge_list *
 392 pre_edge_lcm (file, n_exprs, transp, avloc, antloc, kill, insert, delete)
 393      FILE *file ATTRIBUTE_UNUSED;
 394      int n_exprs;
 395      sbitmap *transp;
 396      sbitmap *avloc;
 397      sbitmap *antloc;
 398      sbitmap *kill;
 399      sbitmap **insert;
 400      sbitmap **delete;
 401 {
 402   sbitmap *antin, *antout, *earliest;
 403   sbitmap *avin, *avout;
 404   sbitmap *later, *laterin;
 405   struct edge_list *edge_list;
 406   int num_edges;
 407
 408   edge_list = create_edge_list ();
 409   num_edges = NUM_EDGES (edge_list);
 410
 411 #ifdef LCM_DEBUG_INFO
 412   if (file)
 413     {
 414       fprintf (file, "Edge List:\n");
 415       verify_edge_list (file, edge_list);
 416       print_edge_list (file, edge_list);
 417       dump_sbitmap_vector (file, "transp", "", transp, n_basic_blocks);
 418       dump_sbitmap_vector (file, "antloc", "", antloc, n_basic_blocks);
 419       dump_sbitmap_vector (file, "avloc", "", avloc, n_basic_blocks);
 420       dump_sbitmap_vector (file, "kill", "", kill, n_basic_blocks);
 421     }
 422 #endif
 423
 424   /* Compute global availability.  */
 425   avin = sbitmap_vector_alloc (n_basic_blocks, n_exprs);
 426   avout = sbitmap_vector_alloc (n_basic_blocks, n_exprs);
 427   compute_available (avloc, kill, avout, avin);
 428   sbitmap_vector_free (avin);
 429
 430   /* Compute global anticipatability.  */
 431   antin = sbitmap_vector_alloc (n_basic_blocks, n_exprs);
 432   antout = sbitmap_vector_alloc (n_basic_blocks, n_exprs);
 433   compute_antinout_edge (antloc, transp, antin, antout);
 434
 435 #ifdef LCM_DEBUG_INFO
 436   if (file)
 437     {
 438       dump_sbitmap_vector (file, "antin", "", antin, n_basic_blocks);
 439       dump_sbitmap_vector (file, "antout", "", antout, n_basic_blocks);
 440     }
 441 #endif
 442
 443   /* Compute earliestness.  */
 444   earliest = sbitmap_vector_alloc (num_edges, n_exprs);
 445   compute_earliest (edge_list, n_exprs, antin, antout, avout, kill, earliest);
 446
 447 #ifdef LCM_DEBUG_INFO
 448   if (file)
 449     dump_sbitmap_vector (file, "earliest", "", earliest, num_edges);
 450 #endif
 451
 452   sbitmap_vector_free (antout);
 453   sbitmap_vector_free (antin);
 454   sbitmap_vector_free (avout);
 455
 456   later = sbitmap_vector_alloc (num_edges, n_exprs);
 457
 458   /* Allocate an extra element for the exit block in the laterin vector.  */
 459   laterin = sbitmap_vector_alloc (n_basic_blocks + 1, n_exprs);
 460   compute_laterin (edge_list, earliest, antloc, later, laterin);
 461
 462 #ifdef LCM_DEBUG_INFO
 463   if (file)
 464     {
 465       dump_sbitmap_vector (file, "laterin", "", laterin, n_basic_blocks + 1);
 466       dump_sbitmap_vector (file, "later", "", later, num_edges);
 467     }
 468 #endif
 469
 470   sbitmap_vector_free (earliest);
 471
 472   *insert = sbitmap_vector_alloc (num_edges, n_exprs);
 473   *delete = sbitmap_vector_alloc (n_basic_blocks, n_exprs);
 474   compute_insert_delete (edge_list, antloc, later, laterin, *insert, *delete);
 475
 476   sbitmap_vector_free (laterin);
 477   sbitmap_vector_free (later);
 478
 479 #ifdef LCM_DEBUG_INFO
 480   if (file)
 481     {
 482       dump_sbitmap_vector (file, "pre_insert_map", "", *insert, num_edges);
 483       dump_sbitmap_vector (file, "pre_delete_map", "", *delete,
 484                            n_basic_blocks);
 485     }
 486 #endif
 487
 488   return edge_list;
 489 }
 490
 491 /* Compute the AVIN and AVOUT vectors from the AVLOC and KILL vectors.
 492    Return the number of passes we performed to iterate to a solution.  */
 493
 494 void
 495 compute_available (avloc, kill, avout, avin)
 496      sbitmap *avloc, *kill, *avout, *avin;
 497 {
 498   int bb;
 499   edge e;
 500   basic_block *worklist, *qin, *qout, *qend;
 501   unsigned int qlen;
 502
 503   /* Allocate a worklist array/queue.  Entries are only added to the
 504      list if they were not already on the list.  So the size is
 505      bounded by the number of basic blocks.  */
 506   qin = qout = worklist
 507     = (basic_block *) xmalloc (sizeof (basic_block) * n_basic_blocks);
 508
 509   /* We want a maximal solution.  */
 510   sbitmap_vector_ones (avout, n_basic_blocks);
 511
 512   /* Put every block on the worklist; this is necessary because of the
 513      optimistic initialization of AVOUT above.  */
 514   for (bb = 0; bb < n_basic_blocks; bb++)
 515     {
 516       *qin++ = BASIC_BLOCK (bb);
 517       BASIC_BLOCK (bb)->aux = BASIC_BLOCK (bb);
 518     }
 519
 520   qin = worklist;
 521   qend = &worklist[n_basic_blocks];
 522   qlen = n_basic_blocks;
 523
 524   /* Mark blocks which are successors of the entry block so that we
 525      can easily identify them below.  */
 526   for (e = ENTRY_BLOCK_PTR->succ; e; e = e->succ_next)
 527     e->dest->aux = ENTRY_BLOCK_PTR;
 528
 529   /* Iterate until the worklist is empty.  */
 530   while (qlen)
 531     {
 532       /* Take the first entry off the worklist.  */
 533       basic_block b = *qout++;
 534       bb = b->index;
 535       qlen--;
 536
 537       if (qout >= qend)
 538         qout = worklist;
 539
 540       /* If one of the predecessor blocks is the ENTRY block, then the
 541          intersection of avouts is the null set.  We can identify such blocks
 542          by the special value in the AUX field in the block structure.  */
 543       if (b->aux == ENTRY_BLOCK_PTR)
 544         /* Do not clear the aux field for blocks which are successors of the
 545            ENTRY block.  That way we never add then to the worklist again.  */
 546         sbitmap_zero (avin[bb]);
 547       else
 548         {
 549           /* Clear the aux field of this block so that it can be added to
 550              the worklist again if necessary.  */
 551           b->aux = NULL;
 552           sbitmap_intersection_of_preds (avin[bb], avout, bb);
 553         }
 554
 555       if (sbitmap_union_of_diff (avout[bb], avloc[bb], avin[bb], kill[bb]))
 556         /* If the out state of this block changed, then we need
 557            to add the successors of this block to the worklist
 558            if they are not already on the worklist.  */
 559         for (e = b->succ; e; e = e->succ_next)
 560           if (!e->dest->aux && e->dest != EXIT_BLOCK_PTR)
 561             {
 562               *qin++ = e->dest;
 563               e->dest->aux = e;
 564               qlen++;
 565
 566               if (qin >= qend)
 567                 qin = worklist;
 568             }
 569     }
 570
 571   clear_aux_for_edges ();
 572   clear_aux_for_blocks ();
 573   free (worklist);
 574 }
 575
 576 /* Compute the farthest vector for edge based lcm.  */
 577
 578 static void
 579 compute_farthest (edge_list, n_exprs, st_avout, st_avin, st_antin,
 580                   kill, farthest)
 581      struct edge_list *edge_list;
 582      int n_exprs;
 583      sbitmap *st_avout, *st_avin, *st_antin, *kill, *farthest;
 584 {
 585   sbitmap difference, temp_bitmap;
 586   int x, num_edges;
 587   basic_block pred, succ;
 588
 589   num_edges = NUM_EDGES (edge_list);
 590
 591   difference = sbitmap_alloc (n_exprs);
 592   temp_bitmap = sbitmap_alloc (n_exprs);
 593
 594   for (x = 0; x < num_edges; x++)
 595     {
 596       pred = INDEX_EDGE_PRED_BB (edge_list, x);
 597       succ = INDEX_EDGE_SUCC_BB (edge_list, x);
 598       if (succ == EXIT_BLOCK_PTR)
 599         sbitmap_copy (farthest[x], st_avout[pred->index]);
 600       else
 601         {
 602           if (pred == ENTRY_BLOCK_PTR)
 603             sbitmap_zero (farthest[x]);
 604           else
 605             {
 606               sbitmap_difference (difference, st_avout[pred->index],
 607                                   st_antin[succ->index]);
 608               sbitmap_not (temp_bitmap, st_avin[succ->index]);
 609               sbitmap_a_and_b_or_c (farthest[x], difference,
 610                                     kill[succ->index], temp_bitmap);
 611             }
 612         }
 613     }
 614
 615   sbitmap_free (temp_bitmap);
 616   sbitmap_free (difference);
 617 }
 618
 619 /* Compute nearer and nearerout vectors for edge based lcm.
 620
 621    This is the mirror of compute_laterin, additional comments on the
 622    implementation can be found before compute_laterin.  */
 623
 624 static void
 625 compute_nearerout (edge_list, farthest, st_avloc, nearer, nearerout)
 626      struct edge_list *edge_list;
 627      sbitmap *farthest, *st_avloc, *nearer, *nearerout;
 628 {
 629   int bb, num_edges, i;
 630   edge e;
 631   basic_block *worklist, *tos;
 632
 633   num_edges = NUM_EDGES (edge_list);
 634
 635   /* Allocate a worklist array/queue.  Entries are only added to the
 636      list if they were not already on the list.  So the size is
 637      bounded by the number of basic blocks.  */
 638   tos = worklist
 639     = (basic_block *) xmalloc (sizeof (basic_block) * (n_basic_blocks + 1));
 640
 641   /* Initialize NEARER for each edge and build a mapping from an edge to
 642      its index.  */
 643   for (i = 0; i < num_edges; i++)
 644     INDEX_EDGE (edge_list, i)->aux = (void *) (size_t) i;
 645
 646   /* We want a maximal solution.  */
 647   sbitmap_vector_ones (nearer, num_edges);
 648
 649   /* Note that even though we want an optimistic setting of NEARER, we
 650      do not want to be overly optimistic.  Consider an incoming edge to
 651      the exit block.  That edge should always have a NEARER value the
 652      same as FARTHEST for that edge.  */
 653   for (e = EXIT_BLOCK_PTR->pred; e; e = e->pred_next)
 654     sbitmap_copy (nearer[(size_t)e->aux], farthest[(size_t)e->aux]);
 655
 656   /* Add all the blocks to the worklist.  This prevents an early exit
 657      from the loop given our optimistic initialization of NEARER.  */
 658   for (bb = 0; bb < n_basic_blocks; bb++)
 659     {
 660       basic_block b = BASIC_BLOCK (bb);
 661       *tos++ = b;
 662       b->aux = b;
 663     }
 664
 665   /* Iterate until the worklist is empty.  */
 666   while (tos != worklist)
 667     {
 668       /* Take the first entry off the worklist.  */
 669       basic_block b = *--tos;
 670       b->aux = NULL;
 671
 672       /* Compute the intersection of NEARER for each outgoing edge from B.  */
 673       bb = b->index;
 674       sbitmap_ones (nearerout[bb]);
 675       for (e = b->succ; e != NULL; e = e->succ_next)
 676         sbitmap_a_and_b (nearerout[bb], nearerout[bb],
 677                          nearer[(size_t) e->aux]);
 678
 679       /* Calculate NEARER for all incoming edges.  */
 680       for (e = b->pred; e != NULL; e = e->pred_next)
 681         if (sbitmap_union_of_diff (nearer[(size_t) e->aux],
 682                                    farthest[(size_t) e->aux],
 683                                    nearerout[e->dest->index],
 684                                    st_avloc[e->dest->index])
 685             /* If NEARER for an incoming edge was changed, then we need
 686                to add the source of the incoming edge to the worklist.  */
 687             && e->src != ENTRY_BLOCK_PTR && e->src->aux == 0)
 688           {
 689             *tos++ = e->src;
 690             e->src->aux = e;
 691           }
 692     }
 693
 694   /* Computation of insertion and deletion points requires computing NEAREROUT
 695      for the ENTRY block.  We allocated an extra entry in the NEAREROUT array
 696      for just this purpose.  */
 697   sbitmap_ones (nearerout[n_basic_blocks]);
 698   for (e = ENTRY_BLOCK_PTR->succ; e != NULL; e = e->succ_next)
 699     sbitmap_a_and_b (nearerout[n_basic_blocks],
 700                      nearerout[n_basic_blocks],
 701                      nearer[(size_t) e->aux]);
 702
 703   clear_aux_for_edges ();
 704   free (tos);
 705 }
 706
 707 /* Compute the insertion and deletion points for edge based LCM.  */
 708
 709 static void
 710 compute_rev_insert_delete (edge_list, st_avloc, nearer, nearerout,
 711                            insert, delete)
 712      struct edge_list *edge_list;
 713      sbitmap *st_avloc, *nearer, *nearerout, *insert, *delete;
 714 {
 715   int x;
 716
 717   for (x = 0; x < n_basic_blocks; x++)
 718     sbitmap_difference (delete[x], st_avloc[x], nearerout[x]);
 719
 720   for (x = 0; x < NUM_EDGES (edge_list); x++)
 721     {
 722       basic_block b = INDEX_EDGE_PRED_BB (edge_list, x);
 723       if (b == ENTRY_BLOCK_PTR)
 724         sbitmap_difference (insert[x], nearer[x], nearerout[n_basic_blocks]);
 725       else
 726         sbitmap_difference (insert[x], nearer[x], nearerout[b->index]);
 727     }
 728 }
 729
 730 /* Given local properties TRANSP, ST_AVLOC, ST_ANTLOC, KILL return the
 731    insert and delete vectors for edge based reverse LCM.  Returns an
 732    edgelist which is used to map the insert vector to what edge
 733    an expression should be inserted on.  */
 734
 735 struct edge_list *
 736 pre_edge_rev_lcm (file, n_exprs, transp, st_avloc, st_antloc, kill,
 737                   insert, delete)
 738      FILE *file ATTRIBUTE_UNUSED;
 739      int n_exprs;
 740      sbitmap *transp;
 741      sbitmap *st_avloc;
 742      sbitmap *st_antloc;
 743      sbitmap *kill;
 744      sbitmap **insert;
 745      sbitmap **delete;
 746 {
 747   sbitmap *st_antin, *st_antout;
 748   sbitmap *st_avout, *st_avin, *farthest;
 749   sbitmap *nearer, *nearerout;
 750   struct edge_list *edge_list;
 751   int num_edges;
 752
 753   edge_list = create_edge_list ();
 754   num_edges = NUM_EDGES (edge_list);
 755
 756   st_antin = (sbitmap *) sbitmap_vector_alloc (n_basic_blocks, n_exprs);
 757   st_antout = (sbitmap *) sbitmap_vector_alloc (n_basic_blocks, n_exprs);
 758   sbitmap_vector_zero (st_antin, n_basic_blocks);
 759   sbitmap_vector_zero (st_antout, n_basic_blocks);
 760   compute_antinout_edge (st_antloc, transp, st_antin, st_antout);
 761
 762   /* Compute global anticipatability.  */
 763   st_avout = sbitmap_vector_alloc (n_basic_blocks, n_exprs);
 764   st_avin = sbitmap_vector_alloc (n_basic_blocks, n_exprs);
 765   compute_available (st_avloc, kill, st_avout, st_avin);
 766
 767 #ifdef LCM_DEBUG_INFO
 768   if (file)
 769     {
 770       fprintf (file, "Edge List:\n");
 771       verify_edge_list (file, edge_list);
 772       print_edge_list (file, edge_list);
 773       dump_sbitmap_vector (file, "transp", "", transp, n_basic_blocks);
 774       dump_sbitmap_vector (file, "st_avloc", "", st_avloc, n_basic_blocks);
 775       dump_sbitmap_vector (file, "st_antloc", "", st_antloc, n_basic_blocks);
 776       dump_sbitmap_vector (file, "st_antin", "", st_antin, n_basic_blocks);
 777       dump_sbitmap_vector (file, "st_antout", "", st_antout, n_basic_blocks);
 778       dump_sbitmap_vector (file, "st_kill", "", kill, n_basic_blocks);
 779     }
 780 #endif
 781
 782 #ifdef LCM_DEBUG_INFO
 783   if (file)
 784     {
 785       dump_sbitmap_vector (file, "st_avout", "", st_avout, n_basic_blocks);
 786       dump_sbitmap_vector (file, "st_avin", "", st_avin, n_basic_blocks);
 787     }
 788 #endif
 789
 790   /* Compute farthestness.  */
 791   farthest = sbitmap_vector_alloc (num_edges, n_exprs);
 792   compute_farthest (edge_list, n_exprs, st_avout, st_avin, st_antin,
 793                     kill, farthest);
 794
 795 #ifdef LCM_DEBUG_INFO
 796   if (file)
 797     dump_sbitmap_vector (file, "farthest", "", farthest, num_edges);
 798 #endif
 799
 800   sbitmap_vector_free (st_antin);
 801   sbitmap_vector_free (st_antout);
 802
 803   sbitmap_vector_free (st_avin);
 804   sbitmap_vector_free (st_avout);
 805
 806   nearer = sbitmap_vector_alloc (num_edges, n_exprs);
 807
 808   /* Allocate an extra element for the entry block.  */
 809   nearerout = sbitmap_vector_alloc (n_basic_blocks + 1, n_exprs);
 810   compute_nearerout (edge_list, farthest, st_avloc, nearer, nearerout);
 811
 812 #ifdef LCM_DEBUG_INFO
 813   if (file)
 814     {
 815       dump_sbitmap_vector (file, "nearerout", "", nearerout,
 816                            n_basic_blocks + 1);
 817       dump_sbitmap_vector (file, "nearer", "", nearer, num_edges);
 818     }
 819 #endif
 820
 821   sbitmap_vector_free (farthest);
 822
 823   *insert = sbitmap_vector_alloc (num_edges, n_exprs);
 824   *delete = sbitmap_vector_alloc (n_basic_blocks, n_exprs);
 825   compute_rev_insert_delete (edge_list, st_avloc, nearer, nearerout,
 826                              *insert, *delete);
 827
 828   sbitmap_vector_free (nearerout);
 829   sbitmap_vector_free (nearer);
 830
 831 #ifdef LCM_DEBUG_INFO
 832   if (file)
 833     {
 834       dump_sbitmap_vector (file, "pre_insert_map", "", *insert, num_edges);
 835       dump_sbitmap_vector (file, "pre_delete_map", "", *delete,
 836                            n_basic_blocks);
 837     }
 838 #endif
 839   return edge_list;
 840 }
 841
 842 /* Mode switching:
 843
 844    The algorithm for setting the modes consists of scanning the insn list
 845    and finding all the insns which require a specific mode.  Each insn gets
 846    a unique struct seginfo element.  These structures are inserted into a list
 847    for each basic block.  For each entity, there is an array of bb_info over
 848    the flow graph basic blocks (local var 'bb_info'), and contains a list
 849    of all insns within that basic block, in the order they are encountered.
 850
 851    For each entity, any basic block WITHOUT any insns requiring a specific
 852    mode are given a single entry, without a mode.  (Each basic block
 853    in the flow graph must have at least one entry in the segment table.)
 854
 855    The LCM algorithm is then run over the flow graph to determine where to
 856    place the sets to the highest-priority value in respect of first the first
 857    insn in any one block.  Any adjustments required to the transparancy
 858    vectors are made, then the next iteration starts for the next-lower
 859    priority mode, till for each entity all modes are exhasted.
 860
 861    More details are located in the code for optimize_mode_switching().  */
 862
 863 /* This structure contains the information for each insn which requires
 864    either single or double mode to be set.
 865    MODE is the mode this insn must be executed in.
 866    INSN_PTR is the insn to be executed (may be the note that marks the
 867    beginning of a basic block).
 868    BBNUM is the flow graph basic block this insn occurs in.
 869    NEXT is the next insn in the same basic block.  */
 870 struct seginfo
 871 {
 872   int mode;
 873   rtx insn_ptr;
 874   int bbnum;
 875   struct seginfo *next;
 876   HARD_REG_SET regs_live;
 877 };
 878
 879 struct bb_info
 880 {
 881   struct seginfo *seginfo;
 882   int computing;
 883 };
 884
 885 /* These bitmaps are used for the LCM algorithm.  */
 886
 887 #ifdef OPTIMIZE_MODE_SWITCHING
 888 static sbitmap *antic;
 889 static sbitmap *transp;
 890 static sbitmap *comp;
 891 static sbitmap *delete;
 892 static sbitmap *insert;
 893
 894 static struct seginfo * new_seginfo PARAMS ((int, rtx, int, HARD_REG_SET));
 895 static void add_seginfo PARAMS ((struct bb_info *, struct seginfo *));
 896 static void reg_dies PARAMS ((rtx, HARD_REG_SET));
 897 static void reg_becomes_live PARAMS ((rtx, rtx, void *));
 898 static void make_preds_opaque PARAMS ((basic_block, int));
 899 #endif
 900 \f
 901 #ifdef OPTIMIZE_MODE_SWITCHING
 902
 903 /* This function will allocate a new BBINFO structure, initialized
 904    with the MODE, INSN, and basic block BB parameters.  */
 905
 906 static struct seginfo *
 907 new_seginfo (mode, insn, bb, regs_live)
 908      int mode;
 909      rtx insn;
 910      int bb;
 911      HARD_REG_SET regs_live;
 912 {
 913   struct seginfo *ptr;
 914   ptr = xmalloc (sizeof (struct seginfo));
 915   ptr->mode = mode;
 916   ptr->insn_ptr = insn;
 917   ptr->bbnum = bb;
 918   ptr->next = NULL;
 919   COPY_HARD_REG_SET (ptr->regs_live, regs_live);
 920   return ptr;
 921 }
 922
 923 /* Add a seginfo element to the end of a list.
 924    HEAD is a pointer to the list beginning.
 925    INFO is the structure to be linked in.  */
 926
 927 static void
 928 add_seginfo (head, info)
 929      struct bb_info *head;
 930      struct seginfo *info;
 931 {
 932   struct seginfo *ptr;
 933
 934   if (head->seginfo == NULL)
 935     head->seginfo = info;
 936   else
 937     {
 938       ptr = head->seginfo;
 939       while (ptr->next != NULL)
 940         ptr = ptr->next;
 941       ptr->next = info;
 942     }
 943 }
 944
 945 /* Make all predecessors of basic block B opaque, recursively, till we hit
 946    some that are already non-transparent, or an edge where aux is set; that
 947    denotes that a mode set is to be done on that edge.
 948    J is the bit number in the bitmaps that corresponds to the entity that
 949    we are currently handling mode-switching for.  */
 950
 951 static void
 952 make_preds_opaque (b, j)
 953      basic_block b;
 954      int j;
 955 {
 956   edge e;
 957
 958   for (e = b->pred; e; e = e->pred_next)
 959     {
 960       basic_block pb = e->src;
 961
 962       if (e->aux || ! TEST_BIT (transp[pb->index], j))
 963         continue;
 964
 965       RESET_BIT (transp[pb->index], j);
 966       make_preds_opaque (pb, j);
 967     }
 968 }
 969
 970 /* Record in LIVE that register REG died.  */
 971
 972 static void
 973 reg_dies (reg, live)
 974      rtx reg;
 975      HARD_REG_SET live;
 976 {
 977   int regno, nregs;
 978
 979   if (GET_CODE (reg) != REG)
 980     return;
 981
 982   regno = REGNO (reg);
 983   if (regno < FIRST_PSEUDO_REGISTER)
 984     for (nregs = HARD_REGNO_NREGS (regno, GET_MODE (reg)) - 1; nregs >= 0;
 985          nregs--)
 986       CLEAR_HARD_REG_BIT (live, regno + nregs);
 987 }
 988
 989 /* Record in LIVE that register REG became live.
 990    This is called via note_stores.  */
 991
 992 static void
 993 reg_becomes_live (reg, setter, live)
 994      rtx reg;
 995      rtx setter ATTRIBUTE_UNUSED;
 996      void *live;
 997 {
 998   int regno, nregs;
 999
1000   if (GET_CODE (reg) == SUBREG)
1001     reg = SUBREG_REG (reg);
1002
1003   if (GET_CODE (reg) != REG)
1004     return;
1005
1006   regno = REGNO (reg);
1007   if (regno < FIRST_PSEUDO_REGISTER)
1008     for (nregs = HARD_REGNO_NREGS (regno, GET_MODE (reg)) - 1; nregs >= 0;
1009          nregs--)
1010       SET_HARD_REG_BIT (* (HARD_REG_SET *) live, regno + nregs);
1011 }
1012
1013 /* Find all insns that need a particular mode setting, and insert the
1014    necessary mode switches.  Return true if we did work.  */
1015
1016 int
1017 optimize_mode_switching (file)
1018      FILE *file;
1019 {
1020   rtx insn;
1021   int bb, e;
1022   int need_commit = 0;
1023   sbitmap *kill;
1024   struct edge_list *edge_list;
1025   static const int num_modes[] = NUM_MODES_FOR_MODE_SWITCHING;
1026 #define N_ENTITIES (sizeof num_modes / sizeof (int))
1027   int entity_map[N_ENTITIES];
1028   struct bb_info *bb_info[N_ENTITIES];
1029   int i, j;
1030   int n_entities;
1031   int max_num_modes = 0;
1032   bool emited = false;
1033
1034 #ifdef NORMAL_MODE
1035   /* Increment n_basic_blocks before allocating bb_info.  */
1036   n_basic_blocks++;
1037 #endif
1038
1039   for (e = N_ENTITIES - 1, n_entities = 0; e >= 0; e--)
1040     if (OPTIMIZE_MODE_SWITCHING (e))
1041       {
1042         /* Create the list of segments within each basic block.  */
1043         bb_info[n_entities]
1044           = (struct bb_info *) xcalloc (n_basic_blocks, sizeof **bb_info);
1045         entity_map[n_entities++] = e;
1046         if (num_modes[e] > max_num_modes)
1047           max_num_modes = num_modes[e];
1048       }
1049
1050 #ifdef NORMAL_MODE
1051   /* Decrement it back in case we return below.  */
1052   n_basic_blocks--;
1053 #endif
1054
1055   if (! n_entities)
1056     return 0;
1057
1058 #ifdef NORMAL_MODE
1059   /* We're going to pretend the EXIT_BLOCK is a regular basic block,
1060      so that switching back to normal mode when entering the
1061      EXIT_BLOCK isn't optimized away.  We do this by incrementing the
1062      basic block count, growing the VARRAY of basic_block_info and
1063      appending the EXIT_BLOCK_PTR to it.  */
1064   n_basic_blocks++;
1065   if (VARRAY_SIZE (basic_block_info) < n_basic_blocks)
1066     VARRAY_GROW (basic_block_info, n_basic_blocks);
1067   BASIC_BLOCK (n_basic_blocks - 1) = EXIT_BLOCK_PTR;
1068   EXIT_BLOCK_PTR->index = n_basic_blocks - 1;
1069 #endif
1070
1071   /* Create the bitmap vectors.  */
1072
1073   antic = sbitmap_vector_alloc (n_basic_blocks, n_entities);
1074   transp = sbitmap_vector_alloc (n_basic_blocks, n_entities);
1075   comp = sbitmap_vector_alloc (n_basic_blocks, n_entities);
1076
1077   sbitmap_vector_ones (transp, n_basic_blocks);
1078
1079   for (j = n_entities - 1; j >= 0; j--)
1080     {
1081       int e = entity_map[j];
1082       int no_mode = num_modes[e];
1083       struct bb_info *info = bb_info[j];
1084
1085       /* Determine what the first use (if any) need for a mode of entity E is.
1086          This will be the mode that is anticipatable for this block.
1087          Also compute the initial transparency settings.  */
1088       for (bb = 0 ; bb < n_basic_blocks; bb++)
1089         {
1090           struct seginfo *ptr;
1091           int last_mode = no_mode;
1092           HARD_REG_SET live_now;
1093
1094           REG_SET_TO_HARD_REG_SET (live_now,
1095                                    BASIC_BLOCK (bb)->global_live_at_start);
1096           for (insn = BLOCK_HEAD (bb);
1097                insn != NULL && insn != NEXT_INSN (BLOCK_END (bb));
1098                insn = NEXT_INSN (insn))
1099             {
1100               if (INSN_P (insn))
1101                 {
1102                   int mode = MODE_NEEDED (e, insn);
1103                   rtx link;
1104
1105                   if (mode != no_mode && mode != last_mode)
1106                     {
1107                       last_mode = mode;
1108                       ptr = new_seginfo (mode, insn, bb, live_now);
1109                       add_seginfo (info + bb, ptr);
1110                       RESET_BIT (transp[bb], j);
1111                     }
1112
1113                   /* Update LIVE_NOW.  */
1114                   for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
1115                     if (REG_NOTE_KIND (link) == REG_DEAD)
1116                       reg_dies (XEXP (link, 0), live_now);
1117
1118                   note_stores (PATTERN (insn), reg_becomes_live, &live_now);
1119                   for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
1120                     if (REG_NOTE_KIND (link) == REG_UNUSED)
1121                       reg_dies (XEXP (link, 0), live_now);
1122                 }
1123             }
1124
1125           info[bb].computing = last_mode;
1126           /* Check for blocks without ANY mode requirements.  */
1127           if (last_mode == no_mode)
1128             {
1129               ptr = new_seginfo (no_mode, insn, bb, live_now);
1130               add_seginfo (info + bb, ptr);
1131             }
1132         }
1133 #ifdef NORMAL_MODE
1134       {
1135         int mode = NORMAL_MODE (e);
1136
1137         if (mode != no_mode)
1138           {
1139             edge eg;
1140
1141             for (eg = ENTRY_BLOCK_PTR->succ; eg; eg = eg->succ_next)
1142               {
1143                 bb = eg->dest->index;
1144
1145                 /* By always making this nontransparent, we save
1146                    an extra check in make_preds_opaque.  We also
1147                    need this to avoid confusing pre_edge_lcm when
1148                    antic is cleared but transp and comp are set.  */
1149                 RESET_BIT (transp[bb], j);
1150
1151                 /* If the block already has MODE, pretend it
1152                    has none (because we don't need to set it),
1153                    but retain whatever mode it computes.  */
1154                 if (info[bb].seginfo->mode == mode)
1155                   info[bb].seginfo->mode = no_mode;
1156
1157                 /* Insert a fake computing definition of MODE into entry
1158                    blocks which compute no mode. This represents the mode on
1159                    entry.  */
1160                 else if (info[bb].computing == no_mode)
1161                   {
1162                     info[bb].computing = mode;
1163                     info[bb].seginfo->mode = no_mode;
1164                   }
1165               }
1166
1167             bb = n_basic_blocks - 1;
1168             info[bb].seginfo->mode = mode;
1169           }
1170       }
1171 #endif /* NORMAL_MODE */
1172     }
1173
1174   kill = sbitmap_vector_alloc (n_basic_blocks, n_entities);
1175   for (i = 0; i < max_num_modes; i++)
1176     {
1177       int current_mode[N_ENTITIES];
1178
1179       /* Set the anticipatable and computing arrays.  */
1180       sbitmap_vector_zero (antic, n_basic_blocks);
1181       sbitmap_vector_zero (comp, n_basic_blocks);
1182       for (j = n_entities - 1; j >= 0; j--)
1183         {
1184           int m = current_mode[j] = MODE_PRIORITY_TO_MODE (entity_map[j], i);
1185           struct bb_info *info = bb_info[j];
1186
1187           for (bb = 0 ; bb < n_basic_blocks; bb++)
1188             {
1189               if (info[bb].seginfo->mode == m)
1190                 SET_BIT (antic[bb], j);
1191
1192               if (info[bb].computing == m)
1193                 SET_BIT (comp[bb], j);
1194             }
1195         }
1196
1197       /* Calculate the optimal locations for the
1198          placement mode switches to modes with priority I.  */
1199
1200       for (bb = n_basic_blocks - 1; bb >= 0; bb--)
1201         sbitmap_not (kill[bb], transp[bb]);
1202       edge_list = pre_edge_lcm (file, 1, transp, comp, antic,
1203                                 kill, &insert, &delete);
1204
1205       for (j = n_entities - 1; j >= 0; j--)
1206         {
1207           /* Insert all mode sets that have been inserted by lcm.  */
1208           int no_mode = num_modes[entity_map[j]];
1209
1210           /* Wherever we have moved a mode setting upwards in the flow graph,
1211              the blocks between the new setting site and the now redundant
1212              computation ceases to be transparent for any lower-priority
1213              mode of the same entity.  First set the aux field of each
1214              insertion site edge non-transparent, then propagate the new
1215              non-transparency from the redundant computation upwards till
1216              we hit an insertion site or an already non-transparent block.  */
1217           for (e = NUM_EDGES (edge_list) - 1; e >= 0; e--)
1218             {
1219               edge eg = INDEX_EDGE (edge_list, e);
1220               int mode;
1221               basic_block src_bb;
1222               HARD_REG_SET live_at_edge;
1223               rtx mode_set;
1224
1225               eg->aux = 0;
1226
1227               if (! TEST_BIT (insert[e], j))
1228                 continue;
1229
1230               eg->aux = (void *)1;
1231
1232               mode = current_mode[j];
1233               src_bb = eg->src;
1234
1235               REG_SET_TO_HARD_REG_SET (live_at_edge,
1236                                        src_bb->global_live_at_end);
1237
1238               start_sequence ();
1239               EMIT_MODE_SET (entity_map[j], mode, live_at_edge);
1240               mode_set = gen_sequence ();
1241               end_sequence ();
1242
1243               /* Do not bother to insert empty sequence.  */
1244               if (GET_CODE (mode_set) == SEQUENCE
1245                   && !XVECLEN (mode_set, 0))
1246                 continue;
1247
1248               /* If this is an abnormal edge, we'll insert at the end
1249                  of the previous block.  */
1250               if (eg->flags & EDGE_ABNORMAL)
1251                 {
1252                   emited = true;
1253                   if (GET_CODE (src_bb->end) == JUMP_INSN)
1254                     emit_insn_before (mode_set, src_bb->end);
1255                   /* It doesn't make sense to switch to normal mode
1256                      after a CALL_INSN, so we're going to abort if we
1257                      find one.  The cases in which a CALL_INSN may
1258                      have an abnormal edge are sibcalls and EH edges.
1259                      In the case of sibcalls, the dest basic-block is
1260                      the EXIT_BLOCK, that runs in normal mode; it is
1261                      assumed that a sibcall insn requires normal mode
1262                      itself, so no mode switch would be required after
1263                      the call (it wouldn't make sense, anyway).  In
1264                      the case of EH edges, EH entry points also start
1265                      in normal mode, so a similar reasoning applies.  */
1266                   else if (GET_CODE (src_bb->end) == INSN)
1267                     emit_insn_after (mode_set, src_bb->end);
1268                   else
1269                     abort ();
1270                   bb_info[j][src_bb->index].computing = mode;
1271                   RESET_BIT (transp[src_bb->index], j);
1272                 }
1273               else
1274                 {
1275                   need_commit = 1;
1276                   insert_insn_on_edge (mode_set, eg);
1277                 }
1278             }
1279
1280           for (bb = n_basic_blocks - 1; bb >= 0; bb--)
1281             if (TEST_BIT (delete[bb], j))
1282               {
1283                 make_preds_opaque (BASIC_BLOCK (bb), j);
1284                 /* Cancel the 'deleted' mode set.  */
1285                 bb_info[j][bb].seginfo->mode = no_mode;
1286               }
1287         }
1288
1289       clear_aux_for_edges ();
1290       free_edge_list (edge_list);
1291     }
1292
1293 #ifdef NORMAL_MODE
1294   /* Restore the special status of EXIT_BLOCK.  */
1295   n_basic_blocks--;
1296   VARRAY_POP (basic_block_info);
1297   EXIT_BLOCK_PTR->index = EXIT_BLOCK;
1298 #endif
1299
1300   /* Now output the remaining mode sets in all the segments.  */
1301   for (j = n_entities - 1; j >= 0; j--)
1302     {
1303       int no_mode = num_modes[entity_map[j]];
1304
1305 #ifdef NORMAL_MODE
1306       if (bb_info[j][n_basic_blocks].seginfo->mode != no_mode)
1307         {
1308           edge eg;
1309           struct seginfo *ptr = bb_info[j][n_basic_blocks].seginfo;
1310
1311           for (eg = EXIT_BLOCK_PTR->pred; eg; eg = eg->pred_next)
1312             {
1313               rtx mode_set;
1314
1315               if (bb_info[j][eg->src->index].computing == ptr->mode)
1316                 continue;
1317
1318               start_sequence ();
1319               EMIT_MODE_SET (entity_map[j], ptr->mode, ptr->regs_live);
1320               mode_set = gen_sequence ();
1321               end_sequence ();
1322
1323               /* Do not bother to insert empty sequence.  */
1324               if (GET_CODE (mode_set) == SEQUENCE
1325                   && !XVECLEN (mode_set, 0))
1326                 continue;
1327
1328               /* If this is an abnormal edge, we'll insert at the end of the
1329                  previous block.  */
1330               if (eg->flags & EDGE_ABNORMAL)
1331                 {
1332                   emited = true;
1333                   if (GET_CODE (eg->src->end) == JUMP_INSN)
1334                     emit_insn_before (mode_set, eg->src->end);
1335                   else if (GET_CODE (eg->src->end) == INSN)
1336                     emit_insn_after (mode_set, eg->src->end);
1337                   else
1338                     abort ();
1339                 }
1340               else
1341                 {
1342                   need_commit = 1;
1343                   insert_insn_on_edge (mode_set, eg);
1344                 }
1345             }
1346
1347         }
1348 #endif
1349
1350       for (bb = n_basic_blocks - 1; bb >= 0; bb--)
1351         {
1352           struct seginfo *ptr, *next;
1353           for (ptr = bb_info[j][bb].seginfo; ptr; ptr = next)
1354             {
1355               next = ptr->next;
1356               if (ptr->mode != no_mode)
1357                 {
1358                   rtx mode_set;
1359
1360                   start_sequence ();
1361                   EMIT_MODE_SET (entity_map[j], ptr->mode, ptr->regs_live);
1362                   mode_set = gen_sequence ();
1363                   end_sequence ();
1364
1365                   /* Do not bother to insert empty sequence.  */
1366                   if (GET_CODE (mode_set) == SEQUENCE
1367                       && !XVECLEN (mode_set, 0))
1368                     continue;
1369
1370                   emited = true;
1371                   if (GET_CODE (ptr->insn_ptr) == NOTE
1372                       && (NOTE_LINE_NUMBER (ptr->insn_ptr)
1373                           == NOTE_INSN_BASIC_BLOCK))
1374                     emit_insn_after (mode_set, ptr->insn_ptr);
1375                   else
1376                     emit_insn_before (mode_set, ptr->insn_ptr);
1377                 }
1378
1379               free (ptr);
1380             }
1381         }
1382
1383       free (bb_info[j]);
1384     }
1385
1386   /* Finished. Free up all the things we've allocated.  */
1387
1388   sbitmap_vector_free (kill);
1389   sbitmap_vector_free (antic);
1390   sbitmap_vector_free (transp);
1391   sbitmap_vector_free (comp);
1392   sbitmap_vector_free (delete);
1393   sbitmap_vector_free (insert);
1394
1395   if (need_commit)
1396     commit_edge_insertions ();
1397
1398   if (!need_commit && !emited)
1399     return 0;
1400
1401   /* Ideally we'd figure out what blocks were affected and start from
1402      there, but this is enormously complicated by commit_edge_insertions,
1403      which would screw up any indices we'd collected, and also need to
1404      be involved in the update.  Bail and recompute global life info for
1405      everything.  */
1406
1407   allocate_reg_life_data ();
1408   update_life_info (NULL, UPDATE_LIFE_GLOBAL_RM_NOTES,
1409                     (PROP_DEATH_NOTES | PROP_KILL_DEAD_CODE
1410                      | PROP_SCAN_DEAD_CODE | PROP_REG_INFO));
1411
1412   return 1;
1413 }
1414 #endif /* OPTIMIZE_MODE_SWITCHING */