gcc/lcm.c

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