Mercurial > hg > CbC > CbC_gcc
annotate gcc/tree-affine.c @ 108:7ad14f446135
add CbC-example/rectypeTest/
| author | Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> |
|---|---|
| date | Thu, 14 Jun 2012 20:30:24 +0900 |
| parents | f6334be47118 |
| children | 04ced10e8804 |
| rev | line source |
|---|---|
| 0 | 1 /* Operations with affine combinations of trees. |
|
63
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
2 Copyright (C) 2005, 2007, 2008, 2010 Free Software Foundation, Inc. |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
3 |
| 0 | 4 This file is part of GCC. |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
5 |
| 0 | 6 GCC is free software; you can redistribute it and/or modify it |
| 7 under the terms of the GNU General Public License as published by the | |
| 8 Free Software Foundation; either version 3, or (at your option) any | |
| 9 later version. | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
10 |
| 0 | 11 GCC is distributed in the hope that it will be useful, but WITHOUT |
| 12 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or | |
| 13 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License | |
| 14 for more details. | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
15 |
| 0 | 16 You should have received a copy of the GNU General Public License |
| 17 along with GCC; see the file COPYING3. If not see | |
| 18 <http://www.gnu.org/licenses/>. */ | |
| 19 | |
| 20 #include "config.h" | |
| 21 #include "system.h" | |
| 22 #include "coretypes.h" | |
| 23 #include "tree.h" | |
| 24 #include "output.h" | |
|
63
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
25 #include "tree-pretty-print.h" |
| 0 | 26 #include "tree-dump.h" |
| 27 #include "pointer-set.h" | |
| 28 #include "tree-affine.h" | |
| 29 #include "gimple.h" | |
| 30 #include "flags.h" | |
| 31 | |
| 32 /* Extends CST as appropriate for the affine combinations COMB. */ | |
| 33 | |
| 34 double_int | |
| 35 double_int_ext_for_comb (double_int cst, aff_tree *comb) | |
| 36 { | |
| 37 return double_int_sext (cst, TYPE_PRECISION (comb->type)); | |
| 38 } | |
| 39 | |
| 40 /* Initializes affine combination COMB so that its value is zero in TYPE. */ | |
| 41 | |
| 42 static void | |
| 43 aff_combination_zero (aff_tree *comb, tree type) | |
| 44 { | |
| 45 comb->type = type; | |
| 46 comb->offset = double_int_zero; | |
| 47 comb->n = 0; | |
| 48 comb->rest = NULL_TREE; | |
| 49 } | |
| 50 | |
| 51 /* Sets COMB to CST. */ | |
| 52 | |
| 53 void | |
| 54 aff_combination_const (aff_tree *comb, tree type, double_int cst) | |
| 55 { | |
| 56 aff_combination_zero (comb, type); | |
| 57 comb->offset = double_int_ext_for_comb (cst, comb); | |
| 58 } | |
| 59 | |
| 60 /* Sets COMB to single element ELT. */ | |
| 61 | |
| 62 void | |
| 63 aff_combination_elt (aff_tree *comb, tree type, tree elt) | |
| 64 { | |
| 65 aff_combination_zero (comb, type); | |
| 66 | |
| 67 comb->n = 1; | |
| 68 comb->elts[0].val = elt; | |
| 69 comb->elts[0].coef = double_int_one; | |
| 70 } | |
| 71 | |
| 72 /* Scales COMB by SCALE. */ | |
| 73 | |
| 74 void | |
| 75 aff_combination_scale (aff_tree *comb, double_int scale) | |
| 76 { | |
| 77 unsigned i, j; | |
| 78 | |
| 79 scale = double_int_ext_for_comb (scale, comb); | |
| 80 if (double_int_one_p (scale)) | |
| 81 return; | |
| 82 | |
| 83 if (double_int_zero_p (scale)) | |
| 84 { | |
| 85 aff_combination_zero (comb, comb->type); | |
| 86 return; | |
| 87 } | |
| 88 | |
| 89 comb->offset | |
| 90 = double_int_ext_for_comb (double_int_mul (scale, comb->offset), comb); | |
| 91 for (i = 0, j = 0; i < comb->n; i++) | |
| 92 { | |
| 93 double_int new_coef; | |
| 94 | |
| 95 new_coef | |
| 96 = double_int_ext_for_comb (double_int_mul (scale, comb->elts[i].coef), | |
| 97 comb); | |
| 98 /* A coefficient may become zero due to overflow. Remove the zero | |
| 99 elements. */ | |
| 100 if (double_int_zero_p (new_coef)) | |
| 101 continue; | |
| 102 comb->elts[j].coef = new_coef; | |
| 103 comb->elts[j].val = comb->elts[i].val; | |
| 104 j++; | |
| 105 } | |
| 106 comb->n = j; | |
| 107 | |
| 108 if (comb->rest) | |
| 109 { | |
| 110 tree type = comb->type; | |
| 111 if (POINTER_TYPE_P (type)) | |
| 112 type = sizetype; | |
| 113 if (comb->n < MAX_AFF_ELTS) | |
| 114 { | |
| 115 comb->elts[comb->n].coef = scale; | |
| 116 comb->elts[comb->n].val = comb->rest; | |
| 117 comb->rest = NULL_TREE; | |
| 118 comb->n++; | |
| 119 } | |
| 120 else | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
121 comb->rest = fold_build2 (MULT_EXPR, type, comb->rest, |
| 0 | 122 double_int_to_tree (type, scale)); |
| 123 } | |
| 124 } | |
| 125 | |
| 126 /* Adds ELT * SCALE to COMB. */ | |
| 127 | |
| 128 void | |
| 129 aff_combination_add_elt (aff_tree *comb, tree elt, double_int scale) | |
| 130 { | |
| 131 unsigned i; | |
| 132 tree type; | |
| 133 | |
| 134 scale = double_int_ext_for_comb (scale, comb); | |
| 135 if (double_int_zero_p (scale)) | |
| 136 return; | |
| 137 | |
| 138 for (i = 0; i < comb->n; i++) | |
| 139 if (operand_equal_p (comb->elts[i].val, elt, 0)) | |
| 140 { | |
| 141 double_int new_coef; | |
| 142 | |
| 143 new_coef = double_int_add (comb->elts[i].coef, scale); | |
| 144 new_coef = double_int_ext_for_comb (new_coef, comb); | |
| 145 if (!double_int_zero_p (new_coef)) | |
| 146 { | |
| 147 comb->elts[i].coef = new_coef; | |
| 148 return; | |
| 149 } | |
| 150 | |
| 151 comb->n--; | |
| 152 comb->elts[i] = comb->elts[comb->n]; | |
| 153 | |
| 154 if (comb->rest) | |
| 155 { | |
| 156 gcc_assert (comb->n == MAX_AFF_ELTS - 1); | |
| 157 comb->elts[comb->n].coef = double_int_one; | |
| 158 comb->elts[comb->n].val = comb->rest; | |
| 159 comb->rest = NULL_TREE; | |
| 160 comb->n++; | |
| 161 } | |
| 162 return; | |
| 163 } | |
| 164 if (comb->n < MAX_AFF_ELTS) | |
| 165 { | |
| 166 comb->elts[comb->n].coef = scale; | |
| 167 comb->elts[comb->n].val = elt; | |
| 168 comb->n++; | |
| 169 return; | |
| 170 } | |
| 171 | |
| 172 type = comb->type; | |
| 173 if (POINTER_TYPE_P (type)) | |
| 174 type = sizetype; | |
| 175 | |
| 176 if (double_int_one_p (scale)) | |
| 177 elt = fold_convert (type, elt); | |
| 178 else | |
| 179 elt = fold_build2 (MULT_EXPR, type, | |
| 180 fold_convert (type, elt), | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
181 double_int_to_tree (type, scale)); |
| 0 | 182 |
| 183 if (comb->rest) | |
| 184 comb->rest = fold_build2 (PLUS_EXPR, type, comb->rest, | |
| 185 elt); | |
| 186 else | |
| 187 comb->rest = elt; | |
| 188 } | |
| 189 | |
| 190 /* Adds CST to C. */ | |
| 191 | |
| 192 static void | |
| 193 aff_combination_add_cst (aff_tree *c, double_int cst) | |
| 194 { | |
| 195 c->offset = double_int_ext_for_comb (double_int_add (c->offset, cst), c); | |
| 196 } | |
| 197 | |
| 198 /* Adds COMB2 to COMB1. */ | |
| 199 | |
| 200 void | |
| 201 aff_combination_add (aff_tree *comb1, aff_tree *comb2) | |
| 202 { | |
| 203 unsigned i; | |
| 204 | |
| 205 aff_combination_add_cst (comb1, comb2->offset); | |
| 206 for (i = 0; i < comb2->n; i++) | |
| 207 aff_combination_add_elt (comb1, comb2->elts[i].val, comb2->elts[i].coef); | |
| 208 if (comb2->rest) | |
| 209 aff_combination_add_elt (comb1, comb2->rest, double_int_one); | |
| 210 } | |
| 211 | |
| 212 /* Converts affine combination COMB to TYPE. */ | |
| 213 | |
| 214 void | |
| 215 aff_combination_convert (aff_tree *comb, tree type) | |
| 216 { | |
| 217 unsigned i, j; | |
| 218 tree comb_type = comb->type; | |
| 219 | |
| 220 if (TYPE_PRECISION (type) > TYPE_PRECISION (comb_type)) | |
| 221 { | |
| 222 tree val = fold_convert (type, aff_combination_to_tree (comb)); | |
| 223 tree_to_aff_combination (val, type, comb); | |
| 224 return; | |
| 225 } | |
| 226 | |
| 227 comb->type = type; | |
| 228 if (comb->rest && !POINTER_TYPE_P (type)) | |
| 229 comb->rest = fold_convert (type, comb->rest); | |
| 230 | |
| 231 if (TYPE_PRECISION (type) == TYPE_PRECISION (comb_type)) | |
| 232 return; | |
| 233 | |
| 234 comb->offset = double_int_ext_for_comb (comb->offset, comb); | |
| 235 for (i = j = 0; i < comb->n; i++) | |
| 236 { | |
| 237 double_int new_coef = double_int_ext_for_comb (comb->elts[i].coef, comb); | |
| 238 if (double_int_zero_p (new_coef)) | |
| 239 continue; | |
| 240 comb->elts[j].coef = new_coef; | |
| 241 comb->elts[j].val = fold_convert (type, comb->elts[i].val); | |
| 242 j++; | |
| 243 } | |
| 244 | |
| 245 comb->n = j; | |
| 246 if (comb->n < MAX_AFF_ELTS && comb->rest) | |
| 247 { | |
| 248 comb->elts[comb->n].coef = double_int_one; | |
| 249 comb->elts[comb->n].val = comb->rest; | |
| 250 comb->rest = NULL_TREE; | |
| 251 comb->n++; | |
| 252 } | |
| 253 } | |
| 254 | |
| 255 /* Splits EXPR into an affine combination of parts. */ | |
| 256 | |
| 257 void | |
| 258 tree_to_aff_combination (tree expr, tree type, aff_tree *comb) | |
| 259 { | |
| 260 aff_tree tmp; | |
| 261 enum tree_code code; | |
| 262 tree cst, core, toffset; | |
| 263 HOST_WIDE_INT bitpos, bitsize; | |
| 264 enum machine_mode mode; | |
| 265 int unsignedp, volatilep; | |
| 266 | |
| 267 STRIP_NOPS (expr); | |
| 268 | |
| 269 code = TREE_CODE (expr); | |
| 270 switch (code) | |
| 271 { | |
| 272 case INTEGER_CST: | |
| 273 aff_combination_const (comb, type, tree_to_double_int (expr)); | |
| 274 return; | |
| 275 | |
| 276 case POINTER_PLUS_EXPR: | |
| 277 tree_to_aff_combination (TREE_OPERAND (expr, 0), type, comb); | |
| 278 tree_to_aff_combination (TREE_OPERAND (expr, 1), sizetype, &tmp); | |
| 279 aff_combination_add (comb, &tmp); | |
| 280 return; | |
| 281 | |
| 282 case PLUS_EXPR: | |
| 283 case MINUS_EXPR: | |
| 284 tree_to_aff_combination (TREE_OPERAND (expr, 0), type, comb); | |
| 285 tree_to_aff_combination (TREE_OPERAND (expr, 1), type, &tmp); | |
| 286 if (code == MINUS_EXPR) | |
| 287 aff_combination_scale (&tmp, double_int_minus_one); | |
| 288 aff_combination_add (comb, &tmp); | |
| 289 return; | |
| 290 | |
| 291 case MULT_EXPR: | |
| 292 cst = TREE_OPERAND (expr, 1); | |
| 293 if (TREE_CODE (cst) != INTEGER_CST) | |
| 294 break; | |
| 295 tree_to_aff_combination (TREE_OPERAND (expr, 0), type, comb); | |
| 296 aff_combination_scale (comb, tree_to_double_int (cst)); | |
| 297 return; | |
| 298 | |
| 299 case NEGATE_EXPR: | |
| 300 tree_to_aff_combination (TREE_OPERAND (expr, 0), type, comb); | |
| 301 aff_combination_scale (comb, double_int_minus_one); | |
| 302 return; | |
| 303 | |
| 304 case BIT_NOT_EXPR: | |
| 305 /* ~x = -x - 1 */ | |
| 306 tree_to_aff_combination (TREE_OPERAND (expr, 0), type, comb); | |
| 307 aff_combination_scale (comb, double_int_minus_one); | |
| 308 aff_combination_add_cst (comb, double_int_minus_one); | |
| 309 return; | |
| 310 | |
| 311 case ADDR_EXPR: | |
|
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
312 /* Handle &MEM[ptr + CST] which is equivalent to POINTER_PLUS_EXPR. */ |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
313 if (TREE_CODE (TREE_OPERAND (expr, 0)) == MEM_REF) |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
314 { |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
315 expr = TREE_OPERAND (expr, 0); |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
316 tree_to_aff_combination (TREE_OPERAND (expr, 0), type, comb); |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
317 tree_to_aff_combination (TREE_OPERAND (expr, 1), sizetype, &tmp); |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
318 aff_combination_add (comb, &tmp); |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
319 return; |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
320 } |
| 0 | 321 core = get_inner_reference (TREE_OPERAND (expr, 0), &bitsize, &bitpos, |
| 322 &toffset, &mode, &unsignedp, &volatilep, | |
| 323 false); | |
| 324 if (bitpos % BITS_PER_UNIT != 0) | |
| 325 break; | |
| 326 aff_combination_const (comb, type, | |
| 327 uhwi_to_double_int (bitpos / BITS_PER_UNIT)); | |
| 328 core = build_fold_addr_expr (core); | |
| 329 if (TREE_CODE (core) == ADDR_EXPR) | |
| 330 aff_combination_add_elt (comb, core, double_int_one); | |
| 331 else | |
| 332 { | |
| 333 tree_to_aff_combination (core, type, &tmp); | |
| 334 aff_combination_add (comb, &tmp); | |
| 335 } | |
| 336 if (toffset) | |
| 337 { | |
| 338 tree_to_aff_combination (toffset, type, &tmp); | |
| 339 aff_combination_add (comb, &tmp); | |
| 340 } | |
| 341 return; | |
| 342 | |
|
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
343 case MEM_REF: |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
344 if (TREE_CODE (TREE_OPERAND (expr, 0)) == ADDR_EXPR) |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
345 tree_to_aff_combination (TREE_OPERAND (TREE_OPERAND (expr, 0), 0), |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
346 type, comb); |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
347 else if (integer_zerop (TREE_OPERAND (expr, 1))) |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
348 { |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
349 aff_combination_elt (comb, type, expr); |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
350 return; |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
351 } |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
352 else |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
353 aff_combination_elt (comb, type, |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
354 build2 (MEM_REF, TREE_TYPE (expr), |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
355 TREE_OPERAND (expr, 0), |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
356 build_int_cst |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
357 (TREE_TYPE (TREE_OPERAND (expr, 1)), 0))); |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
358 tree_to_aff_combination (TREE_OPERAND (expr, 1), sizetype, &tmp); |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
359 aff_combination_add (comb, &tmp); |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
360 return; |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
361 |
| 0 | 362 default: |
| 363 break; | |
| 364 } | |
| 365 | |
| 366 aff_combination_elt (comb, type, expr); | |
| 367 } | |
| 368 | |
| 369 /* Creates EXPR + ELT * SCALE in TYPE. EXPR is taken from affine | |
| 370 combination COMB. */ | |
| 371 | |
| 372 static tree | |
| 373 add_elt_to_tree (tree expr, tree type, tree elt, double_int scale, | |
| 374 aff_tree *comb) | |
| 375 { | |
| 376 enum tree_code code; | |
| 377 tree type1 = type; | |
| 378 if (POINTER_TYPE_P (type)) | |
| 379 type1 = sizetype; | |
| 380 | |
| 381 scale = double_int_ext_for_comb (scale, comb); | |
| 382 elt = fold_convert (type1, elt); | |
| 383 | |
| 384 if (double_int_one_p (scale)) | |
| 385 { | |
| 386 if (!expr) | |
| 387 return fold_convert (type, elt); | |
| 388 | |
| 389 if (POINTER_TYPE_P (type)) | |
| 390 return fold_build2 (POINTER_PLUS_EXPR, type, expr, elt); | |
| 391 return fold_build2 (PLUS_EXPR, type, expr, elt); | |
| 392 } | |
| 393 | |
| 394 if (double_int_minus_one_p (scale)) | |
| 395 { | |
| 396 if (!expr) | |
| 397 return fold_convert (type, fold_build1 (NEGATE_EXPR, type1, elt)); | |
| 398 | |
| 399 if (POINTER_TYPE_P (type)) | |
| 400 { | |
| 401 elt = fold_build1 (NEGATE_EXPR, type1, elt); | |
| 402 return fold_build2 (POINTER_PLUS_EXPR, type, expr, elt); | |
| 403 } | |
| 404 return fold_build2 (MINUS_EXPR, type, expr, elt); | |
| 405 } | |
| 406 | |
| 407 if (!expr) | |
| 408 return fold_convert (type, | |
| 409 fold_build2 (MULT_EXPR, type1, elt, | |
| 410 double_int_to_tree (type1, scale))); | |
| 411 | |
| 412 if (double_int_negative_p (scale)) | |
| 413 { | |
| 414 code = MINUS_EXPR; | |
| 415 scale = double_int_neg (scale); | |
| 416 } | |
| 417 else | |
| 418 code = PLUS_EXPR; | |
| 419 | |
| 420 elt = fold_build2 (MULT_EXPR, type1, elt, | |
| 421 double_int_to_tree (type1, scale)); | |
| 422 if (POINTER_TYPE_P (type)) | |
| 423 { | |
| 424 if (code == MINUS_EXPR) | |
| 425 elt = fold_build1 (NEGATE_EXPR, type1, elt); | |
| 426 return fold_build2 (POINTER_PLUS_EXPR, type, expr, elt); | |
| 427 } | |
| 428 return fold_build2 (code, type, expr, elt); | |
| 429 } | |
| 430 | |
| 431 /* Makes tree from the affine combination COMB. */ | |
| 432 | |
| 433 tree | |
| 434 aff_combination_to_tree (aff_tree *comb) | |
| 435 { | |
| 436 tree type = comb->type; | |
|
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
437 tree expr = NULL_TREE; |
| 0 | 438 unsigned i; |
| 439 double_int off, sgn; | |
| 440 tree type1 = type; | |
| 441 if (POINTER_TYPE_P (type)) | |
| 442 type1 = sizetype; | |
| 443 | |
| 444 gcc_assert (comb->n == MAX_AFF_ELTS || comb->rest == NULL_TREE); | |
| 445 | |
| 446 for (i = 0; i < comb->n; i++) | |
| 447 expr = add_elt_to_tree (expr, type, comb->elts[i].val, comb->elts[i].coef, | |
| 448 comb); | |
| 449 | |
|
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
450 if (comb->rest) |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
451 expr = add_elt_to_tree (expr, type, comb->rest, double_int_one, comb); |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
452 |
| 0 | 453 /* Ensure that we get x - 1, not x + (-1) or x + 0xff..f if x is |
| 454 unsigned. */ | |
| 455 if (double_int_negative_p (comb->offset)) | |
| 456 { | |
| 457 off = double_int_neg (comb->offset); | |
| 458 sgn = double_int_minus_one; | |
| 459 } | |
| 460 else | |
| 461 { | |
| 462 off = comb->offset; | |
| 463 sgn = double_int_one; | |
| 464 } | |
| 465 return add_elt_to_tree (expr, type, double_int_to_tree (type1, off), sgn, | |
| 466 comb); | |
| 467 } | |
| 468 | |
| 469 /* Copies the tree elements of COMB to ensure that they are not shared. */ | |
| 470 | |
| 471 void | |
| 472 unshare_aff_combination (aff_tree *comb) | |
| 473 { | |
| 474 unsigned i; | |
| 475 | |
| 476 for (i = 0; i < comb->n; i++) | |
| 477 comb->elts[i].val = unshare_expr (comb->elts[i].val); | |
| 478 if (comb->rest) | |
| 479 comb->rest = unshare_expr (comb->rest); | |
| 480 } | |
| 481 | |
| 482 /* Remove M-th element from COMB. */ | |
| 483 | |
| 484 void | |
| 485 aff_combination_remove_elt (aff_tree *comb, unsigned m) | |
| 486 { | |
| 487 comb->n--; | |
| 488 if (m <= comb->n) | |
| 489 comb->elts[m] = comb->elts[comb->n]; | |
| 490 if (comb->rest) | |
| 491 { | |
| 492 comb->elts[comb->n].coef = double_int_one; | |
| 493 comb->elts[comb->n].val = comb->rest; | |
| 494 comb->rest = NULL_TREE; | |
| 495 comb->n++; | |
| 496 } | |
| 497 } | |
| 498 | |
| 499 /* Adds C * COEF * VAL to R. VAL may be NULL, in that case only | |
| 500 C * COEF is added to R. */ | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
501 |
| 0 | 502 |
| 503 static void | |
| 504 aff_combination_add_product (aff_tree *c, double_int coef, tree val, | |
| 505 aff_tree *r) | |
| 506 { | |
| 507 unsigned i; | |
| 508 tree aval, type; | |
| 509 | |
| 510 for (i = 0; i < c->n; i++) | |
| 511 { | |
| 512 aval = c->elts[i].val; | |
| 513 if (val) | |
| 514 { | |
| 515 type = TREE_TYPE (aval); | |
| 516 aval = fold_build2 (MULT_EXPR, type, aval, | |
| 517 fold_convert (type, val)); | |
| 518 } | |
| 519 | |
| 520 aff_combination_add_elt (r, aval, | |
| 521 double_int_mul (coef, c->elts[i].coef)); | |
| 522 } | |
| 523 | |
| 524 if (c->rest) | |
| 525 { | |
| 526 aval = c->rest; | |
| 527 if (val) | |
| 528 { | |
| 529 type = TREE_TYPE (aval); | |
| 530 aval = fold_build2 (MULT_EXPR, type, aval, | |
| 531 fold_convert (type, val)); | |
| 532 } | |
| 533 | |
| 534 aff_combination_add_elt (r, aval, coef); | |
| 535 } | |
| 536 | |
| 537 if (val) | |
| 538 aff_combination_add_elt (r, val, | |
| 539 double_int_mul (coef, c->offset)); | |
| 540 else | |
| 541 aff_combination_add_cst (r, double_int_mul (coef, c->offset)); | |
| 542 } | |
| 543 | |
| 544 /* Multiplies C1 by C2, storing the result to R */ | |
| 545 | |
| 546 void | |
| 547 aff_combination_mult (aff_tree *c1, aff_tree *c2, aff_tree *r) | |
| 548 { | |
| 549 unsigned i; | |
| 550 gcc_assert (TYPE_PRECISION (c1->type) == TYPE_PRECISION (c2->type)); | |
| 551 | |
| 552 aff_combination_zero (r, c1->type); | |
| 553 | |
| 554 for (i = 0; i < c2->n; i++) | |
| 555 aff_combination_add_product (c1, c2->elts[i].coef, c2->elts[i].val, r); | |
| 556 if (c2->rest) | |
| 557 aff_combination_add_product (c1, double_int_one, c2->rest, r); | |
| 558 aff_combination_add_product (c1, c2->offset, NULL, r); | |
| 559 } | |
| 560 | |
| 561 /* Returns the element of COMB whose value is VAL, or NULL if no such | |
| 562 element exists. If IDX is not NULL, it is set to the index of VAL in | |
| 563 COMB. */ | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
564 |
| 0 | 565 static struct aff_comb_elt * |
| 566 aff_combination_find_elt (aff_tree *comb, tree val, unsigned *idx) | |
| 567 { | |
| 568 unsigned i; | |
| 569 | |
| 570 for (i = 0; i < comb->n; i++) | |
| 571 if (operand_equal_p (comb->elts[i].val, val, 0)) | |
| 572 { | |
| 573 if (idx) | |
| 574 *idx = i; | |
| 575 | |
| 576 return &comb->elts[i]; | |
| 577 } | |
| 578 | |
| 579 return NULL; | |
| 580 } | |
| 581 | |
| 582 /* Element of the cache that maps ssa name NAME to its expanded form | |
| 583 as an affine expression EXPANSION. */ | |
| 584 | |
| 585 struct name_expansion | |
| 586 { | |
| 587 aff_tree expansion; | |
| 588 | |
| 589 /* True if the expansion for the name is just being generated. */ | |
| 590 unsigned in_progress : 1; | |
| 591 }; | |
| 592 | |
| 593 /* Expands SSA names in COMB recursively. CACHE is used to cache the | |
| 594 results. */ | |
| 595 | |
| 596 void | |
| 597 aff_combination_expand (aff_tree *comb ATTRIBUTE_UNUSED, | |
| 598 struct pointer_map_t **cache ATTRIBUTE_UNUSED) | |
| 599 { | |
| 600 unsigned i; | |
| 601 aff_tree to_add, current, curre; | |
| 602 tree e, rhs; | |
| 603 gimple def; | |
| 604 double_int scale; | |
| 605 void **slot; | |
| 606 struct name_expansion *exp; | |
| 607 | |
| 608 aff_combination_zero (&to_add, comb->type); | |
| 609 for (i = 0; i < comb->n; i++) | |
| 610 { | |
| 611 tree type, name; | |
| 612 enum tree_code code; | |
| 613 | |
| 614 e = comb->elts[i].val; | |
| 615 type = TREE_TYPE (e); | |
| 616 name = e; | |
| 617 /* Look through some conversions. */ | |
| 618 if (TREE_CODE (e) == NOP_EXPR | |
| 619 && (TYPE_PRECISION (type) | |
| 620 >= TYPE_PRECISION (TREE_TYPE (TREE_OPERAND (e, 0))))) | |
| 621 name = TREE_OPERAND (e, 0); | |
| 622 if (TREE_CODE (name) != SSA_NAME) | |
| 623 continue; | |
| 624 def = SSA_NAME_DEF_STMT (name); | |
| 625 if (!is_gimple_assign (def) || gimple_assign_lhs (def) != name) | |
| 626 continue; | |
| 627 | |
| 628 code = gimple_assign_rhs_code (def); | |
| 629 if (code != SSA_NAME | |
| 630 && !IS_EXPR_CODE_CLASS (TREE_CODE_CLASS (code)) | |
| 631 && (get_gimple_rhs_class (code) != GIMPLE_SINGLE_RHS | |
| 632 || !is_gimple_min_invariant (gimple_assign_rhs1 (def)))) | |
| 633 continue; | |
| 634 | |
| 635 /* We do not know whether the reference retains its value at the | |
| 636 place where the expansion is used. */ | |
| 637 if (TREE_CODE_CLASS (code) == tcc_reference) | |
| 638 continue; | |
| 639 | |
| 640 if (!*cache) | |
| 641 *cache = pointer_map_create (); | |
| 642 slot = pointer_map_insert (*cache, e); | |
| 643 exp = (struct name_expansion *) *slot; | |
| 644 | |
| 645 if (!exp) | |
| 646 { | |
| 647 exp = XNEW (struct name_expansion); | |
| 648 exp->in_progress = 1; | |
| 649 *slot = exp; | |
| 650 /* In principle this is a generally valid folding, but | |
| 651 it is not unconditionally an optimization, so do it | |
| 652 here and not in fold_unary. */ | |
| 653 /* Convert (T1)(X *+- CST) into (T1)X *+- (T1)CST if T1 is wider | |
| 654 than the type of X and overflow for the type of X is | |
| 655 undefined. */ | |
| 656 if (e != name | |
| 657 && INTEGRAL_TYPE_P (type) | |
| 658 && INTEGRAL_TYPE_P (TREE_TYPE (name)) | |
| 659 && TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (name)) | |
| 660 && TYPE_PRECISION (type) > TYPE_PRECISION (TREE_TYPE (name)) | |
| 661 && (code == PLUS_EXPR || code == MINUS_EXPR || code == MULT_EXPR) | |
| 662 && TREE_CODE (gimple_assign_rhs2 (def)) == INTEGER_CST) | |
| 663 rhs = fold_build2 (code, type, | |
| 664 fold_convert (type, gimple_assign_rhs1 (def)), | |
| 665 fold_convert (type, gimple_assign_rhs2 (def))); | |
| 666 else | |
| 667 { | |
| 668 rhs = gimple_assign_rhs_to_tree (def); | |
| 669 if (e != name) | |
| 670 rhs = fold_convert (type, rhs); | |
| 671 } | |
| 672 tree_to_aff_combination_expand (rhs, comb->type, ¤t, cache); | |
| 673 exp->expansion = current; | |
| 674 exp->in_progress = 0; | |
| 675 } | |
| 676 else | |
| 677 { | |
| 678 /* Since we follow the definitions in the SSA form, we should not | |
| 679 enter a cycle unless we pass through a phi node. */ | |
| 680 gcc_assert (!exp->in_progress); | |
| 681 current = exp->expansion; | |
| 682 } | |
| 683 | |
| 684 /* Accumulate the new terms to TO_ADD, so that we do not modify | |
| 685 COMB while traversing it; include the term -coef * E, to remove | |
| 686 it from COMB. */ | |
| 687 scale = comb->elts[i].coef; | |
| 688 aff_combination_zero (&curre, comb->type); | |
| 689 aff_combination_add_elt (&curre, e, double_int_neg (scale)); | |
| 690 aff_combination_scale (¤t, scale); | |
| 691 aff_combination_add (&to_add, ¤t); | |
| 692 aff_combination_add (&to_add, &curre); | |
| 693 } | |
| 694 aff_combination_add (comb, &to_add); | |
| 695 } | |
| 696 | |
| 697 /* Similar to tree_to_aff_combination, but follows SSA name definitions | |
| 698 and expands them recursively. CACHE is used to cache the expansions | |
| 699 of the ssa names, to avoid exponential time complexity for cases | |
| 700 like | |
| 701 | |
| 702 a1 = a0 + a0; | |
| 703 a2 = a1 + a1; | |
| 704 a3 = a2 + a2; | |
| 705 ... */ | |
| 706 | |
| 707 void | |
| 708 tree_to_aff_combination_expand (tree expr, tree type, aff_tree *comb, | |
| 709 struct pointer_map_t **cache) | |
| 710 { | |
| 711 tree_to_aff_combination (expr, type, comb); | |
| 712 aff_combination_expand (comb, cache); | |
| 713 } | |
| 714 | |
| 715 /* Frees memory occupied by struct name_expansion in *VALUE. Callback for | |
| 716 pointer_map_traverse. */ | |
| 717 | |
| 718 static bool | |
| 719 free_name_expansion (const void *key ATTRIBUTE_UNUSED, void **value, | |
| 720 void *data ATTRIBUTE_UNUSED) | |
| 721 { | |
| 722 struct name_expansion *const exp = (struct name_expansion *) *value; | |
| 723 | |
| 724 free (exp); | |
| 725 return true; | |
| 726 } | |
| 727 | |
| 728 /* Frees memory allocated for the CACHE used by | |
| 729 tree_to_aff_combination_expand. */ | |
| 730 | |
| 731 void | |
| 732 free_affine_expand_cache (struct pointer_map_t **cache) | |
| 733 { | |
| 734 if (!*cache) | |
| 735 return; | |
| 736 | |
| 737 pointer_map_traverse (*cache, free_name_expansion, NULL); | |
| 738 pointer_map_destroy (*cache); | |
| 739 *cache = NULL; | |
| 740 } | |
| 741 | |
| 742 /* If VAL != CST * DIV for any constant CST, returns false. | |
| 743 Otherwise, if VAL != 0 (and hence CST != 0), and *MULT_SET is true, | |
| 744 additionally compares CST and MULT, and if they are different, | |
| 745 returns false. Finally, if neither of these two cases occur, | |
| 746 true is returned, and if CST != 0, CST is stored to MULT and | |
| 747 MULT_SET is set to true. */ | |
| 748 | |
| 749 static bool | |
| 750 double_int_constant_multiple_p (double_int val, double_int div, | |
| 751 bool *mult_set, double_int *mult) | |
| 752 { | |
| 753 double_int rem, cst; | |
| 754 | |
| 755 if (double_int_zero_p (val)) | |
| 756 return true; | |
| 757 | |
| 758 if (double_int_zero_p (div)) | |
| 759 return false; | |
| 760 | |
| 761 cst = double_int_sdivmod (val, div, FLOOR_DIV_EXPR, &rem); | |
| 762 if (!double_int_zero_p (rem)) | |
| 763 return false; | |
| 764 | |
| 765 if (*mult_set && !double_int_equal_p (*mult, cst)) | |
| 766 return false; | |
| 767 | |
| 768 *mult_set = true; | |
| 769 *mult = cst; | |
| 770 return true; | |
| 771 } | |
| 772 | |
| 773 /* Returns true if VAL = X * DIV for some constant X. If this is the case, | |
| 774 X is stored to MULT. */ | |
| 775 | |
| 776 bool | |
| 777 aff_combination_constant_multiple_p (aff_tree *val, aff_tree *div, | |
| 778 double_int *mult) | |
| 779 { | |
| 780 bool mult_set = false; | |
| 781 unsigned i; | |
| 782 | |
| 783 if (val->n == 0 && double_int_zero_p (val->offset)) | |
| 784 { | |
| 785 *mult = double_int_zero; | |
| 786 return true; | |
| 787 } | |
| 788 if (val->n != div->n) | |
| 789 return false; | |
| 790 | |
| 791 if (val->rest || div->rest) | |
| 792 return false; | |
| 793 | |
| 794 if (!double_int_constant_multiple_p (val->offset, div->offset, | |
| 795 &mult_set, mult)) | |
| 796 return false; | |
| 797 | |
| 798 for (i = 0; i < div->n; i++) | |
| 799 { | |
| 800 struct aff_comb_elt *elt | |
| 801 = aff_combination_find_elt (val, div->elts[i].val, NULL); | |
| 802 if (!elt) | |
| 803 return false; | |
| 804 if (!double_int_constant_multiple_p (elt->coef, div->elts[i].coef, | |
| 805 &mult_set, mult)) | |
| 806 return false; | |
| 807 } | |
| 808 | |
| 809 gcc_assert (mult_set); | |
| 810 return true; | |
| 811 } | |
| 812 | |
| 813 /* Prints the affine VAL to the FILE. */ | |
| 814 | |
| 815 void | |
| 816 print_aff (FILE *file, aff_tree *val) | |
| 817 { | |
| 818 unsigned i; | |
| 819 bool uns = TYPE_UNSIGNED (val->type); | |
| 820 if (POINTER_TYPE_P (val->type)) | |
| 821 uns = false; | |
| 822 fprintf (file, "{\n type = "); | |
| 823 print_generic_expr (file, val->type, TDF_VOPS|TDF_MEMSYMS); | |
| 824 fprintf (file, "\n offset = "); | |
| 825 dump_double_int (file, val->offset, uns); | |
| 826 if (val->n > 0) | |
| 827 { | |
| 828 fprintf (file, "\n elements = {\n"); | |
| 829 for (i = 0; i < val->n; i++) | |
| 830 { | |
| 831 fprintf (file, " [%d] = ", i); | |
| 832 print_generic_expr (file, val->elts[i].val, TDF_VOPS|TDF_MEMSYMS); | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
833 |
| 0 | 834 fprintf (file, " * "); |
| 835 dump_double_int (file, val->elts[i].coef, uns); | |
| 836 if (i != val->n - 1) | |
| 837 fprintf (file, ", \n"); | |
| 838 } | |
| 839 fprintf (file, "\n }"); | |
| 840 } | |
| 841 if (val->rest) | |
| 842 { | |
| 843 fprintf (file, "\n rest = "); | |
| 844 print_generic_expr (file, val->rest, TDF_VOPS|TDF_MEMSYMS); | |
| 845 } | |
| 846 fprintf (file, "\n}"); | |
| 847 } | |
| 848 | |
| 849 /* Prints the affine VAL to the standard error, used for debugging. */ | |
| 850 | |
|
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
851 DEBUG_FUNCTION void |
| 0 | 852 debug_aff (aff_tree *val) |
| 853 { | |
| 854 print_aff (stderr, val); | |
| 855 fprintf (stderr, "\n"); | |
| 856 } | |
| 857 | |
| 858 /* Returns address of the reference REF in ADDR. The size of the accessed | |
| 859 location is stored to SIZE. */ | |
| 860 | |
| 861 void | |
| 862 get_inner_reference_aff (tree ref, aff_tree *addr, double_int *size) | |
| 863 { | |
| 864 HOST_WIDE_INT bitsize, bitpos; | |
| 865 tree toff; | |
| 866 enum machine_mode mode; | |
| 867 int uns, vol; | |
| 868 aff_tree tmp; | |
| 869 tree base = get_inner_reference (ref, &bitsize, &bitpos, &toff, &mode, | |
| 870 &uns, &vol, false); | |
| 871 tree base_addr = build_fold_addr_expr (base); | |
| 872 | |
| 873 /* ADDR = &BASE + TOFF + BITPOS / BITS_PER_UNIT. */ | |
| 874 | |
| 875 tree_to_aff_combination (base_addr, sizetype, addr); | |
| 876 | |
| 877 if (toff) | |
| 878 { | |
| 879 tree_to_aff_combination (toff, sizetype, &tmp); | |
| 880 aff_combination_add (addr, &tmp); | |
| 881 } | |
| 882 | |
| 883 aff_combination_const (&tmp, sizetype, | |
| 884 shwi_to_double_int (bitpos / BITS_PER_UNIT)); | |
| 885 aff_combination_add (addr, &tmp); | |
| 886 | |
| 887 *size = shwi_to_double_int ((bitsize + BITS_PER_UNIT - 1) / BITS_PER_UNIT); | |
| 888 } | |
| 889 |