annotate gcc/graphite-scop-detection.c @ 16:04ced10e8804

gcc 7
author kono
date Fri, 27 Oct 2017 22:46:09 +0900
parents f6334be47118
children 84e7813d76e9
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
</
rev   line source
9
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
1 /* Detection of Static Control Parts (SCoP) for Graphite.
16
kono
parents: 14
diff changeset
2 Copyright (C) 2009-2017 Free Software Foundation, Inc.
9
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
3 Contributed by Sebastian Pop <sebastian.pop@amd.com> and
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
4 Tobias Grosser <grosser@fim.uni-passau.de>.
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
5
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
6 This file is part of GCC.
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
7
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
8 GCC is free software; you can redistribute it and/or modify
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
9 it under the terms of the GNU General Public License as published by
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
10 the Free Software Foundation; either version 3, or (at your option)
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
11 any later version.
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
12
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
13 GCC is distributed in the hope that it will be useful,
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
14 but WITHOUT ANY WARRANTY; without even the implied warranty of
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
16 GNU General Public License for more details.
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
17
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
18 You should have received a copy of the GNU General Public License
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
19 along with GCC; see the file COPYING3. If not see
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
20 <http://www.gnu.org/licenses/>. */
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
21
16
kono
parents: 14
diff changeset
22 #define USES_ISL
kono
parents: 14
diff changeset
23
9
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
24 #include "config.h"
16
kono
parents: 14
diff changeset
25
kono
parents: 14
diff changeset
26 #ifdef HAVE_isl
kono
parents: 14
diff changeset
27
9
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
28 #include "system.h"
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
29 #include "coretypes.h"
16
kono
parents: 14
diff changeset
30 #include "backend.h"
kono
parents: 14
diff changeset
31 #include "cfghooks.h"
kono
parents: 14
diff changeset
32 #include "domwalk.h"
kono
parents: 14
diff changeset
33 #include "params.h"
kono
parents: 14
diff changeset
34 #include "tree.h"
kono
parents: 14
diff changeset
35 #include "gimple.h"
kono
parents: 14
diff changeset
36 #include "ssa.h"
kono
parents: 14
diff changeset
37 #include "fold-const.h"
kono
parents: 14
diff changeset
38 #include "gimple-iterator.h"
kono
parents: 14
diff changeset
39 #include "tree-cfg.h"
kono
parents: 14
diff changeset
40 #include "tree-ssa-loop-manip.h"
kono
parents: 14
diff changeset
41 #include "tree-ssa-loop-niter.h"
kono
parents: 14
diff changeset
42 #include "tree-ssa-loop.h"
kono
parents: 14
diff changeset
43 #include "tree-into-ssa.h"
kono
parents: 14
diff changeset
44 #include "tree-ssa.h"
9
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
45 #include "cfgloop.h"
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
46 #include "tree-data-ref.h"
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
47 #include "tree-scalar-evolution.h"
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
48 #include "tree-pass.h"
16
kono
parents: 14
diff changeset
49 #include "tree-ssa-propagate.h"
kono
parents: 14
diff changeset
50 #include "gimple-pretty-print.h"
kono
parents: 14
diff changeset
51 #include "cfganal.h"
kono
parents: 14
diff changeset
52 #include "graphite.h"
9
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
53
16
kono
parents: 14
diff changeset
54 class debug_printer
9
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
55 {
16
kono
parents: 14
diff changeset
56 private:
kono
parents: 14
diff changeset
57 FILE *dump_file;
9
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
58
16
kono
parents: 14
diff changeset
59 public:
kono
parents: 14
diff changeset
60 void
kono
parents: 14
diff changeset
61 set_dump_file (FILE *f)
kono
parents: 14
diff changeset
62 {
kono
parents: 14
diff changeset
63 gcc_assert (f);
kono
parents: 14
diff changeset
64 dump_file = f;
kono
parents: 14
diff changeset
65 }
9
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
66
16
kono
parents: 14
diff changeset
67 friend debug_printer &
kono
parents: 14
diff changeset
68 operator<< (debug_printer &output, int i)
kono
parents: 14
diff changeset
69 {
kono
parents: 14
diff changeset
70 fprintf (output.dump_file, "%d", i);
kono
parents: 14
diff changeset
71 return output;
kono
parents: 14
diff changeset
72 }
kono
parents: 14
diff changeset
73 friend debug_printer &
kono
parents: 14
diff changeset
74 operator<< (debug_printer &output, const char *s)
kono
parents: 14
diff changeset
75 {
kono
parents: 14
diff changeset
76 fprintf (output.dump_file, "%s", s);
kono
parents: 14
diff changeset
77 return output;
kono
parents: 14
diff changeset
78 }
kono
parents: 14
diff changeset
79 } dp;
14
f6334be47118 update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
80
16
kono
parents: 14
diff changeset
81 #define DEBUG_PRINT(args) do \
kono
parents: 14
diff changeset
82 { \
kono
parents: 14
diff changeset
83 if (dump_file && (dump_flags & TDF_DETAILS)) { args; } \
kono
parents: 14
diff changeset
84 } while (0);
9
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
85
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
86 /* Pretty print to FILE all the SCoPs in DOT format and mark them with
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
87 different colors. If there are not enough colors, paint the
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
88 remaining SCoPs in gray.
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
89
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
90 Special nodes:
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
91 - "*" after the node number denotes the entry of a SCoP,
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
92 - "#" after the node number denotes the exit of a SCoP,
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
93 - "()" around the node number denotes the entry or the
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
94 exit nodes of the SCOP. These are not part of SCoP. */
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
95
16
kono
parents: 14
diff changeset
96 DEBUG_FUNCTION void
kono
parents: 14
diff changeset
97 dot_all_sese (FILE *file, vec<sese_l>& scops)
9
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
98 {
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
99 /* Disable debugging while printing graph. */
16
kono
parents: 14
diff changeset
100 dump_flags_t tmp_dump_flags = dump_flags;
kono
parents: 14
diff changeset
101 dump_flags = TDF_NONE;
9
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
102
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
103 fprintf (file, "digraph all {\n");
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
104
16
kono
parents: 14
diff changeset
105 basic_block bb;
kono
parents: 14
diff changeset
106 FOR_ALL_BB_FN (bb, cfun)
9
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
107 {
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
108 int part_of_scop = false;
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
109
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
110 /* Use HTML for every bb label. So we are able to print bbs
16
kono
parents: 14
diff changeset
111 which are part of two different SCoPs, with two different
kono
parents: 14
diff changeset
112 background colors. */
9
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
113 fprintf (file, "%d [label=<\n <TABLE BORDER=\"0\" CELLBORDER=\"1\" ",
16
kono
parents: 14
diff changeset
114 bb->index);
9
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
115 fprintf (file, "CELLSPACING=\"0\">\n");
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
116
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
117 /* Select color for SCoP. */
16
kono
parents: 14
diff changeset
118 sese_l *region;
kono
parents: 14
diff changeset
119 int i;
kono
parents: 14
diff changeset
120 FOR_EACH_VEC_ELT (scops, i, region)
9
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
121 {
16
kono
parents: 14
diff changeset
122 bool sese_in_region = bb_in_sese_p (bb, *region);
kono
parents: 14
diff changeset
123 if (sese_in_region || (region->exit->dest == bb)
kono
parents: 14
diff changeset
124 || (region->entry->dest == bb))
9
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
125 {
16
kono
parents: 14
diff changeset
126 const char *color;
9
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
127 switch (i % 17)
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
128 {
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
129 case 0: /* red */
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
130 color = "#e41a1c";
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
131 break;
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
132 case 1: /* blue */
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
133 color = "#377eb8";
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
134 break;
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
135 case 2: /* green */
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
136 color = "#4daf4a";
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
137 break;
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
138 case 3: /* purple */
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
139 color = "#984ea3";
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
140 break;
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
141 case 4: /* orange */
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
142 color = "#ff7f00";
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
143 break;
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
144 case 5: /* yellow */
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
145 color = "#ffff33";
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
146 break;
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
147 case 6: /* brown */
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
148 color = "#a65628";
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
149 break;
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
150 case 7: /* rose */
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
151 color = "#f781bf";
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
152 break;
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
153 case 8:
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
154 color = "#8dd3c7";
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
155 break;
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
156 case 9:
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
157 color = "#ffffb3";
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
158 break;
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
159 case 10:
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
160 color = "#bebada";
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
161 break;
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
162 case 11:
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
163 color = "#fb8072";
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
164 break;
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
165 case 12:
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
166 color = "#80b1d3";
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
167 break;
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
168 case 13:
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
169 color = "#fdb462";
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
170 break;
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
171 case 14:
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
172 color = "#b3de69";
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
173 break;
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
174 case 15:
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
175 color = "#fccde5";
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
176 break;
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
177 case 16:
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
178 color = "#bc80bd";
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
179 break;
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
180 default: /* gray */
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
181 color = "#999999";
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
182 }
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
183
16
kono
parents: 14
diff changeset
184 fprintf (file, " <TR><TD WIDTH=\"50\" BGCOLOR=\"%s\">",
kono
parents: 14
diff changeset
185 color);
9
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
186
16
kono
parents: 14
diff changeset
187 if (!sese_in_region)
9
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
188 fprintf (file, " (");
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
189
16
kono
parents: 14
diff changeset
190 if (bb == region->entry->dest && bb == region->exit->dest)
9
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
191 fprintf (file, " %d*# ", bb->index);
16
kono
parents: 14
diff changeset
192 else if (bb == region->entry->dest)
9
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
193 fprintf (file, " %d* ", bb->index);
16
kono
parents: 14
diff changeset
194 else if (bb == region->exit->dest)
9
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
195 fprintf (file, " %d# ", bb->index);
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
196 else
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
197 fprintf (file, " %d ", bb->index);
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
198
16
kono
parents: 14
diff changeset
199 fprintf (file, "{lp_%d}", bb->loop_father->num);
kono
parents: 14
diff changeset
200
kono
parents: 14
diff changeset
201 if (!sese_in_region)
9
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
202 fprintf (file, ")");
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
203
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
204 fprintf (file, "</TD></TR>\n");
16
kono
parents: 14
diff changeset
205 part_of_scop = true;
9
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
206 }
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
207 }
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
208
16
kono
parents: 14
diff changeset
209 if (!part_of_scop)
kono
parents: 14
diff changeset
210 {
kono
parents: 14
diff changeset
211 fprintf (file, " <TR><TD WIDTH=\"50\" BGCOLOR=\"#ffffff\">");
kono
parents: 14
diff changeset
212 fprintf (file, " %d {lp_%d} </TD></TR>\n", bb->index,
kono
parents: 14
diff changeset
213 bb->loop_father->num);
kono
parents: 14
diff changeset
214 }
kono
parents: 14
diff changeset
215 fprintf (file, " </TABLE>>, shape=box, style=\"setlinewidth(0)\"]\n");
9
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
216 }
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
217
16
kono
parents: 14
diff changeset
218 FOR_ALL_BB_FN (bb, cfun)
kono
parents: 14
diff changeset
219 {
kono
parents: 14
diff changeset
220 edge e;
kono
parents: 14
diff changeset
221 edge_iterator ei;
kono
parents: 14
diff changeset
222 FOR_EACH_EDGE (e, ei, bb->succs)
kono
parents: 14
diff changeset
223 fprintf (file, "%d -> %d;\n", bb->index, e->dest->index);
kono
parents: 14
diff changeset
224 }
9
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
225
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
226 fputs ("}\n\n", file);
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
227
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
228 /* Enable debugging again. */
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
229 dump_flags = tmp_dump_flags;
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
230 }
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
231
16
kono
parents: 14
diff changeset
232 /* Display SCoP on stderr. */
9
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
233
14
f6334be47118 update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
234 DEBUG_FUNCTION void
16
kono
parents: 14
diff changeset
235 dot_sese (sese_l& scop)
9
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
236 {
16
kono
parents: 14
diff changeset
237 vec<sese_l> scops;
kono
parents: 14
diff changeset
238 scops.create (1);
9
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
239
16
kono
parents: 14
diff changeset
240 if (scop)
kono
parents: 14
diff changeset
241 scops.safe_push (scop);
9
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
242
16
kono
parents: 14
diff changeset
243 dot_all_sese (stderr, scops);
kono
parents: 14
diff changeset
244
kono
parents: 14
diff changeset
245 scops.release ();
9
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
246 }
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
247
14
f6334be47118 update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
248 DEBUG_FUNCTION void
16
kono
parents: 14
diff changeset
249 dot_cfg ()
9
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
250 {
16
kono
parents: 14
diff changeset
251 vec<sese_l> scops;
kono
parents: 14
diff changeset
252 scops.create (1);
kono
parents: 14
diff changeset
253 dot_all_sese (stderr, scops);
kono
parents: 14
diff changeset
254 scops.release ();
kono
parents: 14
diff changeset
255 }
kono
parents: 14
diff changeset
256
kono
parents: 14
diff changeset
257 /* Returns a COND_EXPR statement when BB has a single predecessor, the
kono
parents: 14
diff changeset
258 edge between BB and its predecessor is not a loop exit edge, and
kono
parents: 14
diff changeset
259 the last statement of the single predecessor is a COND_EXPR. */
kono
parents: 14
diff changeset
260
kono
parents: 14
diff changeset
261 static gcond *
kono
parents: 14
diff changeset
262 single_pred_cond_non_loop_exit (basic_block bb)
kono
parents: 14
diff changeset
263 {
kono
parents: 14
diff changeset
264 if (single_pred_p (bb))
kono
parents: 14
diff changeset
265 {
kono
parents: 14
diff changeset
266 edge e = single_pred_edge (bb);
kono
parents: 14
diff changeset
267 basic_block pred = e->src;
kono
parents: 14
diff changeset
268 gimple *stmt;
kono
parents: 14
diff changeset
269
kono
parents: 14
diff changeset
270 if (loop_depth (pred->loop_father) > loop_depth (bb->loop_father))
kono
parents: 14
diff changeset
271 return NULL;
kono
parents: 14
diff changeset
272
kono
parents: 14
diff changeset
273 stmt = last_stmt (pred);
9
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
274
16
kono
parents: 14
diff changeset
275 if (stmt && gimple_code (stmt) == GIMPLE_COND)
kono
parents: 14
diff changeset
276 return as_a<gcond *> (stmt);
kono
parents: 14
diff changeset
277 }
kono
parents: 14
diff changeset
278
kono
parents: 14
diff changeset
279 return NULL;
kono
parents: 14
diff changeset
280 }
kono
parents: 14
diff changeset
281
kono
parents: 14
diff changeset
282 namespace
kono
parents: 14
diff changeset
283 {
kono
parents: 14
diff changeset
284
kono
parents: 14
diff changeset
285 /* Build the maximal scop containing LOOPs and add it to SCOPS. */
9
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
286
16
kono
parents: 14
diff changeset
287 class scop_detection
kono
parents: 14
diff changeset
288 {
kono
parents: 14
diff changeset
289 public:
kono
parents: 14
diff changeset
290 scop_detection () : scops (vNULL) {}
kono
parents: 14
diff changeset
291
kono
parents: 14
diff changeset
292 ~scop_detection ()
kono
parents: 14
diff changeset
293 {
kono
parents: 14
diff changeset
294 scops.release ();
kono
parents: 14
diff changeset
295 }
kono
parents: 14
diff changeset
296
kono
parents: 14
diff changeset
297 /* A marker for invalid sese_l. */
kono
parents: 14
diff changeset
298 static sese_l invalid_sese;
kono
parents: 14
diff changeset
299
kono
parents: 14
diff changeset
300 /* Return the SCOPS in this SCOP_DETECTION. */
kono
parents: 14
diff changeset
301
kono
parents: 14
diff changeset
302 vec<sese_l>
kono
parents: 14
diff changeset
303 get_scops ()
9
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
304 {
16
kono
parents: 14
diff changeset
305 return scops;
kono
parents: 14
diff changeset
306 }
kono
parents: 14
diff changeset
307
kono
parents: 14
diff changeset
308 /* Return an sese_l around the LOOP. */
kono
parents: 14
diff changeset
309
kono
parents: 14
diff changeset
310 sese_l get_sese (loop_p loop);
kono
parents: 14
diff changeset
311
kono
parents: 14
diff changeset
312 /* Return the closest dominator with a single entry edge. In case of a
kono
parents: 14
diff changeset
313 back-loop the back-edge is not counted. */
kono
parents: 14
diff changeset
314
kono
parents: 14
diff changeset
315 static edge get_nearest_dom_with_single_entry (basic_block dom);
kono
parents: 14
diff changeset
316
kono
parents: 14
diff changeset
317 /* Return the closest post-dominator with a single exit edge. In case of a
kono
parents: 14
diff changeset
318 back-loop the back-edge is not counted. */
kono
parents: 14
diff changeset
319
kono
parents: 14
diff changeset
320 static edge get_nearest_pdom_with_single_exit (basic_block dom);
kono
parents: 14
diff changeset
321
kono
parents: 14
diff changeset
322 /* Merge scops at same loop depth and returns the new sese.
kono
parents: 14
diff changeset
323 Returns a new SESE when merge was successful, INVALID_SESE otherwise. */
kono
parents: 14
diff changeset
324
kono
parents: 14
diff changeset
325 sese_l merge_sese (sese_l first, sese_l second) const;
kono
parents: 14
diff changeset
326
kono
parents: 14
diff changeset
327 /* Build scop outer->inner if possible. */
kono
parents: 14
diff changeset
328
kono
parents: 14
diff changeset
329 void build_scop_depth (loop_p loop);
kono
parents: 14
diff changeset
330
kono
parents: 14
diff changeset
331 /* Return true when BEGIN is the preheader edge of a loop with a single exit
kono
parents: 14
diff changeset
332 END. */
kono
parents: 14
diff changeset
333
kono
parents: 14
diff changeset
334 static bool region_has_one_loop (sese_l s);
kono
parents: 14
diff changeset
335
kono
parents: 14
diff changeset
336 /* Add to SCOPS a scop starting at SCOP_BEGIN and ending at SCOP_END. */
kono
parents: 14
diff changeset
337
kono
parents: 14
diff changeset
338 void add_scop (sese_l s);
kono
parents: 14
diff changeset
339
kono
parents: 14
diff changeset
340 /* Returns true if S1 subsumes/surrounds S2. */
kono
parents: 14
diff changeset
341 static bool subsumes (sese_l s1, sese_l s2);
kono
parents: 14
diff changeset
342
kono
parents: 14
diff changeset
343 /* Remove a SCoP which is subsumed by S1. */
kono
parents: 14
diff changeset
344 void remove_subscops (sese_l s1);
kono
parents: 14
diff changeset
345
kono
parents: 14
diff changeset
346 /* Returns true if S1 intersects with S2. Since we already know that S1 does
kono
parents: 14
diff changeset
347 not subsume S2 or vice-versa, we only check for entry bbs. */
kono
parents: 14
diff changeset
348
kono
parents: 14
diff changeset
349 static bool intersects (sese_l s1, sese_l s2);
kono
parents: 14
diff changeset
350
kono
parents: 14
diff changeset
351 /* Remove one of the scops when it intersects with any other. */
kono
parents: 14
diff changeset
352
kono
parents: 14
diff changeset
353 void remove_intersecting_scops (sese_l s1);
kono
parents: 14
diff changeset
354
kono
parents: 14
diff changeset
355 /* Return true when a statement in SCOP cannot be represented by Graphite. */
kono
parents: 14
diff changeset
356
kono
parents: 14
diff changeset
357 bool harmful_loop_in_region (sese_l scop) const;
kono
parents: 14
diff changeset
358
kono
parents: 14
diff changeset
359 /* Return true only when STMT is simple enough for being handled by Graphite.
kono
parents: 14
diff changeset
360 This depends on SCOP, as the parameters are initialized relatively to
kono
parents: 14
diff changeset
361 this basic block, the linear functions are initialized based on the
kono
parents: 14
diff changeset
362 outermost loop containing STMT inside the SCOP. BB is the place where we
kono
parents: 14
diff changeset
363 try to evaluate the STMT. */
kono
parents: 14
diff changeset
364
kono
parents: 14
diff changeset
365 bool stmt_simple_for_scop_p (sese_l scop, gimple *stmt,
kono
parents: 14
diff changeset
366 basic_block bb) const;
kono
parents: 14
diff changeset
367
kono
parents: 14
diff changeset
368 /* Something like "n * m" is not allowed. */
kono
parents: 14
diff changeset
369
kono
parents: 14
diff changeset
370 static bool graphite_can_represent_init (tree e);
kono
parents: 14
diff changeset
371
kono
parents: 14
diff changeset
372 /* Return true when SCEV can be represented in the polyhedral model.
kono
parents: 14
diff changeset
373
kono
parents: 14
diff changeset
374 An expression can be represented, if it can be expressed as an
kono
parents: 14
diff changeset
375 affine expression. For loops (i, j) and parameters (m, n) all
kono
parents: 14
diff changeset
376 affine expressions are of the form:
kono
parents: 14
diff changeset
377
kono
parents: 14
diff changeset
378 x1 * i + x2 * j + x3 * m + x4 * n + x5 * 1 where x1..x5 element of Z
kono
parents: 14
diff changeset
379
kono
parents: 14
diff changeset
380 1 i + 20 j + (-2) m + 25
kono
parents: 14
diff changeset
381
kono
parents: 14
diff changeset
382 Something like "i * n" or "n * m" is not allowed. */
kono
parents: 14
diff changeset
383
kono
parents: 14
diff changeset
384 static bool graphite_can_represent_scev (sese_l scop, tree scev);
kono
parents: 14
diff changeset
385
kono
parents: 14
diff changeset
386 /* Return true when EXPR can be represented in the polyhedral model.
kono
parents: 14
diff changeset
387
kono
parents: 14
diff changeset
388 This means an expression can be represented, if it is linear with respect
kono
parents: 14
diff changeset
389 to the loops and the strides are non parametric. LOOP is the place where
kono
parents: 14
diff changeset
390 the expr will be evaluated. SCOP defines the region we analyse. */
kono
parents: 14
diff changeset
391
kono
parents: 14
diff changeset
392 static bool graphite_can_represent_expr (sese_l scop, loop_p loop,
kono
parents: 14
diff changeset
393 tree expr);
kono
parents: 14
diff changeset
394
kono
parents: 14
diff changeset
395 /* Return true if the data references of STMT can be represented by Graphite.
kono
parents: 14
diff changeset
396 We try to analyze the data references in a loop contained in the SCOP. */
kono
parents: 14
diff changeset
397
kono
parents: 14
diff changeset
398 static bool stmt_has_simple_data_refs_p (sese_l scop, gimple *stmt);
kono
parents: 14
diff changeset
399
kono
parents: 14
diff changeset
400 /* Remove the close phi node at GSI and replace its rhs with the rhs
kono
parents: 14
diff changeset
401 of PHI. */
kono
parents: 14
diff changeset
402
kono
parents: 14
diff changeset
403 static void remove_duplicate_close_phi (gphi *phi, gphi_iterator *gsi);
kono
parents: 14
diff changeset
404
kono
parents: 14
diff changeset
405 /* Returns true when Graphite can represent LOOP in SCOP.
kono
parents: 14
diff changeset
406 FIXME: For the moment, graphite cannot be used on loops that iterate using
kono
parents: 14
diff changeset
407 induction variables that wrap. */
kono
parents: 14
diff changeset
408
kono
parents: 14
diff changeset
409 static bool can_represent_loop (loop_p loop, sese_l scop);
kono
parents: 14
diff changeset
410
kono
parents: 14
diff changeset
411 /* Returns the number of pbbs that are in loops contained in SCOP. */
kono
parents: 14
diff changeset
412
kono
parents: 14
diff changeset
413 static int nb_pbbs_in_loops (scop_p scop);
kono
parents: 14
diff changeset
414
kono
parents: 14
diff changeset
415 private:
kono
parents: 14
diff changeset
416 vec<sese_l> scops;
kono
parents: 14
diff changeset
417 };
kono
parents: 14
diff changeset
418
kono
parents: 14
diff changeset
419 sese_l scop_detection::invalid_sese (NULL, NULL);
kono
parents: 14
diff changeset
420
kono
parents: 14
diff changeset
421 /* Return an sese_l around the LOOP. */
kono
parents: 14
diff changeset
422
kono
parents: 14
diff changeset
423 sese_l
kono
parents: 14
diff changeset
424 scop_detection::get_sese (loop_p loop)
kono
parents: 14
diff changeset
425 {
kono
parents: 14
diff changeset
426 if (!loop)
kono
parents: 14
diff changeset
427 return invalid_sese;
kono
parents: 14
diff changeset
428
kono
parents: 14
diff changeset
429 edge scop_begin = loop_preheader_edge (loop);
kono
parents: 14
diff changeset
430 edge scop_end = single_exit (loop);
kono
parents: 14
diff changeset
431 if (!scop_end || (scop_end->flags & EDGE_COMPLEX))
kono
parents: 14
diff changeset
432 return invalid_sese;
kono
parents: 14
diff changeset
433 /* Include the BB with the loop-closed SSA PHI nodes.
kono
parents: 14
diff changeset
434 canonicalize_loop_closed_ssa makes sure that is in proper shape. */
kono
parents: 14
diff changeset
435 if (! single_pred_p (scop_end->dest)
kono
parents: 14
diff changeset
436 || ! single_succ_p (scop_end->dest)
kono
parents: 14
diff changeset
437 || ! sese_trivially_empty_bb_p (scop_end->dest))
kono
parents: 14
diff changeset
438 gcc_unreachable ();
kono
parents: 14
diff changeset
439 scop_end = single_succ_edge (scop_end->dest);
kono
parents: 14
diff changeset
440
kono
parents: 14
diff changeset
441 return sese_l (scop_begin, scop_end);
kono
parents: 14
diff changeset
442 }
kono
parents: 14
diff changeset
443
kono
parents: 14
diff changeset
444 /* Return the closest dominator with a single entry edge. */
kono
parents: 14
diff changeset
445
kono
parents: 14
diff changeset
446 edge
kono
parents: 14
diff changeset
447 scop_detection::get_nearest_dom_with_single_entry (basic_block dom)
kono
parents: 14
diff changeset
448 {
kono
parents: 14
diff changeset
449 if (!dom->preds)
kono
parents: 14
diff changeset
450 return NULL;
kono
parents: 14
diff changeset
451
kono
parents: 14
diff changeset
452 /* If any of the dominators has two predecessors but one of them is a back
kono
parents: 14
diff changeset
453 edge, then that basic block also qualifies as a dominator with single
kono
parents: 14
diff changeset
454 entry. */
kono
parents: 14
diff changeset
455 if (dom->preds->length () == 2)
kono
parents: 14
diff changeset
456 {
kono
parents: 14
diff changeset
457 /* If e1->src dominates e2->src then e1->src will also dominate dom. */
kono
parents: 14
diff changeset
458 edge e1 = (*dom->preds)[0];
kono
parents: 14
diff changeset
459 edge e2 = (*dom->preds)[1];
kono
parents: 14
diff changeset
460 loop_p l = dom->loop_father;
kono
parents: 14
diff changeset
461 loop_p l1 = e1->src->loop_father;
kono
parents: 14
diff changeset
462 loop_p l2 = e2->src->loop_father;
kono
parents: 14
diff changeset
463 if (l != l1 && l == l2
kono
parents: 14
diff changeset
464 && dominated_by_p (CDI_DOMINATORS, e2->src, e1->src))
kono
parents: 14
diff changeset
465 return e1;
kono
parents: 14
diff changeset
466 if (l != l2 && l == l1
kono
parents: 14
diff changeset
467 && dominated_by_p (CDI_DOMINATORS, e1->src, e2->src))
kono
parents: 14
diff changeset
468 return e2;
kono
parents: 14
diff changeset
469 }
kono
parents: 14
diff changeset
470
kono
parents: 14
diff changeset
471 while (dom->preds->length () != 1)
kono
parents: 14
diff changeset
472 {
kono
parents: 14
diff changeset
473 if (dom->preds->length () < 1)
kono
parents: 14
diff changeset
474 return NULL;
kono
parents: 14
diff changeset
475 dom = get_immediate_dominator (CDI_DOMINATORS, dom);
kono
parents: 14
diff changeset
476 if (!dom->preds)
kono
parents: 14
diff changeset
477 return NULL;
kono
parents: 14
diff changeset
478 }
kono
parents: 14
diff changeset
479 return (*dom->preds)[0];
kono
parents: 14
diff changeset
480 }
kono
parents: 14
diff changeset
481
kono
parents: 14
diff changeset
482 /* Return the closest post-dominator with a single exit edge. In case of a
kono
parents: 14
diff changeset
483 back-loop the back-edge is not counted. */
kono
parents: 14
diff changeset
484
kono
parents: 14
diff changeset
485 edge
kono
parents: 14
diff changeset
486 scop_detection::get_nearest_pdom_with_single_exit (basic_block pdom)
kono
parents: 14
diff changeset
487 {
kono
parents: 14
diff changeset
488 if (!pdom->succs)
kono
parents: 14
diff changeset
489 return NULL;
kono
parents: 14
diff changeset
490
kono
parents: 14
diff changeset
491 /* If any of the post-dominators has two successors but one of them is a back
kono
parents: 14
diff changeset
492 edge, then that basic block also qualifies as a post-dominator with single
kono
parents: 14
diff changeset
493 exit. */
kono
parents: 14
diff changeset
494 if (pdom->succs->length () == 2)
kono
parents: 14
diff changeset
495 {
kono
parents: 14
diff changeset
496 /* If e1->dest post-dominates e2->dest then e1->dest will also
kono
parents: 14
diff changeset
497 post-dominate pdom. */
kono
parents: 14
diff changeset
498 edge e1 = (*pdom->succs)[0];
kono
parents: 14
diff changeset
499 edge e2 = (*pdom->succs)[1];
kono
parents: 14
diff changeset
500 loop_p l = pdom->loop_father;
kono
parents: 14
diff changeset
501 loop_p l1 = e1->dest->loop_father;
kono
parents: 14
diff changeset
502 loop_p l2 = e2->dest->loop_father;
kono
parents: 14
diff changeset
503 if (l != l1 && l == l2
kono
parents: 14
diff changeset
504 && dominated_by_p (CDI_POST_DOMINATORS, e2->dest, e1->dest))
kono
parents: 14
diff changeset
505 return e1;
kono
parents: 14
diff changeset
506 if (l != l2 && l == l1
kono
parents: 14
diff changeset
507 && dominated_by_p (CDI_POST_DOMINATORS, e1->dest, e2->dest))
kono
parents: 14
diff changeset
508 return e2;
kono
parents: 14
diff changeset
509 }
kono
parents: 14
diff changeset
510
kono
parents: 14
diff changeset
511 while (pdom->succs->length () != 1)
kono
parents: 14
diff changeset
512 {
kono
parents: 14
diff changeset
513 if (pdom->succs->length () < 1)
kono
parents: 14
diff changeset
514 return NULL;
kono
parents: 14
diff changeset
515 pdom = get_immediate_dominator (CDI_POST_DOMINATORS, pdom);
kono
parents: 14
diff changeset
516 if (!pdom->succs)
kono
parents: 14
diff changeset
517 return NULL;
kono
parents: 14
diff changeset
518 }
kono
parents: 14
diff changeset
519
kono
parents: 14
diff changeset
520 return (*pdom->succs)[0];
kono
parents: 14
diff changeset
521 }
kono
parents: 14
diff changeset
522
kono
parents: 14
diff changeset
523 /* Merge scops at same loop depth and returns the new sese.
kono
parents: 14
diff changeset
524 Returns a new SESE when merge was successful, INVALID_SESE otherwise. */
kono
parents: 14
diff changeset
525
kono
parents: 14
diff changeset
526 sese_l
kono
parents: 14
diff changeset
527 scop_detection::merge_sese (sese_l first, sese_l second) const
kono
parents: 14
diff changeset
528 {
kono
parents: 14
diff changeset
529 /* In the trivial case first/second may be NULL. */
kono
parents: 14
diff changeset
530 if (!first)
kono
parents: 14
diff changeset
531 return second;
kono
parents: 14
diff changeset
532 if (!second)
kono
parents: 14
diff changeset
533 return first;
kono
parents: 14
diff changeset
534
kono
parents: 14
diff changeset
535 DEBUG_PRINT (dp << "[scop-detection] try merging sese s1: ";
kono
parents: 14
diff changeset
536 print_sese (dump_file, first);
kono
parents: 14
diff changeset
537 dp << "[scop-detection] try merging sese s2: ";
kono
parents: 14
diff changeset
538 print_sese (dump_file, second));
kono
parents: 14
diff changeset
539
kono
parents: 14
diff changeset
540 /* Assumption: Both the sese's should be at the same loop depth or one scop
kono
parents: 14
diff changeset
541 should subsume the other like in case of nested loops. */
kono
parents: 14
diff changeset
542
kono
parents: 14
diff changeset
543 /* Find the common dominators for entry,
kono
parents: 14
diff changeset
544 and common post-dominators for the exit. */
kono
parents: 14
diff changeset
545 basic_block dom = nearest_common_dominator (CDI_DOMINATORS,
kono
parents: 14
diff changeset
546 get_entry_bb (first),
kono
parents: 14
diff changeset
547 get_entry_bb (second));
kono
parents: 14
diff changeset
548
kono
parents: 14
diff changeset
549 edge entry = get_nearest_dom_with_single_entry (dom);
kono
parents: 14
diff changeset
550
kono
parents: 14
diff changeset
551 if (!entry || (entry->flags & EDGE_IRREDUCIBLE_LOOP))
kono
parents: 14
diff changeset
552 return invalid_sese;
kono
parents: 14
diff changeset
553
kono
parents: 14
diff changeset
554 basic_block pdom = nearest_common_dominator (CDI_POST_DOMINATORS,
kono
parents: 14
diff changeset
555 get_exit_bb (first),
kono
parents: 14
diff changeset
556 get_exit_bb (second));
kono
parents: 14
diff changeset
557 pdom = nearest_common_dominator (CDI_POST_DOMINATORS, dom, pdom);
kono
parents: 14
diff changeset
558
kono
parents: 14
diff changeset
559 edge exit = get_nearest_pdom_with_single_exit (pdom);
kono
parents: 14
diff changeset
560
kono
parents: 14
diff changeset
561 if (!exit || (exit->flags & EDGE_IRREDUCIBLE_LOOP))
kono
parents: 14
diff changeset
562 return invalid_sese;
kono
parents: 14
diff changeset
563
kono
parents: 14
diff changeset
564 sese_l combined (entry, exit);
kono
parents: 14
diff changeset
565
kono
parents: 14
diff changeset
566 DEBUG_PRINT (dp << "[scop-detection] checking combined sese: ";
kono
parents: 14
diff changeset
567 print_sese (dump_file, combined));
kono
parents: 14
diff changeset
568
kono
parents: 14
diff changeset
569 /* FIXME: We could iterate to find the dom which dominates pdom, and pdom
kono
parents: 14
diff changeset
570 which post-dominates dom, until it stabilizes. Also, ENTRY->SRC and
kono
parents: 14
diff changeset
571 EXIT->DEST should be in the same loop nest. */
kono
parents: 14
diff changeset
572 if (!dominated_by_p (CDI_DOMINATORS, pdom, dom)
kono
parents: 14
diff changeset
573 || loop_depth (entry->src->loop_father)
kono
parents: 14
diff changeset
574 != loop_depth (exit->dest->loop_father))
kono
parents: 14
diff changeset
575 return invalid_sese;
kono
parents: 14
diff changeset
576
kono
parents: 14
diff changeset
577 /* For now we just bail out when there is a loop exit in the region
kono
parents: 14
diff changeset
578 that is not also the exit of the region. We could enlarge the
kono
parents: 14
diff changeset
579 region to cover the loop that region exits to. See PR79977. */
kono
parents: 14
diff changeset
580 if (loop_outer (entry->src->loop_father))
kono
parents: 14
diff changeset
581 {
kono
parents: 14
diff changeset
582 vec<edge> exits = get_loop_exit_edges (entry->src->loop_father);
kono
parents: 14
diff changeset
583 for (unsigned i = 0; i < exits.length (); ++i)
kono
parents: 14
diff changeset
584 {
kono
parents: 14
diff changeset
585 if (exits[i] != exit
kono
parents: 14
diff changeset
586 && bb_in_region (exits[i]->src, entry->dest, exit->src))
kono
parents: 14
diff changeset
587 {
kono
parents: 14
diff changeset
588 DEBUG_PRINT (dp << "[scop-detection-fail] cannot merge seses.\n");
kono
parents: 14
diff changeset
589 exits.release ();
kono
parents: 14
diff changeset
590 return invalid_sese;
kono
parents: 14
diff changeset
591 }
kono
parents: 14
diff changeset
592 }
kono
parents: 14
diff changeset
593 exits.release ();
kono
parents: 14
diff changeset
594 }
kono
parents: 14
diff changeset
595
kono
parents: 14
diff changeset
596 /* For now we just want to bail out when exit does not post-dominate entry.
kono
parents: 14
diff changeset
597 TODO: We might just add a basic_block at the exit to make exit
kono
parents: 14
diff changeset
598 post-dominate entry (the entire region). */
kono
parents: 14
diff changeset
599 if (!dominated_by_p (CDI_POST_DOMINATORS, get_entry_bb (combined),
kono
parents: 14
diff changeset
600 get_exit_bb (combined))
kono
parents: 14
diff changeset
601 || !dominated_by_p (CDI_DOMINATORS, get_exit_bb (combined),
kono
parents: 14
diff changeset
602 get_entry_bb (combined)))
kono
parents: 14
diff changeset
603 {
kono
parents: 14
diff changeset
604 DEBUG_PRINT (dp << "[scop-detection-fail] cannot merge seses.\n");
kono
parents: 14
diff changeset
605 return invalid_sese;
kono
parents: 14
diff changeset
606 }
kono
parents: 14
diff changeset
607
kono
parents: 14
diff changeset
608 DEBUG_PRINT (dp << "[merged-sese] s1: "; print_sese (dump_file, combined));
kono
parents: 14
diff changeset
609
kono
parents: 14
diff changeset
610 return combined;
kono
parents: 14
diff changeset
611 }
kono
parents: 14
diff changeset
612
kono
parents: 14
diff changeset
613 /* Build scop outer->inner if possible. */
9
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
614
16
kono
parents: 14
diff changeset
615 void
kono
parents: 14
diff changeset
616 scop_detection::build_scop_depth (loop_p loop)
kono
parents: 14
diff changeset
617 {
kono
parents: 14
diff changeset
618 sese_l s = invalid_sese;
kono
parents: 14
diff changeset
619 loop = loop->inner;
kono
parents: 14
diff changeset
620 while (loop)
kono
parents: 14
diff changeset
621 {
kono
parents: 14
diff changeset
622 sese_l next = get_sese (loop);
kono
parents: 14
diff changeset
623 if (! next
kono
parents: 14
diff changeset
624 || harmful_loop_in_region (next))
kono
parents: 14
diff changeset
625 {
kono
parents: 14
diff changeset
626 if (s)
kono
parents: 14
diff changeset
627 add_scop (s);
kono
parents: 14
diff changeset
628 build_scop_depth (loop);
kono
parents: 14
diff changeset
629 s = invalid_sese;
kono
parents: 14
diff changeset
630 }
kono
parents: 14
diff changeset
631 else if (! s)
kono
parents: 14
diff changeset
632 s = next;
kono
parents: 14
diff changeset
633 else
kono
parents: 14
diff changeset
634 {
kono
parents: 14
diff changeset
635 sese_l combined = merge_sese (s, next);
kono
parents: 14
diff changeset
636 if (! combined
kono
parents: 14
diff changeset
637 || harmful_loop_in_region (combined))
kono
parents: 14
diff changeset
638 {
kono
parents: 14
diff changeset
639 add_scop (s);
kono
parents: 14
diff changeset
640 s = next;
kono
parents: 14
diff changeset
641 }
kono
parents: 14
diff changeset
642 else
kono
parents: 14
diff changeset
643 s = combined;
kono
parents: 14
diff changeset
644 }
kono
parents: 14
diff changeset
645 loop = loop->next;
kono
parents: 14
diff changeset
646 }
kono
parents: 14
diff changeset
647 if (s)
kono
parents: 14
diff changeset
648 add_scop (s);
kono
parents: 14
diff changeset
649 }
kono
parents: 14
diff changeset
650
kono
parents: 14
diff changeset
651 /* Returns true when Graphite can represent LOOP in SCOP.
kono
parents: 14
diff changeset
652 FIXME: For the moment, graphite cannot be used on loops that iterate using
kono
parents: 14
diff changeset
653 induction variables that wrap. */
kono
parents: 14
diff changeset
654
kono
parents: 14
diff changeset
655 bool
kono
parents: 14
diff changeset
656 scop_detection::can_represent_loop (loop_p loop, sese_l scop)
kono
parents: 14
diff changeset
657 {
kono
parents: 14
diff changeset
658 tree niter;
kono
parents: 14
diff changeset
659 struct tree_niter_desc niter_desc;
kono
parents: 14
diff changeset
660
kono
parents: 14
diff changeset
661 return single_exit (loop)
kono
parents: 14
diff changeset
662 && !(loop_preheader_edge (loop)->flags & EDGE_IRREDUCIBLE_LOOP)
kono
parents: 14
diff changeset
663 && number_of_iterations_exit (loop, single_exit (loop), &niter_desc, false)
kono
parents: 14
diff changeset
664 && niter_desc.control.no_overflow
kono
parents: 14
diff changeset
665 && (niter = number_of_latch_executions (loop))
kono
parents: 14
diff changeset
666 && !chrec_contains_undetermined (niter)
kono
parents: 14
diff changeset
667 && !chrec_contains_undetermined (scalar_evolution_in_region (scop,
kono
parents: 14
diff changeset
668 loop, niter))
kono
parents: 14
diff changeset
669 && graphite_can_represent_expr (scop, loop, niter);
kono
parents: 14
diff changeset
670 }
kono
parents: 14
diff changeset
671
kono
parents: 14
diff changeset
672 /* Return true when BEGIN is the preheader edge of a loop with a single exit
kono
parents: 14
diff changeset
673 END. */
kono
parents: 14
diff changeset
674
kono
parents: 14
diff changeset
675 bool
kono
parents: 14
diff changeset
676 scop_detection::region_has_one_loop (sese_l s)
kono
parents: 14
diff changeset
677 {
kono
parents: 14
diff changeset
678 edge begin = s.entry;
kono
parents: 14
diff changeset
679 edge end = s.exit;
kono
parents: 14
diff changeset
680 /* Check for a single perfectly nested loop. */
kono
parents: 14
diff changeset
681 if (begin->dest->loop_father->inner)
kono
parents: 14
diff changeset
682 return false;
kono
parents: 14
diff changeset
683
kono
parents: 14
diff changeset
684 /* Otherwise, check whether we have adjacent loops. */
kono
parents: 14
diff changeset
685 return (single_pred_p (end->src)
kono
parents: 14
diff changeset
686 && begin->dest->loop_father == single_pred (end->src)->loop_father);
kono
parents: 14
diff changeset
687 }
kono
parents: 14
diff changeset
688
kono
parents: 14
diff changeset
689 /* Add to SCOPS a scop starting at SCOP_BEGIN and ending at SCOP_END. */
kono
parents: 14
diff changeset
690
kono
parents: 14
diff changeset
691 void
kono
parents: 14
diff changeset
692 scop_detection::add_scop (sese_l s)
kono
parents: 14
diff changeset
693 {
kono
parents: 14
diff changeset
694 gcc_assert (s);
kono
parents: 14
diff changeset
695
kono
parents: 14
diff changeset
696 /* Do not add scops with only one loop. */
kono
parents: 14
diff changeset
697 if (region_has_one_loop (s))
kono
parents: 14
diff changeset
698 {
kono
parents: 14
diff changeset
699 DEBUG_PRINT (dp << "[scop-detection-fail] Discarding one loop SCoP: ";
kono
parents: 14
diff changeset
700 print_sese (dump_file, s));
kono
parents: 14
diff changeset
701 return;
kono
parents: 14
diff changeset
702 }
kono
parents: 14
diff changeset
703
kono
parents: 14
diff changeset
704 if (get_exit_bb (s) == EXIT_BLOCK_PTR_FOR_FN (cfun))
kono
parents: 14
diff changeset
705 {
kono
parents: 14
diff changeset
706 DEBUG_PRINT (dp << "[scop-detection-fail] "
kono
parents: 14
diff changeset
707 << "Discarding SCoP exiting to return: ";
kono
parents: 14
diff changeset
708 print_sese (dump_file, s));
kono
parents: 14
diff changeset
709 return;
kono
parents: 14
diff changeset
710 }
kono
parents: 14
diff changeset
711
kono
parents: 14
diff changeset
712 /* Remove all the scops which are subsumed by s. */
kono
parents: 14
diff changeset
713 remove_subscops (s);
kono
parents: 14
diff changeset
714
kono
parents: 14
diff changeset
715 /* Remove intersecting scops. FIXME: It will be a good idea to keep
kono
parents: 14
diff changeset
716 the non-intersecting part of the scop already in the list. */
kono
parents: 14
diff changeset
717 remove_intersecting_scops (s);
kono
parents: 14
diff changeset
718
kono
parents: 14
diff changeset
719 scops.safe_push (s);
kono
parents: 14
diff changeset
720 DEBUG_PRINT (dp << "[scop-detection] Adding SCoP: "; print_sese (dump_file, s));
kono
parents: 14
diff changeset
721 }
kono
parents: 14
diff changeset
722
kono
parents: 14
diff changeset
723 /* Return true when a statement in SCOP cannot be represented by Graphite. */
kono
parents: 14
diff changeset
724
kono
parents: 14
diff changeset
725 bool
kono
parents: 14
diff changeset
726 scop_detection::harmful_loop_in_region (sese_l scop) const
kono
parents: 14
diff changeset
727 {
kono
parents: 14
diff changeset
728 basic_block exit_bb = get_exit_bb (scop);
kono
parents: 14
diff changeset
729 basic_block entry_bb = get_entry_bb (scop);
kono
parents: 14
diff changeset
730
kono
parents: 14
diff changeset
731 DEBUG_PRINT (dp << "[checking-harmful-bbs] ";
kono
parents: 14
diff changeset
732 print_sese (dump_file, scop));
kono
parents: 14
diff changeset
733 gcc_assert (dominated_by_p (CDI_DOMINATORS, exit_bb, entry_bb));
kono
parents: 14
diff changeset
734
kono
parents: 14
diff changeset
735 auto_vec<basic_block> worklist;
kono
parents: 14
diff changeset
736 auto_bitmap loops;
kono
parents: 14
diff changeset
737
kono
parents: 14
diff changeset
738 worklist.safe_push (entry_bb);
kono
parents: 14
diff changeset
739 while (! worklist.is_empty ())
kono
parents: 14
diff changeset
740 {
kono
parents: 14
diff changeset
741 basic_block bb = worklist.pop ();
kono
parents: 14
diff changeset
742 DEBUG_PRINT (dp << "Visiting bb_" << bb->index << "\n");
kono
parents: 14
diff changeset
743
kono
parents: 14
diff changeset
744 /* The basic block should not be part of an irreducible loop. */
kono
parents: 14
diff changeset
745 if (bb->flags & BB_IRREDUCIBLE_LOOP)
kono
parents: 14
diff changeset
746 return true;
kono
parents: 14
diff changeset
747
kono
parents: 14
diff changeset
748 /* Check for unstructured control flow: CFG not generated by structured
kono
parents: 14
diff changeset
749 if-then-else. */
kono
parents: 14
diff changeset
750 if (bb->succs->length () > 1)
kono
parents: 14
diff changeset
751 {
kono
parents: 14
diff changeset
752 edge e;
kono
parents: 14
diff changeset
753 edge_iterator ei;
kono
parents: 14
diff changeset
754 FOR_EACH_EDGE (e, ei, bb->succs)
kono
parents: 14
diff changeset
755 if (!dominated_by_p (CDI_POST_DOMINATORS, bb, e->dest)
kono
parents: 14
diff changeset
756 && !dominated_by_p (CDI_DOMINATORS, e->dest, bb))
kono
parents: 14
diff changeset
757 return true;
kono
parents: 14
diff changeset
758 }
kono
parents: 14
diff changeset
759
kono
parents: 14
diff changeset
760 /* Collect all loops in the current region. */
kono
parents: 14
diff changeset
761 loop_p loop = bb->loop_father;
kono
parents: 14
diff changeset
762 if (loop_in_sese_p (loop, scop))
kono
parents: 14
diff changeset
763 bitmap_set_bit (loops, loop->num);
kono
parents: 14
diff changeset
764
kono
parents: 14
diff changeset
765 /* Check for harmful statements in basic blocks part of the region. */
kono
parents: 14
diff changeset
766 for (gimple_stmt_iterator gsi = gsi_start_bb (bb);
kono
parents: 14
diff changeset
767 !gsi_end_p (gsi); gsi_next (&gsi))
kono
parents: 14
diff changeset
768 if (!stmt_simple_for_scop_p (scop, gsi_stmt (gsi), bb))
kono
parents: 14
diff changeset
769 return true;
kono
parents: 14
diff changeset
770
kono
parents: 14
diff changeset
771 if (bb != exit_bb)
kono
parents: 14
diff changeset
772 for (basic_block dom = first_dom_son (CDI_DOMINATORS, bb);
kono
parents: 14
diff changeset
773 dom;
kono
parents: 14
diff changeset
774 dom = next_dom_son (CDI_DOMINATORS, dom))
kono
parents: 14
diff changeset
775 worklist.safe_push (dom);
kono
parents: 14
diff changeset
776 }
kono
parents: 14
diff changeset
777
kono
parents: 14
diff changeset
778 /* Go through all loops and check that they are still valid in the combined
kono
parents: 14
diff changeset
779 scop. */
kono
parents: 14
diff changeset
780 unsigned j;
kono
parents: 14
diff changeset
781 bitmap_iterator bi;
kono
parents: 14
diff changeset
782 EXECUTE_IF_SET_IN_BITMAP (loops, 0, j, bi)
kono
parents: 14
diff changeset
783 {
kono
parents: 14
diff changeset
784 loop_p loop = (*current_loops->larray)[j];
kono
parents: 14
diff changeset
785 gcc_assert (loop->num == (int) j);
kono
parents: 14
diff changeset
786
kono
parents: 14
diff changeset
787 /* Check if the loop nests are to be optimized for speed. */
kono
parents: 14
diff changeset
788 if (! loop->inner
kono
parents: 14
diff changeset
789 && ! optimize_loop_for_speed_p (loop))
kono
parents: 14
diff changeset
790 {
kono
parents: 14
diff changeset
791 DEBUG_PRINT (dp << "[scop-detection-fail] loop_"
kono
parents: 14
diff changeset
792 << loop->num << " is not on a hot path.\n");
kono
parents: 14
diff changeset
793 return true;
kono
parents: 14
diff changeset
794 }
9
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
795
16
kono
parents: 14
diff changeset
796 if (! can_represent_loop (loop, scop))
kono
parents: 14
diff changeset
797 {
kono
parents: 14
diff changeset
798 DEBUG_PRINT (dp << "[scop-detection-fail] cannot represent loop_"
kono
parents: 14
diff changeset
799 << loop->num << "\n");
kono
parents: 14
diff changeset
800 return true;
kono
parents: 14
diff changeset
801 }
kono
parents: 14
diff changeset
802
kono
parents: 14
diff changeset
803 /* Check if all loop nests have at least one data reference.
kono
parents: 14
diff changeset
804 ??? This check is expensive and loops premature at this point.
kono
parents: 14
diff changeset
805 If important to retain we can pre-compute this for all innermost
kono
parents: 14
diff changeset
806 loops and reject those when we build a SESE region for a loop
kono
parents: 14
diff changeset
807 during SESE discovery. */
kono
parents: 14
diff changeset
808 if (! loop->inner
kono
parents: 14
diff changeset
809 && ! loop_nest_has_data_refs (loop))
kono
parents: 14
diff changeset
810 {
kono
parents: 14
diff changeset
811 DEBUG_PRINT (dp << "[scop-detection-fail] loop_" << loop->num
kono
parents: 14
diff changeset
812 << "does not have any data reference.\n");
kono
parents: 14
diff changeset
813 return true;
kono
parents: 14
diff changeset
814 }
kono
parents: 14
diff changeset
815 }
kono
parents: 14
diff changeset
816
kono
parents: 14
diff changeset
817 return false;
kono
parents: 14
diff changeset
818 }
kono
parents: 14
diff changeset
819
kono
parents: 14
diff changeset
820 /* Returns true if S1 subsumes/surrounds S2. */
kono
parents: 14
diff changeset
821 bool
kono
parents: 14
diff changeset
822 scop_detection::subsumes (sese_l s1, sese_l s2)
kono
parents: 14
diff changeset
823 {
kono
parents: 14
diff changeset
824 if (dominated_by_p (CDI_DOMINATORS, get_entry_bb (s2),
kono
parents: 14
diff changeset
825 get_entry_bb (s1))
kono
parents: 14
diff changeset
826 && dominated_by_p (CDI_POST_DOMINATORS, s2.exit->dest,
kono
parents: 14
diff changeset
827 s1.exit->dest))
kono
parents: 14
diff changeset
828 return true;
kono
parents: 14
diff changeset
829 return false;
kono
parents: 14
diff changeset
830 }
kono
parents: 14
diff changeset
831
kono
parents: 14
diff changeset
832 /* Remove a SCoP which is subsumed by S1. */
kono
parents: 14
diff changeset
833 void
kono
parents: 14
diff changeset
834 scop_detection::remove_subscops (sese_l s1)
kono
parents: 14
diff changeset
835 {
kono
parents: 14
diff changeset
836 int j;
kono
parents: 14
diff changeset
837 sese_l *s2;
kono
parents: 14
diff changeset
838 FOR_EACH_VEC_ELT_REVERSE (scops, j, s2)
kono
parents: 14
diff changeset
839 {
kono
parents: 14
diff changeset
840 if (subsumes (s1, *s2))
kono
parents: 14
diff changeset
841 {
kono
parents: 14
diff changeset
842 DEBUG_PRINT (dp << "Removing sub-SCoP";
kono
parents: 14
diff changeset
843 print_sese (dump_file, *s2));
kono
parents: 14
diff changeset
844 scops.unordered_remove (j);
kono
parents: 14
diff changeset
845 }
kono
parents: 14
diff changeset
846 }
kono
parents: 14
diff changeset
847 }
kono
parents: 14
diff changeset
848
kono
parents: 14
diff changeset
849 /* Returns true if S1 intersects with S2. Since we already know that S1 does
kono
parents: 14
diff changeset
850 not subsume S2 or vice-versa, we only check for entry bbs. */
kono
parents: 14
diff changeset
851
kono
parents: 14
diff changeset
852 bool
kono
parents: 14
diff changeset
853 scop_detection::intersects (sese_l s1, sese_l s2)
kono
parents: 14
diff changeset
854 {
kono
parents: 14
diff changeset
855 if (dominated_by_p (CDI_DOMINATORS, get_entry_bb (s2),
kono
parents: 14
diff changeset
856 get_entry_bb (s1))
kono
parents: 14
diff changeset
857 && !dominated_by_p (CDI_DOMINATORS, get_entry_bb (s2),
kono
parents: 14
diff changeset
858 get_exit_bb (s1)))
kono
parents: 14
diff changeset
859 return true;
kono
parents: 14
diff changeset
860 if ((s1.exit == s2.entry) || (s2.exit == s1.entry))
kono
parents: 14
diff changeset
861 return true;
kono
parents: 14
diff changeset
862
kono
parents: 14
diff changeset
863 return false;
kono
parents: 14
diff changeset
864 }
kono
parents: 14
diff changeset
865
kono
parents: 14
diff changeset
866 /* Remove one of the scops when it intersects with any other. */
kono
parents: 14
diff changeset
867
kono
parents: 14
diff changeset
868 void
kono
parents: 14
diff changeset
869 scop_detection::remove_intersecting_scops (sese_l s1)
kono
parents: 14
diff changeset
870 {
kono
parents: 14
diff changeset
871 int j;
kono
parents: 14
diff changeset
872 sese_l *s2;
kono
parents: 14
diff changeset
873 FOR_EACH_VEC_ELT_REVERSE (scops, j, s2)
kono
parents: 14
diff changeset
874 {
kono
parents: 14
diff changeset
875 if (intersects (s1, *s2))
kono
parents: 14
diff changeset
876 {
kono
parents: 14
diff changeset
877 DEBUG_PRINT (dp << "Removing intersecting SCoP";
kono
parents: 14
diff changeset
878 print_sese (dump_file, *s2);
kono
parents: 14
diff changeset
879 dp << "Intersects with:";
kono
parents: 14
diff changeset
880 print_sese (dump_file, s1));
kono
parents: 14
diff changeset
881 scops.unordered_remove (j);
kono
parents: 14
diff changeset
882 }
kono
parents: 14
diff changeset
883 }
kono
parents: 14
diff changeset
884 }
kono
parents: 14
diff changeset
885
kono
parents: 14
diff changeset
886 /* Something like "n * m" is not allowed. */
kono
parents: 14
diff changeset
887
kono
parents: 14
diff changeset
888 bool
kono
parents: 14
diff changeset
889 scop_detection::graphite_can_represent_init (tree e)
kono
parents: 14
diff changeset
890 {
kono
parents: 14
diff changeset
891 switch (TREE_CODE (e))
kono
parents: 14
diff changeset
892 {
kono
parents: 14
diff changeset
893 case POLYNOMIAL_CHREC:
kono
parents: 14
diff changeset
894 return graphite_can_represent_init (CHREC_LEFT (e))
kono
parents: 14
diff changeset
895 && graphite_can_represent_init (CHREC_RIGHT (e));
kono
parents: 14
diff changeset
896
kono
parents: 14
diff changeset
897 case MULT_EXPR:
kono
parents: 14
diff changeset
898 if (chrec_contains_symbols (TREE_OPERAND (e, 0)))
kono
parents: 14
diff changeset
899 return graphite_can_represent_init (TREE_OPERAND (e, 0))
kono
parents: 14
diff changeset
900 && tree_fits_shwi_p (TREE_OPERAND (e, 1));
kono
parents: 14
diff changeset
901 else
kono
parents: 14
diff changeset
902 return graphite_can_represent_init (TREE_OPERAND (e, 1))
kono
parents: 14
diff changeset
903 && tree_fits_shwi_p (TREE_OPERAND (e, 0));
kono
parents: 14
diff changeset
904
kono
parents: 14
diff changeset
905 case PLUS_EXPR:
kono
parents: 14
diff changeset
906 case POINTER_PLUS_EXPR:
kono
parents: 14
diff changeset
907 case MINUS_EXPR:
kono
parents: 14
diff changeset
908 return graphite_can_represent_init (TREE_OPERAND (e, 0))
kono
parents: 14
diff changeset
909 && graphite_can_represent_init (TREE_OPERAND (e, 1));
kono
parents: 14
diff changeset
910
kono
parents: 14
diff changeset
911 case NEGATE_EXPR:
kono
parents: 14
diff changeset
912 case BIT_NOT_EXPR:
kono
parents: 14
diff changeset
913 CASE_CONVERT:
kono
parents: 14
diff changeset
914 case NON_LVALUE_EXPR:
kono
parents: 14
diff changeset
915 return graphite_can_represent_init (TREE_OPERAND (e, 0));
kono
parents: 14
diff changeset
916
kono
parents: 14
diff changeset
917 default:
kono
parents: 14
diff changeset
918 break;
kono
parents: 14
diff changeset
919 }
kono
parents: 14
diff changeset
920
kono
parents: 14
diff changeset
921 return true;
kono
parents: 14
diff changeset
922 }
kono
parents: 14
diff changeset
923
kono
parents: 14
diff changeset
924 /* Return true when SCEV can be represented in the polyhedral model.
kono
parents: 14
diff changeset
925
kono
parents: 14
diff changeset
926 An expression can be represented, if it can be expressed as an
kono
parents: 14
diff changeset
927 affine expression. For loops (i, j) and parameters (m, n) all
kono
parents: 14
diff changeset
928 affine expressions are of the form:
kono
parents: 14
diff changeset
929
kono
parents: 14
diff changeset
930 x1 * i + x2 * j + x3 * m + x4 * n + x5 * 1 where x1..x5 element of Z
kono
parents: 14
diff changeset
931
kono
parents: 14
diff changeset
932 1 i + 20 j + (-2) m + 25
kono
parents: 14
diff changeset
933
kono
parents: 14
diff changeset
934 Something like "i * n" or "n * m" is not allowed. */
kono
parents: 14
diff changeset
935
kono
parents: 14
diff changeset
936 bool
kono
parents: 14
diff changeset
937 scop_detection::graphite_can_represent_scev (sese_l scop, tree scev)
kono
parents: 14
diff changeset
938 {
kono
parents: 14
diff changeset
939 if (chrec_contains_undetermined (scev))
kono
parents: 14
diff changeset
940 return false;
kono
parents: 14
diff changeset
941
kono
parents: 14
diff changeset
942 switch (TREE_CODE (scev))
kono
parents: 14
diff changeset
943 {
kono
parents: 14
diff changeset
944 case NEGATE_EXPR:
kono
parents: 14
diff changeset
945 case BIT_NOT_EXPR:
kono
parents: 14
diff changeset
946 CASE_CONVERT:
kono
parents: 14
diff changeset
947 case NON_LVALUE_EXPR:
kono
parents: 14
diff changeset
948 return graphite_can_represent_scev (scop, TREE_OPERAND (scev, 0));
kono
parents: 14
diff changeset
949
kono
parents: 14
diff changeset
950 case PLUS_EXPR:
kono
parents: 14
diff changeset
951 case POINTER_PLUS_EXPR:
kono
parents: 14
diff changeset
952 case MINUS_EXPR:
kono
parents: 14
diff changeset
953 return graphite_can_represent_scev (scop, TREE_OPERAND (scev, 0))
kono
parents: 14
diff changeset
954 && graphite_can_represent_scev (scop, TREE_OPERAND (scev, 1));
kono
parents: 14
diff changeset
955
kono
parents: 14
diff changeset
956 case MULT_EXPR:
kono
parents: 14
diff changeset
957 return !CONVERT_EXPR_CODE_P (TREE_CODE (TREE_OPERAND (scev, 0)))
kono
parents: 14
diff changeset
958 && !CONVERT_EXPR_CODE_P (TREE_CODE (TREE_OPERAND (scev, 1)))
kono
parents: 14
diff changeset
959 && !(chrec_contains_symbols (TREE_OPERAND (scev, 0))
kono
parents: 14
diff changeset
960 && chrec_contains_symbols (TREE_OPERAND (scev, 1)))
kono
parents: 14
diff changeset
961 && graphite_can_represent_init (scev)
kono
parents: 14
diff changeset
962 && graphite_can_represent_scev (scop, TREE_OPERAND (scev, 0))
kono
parents: 14
diff changeset
963 && graphite_can_represent_scev (scop, TREE_OPERAND (scev, 1));
kono
parents: 14
diff changeset
964
kono
parents: 14
diff changeset
965 case POLYNOMIAL_CHREC:
kono
parents: 14
diff changeset
966 /* Check for constant strides. With a non constant stride of
kono
parents: 14
diff changeset
967 'n' we would have a value of 'iv * n'. Also check that the
kono
parents: 14
diff changeset
968 initial value can represented: for example 'n * m' cannot be
kono
parents: 14
diff changeset
969 represented. */
kono
parents: 14
diff changeset
970 gcc_assert (loop_in_sese_p (get_loop (cfun,
kono
parents: 14
diff changeset
971 CHREC_VARIABLE (scev)), scop));
kono
parents: 14
diff changeset
972 if (!evolution_function_right_is_integer_cst (scev)
kono
parents: 14
diff changeset
973 || !graphite_can_represent_init (scev))
kono
parents: 14
diff changeset
974 return false;
kono
parents: 14
diff changeset
975 return graphite_can_represent_scev (scop, CHREC_LEFT (scev));
kono
parents: 14
diff changeset
976
kono
parents: 14
diff changeset
977 default:
kono
parents: 14
diff changeset
978 break;
kono
parents: 14
diff changeset
979 }
kono
parents: 14
diff changeset
980
kono
parents: 14
diff changeset
981 /* Only affine functions can be represented. */
kono
parents: 14
diff changeset
982 if (tree_contains_chrecs (scev, NULL) || !scev_is_linear_expression (scev))
kono
parents: 14
diff changeset
983 return false;
kono
parents: 14
diff changeset
984
kono
parents: 14
diff changeset
985 return true;
9
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
986 }
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
diff changeset
987
16
kono
parents: 14
diff changeset
988 /* Return true when EXPR can be represented in the polyhedral model.
kono
parents: 14
diff changeset
989
kono
parents: 14
diff changeset
990 This means an expression can be represented, if it is linear with respect to
kono
parents: 14
diff changeset
991 the loops and the strides are non parametric. LOOP is the place where the
kono
parents: 14
diff changeset
992 expr will be evaluated. SCOP defines the region we analyse. */
kono
parents: 14
diff changeset
993
kono
parents: 14
diff changeset
994 bool
kono
parents: 14
diff changeset
995 scop_detection::graphite_can_represent_expr (sese_l scop, loop_p loop,
kono
parents: 14
diff changeset
996 tree expr)
kono
parents: 14
diff changeset
997 {
kono
parents: 14
diff changeset
998 tree scev = scalar_evolution_in_region (scop, loop, expr);
kono
parents: 14
diff changeset
999 return graphite_can_represent_scev (scop, scev);
kono
parents: 14
diff changeset
1000 }
kono
parents: 14
diff changeset
1001
kono
parents: 14
diff changeset
1002 /* Return true if the data references of STMT can be represented by Graphite.
kono
parents: 14
diff changeset
1003 We try to analyze the data references in a loop contained in the SCOP. */
kono
parents: 14
diff changeset
1004
kono
parents: 14
diff changeset
1005 bool
kono
parents: 14
diff changeset
1006 scop_detection::stmt_has_simple_data_refs_p (sese_l scop, gimple *stmt)
kono
parents: 14
diff changeset
1007 {
kono
parents: 14
diff changeset
1008 edge nest = scop.entry;;
kono
parents: 14
diff changeset
1009 loop_p loop = loop_containing_stmt (stmt);
kono
parents: 14
diff changeset
1010 if (!loop_in_sese_p (loop, scop))
kono
parents: 14
diff changeset
1011 loop = NULL;
kono
parents: 14
diff changeset
1012
kono
parents: 14
diff changeset
1013 auto_vec<data_reference_p> drs;
kono
parents: 14
diff changeset
1014 if (! graphite_find_data_references_in_stmt (nest, loop, stmt, &drs))
kono
parents: 14
diff changeset
1015 return false;
kono
parents: 14
diff changeset
1016
kono
parents: 14
diff changeset
1017 int j;
kono
parents: 14
diff changeset
1018 data_reference_p dr;
kono
parents: 14
diff changeset
1019 FOR_EACH_VEC_ELT (drs, j, dr)
kono
parents: 14
diff changeset
1020 {
kono
parents: 14
diff changeset
1021 for (unsigned i = 0; i < DR_NUM_DIMENSIONS (dr); ++i)
kono
parents: 14
diff changeset
1022 if (! graphite_can_represent_scev (scop, DR_ACCESS_FN (dr, i)))
kono
parents: 14
diff changeset
1023 return false;
kono
parents: 14
diff changeset
1024 }
kono
parents: 14
diff changeset
1025
kono
parents: 14
diff changeset
1026 return true;
kono
parents: 14
diff changeset
1027 }
kono
parents: 14
diff changeset
1028
kono
parents: 14
diff changeset
1029 /* GIMPLE_ASM and GIMPLE_CALL may embed arbitrary side effects.
kono
parents: 14
diff changeset
1030 Calls have side-effects, except those to const or pure
kono
parents: 14
diff changeset
1031 functions. */
kono
parents: 14
diff changeset
1032
kono
parents: 14
diff changeset
1033 static bool
kono
parents: 14
diff changeset
1034 stmt_has_side_effects (gimple *stmt)
kono
parents: 14
diff changeset
1035 {
kono
parents: 14
diff changeset
1036 if (gimple_has_volatile_ops (stmt)
kono
parents: 14
diff changeset
1037 || (gimple_code (stmt) == GIMPLE_CALL
kono
parents: 14
diff changeset
1038 && !(gimple_call_flags (stmt) & (ECF_CONST | ECF_PURE)))
kono
parents: 14
diff changeset
1039 || (gimple_code (stmt) == GIMPLE_ASM))
kono
parents: 14
diff changeset
1040 {
kono
parents: 14
diff changeset
1041 DEBUG_PRINT (dp << "[scop-detection-fail] "
kono
parents: 14
diff changeset
1042 << "Statement has side-effects:\n";
kono
parents: 14
diff changeset
1043 print_gimple_stmt (dump_file, stmt, 0, TDF_VOPS | TDF_MEMSYMS));
kono
parents: 14
diff changeset
1044 return true;
kono
parents: 14
diff changeset
1045 }
kono
parents: 14
diff changeset
1046 return false;
kono
parents: 14
diff changeset
1047 }
kono
parents: 14
diff changeset
1048
kono
parents: 14
diff changeset
1049 /* Return true only when STMT is simple enough for being handled by Graphite.
kono
parents: 14
diff changeset
1050 This depends on SCOP, as the parameters are initialized relatively to
kono
parents: 14
diff changeset
1051 this basic block, the linear functions are initialized based on the outermost
kono
parents: 14
diff changeset
1052 loop containing STMT inside the SCOP. BB is the place where we try to
kono
parents: 14
diff changeset
1053 evaluate the STMT. */
kono
parents: 14
diff changeset
1054
kono
parents: 14
diff changeset
1055 bool
kono
parents: 14
diff changeset
1056 scop_detection::stmt_simple_for_scop_p (sese_l scop, gimple *stmt,
kono
parents: 14
diff changeset
1057 basic_block bb) const
kono
parents: 14
diff changeset
1058 {
kono
parents: 14
diff changeset
1059 gcc_assert (scop);
kono
parents: 14
diff changeset
1060
kono
parents: 14
diff changeset
1061 if (is_gimple_debug (stmt))
kono
parents: 14
diff changeset
1062 return true;
kono
parents: 14
diff changeset
1063
kono
parents: 14
diff changeset
1064 if (stmt_has_side_effects (stmt))
kono
parents: 14
diff changeset
1065 return false;
kono
parents: 14
diff changeset
1066
kono
parents: 14
diff changeset
1067 if (!stmt_has_simple_data_refs_p (scop, stmt))
kono
parents: 14
diff changeset
1068 {
kono
parents: 14
diff changeset
1069 DEBUG_PRINT (dp << "[scop-detection-fail] "
kono
parents: 14
diff changeset
1070 << "Graphite cannot handle data-refs in stmt:\n";
kono
parents: 14
diff changeset
1071 print_gimple_stmt (dump_file, stmt, 0, TDF_VOPS|TDF_MEMSYMS););
kono
parents: 14
diff changeset
1072 return false;
kono
parents: 14
diff changeset
1073 }
kono
parents: 14
diff changeset
1074
kono
parents: 14
diff changeset
1075 switch (gimple_code (stmt))
kono
parents: 14
diff changeset
1076 {
kono
parents: 14
diff changeset
1077 case GIMPLE_LABEL:
kono
parents: 14
diff changeset
1078 return true;
kono
parents: 14
diff changeset
1079
kono
parents: 14
diff changeset
1080 case GIMPLE_COND:
kono
parents: 14
diff changeset
1081 {
kono
parents: 14
diff changeset
1082 /* We can handle all binary comparisons. Inequalities are
kono
parents: 14
diff changeset
1083 also supported as they can be represented with union of
kono
parents: 14
diff changeset
1084 polyhedra. */
kono
parents: 14
diff changeset
1085 enum tree_code code = gimple_cond_code (stmt);
kono
parents: 14
diff changeset
1086 if (!(code == LT_EXPR
kono
parents: 14
diff changeset
1087 || code == GT_EXPR
kono
parents: 14
diff changeset
1088 || code == LE_EXPR
kono
parents: 14
diff changeset
1089 || code == GE_EXPR
kono
parents: 14
diff changeset
1090 || code == EQ_EXPR
kono
parents: 14
diff changeset
1091 || code == NE_EXPR))
kono
parents: 14
diff changeset
1092 {
kono
parents: 14
diff changeset
1093 DEBUG_PRINT (dp << "[scop-detection-fail] "
kono
parents: 14
diff changeset
1094 << "Graphite cannot handle cond stmt:\n";
kono
parents: 14
diff changeset
1095 print_gimple_stmt (dump_file, stmt, 0,
kono
parents: 14
diff changeset
1096 TDF_VOPS | TDF_MEMSYMS));
kono
parents: 14
diff changeset
1097 return false;
kono
parents: 14
diff changeset
1098 }
kono
parents: 14
diff changeset
1099
kono
parents: 14
diff changeset
1100 loop_p loop = bb->loop_father;
kono
parents: 14
diff changeset
1101 for (unsigned i = 0; i < 2; ++i)
kono
parents: 14
diff changeset
1102 {
kono
parents: 14
diff changeset
1103 tree op = gimple_op (stmt, i);
kono
parents: 14
diff changeset
1104 if (!graphite_can_represent_expr (scop, loop, op)
kono
parents: 14
diff changeset
1105 /* We can only constrain on integer type. */
kono
parents: 14
diff changeset
1106 || ! INTEGRAL_TYPE_P (TREE_TYPE (op)))
kono
parents: 14
diff changeset
1107 {
kono
parents: 14
diff changeset
1108 DEBUG_PRINT (dp << "[scop-detection-fail] "
kono
parents: 14
diff changeset
1109 << "Graphite cannot represent stmt:\n";
kono
parents: 14
diff changeset
1110 print_gimple_stmt (dump_file, stmt, 0,
kono
parents: 14
diff changeset
1111 TDF_VOPS | TDF_MEMSYMS));
kono
parents: 14
diff changeset
1112 return false;
kono
parents: 14
diff changeset
1113 }
kono
parents: 14
diff changeset
1114 }
kono
parents: 14
diff changeset
1115
kono
parents: 14
diff changeset
1116 return true;
kono
parents: 14
diff changeset
1117 }
kono
parents: 14
diff changeset
1118
kono
parents: 14
diff changeset
1119 case GIMPLE_ASSIGN:
kono
parents: 14
diff changeset
1120 case GIMPLE_CALL:
kono
parents: 14
diff changeset
1121 return true;
kono
parents: 14
diff changeset
1122
kono
parents: 14
diff changeset
1123 default:
kono
parents: 14
diff changeset
1124 /* These nodes cut a new scope. */
kono
parents: 14
diff changeset
1125 DEBUG_PRINT (
kono
parents: 14
diff changeset
1126 dp << "[scop-detection-fail] "
kono
parents: 14
diff changeset
1127 << "Gimple stmt not handled in Graphite:\n";
kono
parents: 14
diff changeset
1128 print_gimple_stmt (dump_file, stmt, 0, TDF_VOPS | TDF_MEMSYMS));
kono
parents: 14
diff changeset
1129 return false;
kono
parents: 14
diff changeset
1130 }
kono
parents: 14
diff changeset
1131 }
kono
parents: 14
diff changeset
1132
kono
parents: 14
diff changeset
1133 /* Returns the number of pbbs that are in loops contained in SCOP. */
kono
parents: 14
diff changeset
1134
kono
parents: 14
diff changeset
1135 int
kono
parents: 14
diff changeset
1136 scop_detection::nb_pbbs_in_loops (scop_p scop)
kono
parents: 14
diff changeset
1137 {
kono
parents: 14
diff changeset
1138 int i;
kono
parents: 14
diff changeset
1139 poly_bb_p pbb;
kono
parents: 14
diff changeset
1140 int res = 0;
kono
parents: 14
diff changeset
1141
kono
parents: 14
diff changeset
1142 FOR_EACH_VEC_ELT (scop->pbbs, i, pbb)
kono
parents: 14
diff changeset
1143 if (loop_in_sese_p (gbb_loop (PBB_BLACK_BOX (pbb)), scop->scop_info->region))
kono
parents: 14
diff changeset
1144 res++;
kono
parents: 14
diff changeset
1145
kono
parents: 14
diff changeset
1146 return res;
kono
parents: 14
diff changeset
1147 }
kono
parents: 14
diff changeset
1148
kono
parents: 14
diff changeset
1149 /* Assigns the parameter NAME an index in REGION. */
kono
parents: 14
diff changeset
1150
kono
parents: 14
diff changeset
1151 static void
kono
parents: 14
diff changeset
1152 assign_parameter_index_in_region (tree name, sese_info_p region)
kono
parents: 14
diff changeset
1153 {
kono
parents: 14
diff changeset
1154 gcc_assert (TREE_CODE (name) == SSA_NAME
kono
parents: 14
diff changeset
1155 && INTEGRAL_TYPE_P (TREE_TYPE (name))
kono
parents: 14
diff changeset
1156 && ! defined_in_sese_p (name, region->region));
kono
parents: 14
diff changeset
1157
kono
parents: 14
diff changeset
1158 int i;
kono
parents: 14
diff changeset
1159 tree p;
kono
parents: 14
diff changeset
1160 FOR_EACH_VEC_ELT (region->params, i, p)
kono
parents: 14
diff changeset
1161 if (p == name)
kono
parents: 14
diff changeset
1162 return;
kono
parents: 14
diff changeset
1163
kono
parents: 14
diff changeset
1164 i = region->params.length ();
kono
parents: 14
diff changeset
1165 region->params.safe_push (name);
kono
parents: 14
diff changeset
1166 }
kono
parents: 14
diff changeset
1167
kono
parents: 14
diff changeset
1168 /* In the context of sese S, scan the expression E and translate it to
kono
parents: 14
diff changeset
1169 a linear expression C. When parsing a symbolic multiplication, K
kono
parents: 14
diff changeset
1170 represents the constant multiplier of an expression containing
kono
parents: 14
diff changeset
1171 parameters. */
kono
parents: 14
diff changeset
1172
kono
parents: 14
diff changeset
1173 static void
kono
parents: 14
diff changeset
1174 scan_tree_for_params (sese_info_p s, tree e)
kono
parents: 14
diff changeset
1175 {
kono
parents: 14
diff changeset
1176 if (e == chrec_dont_know)
kono
parents: 14
diff changeset
1177 return;
kono
parents: 14
diff changeset
1178
kono
parents: 14
diff changeset
1179 switch (TREE_CODE (e))
kono
parents: 14
diff changeset
1180 {
kono
parents: 14
diff changeset
1181 case POLYNOMIAL_CHREC:
kono
parents: 14
diff changeset
1182 scan_tree_for_params (s, CHREC_LEFT (e));
kono
parents: 14
diff changeset
1183 break;
kono
parents: 14
diff changeset
1184
kono
parents: 14
diff changeset
1185 case MULT_EXPR:
kono
parents: 14
diff changeset
1186 if (chrec_contains_symbols (TREE_OPERAND (e, 0)))
kono
parents: 14
diff changeset
1187 scan_tree_for_params (s, TREE_OPERAND (e, 0));
kono
parents: 14
diff changeset
1188 else
kono
parents: 14
diff changeset
1189 scan_tree_for_params (s, TREE_OPERAND (e, 1));
kono
parents: 14
diff changeset
1190 break;
kono
parents: 14
diff changeset
1191
kono
parents: 14
diff changeset
1192 case PLUS_EXPR:
kono
parents: 14
diff changeset
1193 case POINTER_PLUS_EXPR:
kono
parents: 14
diff changeset
1194 case MINUS_EXPR:
kono
parents: 14
diff changeset
1195 scan_tree_for_params (s, TREE_OPERAND (e, 0));
kono
parents: 14
diff changeset
1196 scan_tree_for_params (s, TREE_OPERAND (e, 1));
kono
parents: 14
diff changeset
1197 break;
kono
parents: 14
diff changeset
1198
kono
parents: 14
diff changeset
1199 case NEGATE_EXPR:
kono
parents: 14
diff changeset
1200 case BIT_NOT_EXPR:
kono
parents: 14
diff changeset
1201 CASE_CONVERT:
kono
parents: 14
diff changeset
1202 case NON_LVALUE_EXPR:
kono
parents: 14
diff changeset
1203 scan_tree_for_params (s, TREE_OPERAND (e, 0));
kono
parents: 14
diff changeset
1204 break;
kono
parents: 14
diff changeset
1205
kono
parents: 14
diff changeset
1206 case SSA_NAME:
kono
parents: 14
diff changeset
1207 assign_parameter_index_in_region (e, s);
kono
parents: 14
diff changeset
1208 break;
kono
parents: 14
diff changeset
1209
kono
parents: 14
diff changeset
1210 case INTEGER_CST:
kono
parents: 14
diff changeset
1211 case ADDR_EXPR:
kono
parents: 14
diff changeset
1212 case REAL_CST:
kono
parents: 14
diff changeset
1213 case COMPLEX_CST:
kono
parents: 14
diff changeset
1214 case VECTOR_CST:
kono
parents: 14
diff changeset
1215 break;
kono
parents: 14
diff changeset
1216
kono
parents: 14
diff changeset
1217 default:
kono
parents: 14
diff changeset
1218 gcc_unreachable ();
kono
parents: 14
diff changeset
1219 break;
kono
parents: 14
diff changeset
1220 }
kono
parents: 14
diff changeset
1221 }
kono
parents: 14
diff changeset
1222
kono
parents: 14
diff changeset
1223 /* Find parameters with respect to REGION in BB. We are looking in memory
kono
parents: 14
diff changeset
1224 access functions, conditions and loop bounds. */
kono
parents: 14
diff changeset
1225
kono
parents: 14
diff changeset
1226 static void
kono
parents: 14
diff changeset
1227 find_params_in_bb (sese_info_p region, gimple_poly_bb_p gbb)
kono
parents: 14
diff changeset
1228 {
kono
parents: 14
diff changeset
1229 /* Find parameters in the access functions of data references. */
kono
parents: 14
diff changeset
1230 int i;
kono
parents: 14
diff changeset
1231 data_reference_p dr;
kono
parents: 14
diff changeset
1232 FOR_EACH_VEC_ELT (GBB_DATA_REFS (gbb), i, dr)
kono
parents: 14
diff changeset
1233 for (unsigned j = 0; j < DR_NUM_DIMENSIONS (dr); j++)
kono
parents: 14
diff changeset
1234 scan_tree_for_params (region, DR_ACCESS_FN (dr, j));
kono
parents: 14
diff changeset
1235
kono
parents: 14
diff changeset
1236 /* Find parameters in conditional statements. */
kono
parents: 14
diff changeset
1237 gimple *stmt;
kono
parents: 14
diff changeset
1238 loop_p loop = GBB_BB (gbb)->loop_father;
kono
parents: 14
diff changeset
1239 FOR_EACH_VEC_ELT (GBB_CONDITIONS (gbb), i, stmt)
kono
parents: 14
diff changeset
1240 {
kono
parents: 14
diff changeset
1241 tree lhs = scalar_evolution_in_region (region->region, loop,
kono
parents: 14
diff changeset
1242 gimple_cond_lhs (stmt));
kono
parents: 14
diff changeset
1243 tree rhs = scalar_evolution_in_region (region->region, loop,
kono
parents: 14
diff changeset
1244 gimple_cond_rhs (stmt));
kono
parents: 14
diff changeset
1245
kono
parents: 14
diff changeset
1246 scan_tree_for_params (region, lhs);
kono
parents: 14
diff changeset
1247 scan_tree_for_params (region, rhs);
kono
parents: 14
diff changeset
1248 }
kono
parents: 14
diff changeset
1249 }
kono
parents: 14
diff changeset
1250
kono
parents: 14
diff changeset
1251 /* Record the parameters used in the SCOP BBs. A variable is a parameter
kono
parents: 14
diff changeset
1252 in a scop if it does not vary during the execution of that scop. */
kono
parents: 14
diff changeset
1253
kono
parents: 14
diff changeset
1254 static void
kono
parents: 14
diff changeset
1255 find_scop_parameters (scop_p scop)
kono
parents: 14
diff changeset
1256 {
kono
parents: 14
diff changeset
1257 unsigned i;
kono
parents: 14
diff changeset
1258 sese_info_p region = scop->scop_info;
kono
parents: 14
diff changeset
1259
kono
parents: 14
diff changeset
1260 /* Parameters used in loop bounds are processed during gather_bbs. */
kono
parents: 14
diff changeset
1261
kono
parents: 14
diff changeset
1262 /* Find the parameters used in data accesses. */
kono
parents: 14
diff changeset
1263 poly_bb_p pbb;
kono
parents: 14
diff changeset
1264 FOR_EACH_VEC_ELT (scop->pbbs, i, pbb)
kono
parents: 14
diff changeset
1265 find_params_in_bb (region, PBB_BLACK_BOX (pbb));
kono
parents: 14
diff changeset
1266
kono
parents: 14
diff changeset
1267 int nbp = sese_nb_params (region);
kono
parents: 14
diff changeset
1268 scop_set_nb_params (scop, nbp);
kono
parents: 14
diff changeset
1269 }
kono
parents: 14
diff changeset
1270
kono
parents: 14
diff changeset
1271 static void
kono
parents: 14
diff changeset
1272 add_write (vec<tree> *writes, tree def)
kono
parents: 14
diff changeset
1273 {
kono
parents: 14
diff changeset
1274 writes->safe_push (def);
kono
parents: 14
diff changeset
1275 DEBUG_PRINT (dp << "Adding scalar write: ";
kono
parents: 14
diff changeset
1276 print_generic_expr (dump_file, def);
kono
parents: 14
diff changeset
1277 dp << "\nFrom stmt: ";
kono
parents: 14
diff changeset
1278 print_gimple_stmt (dump_file,
kono
parents: 14
diff changeset
1279 SSA_NAME_DEF_STMT (def), 0));
kono
parents: 14
diff changeset
1280 }
kono
parents: 14
diff changeset
1281
kono
parents: 14
diff changeset
1282 static void
kono
parents: 14
diff changeset
1283 add_read (vec<scalar_use> *reads, tree use, gimple *use_stmt)
kono
parents: 14
diff changeset
1284 {
kono
parents: 14
diff changeset
1285 DEBUG_PRINT (dp << "Adding scalar read: ";
kono
parents: 14
diff changeset
1286 print_generic_expr (dump_file, use);
kono
parents: 14
diff changeset
1287 dp << "\nFrom stmt: ";
kono
parents: 14
diff changeset
1288 print_gimple_stmt (dump_file, use_stmt, 0));
kono
parents: 14
diff changeset
1289 reads->safe_push (std::make_pair (use_stmt, use));
kono
parents: 14
diff changeset
1290 }
kono
parents: 14
diff changeset
1291
kono
parents: 14
diff changeset
1292
kono
parents: 14
diff changeset
1293 /* Record DEF if it is used in other bbs different than DEF_BB in the SCOP. */
kono
parents: 14
diff changeset
1294
kono
parents: 14
diff changeset
1295 static void
kono
parents: 14
diff changeset
1296 build_cross_bb_scalars_def (scop_p scop, tree def, basic_block def_bb,
kono
parents: 14
diff changeset
1297 vec<tree> *writes)
kono
parents: 14
diff changeset
1298 {
kono
parents: 14
diff changeset
1299 if (!is_gimple_reg (def))
kono
parents: 14
diff changeset
1300 return;
kono
parents: 14
diff changeset
1301
kono
parents: 14
diff changeset
1302 bool scev_analyzable = scev_analyzable_p (def, scop->scop_info->region);
kono
parents: 14
diff changeset
1303
kono
parents: 14
diff changeset
1304 gimple *use_stmt;
kono
parents: 14
diff changeset
1305 imm_use_iterator imm_iter;
kono
parents: 14
diff changeset
1306 FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter, def)
kono
parents: 14
diff changeset
1307 /* Do not gather scalar variables that can be analyzed by SCEV as they can
kono
parents: 14
diff changeset
1308 be generated out of the induction variables. */
kono
parents: 14
diff changeset
1309 if ((! scev_analyzable
kono
parents: 14
diff changeset
1310 /* But gather SESE liveouts as we otherwise fail to rewrite their
kono
parents: 14
diff changeset
1311 exit PHIs. */
kono
parents: 14
diff changeset
1312 || ! bb_in_sese_p (gimple_bb (use_stmt), scop->scop_info->region))
kono
parents: 14
diff changeset
1313 && (def_bb != gimple_bb (use_stmt) && !is_gimple_debug (use_stmt)))
kono
parents: 14
diff changeset
1314 {
kono
parents: 14
diff changeset
1315 add_write (writes, def);
kono
parents: 14
diff changeset
1316 /* This is required by the FOR_EACH_IMM_USE_STMT when we want to break
kono
parents: 14
diff changeset
1317 before all the uses have been visited. */
kono
parents: 14
diff changeset
1318 BREAK_FROM_IMM_USE_STMT (imm_iter);
kono
parents: 14
diff changeset
1319 }
kono
parents: 14
diff changeset
1320 }
kono
parents: 14
diff changeset
1321
kono
parents: 14
diff changeset
1322 /* Record USE if it is defined in other bbs different than USE_STMT
kono
parents: 14
diff changeset
1323 in the SCOP. */
kono
parents: 14
diff changeset
1324
kono
parents: 14
diff changeset
1325 static void
kono
parents: 14
diff changeset
1326 build_cross_bb_scalars_use (scop_p scop, tree use, gimple *use_stmt,
kono
parents: 14
diff changeset
1327 vec<scalar_use> *reads)
kono
parents: 14
diff changeset
1328 {
kono
parents: 14
diff changeset
1329 if (!is_gimple_reg (use))
kono
parents: 14
diff changeset
1330 return;
kono
parents: 14
diff changeset
1331
kono
parents: 14
diff changeset
1332 /* Do not gather scalar variables that can be analyzed by SCEV as they can be
kono
parents: 14
diff changeset
1333 generated out of the induction variables. */
kono
parents: 14
diff changeset
1334 if (scev_analyzable_p (use, scop->scop_info->region))
kono
parents: 14
diff changeset
1335 return;
kono
parents: 14
diff changeset
1336
kono
parents: 14
diff changeset
1337 gimple *def_stmt = SSA_NAME_DEF_STMT (use);
kono
parents: 14
diff changeset
1338 if (gimple_bb (def_stmt) != gimple_bb (use_stmt))
kono
parents: 14
diff changeset
1339 add_read (reads, use, use_stmt);
kono
parents: 14
diff changeset
1340 }
kono
parents: 14
diff changeset
1341
kono
parents: 14
diff changeset
1342 /* Generates a polyhedral black box only if the bb contains interesting
kono
parents: 14
diff changeset
1343 information. */
kono
parents: 14
diff changeset
1344
kono
parents: 14
diff changeset
1345 static gimple_poly_bb_p
kono
parents: 14
diff changeset
1346 try_generate_gimple_bb (scop_p scop, basic_block bb)
kono
parents: 14
diff changeset
1347 {
kono
parents: 14
diff changeset
1348 vec<data_reference_p> drs = vNULL;
kono
parents: 14
diff changeset
1349 vec<tree> writes = vNULL;
kono
parents: 14
diff changeset
1350 vec<scalar_use> reads = vNULL;
kono
parents: 14
diff changeset
1351
kono
parents: 14
diff changeset
1352 sese_l region = scop->scop_info->region;
kono
parents: 14
diff changeset
1353 edge nest = region.entry;
kono
parents: 14
diff changeset
1354 loop_p loop = bb->loop_father;
kono
parents: 14
diff changeset
1355 if (!loop_in_sese_p (loop, region))
kono
parents: 14
diff changeset
1356 loop = NULL;
kono
parents: 14
diff changeset
1357
kono
parents: 14
diff changeset
1358 for (gimple_stmt_iterator gsi = gsi_start_bb (bb); !gsi_end_p (gsi);
kono
parents: 14
diff changeset
1359 gsi_next (&gsi))
kono
parents: 14
diff changeset
1360 {
kono
parents: 14
diff changeset
1361 gimple *stmt = gsi_stmt (gsi);
kono
parents: 14
diff changeset
1362 if (is_gimple_debug (stmt))
kono
parents: 14
diff changeset
1363 continue;
kono
parents: 14
diff changeset
1364
kono
parents: 14
diff changeset
1365 graphite_find_data_references_in_stmt (nest, loop, stmt, &drs);
kono
parents: 14
diff changeset
1366
kono
parents: 14
diff changeset
1367 tree def = gimple_get_lhs (stmt);
kono
parents: 14
diff changeset
1368 if (def)
kono
parents: 14
diff changeset
1369 build_cross_bb_scalars_def (scop, def, gimple_bb (stmt), &writes);
kono
parents: 14
diff changeset
1370
kono
parents: 14
diff changeset
1371 ssa_op_iter iter;
kono
parents: 14
diff changeset
1372 tree use;
kono
parents: 14
diff changeset
1373 FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE)
kono
parents: 14
diff changeset
1374 build_cross_bb_scalars_use (scop, use, stmt, &reads);
kono
parents: 14
diff changeset
1375 }
kono
parents: 14
diff changeset
1376
kono
parents: 14
diff changeset
1377 /* Handle defs and uses in PHIs. Those need special treatment given
kono
parents: 14
diff changeset
1378 that we have to present ISL with sth that looks like we've rewritten
kono
parents: 14
diff changeset
1379 the IL out-of-SSA. */
kono
parents: 14
diff changeset
1380 for (gphi_iterator psi = gsi_start_phis (bb); !gsi_end_p (psi);
kono
parents: 14
diff changeset
1381 gsi_next (&psi))
kono
parents: 14
diff changeset
1382 {
kono
parents: 14
diff changeset
1383 gphi *phi = psi.phi ();
kono
parents: 14
diff changeset
1384 tree res = gimple_phi_result (phi);
kono
parents: 14
diff changeset
1385 if (virtual_operand_p (res)
kono
parents: 14
diff changeset
1386 || scev_analyzable_p (res, scop->scop_info->region))
kono
parents: 14
diff changeset
1387 continue;
kono
parents: 14
diff changeset
1388 /* To simulate out-of-SSA the block containing the PHI node has
kono
parents: 14
diff changeset
1389 reads of the PHI destination. And to preserve SSA dependences
kono
parents: 14
diff changeset
1390 we also write to it (the out-of-SSA decl and the SSA result
kono
parents: 14
diff changeset
1391 are coalesced for dependence purposes which is good enough). */
kono
parents: 14
diff changeset
1392 add_read (&reads, res, phi);
kono
parents: 14
diff changeset
1393 add_write (&writes, res);
kono
parents: 14
diff changeset
1394 }
kono
parents: 14
diff changeset
1395 basic_block bb_for_succs = bb;
kono
parents: 14
diff changeset
1396 if (bb_for_succs == bb_for_succs->loop_father->latch
kono
parents: 14
diff changeset
1397 && bb_in_sese_p (bb_for_succs, scop->scop_info->region)
kono
parents: 14
diff changeset
1398 && sese_trivially_empty_bb_p (bb_for_succs))
kono
parents: 14
diff changeset
1399 bb_for_succs = NULL;
kono
parents: 14
diff changeset
1400 while (bb_for_succs)
kono
parents: 14
diff changeset
1401 {
kono
parents: 14
diff changeset
1402 basic_block latch = NULL;
kono
parents: 14
diff changeset
1403 edge_iterator ei;
kono
parents: 14
diff changeset
1404 edge e;
kono
parents: 14
diff changeset
1405 FOR_EACH_EDGE (e, ei, bb_for_succs->succs)
kono
parents: 14
diff changeset
1406 {
kono
parents: 14
diff changeset
1407 for (gphi_iterator psi = gsi_start_phis (e->dest); !gsi_end_p (psi);
kono
parents: 14
diff changeset
1408 gsi_next (&psi))
kono
parents: 14
diff changeset
1409 {
kono
parents: 14
diff changeset
1410 gphi *phi = psi.phi ();
kono
parents: 14
diff changeset
1411 tree res = gimple_phi_result (phi);
kono
parents: 14
diff changeset
1412 if (virtual_operand_p (res))
kono
parents: 14
diff changeset
1413 continue;
kono
parents: 14
diff changeset
1414 /* To simulate out-of-SSA the predecessor of edges into PHI nodes
kono
parents: 14
diff changeset
1415 has a copy from the PHI argument to the PHI destination. */
kono
parents: 14
diff changeset
1416 if (! scev_analyzable_p (res, scop->scop_info->region))
kono
parents: 14
diff changeset
1417 add_write (&writes, res);
kono
parents: 14
diff changeset
1418 tree use = PHI_ARG_DEF_FROM_EDGE (phi, e);
kono
parents: 14
diff changeset
1419 if (TREE_CODE (use) == SSA_NAME
kono
parents: 14
diff changeset
1420 && ! SSA_NAME_IS_DEFAULT_DEF (use)
kono
parents: 14
diff changeset
1421 && gimple_bb (SSA_NAME_DEF_STMT (use)) != bb_for_succs
kono
parents: 14
diff changeset
1422 && ! scev_analyzable_p (use, scop->scop_info->region))
kono
parents: 14
diff changeset
1423 add_read (&reads, use, phi);
kono
parents: 14
diff changeset
1424 }
kono
parents: 14
diff changeset
1425 if (e->dest == bb_for_succs->loop_father->latch
kono
parents: 14
diff changeset
1426 && bb_in_sese_p (e->dest, scop->scop_info->region)
kono
parents: 14
diff changeset
1427 && sese_trivially_empty_bb_p (e->dest))
kono
parents: 14
diff changeset
1428 latch = e->dest;
kono
parents: 14
diff changeset
1429 }
kono
parents: 14
diff changeset
1430 /* Handle empty latch block PHIs here, otherwise we confuse ISL
kono
parents: 14
diff changeset
1431 with extra conditional code where it then peels off the last
kono
parents: 14
diff changeset
1432 iteration just because of that. It would be simplest if we
kono
parents: 14
diff changeset
1433 just didn't force simple latches (thus remove the forwarder). */
kono
parents: 14
diff changeset
1434 bb_for_succs = latch;
kono
parents: 14
diff changeset
1435 }
kono
parents: 14
diff changeset
1436
kono
parents: 14
diff changeset
1437 /* For the region exit block add reads for all live-out vars. */
kono
parents: 14
diff changeset
1438 if (bb == scop->scop_info->region.exit->src)
kono
parents: 14
diff changeset
1439 {
kono
parents: 14
diff changeset
1440 sese_build_liveouts (scop->scop_info);
kono
parents: 14
diff changeset
1441 unsigned i;
kono
parents: 14
diff changeset
1442 bitmap_iterator bi;
kono
parents: 14
diff changeset
1443 EXECUTE_IF_SET_IN_BITMAP (scop->scop_info->liveout, 0, i, bi)
kono
parents: 14
diff changeset
1444 {
kono
parents: 14
diff changeset
1445 tree use = ssa_name (i);
kono
parents: 14
diff changeset
1446 add_read (&reads, use, NULL);
kono
parents: 14
diff changeset
1447 }
kono
parents: 14
diff changeset
1448 }
kono
parents: 14
diff changeset
1449
kono
parents: 14
diff changeset
1450 if (drs.is_empty () && writes.is_empty () && reads.is_empty ())
kono
parents: 14
diff changeset
1451 return NULL;
kono
parents: 14
diff changeset
1452
kono
parents: 14
diff changeset
1453 return new_gimple_poly_bb (bb, drs, reads, writes);
kono
parents: 14
diff changeset
1454 }
kono
parents: 14
diff changeset
1455
kono
parents: 14
diff changeset
1456 /* Compute alias-sets for all data references in DRS. */
kono
parents: 14
diff changeset
1457
kono
parents: 14
diff changeset
1458 static bool
kono
parents: 14
diff changeset
1459 build_alias_set (scop_p scop)
kono
parents: 14
diff changeset
1460 {
kono
parents: 14
diff changeset
1461 int num_vertices = scop->drs.length ();
kono
parents: 14
diff changeset
1462 struct graph *g = new_graph (num_vertices);
kono
parents: 14
diff changeset
1463 dr_info *dr1, *dr2;
kono
parents: 14
diff changeset
1464 int i, j;
kono
parents: 14
diff changeset
1465 int *all_vertices;
kono
parents: 14
diff changeset
1466
kono
parents: 14
diff changeset
1467 FOR_EACH_VEC_ELT (scop->drs, i, dr1)
kono
parents: 14
diff changeset
1468 for (j = i+1; scop->drs.iterate (j, &dr2); j++)
kono
parents: 14
diff changeset
1469 if (dr_may_alias_p (dr1->dr, dr2->dr, true))
kono
parents: 14
diff changeset
1470 {
kono
parents: 14
diff changeset
1471 /* Dependences in the same alias set need to be handled
kono
parents: 14
diff changeset
1472 by just looking at DR_ACCESS_FNs. */
kono
parents: 14
diff changeset
1473 if (DR_NUM_DIMENSIONS (dr1->dr) == 0
kono
parents: 14
diff changeset
1474 || DR_NUM_DIMENSIONS (dr1->dr) != DR_NUM_DIMENSIONS (dr2->dr)
kono
parents: 14
diff changeset
1475 || ! operand_equal_p (DR_BASE_OBJECT (dr1->dr),
kono
parents: 14
diff changeset
1476 DR_BASE_OBJECT (dr2->dr),
kono
parents: 14
diff changeset
1477 OEP_ADDRESS_OF)
kono
parents: 14
diff changeset
1478 || ! types_compatible_p (TREE_TYPE (DR_BASE_OBJECT (dr1->dr)),
kono
parents: 14
diff changeset
1479 TREE_TYPE (DR_BASE_OBJECT (dr2->dr))))
kono
parents: 14
diff changeset
1480 {
kono
parents: 14
diff changeset
1481 free_graph (g);
kono
parents: 14
diff changeset
1482 return false;
kono
parents: 14
diff changeset
1483 }
kono
parents: 14
diff changeset
1484 add_edge (g, i, j);
kono
parents: 14
diff changeset
1485 add_edge (g, j, i);
kono
parents: 14
diff changeset
1486 }
kono
parents: 14
diff changeset
1487
kono
parents: 14
diff changeset
1488 all_vertices = XNEWVEC (int, num_vertices);
kono
parents: 14
diff changeset
1489 for (i = 0; i < num_vertices; i++)
kono
parents: 14
diff changeset
1490 all_vertices[i] = i;
kono
parents: 14
diff changeset
1491
kono
parents: 14
diff changeset
1492 scop->max_alias_set
kono
parents: 14
diff changeset
1493 = graphds_dfs (g, all_vertices, num_vertices, NULL, true, NULL) + 1;
kono
parents: 14
diff changeset
1494 free (all_vertices);
kono
parents: 14
diff changeset
1495
kono
parents: 14
diff changeset
1496 for (i = 0; i < g->n_vertices; i++)
kono
parents: 14
diff changeset
1497 scop->drs[i].alias_set = g->vertices[i].component + 1;
kono
parents: 14
diff changeset
1498
kono
parents: 14
diff changeset
1499 free_graph (g);
kono
parents: 14
diff changeset
1500 return true;
kono
parents: 14
diff changeset
1501 }
kono
parents: 14
diff changeset
1502
kono
parents: 14
diff changeset
1503 /* Gather BBs and conditions for a SCOP. */
kono
parents: 14
diff changeset
1504 class gather_bbs : public dom_walker
kono
parents: 14
diff changeset
1505 {
kono
parents: 14
diff changeset
1506 public:
kono
parents: 14
diff changeset
1507 gather_bbs (cdi_direction, scop_p, int *);
kono
parents: 14
diff changeset
1508
kono
parents: 14
diff changeset
1509 virtual edge before_dom_children (basic_block);
kono
parents: 14
diff changeset
1510 virtual void after_dom_children (basic_block);
kono
parents: 14
diff changeset
1511
kono
parents: 14
diff changeset
1512 private:
kono
parents: 14
diff changeset
1513 auto_vec<gimple *, 3> conditions, cases;
kono
parents: 14
diff changeset
1514 scop_p scop;
kono
parents: 14
diff changeset
1515 };
kono
parents: 14
diff changeset
1516 }
kono
parents: 14
diff changeset
1517 gather_bbs::gather_bbs (cdi_direction direction, scop_p scop, int *bb_to_rpo)
kono
parents: 14
diff changeset
1518 : dom_walker (direction, false, bb_to_rpo), scop (scop)
kono
parents: 14
diff changeset
1519 {
kono
parents: 14
diff changeset
1520 }
kono
parents: 14
diff changeset
1521
kono
parents: 14
diff changeset
1522 /* Call-back for dom_walk executed before visiting the dominated
kono
parents: 14
diff changeset
1523 blocks. */
kono
parents: 14
diff changeset
1524
kono
parents: 14
diff changeset
1525 edge
kono
parents: 14
diff changeset
1526 gather_bbs::before_dom_children (basic_block bb)
kono
parents: 14
diff changeset
1527 {
kono
parents: 14
diff changeset
1528 sese_info_p region = scop->scop_info;
kono
parents: 14
diff changeset
1529 if (!bb_in_sese_p (bb, region->region))
kono
parents: 14
diff changeset
1530 return dom_walker::STOP;
kono
parents: 14
diff changeset
1531
kono
parents: 14
diff changeset
1532 /* For loops fully contained in the region record parameters in the
kono
parents: 14
diff changeset
1533 loop bounds. */
kono
parents: 14
diff changeset
1534 loop_p loop = bb->loop_father;
kono
parents: 14
diff changeset
1535 if (loop->header == bb
kono
parents: 14
diff changeset
1536 && loop_in_sese_p (loop, region->region))
kono
parents: 14
diff changeset
1537 {
kono
parents: 14
diff changeset
1538 tree nb_iters = number_of_latch_executions (loop);
kono
parents: 14
diff changeset
1539 if (chrec_contains_symbols (nb_iters))
kono
parents: 14
diff changeset
1540 {
kono
parents: 14
diff changeset
1541 nb_iters = scalar_evolution_in_region (region->region,
kono
parents: 14
diff changeset
1542 loop, nb_iters);
kono
parents: 14
diff changeset
1543 scan_tree_for_params (region, nb_iters);
kono
parents: 14
diff changeset
1544 }
kono
parents: 14
diff changeset
1545 }
kono
parents: 14
diff changeset
1546
kono
parents: 14
diff changeset
1547 gcond *stmt = single_pred_cond_non_loop_exit (bb);
kono
parents: 14
diff changeset
1548
kono
parents: 14
diff changeset
1549 if (stmt)
kono
parents: 14
diff changeset
1550 {
kono
parents: 14
diff changeset
1551 edge e = single_pred_edge (bb);
kono
parents: 14
diff changeset
1552
kono
parents: 14
diff changeset
1553 conditions.safe_push (stmt);
kono
parents: 14
diff changeset
1554
kono
parents: 14
diff changeset
1555 if (e->flags & EDGE_TRUE_VALUE)
kono
parents: 14
diff changeset
1556 cases.safe_push (stmt);
kono
parents: 14
diff changeset
1557 else
kono
parents: 14
diff changeset
1558 cases.safe_push (NULL);
kono
parents: 14
diff changeset
1559 }
kono
parents: 14
diff changeset
1560
kono
parents: 14
diff changeset
1561 scop->scop_info->bbs.safe_push (bb);
kono
parents: 14
diff changeset
1562
kono
parents: 14
diff changeset
1563 gimple_poly_bb_p gbb = try_generate_gimple_bb (scop, bb);
kono
parents: 14
diff changeset
1564 if (!gbb)
kono
parents: 14
diff changeset
1565 return NULL;
kono
parents: 14
diff changeset
1566
kono
parents: 14
diff changeset
1567 GBB_CONDITIONS (gbb) = conditions.copy ();
kono
parents: 14
diff changeset
1568 GBB_CONDITION_CASES (gbb) = cases.copy ();
kono
parents: 14
diff changeset
1569
kono
parents: 14
diff changeset
1570 poly_bb_p pbb = new_poly_bb (scop, gbb);
kono
parents: 14
diff changeset
1571 scop->pbbs.safe_push (pbb);
kono
parents: 14
diff changeset
1572
kono
parents: 14
diff changeset
1573 int i;
kono
parents: 14
diff changeset
1574 data_reference_p dr;
kono
parents: 14
diff changeset
1575 FOR_EACH_VEC_ELT (gbb->data_refs, i, dr)
kono
parents: 14
diff changeset
1576 {
kono
parents: 14
diff changeset
1577 DEBUG_PRINT (dp << "Adding memory ";
kono
parents: 14
diff changeset
1578 if (dr->is_read)
kono
parents: 14
diff changeset
1579 dp << "read: ";
kono
parents: 14
diff changeset
1580 else
kono
parents: 14
diff changeset
1581 dp << "write: ";
kono
parents: 14
diff changeset
1582 print_generic_expr (dump_file, dr->ref);
kono
parents: 14
diff changeset
1583 dp << "\nFrom stmt: ";
kono
parents: 14
diff changeset
1584 print_gimple_stmt (dump_file, dr->stmt, 0));
kono
parents: 14
diff changeset
1585
kono
parents: 14
diff changeset
1586 scop->drs.safe_push (dr_info (dr, pbb));
kono
parents: 14
diff changeset
1587 }