1 /* RTL-level loop invariant motion.
2    Copyright (C) 2004-2018 Free Software Foundation, Inc.
3 
4 This file is part of GCC.
5 
6 GCC is free software; you can redistribute it and/or modify it
7 under the terms of the GNU General Public License as published by the
8 Free Software Foundation; either version 3, or (at your option) any
9 later version.
10 
11 GCC is distributed in the hope that it will be useful, but WITHOUT
12 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
14 for more details.
15 
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING3.  If not see
18 <http://www.gnu.org/licenses/>.  */
19 
20 /* This implements the loop invariant motion pass.  It is very simple
21    (no calls, no loads/stores, etc.).  This should be sufficient to cleanup
22    things like address arithmetics -- other more complicated invariants should
23    be eliminated on GIMPLE either in tree-ssa-loop-im.c or in tree-ssa-pre.c.
24 
25    We proceed loop by loop -- it is simpler than trying to handle things
26    globally and should not lose much.  First we inspect all sets inside loop
27    and create a dependency graph on insns (saying "to move this insn, you must
28    also move the following insns").
29 
30    We then need to determine what to move.  We estimate the number of registers
31    used and move as many invariants as possible while we still have enough free
32    registers.  We prefer the expensive invariants.
33 
34    Then we move the selected invariants out of the loop, creating a new
35    temporaries for them if necessary.  */
36 
37 #include "config.h"
38 #include "system.h"
39 #include "coretypes.h"
40 #include "backend.h"
41 #include "target.h"
42 #include "rtl.h"
43 #include "tree.h"
44 #include "cfghooks.h"
45 #include "df.h"
46 #include "memmodel.h"
47 #include "tm_p.h"
48 #include "insn-config.h"
49 #include "regs.h"
50 #include "ira.h"
51 #include "recog.h"
52 #include "cfgrtl.h"
53 #include "cfgloop.h"
54 #include "expr.h"
55 #include "params.h"
56 #include "rtl-iter.h"
57 #include "dumpfile.h"
58 
59 /* The data stored for the loop.  */
60 
61 struct loop_data
62 {
63   struct loop *outermost_exit;	/* The outermost exit of the loop.  */
64   bool has_call;		/* True if the loop contains a call.  */
65   /* Maximal register pressure inside loop for given register class
66      (defined only for the pressure classes).  */
67   int max_reg_pressure[N_REG_CLASSES];
68   /* Loop regs referenced and live pseudo-registers.  */
69   bitmap_head regs_ref;
70   bitmap_head regs_live;
71 };
72 
73 #define LOOP_DATA(LOOP) ((struct loop_data *) (LOOP)->aux)
74 
75 /* The description of an use.  */
76 
77 struct use
78 {
79   rtx *pos;			/* Position of the use.  */
80   rtx_insn *insn;		/* The insn in that the use occurs.  */
81   unsigned addr_use_p;		/* Whether the use occurs in an address.  */
82   struct use *next;		/* Next use in the list.  */
83 };
84 
85 /* The description of a def.  */
86 
87 struct def
88 {
89   struct use *uses;		/* The list of uses that are uniquely reached
90 				   by it.  */
91   unsigned n_uses;		/* Number of such uses.  */
92   unsigned n_addr_uses;		/* Number of uses in addresses.  */
93   unsigned invno;		/* The corresponding invariant.  */
94   bool can_prop_to_addr_uses;	/* True if the corresponding inv can be
95 				   propagated into its address uses.  */
96 };
97 
98 /* The data stored for each invariant.  */
99 
100 struct invariant
101 {
102   /* The number of the invariant.  */
103   unsigned invno;
104 
105   /* The number of the invariant with the same value.  */
106   unsigned eqto;
107 
108   /* The number of invariants which eqto this.  */
109   unsigned eqno;
110 
111   /* If we moved the invariant out of the loop, the original regno
112      that contained its value.  */
113   int orig_regno;
114 
115   /* If we moved the invariant out of the loop, the register that contains its
116      value.  */
117   rtx reg;
118 
119   /* The definition of the invariant.  */
120   struct def *def;
121 
122   /* The insn in that it is defined.  */
123   rtx_insn *insn;
124 
125   /* Whether it is always executed.  */
126   bool always_executed;
127 
128   /* Whether to move the invariant.  */
129   bool move;
130 
131   /* Whether the invariant is cheap when used as an address.  */
132   bool cheap_address;
133 
134   /* Cost of the invariant.  */
135   unsigned cost;
136 
137   /* Used for detecting already visited invariants during determining
138      costs of movements.  */
139   unsigned stamp;
140 
141   /* The invariants it depends on.  */
142   bitmap depends_on;
143 };
144 
145 /* Currently processed loop.  */
146 static struct loop *curr_loop;
147 
148 /* Table of invariants indexed by the df_ref uid field.  */
149 
150 static unsigned int invariant_table_size = 0;
151 static struct invariant ** invariant_table;
152 
153 /* Entry for hash table of invariant expressions.  */
154 
155 struct invariant_expr_entry
156 {
157   /* The invariant.  */
158   struct invariant *inv;
159 
160   /* Its value.  */
161   rtx expr;
162 
163   /* Its mode.  */
164   machine_mode mode;
165 
166   /* Its hash.  */
167   hashval_t hash;
168 };
169 
170 /* The actual stamp for marking already visited invariants during determining
171    costs of movements.  */
172 
173 static unsigned actual_stamp;
174 
175 typedef struct invariant *invariant_p;
176 
177 
178 /* The invariants.  */
179 
180 static vec<invariant_p> invariants;
181 
182 /* Check the size of the invariant table and realloc if necessary.  */
183 
184 static void
check_invariant_table_size(void)185 check_invariant_table_size (void)
186 {
187   if (invariant_table_size < DF_DEFS_TABLE_SIZE ())
188     {
189       unsigned int new_size = DF_DEFS_TABLE_SIZE () + (DF_DEFS_TABLE_SIZE () / 4);
190       invariant_table = XRESIZEVEC (struct invariant *, invariant_table, new_size);
191       memset (&invariant_table[invariant_table_size], 0,
192 	      (new_size - invariant_table_size) * sizeof (struct invariant *));
193       invariant_table_size = new_size;
194     }
195 }
196 
197 /* Test for possibility of invariantness of X.  */
198 
199 static bool
check_maybe_invariant(rtx x)200 check_maybe_invariant (rtx x)
201 {
202   enum rtx_code code = GET_CODE (x);
203   int i, j;
204   const char *fmt;
205 
206   switch (code)
207     {
208     CASE_CONST_ANY:
209     case SYMBOL_REF:
210     case CONST:
211     case LABEL_REF:
212       return true;
213 
214     case PC:
215     case CC0:
216     case UNSPEC_VOLATILE:
217     case CALL:
218       return false;
219 
220     case REG:
221       return true;
222 
223     case MEM:
224       /* Load/store motion is done elsewhere.  ??? Perhaps also add it here?
225 	 It should not be hard, and might be faster than "elsewhere".  */
226 
227       /* Just handle the most trivial case where we load from an unchanging
228 	 location (most importantly, pic tables).  */
229       if (MEM_READONLY_P (x) && !MEM_VOLATILE_P (x))
230 	break;
231 
232       return false;
233 
234     case ASM_OPERANDS:
235       /* Don't mess with insns declared volatile.  */
236       if (MEM_VOLATILE_P (x))
237 	return false;
238       break;
239 
240     default:
241       break;
242     }
243 
244   fmt = GET_RTX_FORMAT (code);
245   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
246     {
247       if (fmt[i] == 'e')
248 	{
249 	  if (!check_maybe_invariant (XEXP (x, i)))
250 	    return false;
251 	}
252       else if (fmt[i] == 'E')
253 	{
254 	  for (j = 0; j < XVECLEN (x, i); j++)
255 	    if (!check_maybe_invariant (XVECEXP (x, i, j)))
256 	      return false;
257 	}
258     }
259 
260   return true;
261 }
262 
263 /* Returns the invariant definition for USE, or NULL if USE is not
264    invariant.  */
265 
266 static struct invariant *
invariant_for_use(df_ref use)267 invariant_for_use (df_ref use)
268 {
269   struct df_link *defs;
270   df_ref def;
271   basic_block bb = DF_REF_BB (use), def_bb;
272 
273   if (DF_REF_FLAGS (use) & DF_REF_READ_WRITE)
274     return NULL;
275 
276   defs = DF_REF_CHAIN (use);
277   if (!defs || defs->next)
278     return NULL;
279   def = defs->ref;
280   check_invariant_table_size ();
281   if (!invariant_table[DF_REF_ID (def)])
282     return NULL;
283 
284   def_bb = DF_REF_BB (def);
285   if (!dominated_by_p (CDI_DOMINATORS, bb, def_bb))
286     return NULL;
287   return invariant_table[DF_REF_ID (def)];
288 }
289 
290 /* Computes hash value for invariant expression X in INSN.  */
291 
292 static hashval_t
hash_invariant_expr_1(rtx_insn * insn,rtx x)293 hash_invariant_expr_1 (rtx_insn *insn, rtx x)
294 {
295   enum rtx_code code = GET_CODE (x);
296   int i, j;
297   const char *fmt;
298   hashval_t val = code;
299   int do_not_record_p;
300   df_ref use;
301   struct invariant *inv;
302 
303   switch (code)
304     {
305     CASE_CONST_ANY:
306     case SYMBOL_REF:
307     case CONST:
308     case LABEL_REF:
309       return hash_rtx (x, GET_MODE (x), &do_not_record_p, NULL, false);
310 
311     case REG:
312       use = df_find_use (insn, x);
313       if (!use)
314 	return hash_rtx (x, GET_MODE (x), &do_not_record_p, NULL, false);
315       inv = invariant_for_use (use);
316       if (!inv)
317 	return hash_rtx (x, GET_MODE (x), &do_not_record_p, NULL, false);
318 
319       gcc_assert (inv->eqto != ~0u);
320       return inv->eqto;
321 
322     default:
323       break;
324     }
325 
326   fmt = GET_RTX_FORMAT (code);
327   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
328     {
329       if (fmt[i] == 'e')
330 	val ^= hash_invariant_expr_1 (insn, XEXP (x, i));
331       else if (fmt[i] == 'E')
332 	{
333 	  for (j = 0; j < XVECLEN (x, i); j++)
334 	    val ^= hash_invariant_expr_1 (insn, XVECEXP (x, i, j));
335 	}
336       else if (fmt[i] == 'i' || fmt[i] == 'n')
337 	val ^= XINT (x, i);
338       else if (fmt[i] == 'p')
339 	val ^= constant_lower_bound (SUBREG_BYTE (x));
340     }
341 
342   return val;
343 }
344 
345 /* Returns true if the invariant expressions E1 and E2 used in insns INSN1
346    and INSN2 have always the same value.  */
347 
348 static bool
invariant_expr_equal_p(rtx_insn * insn1,rtx e1,rtx_insn * insn2,rtx e2)349 invariant_expr_equal_p (rtx_insn *insn1, rtx e1, rtx_insn *insn2, rtx e2)
350 {
351   enum rtx_code code = GET_CODE (e1);
352   int i, j;
353   const char *fmt;
354   df_ref use1, use2;
355   struct invariant *inv1 = NULL, *inv2 = NULL;
356   rtx sub1, sub2;
357 
358   /* If mode of only one of the operands is VOIDmode, it is not equivalent to
359      the other one.  If both are VOIDmode, we rely on the caller of this
360      function to verify that their modes are the same.  */
361   if (code != GET_CODE (e2) || GET_MODE (e1) != GET_MODE (e2))
362     return false;
363 
364   switch (code)
365     {
366     CASE_CONST_ANY:
367     case SYMBOL_REF:
368     case CONST:
369     case LABEL_REF:
370       return rtx_equal_p (e1, e2);
371 
372     case REG:
373       use1 = df_find_use (insn1, e1);
374       use2 = df_find_use (insn2, e2);
375       if (use1)
376 	inv1 = invariant_for_use (use1);
377       if (use2)
378 	inv2 = invariant_for_use (use2);
379 
380       if (!inv1 && !inv2)
381 	return rtx_equal_p (e1, e2);
382 
383       if (!inv1 || !inv2)
384 	return false;
385 
386       gcc_assert (inv1->eqto != ~0u);
387       gcc_assert (inv2->eqto != ~0u);
388       return inv1->eqto == inv2->eqto;
389 
390     default:
391       break;
392     }
393 
394   fmt = GET_RTX_FORMAT (code);
395   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
396     {
397       if (fmt[i] == 'e')
398 	{
399 	  sub1 = XEXP (e1, i);
400 	  sub2 = XEXP (e2, i);
401 
402 	  if (!invariant_expr_equal_p (insn1, sub1, insn2, sub2))
403 	    return false;
404 	}
405 
406       else if (fmt[i] == 'E')
407 	{
408 	  if (XVECLEN (e1, i) != XVECLEN (e2, i))
409 	    return false;
410 
411 	  for (j = 0; j < XVECLEN (e1, i); j++)
412 	    {
413 	      sub1 = XVECEXP (e1, i, j);
414 	      sub2 = XVECEXP (e2, i, j);
415 
416 	      if (!invariant_expr_equal_p (insn1, sub1, insn2, sub2))
417 		return false;
418 	    }
419 	}
420       else if (fmt[i] == 'i' || fmt[i] == 'n')
421 	{
422 	  if (XINT (e1, i) != XINT (e2, i))
423 	    return false;
424 	}
425       else if (fmt[i] == 'p')
426 	{
427 	  if (maybe_ne (SUBREG_BYTE (e1), SUBREG_BYTE (e2)))
428 	    return false;
429 	}
430       /* Unhandled type of subexpression, we fail conservatively.  */
431       else
432 	return false;
433     }
434 
435   return true;
436 }
437 
438 struct invariant_expr_hasher : free_ptr_hash <invariant_expr_entry>
439 {
440   static inline hashval_t hash (const invariant_expr_entry *);
441   static inline bool equal (const invariant_expr_entry *,
442 			    const invariant_expr_entry *);
443 };
444 
445 /* Returns hash value for invariant expression entry ENTRY.  */
446 
447 inline hashval_t
hash(const invariant_expr_entry * entry)448 invariant_expr_hasher::hash (const invariant_expr_entry *entry)
449 {
450   return entry->hash;
451 }
452 
453 /* Compares invariant expression entries ENTRY1 and ENTRY2.  */
454 
455 inline bool
equal(const invariant_expr_entry * entry1,const invariant_expr_entry * entry2)456 invariant_expr_hasher::equal (const invariant_expr_entry *entry1,
457 			      const invariant_expr_entry *entry2)
458 {
459   if (entry1->mode != entry2->mode)
460     return 0;
461 
462   return invariant_expr_equal_p (entry1->inv->insn, entry1->expr,
463 				 entry2->inv->insn, entry2->expr);
464 }
465 
466 typedef hash_table<invariant_expr_hasher> invariant_htab_type;
467 
468 /* Checks whether invariant with value EXPR in machine mode MODE is
469    recorded in EQ.  If this is the case, return the invariant.  Otherwise
470    insert INV to the table for this expression and return INV.  */
471 
472 static struct invariant *
find_or_insert_inv(invariant_htab_type * eq,rtx expr,machine_mode mode,struct invariant * inv)473 find_or_insert_inv (invariant_htab_type *eq, rtx expr, machine_mode mode,
474 		    struct invariant *inv)
475 {
476   hashval_t hash = hash_invariant_expr_1 (inv->insn, expr);
477   struct invariant_expr_entry *entry;
478   struct invariant_expr_entry pentry;
479   invariant_expr_entry **slot;
480 
481   pentry.expr = expr;
482   pentry.inv = inv;
483   pentry.mode = mode;
484   slot = eq->find_slot_with_hash (&pentry, hash, INSERT);
485   entry = *slot;
486 
487   if (entry)
488     return entry->inv;
489 
490   entry = XNEW (struct invariant_expr_entry);
491   entry->inv = inv;
492   entry->expr = expr;
493   entry->mode = mode;
494   entry->hash = hash;
495   *slot = entry;
496 
497   return inv;
498 }
499 
500 /* Finds invariants identical to INV and records the equivalence.  EQ is the
501    hash table of the invariants.  */
502 
503 static void
find_identical_invariants(invariant_htab_type * eq,struct invariant * inv)504 find_identical_invariants (invariant_htab_type *eq, struct invariant *inv)
505 {
506   unsigned depno;
507   bitmap_iterator bi;
508   struct invariant *dep;
509   rtx expr, set;
510   machine_mode mode;
511   struct invariant *tmp;
512 
513   if (inv->eqto != ~0u)
514     return;
515 
516   EXECUTE_IF_SET_IN_BITMAP (inv->depends_on, 0, depno, bi)
517     {
518       dep = invariants[depno];
519       find_identical_invariants (eq, dep);
520     }
521 
522   set = single_set (inv->insn);
523   expr = SET_SRC (set);
524   mode = GET_MODE (expr);
525   if (mode == VOIDmode)
526     mode = GET_MODE (SET_DEST (set));
527 
528   tmp = find_or_insert_inv (eq, expr, mode, inv);
529   inv->eqto = tmp->invno;
530 
531   if (tmp->invno != inv->invno && inv->always_executed)
532     tmp->eqno++;
533 
534   if (dump_file && inv->eqto != inv->invno)
535     fprintf (dump_file,
536 	     "Invariant %d is equivalent to invariant %d.\n",
537 	     inv->invno, inv->eqto);
538 }
539 
540 /* Find invariants with the same value and record the equivalences.  */
541 
542 static void
merge_identical_invariants(void)543 merge_identical_invariants (void)
544 {
545   unsigned i;
546   struct invariant *inv;
547   invariant_htab_type eq (invariants.length ());
548 
549   FOR_EACH_VEC_ELT (invariants, i, inv)
550     find_identical_invariants (&eq, inv);
551 }
552 
553 /* Determines the basic blocks inside LOOP that are always executed and
554    stores their bitmap to ALWAYS_REACHED.  MAY_EXIT is a bitmap of
555    basic blocks that may either exit the loop, or contain the call that
556    does not have to return.  BODY is body of the loop obtained by
557    get_loop_body_in_dom_order.  */
558 
559 static void
compute_always_reached(struct loop * loop,basic_block * body,bitmap may_exit,bitmap always_reached)560 compute_always_reached (struct loop *loop, basic_block *body,
561 			bitmap may_exit, bitmap always_reached)
562 {
563   unsigned i;
564 
565   for (i = 0; i < loop->num_nodes; i++)
566     {
567       if (dominated_by_p (CDI_DOMINATORS, loop->latch, body[i]))
568 	bitmap_set_bit (always_reached, i);
569 
570       if (bitmap_bit_p (may_exit, i))
571 	return;
572     }
573 }
574 
575 /* Finds exits out of the LOOP with body BODY.  Marks blocks in that we may
576    exit the loop by cfg edge to HAS_EXIT and MAY_EXIT.  In MAY_EXIT
577    additionally mark blocks that may exit due to a call.  */
578 
579 static void
find_exits(struct loop * loop,basic_block * body,bitmap may_exit,bitmap has_exit)580 find_exits (struct loop *loop, basic_block *body,
581 	    bitmap may_exit, bitmap has_exit)
582 {
583   unsigned i;
584   edge_iterator ei;
585   edge e;
586   struct loop *outermost_exit = loop, *aexit;
587   bool has_call = false;
588   rtx_insn *insn;
589 
590   for (i = 0; i < loop->num_nodes; i++)
591     {
592       if (body[i]->loop_father == loop)
593 	{
594 	  FOR_BB_INSNS (body[i], insn)
595 	    {
596 	      if (CALL_P (insn)
597 		  && (RTL_LOOPING_CONST_OR_PURE_CALL_P (insn)
598 		      || !RTL_CONST_OR_PURE_CALL_P (insn)))
599 		{
600 		  has_call = true;
601 		  bitmap_set_bit (may_exit, i);
602 		  break;
603 		}
604 	    }
605 
606 	  FOR_EACH_EDGE (e, ei, body[i]->succs)
607 	    {
608 	      if (! flow_bb_inside_loop_p (loop, e->dest))
609 		{
610 		  bitmap_set_bit (may_exit, i);
611 		  bitmap_set_bit (has_exit, i);
612 		  outermost_exit = find_common_loop (outermost_exit,
613 						     e->dest->loop_father);
614 		}
615 	      /* If we enter a subloop that might never terminate treat
616 	         it like a possible exit.  */
617 	      if (flow_loop_nested_p (loop, e->dest->loop_father))
618 		bitmap_set_bit (may_exit, i);
619 	    }
620 	  continue;
621 	}
622 
623       /* Use the data stored for the subloop to decide whether we may exit
624 	 through it.  It is sufficient to do this for header of the loop,
625 	 as other basic blocks inside it must be dominated by it.  */
626       if (body[i]->loop_father->header != body[i])
627 	continue;
628 
629       if (LOOP_DATA (body[i]->loop_father)->has_call)
630 	{
631 	  has_call = true;
632 	  bitmap_set_bit (may_exit, i);
633 	}
634       aexit = LOOP_DATA (body[i]->loop_father)->outermost_exit;
635       if (aexit != loop)
636 	{
637 	  bitmap_set_bit (may_exit, i);
638 	  bitmap_set_bit (has_exit, i);
639 
640 	  if (flow_loop_nested_p (aexit, outermost_exit))
641 	    outermost_exit = aexit;
642 	}
643     }
644 
645   if (loop->aux == NULL)
646     {
647       loop->aux = xcalloc (1, sizeof (struct loop_data));
648       bitmap_initialize (&LOOP_DATA (loop)->regs_ref, &reg_obstack);
649       bitmap_initialize (&LOOP_DATA (loop)->regs_live, &reg_obstack);
650     }
651   LOOP_DATA (loop)->outermost_exit = outermost_exit;
652   LOOP_DATA (loop)->has_call = has_call;
653 }
654 
655 /* Check whether we may assign a value to X from a register.  */
656 
657 static bool
may_assign_reg_p(rtx x)658 may_assign_reg_p (rtx x)
659 {
660   return (GET_MODE (x) != VOIDmode
661 	  && GET_MODE (x) != BLKmode
662 	  && can_copy_p (GET_MODE (x))
663 	  && (!REG_P (x)
664 	      || !HARD_REGISTER_P (x)
665 	      || REGNO_REG_CLASS (REGNO (x)) != NO_REGS));
666 }
667 
668 /* Finds definitions that may correspond to invariants in LOOP with body
669    BODY.  */
670 
671 static void
find_defs(struct loop * loop)672 find_defs (struct loop *loop)
673 {
674   if (dump_file)
675     {
676       fprintf (dump_file,
677 	       "*****starting processing of loop %d ******\n",
678 	       loop->num);
679     }
680 
681   df_remove_problem (df_chain);
682   df_process_deferred_rescans ();
683   df_chain_add_problem (DF_UD_CHAIN);
684   df_live_add_problem ();
685   df_live_set_all_dirty ();
686   df_set_flags (DF_RD_PRUNE_DEAD_DEFS);
687   df_analyze_loop (loop);
688   check_invariant_table_size ();
689 
690   if (dump_file)
691     {
692       df_dump_region (dump_file);
693       fprintf (dump_file,
694 	       "*****ending processing of loop %d ******\n",
695 	       loop->num);
696     }
697 }
698 
699 /* Creates a new invariant for definition DEF in INSN, depending on invariants
700    in DEPENDS_ON.  ALWAYS_EXECUTED is true if the insn is always executed,
701    unless the program ends due to a function call.  The newly created invariant
702    is returned.  */
703 
704 static struct invariant *
create_new_invariant(struct def * def,rtx_insn * insn,bitmap depends_on,bool always_executed)705 create_new_invariant (struct def *def, rtx_insn *insn, bitmap depends_on,
706 		      bool always_executed)
707 {
708   struct invariant *inv = XNEW (struct invariant);
709   rtx set = single_set (insn);
710   bool speed = optimize_bb_for_speed_p (BLOCK_FOR_INSN (insn));
711 
712   inv->def = def;
713   inv->always_executed = always_executed;
714   inv->depends_on = depends_on;
715 
716   /* If the set is simple, usually by moving it we move the whole store out of
717      the loop.  Otherwise we save only cost of the computation.  */
718   if (def)
719     {
720       inv->cost = set_rtx_cost (set, speed);
721       /* ??? Try to determine cheapness of address computation.  Unfortunately
722          the address cost is only a relative measure, we can't really compare
723 	 it with any absolute number, but only with other address costs.
724 	 But here we don't have any other addresses, so compare with a magic
725 	 number anyway.  It has to be large enough to not regress PR33928
726 	 (by avoiding to move reg+8,reg+16,reg+24 invariants), but small
727 	 enough to not regress 410.bwaves either (by still moving reg+reg
728 	 invariants).
729 	 See http://gcc.gnu.org/ml/gcc-patches/2009-10/msg01210.html .  */
730       if (SCALAR_INT_MODE_P (GET_MODE (SET_DEST (set))))
731 	inv->cheap_address = address_cost (SET_SRC (set), word_mode,
732 					   ADDR_SPACE_GENERIC, speed) < 3;
733       else
734 	inv->cheap_address = false;
735     }
736   else
737     {
738       inv->cost = set_src_cost (SET_SRC (set), GET_MODE (SET_DEST (set)),
739 				speed);
740       inv->cheap_address = false;
741     }
742 
743   inv->move = false;
744   inv->reg = NULL_RTX;
745   inv->orig_regno = -1;
746   inv->stamp = 0;
747   inv->insn = insn;
748 
749   inv->invno = invariants.length ();
750   inv->eqto = ~0u;
751 
752   /* Itself.  */
753   inv->eqno = 1;
754 
755   if (def)
756     def->invno = inv->invno;
757   invariants.safe_push (inv);
758 
759   if (dump_file)
760     {
761       fprintf (dump_file,
762 	       "Set in insn %d is invariant (%d), cost %d, depends on ",
763 	       INSN_UID (insn), inv->invno, inv->cost);
764       dump_bitmap (dump_file, inv->depends_on);
765     }
766 
767   return inv;
768 }
769 
770 /* Return a canonical version of X for the address, from the point of view,
771    that all multiplications are represented as MULT instead of the multiply
772    by a power of 2 being represented as ASHIFT.
773 
774    Callers should prepare a copy of X because this function may modify it
775    in place.  */
776 
777 static void
canonicalize_address_mult(rtx x)778 canonicalize_address_mult (rtx x)
779 {
780   subrtx_var_iterator::array_type array;
781   FOR_EACH_SUBRTX_VAR (iter, array, x, NONCONST)
782     {
783       rtx sub = *iter;
784       scalar_int_mode sub_mode;
785       if (is_a <scalar_int_mode> (GET_MODE (sub), &sub_mode)
786 	  && GET_CODE (sub) == ASHIFT
787 	  && CONST_INT_P (XEXP (sub, 1))
788 	  && INTVAL (XEXP (sub, 1)) < GET_MODE_BITSIZE (sub_mode)
789 	  && INTVAL (XEXP (sub, 1)) >= 0)
790 	{
791 	  HOST_WIDE_INT shift = INTVAL (XEXP (sub, 1));
792 	  PUT_CODE (sub, MULT);
793 	  XEXP (sub, 1) = gen_int_mode (HOST_WIDE_INT_1 << shift, sub_mode);
794 	  iter.skip_subrtxes ();
795 	}
796     }
797 }
798 
799 /* Maximum number of sub expressions in address.  We set it to
800    a small integer since it's unlikely to have a complicated
801    address expression.  */
802 
803 #define MAX_CANON_ADDR_PARTS (5)
804 
805 /* Collect sub expressions in address X with PLUS as the seperator.
806    Sub expressions are stored in vector ADDR_PARTS.  */
807 
808 static void
collect_address_parts(rtx x,vec<rtx> * addr_parts)809 collect_address_parts (rtx x, vec<rtx> *addr_parts)
810 {
811   subrtx_var_iterator::array_type array;
812   FOR_EACH_SUBRTX_VAR (iter, array, x, NONCONST)
813     {
814       rtx sub = *iter;
815 
816       if (GET_CODE (sub) != PLUS)
817 	{
818 	  addr_parts->safe_push (sub);
819 	  iter.skip_subrtxes ();
820 	}
821     }
822 }
823 
824 /* Compare function for sorting sub expressions X and Y based on
825    precedence defined for communitive operations.  */
826 
827 static int
compare_address_parts(const void * x,const void * y)828 compare_address_parts (const void *x, const void *y)
829 {
830   const rtx *rx = (const rtx *)x;
831   const rtx *ry = (const rtx *)y;
832   int px = commutative_operand_precedence (*rx);
833   int py = commutative_operand_precedence (*ry);
834 
835   return (py - px);
836 }
837 
838 /* Return a canonical version address for X by following steps:
839      1) Rewrite ASHIFT into MULT recursively.
840      2) Divide address into sub expressions with PLUS as the
841 	separator.
842      3) Sort sub expressions according to precedence defined
843 	for communative operations.
844      4) Simplify CONST_INT_P sub expressions.
845      5) Create new canonicalized address and return.
846    Callers should prepare a copy of X because this function may
847    modify it in place.  */
848 
849 static rtx
canonicalize_address(rtx x)850 canonicalize_address (rtx x)
851 {
852   rtx res;
853   unsigned int i, j;
854   machine_mode mode = GET_MODE (x);
855   auto_vec<rtx, MAX_CANON_ADDR_PARTS> addr_parts;
856 
857   /* Rewrite ASHIFT into MULT.  */
858   canonicalize_address_mult (x);
859   /* Divide address into sub expressions.  */
860   collect_address_parts (x, &addr_parts);
861   /* Unlikely to have very complicated address.  */
862   if (addr_parts.length () < 2
863       || addr_parts.length () > MAX_CANON_ADDR_PARTS)
864     return x;
865 
866   /* Sort sub expressions according to canonicalization precedence.  */
867   addr_parts.qsort (compare_address_parts);
868 
869   /* Simplify all constant int summary if possible.  */
870   for (i = 0; i < addr_parts.length (); i++)
871     if (CONST_INT_P (addr_parts[i]))
872       break;
873 
874   for (j = i + 1; j < addr_parts.length (); j++)
875     {
876       gcc_assert (CONST_INT_P (addr_parts[j]));
877       addr_parts[i] = simplify_gen_binary (PLUS, mode,
878 					   addr_parts[i],
879 					   addr_parts[j]);
880     }
881 
882   /* Chain PLUS operators to the left for !CONST_INT_P sub expressions.  */
883   res = addr_parts[0];
884   for (j = 1; j < i; j++)
885     res = simplify_gen_binary (PLUS, mode, res, addr_parts[j]);
886 
887   /* Pickup the last CONST_INT_P sub expression.  */
888   if (i < addr_parts.length ())
889     res = simplify_gen_binary (PLUS, mode, res, addr_parts[i]);
890 
891   return res;
892 }
893 
894 /* Given invariant DEF and its address USE, check if the corresponding
895    invariant expr can be propagated into the use or not.  */
896 
897 static bool
inv_can_prop_to_addr_use(struct def * def,df_ref use)898 inv_can_prop_to_addr_use (struct def *def, df_ref use)
899 {
900   struct invariant *inv;
901   rtx *pos = DF_REF_REAL_LOC (use), def_set, use_set;
902   rtx_insn *use_insn = DF_REF_INSN (use);
903   rtx_insn *def_insn;
904   bool ok;
905 
906   inv = invariants[def->invno];
907   /* No need to check if address expression is expensive.  */
908   if (!inv->cheap_address)
909     return false;
910 
911   def_insn = inv->insn;
912   def_set = single_set (def_insn);
913   if (!def_set)
914     return false;
915 
916   validate_unshare_change (use_insn, pos, SET_SRC (def_set), true);
917   ok = verify_changes (0);
918   /* Try harder with canonicalization in address expression.  */
919   if (!ok && (use_set = single_set (use_insn)) != NULL_RTX)
920     {
921       rtx src, dest, mem = NULL_RTX;
922 
923       src = SET_SRC (use_set);
924       dest = SET_DEST (use_set);
925       if (MEM_P (src))
926 	mem = src;
927       else if (MEM_P (dest))
928 	mem = dest;
929 
930       if (mem != NULL_RTX
931 	  && !memory_address_addr_space_p (GET_MODE (mem),
932 					   XEXP (mem, 0),
933 					   MEM_ADDR_SPACE (mem)))
934 	{
935 	  rtx addr = canonicalize_address (copy_rtx (XEXP (mem, 0)));
936 	  if (memory_address_addr_space_p (GET_MODE (mem),
937 					   addr, MEM_ADDR_SPACE (mem)))
938 	    ok = true;
939 	}
940     }
941   cancel_changes (0);
942   return ok;
943 }
944 
945 /* Record USE at DEF.  */
946 
947 static void
record_use(struct def * def,df_ref use)948 record_use (struct def *def, df_ref use)
949 {
950   struct use *u = XNEW (struct use);
951 
952   u->pos = DF_REF_REAL_LOC (use);
953   u->insn = DF_REF_INSN (use);
954   u->addr_use_p = (DF_REF_TYPE (use) == DF_REF_REG_MEM_LOAD
955 		   || DF_REF_TYPE (use) == DF_REF_REG_MEM_STORE);
956   u->next = def->uses;
957   def->uses = u;
958   def->n_uses++;
959   if (u->addr_use_p)
960     {
961       /* Initialize propagation information if this is the first addr
962 	 use of the inv def.  */
963       if (def->n_addr_uses == 0)
964 	def->can_prop_to_addr_uses = true;
965 
966       def->n_addr_uses++;
967       if (def->can_prop_to_addr_uses && !inv_can_prop_to_addr_use (def, use))
968 	def->can_prop_to_addr_uses = false;
969     }
970 }
971 
972 /* Finds the invariants USE depends on and store them to the DEPENDS_ON
973    bitmap.  Returns true if all dependencies of USE are known to be
974    loop invariants, false otherwise.  */
975 
976 static bool
check_dependency(basic_block bb,df_ref use,bitmap depends_on)977 check_dependency (basic_block bb, df_ref use, bitmap depends_on)
978 {
979   df_ref def;
980   basic_block def_bb;
981   struct df_link *defs;
982   struct def *def_data;
983   struct invariant *inv;
984 
985   if (DF_REF_FLAGS (use) & DF_REF_READ_WRITE)
986     return false;
987 
988   defs = DF_REF_CHAIN (use);
989   if (!defs)
990     {
991       unsigned int regno = DF_REF_REGNO (use);
992 
993       /* If this is the use of an uninitialized argument register that is
994 	 likely to be spilled, do not move it lest this might extend its
995 	 lifetime and cause reload to die.  This can occur for a call to
996 	 a function taking complex number arguments and moving the insns
997 	 preparing the arguments without moving the call itself wouldn't
998 	 gain much in practice.  */
999       if ((DF_REF_FLAGS (use) & DF_HARD_REG_LIVE)
1000 	  && FUNCTION_ARG_REGNO_P (regno)
1001 	  && targetm.class_likely_spilled_p (REGNO_REG_CLASS (regno)))
1002 	return false;
1003 
1004       return true;
1005     }
1006 
1007   if (defs->next)
1008     return false;
1009 
1010   def = defs->ref;
1011   check_invariant_table_size ();
1012   inv = invariant_table[DF_REF_ID (def)];
1013   if (!inv)
1014     return false;
1015 
1016   def_data = inv->def;
1017   gcc_assert (def_data != NULL);
1018 
1019   def_bb = DF_REF_BB (def);
1020   /* Note that in case bb == def_bb, we know that the definition
1021      dominates insn, because def has invariant_table[DF_REF_ID(def)]
1022      defined and we process the insns in the basic block bb
1023      sequentially.  */
1024   if (!dominated_by_p (CDI_DOMINATORS, bb, def_bb))
1025     return false;
1026 
1027   bitmap_set_bit (depends_on, def_data->invno);
1028   return true;
1029 }
1030 
1031 
1032 /* Finds the invariants INSN depends on and store them to the DEPENDS_ON
1033    bitmap.  Returns true if all dependencies of INSN are known to be
1034    loop invariants, false otherwise.  */
1035 
1036 static bool
check_dependencies(rtx_insn * insn,bitmap depends_on)1037 check_dependencies (rtx_insn *insn, bitmap depends_on)
1038 {
1039   struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
1040   df_ref use;
1041   basic_block bb = BLOCK_FOR_INSN (insn);
1042 
1043   FOR_EACH_INSN_INFO_USE (use, insn_info)
1044     if (!check_dependency (bb, use, depends_on))
1045       return false;
1046   FOR_EACH_INSN_INFO_EQ_USE (use, insn_info)
1047     if (!check_dependency (bb, use, depends_on))
1048       return false;
1049 
1050   return true;
1051 }
1052 
1053 /* Pre-check candidate DEST to skip the one which can not make a valid insn
1054    during move_invariant_reg.  SIMPLE is to skip HARD_REGISTER.  */
1055 static bool
pre_check_invariant_p(bool simple,rtx dest)1056 pre_check_invariant_p (bool simple, rtx dest)
1057 {
1058   if (simple && REG_P (dest) && DF_REG_DEF_COUNT (REGNO (dest)) > 1)
1059     {
1060       df_ref use;
1061       unsigned int i = REGNO (dest);
1062       struct df_insn_info *insn_info;
1063       df_ref def_rec;
1064 
1065       for (use = DF_REG_USE_CHAIN (i); use; use = DF_REF_NEXT_REG (use))
1066 	{
1067 	  rtx_insn *ref = DF_REF_INSN (use);
1068 	  insn_info = DF_INSN_INFO_GET (ref);
1069 
1070 	  FOR_EACH_INSN_INFO_DEF (def_rec, insn_info)
1071 	    if (DF_REF_REGNO (def_rec) == i)
1072 	      {
1073 		/* Multi definitions at this stage, most likely are due to
1074 		   instruction constraints, which requires both read and write
1075 		   on the same register.  Since move_invariant_reg is not
1076 		   powerful enough to handle such cases, just ignore the INV
1077 		   and leave the chance to others.  */
1078 		return false;
1079 	      }
1080 	}
1081     }
1082   return true;
1083 }
1084 
1085 /* Finds invariant in INSN.  ALWAYS_REACHED is true if the insn is always
1086    executed.  ALWAYS_EXECUTED is true if the insn is always executed,
1087    unless the program ends due to a function call.  */
1088 
1089 static void
find_invariant_insn(rtx_insn * insn,bool always_reached,bool always_executed)1090 find_invariant_insn (rtx_insn *insn, bool always_reached, bool always_executed)
1091 {
1092   df_ref ref;
1093   struct def *def;
1094   bitmap depends_on;
1095   rtx set, dest;
1096   bool simple = true;
1097   struct invariant *inv;
1098 
1099   /* We can't move a CC0 setter without the user.  */
1100   if (HAVE_cc0 && sets_cc0_p (insn))
1101     return;
1102 
1103   set = single_set (insn);
1104   if (!set)
1105     return;
1106   dest = SET_DEST (set);
1107 
1108   if (!REG_P (dest)
1109       || HARD_REGISTER_P (dest))
1110     simple = false;
1111 
1112   if (!may_assign_reg_p (dest)
1113       || !pre_check_invariant_p (simple, dest)
1114       || !check_maybe_invariant (SET_SRC (set)))
1115     return;
1116 
1117   /* If the insn can throw exception, we cannot move it at all without changing
1118      cfg.  */
1119   if (can_throw_internal (insn))
1120     return;
1121 
1122   /* We cannot make trapping insn executed, unless it was executed before.  */
1123   if (may_trap_or_fault_p (PATTERN (insn)) && !always_reached)
1124     return;
1125 
1126   depends_on = BITMAP_ALLOC (NULL);
1127   if (!check_dependencies (insn, depends_on))
1128     {
1129       BITMAP_FREE (depends_on);
1130       return;
1131     }
1132 
1133   if (simple)
1134     def = XCNEW (struct def);
1135   else
1136     def = NULL;
1137 
1138   inv = create_new_invariant (def, insn, depends_on, always_executed);
1139 
1140   if (simple)
1141     {
1142       ref = df_find_def (insn, dest);
1143       check_invariant_table_size ();
1144       invariant_table[DF_REF_ID (ref)] = inv;
1145     }
1146 }
1147 
1148 /* Record registers used in INSN that have a unique invariant definition.  */
1149 
1150 static void
record_uses(rtx_insn * insn)1151 record_uses (rtx_insn *insn)
1152 {
1153   struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
1154   df_ref use;
1155   struct invariant *inv;
1156 
1157   FOR_EACH_INSN_INFO_USE (use, insn_info)
1158     {
1159       inv = invariant_for_use (use);
1160       if (inv)
1161 	record_use (inv->def, use);
1162     }
1163   FOR_EACH_INSN_INFO_EQ_USE (use, insn_info)
1164     {
1165       inv = invariant_for_use (use);
1166       if (inv)
1167 	record_use (inv->def, use);
1168     }
1169 }
1170 
1171 /* Finds invariants in INSN.  ALWAYS_REACHED is true if the insn is always
1172    executed.  ALWAYS_EXECUTED is true if the insn is always executed,
1173    unless the program ends due to a function call.  */
1174 
1175 static void
find_invariants_insn(rtx_insn * insn,bool always_reached,bool always_executed)1176 find_invariants_insn (rtx_insn *insn, bool always_reached, bool always_executed)
1177 {
1178   find_invariant_insn (insn, always_reached, always_executed);
1179   record_uses (insn);
1180 }
1181 
1182 /* Finds invariants in basic block BB.  ALWAYS_REACHED is true if the
1183    basic block is always executed.  ALWAYS_EXECUTED is true if the basic
1184    block is always executed, unless the program ends due to a function
1185    call.  */
1186 
1187 static void
find_invariants_bb(basic_block bb,bool always_reached,bool always_executed)1188 find_invariants_bb (basic_block bb, bool always_reached, bool always_executed)
1189 {
1190   rtx_insn *insn;
1191 
1192   FOR_BB_INSNS (bb, insn)
1193     {
1194       if (!NONDEBUG_INSN_P (insn))
1195 	continue;
1196 
1197       find_invariants_insn (insn, always_reached, always_executed);
1198 
1199       if (always_reached
1200 	  && CALL_P (insn)
1201 	  && (RTL_LOOPING_CONST_OR_PURE_CALL_P (insn)
1202 	      || ! RTL_CONST_OR_PURE_CALL_P (insn)))
1203 	always_reached = false;
1204     }
1205 }
1206 
1207 /* Finds invariants in LOOP with body BODY.  ALWAYS_REACHED is the bitmap of
1208    basic blocks in BODY that are always executed.  ALWAYS_EXECUTED is the
1209    bitmap of basic blocks in BODY that are always executed unless the program
1210    ends due to a function call.  */
1211 
1212 static void
find_invariants_body(struct loop * loop,basic_block * body,bitmap always_reached,bitmap always_executed)1213 find_invariants_body (struct loop *loop, basic_block *body,
1214 		      bitmap always_reached, bitmap always_executed)
1215 {
1216   unsigned i;
1217 
1218   for (i = 0; i < loop->num_nodes; i++)
1219     find_invariants_bb (body[i],
1220 			bitmap_bit_p (always_reached, i),
1221 			bitmap_bit_p (always_executed, i));
1222 }
1223 
1224 /* Finds invariants in LOOP.  */
1225 
1226 static void
find_invariants(struct loop * loop)1227 find_invariants (struct loop *loop)
1228 {
1229   auto_bitmap may_exit;
1230   auto_bitmap always_reached;
1231   auto_bitmap has_exit;
1232   auto_bitmap always_executed;
1233   basic_block *body = get_loop_body_in_dom_order (loop);
1234 
1235   find_exits (loop, body, may_exit, has_exit);
1236   compute_always_reached (loop, body, may_exit, always_reached);
1237   compute_always_reached (loop, body, has_exit, always_executed);
1238 
1239   find_defs (loop);
1240   find_invariants_body (loop, body, always_reached, always_executed);
1241   merge_identical_invariants ();
1242 
1243   free (body);
1244 }
1245 
1246 /* Frees a list of uses USE.  */
1247 
1248 static void
free_use_list(struct use * use)1249 free_use_list (struct use *use)
1250 {
1251   struct use *next;
1252 
1253   for (; use; use = next)
1254     {
1255       next = use->next;
1256       free (use);
1257     }
1258 }
1259 
1260 /* Return pressure class and number of hard registers (through *NREGS)
1261    for destination of INSN. */
1262 static enum reg_class
get_pressure_class_and_nregs(rtx_insn * insn,int * nregs)1263 get_pressure_class_and_nregs (rtx_insn *insn, int *nregs)
1264 {
1265   rtx reg;
1266   enum reg_class pressure_class;
1267   rtx set = single_set (insn);
1268 
1269   /* Considered invariant insns have only one set.  */
1270   gcc_assert (set != NULL_RTX);
1271   reg = SET_DEST (set);
1272   if (GET_CODE (reg) == SUBREG)
1273     reg = SUBREG_REG (reg);
1274   if (MEM_P (reg))
1275     {
1276       *nregs = 0;
1277       pressure_class = NO_REGS;
1278     }
1279   else
1280     {
1281       if (! REG_P (reg))
1282 	reg = NULL_RTX;
1283       if (reg == NULL_RTX)
1284 	pressure_class = GENERAL_REGS;
1285       else
1286 	{
1287 	  pressure_class = reg_allocno_class (REGNO (reg));
1288 	  pressure_class = ira_pressure_class_translate[pressure_class];
1289 	}
1290       *nregs
1291 	= ira_reg_class_max_nregs[pressure_class][GET_MODE (SET_SRC (set))];
1292     }
1293   return pressure_class;
1294 }
1295 
1296 /* Calculates cost and number of registers needed for moving invariant INV
1297    out of the loop and stores them to *COST and *REGS_NEEDED.  *CL will be
1298    the REG_CLASS of INV.  Return
1299      -1: if INV is invalid.
1300       0: if INV and its depends_on have same reg_class
1301       1: if INV and its depends_on have different reg_classes.  */
1302 
1303 static int
get_inv_cost(struct invariant * inv,int * comp_cost,unsigned * regs_needed,enum reg_class * cl)1304 get_inv_cost (struct invariant *inv, int *comp_cost, unsigned *regs_needed,
1305 	      enum reg_class *cl)
1306 {
1307   int i, acomp_cost;
1308   unsigned aregs_needed[N_REG_CLASSES];
1309   unsigned depno;
1310   struct invariant *dep;
1311   bitmap_iterator bi;
1312   int ret = 1;
1313 
1314   /* Find the representative of the class of the equivalent invariants.  */
1315   inv = invariants[inv->eqto];
1316 
1317   *comp_cost = 0;
1318   if (! flag_ira_loop_pressure)
1319     regs_needed[0] = 0;
1320   else
1321     {
1322       for (i = 0; i < ira_pressure_classes_num; i++)
1323 	regs_needed[ira_pressure_classes[i]] = 0;
1324     }
1325 
1326   if (inv->move
1327       || inv->stamp == actual_stamp)
1328     return -1;
1329   inv->stamp = actual_stamp;
1330 
1331   if (! flag_ira_loop_pressure)
1332     regs_needed[0]++;
1333   else
1334     {
1335       int nregs;
1336       enum reg_class pressure_class;
1337 
1338       pressure_class = get_pressure_class_and_nregs (inv->insn, &nregs);
1339       regs_needed[pressure_class] += nregs;
1340       *cl = pressure_class;
1341       ret = 0;
1342     }
1343 
1344   if (!inv->cheap_address
1345       || inv->def->n_uses == 0
1346       || inv->def->n_addr_uses < inv->def->n_uses
1347       /* Count cost if the inv can't be propagated into address uses.  */
1348       || !inv->def->can_prop_to_addr_uses)
1349     (*comp_cost) += inv->cost * inv->eqno;
1350 
1351 #ifdef STACK_REGS
1352   {
1353     /* Hoisting constant pool constants into stack regs may cost more than
1354        just single register.  On x87, the balance is affected both by the
1355        small number of FP registers, and by its register stack organization,
1356        that forces us to add compensation code in and around the loop to
1357        shuffle the operands to the top of stack before use, and pop them
1358        from the stack after the loop finishes.
1359 
1360        To model this effect, we increase the number of registers needed for
1361        stack registers by two: one register push, and one register pop.
1362        This usually has the effect that FP constant loads from the constant
1363        pool are not moved out of the loop.
1364 
1365        Note that this also means that dependent invariants can not be moved.
1366        However, the primary purpose of this pass is to move loop invariant
1367        address arithmetic out of loops, and address arithmetic that depends
1368        on floating point constants is unlikely to ever occur.  */
1369     rtx set = single_set (inv->insn);
1370     if (set
1371 	&& IS_STACK_MODE (GET_MODE (SET_SRC (set)))
1372 	&& constant_pool_constant_p (SET_SRC (set)))
1373       {
1374 	if (flag_ira_loop_pressure)
1375 	  regs_needed[ira_stack_reg_pressure_class] += 2;
1376 	else
1377 	  regs_needed[0] += 2;
1378       }
1379   }
1380 #endif
1381 
1382   EXECUTE_IF_SET_IN_BITMAP (inv->depends_on, 0, depno, bi)
1383     {
1384       bool check_p;
1385       enum reg_class dep_cl = ALL_REGS;
1386       int dep_ret;
1387 
1388       dep = invariants[depno];
1389 
1390       /* If DEP is moved out of the loop, it is not a depends_on any more.  */
1391       if (dep->move)
1392 	continue;
1393 
1394       dep_ret = get_inv_cost (dep, &acomp_cost, aregs_needed, &dep_cl);
1395 
1396       if (! flag_ira_loop_pressure)
1397 	check_p = aregs_needed[0] != 0;
1398       else
1399 	{
1400 	  for (i = 0; i < ira_pressure_classes_num; i++)
1401 	    if (aregs_needed[ira_pressure_classes[i]] != 0)
1402 	      break;
1403 	  check_p = i < ira_pressure_classes_num;
1404 
1405 	  if ((dep_ret == 1) || ((dep_ret == 0) && (*cl != dep_cl)))
1406 	    {
1407 	      *cl = ALL_REGS;
1408 	      ret = 1;
1409 	    }
1410 	}
1411       if (check_p
1412 	  /* We need to check always_executed, since if the original value of
1413 	     the invariant may be preserved, we may need to keep it in a
1414 	     separate register.  TODO check whether the register has an
1415 	     use outside of the loop.  */
1416 	  && dep->always_executed
1417 	  && !dep->def->uses->next)
1418 	{
1419 	  /* If this is a single use, after moving the dependency we will not
1420 	     need a new register.  */
1421 	  if (! flag_ira_loop_pressure)
1422 	    aregs_needed[0]--;
1423 	  else
1424 	    {
1425 	      int nregs;
1426 	      enum reg_class pressure_class;
1427 
1428 	      pressure_class = get_pressure_class_and_nregs (inv->insn, &nregs);
1429 	      aregs_needed[pressure_class] -= nregs;
1430 	    }
1431 	}
1432 
1433       if (! flag_ira_loop_pressure)
1434 	regs_needed[0] += aregs_needed[0];
1435       else
1436 	{
1437 	  for (i = 0; i < ira_pressure_classes_num; i++)
1438 	    regs_needed[ira_pressure_classes[i]]
1439 	      += aregs_needed[ira_pressure_classes[i]];
1440 	}
1441       (*comp_cost) += acomp_cost;
1442     }
1443   return ret;
1444 }
1445 
1446 /* Calculates gain for eliminating invariant INV.  REGS_USED is the number
1447    of registers used in the loop, NEW_REGS is the number of new variables
1448    already added due to the invariant motion.  The number of registers needed
1449    for it is stored in *REGS_NEEDED.  SPEED and CALL_P are flags passed
1450    through to estimate_reg_pressure_cost. */
1451 
1452 static int
gain_for_invariant(struct invariant * inv,unsigned * regs_needed,unsigned * new_regs,unsigned regs_used,bool speed,bool call_p)1453 gain_for_invariant (struct invariant *inv, unsigned *regs_needed,
1454 		    unsigned *new_regs, unsigned regs_used,
1455 		    bool speed, bool call_p)
1456 {
1457   int comp_cost, size_cost;
1458   /* Workaround -Wmaybe-uninitialized false positive during
1459      profiledbootstrap by initializing it.  */
1460   enum reg_class cl = NO_REGS;
1461   int ret;
1462 
1463   actual_stamp++;
1464 
1465   ret = get_inv_cost (inv, &comp_cost, regs_needed, &cl);
1466 
1467   if (! flag_ira_loop_pressure)
1468     {
1469       size_cost = (estimate_reg_pressure_cost (new_regs[0] + regs_needed[0],
1470 					       regs_used, speed, call_p)
1471 		   - estimate_reg_pressure_cost (new_regs[0],
1472 						 regs_used, speed, call_p));
1473     }
1474   else if (ret < 0)
1475     return -1;
1476   else if ((ret == 0) && (cl == NO_REGS))
1477     /* Hoist it anyway since it does not impact register pressure.  */
1478     return 1;
1479   else
1480     {
1481       int i;
1482       enum reg_class pressure_class;
1483 
1484       for (i = 0; i < ira_pressure_classes_num; i++)
1485 	{
1486 	  pressure_class = ira_pressure_classes[i];
1487 
1488 	  if (!reg_classes_intersect_p (pressure_class, cl))
1489 	    continue;
1490 
1491 	  if ((int) new_regs[pressure_class]
1492 	      + (int) regs_needed[pressure_class]
1493 	      + LOOP_DATA (curr_loop)->max_reg_pressure[pressure_class]
1494 	      + IRA_LOOP_RESERVED_REGS
1495 	      > ira_class_hard_regs_num[pressure_class])
1496 	    break;
1497 	}
1498       if (i < ira_pressure_classes_num)
1499 	/* There will be register pressure excess and we want not to
1500 	   make this loop invariant motion.  All loop invariants with
1501 	   non-positive gains will be rejected in function
1502 	   find_invariants_to_move.  Therefore we return the negative
1503 	   number here.
1504 
1505 	   One could think that this rejects also expensive loop
1506 	   invariant motions and this will hurt code performance.
1507 	   However numerous experiments with different heuristics
1508 	   taking invariant cost into account did not confirm this
1509 	   assumption.  There are possible explanations for this
1510 	   result:
1511            o probably all expensive invariants were already moved out
1512              of the loop by PRE and gimple invariant motion pass.
1513            o expensive invariant execution will be hidden by insn
1514              scheduling or OOO processor hardware because usually such
1515              invariants have a lot of freedom to be executed
1516              out-of-order.
1517 	   Another reason for ignoring invariant cost vs spilling cost
1518 	   heuristics is also in difficulties to evaluate accurately
1519 	   spill cost at this stage.  */
1520 	return -1;
1521       else
1522 	size_cost = 0;
1523     }
1524 
1525   return comp_cost - size_cost;
1526 }
1527 
1528 /* Finds invariant with best gain for moving.  Returns the gain, stores
1529    the invariant in *BEST and number of registers needed for it to
1530    *REGS_NEEDED.  REGS_USED is the number of registers used in the loop.
1531    NEW_REGS is the number of new variables already added due to invariant
1532    motion.  */
1533 
1534 static int
best_gain_for_invariant(struct invariant ** best,unsigned * regs_needed,unsigned * new_regs,unsigned regs_used,bool speed,bool call_p)1535 best_gain_for_invariant (struct invariant **best, unsigned *regs_needed,
1536 			 unsigned *new_regs, unsigned regs_used,
1537 			 bool speed, bool call_p)
1538 {
1539   struct invariant *inv;
1540   int i, gain = 0, again;
1541   unsigned aregs_needed[N_REG_CLASSES], invno;
1542 
1543   FOR_EACH_VEC_ELT (invariants, invno, inv)
1544     {
1545       if (inv->move)
1546 	continue;
1547 
1548       /* Only consider the "representatives" of equivalent invariants.  */
1549       if (inv->eqto != inv->invno)
1550 	continue;
1551 
1552       again = gain_for_invariant (inv, aregs_needed, new_regs, regs_used,
1553       				  speed, call_p);
1554       if (again > gain)
1555 	{
1556 	  gain = again;
1557 	  *best = inv;
1558 	  if (! flag_ira_loop_pressure)
1559 	    regs_needed[0] = aregs_needed[0];
1560 	  else
1561 	    {
1562 	      for (i = 0; i < ira_pressure_classes_num; i++)
1563 		regs_needed[ira_pressure_classes[i]]
1564 		  = aregs_needed[ira_pressure_classes[i]];
1565 	    }
1566 	}
1567     }
1568 
1569   return gain;
1570 }
1571 
1572 /* Marks invariant INVNO and all its dependencies for moving.  */
1573 
1574 static void
set_move_mark(unsigned invno,int gain)1575 set_move_mark (unsigned invno, int gain)
1576 {
1577   struct invariant *inv = invariants[invno];
1578   bitmap_iterator bi;
1579 
1580   /* Find the representative of the class of the equivalent invariants.  */
1581   inv = invariants[inv->eqto];
1582 
1583   if (inv->move)
1584     return;
1585   inv->move = true;
1586 
1587   if (dump_file)
1588     {
1589       if (gain >= 0)
1590 	fprintf (dump_file, "Decided to move invariant %d -- gain %d\n",
1591 		 invno, gain);
1592       else
1593 	fprintf (dump_file, "Decided to move dependent invariant %d\n",
1594 		 invno);
1595     };
1596 
1597   EXECUTE_IF_SET_IN_BITMAP (inv->depends_on, 0, invno, bi)
1598     {
1599       set_move_mark (invno, -1);
1600     }
1601 }
1602 
1603 /* Determines which invariants to move.  */
1604 
1605 static void
find_invariants_to_move(bool speed,bool call_p)1606 find_invariants_to_move (bool speed, bool call_p)
1607 {
1608   int gain;
1609   unsigned i, regs_used, regs_needed[N_REG_CLASSES], new_regs[N_REG_CLASSES];
1610   struct invariant *inv = NULL;
1611 
1612   if (!invariants.length ())
1613     return;
1614 
1615   if (flag_ira_loop_pressure)
1616     /* REGS_USED is actually never used when the flag is on.  */
1617     regs_used = 0;
1618   else
1619     /* We do not really do a good job in estimating number of
1620        registers used; we put some initial bound here to stand for
1621        induction variables etc.  that we do not detect.  */
1622     {
1623       unsigned int n_regs = DF_REG_SIZE (df);
1624 
1625       regs_used = 2;
1626 
1627       for (i = 0; i < n_regs; i++)
1628 	{
1629 	  if (!DF_REGNO_FIRST_DEF (i) && DF_REGNO_LAST_USE (i))
1630 	    {
1631 	      /* This is a value that is used but not changed inside loop.  */
1632 	      regs_used++;
1633 	    }
1634 	}
1635     }
1636 
1637   if (! flag_ira_loop_pressure)
1638     new_regs[0] = regs_needed[0] = 0;
1639   else
1640     {
1641       for (i = 0; (int) i < ira_pressure_classes_num; i++)
1642 	new_regs[ira_pressure_classes[i]] = 0;
1643     }
1644   while ((gain = best_gain_for_invariant (&inv, regs_needed,
1645 					  new_regs, regs_used,
1646 					  speed, call_p)) > 0)
1647     {
1648       set_move_mark (inv->invno, gain);
1649       if (! flag_ira_loop_pressure)
1650 	new_regs[0] += regs_needed[0];
1651       else
1652 	{
1653 	  for (i = 0; (int) i < ira_pressure_classes_num; i++)
1654 	    new_regs[ira_pressure_classes[i]]
1655 	      += regs_needed[ira_pressure_classes[i]];
1656 	}
1657     }
1658 }
1659 
1660 /* Replace the uses, reached by the definition of invariant INV, by REG.
1661 
1662    IN_GROUP is nonzero if this is part of a group of changes that must be
1663    performed as a group.  In that case, the changes will be stored.  The
1664    function `apply_change_group' will validate and apply the changes.  */
1665 
1666 static int
replace_uses(struct invariant * inv,rtx reg,bool in_group)1667 replace_uses (struct invariant *inv, rtx reg, bool in_group)
1668 {
1669   /* Replace the uses we know to be dominated.  It saves work for copy
1670      propagation, and also it is necessary so that dependent invariants
1671      are computed right.  */
1672   if (inv->def)
1673     {
1674       struct use *use;
1675       for (use = inv->def->uses; use; use = use->next)
1676 	validate_change (use->insn, use->pos, reg, true);
1677 
1678       /* If we aren't part of a larger group, apply the changes now.  */
1679       if (!in_group)
1680 	return apply_change_group ();
1681     }
1682 
1683   return 1;
1684 }
1685 
1686 /* Whether invariant INV setting REG can be moved out of LOOP, at the end of
1687    the block preceding its header.  */
1688 
1689 static bool
can_move_invariant_reg(struct loop * loop,struct invariant * inv,rtx reg)1690 can_move_invariant_reg (struct loop *loop, struct invariant *inv, rtx reg)
1691 {
1692   df_ref def, use;
1693   unsigned int dest_regno, defs_in_loop_count = 0;
1694   rtx_insn *insn = inv->insn;
1695   basic_block bb = BLOCK_FOR_INSN (inv->insn);
1696 
1697   /* We ignore hard register and memory access for cost and complexity reasons.
1698      Hard register are few at this stage and expensive to consider as they
1699      require building a separate data flow.  Memory access would require using
1700      df_simulate_* and can_move_insns_across functions and is more complex.  */
1701   if (!REG_P (reg) || HARD_REGISTER_P (reg))
1702     return false;
1703 
1704   /* Check whether the set is always executed.  We could omit this condition if
1705      we know that the register is unused outside of the loop, but it does not
1706      seem worth finding out.  */
1707   if (!inv->always_executed)
1708     return false;
1709 
1710   /* Check that all uses that would be dominated by def are already dominated
1711      by it.  */
1712   dest_regno = REGNO (reg);
1713   for (use = DF_REG_USE_CHAIN (dest_regno); use; use = DF_REF_NEXT_REG (use))
1714     {
1715       rtx_insn *use_insn;
1716       basic_block use_bb;
1717 
1718       use_insn = DF_REF_INSN (use);
1719       use_bb = BLOCK_FOR_INSN (use_insn);
1720 
1721       /* Ignore instruction considered for moving.  */
1722       if (use_insn == insn)
1723 	continue;
1724 
1725       /* Don't consider uses outside loop.  */
1726       if (!flow_bb_inside_loop_p (loop, use_bb))
1727 	continue;
1728 
1729       /* Don't move if a use is not dominated by def in insn.  */
1730       if (use_bb == bb && DF_INSN_LUID (insn) >= DF_INSN_LUID (use_insn))
1731 	return false;
1732       if (!dominated_by_p (CDI_DOMINATORS, use_bb, bb))
1733 	return false;
1734     }
1735 
1736   /* Check for other defs.  Any other def in the loop might reach a use
1737      currently reached by the def in insn.  */
1738   for (def = DF_REG_DEF_CHAIN (dest_regno); def; def = DF_REF_NEXT_REG (def))
1739     {
1740       basic_block def_bb = DF_REF_BB (def);
1741 
1742       /* Defs in exit block cannot reach a use they weren't already.  */
1743       if (single_succ_p (def_bb))
1744 	{
1745 	  basic_block def_bb_succ;
1746 
1747 	  def_bb_succ = single_succ (def_bb);
1748 	  if (!flow_bb_inside_loop_p (loop, def_bb_succ))
1749 	    continue;
1750 	}
1751 
1752       if (++defs_in_loop_count > 1)
1753 	return false;
1754     }
1755 
1756   return true;
1757 }
1758 
1759 /* Move invariant INVNO out of the LOOP.  Returns true if this succeeds, false
1760    otherwise.  */
1761 
1762 static bool
move_invariant_reg(struct loop * loop,unsigned invno)1763 move_invariant_reg (struct loop *loop, unsigned invno)
1764 {
1765   struct invariant *inv = invariants[invno];
1766   struct invariant *repr = invariants[inv->eqto];
1767   unsigned i;
1768   basic_block preheader = loop_preheader_edge (loop)->src;
1769   rtx reg, set, dest, note;
1770   bitmap_iterator bi;
1771   int regno = -1;
1772 
1773   if (inv->reg)
1774     return true;
1775   if (!repr->move)
1776     return false;
1777 
1778   /* If this is a representative of the class of equivalent invariants,
1779      really move the invariant.  Otherwise just replace its use with
1780      the register used for the representative.  */
1781   if (inv == repr)
1782     {
1783       if (inv->depends_on)
1784 	{
1785 	  EXECUTE_IF_SET_IN_BITMAP (inv->depends_on, 0, i, bi)
1786 	    {
1787 	      if (!move_invariant_reg (loop, i))
1788 		goto fail;
1789 	    }
1790 	}
1791 
1792       /* If possible, just move the set out of the loop.  Otherwise, we
1793 	 need to create a temporary register.  */
1794       set = single_set (inv->insn);
1795       reg = dest = SET_DEST (set);
1796       if (GET_CODE (reg) == SUBREG)
1797 	reg = SUBREG_REG (reg);
1798       if (REG_P (reg))
1799 	regno = REGNO (reg);
1800 
1801       if (!can_move_invariant_reg (loop, inv, dest))
1802 	{
1803 	  reg = gen_reg_rtx_and_attrs (dest);
1804 
1805 	  /* Try replacing the destination by a new pseudoregister.  */
1806 	  validate_change (inv->insn, &SET_DEST (set), reg, true);
1807 
1808 	  /* As well as all the dominated uses.  */
1809 	  replace_uses (inv, reg, true);
1810 
1811 	  /* And validate all the changes.  */
1812 	  if (!apply_change_group ())
1813 	    goto fail;
1814 
1815 	  emit_insn_after (gen_move_insn (dest, reg), inv->insn);
1816 	}
1817       else if (dump_file)
1818 	fprintf (dump_file, "Invariant %d moved without introducing a new "
1819 			    "temporary register\n", invno);
1820       reorder_insns (inv->insn, inv->insn, BB_END (preheader));
1821       df_recompute_luids (preheader);
1822 
1823       /* If there is a REG_EQUAL note on the insn we just moved, and the
1824 	 insn is in a basic block that is not always executed or the note
1825 	 contains something for which we don't know the invariant status,
1826 	 the note may no longer be valid after we move the insn.  Note that
1827 	 uses in REG_EQUAL notes are taken into account in the computation
1828 	 of invariants, so it is safe to retain the note even if it contains
1829 	 register references for which we know the invariant status.  */
1830       if ((note = find_reg_note (inv->insn, REG_EQUAL, NULL_RTX))
1831 	  && (!inv->always_executed
1832 	      || !check_maybe_invariant (XEXP (note, 0))))
1833 	remove_note (inv->insn, note);
1834     }
1835   else
1836     {
1837       if (!move_invariant_reg (loop, repr->invno))
1838 	goto fail;
1839       reg = repr->reg;
1840       regno = repr->orig_regno;
1841       if (!replace_uses (inv, reg, false))
1842 	goto fail;
1843       set = single_set (inv->insn);
1844       emit_insn_after (gen_move_insn (SET_DEST (set), reg), inv->insn);
1845       delete_insn (inv->insn);
1846     }
1847 
1848   inv->reg = reg;
1849   inv->orig_regno = regno;
1850 
1851   return true;
1852 
1853 fail:
1854   /* If we failed, clear move flag, so that we do not try to move inv
1855      again.  */
1856   if (dump_file)
1857     fprintf (dump_file, "Failed to move invariant %d\n", invno);
1858   inv->move = false;
1859   inv->reg = NULL_RTX;
1860   inv->orig_regno = -1;
1861 
1862   return false;
1863 }
1864 
1865 /* Move selected invariant out of the LOOP.  Newly created regs are marked
1866    in TEMPORARY_REGS.  */
1867 
1868 static void
move_invariants(struct loop * loop)1869 move_invariants (struct loop *loop)
1870 {
1871   struct invariant *inv;
1872   unsigned i;
1873 
1874   FOR_EACH_VEC_ELT (invariants, i, inv)
1875     move_invariant_reg (loop, i);
1876   if (flag_ira_loop_pressure && resize_reg_info ())
1877     {
1878       FOR_EACH_VEC_ELT (invariants, i, inv)
1879 	if (inv->reg != NULL_RTX)
1880 	  {
1881 	    if (inv->orig_regno >= 0)
1882 	      setup_reg_classes (REGNO (inv->reg),
1883 				 reg_preferred_class (inv->orig_regno),
1884 				 reg_alternate_class (inv->orig_regno),
1885 				 reg_allocno_class (inv->orig_regno));
1886 	    else
1887 	      setup_reg_classes (REGNO (inv->reg),
1888 				 GENERAL_REGS, NO_REGS, GENERAL_REGS);
1889 	  }
1890     }
1891 }
1892 
1893 /* Initializes invariant motion data.  */
1894 
1895 static void
init_inv_motion_data(void)1896 init_inv_motion_data (void)
1897 {
1898   actual_stamp = 1;
1899 
1900   invariants.create (100);
1901 }
1902 
1903 /* Frees the data allocated by invariant motion.  */
1904 
1905 static void
free_inv_motion_data(void)1906 free_inv_motion_data (void)
1907 {
1908   unsigned i;
1909   struct def *def;
1910   struct invariant *inv;
1911 
1912   check_invariant_table_size ();
1913   for (i = 0; i < DF_DEFS_TABLE_SIZE (); i++)
1914     {
1915       inv = invariant_table[i];
1916       if (inv)
1917 	{
1918 	  def = inv->def;
1919 	  gcc_assert (def != NULL);
1920 
1921 	  free_use_list (def->uses);
1922 	  free (def);
1923 	  invariant_table[i] = NULL;
1924 	}
1925     }
1926 
1927   FOR_EACH_VEC_ELT (invariants, i, inv)
1928     {
1929       BITMAP_FREE (inv->depends_on);
1930       free (inv);
1931     }
1932   invariants.release ();
1933 }
1934 
1935 /* Move the invariants out of the LOOP.  */
1936 
1937 static void
move_single_loop_invariants(struct loop * loop)1938 move_single_loop_invariants (struct loop *loop)
1939 {
1940   init_inv_motion_data ();
1941 
1942   find_invariants (loop);
1943   find_invariants_to_move (optimize_loop_for_speed_p (loop),
1944 			   LOOP_DATA (loop)->has_call);
1945   move_invariants (loop);
1946 
1947   free_inv_motion_data ();
1948 }
1949 
1950 /* Releases the auxiliary data for LOOP.  */
1951 
1952 static void
free_loop_data(struct loop * loop)1953 free_loop_data (struct loop *loop)
1954 {
1955   struct loop_data *data = LOOP_DATA (loop);
1956   if (!data)
1957     return;
1958 
1959   bitmap_clear (&LOOP_DATA (loop)->regs_ref);
1960   bitmap_clear (&LOOP_DATA (loop)->regs_live);
1961   free (data);
1962   loop->aux = NULL;
1963 }
1964 
1965 
1966 
1967 /* Registers currently living.  */
1968 static bitmap_head curr_regs_live;
1969 
1970 /* Current reg pressure for each pressure class.  */
1971 static int curr_reg_pressure[N_REG_CLASSES];
1972 
1973 /* Record all regs that are set in any one insn.  Communication from
1974    mark_reg_{store,clobber} and global_conflicts.  Asm can refer to
1975    all hard-registers.  */
1976 static rtx regs_set[(FIRST_PSEUDO_REGISTER > MAX_RECOG_OPERANDS
1977 		     ? FIRST_PSEUDO_REGISTER : MAX_RECOG_OPERANDS) * 2];
1978 /* Number of regs stored in the previous array.  */
1979 static int n_regs_set;
1980 
1981 /* Return pressure class and number of needed hard registers (through
1982    *NREGS) of register REGNO.  */
1983 static enum reg_class
get_regno_pressure_class(int regno,int * nregs)1984 get_regno_pressure_class (int regno, int *nregs)
1985 {
1986   if (regno >= FIRST_PSEUDO_REGISTER)
1987     {
1988       enum reg_class pressure_class;
1989 
1990       pressure_class = reg_allocno_class (regno);
1991       pressure_class = ira_pressure_class_translate[pressure_class];
1992       *nregs
1993 	= ira_reg_class_max_nregs[pressure_class][PSEUDO_REGNO_MODE (regno)];
1994       return pressure_class;
1995     }
1996   else if (! TEST_HARD_REG_BIT (ira_no_alloc_regs, regno)
1997 	   && ! TEST_HARD_REG_BIT (eliminable_regset, regno))
1998     {
1999       *nregs = 1;
2000       return ira_pressure_class_translate[REGNO_REG_CLASS (regno)];
2001     }
2002   else
2003     {
2004       *nregs = 0;
2005       return NO_REGS;
2006     }
2007 }
2008 
2009 /* Increase (if INCR_P) or decrease current register pressure for
2010    register REGNO.  */
2011 static void
change_pressure(int regno,bool incr_p)2012 change_pressure (int regno, bool incr_p)
2013 {
2014   int nregs;
2015   enum reg_class pressure_class;
2016 
2017   pressure_class = get_regno_pressure_class (regno, &nregs);
2018   if (! incr_p)
2019     curr_reg_pressure[pressure_class] -= nregs;
2020   else
2021     {
2022       curr_reg_pressure[pressure_class] += nregs;
2023       if (LOOP_DATA (curr_loop)->max_reg_pressure[pressure_class]
2024 	  < curr_reg_pressure[pressure_class])
2025 	LOOP_DATA (curr_loop)->max_reg_pressure[pressure_class]
2026 	  = curr_reg_pressure[pressure_class];
2027     }
2028 }
2029 
2030 /* Mark REGNO birth.  */
2031 static void
mark_regno_live(int regno)2032 mark_regno_live (int regno)
2033 {
2034   struct loop *loop;
2035 
2036   for (loop = curr_loop;
2037        loop != current_loops->tree_root;
2038        loop = loop_outer (loop))
2039     bitmap_set_bit (&LOOP_DATA (loop)->regs_live, regno);
2040   if (!bitmap_set_bit (&curr_regs_live, regno))
2041     return;
2042   change_pressure (regno, true);
2043 }
2044 
2045 /* Mark REGNO death.  */
2046 static void
mark_regno_death(int regno)2047 mark_regno_death (int regno)
2048 {
2049   if (! bitmap_clear_bit (&curr_regs_live, regno))
2050     return;
2051   change_pressure (regno, false);
2052 }
2053 
2054 /* Mark setting register REG.  */
2055 static void
mark_reg_store(rtx reg,const_rtx setter ATTRIBUTE_UNUSED,void * data ATTRIBUTE_UNUSED)2056 mark_reg_store (rtx reg, const_rtx setter ATTRIBUTE_UNUSED,
2057 		void *data ATTRIBUTE_UNUSED)
2058 {
2059   if (GET_CODE (reg) == SUBREG)
2060     reg = SUBREG_REG (reg);
2061 
2062   if (! REG_P (reg))
2063     return;
2064 
2065   regs_set[n_regs_set++] = reg;
2066 
2067   unsigned int end_regno = END_REGNO (reg);
2068   for (unsigned int regno = REGNO (reg); regno < end_regno; ++regno)
2069     mark_regno_live (regno);
2070 }
2071 
2072 /* Mark clobbering register REG.  */
2073 static void
mark_reg_clobber(rtx reg,const_rtx setter,void * data)2074 mark_reg_clobber (rtx reg, const_rtx setter, void *data)
2075 {
2076   if (GET_CODE (setter) == CLOBBER)
2077     mark_reg_store (reg, setter, data);
2078 }
2079 
2080 /* Mark register REG death.  */
2081 static void
mark_reg_death(rtx reg)2082 mark_reg_death (rtx reg)
2083 {
2084   unsigned int end_regno = END_REGNO (reg);
2085   for (unsigned int regno = REGNO (reg); regno < end_regno; ++regno)
2086     mark_regno_death (regno);
2087 }
2088 
2089 /* Mark occurrence of registers in X for the current loop.  */
2090 static void
mark_ref_regs(rtx x)2091 mark_ref_regs (rtx x)
2092 {
2093   RTX_CODE code;
2094   int i;
2095   const char *fmt;
2096 
2097   if (!x)
2098     return;
2099 
2100   code = GET_CODE (x);
2101   if (code == REG)
2102     {
2103       struct loop *loop;
2104 
2105       for (loop = curr_loop;
2106 	   loop != current_loops->tree_root;
2107 	   loop = loop_outer (loop))
2108 	bitmap_set_bit (&LOOP_DATA (loop)->regs_ref, REGNO (x));
2109       return;
2110     }
2111 
2112   fmt = GET_RTX_FORMAT (code);
2113   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2114     if (fmt[i] == 'e')
2115       mark_ref_regs (XEXP (x, i));
2116     else if (fmt[i] == 'E')
2117       {
2118 	int j;
2119 
2120 	for (j = 0; j < XVECLEN (x, i); j++)
2121 	  mark_ref_regs (XVECEXP (x, i, j));
2122       }
2123 }
2124 
2125 /* Calculate register pressure in the loops.  */
2126 static void
calculate_loop_reg_pressure(void)2127 calculate_loop_reg_pressure (void)
2128 {
2129   int i;
2130   unsigned int j;
2131   bitmap_iterator bi;
2132   basic_block bb;
2133   rtx_insn *insn;
2134   rtx link;
2135   struct loop *loop, *parent;
2136 
2137   FOR_EACH_LOOP (loop, 0)
2138     if (loop->aux == NULL)
2139       {
2140 	loop->aux = xcalloc (1, sizeof (struct loop_data));
2141 	bitmap_initialize (&LOOP_DATA (loop)->regs_ref, &reg_obstack);
2142 	bitmap_initialize (&LOOP_DATA (loop)->regs_live, &reg_obstack);
2143       }
2144   ira_setup_eliminable_regset ();
2145   bitmap_initialize (&curr_regs_live, &reg_obstack);
2146   FOR_EACH_BB_FN (bb, cfun)
2147     {
2148       curr_loop = bb->loop_father;
2149       if (curr_loop == current_loops->tree_root)
2150 	continue;
2151 
2152       for (loop = curr_loop;
2153 	   loop != current_loops->tree_root;
2154 	   loop = loop_outer (loop))
2155 	bitmap_ior_into (&LOOP_DATA (loop)->regs_live, DF_LR_IN (bb));
2156 
2157       bitmap_copy (&curr_regs_live, DF_LR_IN (bb));
2158       for (i = 0; i < ira_pressure_classes_num; i++)
2159 	curr_reg_pressure[ira_pressure_classes[i]] = 0;
2160       EXECUTE_IF_SET_IN_BITMAP (&curr_regs_live, 0, j, bi)
2161 	change_pressure (j, true);
2162 
2163       FOR_BB_INSNS (bb, insn)
2164 	{
2165 	  if (! NONDEBUG_INSN_P (insn))
2166 	    continue;
2167 
2168 	  mark_ref_regs (PATTERN (insn));
2169 	  n_regs_set = 0;
2170 	  note_stores (PATTERN (insn), mark_reg_clobber, NULL);
2171 
2172 	  /* Mark any registers dead after INSN as dead now.  */
2173 
2174 	  for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
2175 	    if (REG_NOTE_KIND (link) == REG_DEAD)
2176 	      mark_reg_death (XEXP (link, 0));
2177 
2178 	  /* Mark any registers set in INSN as live,
2179 	     and mark them as conflicting with all other live regs.
2180 	     Clobbers are processed again, so they conflict with
2181 	     the registers that are set.  */
2182 
2183 	  note_stores (PATTERN (insn), mark_reg_store, NULL);
2184 
2185 	  if (AUTO_INC_DEC)
2186 	    for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
2187 	      if (REG_NOTE_KIND (link) == REG_INC)
2188 		mark_reg_store (XEXP (link, 0), NULL_RTX, NULL);
2189 
2190 	  while (n_regs_set-- > 0)
2191 	    {
2192 	      rtx note = find_regno_note (insn, REG_UNUSED,
2193 					  REGNO (regs_set[n_regs_set]));
2194 	      if (! note)
2195 		continue;
2196 
2197 	      mark_reg_death (XEXP (note, 0));
2198 	    }
2199 	}
2200     }
2201   bitmap_clear (&curr_regs_live);
2202   if (flag_ira_region == IRA_REGION_MIXED
2203       || flag_ira_region == IRA_REGION_ALL)
2204     FOR_EACH_LOOP (loop, 0)
2205       {
2206 	EXECUTE_IF_SET_IN_BITMAP (&LOOP_DATA (loop)->regs_live, 0, j, bi)
2207 	  if (! bitmap_bit_p (&LOOP_DATA (loop)->regs_ref, j))
2208 	    {
2209 	      enum reg_class pressure_class;
2210 	      int nregs;
2211 
2212 	      pressure_class = get_regno_pressure_class (j, &nregs);
2213 	      LOOP_DATA (loop)->max_reg_pressure[pressure_class] -= nregs;
2214 	    }
2215       }
2216   if (dump_file == NULL)
2217     return;
2218   FOR_EACH_LOOP (loop, 0)
2219     {
2220       parent = loop_outer (loop);
2221       fprintf (dump_file, "\n  Loop %d (parent %d, header bb%d, depth %d)\n",
2222 	       loop->num, (parent == NULL ? -1 : parent->num),
2223 	       loop->header->index, loop_depth (loop));
2224       fprintf (dump_file, "\n    ref. regnos:");
2225       EXECUTE_IF_SET_IN_BITMAP (&LOOP_DATA (loop)->regs_ref, 0, j, bi)
2226 	fprintf (dump_file, " %d", j);
2227       fprintf (dump_file, "\n    live regnos:");
2228       EXECUTE_IF_SET_IN_BITMAP (&LOOP_DATA (loop)->regs_live, 0, j, bi)
2229 	fprintf (dump_file, " %d", j);
2230       fprintf (dump_file, "\n    Pressure:");
2231       for (i = 0; (int) i < ira_pressure_classes_num; i++)
2232 	{
2233 	  enum reg_class pressure_class;
2234 
2235 	  pressure_class = ira_pressure_classes[i];
2236 	  if (LOOP_DATA (loop)->max_reg_pressure[pressure_class] == 0)
2237 	    continue;
2238 	  fprintf (dump_file, " %s=%d", reg_class_names[pressure_class],
2239 		   LOOP_DATA (loop)->max_reg_pressure[pressure_class]);
2240 	}
2241       fprintf (dump_file, "\n");
2242     }
2243 }
2244 
2245 
2246 
2247 /* Move the invariants out of the loops.  */
2248 
2249 void
move_loop_invariants(void)2250 move_loop_invariants (void)
2251 {
2252   struct loop *loop;
2253 
2254   if (flag_ira_loop_pressure)
2255     {
2256       df_analyze ();
2257       regstat_init_n_sets_and_refs ();
2258       ira_set_pseudo_classes (true, dump_file);
2259       calculate_loop_reg_pressure ();
2260       regstat_free_n_sets_and_refs ();
2261     }
2262   df_set_flags (DF_EQ_NOTES + DF_DEFER_INSN_RESCAN);
2263   /* Process the loops, innermost first.  */
2264   FOR_EACH_LOOP (loop, LI_FROM_INNERMOST)
2265     {
2266       curr_loop = loop;
2267       /* move_single_loop_invariants for very large loops
2268 	 is time consuming and might need a lot of memory.  */
2269       if (loop->num_nodes <= (unsigned) LOOP_INVARIANT_MAX_BBS_IN_LOOP)
2270 	move_single_loop_invariants (loop);
2271     }
2272 
2273   FOR_EACH_LOOP (loop, 0)
2274     {
2275       free_loop_data (loop);
2276     }
2277 
2278   if (flag_ira_loop_pressure)
2279     /* There is no sense to keep this info because it was most
2280        probably outdated by subsequent passes.  */
2281     free_reg_info ();
2282   free (invariant_table);
2283   invariant_table = NULL;
2284   invariant_table_size = 0;
2285 
2286   checking_verify_flow_info ();
2287 }
2288