Index: tree-into-ssa.c
===================================================================
*** tree-into-ssa.c	(revision 115645)
--- tree-into-ssa.c	(working copy)
*************** compute_global_livein (bitmap livein, bi
*** 369,377 ****
--- 369,386 ----
    tos = worklist
      = (basic_block *) xmalloc (sizeof (basic_block) * (last_basic_block + 1));
  
+   /* This function tends to be CPU hog for large CFGs.  Avoid unnecesary
+      bitmap queries by caching the in aux blocks.  */
    EXECUTE_IF_SET_IN_BITMAP (livein, 0, i, bi)
      {
        *tos++ = BASIC_BLOCK (i);
+       gcc_assert (!BASIC_BLOCK (i)->aux);
+       BASIC_BLOCK (i)->aux = (void *)1;
+     }
+   EXECUTE_IF_SET_IN_BITMAP (def_blocks, 0, i, bi)
+     {
+       gcc_assert (!BASIC_BLOCK (i)->aux);
+       BASIC_BLOCK (i)->aux = (void *)1;
      }
  
    /* Iterate until the worklist is empty.  */
*************** compute_global_livein (bitmap livein, bi
*** 390,404 ****
  	  int pred_index = pred->index;
  
  	  /* None of this is necessary for the entry block.  */
! 	  if (pred != ENTRY_BLOCK_PTR
! 	      && ! bitmap_bit_p (livein, pred_index)
! 	      && ! bitmap_bit_p (def_blocks, pred_index))
  	    {
  	      *tos++ = pred;
  	      bitmap_set_bit (livein, pred_index);
  	    }
  	}
      }
  
    free (worklist);
  }
--- 399,416 ----
  	  int pred_index = pred->index;
  
  	  /* None of this is necessary for the entry block.  */
! 	  if (pred != ENTRY_BLOCK_PTR && !bb->aux)
  	    {
  	      *tos++ = pred;
  	      bitmap_set_bit (livein, pred_index);
+ 	      bb->aux = (void *)1;
  	    }
  	}
      }
+   EXECUTE_IF_SET_IN_BITMAP (livein, 0, i, bi)
+     BASIC_BLOCK (i)->aux = NULL;
+   EXECUTE_IF_SET_IN_BITMAP (def_blocks, 0, i, bi)
+     BASIC_BLOCK (i)->aux = NULL;
  
    free (worklist);
  }