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