OSDN Git Service

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