gcc/lcm.c

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