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