OSDN Git Service

91ce890755fd619970e57cdbffbae07b85d715ec
[pf3gnuchains/gcc-fork.git] / gcc / tree-parloops.c
1 /* Loop autoparallelization.
2    Copyright (C) 2006, 2007, 2008 Free Software Foundation, Inc.
3    Contributed by Sebastian Pop <pop@cri.ensmp.fr> and
4    Zdenek Dvorak <dvorakz@suse.cz>.
5
6 This file is part of GCC.
7
8 GCC is free software; you can redistribute it and/or modify it under
9 the terms of the GNU General Public License as published by the Free
10 Software Foundation; either version 2, or (at your option) any later
11 version.
12
13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
16 for more details.
17
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING.  If not, write to the Free
20 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
21 02110-1301, USA.  */
22
23 #include "config.h"
24 #include "system.h"
25 #include "coretypes.h"
26 #include "tm.h"
27 #include "tree.h"
28 #include "rtl.h"
29 #include "tree-flow.h"
30 #include "cfgloop.h"
31 #include "ggc.h"
32 #include "tree-data-ref.h"
33 #include "diagnostic.h"
34 #include "tree-pass.h"
35 #include "tree-scalar-evolution.h"
36 #include "hashtab.h"
37 #include "langhooks.h"
38 #include "tree-vectorizer.h"
39
40 /* This pass tries to distribute iterations of loops into several threads.
41    The implementation is straightforward -- for each loop we test whether its
42    iterations are independent, and if it is the case (and some additional
43    conditions regarding profitability and correctness are satisfied), we
44    add GIMPLE_OMP_PARALLEL and GIMPLE_OMP_FOR codes and let omp expansion
45    machinery do its job.
46    
47    The most of the complexity is in bringing the code into shape expected
48    by the omp expanders:
49    -- for GIMPLE_OMP_FOR, ensuring that the loop has only one induction
50       variable and that the exit test is at the start of the loop body
51    -- for GIMPLE_OMP_PARALLEL, replacing the references to local addressable
52       variables by accesses through pointers, and breaking up ssa chains
53       by storing the values incoming to the parallelized loop to a structure
54       passed to the new function as an argument (something similar is done
55       in omp gimplification, unfortunately only a small part of the code
56       can be shared).
57
58    TODO:
59    -- if there are several parallelizable loops in a function, it may be
60       possible to generate the threads just once (using synchronization to
61       ensure that cross-loop dependences are obeyed).
62    -- handling of common scalar dependence patterns (accumulation, ...)
63    -- handling of non-innermost loops  */
64
65 /*  
66   Reduction handling:
67   currently we use vect_is_simple_reduction() to detect reduction patterns.
68   The code transformation will be introduced by an example.
69   
70     
71 parloop
72 {
73   int sum=1;
74
75   for (i = 0; i < N; i++)
76    {
77     x[i] = i + 3;
78     sum+=x[i];
79    }
80 }
81
82 gimple-like code:
83 header_bb:
84
85   # sum_29 = PHI <sum_11(5), 1(3)>
86   # i_28 = PHI <i_12(5), 0(3)>
87   D.1795_8 = i_28 + 3;
88   x[i_28] = D.1795_8;
89   sum_11 = D.1795_8 + sum_29;
90   i_12 = i_28 + 1;
91   if (N_6(D) > i_12)
92     goto header_bb;
93
94
95 exit_bb:
96
97   # sum_21 = PHI <sum_11(4)>
98   printf (&"%d"[0], sum_21);
99
100
101 after reduction transformation (only relevant parts):
102
103 parloop
104 {
105
106 ....
107
108
109   # Storing the initial value given by the user.  #
110
111   .paral_data_store.32.sum.27 = 1;
112  
113   #pragma omp parallel num_threads(4) 
114
115   #pragma omp for schedule(static)
116
117   # The neutral element corresponding to the particular
118   reduction's operation, e.g. 0 for PLUS_EXPR,
119   1 for MULT_EXPR, etc. replaces the user's initial value.  #
120
121   # sum.27_29 = PHI <sum.27_11, 0>
122
123   sum.27_11 = D.1827_8 + sum.27_29;
124
125   GIMPLE_OMP_CONTINUE
126
127   # Adding this reduction phi is done at create_phi_for_local_result() #
128   # sum.27_56 = PHI <sum.27_11, 0>
129   GIMPLE_OMP_RETURN
130   
131   # Creating the atomic operation is done at 
132   create_call_for_reduction_1()  #
133
134   #pragma omp atomic_load
135   D.1839_59 = *&.paral_data_load.33_51->reduction.23;
136   D.1840_60 = sum.27_56 + D.1839_59;
137   #pragma omp atomic_store (D.1840_60);
138   
139   GIMPLE_OMP_RETURN
140   
141  # collecting the result after the join of the threads is done at
142   create_loads_for_reductions().
143   The value computed by the threads is loaded from the
144   shared struct.  #
145
146  
147   .paral_data_load.33_52 = &.paral_data_store.32;
148   sum_37 =  .paral_data_load.33_52->sum.27;
149   sum_43 = D.1795_41 + sum_37;
150
151   exit bb:
152   # sum_21 = PHI <sum_43, sum_26>
153   printf (&"%d"[0], sum_21);
154
155 ...
156
157 }
158
159 */
160
161 /* Minimal number of iterations of a loop that should be executed in each
162    thread.  */
163 #define MIN_PER_THREAD 100
164
165 /* Element of the hashtable, representing a 
166    reduction in the current loop.  */
167 struct reduction_info
168 {
169   gimple reduc_stmt;            /* reduction statement.  */
170   gimple reduc_phi;             /* The phi node defining the reduction.  */
171   enum tree_code reduction_code;/* code for the reduction operation.  */
172   gimple keep_res;              /* The PHI_RESULT of this phi is the resulting value 
173                                    of the reduction variable when existing the loop. */
174   tree initial_value;           /* The initial value of the reduction var before entering the loop.  */
175   tree field;                   /*  the name of the field in the parloop data structure intended for reduction.  */
176   tree init;                    /* reduction initialization value.  */
177   gimple new_phi;               /* (helper field) Newly created phi node whose result 
178                                    will be passed to the atomic operation.  Represents
179                                    the local result each thread computed for the reduction
180                                    operation.  */
181 };
182
183 /* Equality and hash functions for hashtab code.  */
184
185 static int
186 reduction_info_eq (const void *aa, const void *bb)
187 {
188   const struct reduction_info *a = (const struct reduction_info *) aa;
189   const struct reduction_info *b = (const struct reduction_info *) bb;
190
191   return (a->reduc_phi == b->reduc_phi);
192 }
193
194 static hashval_t
195 reduction_info_hash (const void *aa)
196 {
197   const struct reduction_info *a = (const struct reduction_info *) aa;
198
199   return htab_hash_pointer (a->reduc_phi);
200 }
201
202 static struct reduction_info *
203 reduction_phi (htab_t reduction_list, gimple phi)
204 {
205   struct reduction_info tmpred, *red;
206
207   if (htab_elements (reduction_list) == 0)
208     return NULL;
209
210   tmpred.reduc_phi = phi;
211   red = (struct reduction_info *) htab_find (reduction_list, &tmpred);
212
213   return red;
214 }
215
216 /* Element of hashtable of names to copy.  */
217
218 struct name_to_copy_elt
219 {
220   unsigned version;     /* The version of the name to copy.  */
221   tree new_name;        /* The new name used in the copy.  */
222   tree field;           /* The field of the structure used to pass the
223                            value.  */
224 };
225
226 /* Equality and hash functions for hashtab code.  */
227
228 static int
229 name_to_copy_elt_eq (const void *aa, const void *bb)
230 {
231   const struct name_to_copy_elt *a = (const struct name_to_copy_elt *) aa;
232   const struct name_to_copy_elt *b = (const struct name_to_copy_elt *) bb;
233
234   return a->version == b->version;
235 }
236
237 static hashval_t
238 name_to_copy_elt_hash (const void *aa)
239 {
240   const struct name_to_copy_elt *a = (const struct name_to_copy_elt *) aa;
241
242   return (hashval_t) a->version;
243 }
244
245 /* Returns true if the iterations of LOOP are independent on each other (that
246    is, if we can execute them in parallel), and if LOOP satisfies other
247    conditions that we need to be able to parallelize it.  Description of number
248    of iterations is stored to NITER.  Reduction analysis is done, if
249    reductions are found, they are inserted to the REDUCTION_LIST.  */  
250
251 static bool
252 loop_parallel_p (struct loop *loop, htab_t reduction_list,
253                  struct tree_niter_desc *niter)
254 {
255   edge exit = single_dom_exit (loop);
256   VEC (ddr_p, heap) * dependence_relations;
257   VEC (data_reference_p, heap) *datarefs;
258   lambda_trans_matrix trans;
259   bool ret = false;
260   gimple_stmt_iterator gsi;
261   loop_vec_info simple_loop_info;
262
263   /* Only consider innermost loops with just one exit.  The innermost-loop
264      restriction is not necessary, but it makes things simpler.  */
265   if (loop->inner || !exit)
266     return false;
267
268   if (dump_file && (dump_flags & TDF_DETAILS))
269     fprintf (dump_file, "\nConsidering loop %d\n", loop->num);
270
271   /* We need to know # of iterations, and there should be no uses of values
272      defined inside loop outside of it, unless the values are invariants of
273      the loop.  */
274   if (!number_of_iterations_exit (loop, exit, niter, false))
275     {
276       if (dump_file && (dump_flags & TDF_DETAILS))
277         fprintf (dump_file, "  FAILED: number of iterations not known\n");
278       return false;
279     }
280
281   vect_dump = NULL;
282   simple_loop_info = vect_analyze_loop_form (loop);
283
284   for (gsi = gsi_start_phis (loop->header); !gsi_end_p (gsi); gsi_next (&gsi))
285     {
286       gimple phi = gsi_stmt (gsi);
287       gimple reduc_stmt = NULL;
288
289       /* ??? TODO: Change this into a generic function that 
290          recognizes reductions.  */
291       if (!is_gimple_reg (PHI_RESULT (phi)))
292         continue;
293       if (simple_loop_info)
294         reduc_stmt = vect_is_simple_reduction (simple_loop_info, phi);
295
296       /*  Create a reduction_info struct, initialize it and insert it to 
297          the reduction list.  */
298
299       if (reduc_stmt)
300         {
301           PTR *slot;
302           struct reduction_info *new_reduction;
303
304           if (dump_file && (dump_flags & TDF_DETAILS))
305             {
306               fprintf (dump_file,
307                        "Detected reduction. reduction stmt is: \n");
308               print_gimple_stmt (dump_file, reduc_stmt, 0, 0);
309               fprintf (dump_file, "\n");
310             }
311
312           new_reduction = XCNEW (struct reduction_info);
313
314           new_reduction->reduc_stmt = reduc_stmt;
315           new_reduction->reduc_phi = phi;
316           new_reduction->reduction_code = gimple_assign_rhs_code (reduc_stmt);
317           slot = htab_find_slot (reduction_list, new_reduction, INSERT);
318           *slot = new_reduction;
319         }
320     }
321
322   /* Get rid of the information created by the vectorizer functions.  */
323   destroy_loop_vec_info (simple_loop_info, true);
324
325   for (gsi = gsi_start_phis (exit->dest); !gsi_end_p (gsi); gsi_next (&gsi))
326     {
327       gimple phi = gsi_stmt (gsi);
328       struct reduction_info *red;
329       imm_use_iterator imm_iter;
330       use_operand_p use_p;
331       gimple reduc_phi;
332       tree val = PHI_ARG_DEF_FROM_EDGE (phi, exit);
333
334       if (is_gimple_reg (val))
335         {
336           if (dump_file && (dump_flags & TDF_DETAILS))
337             {
338               fprintf (dump_file, "phi is ");
339               print_gimple_stmt (dump_file, phi, 0, 0);
340               fprintf (dump_file, "arg of phi to exit:   value ");
341               print_generic_expr (dump_file, val, 0);
342               fprintf (dump_file, " used outside loop\n");
343               fprintf (dump_file,
344                        "  checking if it a part of reduction pattern:  \n");
345             }
346           if (htab_elements (reduction_list) == 0)
347             {
348               if (dump_file && (dump_flags & TDF_DETAILS))
349                 fprintf (dump_file,
350                          "  FAILED: it is not a part of reduction.\n");
351               return false;
352             }
353           reduc_phi = NULL;
354           FOR_EACH_IMM_USE_FAST (use_p, imm_iter, val)
355           {
356             if (flow_bb_inside_loop_p (loop, gimple_bb (USE_STMT (use_p))))
357               {
358                 reduc_phi = USE_STMT (use_p);
359                 break;
360               }
361           }
362           red = reduction_phi (reduction_list, reduc_phi);
363           if (red == NULL)
364             {
365               if (dump_file && (dump_flags & TDF_DETAILS))
366                 fprintf (dump_file,
367                          "  FAILED: it is not a part of reduction.\n");
368               return false;
369             }
370           if (dump_file && (dump_flags & TDF_DETAILS))
371             {
372               fprintf (dump_file, "reduction phi is  ");
373               print_gimple_stmt (dump_file, red->reduc_phi, 0, 0);
374               fprintf (dump_file, "reduction stmt is  ");
375               print_gimple_stmt (dump_file, red->reduc_stmt, 0, 0);
376             }
377
378         }
379     }
380
381   /* The iterations of the loop may communicate only through bivs whose
382      iteration space can be distributed efficiently.  */
383   for (gsi = gsi_start_phis (loop->header); !gsi_end_p (gsi); gsi_next (&gsi))
384     {
385       gimple phi = gsi_stmt (gsi);
386       tree def = PHI_RESULT (phi);
387       affine_iv iv;
388
389       if (is_gimple_reg (def) && !simple_iv (loop, phi, def, &iv, true))
390         {
391           struct reduction_info *red;
392
393           red = reduction_phi (reduction_list, phi);
394           if (red == NULL)
395             {
396               if (dump_file && (dump_flags & TDF_DETAILS))
397                 fprintf (dump_file,
398                          "  FAILED: scalar dependency between iterations\n");
399               return false;
400             }
401         }
402     }
403
404   /* We need to version the loop to verify assumptions in runtime.  */
405   if (!can_duplicate_loop_p (loop))
406     {
407       if (dump_file && (dump_flags & TDF_DETAILS))
408         fprintf (dump_file, "  FAILED: cannot be duplicated\n");
409       return false;
410     }
411
412   /* Check for problems with dependences.  If the loop can be reversed,
413      the iterations are independent.  */
414   datarefs = VEC_alloc (data_reference_p, heap, 10);
415   dependence_relations = VEC_alloc (ddr_p, heap, 10 * 10);
416   compute_data_dependences_for_loop (loop, true, &datarefs,
417                                      &dependence_relations);
418   if (dump_file && (dump_flags & TDF_DETAILS))
419     dump_data_dependence_relations (dump_file, dependence_relations);
420
421   trans = lambda_trans_matrix_new (1, 1);
422   LTM_MATRIX (trans)[0][0] = -1;
423
424   if (lambda_transform_legal_p (trans, 1, dependence_relations))
425     {
426       ret = true;
427       if (dump_file && (dump_flags & TDF_DETAILS))
428         fprintf (dump_file, "  SUCCESS: may be parallelized\n");
429     }
430   else if (dump_file && (dump_flags & TDF_DETAILS))
431     fprintf (dump_file,
432              "  FAILED: data dependencies exist across iterations\n");
433
434   free_dependence_relations (dependence_relations);
435   free_data_refs (datarefs);
436
437   return ret;
438 }
439
440 /* Return true when LOOP contains basic blocks marked with the
441    BB_IRREDUCIBLE_LOOP flag.  */
442
443 static inline bool
444 loop_has_blocks_with_irreducible_flag (struct loop *loop)
445 {
446   unsigned i;
447   basic_block *bbs = get_loop_body_in_dom_order (loop);
448   bool res = true;
449
450   for (i = 0; i < loop->num_nodes; i++)
451     if (bbs[i]->flags & BB_IRREDUCIBLE_LOOP)
452       goto end;
453
454   res = false;
455  end:
456   free (bbs);
457   return res;
458 }
459
460 /* Assigns the address of OBJ in TYPE to an ssa name, and returns this name.
461    The assignment statement is placed on edge ENTRY.  DECL_ADDRESS maps decls
462    to their addresses that can be reused.  The address of OBJ is known to
463    be invariant in the whole function.  */
464
465 static tree
466 take_address_of (tree obj, tree type, edge entry, htab_t decl_address)
467 {
468   int uid;
469   void **dslot;
470   struct int_tree_map ielt, *nielt;
471   tree *var_p, name, bvar, addr;
472   gimple stmt;
473   gimple_seq stmts;
474
475   /* Since the address of OBJ is invariant, the trees may be shared.
476      Avoid rewriting unrelated parts of the code.  */
477   obj = unshare_expr (obj);
478   for (var_p = &obj;
479        handled_component_p (*var_p);
480        var_p = &TREE_OPERAND (*var_p, 0))
481     continue;
482   uid = DECL_UID (*var_p);
483
484   ielt.uid = uid;
485   dslot = htab_find_slot_with_hash (decl_address, &ielt, uid, INSERT);
486   if (!*dslot)
487     {
488       addr = build_addr (*var_p, current_function_decl);
489       bvar = create_tmp_var (TREE_TYPE (addr), get_name (*var_p));
490       add_referenced_var (bvar);
491       stmt = gimple_build_assign (bvar, addr);
492       name = make_ssa_name (bvar, stmt);
493       gimple_assign_set_lhs (stmt, name);
494       gsi_insert_on_edge_immediate (entry, stmt);
495
496       nielt = XNEW (struct int_tree_map);
497       nielt->uid = uid;
498       nielt->to = name;
499       *dslot = nielt;
500     }
501   else
502     name = ((struct int_tree_map *) *dslot)->to;
503
504   if (var_p != &obj)
505     {
506       *var_p = build1 (INDIRECT_REF, TREE_TYPE (*var_p), name);
507       name = force_gimple_operand (build_addr (obj, current_function_decl),
508                                    &stmts, true, NULL_TREE);
509       if (!gimple_seq_empty_p (stmts))
510         gsi_insert_seq_on_edge_immediate (entry, stmts);
511     }
512
513   if (TREE_TYPE (name) != type)
514     {
515       name = force_gimple_operand (fold_convert (type, name), &stmts, true,
516                                    NULL_TREE);
517       if (!gimple_seq_empty_p (stmts))
518         gsi_insert_seq_on_edge_immediate (entry, stmts);
519     }
520
521   return name;
522 }
523
524 /* Callback for htab_traverse.  Create the initialization statement
525    for reduction described in SLOT, and place it at the preheader of 
526    the loop described in DATA.  */
527
528 static int
529 initialize_reductions (void **slot, void *data)
530 {
531   tree init, c;
532   tree bvar, type, arg;
533   edge e;
534
535   struct reduction_info *const reduc = (struct reduction_info *) *slot;
536   struct loop *loop = (struct loop *) data;
537
538   /* Create initialization in preheader: 
539      reduction_variable = initialization value of reduction.  */
540
541   /* In the phi node at the header, replace the argument coming 
542      from the preheader with the reduction initialization value.  */
543
544   /* Create a new variable to initialize the reduction.  */
545   type = TREE_TYPE (PHI_RESULT (reduc->reduc_phi));
546   bvar = create_tmp_var (type, "reduction");
547   add_referenced_var (bvar);
548
549   c = build_omp_clause (OMP_CLAUSE_REDUCTION);
550   OMP_CLAUSE_REDUCTION_CODE (c) = reduc->reduction_code;
551   OMP_CLAUSE_DECL (c) = SSA_NAME_VAR (gimple_assign_lhs (reduc->reduc_stmt));
552
553   init = omp_reduction_init (c, TREE_TYPE (bvar));
554   reduc->init = init;
555
556   /* Replace the argument representing the initialization value 
557      with the initialization value for the reduction (neutral 
558      element for the particular operation, e.g. 0 for PLUS_EXPR, 
559      1 for MULT_EXPR, etc).  
560      Keep the old value in a new variable "reduction_initial", 
561      that will be taken in consideration after the parallel 
562      computing is done.  */
563
564   e = loop_preheader_edge (loop);
565   arg = PHI_ARG_DEF_FROM_EDGE (reduc->reduc_phi, e);
566   /* Create new variable to hold the initial value.  */
567
568   SET_USE (PHI_ARG_DEF_PTR_FROM_EDGE
569            (reduc->reduc_phi, loop_preheader_edge (loop)), init);
570   reduc->initial_value = arg;
571   return 1;
572 }
573
574 struct elv_data
575 {
576   struct walk_stmt_info info;
577   edge entry;
578   htab_t decl_address;
579   bool changed;
580 };
581
582 /* Eliminates references to local variables in *TP out of the single
583    entry single exit region starting at DTA->ENTRY.
584    DECL_ADDRESS contains addresses of the references that had their
585    address taken already.  If the expression is changed, CHANGED is
586    set to true.  Callback for walk_tree.  */
587
588 static tree
589 eliminate_local_variables_1 (tree *tp, int *walk_subtrees, void *data)
590 {
591   struct elv_data *const dta = (struct elv_data *) data;
592   tree t = *tp, var, addr, addr_type, type, obj;
593
594   if (DECL_P (t))
595     {
596       *walk_subtrees = 0;
597
598       if (!SSA_VAR_P (t) || DECL_EXTERNAL (t))
599         return NULL_TREE;
600
601       type = TREE_TYPE (t);
602       addr_type = build_pointer_type (type);
603       addr = take_address_of (t, addr_type, dta->entry, dta->decl_address);
604       *tp = build1 (INDIRECT_REF, TREE_TYPE (*tp), addr);
605
606       dta->changed = true;
607       return NULL_TREE;
608     }
609
610   if (TREE_CODE (t) == ADDR_EXPR)
611     {
612       /* ADDR_EXPR may appear in two contexts:
613          -- as a gimple operand, when the address taken is a function invariant
614          -- as gimple rhs, when the resulting address in not a function
615             invariant
616          We do not need to do anything special in the latter case (the base of
617          the memory reference whose address is taken may be replaced in the
618          DECL_P case).  The former case is more complicated, as we need to
619          ensure that the new address is still a gimple operand.  Thus, it
620          is not sufficient to replace just the base of the memory reference --
621          we need to move the whole computation of the address out of the
622          loop.  */
623       if (!is_gimple_val (t))
624         return NULL_TREE;
625
626       *walk_subtrees = 0;
627       obj = TREE_OPERAND (t, 0);
628       var = get_base_address (obj);
629       if (!var || !SSA_VAR_P (var) || DECL_EXTERNAL (var))
630         return NULL_TREE;
631
632       addr_type = TREE_TYPE (t);
633       addr = take_address_of (obj, addr_type, dta->entry, dta->decl_address);
634       *tp = addr;
635
636       dta->changed = true;
637       return NULL_TREE;
638     }
639
640   if (!EXPR_P (t))
641     *walk_subtrees = 0;
642
643   return NULL_TREE;
644 }
645
646 /* Moves the references to local variables in STMT out of the single
647    entry single exit region starting at ENTRY.  DECL_ADDRESS contains
648    addresses of the references that had their address taken
649    already.  */
650
651 static void
652 eliminate_local_variables_stmt (edge entry, gimple stmt,
653                                 htab_t decl_address)
654 {
655   struct elv_data dta;
656
657   memset (&dta.info, '\0', sizeof (dta.info));
658   dta.entry = entry;
659   dta.decl_address = decl_address;
660   dta.changed = false;
661
662   walk_gimple_op (stmt, eliminate_local_variables_1, &dta.info);
663
664   if (dta.changed)
665     update_stmt (stmt);
666 }
667
668 /* Eliminates the references to local variables from the single entry
669    single exit region between the ENTRY and EXIT edges.
670   
671    This includes:
672    1) Taking address of a local variable -- these are moved out of the 
673    region (and temporary variable is created to hold the address if 
674    necessary).
675
676    2) Dereferencing a local variable -- these are replaced with indirect
677    references.  */
678
679 static void
680 eliminate_local_variables (edge entry, edge exit)
681 {
682   basic_block bb;
683   VEC (basic_block, heap) *body = VEC_alloc (basic_block, heap, 3);
684   unsigned i;
685   gimple_stmt_iterator gsi;
686   htab_t decl_address = htab_create (10, int_tree_map_hash, int_tree_map_eq,
687                                      free);
688   basic_block entry_bb = entry->src;
689   basic_block exit_bb = exit->dest;
690
691   gather_blocks_in_sese_region (entry_bb, exit_bb, &body);
692
693   for (i = 0; VEC_iterate (basic_block, body, i, bb); i++)
694     if (bb != entry_bb && bb != exit_bb)
695       for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
696         eliminate_local_variables_stmt (entry, gsi_stmt (gsi),
697                                         decl_address);
698
699   htab_delete (decl_address);
700   VEC_free (basic_block, heap, body);
701 }
702
703 /* Returns true if expression EXPR is not defined between ENTRY and
704    EXIT, i.e. if all its operands are defined outside of the region.  */
705
706 static bool
707 expr_invariant_in_region_p (edge entry, edge exit, tree expr)
708 {
709   basic_block entry_bb = entry->src;
710   basic_block exit_bb = exit->dest;
711   basic_block def_bb;
712
713   if (is_gimple_min_invariant (expr))
714     return true;
715
716   if (TREE_CODE (expr) == SSA_NAME)
717     {
718       def_bb = gimple_bb (SSA_NAME_DEF_STMT (expr));
719       if (def_bb
720           && dominated_by_p (CDI_DOMINATORS, def_bb, entry_bb)
721           && !dominated_by_p (CDI_DOMINATORS, def_bb, exit_bb))
722         return false;
723
724       return true;
725     }
726
727   return false;
728 }
729
730 /* If COPY_NAME_P is true, creates and returns a duplicate of NAME.
731    The copies are stored to NAME_COPIES, if NAME was already duplicated,
732    its duplicate stored in NAME_COPIES is returned.
733    
734    Regardless of COPY_NAME_P, the decl used as a base of the ssa name is also
735    duplicated, storing the copies in DECL_COPIES.  */
736
737 static tree
738 separate_decls_in_region_name (tree name,
739                                htab_t name_copies, htab_t decl_copies,
740                                bool copy_name_p)
741 {
742   tree copy, var, var_copy;
743   unsigned idx, uid, nuid;
744   struct int_tree_map ielt, *nielt;
745   struct name_to_copy_elt elt, *nelt;
746   void **slot, **dslot;
747
748   if (TREE_CODE (name) != SSA_NAME)
749     return name;
750
751   idx = SSA_NAME_VERSION (name);
752   elt.version = idx;
753   slot = htab_find_slot_with_hash (name_copies, &elt, idx,
754                                    copy_name_p ? INSERT : NO_INSERT);
755   if (slot && *slot)
756     return ((struct name_to_copy_elt *) *slot)->new_name;
757
758   var = SSA_NAME_VAR (name);
759   uid = DECL_UID (var);
760   ielt.uid = uid;
761   dslot = htab_find_slot_with_hash (decl_copies, &ielt, uid, INSERT);
762   if (!*dslot)
763     {
764       var_copy = create_tmp_var (TREE_TYPE (var), get_name (var));
765       DECL_GIMPLE_REG_P (var_copy) = DECL_GIMPLE_REG_P (var);
766       add_referenced_var (var_copy);
767       nielt = XNEW (struct int_tree_map);
768       nielt->uid = uid;
769       nielt->to = var_copy;
770       *dslot = nielt;
771
772       /* Ensure that when we meet this decl next time, we won't duplicate
773          it again.  */
774       nuid = DECL_UID (var_copy);
775       ielt.uid = nuid;
776       dslot = htab_find_slot_with_hash (decl_copies, &ielt, nuid, INSERT);
777       gcc_assert (!*dslot);
778       nielt = XNEW (struct int_tree_map);
779       nielt->uid = nuid;
780       nielt->to = var_copy;
781       *dslot = nielt;
782     }
783   else
784     var_copy = ((struct int_tree_map *) *dslot)->to;
785
786   if (copy_name_p)
787     {
788       copy = duplicate_ssa_name (name, NULL);
789       nelt = XNEW (struct name_to_copy_elt);
790       nelt->version = idx;
791       nelt->new_name = copy;
792       nelt->field = NULL_TREE;
793       *slot = nelt;
794     }
795   else
796     {
797       gcc_assert (!slot);
798       copy = name;
799     }
800
801   SSA_NAME_VAR (copy) = var_copy;
802   return copy;
803 }
804
805 /* Finds the ssa names used in STMT that are defined outside the
806    region between ENTRY and EXIT and replaces such ssa names with
807    their duplicates.  The duplicates are stored to NAME_COPIES.  Base
808    decls of all ssa names used in STMT (including those defined in
809    LOOP) are replaced with the new temporary variables; the
810    replacement decls are stored in DECL_COPIES.  */
811
812 static void
813 separate_decls_in_region_stmt (edge entry, edge exit, gimple stmt,
814                                htab_t name_copies, htab_t decl_copies)
815 {
816   use_operand_p use;
817   def_operand_p def;
818   ssa_op_iter oi;
819   tree name, copy;
820   bool copy_name_p;
821
822   mark_virtual_ops_for_renaming (stmt);
823
824   FOR_EACH_PHI_OR_STMT_DEF (def, stmt, oi, SSA_OP_DEF)
825   {
826     name = DEF_FROM_PTR (def);
827     gcc_assert (TREE_CODE (name) == SSA_NAME);
828     copy = separate_decls_in_region_name (name, name_copies, decl_copies,
829                                           false);
830     gcc_assert (copy == name);
831   }
832
833   FOR_EACH_PHI_OR_STMT_USE (use, stmt, oi, SSA_OP_USE)
834   {
835     name = USE_FROM_PTR (use);
836     if (TREE_CODE (name) != SSA_NAME)
837       continue;
838
839     copy_name_p = expr_invariant_in_region_p (entry, exit, name);
840     copy = separate_decls_in_region_name (name, name_copies, decl_copies,
841                                           copy_name_p);
842     SET_USE (use, copy);
843   }
844 }
845
846 /* Callback for htab_traverse.  Adds a field corresponding to the reduction
847    specified in SLOT. The type is passed in DATA.  */
848
849 static int
850 add_field_for_reduction (void **slot, void *data)
851 {
852   
853   struct reduction_info *const red = (struct reduction_info *) *slot;
854   tree const type = (tree) data;
855   tree var = SSA_NAME_VAR (gimple_assign_lhs (red->reduc_stmt));
856   tree field = build_decl (FIELD_DECL, DECL_NAME (var), TREE_TYPE (var));
857
858   insert_field_into_struct (type, field);
859
860   red->field = field;
861
862   return 1;
863 }
864
865 /* Callback for htab_traverse.  Adds a field corresponding to a ssa name
866    described in SLOT. The type is passed in DATA.  */ 
867
868 static int
869 add_field_for_name (void **slot, void *data)
870 {
871   struct name_to_copy_elt *const elt = (struct name_to_copy_elt *) *slot;
872   tree type = (tree) data;
873   tree name = ssa_name (elt->version);
874   tree var = SSA_NAME_VAR (name);
875   tree field = build_decl (FIELD_DECL, DECL_NAME (var), TREE_TYPE (var));
876
877   insert_field_into_struct (type, field);
878   elt->field = field;
879
880   return 1;
881 }
882
883 /* Callback for htab_traverse.  A local result is the intermediate result 
884    computed by a single 
885    thread, or the initial value in case no iteration was executed.
886    This function creates a phi node reflecting these values.  
887    The phi's result will be stored in NEW_PHI field of the 
888    reduction's data structure.  */ 
889
890 static int
891 create_phi_for_local_result (void **slot, void *data)
892 {
893   struct reduction_info *const reduc = (struct reduction_info *) *slot;
894   const struct loop *const loop = (const struct loop *) data;
895   edge e;
896   gimple new_phi;
897   basic_block store_bb;
898   tree local_res;
899
900   /* STORE_BB is the block where the phi 
901      should be stored.  It is the destination of the loop exit.  
902      (Find the fallthru edge from GIMPLE_OMP_CONTINUE).  */
903   store_bb = FALLTHRU_EDGE (loop->latch)->dest;
904
905   /* STORE_BB has two predecessors.  One coming from  the loop
906      (the reduction's result is computed at the loop),
907      and another coming from a block preceding the loop, 
908      when no iterations 
909      are executed (the initial value should be taken).  */ 
910   if (EDGE_PRED (store_bb, 0) == FALLTHRU_EDGE (loop->latch))
911     e = EDGE_PRED (store_bb, 1);
912   else
913     e = EDGE_PRED (store_bb, 0);
914   local_res
915     = make_ssa_name (SSA_NAME_VAR (gimple_assign_lhs (reduc->reduc_stmt)),
916                      NULL);
917   new_phi = create_phi_node (local_res, store_bb);
918   SSA_NAME_DEF_STMT (local_res) = new_phi;
919   add_phi_arg (new_phi, reduc->init, e);
920   add_phi_arg (new_phi, gimple_assign_lhs (reduc->reduc_stmt),
921                FALLTHRU_EDGE (loop->latch));
922   reduc->new_phi = new_phi;
923
924   return 1;
925 }
926
927 struct clsn_data
928 {
929   tree store;
930   tree load;
931
932   basic_block store_bb;
933   basic_block load_bb;
934 };
935
936 /* Callback for htab_traverse.  Create an atomic instruction for the
937    reduction described in SLOT.  
938    DATA annotates the place in memory the atomic operation relates to,
939    and the basic block it needs to be generated in.  */
940
941 static int
942 create_call_for_reduction_1 (void **slot, void *data)
943 {
944   struct reduction_info *const reduc = (struct reduction_info *) *slot;
945   struct clsn_data *const clsn_data = (struct clsn_data *) data;
946   gimple_stmt_iterator gsi;
947   tree type = TREE_TYPE (PHI_RESULT (reduc->reduc_phi));
948   tree struct_type = TREE_TYPE (TREE_TYPE (clsn_data->load));
949   tree load_struct;
950   basic_block bb;
951   basic_block new_bb;
952   edge e;
953   tree t, addr, addr_type, ref, x;
954   tree tmp_load, name;
955   gimple load;
956
957   load_struct = fold_build1 (INDIRECT_REF, struct_type, clsn_data->load);
958   t = build3 (COMPONENT_REF, type, load_struct, reduc->field, NULL_TREE);
959   addr_type = build_pointer_type (type);
960
961   addr = build_addr (t, current_function_decl);
962
963   /* Create phi node.  */
964   bb = clsn_data->load_bb;
965
966   e = split_block (bb, t);
967   new_bb = e->dest;
968
969   tmp_load = create_tmp_var (TREE_TYPE (TREE_TYPE (addr)), NULL);
970   add_referenced_var (tmp_load);
971   tmp_load = make_ssa_name (tmp_load, NULL);
972   load = gimple_build_omp_atomic_load (tmp_load, addr);
973   SSA_NAME_DEF_STMT (tmp_load) = load;
974   gsi = gsi_start_bb (new_bb);
975   gsi_insert_after (&gsi, load, GSI_NEW_STMT);
976
977   e = split_block (new_bb, load);
978   new_bb = e->dest;
979   gsi = gsi_start_bb (new_bb);
980   ref = tmp_load;
981   x = fold_build2 (reduc->reduction_code,
982                    TREE_TYPE (PHI_RESULT (reduc->new_phi)), ref,
983                    PHI_RESULT (reduc->new_phi));
984
985   name = force_gimple_operand_gsi (&gsi, x, true, NULL_TREE, true,
986                                    GSI_CONTINUE_LINKING);
987
988   gsi_insert_after (&gsi, gimple_build_omp_atomic_store (name), GSI_NEW_STMT);
989   return 1;
990 }
991
992 /* Create the atomic operation at the join point of the threads.  
993    REDUCTION_LIST describes the reductions in the LOOP.  
994    LD_ST_DATA describes the shared data structure where 
995    shared data is stored in and loaded from.  */
996 static void
997 create_call_for_reduction (struct loop *loop, htab_t reduction_list, 
998                            struct clsn_data *ld_st_data)
999 {
1000   htab_traverse (reduction_list, create_phi_for_local_result, loop);
1001   /* Find the fallthru edge from GIMPLE_OMP_CONTINUE.  */
1002   ld_st_data->load_bb = FALLTHRU_EDGE (loop->latch)->dest;
1003   htab_traverse (reduction_list, create_call_for_reduction_1, ld_st_data);
1004 }
1005
1006 /* Callback for htab_traverse.  Loads the final reduction value at the
1007    join point of all threads, and inserts it in the right place.  */
1008
1009 static int
1010 create_loads_for_reductions (void **slot, void *data)
1011 {
1012   struct reduction_info *const red = (struct reduction_info *) *slot;
1013   struct clsn_data *const clsn_data = (struct clsn_data *) data;
1014   gimple stmt;
1015   gimple_stmt_iterator gsi;
1016   tree type = TREE_TYPE (gimple_assign_lhs (red->reduc_stmt));
1017   tree struct_type = TREE_TYPE (TREE_TYPE (clsn_data->load));
1018   tree load_struct;
1019   tree name;
1020   tree x;
1021
1022   gsi = gsi_after_labels (clsn_data->load_bb);
1023   load_struct = fold_build1 (INDIRECT_REF, struct_type, clsn_data->load);
1024   load_struct = build3 (COMPONENT_REF, type, load_struct, red->field,
1025                         NULL_TREE);
1026
1027   x = load_struct;
1028   name = PHI_RESULT (red->keep_res);
1029   stmt = gimple_build_assign (name, x);
1030   SSA_NAME_DEF_STMT (name) = stmt;
1031
1032   gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);
1033
1034   for (gsi = gsi_start_phis (gimple_bb (red->keep_res));
1035        !gsi_end_p (gsi); gsi_next (&gsi))
1036     if (gsi_stmt (gsi) == red->keep_res)
1037       {
1038         remove_phi_node (&gsi, false);
1039         return 1;
1040       }
1041   gcc_unreachable ();
1042 }
1043
1044 /* Load the reduction result that was stored in LD_ST_DATA.  
1045    REDUCTION_LIST describes the list of reductions that the
1046    loads should be generated for.  */
1047 static void
1048 create_final_loads_for_reduction (htab_t reduction_list, 
1049                                   struct clsn_data *ld_st_data)
1050 {
1051   gimple_stmt_iterator gsi;
1052   tree t;
1053   gimple stmt;
1054
1055   gsi = gsi_after_labels (ld_st_data->load_bb);
1056   t = build_fold_addr_expr (ld_st_data->store);
1057   stmt = gimple_build_assign (ld_st_data->load, t);
1058
1059   gsi_insert_before (&gsi, stmt, GSI_NEW_STMT);
1060   SSA_NAME_DEF_STMT (ld_st_data->load) = stmt;
1061
1062   htab_traverse (reduction_list, create_loads_for_reductions, ld_st_data);
1063
1064 }
1065
1066 /* Callback for htab_traverse.  Store the neutral value for the
1067   particular reduction's operation, e.g. 0 for PLUS_EXPR,
1068   1 for MULT_EXPR, etc. into the reduction field.
1069   The reduction is specified in SLOT. The store information is 
1070   passed in DATA.  */  
1071
1072 static int
1073 create_stores_for_reduction (void **slot, void *data)
1074 {
1075   struct reduction_info *const red = (struct reduction_info *) *slot;
1076   struct clsn_data *const clsn_data = (struct clsn_data *) data;
1077   tree t;
1078   gimple stmt;
1079   gimple_stmt_iterator gsi;
1080   tree type = TREE_TYPE (gimple_assign_lhs (red->reduc_stmt));
1081
1082   gsi = gsi_last_bb (clsn_data->store_bb);
1083   t = build3 (COMPONENT_REF, type, clsn_data->store, red->field, NULL_TREE);
1084   stmt = gimple_build_assign (t, red->initial_value);
1085   mark_virtual_ops_for_renaming (stmt);
1086   gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);
1087
1088   return 1;
1089 }
1090
1091 /* Callback for htab_traverse.  Creates loads to a field of LOAD in LOAD_BB and
1092    store to a field of STORE in STORE_BB for the ssa name and its duplicate
1093    specified in SLOT.  */
1094
1095 static int
1096 create_loads_and_stores_for_name (void **slot, void *data)
1097 {
1098   struct name_to_copy_elt *const elt = (struct name_to_copy_elt *) *slot;
1099   struct clsn_data *const clsn_data = (struct clsn_data *) data;
1100   tree t;
1101   gimple stmt;
1102   gimple_stmt_iterator gsi;
1103   tree type = TREE_TYPE (elt->new_name);
1104   tree struct_type = TREE_TYPE (TREE_TYPE (clsn_data->load));
1105   tree load_struct;
1106
1107   gsi = gsi_last_bb (clsn_data->store_bb);
1108   t = build3 (COMPONENT_REF, type, clsn_data->store, elt->field, NULL_TREE);
1109   stmt = gimple_build_assign (t, ssa_name (elt->version));
1110   mark_virtual_ops_for_renaming (stmt);
1111   gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);
1112
1113   gsi = gsi_last_bb (clsn_data->load_bb);
1114   load_struct = fold_build1 (INDIRECT_REF, struct_type, clsn_data->load);
1115   t = build3 (COMPONENT_REF, type, load_struct, elt->field, NULL_TREE);
1116   stmt = gimple_build_assign (elt->new_name, t);
1117   SSA_NAME_DEF_STMT (elt->new_name) = stmt;
1118   gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);
1119
1120   return 1;
1121 }
1122
1123 /* Moves all the variables used in LOOP and defined outside of it (including
1124    the initial values of loop phi nodes, and *PER_THREAD if it is a ssa
1125    name) to a structure created for this purpose.  The code
1126  
1127    while (1)
1128      {
1129        use (a);
1130        use (b);
1131      }
1132
1133    is transformed this way:
1134
1135    bb0:
1136    old.a = a;
1137    old.b = b;
1138
1139    bb1:
1140    a' = new->a;
1141    b' = new->b;
1142    while (1)
1143      {
1144        use (a');
1145        use (b');
1146      }
1147
1148    `old' is stored to *ARG_STRUCT and `new' is stored to NEW_ARG_STRUCT.  The
1149    pointer `new' is intentionally not initialized (the loop will be split to a
1150    separate function later, and `new' will be initialized from its arguments).
1151    LD_ST_DATA holds information about the shared data structure used to pass
1152    information among the threads.  It is initialized here, and 
1153    gen_parallel_loop will pass it to create_call_for_reduction that 
1154    needs this information.  REDUCTION_LIST describes the reductions 
1155    in LOOP.  */
1156
1157 static void
1158 separate_decls_in_region (edge entry, edge exit, htab_t reduction_list,
1159                           tree *arg_struct, tree *new_arg_struct, 
1160                           struct clsn_data *ld_st_data)
1161
1162 {
1163   basic_block bb1 = split_edge (entry);
1164   basic_block bb0 = single_pred (bb1);
1165   htab_t name_copies = htab_create (10, name_to_copy_elt_hash,
1166                                     name_to_copy_elt_eq, free);
1167   htab_t decl_copies = htab_create (10, int_tree_map_hash, int_tree_map_eq,
1168                                     free);
1169   unsigned i;
1170   tree type, type_name, nvar;
1171   gimple_stmt_iterator gsi;
1172   struct clsn_data clsn_data;
1173   VEC (basic_block, heap) *body = VEC_alloc (basic_block, heap, 3);
1174   basic_block bb;
1175   basic_block entry_bb = bb1;
1176   basic_block exit_bb = exit->dest;
1177
1178   entry = single_succ_edge (entry_bb);
1179   gather_blocks_in_sese_region (entry_bb, exit_bb, &body);
1180
1181   for (i = 0; VEC_iterate (basic_block, body, i, bb); i++)
1182     {
1183       if (bb != entry_bb && bb != exit_bb) 
1184         {
1185           for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1186             separate_decls_in_region_stmt (entry, exit, gsi_stmt (gsi),
1187                                            name_copies, decl_copies);
1188
1189           for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1190             separate_decls_in_region_stmt (entry, exit, gsi_stmt (gsi),
1191                                            name_copies, decl_copies);
1192         }
1193     }
1194
1195   VEC_free (basic_block, heap, body);
1196
1197   if (htab_elements (name_copies) == 0 && reduction_list == 0) 
1198     {
1199       /* It may happen that there is nothing to copy (if there are only
1200          loop carried and external variables in the loop).  */
1201       *arg_struct = NULL;
1202       *new_arg_struct = NULL;
1203     }
1204   else
1205     {
1206       /* Create the type for the structure to store the ssa names to.  */
1207       type = lang_hooks.types.make_type (RECORD_TYPE);
1208       type_name = build_decl (TYPE_DECL, create_tmp_var_name (".paral_data"),
1209                               type);
1210       TYPE_NAME (type) = type_name;
1211
1212       htab_traverse (name_copies, add_field_for_name, type);
1213       if (reduction_list && htab_elements (reduction_list) > 0)
1214         {
1215           /* Create the fields for reductions.  */
1216           htab_traverse (reduction_list, add_field_for_reduction,
1217                          type);
1218         }
1219       layout_type (type);
1220  
1221       /* Create the loads and stores.  */
1222       *arg_struct = create_tmp_var (type, ".paral_data_store");
1223       add_referenced_var (*arg_struct);
1224       nvar = create_tmp_var (build_pointer_type (type), ".paral_data_load");
1225       add_referenced_var (nvar);
1226       *new_arg_struct = make_ssa_name (nvar, NULL);
1227
1228       ld_st_data->store = *arg_struct;
1229       ld_st_data->load = *new_arg_struct;
1230       ld_st_data->store_bb = bb0;
1231       ld_st_data->load_bb = bb1;
1232
1233       htab_traverse (name_copies, create_loads_and_stores_for_name,
1234                      ld_st_data);
1235
1236       /* Load the calculation from memory (after the join of the threads).  */
1237
1238       if (reduction_list && htab_elements (reduction_list) > 0)
1239         {
1240           htab_traverse (reduction_list, create_stores_for_reduction,
1241                         ld_st_data); 
1242           clsn_data.load = make_ssa_name (nvar, NULL);
1243           clsn_data.load_bb = exit->dest;
1244           clsn_data.store = ld_st_data->store;
1245           create_final_loads_for_reduction (reduction_list, &clsn_data);
1246         }
1247     }
1248
1249   htab_delete (decl_copies);
1250   htab_delete (name_copies);
1251 }
1252
1253 /* Bitmap containing uids of functions created by parallelization.  We cannot
1254    allocate it from the default obstack, as it must live across compilation
1255    of several functions; we make it gc allocated instead.  */
1256
1257 static GTY(()) bitmap parallelized_functions;
1258
1259 /* Returns true if FN was created by create_loop_fn.  */
1260
1261 static bool
1262 parallelized_function_p (tree fn)
1263 {
1264   if (!parallelized_functions || !DECL_ARTIFICIAL (fn))
1265     return false;
1266
1267   return bitmap_bit_p (parallelized_functions, DECL_UID (fn));
1268 }
1269
1270 /* Creates and returns an empty function that will receive the body of
1271    a parallelized loop.  */
1272
1273 static tree
1274 create_loop_fn (void)
1275 {
1276   char buf[100];
1277   char *tname;
1278   tree decl, type, name, t;
1279   struct function *act_cfun = cfun;
1280   static unsigned loopfn_num;
1281
1282   snprintf (buf, 100, "%s.$loopfn", current_function_name ());
1283   ASM_FORMAT_PRIVATE_NAME (tname, buf, loopfn_num++);
1284   clean_symbol_name (tname);
1285   name = get_identifier (tname);
1286   type = build_function_type_list (void_type_node, ptr_type_node, NULL_TREE);
1287
1288   decl = build_decl (FUNCTION_DECL, name, type);
1289   if (!parallelized_functions)
1290     parallelized_functions = BITMAP_GGC_ALLOC ();
1291   bitmap_set_bit (parallelized_functions, DECL_UID (decl));
1292
1293   TREE_STATIC (decl) = 1;
1294   TREE_USED (decl) = 1;
1295   DECL_ARTIFICIAL (decl) = 1;
1296   DECL_IGNORED_P (decl) = 0;
1297   TREE_PUBLIC (decl) = 0;
1298   DECL_UNINLINABLE (decl) = 1;
1299   DECL_EXTERNAL (decl) = 0;
1300   DECL_CONTEXT (decl) = NULL_TREE;
1301   DECL_INITIAL (decl) = make_node (BLOCK);
1302
1303   t = build_decl (RESULT_DECL, NULL_TREE, void_type_node);
1304   DECL_ARTIFICIAL (t) = 1;
1305   DECL_IGNORED_P (t) = 1;
1306   DECL_RESULT (decl) = t;
1307
1308   t = build_decl (PARM_DECL, get_identifier (".paral_data_param"),
1309                   ptr_type_node);
1310   DECL_ARTIFICIAL (t) = 1;
1311   DECL_ARG_TYPE (t) = ptr_type_node;
1312   DECL_CONTEXT (t) = decl;
1313   TREE_USED (t) = 1;
1314   DECL_ARGUMENTS (decl) = t;
1315
1316   allocate_struct_function (decl, false);
1317
1318   /* The call to allocate_struct_function clobbers CFUN, so we need to restore
1319      it.  */
1320   set_cfun (act_cfun);
1321
1322   return decl;
1323 }
1324
1325 /* Bases all the induction variables in LOOP on a single induction variable
1326    (unsigned with base 0 and step 1), whose final value is compared with
1327    NIT.  The induction variable is incremented in the loop latch.  
1328    REDUCTION_LIST describes the reductions in LOOP.  Return the induction 
1329    variable that was created.  */
1330
1331 tree
1332 canonicalize_loop_ivs (struct loop *loop, htab_t reduction_list, tree nit)
1333 {
1334   unsigned precision = TYPE_PRECISION (TREE_TYPE (nit));
1335   tree res, type, var_before, val, atype, mtype;
1336   gimple_stmt_iterator gsi, psi;
1337   gimple phi, stmt;
1338   bool ok;
1339   affine_iv iv;
1340   edge exit = single_dom_exit (loop);
1341   struct reduction_info *red;
1342
1343   for (psi = gsi_start_phis (loop->header);
1344        !gsi_end_p (psi); gsi_next (&psi))
1345     {
1346       phi = gsi_stmt (psi);
1347       res = PHI_RESULT (phi);
1348
1349       if (is_gimple_reg (res) && TYPE_PRECISION (TREE_TYPE (res)) > precision)
1350         precision = TYPE_PRECISION (TREE_TYPE (res));
1351     }
1352
1353   type = lang_hooks.types.type_for_size (precision, 1);
1354
1355   gsi = gsi_last_bb (loop->latch);
1356   create_iv (build_int_cst_type (type, 0), build_int_cst (type, 1), NULL_TREE,
1357              loop, &gsi, true, &var_before, NULL);
1358
1359   gsi = gsi_after_labels (loop->header);
1360   for (psi = gsi_start_phis (loop->header); !gsi_end_p (psi); )
1361     {
1362       phi = gsi_stmt (psi);
1363       res = PHI_RESULT (phi);
1364
1365       if (!is_gimple_reg (res) || res == var_before)
1366         {
1367           gsi_next (&psi);
1368           continue;
1369         }
1370
1371       ok = simple_iv (loop, phi, res, &iv, true);
1372
1373       if (reduction_list)
1374         red = reduction_phi (reduction_list, phi);
1375       else
1376         red = NULL;
1377
1378       /* We preserve the reduction phi nodes.  */
1379       if (!ok && red)
1380         {
1381           gsi_next (&psi);
1382           continue;
1383         }
1384       else
1385         gcc_assert (ok);
1386       remove_phi_node (&psi, false);
1387
1388       atype = TREE_TYPE (res);
1389       mtype = POINTER_TYPE_P (atype) ? sizetype : atype;
1390       val = fold_build2 (MULT_EXPR, mtype, unshare_expr (iv.step),
1391                          fold_convert (mtype, var_before));
1392       val = fold_build2 (POINTER_TYPE_P (atype)
1393                          ? POINTER_PLUS_EXPR : PLUS_EXPR,
1394                          atype, unshare_expr (iv.base), val);
1395       val = force_gimple_operand_gsi (&gsi, val, false, NULL_TREE, true,
1396                                       GSI_SAME_STMT);
1397       stmt = gimple_build_assign (res, val);
1398       gsi_insert_before (&gsi, stmt, GSI_SAME_STMT);
1399       SSA_NAME_DEF_STMT (res) = stmt;
1400     }
1401
1402   stmt = last_stmt (exit->src);
1403   /* Make the loop exit if the control condition is not satisfied.  */
1404   if (exit->flags & EDGE_TRUE_VALUE)
1405     {
1406       edge te, fe;
1407
1408       extract_true_false_edges_from_block (exit->src, &te, &fe);
1409       te->flags = EDGE_FALSE_VALUE;
1410       fe->flags = EDGE_TRUE_VALUE;
1411     }
1412   gimple_cond_set_code (stmt, LT_EXPR);
1413   gimple_cond_set_lhs (stmt, var_before);
1414   gimple_cond_set_rhs (stmt, nit);
1415   update_stmt (stmt);
1416
1417   return var_before;
1418 }
1419
1420 /* Moves the exit condition of LOOP to the beginning of its header, and
1421    duplicates the part of the last iteration that gets disabled to the
1422    exit of the loop.  NIT is the number of iterations of the loop
1423    (used to initialize the variables in the duplicated part).
1424  
1425    TODO: the common case is that latch of the loop is empty and immediately
1426    follows the loop exit.  In this case, it would be better not to copy the
1427    body of the loop, but only move the entry of the loop directly before the
1428    exit check and increase the number of iterations of the loop by one.
1429    This may need some additional preconditioning in case NIT = ~0.  
1430    REDUCTION_LIST describes the reductions in LOOP.  */
1431
1432 static void
1433 transform_to_exit_first_loop (struct loop *loop, htab_t reduction_list, tree nit)
1434 {
1435   basic_block *bbs, *nbbs, ex_bb, orig_header;
1436   unsigned n;
1437   bool ok;
1438   edge exit = single_dom_exit (loop), hpred;
1439   tree control, control_name, res, t;
1440   gimple phi, nphi, cond_stmt, stmt;
1441   gimple_stmt_iterator gsi;
1442
1443   split_block_after_labels (loop->header);
1444   orig_header = single_succ (loop->header);
1445   hpred = single_succ_edge (loop->header);
1446
1447   cond_stmt = last_stmt (exit->src);
1448   control = gimple_cond_lhs (cond_stmt);
1449   gcc_assert (gimple_cond_rhs (cond_stmt) == nit);
1450
1451   /* Make sure that we have phi nodes on exit for all loop header phis
1452      (create_parallel_loop requires that).  */
1453   for (gsi = gsi_start_phis (loop->header); !gsi_end_p (gsi); gsi_next (&gsi))
1454     {
1455       phi = gsi_stmt (gsi);
1456       res = PHI_RESULT (phi);
1457       t = make_ssa_name (SSA_NAME_VAR (res), phi);
1458       SET_PHI_RESULT (phi, t);
1459
1460       nphi = create_phi_node (res, orig_header);
1461       SSA_NAME_DEF_STMT (res) = nphi;
1462       add_phi_arg (nphi, t, hpred);
1463
1464       if (res == control)
1465         {
1466           gimple_cond_set_lhs (cond_stmt, t);
1467           update_stmt (cond_stmt);
1468           control = t;
1469         }
1470     }
1471
1472   bbs = get_loop_body_in_dom_order (loop);
1473   for (n = 0; bbs[n] != exit->src; n++)
1474     continue;
1475   nbbs = XNEWVEC (basic_block, n);
1476   ok = gimple_duplicate_sese_tail (single_succ_edge (loop->header), exit,
1477                                    bbs + 1, n, nbbs);
1478   gcc_assert (ok);
1479   free (bbs);
1480   ex_bb = nbbs[0];
1481   free (nbbs);
1482
1483   /* Other than reductions, the only gimple reg that should be copied 
1484      out of the loop is the control variable.  */
1485
1486   control_name = NULL_TREE;
1487   for (gsi = gsi_start_phis (ex_bb); !gsi_end_p (gsi); )
1488     {
1489       phi = gsi_stmt (gsi);
1490       res = PHI_RESULT (phi);
1491       if (!is_gimple_reg (res))
1492         {
1493           gsi_next (&gsi);
1494           continue;
1495         }
1496
1497       /* Check if it is a part of reduction.  If it is,
1498          keep the phi at the reduction's keep_res field.  The  
1499          PHI_RESULT of this phi is the resulting value of the reduction 
1500          variable when exiting the loop.  */
1501
1502       exit = single_dom_exit (loop);
1503
1504       if (htab_elements (reduction_list) > 0) 
1505         {
1506           struct reduction_info *red;
1507
1508           tree val = PHI_ARG_DEF_FROM_EDGE (phi, exit);
1509
1510           red = reduction_phi (reduction_list, SSA_NAME_DEF_STMT (val));
1511           if (red)
1512             {
1513               red->keep_res = phi;
1514               gsi_next (&gsi);
1515               continue;
1516             }
1517         }
1518       gcc_assert (control_name == NULL_TREE
1519                   && SSA_NAME_VAR (res) == SSA_NAME_VAR (control));
1520       control_name = res;
1521       remove_phi_node (&gsi, false);
1522     }
1523   gcc_assert (control_name != NULL_TREE);
1524
1525   /* Initialize the control variable to NIT.  */
1526   gsi = gsi_after_labels (ex_bb);
1527   nit = force_gimple_operand_gsi (&gsi,
1528                                   fold_convert (TREE_TYPE (control_name), nit),
1529                                   false, NULL_TREE, false, GSI_SAME_STMT);
1530   stmt = gimple_build_assign (control_name, nit);
1531   gsi_insert_before (&gsi, stmt, GSI_NEW_STMT);
1532   SSA_NAME_DEF_STMT (control_name) = stmt;
1533 }
1534
1535 /* Create the parallel constructs for LOOP as described in gen_parallel_loop.
1536    LOOP_FN and DATA are the arguments of GIMPLE_OMP_PARALLEL.
1537    NEW_DATA is the variable that should be initialized from the argument
1538    of LOOP_FN.  N_THREADS is the requested number of threads.  Returns the
1539    basic block containing GIMPLE_OMP_PARALLEL tree.  */
1540
1541 static basic_block
1542 create_parallel_loop (struct loop *loop, tree loop_fn, tree data,
1543                       tree new_data, unsigned n_threads)
1544 {
1545   gimple_stmt_iterator gsi;
1546   basic_block bb, paral_bb, for_bb, ex_bb;
1547   tree t, param, res;
1548   gimple stmt, for_stmt, phi, cond_stmt;
1549   tree cvar, cvar_init, initvar, cvar_next, cvar_base, type;
1550   edge exit, nexit, guard, end, e;
1551
1552   /* Prepare the GIMPLE_OMP_PARALLEL statement.  */
1553   bb = loop_preheader_edge (loop)->src;
1554   paral_bb = single_pred (bb);
1555   gsi = gsi_last_bb (paral_bb);
1556
1557   t = build_omp_clause (OMP_CLAUSE_NUM_THREADS);
1558   OMP_CLAUSE_NUM_THREADS_EXPR (t)
1559     = build_int_cst (integer_type_node, n_threads);
1560   stmt = gimple_build_omp_parallel (NULL, t, loop_fn, data);
1561
1562   gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);
1563
1564   /* Initialize NEW_DATA.  */
1565   if (data)
1566     {
1567       gsi = gsi_after_labels (bb);
1568
1569       param = make_ssa_name (DECL_ARGUMENTS (loop_fn), NULL);
1570       stmt = gimple_build_assign (param, build_fold_addr_expr (data));
1571       gsi_insert_before (&gsi, stmt, GSI_SAME_STMT);
1572       SSA_NAME_DEF_STMT (param) = stmt;
1573
1574       stmt = gimple_build_assign (new_data,
1575                                   fold_convert (TREE_TYPE (new_data), param));
1576       gsi_insert_before (&gsi, stmt, GSI_SAME_STMT);
1577       SSA_NAME_DEF_STMT (new_data) = stmt;
1578     }
1579
1580   /* Emit GIMPLE_OMP_RETURN for GIMPLE_OMP_PARALLEL.  */
1581   bb = split_loop_exit_edge (single_dom_exit (loop));
1582   gsi = gsi_last_bb (bb);
1583   gsi_insert_after (&gsi, gimple_build_omp_return (false), GSI_NEW_STMT);
1584
1585   /* Extract data for GIMPLE_OMP_FOR.  */
1586   gcc_assert (loop->header == single_dom_exit (loop)->src);
1587   cond_stmt = last_stmt (loop->header);
1588
1589   cvar = gimple_cond_lhs (cond_stmt);
1590   cvar_base = SSA_NAME_VAR (cvar);
1591   phi = SSA_NAME_DEF_STMT (cvar);
1592   cvar_init = PHI_ARG_DEF_FROM_EDGE (phi, loop_preheader_edge (loop));
1593   initvar = make_ssa_name (cvar_base, NULL);
1594   SET_USE (PHI_ARG_DEF_PTR_FROM_EDGE (phi, loop_preheader_edge (loop)),
1595            initvar);
1596   cvar_next = PHI_ARG_DEF_FROM_EDGE (phi, loop_latch_edge (loop));
1597
1598   gsi = gsi_last_bb (loop->latch);
1599   gcc_assert (gsi_stmt (gsi) == SSA_NAME_DEF_STMT (cvar_next));
1600   gsi_remove (&gsi, true);
1601
1602   /* Prepare cfg.  */
1603   for_bb = split_edge (loop_preheader_edge (loop));
1604   ex_bb = split_loop_exit_edge (single_dom_exit (loop));
1605   extract_true_false_edges_from_block (loop->header, &nexit, &exit);
1606   gcc_assert (exit == single_dom_exit (loop));
1607
1608   guard = make_edge (for_bb, ex_bb, 0);
1609   single_succ_edge (loop->latch)->flags = 0;
1610   end = make_edge (loop->latch, ex_bb, EDGE_FALLTHRU);
1611   for (gsi = gsi_start_phis (ex_bb); !gsi_end_p (gsi); gsi_next (&gsi))
1612     {
1613       phi = gsi_stmt (gsi);
1614       res = PHI_RESULT (phi);
1615       stmt = SSA_NAME_DEF_STMT (PHI_ARG_DEF_FROM_EDGE (phi, exit));
1616       add_phi_arg (phi,
1617                    PHI_ARG_DEF_FROM_EDGE (stmt, loop_preheader_edge (loop)),
1618                    guard);
1619       add_phi_arg (phi, PHI_ARG_DEF_FROM_EDGE (stmt, loop_latch_edge (loop)),
1620                    end);
1621     }
1622   e = redirect_edge_and_branch (exit, nexit->dest);
1623   PENDING_STMT (e) = NULL;
1624
1625   /* Emit GIMPLE_OMP_FOR.  */
1626   gimple_cond_set_lhs (cond_stmt, cvar_base);
1627   type = TREE_TYPE (cvar);
1628   t = build_omp_clause (OMP_CLAUSE_SCHEDULE);
1629   OMP_CLAUSE_SCHEDULE_KIND (t) = OMP_CLAUSE_SCHEDULE_STATIC;
1630
1631   for_stmt = gimple_build_omp_for (NULL, t, 1, NULL);
1632   gimple_omp_for_set_index (for_stmt, 0, initvar);
1633   gimple_omp_for_set_initial (for_stmt, 0, cvar_init);
1634   gimple_omp_for_set_final (for_stmt, 0, gimple_cond_rhs (cond_stmt));
1635   gimple_omp_for_set_cond (for_stmt, 0, gimple_cond_code (cond_stmt));
1636   gimple_omp_for_set_incr (for_stmt, 0, build2 (PLUS_EXPR, type,
1637                                                 cvar_base,
1638                                                 build_int_cst (type, 1)));
1639
1640   gsi = gsi_last_bb (for_bb);
1641   gsi_insert_after (&gsi, for_stmt, GSI_NEW_STMT);
1642   SSA_NAME_DEF_STMT (initvar) = for_stmt;
1643
1644   /* Emit GIMPLE_OMP_CONTINUE.  */
1645   gsi = gsi_last_bb (loop->latch);
1646   stmt = gimple_build_omp_continue (cvar_next, cvar);
1647   gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);
1648   SSA_NAME_DEF_STMT (cvar_next) = stmt;
1649
1650   /* Emit GIMPLE_OMP_RETURN for GIMPLE_OMP_FOR.  */
1651   gsi = gsi_last_bb (ex_bb);
1652   gsi_insert_after (&gsi, gimple_build_omp_return (true), GSI_NEW_STMT);
1653
1654   return paral_bb;
1655 }
1656
1657 /* Generates code to execute the iterations of LOOP in N_THREADS threads in
1658    parallel.  NITER describes number of iterations of LOOP.  
1659    REDUCTION_LIST describes the reductions existent in the LOOP.  */
1660
1661 static void
1662 gen_parallel_loop (struct loop *loop, htab_t reduction_list, 
1663                    unsigned n_threads, struct tree_niter_desc *niter)
1664 {
1665   struct loop *nloop;
1666   loop_iterator li;
1667   tree many_iterations_cond, type, nit;
1668   tree arg_struct, new_arg_struct;
1669   gimple_seq stmts;
1670   basic_block parallel_head;
1671   edge entry, exit;
1672   struct clsn_data clsn_data;
1673   unsigned prob;
1674
1675   /* From
1676
1677      ---------------------------------------------------------------------
1678      loop
1679        {
1680          IV = phi (INIT, IV + STEP)
1681          BODY1;
1682          if (COND)
1683            break;
1684          BODY2;
1685        }
1686      ---------------------------------------------------------------------
1687
1688      with # of iterations NITER (possibly with MAY_BE_ZERO assumption),
1689      we generate the following code:
1690
1691      ---------------------------------------------------------------------
1692
1693      if (MAY_BE_ZERO
1694      || NITER < MIN_PER_THREAD * N_THREADS)
1695      goto original;
1696
1697      BODY1;
1698      store all local loop-invariant variables used in body of the loop to DATA.
1699      GIMPLE_OMP_PARALLEL (OMP_CLAUSE_NUM_THREADS (N_THREADS), LOOPFN, DATA);
1700      load the variables from DATA.
1701      GIMPLE_OMP_FOR (IV = INIT; COND; IV += STEP) (OMP_CLAUSE_SCHEDULE (static))
1702      BODY2;
1703      BODY1;
1704      GIMPLE_OMP_CONTINUE;
1705      GIMPLE_OMP_RETURN         -- GIMPLE_OMP_FOR
1706      GIMPLE_OMP_RETURN         -- GIMPLE_OMP_PARALLEL
1707      goto end;
1708
1709      original:
1710      loop
1711        {
1712          IV = phi (INIT, IV + STEP)
1713          BODY1;
1714          if (COND)
1715            break;
1716          BODY2;
1717        }
1718
1719      end:
1720
1721    */
1722
1723   /* Create two versions of the loop -- in the old one, we know that the
1724      number of iterations is large enough, and we will transform it into the
1725      loop that will be split to loop_fn, the new one will be used for the
1726      remaining iterations.  */
1727
1728   type = TREE_TYPE (niter->niter);
1729   nit = force_gimple_operand (unshare_expr (niter->niter), &stmts, true,
1730                               NULL_TREE);
1731   if (stmts)
1732     gsi_insert_seq_on_edge_immediate (loop_preheader_edge (loop), stmts);
1733
1734   many_iterations_cond =
1735     fold_build2 (GE_EXPR, boolean_type_node,
1736                  nit, build_int_cst (type, MIN_PER_THREAD * n_threads));
1737   many_iterations_cond
1738     = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
1739                    invert_truthvalue (unshare_expr (niter->may_be_zero)),
1740                    many_iterations_cond);
1741   many_iterations_cond
1742     = force_gimple_operand (many_iterations_cond, &stmts, false, NULL_TREE);
1743   if (stmts)
1744     gsi_insert_seq_on_edge_immediate (loop_preheader_edge (loop), stmts);
1745   if (!is_gimple_condexpr (many_iterations_cond))
1746     {
1747       many_iterations_cond
1748         = force_gimple_operand (many_iterations_cond, &stmts,
1749                                 true, NULL_TREE);
1750       if (stmts)
1751         gsi_insert_seq_on_edge_immediate (loop_preheader_edge (loop), stmts);
1752     }
1753
1754   initialize_original_copy_tables ();
1755
1756   /* We assume that the loop usually iterates a lot.  */
1757   prob = 4 * REG_BR_PROB_BASE / 5;
1758   nloop = loop_version (loop, many_iterations_cond, NULL,
1759                         prob, prob, REG_BR_PROB_BASE - prob, true);
1760   update_ssa (TODO_update_ssa);
1761   free_original_copy_tables ();
1762
1763   /* Base all the induction variables in LOOP on a single control one.  */
1764   canonicalize_loop_ivs (loop, reduction_list, nit);
1765
1766   /* Ensure that the exit condition is the first statement in the loop.  */
1767   transform_to_exit_first_loop (loop, reduction_list, nit);
1768
1769   /* Generate initializations for reductions.  */
1770   if (htab_elements (reduction_list) > 0)  
1771     htab_traverse (reduction_list, initialize_reductions, loop);
1772
1773   /* Eliminate the references to local variables from the loop.  */
1774   gcc_assert (single_exit (loop));
1775   entry = loop_preheader_edge (loop);
1776   exit = single_dom_exit (loop);
1777
1778   eliminate_local_variables (entry, exit);
1779   /* In the old loop, move all variables non-local to the loop to a structure
1780      and back, and create separate decls for the variables used in loop.  */
1781   separate_decls_in_region (entry, exit, reduction_list, &arg_struct, 
1782                             &new_arg_struct, &clsn_data);
1783
1784   /* Create the parallel constructs.  */
1785   parallel_head = create_parallel_loop (loop, create_loop_fn (), arg_struct,
1786                                         new_arg_struct, n_threads);
1787   if (htab_elements (reduction_list) > 0)   
1788     create_call_for_reduction (loop, reduction_list, &clsn_data);
1789
1790   scev_reset ();
1791
1792   /* Cancel the loop (it is simpler to do it here rather than to teach the
1793      expander to do it).  */
1794   cancel_loop_tree (loop);
1795
1796   /* Free loop bound estimations that could contain references to
1797      removed statements.  */
1798   FOR_EACH_LOOP (li, loop, 0)
1799     free_numbers_of_iterations_estimates_loop (loop);
1800
1801   /* Expand the parallel constructs.  We do it directly here instead of running
1802      a separate expand_omp pass, since it is more efficient, and less likely to
1803      cause troubles with further analyses not being able to deal with the
1804      OMP trees.  */
1805
1806   omp_expand_local (parallel_head);
1807 }
1808
1809 /* Returns true when LOOP contains vector phi nodes.  */
1810
1811 static bool
1812 loop_has_vector_phi_nodes (struct loop *loop ATTRIBUTE_UNUSED)
1813 {
1814   unsigned i;
1815   basic_block *bbs = get_loop_body_in_dom_order (loop);
1816   gimple_stmt_iterator gsi;
1817   bool res = true;
1818
1819   for (i = 0; i < loop->num_nodes; i++)
1820     for (gsi = gsi_start_phis (bbs[i]); !gsi_end_p (gsi); gsi_next (&gsi))
1821       if (TREE_CODE (TREE_TYPE (PHI_RESULT (gsi_stmt (gsi)))) == VECTOR_TYPE)
1822         goto end;
1823
1824   res = false;
1825  end:
1826   free (bbs);
1827   return res;
1828 }
1829
1830 /* Detect parallel loops and generate parallel code using libgomp
1831    primitives.  Returns true if some loop was parallelized, false
1832    otherwise.  */
1833
1834 bool
1835 parallelize_loops (void)
1836 {
1837   unsigned n_threads = flag_tree_parallelize_loops;
1838   bool changed = false;
1839   struct loop *loop;
1840   struct tree_niter_desc niter_desc;
1841   loop_iterator li;
1842   htab_t reduction_list;
1843
1844   /* Do not parallelize loops in the functions created by parallelization.  */
1845   if (parallelized_function_p (cfun->decl))
1846     return false;
1847
1848   reduction_list = htab_create (10, reduction_info_hash,
1849                                 reduction_info_eq, free);
1850   init_stmt_vec_info_vec ();
1851
1852   FOR_EACH_LOOP (li, loop, 0)
1853     {
1854       htab_empty (reduction_list);
1855       if (/* Do not bother with loops in cold areas.  */
1856           optimize_loop_nest_for_size_p (loop)
1857           /* Or loops that roll too little.  */
1858           || expected_loop_iterations (loop) <= n_threads
1859           /* And of course, the loop must be parallelizable.  */
1860           || !can_duplicate_loop_p (loop)
1861           || loop_has_blocks_with_irreducible_flag (loop)
1862           /* FIXME: the check for vector phi nodes could be removed.  */
1863           || loop_has_vector_phi_nodes (loop)
1864           || !loop_parallel_p (loop, reduction_list, &niter_desc))
1865         continue;
1866
1867       changed = true;
1868       gen_parallel_loop (loop, reduction_list, n_threads, &niter_desc);
1869       verify_flow_info ();
1870       verify_dominators (CDI_DOMINATORS);
1871       verify_loop_structure ();
1872       verify_loop_closed_ssa ();
1873     }
1874
1875   free_stmt_vec_info_vec ();
1876   htab_delete (reduction_list);
1877   return changed;
1878 }
1879
1880 #include "gt-tree-parloops.h"