Mercurial > hg > CbC > CbC_gcc
comparison gcc/tree-scalar-evolution.c @ 111:04ced10e8804
gcc 7
author | kono |
---|---|
date | Fri, 27 Oct 2017 22:46:09 +0900 |
parents | f6334be47118 |
children | 84e7813d76e9 |
comparison
equal
deleted
inserted
replaced
68:561a7518be6b | 111:04ced10e8804 |
---|---|
1 /* Scalar evolution detector. | 1 /* Scalar evolution detector. |
2 Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010 | 2 Copyright (C) 2003-2017 Free Software Foundation, Inc. |
3 Free Software Foundation, Inc. | |
4 Contributed by Sebastian Pop <s.pop@laposte.net> | 3 Contributed by Sebastian Pop <s.pop@laposte.net> |
5 | 4 |
6 This file is part of GCC. | 5 This file is part of GCC. |
7 | 6 |
8 GCC is free software; you can redistribute it and/or modify it under | 7 GCC is free software; you can redistribute it and/or modify it under |
255 */ | 254 */ |
256 | 255 |
257 #include "config.h" | 256 #include "config.h" |
258 #include "system.h" | 257 #include "system.h" |
259 #include "coretypes.h" | 258 #include "coretypes.h" |
259 #include "backend.h" | |
260 #include "rtl.h" | |
261 #include "tree.h" | |
262 #include "gimple.h" | |
263 #include "ssa.h" | |
260 #include "gimple-pretty-print.h" | 264 #include "gimple-pretty-print.h" |
261 #include "tree-flow.h" | 265 #include "fold-const.h" |
266 #include "gimplify.h" | |
267 #include "gimple-iterator.h" | |
268 #include "gimplify-me.h" | |
269 #include "tree-cfg.h" | |
270 #include "tree-ssa-loop-ivopts.h" | |
271 #include "tree-ssa-loop-manip.h" | |
272 #include "tree-ssa-loop-niter.h" | |
273 #include "tree-ssa-loop.h" | |
274 #include "tree-ssa.h" | |
262 #include "cfgloop.h" | 275 #include "cfgloop.h" |
263 #include "tree-chrec.h" | 276 #include "tree-chrec.h" |
277 #include "tree-affine.h" | |
264 #include "tree-scalar-evolution.h" | 278 #include "tree-scalar-evolution.h" |
265 #include "tree-pass.h" | 279 #include "dumpfile.h" |
266 #include "params.h" | 280 #include "params.h" |
267 | 281 #include "tree-ssa-propagate.h" |
268 static tree analyze_scalar_evolution_1 (struct loop *, tree, tree); | 282 #include "gimple-fold.h" |
269 | 283 |
270 /* The cached information about an SSA name VAR, claiming that below | 284 static tree analyze_scalar_evolution_1 (struct loop *, tree); |
271 basic block INSTANTIATED_BELOW, the value of VAR can be expressed | 285 static tree analyze_scalar_evolution_for_address_of (struct loop *loop, |
272 as CHREC. */ | 286 tree var); |
273 | 287 |
274 struct GTY(()) scev_info_str { | 288 /* The cached information about an SSA name with version NAME_VERSION, |
275 basic_block instantiated_below; | 289 claiming that below basic block with index INSTANTIATED_BELOW, the |
276 tree var; | 290 value of the SSA name can be expressed as CHREC. */ |
291 | |
292 struct GTY((for_user)) scev_info_str { | |
293 unsigned int name_version; | |
294 int instantiated_below; | |
277 tree chrec; | 295 tree chrec; |
278 }; | 296 }; |
279 | 297 |
280 /* Counters for the scev database. */ | 298 /* Counters for the scev database. */ |
281 static unsigned nb_set_scev = 0; | 299 static unsigned nb_set_scev = 0; |
294 | 312 |
295 /* When the analyzer has detected that a property will never | 313 /* When the analyzer has detected that a property will never |
296 happen, then it qualifies it with chrec_known. */ | 314 happen, then it qualifies it with chrec_known. */ |
297 tree chrec_known; | 315 tree chrec_known; |
298 | 316 |
299 static GTY ((param_is (struct scev_info_str))) htab_t scalar_evolution_info; | 317 struct scev_info_hasher : ggc_ptr_hash<scev_info_str> |
318 { | |
319 static hashval_t hash (scev_info_str *i); | |
320 static bool equal (const scev_info_str *a, const scev_info_str *b); | |
321 }; | |
322 | |
323 static GTY (()) hash_table<scev_info_hasher> *scalar_evolution_info; | |
300 | 324 |
301 | 325 |
302 /* Constructs a new SCEV_INFO_STR structure for VAR and INSTANTIATED_BELOW. */ | 326 /* Constructs a new SCEV_INFO_STR structure for VAR and INSTANTIATED_BELOW. */ |
303 | 327 |
304 static inline struct scev_info_str * | 328 static inline struct scev_info_str * |
305 new_scev_info_str (basic_block instantiated_below, tree var) | 329 new_scev_info_str (basic_block instantiated_below, tree var) |
306 { | 330 { |
307 struct scev_info_str *res; | 331 struct scev_info_str *res; |
308 | 332 |
309 res = ggc_alloc_scev_info_str (); | 333 res = ggc_alloc<scev_info_str> (); |
310 res->var = var; | 334 res->name_version = SSA_NAME_VERSION (var); |
311 res->chrec = chrec_not_analyzed_yet; | 335 res->chrec = chrec_not_analyzed_yet; |
312 res->instantiated_below = instantiated_below; | 336 res->instantiated_below = instantiated_below->index; |
313 | 337 |
314 return res; | 338 return res; |
315 } | 339 } |
316 | 340 |
317 /* Computes a hash function for database element ELT. */ | 341 /* Computes a hash function for database element ELT. */ |
318 | 342 |
319 static hashval_t | 343 hashval_t |
320 hash_scev_info (const void *elt) | 344 scev_info_hasher::hash (scev_info_str *elt) |
321 { | 345 { |
322 return SSA_NAME_VERSION (((const struct scev_info_str *) elt)->var); | 346 return elt->name_version ^ elt->instantiated_below; |
323 } | 347 } |
324 | 348 |
325 /* Compares database elements E1 and E2. */ | 349 /* Compares database elements E1 and E2. */ |
326 | 350 |
327 static int | 351 bool |
328 eq_scev_info (const void *e1, const void *e2) | 352 scev_info_hasher::equal (const scev_info_str *elt1, const scev_info_str *elt2) |
329 { | 353 { |
330 const struct scev_info_str *elt1 = (const struct scev_info_str *) e1; | 354 return (elt1->name_version == elt2->name_version |
331 const struct scev_info_str *elt2 = (const struct scev_info_str *) e2; | |
332 | |
333 return (elt1->var == elt2->var | |
334 && elt1->instantiated_below == elt2->instantiated_below); | 355 && elt1->instantiated_below == elt2->instantiated_below); |
335 } | |
336 | |
337 /* Deletes database element E. */ | |
338 | |
339 static void | |
340 del_scev_info (void *e) | |
341 { | |
342 ggc_free (e); | |
343 } | 356 } |
344 | 357 |
345 /* Get the scalar evolution of VAR for INSTANTIATED_BELOW basic block. | 358 /* Get the scalar evolution of VAR for INSTANTIATED_BELOW basic block. |
346 A first query on VAR returns chrec_not_analyzed_yet. */ | 359 A first query on VAR returns chrec_not_analyzed_yet. */ |
347 | 360 |
348 static tree * | 361 static tree * |
349 find_var_scev_info (basic_block instantiated_below, tree var) | 362 find_var_scev_info (basic_block instantiated_below, tree var) |
350 { | 363 { |
351 struct scev_info_str *res; | 364 struct scev_info_str *res; |
352 struct scev_info_str tmp; | 365 struct scev_info_str tmp; |
353 PTR *slot; | 366 |
354 | 367 tmp.name_version = SSA_NAME_VERSION (var); |
355 tmp.var = var; | 368 tmp.instantiated_below = instantiated_below->index; |
356 tmp.instantiated_below = instantiated_below; | 369 scev_info_str **slot = scalar_evolution_info->find_slot (&tmp, INSERT); |
357 slot = htab_find_slot (scalar_evolution_info, &tmp, INSERT); | |
358 | 370 |
359 if (!*slot) | 371 if (!*slot) |
360 *slot = new_scev_info_str (instantiated_below, var); | 372 *slot = new_scev_info_str (instantiated_below, var); |
361 res = (struct scev_info_str *) *slot; | 373 res = *slot; |
362 | 374 |
363 return &res->chrec; | 375 return &res->chrec; |
364 } | 376 } |
365 | 377 |
366 /* Return true when CHREC contains symbolic names defined in | 378 /* Return true when CHREC contains symbolic names defined in |
377 if (is_gimple_min_invariant (chrec)) | 389 if (is_gimple_min_invariant (chrec)) |
378 return false; | 390 return false; |
379 | 391 |
380 if (TREE_CODE (chrec) == SSA_NAME) | 392 if (TREE_CODE (chrec) == SSA_NAME) |
381 { | 393 { |
382 gimple def; | 394 gimple *def; |
383 loop_p def_loop, loop; | 395 loop_p def_loop, loop; |
384 | 396 |
385 if (SSA_NAME_IS_DEFAULT_DEF (chrec)) | 397 if (SSA_NAME_IS_DEFAULT_DEF (chrec)) |
386 return false; | 398 return false; |
387 | 399 |
388 def = SSA_NAME_DEF_STMT (chrec); | 400 def = SSA_NAME_DEF_STMT (chrec); |
389 def_loop = loop_containing_stmt (def); | 401 def_loop = loop_containing_stmt (def); |
390 loop = get_loop (loop_nb); | 402 loop = get_loop (cfun, loop_nb); |
391 | 403 |
392 if (def_loop == NULL) | 404 if (def_loop == NULL) |
393 return false; | 405 return false; |
394 | 406 |
395 if (loop == def_loop || flow_loop_nested_p (loop, def_loop)) | 407 if (loop == def_loop || flow_loop_nested_p (loop, def_loop)) |
407 } | 419 } |
408 | 420 |
409 /* Return true when PHI is a loop-phi-node. */ | 421 /* Return true when PHI is a loop-phi-node. */ |
410 | 422 |
411 static bool | 423 static bool |
412 loop_phi_node_p (gimple phi) | 424 loop_phi_node_p (gimple *phi) |
413 { | 425 { |
414 /* The implementation of this function is based on the following | 426 /* The implementation of this function is based on the following |
415 property: "all the loop-phi-nodes of a loop are contained in the | 427 property: "all the loop-phi-nodes of a loop are contained in the |
416 loop's header basic block". */ | 428 loop's header basic block". */ |
417 | 429 |
497 | 509 |
498 else | 510 else |
499 return chrec_dont_know; | 511 return chrec_dont_know; |
500 } | 512 } |
501 | 513 |
502 /* Determine whether the CHREC is always positive/negative. If the expression | |
503 cannot be statically analyzed, return false, otherwise set the answer into | |
504 VALUE. */ | |
505 | |
506 bool | |
507 chrec_is_positive (tree chrec, bool *value) | |
508 { | |
509 bool value0, value1, value2; | |
510 tree end_value, nb_iter; | |
511 | |
512 switch (TREE_CODE (chrec)) | |
513 { | |
514 case POLYNOMIAL_CHREC: | |
515 if (!chrec_is_positive (CHREC_LEFT (chrec), &value0) | |
516 || !chrec_is_positive (CHREC_RIGHT (chrec), &value1)) | |
517 return false; | |
518 | |
519 /* FIXME -- overflows. */ | |
520 if (value0 == value1) | |
521 { | |
522 *value = value0; | |
523 return true; | |
524 } | |
525 | |
526 /* Otherwise the chrec is under the form: "{-197, +, 2}_1", | |
527 and the proof consists in showing that the sign never | |
528 changes during the execution of the loop, from 0 to | |
529 loop->nb_iterations. */ | |
530 if (!evolution_function_is_affine_p (chrec)) | |
531 return false; | |
532 | |
533 nb_iter = number_of_latch_executions (get_chrec_loop (chrec)); | |
534 if (chrec_contains_undetermined (nb_iter)) | |
535 return false; | |
536 | |
537 #if 0 | |
538 /* TODO -- If the test is after the exit, we may decrease the number of | |
539 iterations by one. */ | |
540 if (after_exit) | |
541 nb_iter = chrec_fold_minus (type, nb_iter, build_int_cst (type, 1)); | |
542 #endif | |
543 | |
544 end_value = chrec_apply (CHREC_VARIABLE (chrec), chrec, nb_iter); | |
545 | |
546 if (!chrec_is_positive (end_value, &value2)) | |
547 return false; | |
548 | |
549 *value = value0; | |
550 return value0 == value1; | |
551 | |
552 case INTEGER_CST: | |
553 *value = (tree_int_cst_sgn (chrec) == 1); | |
554 return true; | |
555 | |
556 default: | |
557 return false; | |
558 } | |
559 } | |
560 | |
561 /* Associate CHREC to SCALAR. */ | 514 /* Associate CHREC to SCALAR. */ |
562 | 515 |
563 static void | 516 static void |
564 set_scalar_evolution (basic_block instantiated_below, tree scalar, tree chrec) | 517 set_scalar_evolution (basic_block instantiated_below, tree scalar, tree chrec) |
565 { | 518 { |
570 | 523 |
571 scalar_info = find_var_scev_info (instantiated_below, scalar); | 524 scalar_info = find_var_scev_info (instantiated_below, scalar); |
572 | 525 |
573 if (dump_file) | 526 if (dump_file) |
574 { | 527 { |
575 if (dump_flags & TDF_DETAILS) | 528 if (dump_flags & TDF_SCEV) |
576 { | 529 { |
577 fprintf (dump_file, "(set_scalar_evolution \n"); | 530 fprintf (dump_file, "(set_scalar_evolution \n"); |
578 fprintf (dump_file, " instantiated_below = %d \n", | 531 fprintf (dump_file, " instantiated_below = %d \n", |
579 instantiated_below->index); | 532 instantiated_below->index); |
580 fprintf (dump_file, " (scalar = "); | 533 fprintf (dump_file, " (scalar = "); |
581 print_generic_expr (dump_file, scalar, 0); | 534 print_generic_expr (dump_file, scalar); |
582 fprintf (dump_file, ")\n (scalar_evolution = "); | 535 fprintf (dump_file, ")\n (scalar_evolution = "); |
583 print_generic_expr (dump_file, chrec, 0); | 536 print_generic_expr (dump_file, chrec); |
584 fprintf (dump_file, "))\n"); | 537 fprintf (dump_file, "))\n"); |
585 } | 538 } |
586 if (dump_flags & TDF_STATS) | 539 if (dump_flags & TDF_STATS) |
587 nb_set_scev++; | 540 nb_set_scev++; |
588 } | 541 } |
598 { | 551 { |
599 tree res; | 552 tree res; |
600 | 553 |
601 if (dump_file) | 554 if (dump_file) |
602 { | 555 { |
603 if (dump_flags & TDF_DETAILS) | 556 if (dump_flags & TDF_SCEV) |
604 { | 557 { |
605 fprintf (dump_file, "(get_scalar_evolution \n"); | 558 fprintf (dump_file, "(get_scalar_evolution \n"); |
606 fprintf (dump_file, " (scalar = "); | 559 fprintf (dump_file, " (scalar = "); |
607 print_generic_expr (dump_file, scalar, 0); | 560 print_generic_expr (dump_file, scalar); |
608 fprintf (dump_file, ")\n"); | 561 fprintf (dump_file, ")\n"); |
609 } | 562 } |
610 if (dump_flags & TDF_STATS) | 563 if (dump_flags & TDF_STATS) |
611 nb_get_scev++; | 564 nb_get_scev++; |
612 } | 565 } |
613 | 566 |
614 switch (TREE_CODE (scalar)) | 567 if (VECTOR_TYPE_P (TREE_TYPE (scalar)) |
615 { | 568 || TREE_CODE (TREE_TYPE (scalar)) == COMPLEX_TYPE) |
616 case SSA_NAME: | 569 /* For chrec_dont_know we keep the symbolic form. */ |
617 res = *find_var_scev_info (instantiated_below, scalar); | 570 res = scalar; |
618 break; | 571 else |
619 | 572 switch (TREE_CODE (scalar)) |
620 case REAL_CST: | 573 { |
621 case FIXED_CST: | 574 case SSA_NAME: |
622 case INTEGER_CST: | 575 if (SSA_NAME_IS_DEFAULT_DEF (scalar)) |
623 res = scalar; | 576 res = scalar; |
624 break; | 577 else |
625 | 578 res = *find_var_scev_info (instantiated_below, scalar); |
626 default: | 579 break; |
627 res = chrec_not_analyzed_yet; | 580 |
628 break; | 581 case REAL_CST: |
629 } | 582 case FIXED_CST: |
630 | 583 case INTEGER_CST: |
631 if (dump_file && (dump_flags & TDF_DETAILS)) | 584 res = scalar; |
585 break; | |
586 | |
587 default: | |
588 res = chrec_not_analyzed_yet; | |
589 break; | |
590 } | |
591 | |
592 if (dump_file && (dump_flags & TDF_SCEV)) | |
632 { | 593 { |
633 fprintf (dump_file, " (scalar_evolution = "); | 594 fprintf (dump_file, " (scalar_evolution = "); |
634 print_generic_expr (dump_file, res, 0); | 595 print_generic_expr (dump_file, res); |
635 fprintf (dump_file, "))\n"); | 596 fprintf (dump_file, "))\n"); |
636 } | 597 } |
637 | 598 |
638 return res; | 599 return res; |
639 } | 600 } |
648 evolution the expression TO_ADD, otherwise construct an evolution | 609 evolution the expression TO_ADD, otherwise construct an evolution |
649 part for this loop. */ | 610 part for this loop. */ |
650 | 611 |
651 static tree | 612 static tree |
652 add_to_evolution_1 (unsigned loop_nb, tree chrec_before, tree to_add, | 613 add_to_evolution_1 (unsigned loop_nb, tree chrec_before, tree to_add, |
653 gimple at_stmt) | 614 gimple *at_stmt) |
654 { | 615 { |
655 tree type, left, right; | 616 tree type, left, right; |
656 struct loop *loop = get_loop (loop_nb), *chloop; | 617 struct loop *loop = get_loop (cfun, loop_nb), *chloop; |
657 | 618 |
658 switch (TREE_CODE (chrec_before)) | 619 switch (TREE_CODE (chrec_before)) |
659 { | 620 { |
660 case POLYNOMIAL_CHREC: | 621 case POLYNOMIAL_CHREC: |
661 chloop = get_chrec_loop (chrec_before); | 622 chloop = get_chrec_loop (chrec_before); |
845 | 806 |
846 */ | 807 */ |
847 | 808 |
848 static tree | 809 static tree |
849 add_to_evolution (unsigned loop_nb, tree chrec_before, enum tree_code code, | 810 add_to_evolution (unsigned loop_nb, tree chrec_before, enum tree_code code, |
850 tree to_add, gimple at_stmt) | 811 tree to_add, gimple *at_stmt) |
851 { | 812 { |
852 tree type = chrec_type (to_add); | 813 tree type = chrec_type (to_add); |
853 tree res = NULL_TREE; | 814 tree res = NULL_TREE; |
854 | 815 |
855 if (to_add == NULL_TREE) | 816 if (to_add == NULL_TREE) |
859 instantiated at this point. */ | 820 instantiated at this point. */ |
860 if (TREE_CODE (to_add) == POLYNOMIAL_CHREC) | 821 if (TREE_CODE (to_add) == POLYNOMIAL_CHREC) |
861 /* This should not happen. */ | 822 /* This should not happen. */ |
862 return chrec_dont_know; | 823 return chrec_dont_know; |
863 | 824 |
864 if (dump_file && (dump_flags & TDF_DETAILS)) | 825 if (dump_file && (dump_flags & TDF_SCEV)) |
865 { | 826 { |
866 fprintf (dump_file, "(add_to_evolution \n"); | 827 fprintf (dump_file, "(add_to_evolution \n"); |
867 fprintf (dump_file, " (loop_nb = %d)\n", loop_nb); | 828 fprintf (dump_file, " (loop_nb = %d)\n", loop_nb); |
868 fprintf (dump_file, " (chrec_before = "); | 829 fprintf (dump_file, " (chrec_before = "); |
869 print_generic_expr (dump_file, chrec_before, 0); | 830 print_generic_expr (dump_file, chrec_before); |
870 fprintf (dump_file, ")\n (to_add = "); | 831 fprintf (dump_file, ")\n (to_add = "); |
871 print_generic_expr (dump_file, to_add, 0); | 832 print_generic_expr (dump_file, to_add); |
872 fprintf (dump_file, ")\n"); | 833 fprintf (dump_file, ")\n"); |
873 } | 834 } |
874 | 835 |
875 if (code == MINUS_EXPR) | 836 if (code == MINUS_EXPR) |
876 to_add = chrec_fold_multiply (type, to_add, SCALAR_FLOAT_TYPE_P (type) | 837 to_add = chrec_fold_multiply (type, to_add, SCALAR_FLOAT_TYPE_P (type) |
877 ? build_real (type, dconstm1) | 838 ? build_real (type, dconstm1) |
878 : build_int_cst_type (type, -1)); | 839 : build_int_cst_type (type, -1)); |
879 | 840 |
880 res = add_to_evolution_1 (loop_nb, chrec_before, to_add, at_stmt); | 841 res = add_to_evolution_1 (loop_nb, chrec_before, to_add, at_stmt); |
881 | 842 |
882 if (dump_file && (dump_flags & TDF_DETAILS)) | 843 if (dump_file && (dump_flags & TDF_SCEV)) |
883 { | 844 { |
884 fprintf (dump_file, " (res = "); | 845 fprintf (dump_file, " (res = "); |
885 print_generic_expr (dump_file, res, 0); | 846 print_generic_expr (dump_file, res); |
886 fprintf (dump_file, "))\n"); | 847 fprintf (dump_file, "))\n"); |
887 } | 848 } |
888 | 849 |
889 return res; | 850 return res; |
890 } | 851 } |
897 | 858 |
898 /* For a loop with a single exit edge, return the COND_EXPR that | 859 /* For a loop with a single exit edge, return the COND_EXPR that |
899 guards the exit edge. If the expression is too difficult to | 860 guards the exit edge. If the expression is too difficult to |
900 analyze, then give up. */ | 861 analyze, then give up. */ |
901 | 862 |
902 gimple | 863 gcond * |
903 get_loop_exit_condition (const struct loop *loop) | 864 get_loop_exit_condition (const struct loop *loop) |
904 { | 865 { |
905 gimple res = NULL; | 866 gcond *res = NULL; |
906 edge exit_edge = single_exit (loop); | 867 edge exit_edge = single_exit (loop); |
907 | 868 |
908 if (dump_file && (dump_flags & TDF_DETAILS)) | 869 if (dump_file && (dump_flags & TDF_SCEV)) |
909 fprintf (dump_file, "(get_loop_exit_condition \n "); | 870 fprintf (dump_file, "(get_loop_exit_condition \n "); |
910 | 871 |
911 if (exit_edge) | 872 if (exit_edge) |
912 { | 873 { |
913 gimple stmt; | 874 gimple *stmt; |
914 | 875 |
915 stmt = last_stmt (exit_edge->src); | 876 stmt = last_stmt (exit_edge->src); |
916 if (gimple_code (stmt) == GIMPLE_COND) | 877 if (gcond *cond_stmt = dyn_cast <gcond *> (stmt)) |
917 res = stmt; | 878 res = cond_stmt; |
918 } | 879 } |
919 | 880 |
920 if (dump_file && (dump_flags & TDF_DETAILS)) | 881 if (dump_file && (dump_flags & TDF_SCEV)) |
921 { | 882 { |
922 print_gimple_stmt (dump_file, res, 0, 0); | 883 print_gimple_stmt (dump_file, res, 0); |
923 fprintf (dump_file, ")\n"); | 884 fprintf (dump_file, ")\n"); |
924 } | 885 } |
925 | 886 |
926 return res; | 887 return res; |
927 } | |
928 | |
929 /* Recursively determine and enqueue the exit conditions for a loop. */ | |
930 | |
931 static void | |
932 get_exit_conditions_rec (struct loop *loop, | |
933 VEC(gimple,heap) **exit_conditions) | |
934 { | |
935 if (!loop) | |
936 return; | |
937 | |
938 /* Recurse on the inner loops, then on the next (sibling) loops. */ | |
939 get_exit_conditions_rec (loop->inner, exit_conditions); | |
940 get_exit_conditions_rec (loop->next, exit_conditions); | |
941 | |
942 if (single_exit (loop)) | |
943 { | |
944 gimple loop_condition = get_loop_exit_condition (loop); | |
945 | |
946 if (loop_condition) | |
947 VEC_safe_push (gimple, heap, *exit_conditions, loop_condition); | |
948 } | |
949 } | |
950 | |
951 /* Select the candidate loop nests for the analysis. This function | |
952 initializes the EXIT_CONDITIONS array. */ | |
953 | |
954 static void | |
955 select_loops_exit_conditions (VEC(gimple,heap) **exit_conditions) | |
956 { | |
957 struct loop *function_body = current_loops->tree_root; | |
958 | |
959 get_exit_conditions_rec (function_body->inner, exit_conditions); | |
960 } | 888 } |
961 | 889 |
962 | 890 |
963 /* Depth first search algorithm. */ | 891 /* Depth first search algorithm. */ |
964 | 892 |
965 typedef enum t_bool { | 893 enum t_bool { |
966 t_false, | 894 t_false, |
967 t_true, | 895 t_true, |
968 t_dont_know | 896 t_dont_know |
969 } t_bool; | 897 }; |
970 | 898 |
971 | 899 |
972 static t_bool follow_ssa_edge (struct loop *loop, gimple, gimple, tree *, int); | 900 static t_bool follow_ssa_edge (struct loop *loop, gimple *, gphi *, |
901 tree *, int); | |
973 | 902 |
974 /* Follow the ssa edge into the binary expression RHS0 CODE RHS1. | 903 /* Follow the ssa edge into the binary expression RHS0 CODE RHS1. |
975 Return true if the strongly connected component has been found. */ | 904 Return true if the strongly connected component has been found. */ |
976 | 905 |
977 static t_bool | 906 static t_bool |
978 follow_ssa_edge_binary (struct loop *loop, gimple at_stmt, | 907 follow_ssa_edge_binary (struct loop *loop, gimple *at_stmt, |
979 tree type, tree rhs0, enum tree_code code, tree rhs1, | 908 tree type, tree rhs0, enum tree_code code, tree rhs1, |
980 gimple halting_phi, tree *evolution_of_loop, int limit) | 909 gphi *halting_phi, tree *evolution_of_loop, |
910 int limit) | |
981 { | 911 { |
982 t_bool res = t_false; | 912 t_bool res = t_false; |
983 tree evol; | 913 tree evol; |
984 | 914 |
985 switch (code) | 915 switch (code) |
997 LIMIT, as the other cases do not necessarily contribute to | 927 LIMIT, as the other cases do not necessarily contribute to |
998 the complexity of the expression. */ | 928 the complexity of the expression. */ |
999 limit++; | 929 limit++; |
1000 | 930 |
1001 evol = *evolution_of_loop; | 931 evol = *evolution_of_loop; |
1002 res = follow_ssa_edge | 932 evol = add_to_evolution |
1003 (loop, SSA_NAME_DEF_STMT (rhs0), halting_phi, &evol, limit); | |
1004 | |
1005 if (res == t_true) | |
1006 *evolution_of_loop = add_to_evolution | |
1007 (loop->num, | 933 (loop->num, |
1008 chrec_convert (type, evol, at_stmt), | 934 chrec_convert (type, evol, at_stmt), |
1009 code, rhs1, at_stmt); | 935 code, rhs1, at_stmt); |
1010 | 936 res = follow_ssa_edge |
937 (loop, SSA_NAME_DEF_STMT (rhs0), halting_phi, &evol, limit); | |
938 if (res == t_true) | |
939 *evolution_of_loop = evol; | |
1011 else if (res == t_false) | 940 else if (res == t_false) |
1012 { | 941 { |
942 *evolution_of_loop = add_to_evolution | |
943 (loop->num, | |
944 chrec_convert (type, *evolution_of_loop, at_stmt), | |
945 code, rhs0, at_stmt); | |
1013 res = follow_ssa_edge | 946 res = follow_ssa_edge |
1014 (loop, SSA_NAME_DEF_STMT (rhs1), halting_phi, | 947 (loop, SSA_NAME_DEF_STMT (rhs1), halting_phi, |
1015 evolution_of_loop, limit); | 948 evolution_of_loop, limit); |
1016 | |
1017 if (res == t_true) | 949 if (res == t_true) |
1018 *evolution_of_loop = add_to_evolution | 950 ; |
1019 (loop->num, | |
1020 chrec_convert (type, *evolution_of_loop, at_stmt), | |
1021 code, rhs0, at_stmt); | |
1022 | |
1023 else if (res == t_dont_know) | 951 else if (res == t_dont_know) |
1024 *evolution_of_loop = chrec_dont_know; | 952 *evolution_of_loop = chrec_dont_know; |
1025 } | 953 } |
1026 | 954 |
1027 else if (res == t_dont_know) | 955 else if (res == t_dont_know) |
1030 | 958 |
1031 else | 959 else |
1032 { | 960 { |
1033 /* Match an assignment under the form: | 961 /* Match an assignment under the form: |
1034 "a = b + ...". */ | 962 "a = b + ...". */ |
963 *evolution_of_loop = add_to_evolution | |
964 (loop->num, chrec_convert (type, *evolution_of_loop, | |
965 at_stmt), | |
966 code, rhs1, at_stmt); | |
1035 res = follow_ssa_edge | 967 res = follow_ssa_edge |
1036 (loop, SSA_NAME_DEF_STMT (rhs0), halting_phi, | 968 (loop, SSA_NAME_DEF_STMT (rhs0), halting_phi, |
1037 evolution_of_loop, limit); | 969 evolution_of_loop, limit); |
1038 if (res == t_true) | 970 if (res == t_true) |
1039 *evolution_of_loop = add_to_evolution | 971 ; |
1040 (loop->num, chrec_convert (type, *evolution_of_loop, | |
1041 at_stmt), | |
1042 code, rhs1, at_stmt); | |
1043 | |
1044 else if (res == t_dont_know) | 972 else if (res == t_dont_know) |
1045 *evolution_of_loop = chrec_dont_know; | 973 *evolution_of_loop = chrec_dont_know; |
1046 } | 974 } |
1047 } | 975 } |
1048 | 976 |
1049 else if (TREE_CODE (rhs1) == SSA_NAME) | 977 else if (TREE_CODE (rhs1) == SSA_NAME) |
1050 { | 978 { |
1051 /* Match an assignment under the form: | 979 /* Match an assignment under the form: |
1052 "a = ... + c". */ | 980 "a = ... + c". */ |
981 *evolution_of_loop = add_to_evolution | |
982 (loop->num, chrec_convert (type, *evolution_of_loop, | |
983 at_stmt), | |
984 code, rhs0, at_stmt); | |
1053 res = follow_ssa_edge | 985 res = follow_ssa_edge |
1054 (loop, SSA_NAME_DEF_STMT (rhs1), halting_phi, | 986 (loop, SSA_NAME_DEF_STMT (rhs1), halting_phi, |
1055 evolution_of_loop, limit); | 987 evolution_of_loop, limit); |
1056 if (res == t_true) | 988 if (res == t_true) |
1057 *evolution_of_loop = add_to_evolution | 989 ; |
1058 (loop->num, chrec_convert (type, *evolution_of_loop, | |
1059 at_stmt), | |
1060 code, rhs0, at_stmt); | |
1061 | |
1062 else if (res == t_dont_know) | 990 else if (res == t_dont_know) |
1063 *evolution_of_loop = chrec_dont_know; | 991 *evolution_of_loop = chrec_dont_know; |
1064 } | 992 } |
1065 | 993 |
1066 else | 994 else |
1081 LIMIT, as the other cases do not necessarily contribute to | 1009 LIMIT, as the other cases do not necessarily contribute to |
1082 the complexity of the expression. */ | 1010 the complexity of the expression. */ |
1083 if (TREE_CODE (rhs1) == SSA_NAME) | 1011 if (TREE_CODE (rhs1) == SSA_NAME) |
1084 limit++; | 1012 limit++; |
1085 | 1013 |
1014 *evolution_of_loop = add_to_evolution | |
1015 (loop->num, chrec_convert (type, *evolution_of_loop, at_stmt), | |
1016 MINUS_EXPR, rhs1, at_stmt); | |
1086 res = follow_ssa_edge (loop, SSA_NAME_DEF_STMT (rhs0), halting_phi, | 1017 res = follow_ssa_edge (loop, SSA_NAME_DEF_STMT (rhs0), halting_phi, |
1087 evolution_of_loop, limit); | 1018 evolution_of_loop, limit); |
1088 if (res == t_true) | 1019 if (res == t_true) |
1089 *evolution_of_loop = add_to_evolution | 1020 ; |
1090 (loop->num, chrec_convert (type, *evolution_of_loop, at_stmt), | |
1091 MINUS_EXPR, rhs1, at_stmt); | |
1092 | |
1093 else if (res == t_dont_know) | 1021 else if (res == t_dont_know) |
1094 *evolution_of_loop = chrec_dont_know; | 1022 *evolution_of_loop = chrec_dont_know; |
1095 } | 1023 } |
1096 else | 1024 else |
1097 /* Otherwise, match an assignment under the form: | 1025 /* Otherwise, match an assignment under the form: |
1109 | 1037 |
1110 /* Follow the ssa edge into the expression EXPR. | 1038 /* Follow the ssa edge into the expression EXPR. |
1111 Return true if the strongly connected component has been found. */ | 1039 Return true if the strongly connected component has been found. */ |
1112 | 1040 |
1113 static t_bool | 1041 static t_bool |
1114 follow_ssa_edge_expr (struct loop *loop, gimple at_stmt, tree expr, | 1042 follow_ssa_edge_expr (struct loop *loop, gimple *at_stmt, tree expr, |
1115 gimple halting_phi, tree *evolution_of_loop, int limit) | 1043 gphi *halting_phi, tree *evolution_of_loop, |
1044 int limit) | |
1116 { | 1045 { |
1117 enum tree_code code = TREE_CODE (expr); | 1046 enum tree_code code = TREE_CODE (expr); |
1118 tree type = TREE_TYPE (expr), rhs0, rhs1; | 1047 tree type = TREE_TYPE (expr), rhs0, rhs1; |
1119 t_bool res; | 1048 t_bool res; |
1120 | 1049 |
1199 | 1128 |
1200 /* Follow the ssa edge into the right hand side of an assignment STMT. | 1129 /* Follow the ssa edge into the right hand side of an assignment STMT. |
1201 Return true if the strongly connected component has been found. */ | 1130 Return true if the strongly connected component has been found. */ |
1202 | 1131 |
1203 static t_bool | 1132 static t_bool |
1204 follow_ssa_edge_in_rhs (struct loop *loop, gimple stmt, | 1133 follow_ssa_edge_in_rhs (struct loop *loop, gimple *stmt, |
1205 gimple halting_phi, tree *evolution_of_loop, int limit) | 1134 gphi *halting_phi, tree *evolution_of_loop, |
1135 int limit) | |
1206 { | 1136 { |
1207 enum tree_code code = gimple_assign_rhs_code (stmt); | 1137 enum tree_code code = gimple_assign_rhs_code (stmt); |
1208 tree type = gimple_expr_type (stmt), rhs1, rhs2; | 1138 tree type = gimple_expr_type (stmt), rhs1, rhs2; |
1209 t_bool res; | 1139 t_bool res; |
1210 | 1140 |
1240 } | 1170 } |
1241 | 1171 |
1242 /* Checks whether the I-th argument of a PHI comes from a backedge. */ | 1172 /* Checks whether the I-th argument of a PHI comes from a backedge. */ |
1243 | 1173 |
1244 static bool | 1174 static bool |
1245 backedge_phi_arg_p (gimple phi, int i) | 1175 backedge_phi_arg_p (gphi *phi, int i) |
1246 { | 1176 { |
1247 const_edge e = gimple_phi_arg_edge (phi, i); | 1177 const_edge e = gimple_phi_arg_edge (phi, i); |
1248 | 1178 |
1249 /* We would in fact like to test EDGE_DFS_BACK here, but we do not care | 1179 /* We would in fact like to test EDGE_DFS_BACK here, but we do not care |
1250 about updating it anywhere, and this should work as well most of the | 1180 about updating it anywhere, and this should work as well most of the |
1260 this path. */ | 1190 this path. */ |
1261 | 1191 |
1262 static inline t_bool | 1192 static inline t_bool |
1263 follow_ssa_edge_in_condition_phi_branch (int i, | 1193 follow_ssa_edge_in_condition_phi_branch (int i, |
1264 struct loop *loop, | 1194 struct loop *loop, |
1265 gimple condition_phi, | 1195 gphi *condition_phi, |
1266 gimple halting_phi, | 1196 gphi *halting_phi, |
1267 tree *evolution_of_branch, | 1197 tree *evolution_of_branch, |
1268 tree init_cond, int limit) | 1198 tree init_cond, int limit) |
1269 { | 1199 { |
1270 tree branch = PHI_ARG_DEF (condition_phi, i); | 1200 tree branch = PHI_ARG_DEF (condition_phi, i); |
1271 *evolution_of_branch = chrec_dont_know; | 1201 *evolution_of_branch = chrec_dont_know; |
1295 /* This function merges the branches of a condition-phi-node in a | 1225 /* This function merges the branches of a condition-phi-node in a |
1296 loop. */ | 1226 loop. */ |
1297 | 1227 |
1298 static t_bool | 1228 static t_bool |
1299 follow_ssa_edge_in_condition_phi (struct loop *loop, | 1229 follow_ssa_edge_in_condition_phi (struct loop *loop, |
1300 gimple condition_phi, | 1230 gphi *condition_phi, |
1301 gimple halting_phi, | 1231 gphi *halting_phi, |
1302 tree *evolution_of_loop, int limit) | 1232 tree *evolution_of_loop, int limit) |
1303 { | 1233 { |
1304 int i, n; | 1234 int i, n; |
1305 tree init = *evolution_of_loop; | 1235 tree init = *evolution_of_loop; |
1306 tree evolution_of_branch; | 1236 tree evolution_of_branch; |
1342 it follows the edges in the parent loop. The inner loop is | 1272 it follows the edges in the parent loop. The inner loop is |
1343 considered as a single statement. */ | 1273 considered as a single statement. */ |
1344 | 1274 |
1345 static t_bool | 1275 static t_bool |
1346 follow_ssa_edge_inner_loop_phi (struct loop *outer_loop, | 1276 follow_ssa_edge_inner_loop_phi (struct loop *outer_loop, |
1347 gimple loop_phi_node, | 1277 gphi *loop_phi_node, |
1348 gimple halting_phi, | 1278 gphi *halting_phi, |
1349 tree *evolution_of_loop, int limit) | 1279 tree *evolution_of_loop, int limit) |
1350 { | 1280 { |
1351 struct loop *loop = loop_containing_stmt (loop_phi_node); | 1281 struct loop *loop = loop_containing_stmt (loop_phi_node); |
1352 tree ev = analyze_scalar_evolution (loop, PHI_RESULT (loop_phi_node)); | 1282 tree ev = analyze_scalar_evolution (loop, PHI_RESULT (loop_phi_node)); |
1353 | 1283 |
1388 | 1318 |
1389 /* Follow an SSA edge from a loop-phi-node to itself, constructing a | 1319 /* Follow an SSA edge from a loop-phi-node to itself, constructing a |
1390 path that is analyzed on the return walk. */ | 1320 path that is analyzed on the return walk. */ |
1391 | 1321 |
1392 static t_bool | 1322 static t_bool |
1393 follow_ssa_edge (struct loop *loop, gimple def, gimple halting_phi, | 1323 follow_ssa_edge (struct loop *loop, gimple *def, gphi *halting_phi, |
1394 tree *evolution_of_loop, int limit) | 1324 tree *evolution_of_loop, int limit) |
1395 { | 1325 { |
1396 struct loop *def_loop; | 1326 struct loop *def_loop; |
1397 | 1327 |
1398 if (gimple_nop_p (def)) | 1328 if (gimple_nop_p (def)) |
1411 /* DEF is a condition-phi-node. Follow the branches, and | 1341 /* DEF is a condition-phi-node. Follow the branches, and |
1412 record their evolutions. Finally, merge the collected | 1342 record their evolutions. Finally, merge the collected |
1413 information and set the approximation to the main | 1343 information and set the approximation to the main |
1414 variable. */ | 1344 variable. */ |
1415 return follow_ssa_edge_in_condition_phi | 1345 return follow_ssa_edge_in_condition_phi |
1416 (loop, def, halting_phi, evolution_of_loop, limit); | 1346 (loop, as_a <gphi *> (def), halting_phi, evolution_of_loop, |
1347 limit); | |
1417 | 1348 |
1418 /* When the analyzed phi is the halting_phi, the | 1349 /* When the analyzed phi is the halting_phi, the |
1419 depth-first search is over: we have found a path from | 1350 depth-first search is over: we have found a path from |
1420 the halting_phi to itself in the loop. */ | 1351 the halting_phi to itself in the loop. */ |
1421 if (def == halting_phi) | 1352 if (def == halting_phi) |
1428 return t_false; | 1359 return t_false; |
1429 | 1360 |
1430 /* Inner loop. */ | 1361 /* Inner loop. */ |
1431 if (flow_loop_nested_p (loop, def_loop)) | 1362 if (flow_loop_nested_p (loop, def_loop)) |
1432 return follow_ssa_edge_inner_loop_phi | 1363 return follow_ssa_edge_inner_loop_phi |
1433 (loop, def, halting_phi, evolution_of_loop, limit + 1); | 1364 (loop, as_a <gphi *> (def), halting_phi, evolution_of_loop, |
1365 limit + 1); | |
1434 | 1366 |
1435 /* Outer loop. */ | 1367 /* Outer loop. */ |
1436 return t_false; | 1368 return t_false; |
1437 | 1369 |
1438 case GIMPLE_ASSIGN: | 1370 case GIMPLE_ASSIGN: |
1446 return t_false; | 1378 return t_false; |
1447 } | 1379 } |
1448 } | 1380 } |
1449 | 1381 |
1450 | 1382 |
1383 /* Simplify PEELED_CHREC represented by (init_cond, arg) in LOOP. | |
1384 Handle below case and return the corresponding POLYNOMIAL_CHREC: | |
1385 | |
1386 # i_17 = PHI <i_13(5), 0(3)> | |
1387 # _20 = PHI <_5(5), start_4(D)(3)> | |
1388 ... | |
1389 i_13 = i_17 + 1; | |
1390 _5 = start_4(D) + i_13; | |
1391 | |
1392 Though variable _20 appears as a PEELED_CHREC in the form of | |
1393 (start_4, _5)_LOOP, it's a POLYNOMIAL_CHREC like {start_4, 1}_LOOP. | |
1394 | |
1395 See PR41488. */ | |
1396 | |
1397 static tree | |
1398 simplify_peeled_chrec (struct loop *loop, tree arg, tree init_cond) | |
1399 { | |
1400 aff_tree aff1, aff2; | |
1401 tree ev, left, right, type, step_val; | |
1402 hash_map<tree, name_expansion *> *peeled_chrec_map = NULL; | |
1403 | |
1404 ev = instantiate_parameters (loop, analyze_scalar_evolution (loop, arg)); | |
1405 if (ev == NULL_TREE || TREE_CODE (ev) != POLYNOMIAL_CHREC) | |
1406 return chrec_dont_know; | |
1407 | |
1408 left = CHREC_LEFT (ev); | |
1409 right = CHREC_RIGHT (ev); | |
1410 type = TREE_TYPE (left); | |
1411 step_val = chrec_fold_plus (type, init_cond, right); | |
1412 | |
1413 /* Transform (init, {left, right}_LOOP)_LOOP to {init, right}_LOOP | |
1414 if "left" equals to "init + right". */ | |
1415 if (operand_equal_p (left, step_val, 0)) | |
1416 { | |
1417 if (dump_file && (dump_flags & TDF_SCEV)) | |
1418 fprintf (dump_file, "Simplify PEELED_CHREC into POLYNOMIAL_CHREC.\n"); | |
1419 | |
1420 return build_polynomial_chrec (loop->num, init_cond, right); | |
1421 } | |
1422 | |
1423 /* Try harder to check if they are equal. */ | |
1424 tree_to_aff_combination_expand (left, type, &aff1, &peeled_chrec_map); | |
1425 tree_to_aff_combination_expand (step_val, type, &aff2, &peeled_chrec_map); | |
1426 free_affine_expand_cache (&peeled_chrec_map); | |
1427 aff_combination_scale (&aff2, -1); | |
1428 aff_combination_add (&aff1, &aff2); | |
1429 | |
1430 /* Transform (init, {left, right}_LOOP)_LOOP to {init, right}_LOOP | |
1431 if "left" equals to "init + right". */ | |
1432 if (aff_combination_zero_p (&aff1)) | |
1433 { | |
1434 if (dump_file && (dump_flags & TDF_SCEV)) | |
1435 fprintf (dump_file, "Simplify PEELED_CHREC into POLYNOMIAL_CHREC.\n"); | |
1436 | |
1437 return build_polynomial_chrec (loop->num, init_cond, right); | |
1438 } | |
1439 return chrec_dont_know; | |
1440 } | |
1451 | 1441 |
1452 /* Given a LOOP_PHI_NODE, this function determines the evolution | 1442 /* Given a LOOP_PHI_NODE, this function determines the evolution |
1453 function from LOOP_PHI_NODE to LOOP_PHI_NODE in the loop. */ | 1443 function from LOOP_PHI_NODE to LOOP_PHI_NODE in the loop. */ |
1454 | 1444 |
1455 static tree | 1445 static tree |
1456 analyze_evolution_in_loop (gimple loop_phi_node, | 1446 analyze_evolution_in_loop (gphi *loop_phi_node, |
1457 tree init_cond) | 1447 tree init_cond) |
1458 { | 1448 { |
1459 int i, n = gimple_phi_num_args (loop_phi_node); | 1449 int i, n = gimple_phi_num_args (loop_phi_node); |
1460 tree evolution_function = chrec_not_analyzed_yet; | 1450 tree evolution_function = chrec_not_analyzed_yet; |
1461 struct loop *loop = loop_containing_stmt (loop_phi_node); | 1451 struct loop *loop = loop_containing_stmt (loop_phi_node); |
1462 basic_block bb; | 1452 basic_block bb; |
1463 | 1453 static bool simplify_peeled_chrec_p = true; |
1464 if (dump_file && (dump_flags & TDF_DETAILS)) | 1454 |
1455 if (dump_file && (dump_flags & TDF_SCEV)) | |
1465 { | 1456 { |
1466 fprintf (dump_file, "(analyze_evolution_in_loop \n"); | 1457 fprintf (dump_file, "(analyze_evolution_in_loop \n"); |
1467 fprintf (dump_file, " (loop_phi_node = "); | 1458 fprintf (dump_file, " (loop_phi_node = "); |
1468 print_gimple_stmt (dump_file, loop_phi_node, 0, 0); | 1459 print_gimple_stmt (dump_file, loop_phi_node, 0); |
1469 fprintf (dump_file, ")\n"); | 1460 fprintf (dump_file, ")\n"); |
1470 } | 1461 } |
1471 | 1462 |
1472 for (i = 0; i < n; i++) | 1463 for (i = 0; i < n; i++) |
1473 { | 1464 { |
1474 tree arg = PHI_ARG_DEF (loop_phi_node, i); | 1465 tree arg = PHI_ARG_DEF (loop_phi_node, i); |
1475 gimple ssa_chain; | 1466 gimple *ssa_chain; |
1476 tree ev_fn; | 1467 tree ev_fn; |
1477 t_bool res; | 1468 t_bool res; |
1478 | 1469 |
1479 /* Select the edges that enter the loop body. */ | 1470 /* Select the edges that enter the loop body. */ |
1480 bb = gimple_phi_arg_edge (loop_phi_node, i)->src; | 1471 bb = gimple_phi_arg_edge (loop_phi_node, i)->src; |
1508 evolution is represented by a peeled chrec, i.e. the | 1499 evolution is represented by a peeled chrec, i.e. the |
1509 first iteration, EV_FN has the value INIT_COND, then | 1500 first iteration, EV_FN has the value INIT_COND, then |
1510 all the other iterations it has the value of ARG. | 1501 all the other iterations it has the value of ARG. |
1511 For the moment, PEELED_CHREC nodes are not built. */ | 1502 For the moment, PEELED_CHREC nodes are not built. */ |
1512 if (res != t_true) | 1503 if (res != t_true) |
1513 ev_fn = chrec_dont_know; | 1504 { |
1505 ev_fn = chrec_dont_know; | |
1506 /* Try to recognize POLYNOMIAL_CHREC which appears in | |
1507 the form of PEELED_CHREC, but guard the process with | |
1508 a bool variable to keep the analyzer from infinite | |
1509 recurrence for real PEELED_RECs. */ | |
1510 if (simplify_peeled_chrec_p && TREE_CODE (arg) == SSA_NAME) | |
1511 { | |
1512 simplify_peeled_chrec_p = false; | |
1513 ev_fn = simplify_peeled_chrec (loop, arg, init_cond); | |
1514 simplify_peeled_chrec_p = true; | |
1515 } | |
1516 } | |
1514 | 1517 |
1515 /* When there are multiple back edges of the loop (which in fact never | 1518 /* When there are multiple back edges of the loop (which in fact never |
1516 happens currently, but nevertheless), merge their evolutions. */ | 1519 happens currently, but nevertheless), merge their evolutions. */ |
1517 evolution_function = chrec_merge (evolution_function, ev_fn); | 1520 evolution_function = chrec_merge (evolution_function, ev_fn); |
1518 } | 1521 |
1519 | 1522 if (evolution_function == chrec_dont_know) |
1520 if (dump_file && (dump_flags & TDF_DETAILS)) | 1523 break; |
1524 } | |
1525 | |
1526 if (dump_file && (dump_flags & TDF_SCEV)) | |
1521 { | 1527 { |
1522 fprintf (dump_file, " (evolution_function = "); | 1528 fprintf (dump_file, " (evolution_function = "); |
1523 print_generic_expr (dump_file, evolution_function, 0); | 1529 print_generic_expr (dump_file, evolution_function); |
1524 fprintf (dump_file, "))\n"); | 1530 fprintf (dump_file, "))\n"); |
1525 } | 1531 } |
1526 | 1532 |
1527 return evolution_function; | 1533 return evolution_function; |
1534 } | |
1535 | |
1536 /* Looks to see if VAR is a copy of a constant (via straightforward assignments | |
1537 or degenerate phi's). If so, returns the constant; else, returns VAR. */ | |
1538 | |
1539 static tree | |
1540 follow_copies_to_constant (tree var) | |
1541 { | |
1542 tree res = var; | |
1543 while (TREE_CODE (res) == SSA_NAME) | |
1544 { | |
1545 gimple *def = SSA_NAME_DEF_STMT (res); | |
1546 if (gphi *phi = dyn_cast <gphi *> (def)) | |
1547 { | |
1548 if (tree rhs = degenerate_phi_result (phi)) | |
1549 res = rhs; | |
1550 else | |
1551 break; | |
1552 } | |
1553 else if (gimple_assign_single_p (def)) | |
1554 /* Will exit loop if not an SSA_NAME. */ | |
1555 res = gimple_assign_rhs1 (def); | |
1556 else | |
1557 break; | |
1558 } | |
1559 if (CONSTANT_CLASS_P (res)) | |
1560 return res; | |
1561 return var; | |
1528 } | 1562 } |
1529 | 1563 |
1530 /* Given a loop-phi-node, return the initial conditions of the | 1564 /* Given a loop-phi-node, return the initial conditions of the |
1531 variable on entry of the loop. When the CCP has propagated | 1565 variable on entry of the loop. When the CCP has propagated |
1532 constants into the loop-phi-node, the initial condition is | 1566 constants into the loop-phi-node, the initial condition is |
1533 instantiated, otherwise the initial condition is kept symbolic. | 1567 instantiated, otherwise the initial condition is kept symbolic. |
1534 This analyzer does not analyze the evolution outside the current | 1568 This analyzer does not analyze the evolution outside the current |
1535 loop, and leaves this task to the on-demand tree reconstructor. */ | 1569 loop, and leaves this task to the on-demand tree reconstructor. */ |
1536 | 1570 |
1537 static tree | 1571 static tree |
1538 analyze_initial_condition (gimple loop_phi_node) | 1572 analyze_initial_condition (gphi *loop_phi_node) |
1539 { | 1573 { |
1540 int i, n; | 1574 int i, n; |
1541 tree init_cond = chrec_not_analyzed_yet; | 1575 tree init_cond = chrec_not_analyzed_yet; |
1542 struct loop *loop = loop_containing_stmt (loop_phi_node); | 1576 struct loop *loop = loop_containing_stmt (loop_phi_node); |
1543 | 1577 |
1544 if (dump_file && (dump_flags & TDF_DETAILS)) | 1578 if (dump_file && (dump_flags & TDF_SCEV)) |
1545 { | 1579 { |
1546 fprintf (dump_file, "(analyze_initial_condition \n"); | 1580 fprintf (dump_file, "(analyze_initial_condition \n"); |
1547 fprintf (dump_file, " (loop_phi_node = \n"); | 1581 fprintf (dump_file, " (loop_phi_node = \n"); |
1548 print_gimple_stmt (dump_file, loop_phi_node, 0, 0); | 1582 print_gimple_stmt (dump_file, loop_phi_node, 0); |
1549 fprintf (dump_file, ")\n"); | 1583 fprintf (dump_file, ")\n"); |
1550 } | 1584 } |
1551 | 1585 |
1552 n = gimple_phi_num_args (loop_phi_node); | 1586 n = gimple_phi_num_args (loop_phi_node); |
1553 for (i = 0; i < n; i++) | 1587 for (i = 0; i < n; i++) |
1577 | 1611 |
1578 /* Ooops -- a loop without an entry??? */ | 1612 /* Ooops -- a loop without an entry??? */ |
1579 if (init_cond == chrec_not_analyzed_yet) | 1613 if (init_cond == chrec_not_analyzed_yet) |
1580 init_cond = chrec_dont_know; | 1614 init_cond = chrec_dont_know; |
1581 | 1615 |
1582 /* During early loop unrolling we do not have fully constant propagated IL. | 1616 /* We may not have fully constant propagated IL. Handle degenerate PHIs here |
1583 Handle degenerate PHIs here to not miss important unrollings. */ | 1617 to not miss important early loop unrollings. */ |
1584 if (TREE_CODE (init_cond) == SSA_NAME) | 1618 init_cond = follow_copies_to_constant (init_cond); |
1585 { | 1619 |
1586 gimple def = SSA_NAME_DEF_STMT (init_cond); | 1620 if (dump_file && (dump_flags & TDF_SCEV)) |
1587 tree res; | |
1588 if (gimple_code (def) == GIMPLE_PHI | |
1589 && (res = degenerate_phi_result (def)) != NULL_TREE | |
1590 /* Only allow invariants here, otherwise we may break | |
1591 loop-closed SSA form. */ | |
1592 && is_gimple_min_invariant (res)) | |
1593 init_cond = res; | |
1594 } | |
1595 | |
1596 if (dump_file && (dump_flags & TDF_DETAILS)) | |
1597 { | 1621 { |
1598 fprintf (dump_file, " (init_cond = "); | 1622 fprintf (dump_file, " (init_cond = "); |
1599 print_generic_expr (dump_file, init_cond, 0); | 1623 print_generic_expr (dump_file, init_cond); |
1600 fprintf (dump_file, "))\n"); | 1624 fprintf (dump_file, "))\n"); |
1601 } | 1625 } |
1602 | 1626 |
1603 return init_cond; | 1627 return init_cond; |
1604 } | 1628 } |
1605 | 1629 |
1606 /* Analyze the scalar evolution for LOOP_PHI_NODE. */ | 1630 /* Analyze the scalar evolution for LOOP_PHI_NODE. */ |
1607 | 1631 |
1608 static tree | 1632 static tree |
1609 interpret_loop_phi (struct loop *loop, gimple loop_phi_node) | 1633 interpret_loop_phi (struct loop *loop, gphi *loop_phi_node) |
1610 { | 1634 { |
1611 tree res; | 1635 tree res; |
1612 struct loop *phi_loop = loop_containing_stmt (loop_phi_node); | 1636 struct loop *phi_loop = loop_containing_stmt (loop_phi_node); |
1613 tree init_cond; | 1637 tree init_cond; |
1614 | 1638 |
1615 if (phi_loop != loop) | 1639 gcc_assert (phi_loop == loop); |
1616 { | |
1617 struct loop *subloop; | |
1618 tree evolution_fn = analyze_scalar_evolution | |
1619 (phi_loop, PHI_RESULT (loop_phi_node)); | |
1620 | |
1621 /* Dive one level deeper. */ | |
1622 subloop = superloop_at_depth (phi_loop, loop_depth (loop) + 1); | |
1623 | |
1624 /* Interpret the subloop. */ | |
1625 res = compute_overall_effect_of_inner_loop (subloop, evolution_fn); | |
1626 return res; | |
1627 } | |
1628 | 1640 |
1629 /* Otherwise really interpret the loop phi. */ | 1641 /* Otherwise really interpret the loop phi. */ |
1630 init_cond = analyze_initial_condition (loop_phi_node); | 1642 init_cond = analyze_initial_condition (loop_phi_node); |
1631 res = analyze_evolution_in_loop (loop_phi_node, init_cond); | 1643 res = analyze_evolution_in_loop (loop_phi_node, init_cond); |
1632 | 1644 |
1640 new_init = fold_convert (TREE_TYPE (res), | 1652 new_init = fold_convert (TREE_TYPE (res), |
1641 CHREC_LEFT (TREE_OPERAND (res, 0))); | 1653 CHREC_LEFT (TREE_OPERAND (res, 0))); |
1642 else if (TREE_CODE (res) == POLYNOMIAL_CHREC) | 1654 else if (TREE_CODE (res) == POLYNOMIAL_CHREC) |
1643 new_init = CHREC_LEFT (res); | 1655 new_init = CHREC_LEFT (res); |
1644 STRIP_USELESS_TYPE_CONVERSION (new_init); | 1656 STRIP_USELESS_TYPE_CONVERSION (new_init); |
1645 gcc_assert (TREE_CODE (new_init) != POLYNOMIAL_CHREC); | 1657 if (TREE_CODE (new_init) == POLYNOMIAL_CHREC |
1646 if (!operand_equal_p (init_cond, new_init, 0)) | 1658 || !operand_equal_p (init_cond, new_init, 0)) |
1647 return chrec_dont_know; | 1659 return chrec_dont_know; |
1648 } | 1660 } |
1649 | 1661 |
1650 return res; | 1662 return res; |
1651 } | 1663 } |
1653 /* This function merges the branches of a condition-phi-node, | 1665 /* This function merges the branches of a condition-phi-node, |
1654 contained in the outermost loop, and whose arguments are already | 1666 contained in the outermost loop, and whose arguments are already |
1655 analyzed. */ | 1667 analyzed. */ |
1656 | 1668 |
1657 static tree | 1669 static tree |
1658 interpret_condition_phi (struct loop *loop, gimple condition_phi) | 1670 interpret_condition_phi (struct loop *loop, gphi *condition_phi) |
1659 { | 1671 { |
1660 int i, n = gimple_phi_num_args (condition_phi); | 1672 int i, n = gimple_phi_num_args (condition_phi); |
1661 tree res = chrec_not_analyzed_yet; | 1673 tree res = chrec_not_analyzed_yet; |
1662 | 1674 |
1663 for (i = 0; i < n; i++) | 1675 for (i = 0; i < n; i++) |
1672 | 1684 |
1673 branch_chrec = analyze_scalar_evolution | 1685 branch_chrec = analyze_scalar_evolution |
1674 (loop, PHI_ARG_DEF (condition_phi, i)); | 1686 (loop, PHI_ARG_DEF (condition_phi, i)); |
1675 | 1687 |
1676 res = chrec_merge (res, branch_chrec); | 1688 res = chrec_merge (res, branch_chrec); |
1689 if (res == chrec_dont_know) | |
1690 break; | |
1677 } | 1691 } |
1678 | 1692 |
1679 return res; | 1693 return res; |
1680 } | 1694 } |
1681 | 1695 |
1685 return path, this function propagates evolutions (ala constant copy | 1699 return path, this function propagates evolutions (ala constant copy |
1686 propagation). OPND1 is not a GIMPLE expression because we could | 1700 propagation). OPND1 is not a GIMPLE expression because we could |
1687 analyze the effect of an inner loop: see interpret_loop_phi. */ | 1701 analyze the effect of an inner loop: see interpret_loop_phi. */ |
1688 | 1702 |
1689 static tree | 1703 static tree |
1690 interpret_rhs_expr (struct loop *loop, gimple at_stmt, | 1704 interpret_rhs_expr (struct loop *loop, gimple *at_stmt, |
1691 tree type, tree rhs1, enum tree_code code, tree rhs2) | 1705 tree type, tree rhs1, enum tree_code code, tree rhs2) |
1692 { | 1706 { |
1693 tree res, chrec1, chrec2; | 1707 tree res, chrec1, chrec2, ctype; |
1708 gimple *def; | |
1694 | 1709 |
1695 if (get_gimple_rhs_class (code) == GIMPLE_SINGLE_RHS) | 1710 if (get_gimple_rhs_class (code) == GIMPLE_SINGLE_RHS) |
1696 { | 1711 { |
1697 if (is_gimple_min_invariant (rhs1)) | 1712 if (is_gimple_min_invariant (rhs1)) |
1698 return chrec_convert (type, rhs1, at_stmt); | 1713 return chrec_convert (type, rhs1, at_stmt); |
1710 } | 1725 } |
1711 | 1726 |
1712 switch (code) | 1727 switch (code) |
1713 { | 1728 { |
1714 case ADDR_EXPR: | 1729 case ADDR_EXPR: |
1715 /* Handle &MEM[ptr + CST] which is equivalent to POINTER_PLUS_EXPR. */ | 1730 if (TREE_CODE (TREE_OPERAND (rhs1, 0)) == MEM_REF |
1716 if (TREE_CODE (TREE_OPERAND (rhs1, 0)) != MEM_REF) | 1731 || handled_component_p (TREE_OPERAND (rhs1, 0))) |
1717 { | 1732 { |
1718 res = chrec_dont_know; | 1733 machine_mode mode; |
1719 break; | 1734 HOST_WIDE_INT bitsize, bitpos; |
1720 } | 1735 int unsignedp, reversep; |
1721 | 1736 int volatilep = 0; |
1722 rhs2 = TREE_OPERAND (TREE_OPERAND (rhs1, 0), 1); | 1737 tree base, offset; |
1723 rhs1 = TREE_OPERAND (TREE_OPERAND (rhs1, 0), 0); | 1738 tree chrec3; |
1724 /* Fall through. */ | 1739 tree unitpos; |
1740 | |
1741 base = get_inner_reference (TREE_OPERAND (rhs1, 0), | |
1742 &bitsize, &bitpos, &offset, &mode, | |
1743 &unsignedp, &reversep, &volatilep); | |
1744 | |
1745 if (TREE_CODE (base) == MEM_REF) | |
1746 { | |
1747 rhs2 = TREE_OPERAND (base, 1); | |
1748 rhs1 = TREE_OPERAND (base, 0); | |
1749 | |
1750 chrec1 = analyze_scalar_evolution (loop, rhs1); | |
1751 chrec2 = analyze_scalar_evolution (loop, rhs2); | |
1752 chrec1 = chrec_convert (type, chrec1, at_stmt); | |
1753 chrec2 = chrec_convert (TREE_TYPE (rhs2), chrec2, at_stmt); | |
1754 chrec1 = instantiate_parameters (loop, chrec1); | |
1755 chrec2 = instantiate_parameters (loop, chrec2); | |
1756 res = chrec_fold_plus (type, chrec1, chrec2); | |
1757 } | |
1758 else | |
1759 { | |
1760 chrec1 = analyze_scalar_evolution_for_address_of (loop, base); | |
1761 chrec1 = chrec_convert (type, chrec1, at_stmt); | |
1762 res = chrec1; | |
1763 } | |
1764 | |
1765 if (offset != NULL_TREE) | |
1766 { | |
1767 chrec2 = analyze_scalar_evolution (loop, offset); | |
1768 chrec2 = chrec_convert (TREE_TYPE (offset), chrec2, at_stmt); | |
1769 chrec2 = instantiate_parameters (loop, chrec2); | |
1770 res = chrec_fold_plus (type, res, chrec2); | |
1771 } | |
1772 | |
1773 if (bitpos != 0) | |
1774 { | |
1775 gcc_assert ((bitpos % BITS_PER_UNIT) == 0); | |
1776 | |
1777 unitpos = size_int (bitpos / BITS_PER_UNIT); | |
1778 chrec3 = analyze_scalar_evolution (loop, unitpos); | |
1779 chrec3 = chrec_convert (TREE_TYPE (unitpos), chrec3, at_stmt); | |
1780 chrec3 = instantiate_parameters (loop, chrec3); | |
1781 res = chrec_fold_plus (type, res, chrec3); | |
1782 } | |
1783 } | |
1784 else | |
1785 res = chrec_dont_know; | |
1786 break; | |
1725 | 1787 |
1726 case POINTER_PLUS_EXPR: | 1788 case POINTER_PLUS_EXPR: |
1727 chrec1 = analyze_scalar_evolution (loop, rhs1); | 1789 chrec1 = analyze_scalar_evolution (loop, rhs1); |
1728 chrec2 = analyze_scalar_evolution (loop, rhs2); | 1790 chrec2 = analyze_scalar_evolution (loop, rhs2); |
1729 chrec1 = chrec_convert (type, chrec1, at_stmt); | 1791 chrec1 = chrec_convert (type, chrec1, at_stmt); |
1730 chrec2 = chrec_convert (sizetype, chrec2, at_stmt); | 1792 chrec2 = chrec_convert (TREE_TYPE (rhs2), chrec2, at_stmt); |
1793 chrec1 = instantiate_parameters (loop, chrec1); | |
1794 chrec2 = instantiate_parameters (loop, chrec2); | |
1731 res = chrec_fold_plus (type, chrec1, chrec2); | 1795 res = chrec_fold_plus (type, chrec1, chrec2); |
1732 break; | 1796 break; |
1733 | 1797 |
1734 case PLUS_EXPR: | 1798 case PLUS_EXPR: |
1735 chrec1 = analyze_scalar_evolution (loop, rhs1); | 1799 chrec1 = analyze_scalar_evolution (loop, rhs1); |
1736 chrec2 = analyze_scalar_evolution (loop, rhs2); | 1800 chrec2 = analyze_scalar_evolution (loop, rhs2); |
1737 chrec1 = chrec_convert (type, chrec1, at_stmt); | 1801 ctype = type; |
1738 chrec2 = chrec_convert (type, chrec2, at_stmt); | 1802 /* When the stmt is conditionally executed re-write the CHREC |
1739 res = chrec_fold_plus (type, chrec1, chrec2); | 1803 into a form that has well-defined behavior on overflow. */ |
1804 if (at_stmt | |
1805 && INTEGRAL_TYPE_P (type) | |
1806 && ! TYPE_OVERFLOW_WRAPS (type) | |
1807 && ! dominated_by_p (CDI_DOMINATORS, loop->latch, | |
1808 gimple_bb (at_stmt))) | |
1809 ctype = unsigned_type_for (type); | |
1810 chrec1 = chrec_convert (ctype, chrec1, at_stmt); | |
1811 chrec2 = chrec_convert (ctype, chrec2, at_stmt); | |
1812 chrec1 = instantiate_parameters (loop, chrec1); | |
1813 chrec2 = instantiate_parameters (loop, chrec2); | |
1814 res = chrec_fold_plus (ctype, chrec1, chrec2); | |
1815 if (type != ctype) | |
1816 res = chrec_convert (type, res, at_stmt); | |
1740 break; | 1817 break; |
1741 | 1818 |
1742 case MINUS_EXPR: | 1819 case MINUS_EXPR: |
1743 chrec1 = analyze_scalar_evolution (loop, rhs1); | 1820 chrec1 = analyze_scalar_evolution (loop, rhs1); |
1744 chrec2 = analyze_scalar_evolution (loop, rhs2); | 1821 chrec2 = analyze_scalar_evolution (loop, rhs2); |
1745 chrec1 = chrec_convert (type, chrec1, at_stmt); | 1822 ctype = type; |
1746 chrec2 = chrec_convert (type, chrec2, at_stmt); | 1823 /* When the stmt is conditionally executed re-write the CHREC |
1747 res = chrec_fold_minus (type, chrec1, chrec2); | 1824 into a form that has well-defined behavior on overflow. */ |
1825 if (at_stmt | |
1826 && INTEGRAL_TYPE_P (type) | |
1827 && ! TYPE_OVERFLOW_WRAPS (type) | |
1828 && ! dominated_by_p (CDI_DOMINATORS, | |
1829 loop->latch, gimple_bb (at_stmt))) | |
1830 ctype = unsigned_type_for (type); | |
1831 chrec1 = chrec_convert (ctype, chrec1, at_stmt); | |
1832 chrec2 = chrec_convert (ctype, chrec2, at_stmt); | |
1833 chrec1 = instantiate_parameters (loop, chrec1); | |
1834 chrec2 = instantiate_parameters (loop, chrec2); | |
1835 res = chrec_fold_minus (ctype, chrec1, chrec2); | |
1836 if (type != ctype) | |
1837 res = chrec_convert (type, res, at_stmt); | |
1748 break; | 1838 break; |
1749 | 1839 |
1750 case NEGATE_EXPR: | 1840 case NEGATE_EXPR: |
1751 chrec1 = analyze_scalar_evolution (loop, rhs1); | 1841 chrec1 = analyze_scalar_evolution (loop, rhs1); |
1752 chrec1 = chrec_convert (type, chrec1, at_stmt); | 1842 ctype = type; |
1843 /* When the stmt is conditionally executed re-write the CHREC | |
1844 into a form that has well-defined behavior on overflow. */ | |
1845 if (at_stmt | |
1846 && INTEGRAL_TYPE_P (type) | |
1847 && ! TYPE_OVERFLOW_WRAPS (type) | |
1848 && ! dominated_by_p (CDI_DOMINATORS, | |
1849 loop->latch, gimple_bb (at_stmt))) | |
1850 ctype = unsigned_type_for (type); | |
1851 chrec1 = chrec_convert (ctype, chrec1, at_stmt); | |
1753 /* TYPE may be integer, real or complex, so use fold_convert. */ | 1852 /* TYPE may be integer, real or complex, so use fold_convert. */ |
1754 res = chrec_fold_multiply (type, chrec1, | 1853 chrec1 = instantiate_parameters (loop, chrec1); |
1755 fold_convert (type, integer_minus_one_node)); | 1854 res = chrec_fold_multiply (ctype, chrec1, |
1855 fold_convert (ctype, integer_minus_one_node)); | |
1856 if (type != ctype) | |
1857 res = chrec_convert (type, res, at_stmt); | |
1756 break; | 1858 break; |
1757 | 1859 |
1758 case BIT_NOT_EXPR: | 1860 case BIT_NOT_EXPR: |
1759 /* Handle ~X as -1 - X. */ | 1861 /* Handle ~X as -1 - X. */ |
1760 chrec1 = analyze_scalar_evolution (loop, rhs1); | 1862 chrec1 = analyze_scalar_evolution (loop, rhs1); |
1761 chrec1 = chrec_convert (type, chrec1, at_stmt); | 1863 chrec1 = chrec_convert (type, chrec1, at_stmt); |
1864 chrec1 = instantiate_parameters (loop, chrec1); | |
1762 res = chrec_fold_minus (type, | 1865 res = chrec_fold_minus (type, |
1763 fold_convert (type, integer_minus_one_node), | 1866 fold_convert (type, integer_minus_one_node), |
1764 chrec1); | 1867 chrec1); |
1765 break; | 1868 break; |
1766 | 1869 |
1767 case MULT_EXPR: | 1870 case MULT_EXPR: |
1768 chrec1 = analyze_scalar_evolution (loop, rhs1); | 1871 chrec1 = analyze_scalar_evolution (loop, rhs1); |
1769 chrec2 = analyze_scalar_evolution (loop, rhs2); | 1872 chrec2 = analyze_scalar_evolution (loop, rhs2); |
1770 chrec1 = chrec_convert (type, chrec1, at_stmt); | 1873 ctype = type; |
1771 chrec2 = chrec_convert (type, chrec2, at_stmt); | 1874 /* When the stmt is conditionally executed re-write the CHREC |
1772 res = chrec_fold_multiply (type, chrec1, chrec2); | 1875 into a form that has well-defined behavior on overflow. */ |
1876 if (at_stmt | |
1877 && INTEGRAL_TYPE_P (type) | |
1878 && ! TYPE_OVERFLOW_WRAPS (type) | |
1879 && ! dominated_by_p (CDI_DOMINATORS, | |
1880 loop->latch, gimple_bb (at_stmt))) | |
1881 ctype = unsigned_type_for (type); | |
1882 chrec1 = chrec_convert (ctype, chrec1, at_stmt); | |
1883 chrec2 = chrec_convert (ctype, chrec2, at_stmt); | |
1884 chrec1 = instantiate_parameters (loop, chrec1); | |
1885 chrec2 = instantiate_parameters (loop, chrec2); | |
1886 res = chrec_fold_multiply (ctype, chrec1, chrec2); | |
1887 if (type != ctype) | |
1888 res = chrec_convert (type, res, at_stmt); | |
1773 break; | 1889 break; |
1774 | 1890 |
1891 case LSHIFT_EXPR: | |
1892 { | |
1893 /* Handle A<<B as A * (1<<B). */ | |
1894 tree uns = unsigned_type_for (type); | |
1895 chrec1 = analyze_scalar_evolution (loop, rhs1); | |
1896 chrec2 = analyze_scalar_evolution (loop, rhs2); | |
1897 chrec1 = chrec_convert (uns, chrec1, at_stmt); | |
1898 chrec1 = instantiate_parameters (loop, chrec1); | |
1899 chrec2 = instantiate_parameters (loop, chrec2); | |
1900 | |
1901 tree one = build_int_cst (uns, 1); | |
1902 chrec2 = fold_build2 (LSHIFT_EXPR, uns, one, chrec2); | |
1903 res = chrec_fold_multiply (uns, chrec1, chrec2); | |
1904 res = chrec_convert (type, res, at_stmt); | |
1905 } | |
1906 break; | |
1907 | |
1775 CASE_CONVERT: | 1908 CASE_CONVERT: |
1776 chrec1 = analyze_scalar_evolution (loop, rhs1); | 1909 /* In case we have a truncation of a widened operation that in |
1777 res = chrec_convert (type, chrec1, at_stmt); | 1910 the truncated type has undefined overflow behavior analyze |
1911 the operation done in an unsigned type of the same precision | |
1912 as the final truncation. We cannot derive a scalar evolution | |
1913 for the widened operation but for the truncated result. */ | |
1914 if (TREE_CODE (type) == INTEGER_TYPE | |
1915 && TREE_CODE (TREE_TYPE (rhs1)) == INTEGER_TYPE | |
1916 && TYPE_PRECISION (type) < TYPE_PRECISION (TREE_TYPE (rhs1)) | |
1917 && TYPE_OVERFLOW_UNDEFINED (type) | |
1918 && TREE_CODE (rhs1) == SSA_NAME | |
1919 && (def = SSA_NAME_DEF_STMT (rhs1)) | |
1920 && is_gimple_assign (def) | |
1921 && TREE_CODE_CLASS (gimple_assign_rhs_code (def)) == tcc_binary | |
1922 && TREE_CODE (gimple_assign_rhs2 (def)) == INTEGER_CST) | |
1923 { | |
1924 tree utype = unsigned_type_for (type); | |
1925 chrec1 = interpret_rhs_expr (loop, at_stmt, utype, | |
1926 gimple_assign_rhs1 (def), | |
1927 gimple_assign_rhs_code (def), | |
1928 gimple_assign_rhs2 (def)); | |
1929 } | |
1930 else | |
1931 chrec1 = analyze_scalar_evolution (loop, rhs1); | |
1932 res = chrec_convert (type, chrec1, at_stmt, true, rhs1); | |
1933 break; | |
1934 | |
1935 case BIT_AND_EXPR: | |
1936 /* Given int variable A, handle A&0xffff as (int)(unsigned short)A. | |
1937 If A is SCEV and its value is in the range of representable set | |
1938 of type unsigned short, the result expression is a (no-overflow) | |
1939 SCEV. */ | |
1940 res = chrec_dont_know; | |
1941 if (tree_fits_uhwi_p (rhs2)) | |
1942 { | |
1943 int precision; | |
1944 unsigned HOST_WIDE_INT val = tree_to_uhwi (rhs2); | |
1945 | |
1946 val ++; | |
1947 /* Skip if value of rhs2 wraps in unsigned HOST_WIDE_INT or | |
1948 it's not the maximum value of a smaller type than rhs1. */ | |
1949 if (val != 0 | |
1950 && (precision = exact_log2 (val)) > 0 | |
1951 && (unsigned) precision < TYPE_PRECISION (TREE_TYPE (rhs1))) | |
1952 { | |
1953 tree utype = build_nonstandard_integer_type (precision, 1); | |
1954 | |
1955 if (TYPE_PRECISION (utype) < TYPE_PRECISION (TREE_TYPE (rhs1))) | |
1956 { | |
1957 chrec1 = analyze_scalar_evolution (loop, rhs1); | |
1958 chrec1 = chrec_convert (utype, chrec1, at_stmt); | |
1959 res = chrec_convert (TREE_TYPE (rhs1), chrec1, at_stmt); | |
1960 } | |
1961 } | |
1962 } | |
1778 break; | 1963 break; |
1779 | 1964 |
1780 default: | 1965 default: |
1781 res = chrec_dont_know; | 1966 res = chrec_dont_know; |
1782 break; | 1967 break; |
1786 } | 1971 } |
1787 | 1972 |
1788 /* Interpret the expression EXPR. */ | 1973 /* Interpret the expression EXPR. */ |
1789 | 1974 |
1790 static tree | 1975 static tree |
1791 interpret_expr (struct loop *loop, gimple at_stmt, tree expr) | 1976 interpret_expr (struct loop *loop, gimple *at_stmt, tree expr) |
1792 { | 1977 { |
1793 enum tree_code code; | 1978 enum tree_code code; |
1794 tree type = TREE_TYPE (expr), op0, op1; | 1979 tree type = TREE_TYPE (expr), op0, op1; |
1795 | 1980 |
1796 if (automatically_generated_chrec_p (expr)) | 1981 if (automatically_generated_chrec_p (expr)) |
1797 return expr; | 1982 return expr; |
1798 | 1983 |
1799 if (TREE_CODE (expr) == POLYNOMIAL_CHREC) | 1984 if (TREE_CODE (expr) == POLYNOMIAL_CHREC |
1985 || get_gimple_rhs_class (TREE_CODE (expr)) == GIMPLE_TERNARY_RHS) | |
1800 return chrec_dont_know; | 1986 return chrec_dont_know; |
1801 | 1987 |
1802 extract_ops_from_tree (expr, &code, &op0, &op1); | 1988 extract_ops_from_tree (expr, &code, &op0, &op1); |
1803 | 1989 |
1804 return interpret_rhs_expr (loop, at_stmt, type, | 1990 return interpret_rhs_expr (loop, at_stmt, type, |
1806 } | 1992 } |
1807 | 1993 |
1808 /* Interpret the rhs of the assignment STMT. */ | 1994 /* Interpret the rhs of the assignment STMT. */ |
1809 | 1995 |
1810 static tree | 1996 static tree |
1811 interpret_gimple_assign (struct loop *loop, gimple stmt) | 1997 interpret_gimple_assign (struct loop *loop, gimple *stmt) |
1812 { | 1998 { |
1813 tree type = TREE_TYPE (gimple_assign_lhs (stmt)); | 1999 tree type = TREE_TYPE (gimple_assign_lhs (stmt)); |
1814 enum tree_code code = gimple_assign_rhs_code (stmt); | 2000 enum tree_code code = gimple_assign_rhs_code (stmt); |
1815 | 2001 |
1816 return interpret_rhs_expr (loop, stmt, type, | 2002 return interpret_rhs_expr (loop, stmt, type, |
1824 - number_of_iterations_in_loop, | 2010 - number_of_iterations_in_loop, |
1825 - analyze_scalar_evolution, | 2011 - analyze_scalar_evolution, |
1826 - instantiate_parameters. | 2012 - instantiate_parameters. |
1827 */ | 2013 */ |
1828 | 2014 |
1829 /* Compute and return the evolution function in WRTO_LOOP, the nearest | 2015 /* Helper recursive function. */ |
1830 common ancestor of DEF_LOOP and USE_LOOP. */ | |
1831 | 2016 |
1832 static tree | 2017 static tree |
1833 compute_scalar_evolution_in_loop (struct loop *wrto_loop, | 2018 analyze_scalar_evolution_1 (struct loop *loop, tree var) |
1834 struct loop *def_loop, | 2019 { |
1835 tree ev) | 2020 gimple *def; |
1836 { | |
1837 bool val; | |
1838 tree res; | |
1839 | |
1840 if (def_loop == wrto_loop) | |
1841 return ev; | |
1842 | |
1843 def_loop = superloop_at_depth (def_loop, loop_depth (wrto_loop) + 1); | |
1844 res = compute_overall_effect_of_inner_loop (def_loop, ev); | |
1845 | |
1846 if (no_evolution_in_loop_p (res, wrto_loop->num, &val) && val) | |
1847 return res; | |
1848 | |
1849 return analyze_scalar_evolution_1 (wrto_loop, res, chrec_not_analyzed_yet); | |
1850 } | |
1851 | |
1852 /* Helper recursive function. */ | |
1853 | |
1854 static tree | |
1855 analyze_scalar_evolution_1 (struct loop *loop, tree var, tree res) | |
1856 { | |
1857 tree type = TREE_TYPE (var); | |
1858 gimple def; | |
1859 basic_block bb; | 2021 basic_block bb; |
1860 struct loop *def_loop; | 2022 struct loop *def_loop; |
1861 | 2023 tree res; |
1862 if (loop == NULL || TREE_CODE (type) == VECTOR_TYPE) | |
1863 return chrec_dont_know; | |
1864 | 2024 |
1865 if (TREE_CODE (var) != SSA_NAME) | 2025 if (TREE_CODE (var) != SSA_NAME) |
1866 return interpret_expr (loop, NULL, var); | 2026 return interpret_expr (loop, NULL, var); |
1867 | 2027 |
1868 def = SSA_NAME_DEF_STMT (var); | 2028 def = SSA_NAME_DEF_STMT (var); |
1869 bb = gimple_bb (def); | 2029 bb = gimple_bb (def); |
1870 def_loop = bb ? bb->loop_father : NULL; | 2030 def_loop = bb->loop_father; |
1871 | 2031 |
1872 if (bb == NULL | 2032 if (!flow_bb_inside_loop_p (loop, bb)) |
1873 || !flow_bb_inside_loop_p (loop, bb)) | 2033 { |
1874 { | 2034 /* Keep symbolic form, but look through obvious copies for constants. */ |
1875 /* Keep the symbolic form. */ | 2035 res = follow_copies_to_constant (var); |
1876 res = var; | |
1877 goto set_and_end; | 2036 goto set_and_end; |
1878 } | 2037 } |
1879 | 2038 |
1880 if (res != chrec_not_analyzed_yet) | |
1881 { | |
1882 if (loop != bb->loop_father) | |
1883 res = compute_scalar_evolution_in_loop | |
1884 (find_common_loop (loop, bb->loop_father), bb->loop_father, res); | |
1885 | |
1886 goto set_and_end; | |
1887 } | |
1888 | |
1889 if (loop != def_loop) | 2039 if (loop != def_loop) |
1890 { | 2040 { |
1891 res = analyze_scalar_evolution_1 (def_loop, var, chrec_not_analyzed_yet); | 2041 res = analyze_scalar_evolution_1 (def_loop, var); |
1892 res = compute_scalar_evolution_in_loop (loop, def_loop, res); | 2042 struct loop *loop_to_skip = superloop_at_depth (def_loop, |
1893 | 2043 loop_depth (loop) + 1); |
2044 res = compute_overall_effect_of_inner_loop (loop_to_skip, res); | |
2045 if (chrec_contains_symbols_defined_in_loop (res, loop->num)) | |
2046 res = analyze_scalar_evolution_1 (loop, res); | |
1894 goto set_and_end; | 2047 goto set_and_end; |
1895 } | 2048 } |
1896 | 2049 |
1897 switch (gimple_code (def)) | 2050 switch (gimple_code (def)) |
1898 { | 2051 { |
1900 res = interpret_gimple_assign (loop, def); | 2053 res = interpret_gimple_assign (loop, def); |
1901 break; | 2054 break; |
1902 | 2055 |
1903 case GIMPLE_PHI: | 2056 case GIMPLE_PHI: |
1904 if (loop_phi_node_p (def)) | 2057 if (loop_phi_node_p (def)) |
1905 res = interpret_loop_phi (loop, def); | 2058 res = interpret_loop_phi (loop, as_a <gphi *> (def)); |
1906 else | 2059 else |
1907 res = interpret_condition_phi (loop, def); | 2060 res = interpret_condition_phi (loop, as_a <gphi *> (def)); |
1908 break; | 2061 break; |
1909 | 2062 |
1910 default: | 2063 default: |
1911 res = chrec_dont_know; | 2064 res = chrec_dont_know; |
1912 break; | 2065 break; |
1940 tree | 2093 tree |
1941 analyze_scalar_evolution (struct loop *loop, tree var) | 2094 analyze_scalar_evolution (struct loop *loop, tree var) |
1942 { | 2095 { |
1943 tree res; | 2096 tree res; |
1944 | 2097 |
1945 if (dump_file && (dump_flags & TDF_DETAILS)) | 2098 /* ??? Fix callers. */ |
2099 if (! loop) | |
2100 return var; | |
2101 | |
2102 if (dump_file && (dump_flags & TDF_SCEV)) | |
1946 { | 2103 { |
1947 fprintf (dump_file, "(analyze_scalar_evolution \n"); | 2104 fprintf (dump_file, "(analyze_scalar_evolution \n"); |
1948 fprintf (dump_file, " (loop_nb = %d)\n", loop->num); | 2105 fprintf (dump_file, " (loop_nb = %d)\n", loop->num); |
1949 fprintf (dump_file, " (scalar = "); | 2106 fprintf (dump_file, " (scalar = "); |
1950 print_generic_expr (dump_file, var, 0); | 2107 print_generic_expr (dump_file, var); |
1951 fprintf (dump_file, ")\n"); | 2108 fprintf (dump_file, ")\n"); |
1952 } | 2109 } |
1953 | 2110 |
1954 res = get_scalar_evolution (block_before_loop (loop), var); | 2111 res = get_scalar_evolution (block_before_loop (loop), var); |
1955 res = analyze_scalar_evolution_1 (loop, var, res); | 2112 if (res == chrec_not_analyzed_yet) |
1956 | 2113 res = analyze_scalar_evolution_1 (loop, var); |
1957 if (dump_file && (dump_flags & TDF_DETAILS)) | 2114 |
2115 if (dump_file && (dump_flags & TDF_SCEV)) | |
1958 fprintf (dump_file, ")\n"); | 2116 fprintf (dump_file, ")\n"); |
1959 | 2117 |
1960 return res; | 2118 return res; |
2119 } | |
2120 | |
2121 /* Analyzes and returns the scalar evolution of VAR address in LOOP. */ | |
2122 | |
2123 static tree | |
2124 analyze_scalar_evolution_for_address_of (struct loop *loop, tree var) | |
2125 { | |
2126 return analyze_scalar_evolution (loop, build_fold_addr_expr (var)); | |
1961 } | 2127 } |
1962 | 2128 |
1963 /* Analyze scalar evolution of use of VERSION in USE_LOOP with respect to | 2129 /* Analyze scalar evolution of use of VERSION in USE_LOOP with respect to |
1964 WRTO_LOOP (which should be a superloop of USE_LOOP) | 2130 WRTO_LOOP (which should be a superloop of USE_LOOP) |
1965 | 2131 |
2018 tree ev = version, tmp; | 2184 tree ev = version, tmp; |
2019 | 2185 |
2020 /* We cannot just do | 2186 /* We cannot just do |
2021 | 2187 |
2022 tmp = analyze_scalar_evolution (use_loop, version); | 2188 tmp = analyze_scalar_evolution (use_loop, version); |
2023 ev = resolve_mixers (wrto_loop, tmp); | 2189 ev = resolve_mixers (wrto_loop, tmp, folded_casts); |
2024 | 2190 |
2025 as resolve_mixers would query the scalar evolution with respect to | 2191 as resolve_mixers would query the scalar evolution with respect to |
2026 wrto_loop. For example, in the situation described in the function | 2192 wrto_loop. For example, in the situation described in the function |
2027 comment, suppose that wrto_loop = loop1, use_loop = loop3 and | 2193 comment, suppose that wrto_loop = loop1, use_loop = loop3 and |
2028 version = k2. Then | 2194 version = k2. Then |
2029 | 2195 |
2030 analyze_scalar_evolution (use_loop, version) = k2 | 2196 analyze_scalar_evolution (use_loop, version) = k2 |
2031 | 2197 |
2032 and resolve_mixers (loop1, k2) finds that the value of k2 in loop 1 | 2198 and resolve_mixers (loop1, k2, folded_casts) finds that the value of |
2033 is 100, which is a wrong result, since we are interested in the | 2199 k2 in loop 1 is 100, which is a wrong result, since we are interested |
2034 value in loop 3. | 2200 in the value in loop 3. |
2035 | 2201 |
2036 Instead, we need to proceed from use_loop to wrto_loop loop by loop, | 2202 Instead, we need to proceed from use_loop to wrto_loop loop by loop, |
2037 each time checking that there is no evolution in the inner loop. */ | 2203 each time checking that there is no evolution in the inner loop. */ |
2038 | 2204 |
2039 if (folded_casts) | 2205 if (folded_casts) |
2040 *folded_casts = false; | 2206 *folded_casts = false; |
2041 while (1) | 2207 while (1) |
2042 { | 2208 { |
2043 tmp = analyze_scalar_evolution (use_loop, ev); | 2209 tmp = analyze_scalar_evolution (use_loop, ev); |
2044 ev = resolve_mixers (use_loop, tmp); | 2210 ev = resolve_mixers (use_loop, tmp, folded_casts); |
2045 | |
2046 if (folded_casts && tmp != ev) | |
2047 *folded_casts = true; | |
2048 | 2211 |
2049 if (use_loop == wrto_loop) | 2212 if (use_loop == wrto_loop) |
2050 return ev; | 2213 return ev; |
2051 | 2214 |
2052 /* If the value of the use changes in the inner loop, we cannot express | 2215 /* If the value of the use changes in the inner loop, we cannot express |
2058 | 2221 |
2059 use_loop = loop_outer (use_loop); | 2222 use_loop = loop_outer (use_loop); |
2060 } | 2223 } |
2061 } | 2224 } |
2062 | 2225 |
2063 /* Returns from CACHE the value for VERSION instantiated below | 2226 |
2064 INSTANTIATED_BELOW block. */ | 2227 /* Hashtable helpers for a temporary hash-table used when |
2065 | 2228 instantiating a CHREC or resolving mixers. For this use |
2066 static tree | 2229 instantiated_below is always the same. */ |
2067 get_instantiated_value (htab_t cache, basic_block instantiated_below, | 2230 |
2068 tree version) | 2231 struct instantiate_cache_type |
2069 { | 2232 { |
2070 struct scev_info_str *info, pattern; | 2233 htab_t map; |
2071 | 2234 vec<scev_info_str> entries; |
2072 pattern.var = version; | 2235 |
2073 pattern.instantiated_below = instantiated_below; | 2236 instantiate_cache_type () : map (NULL), entries (vNULL) {} |
2074 info = (struct scev_info_str *) htab_find (cache, &pattern); | 2237 ~instantiate_cache_type (); |
2075 | 2238 tree get (unsigned slot) { return entries[slot].chrec; } |
2076 if (info) | 2239 void set (unsigned slot, tree chrec) { entries[slot].chrec = chrec; } |
2077 return info->chrec; | 2240 }; |
2078 else | 2241 |
2079 return NULL_TREE; | 2242 instantiate_cache_type::~instantiate_cache_type () |
2080 } | 2243 { |
2081 | 2244 if (map != NULL) |
2082 /* Sets in CACHE the value of VERSION instantiated below basic block | 2245 { |
2083 INSTANTIATED_BELOW to VAL. */ | 2246 htab_delete (map); |
2084 | 2247 entries.release (); |
2085 static void | 2248 } |
2086 set_instantiated_value (htab_t cache, basic_block instantiated_below, | 2249 } |
2087 tree version, tree val) | 2250 |
2088 { | 2251 /* Cache to avoid infinite recursion when instantiating an SSA name. |
2089 struct scev_info_str *info, pattern; | 2252 Live during the outermost instantiate_scev or resolve_mixers call. */ |
2090 PTR *slot; | 2253 static instantiate_cache_type *global_cache; |
2091 | 2254 |
2092 pattern.var = version; | 2255 /* Computes a hash function for database element ELT. */ |
2093 pattern.instantiated_below = instantiated_below; | 2256 |
2094 slot = htab_find_slot (cache, &pattern, INSERT); | 2257 static inline hashval_t |
2095 | 2258 hash_idx_scev_info (const void *elt_) |
2259 { | |
2260 unsigned idx = ((size_t) elt_) - 2; | |
2261 return scev_info_hasher::hash (&global_cache->entries[idx]); | |
2262 } | |
2263 | |
2264 /* Compares database elements E1 and E2. */ | |
2265 | |
2266 static inline int | |
2267 eq_idx_scev_info (const void *e1, const void *e2) | |
2268 { | |
2269 unsigned idx1 = ((size_t) e1) - 2; | |
2270 return scev_info_hasher::equal (&global_cache->entries[idx1], | |
2271 (const scev_info_str *) e2); | |
2272 } | |
2273 | |
2274 /* Returns from CACHE the slot number of the cached chrec for NAME. */ | |
2275 | |
2276 static unsigned | |
2277 get_instantiated_value_entry (instantiate_cache_type &cache, | |
2278 tree name, edge instantiate_below) | |
2279 { | |
2280 if (!cache.map) | |
2281 { | |
2282 cache.map = htab_create (10, hash_idx_scev_info, eq_idx_scev_info, NULL); | |
2283 cache.entries.create (10); | |
2284 } | |
2285 | |
2286 scev_info_str e; | |
2287 e.name_version = SSA_NAME_VERSION (name); | |
2288 e.instantiated_below = instantiate_below->dest->index; | |
2289 void **slot = htab_find_slot_with_hash (cache.map, &e, | |
2290 scev_info_hasher::hash (&e), INSERT); | |
2096 if (!*slot) | 2291 if (!*slot) |
2097 *slot = new_scev_info_str (instantiated_below, version); | 2292 { |
2098 info = (struct scev_info_str *) *slot; | 2293 e.chrec = chrec_not_analyzed_yet; |
2099 info->chrec = val; | 2294 *slot = (void *)(size_t)(cache.entries.length () + 2); |
2100 } | 2295 cache.entries.safe_push (e); |
2296 } | |
2297 | |
2298 return ((size_t)*slot) - 2; | |
2299 } | |
2300 | |
2101 | 2301 |
2102 /* Return the closed_loop_phi node for VAR. If there is none, return | 2302 /* Return the closed_loop_phi node for VAR. If there is none, return |
2103 NULL_TREE. */ | 2303 NULL_TREE. */ |
2104 | 2304 |
2105 static tree | 2305 static tree |
2106 loop_closed_phi_def (tree var) | 2306 loop_closed_phi_def (tree var) |
2107 { | 2307 { |
2108 struct loop *loop; | 2308 struct loop *loop; |
2109 edge exit; | 2309 edge exit; |
2110 gimple phi; | 2310 gphi *phi; |
2111 gimple_stmt_iterator psi; | 2311 gphi_iterator psi; |
2112 | 2312 |
2113 if (var == NULL_TREE | 2313 if (var == NULL_TREE |
2114 || TREE_CODE (var) != SSA_NAME) | 2314 || TREE_CODE (var) != SSA_NAME) |
2115 return NULL_TREE; | 2315 return NULL_TREE; |
2116 | 2316 |
2119 if (!exit) | 2319 if (!exit) |
2120 return NULL_TREE; | 2320 return NULL_TREE; |
2121 | 2321 |
2122 for (psi = gsi_start_phis (exit->dest); !gsi_end_p (psi); gsi_next (&psi)) | 2322 for (psi = gsi_start_phis (exit->dest); !gsi_end_p (psi); gsi_next (&psi)) |
2123 { | 2323 { |
2124 phi = gsi_stmt (psi); | 2324 phi = psi.phi (); |
2125 if (PHI_ARG_DEF_FROM_EDGE (phi, exit) == var) | 2325 if (PHI_ARG_DEF_FROM_EDGE (phi, exit) == var) |
2126 return PHI_RESULT (phi); | 2326 return PHI_RESULT (phi); |
2127 } | 2327 } |
2128 | 2328 |
2129 return NULL_TREE; | 2329 return NULL_TREE; |
2130 } | 2330 } |
2131 | 2331 |
2132 static tree instantiate_scev_r (basic_block, struct loop *, tree, bool, | 2332 static tree instantiate_scev_r (edge, struct loop *, struct loop *, |
2133 htab_t, int); | 2333 tree, bool *, int); |
2134 | 2334 |
2135 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW | 2335 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW |
2136 and EVOLUTION_LOOP, that were left under a symbolic form. | 2336 and EVOLUTION_LOOP, that were left under a symbolic form. |
2137 | 2337 |
2138 CHREC is an SSA_NAME to be instantiated. | 2338 CHREC is an SSA_NAME to be instantiated. |
2139 | 2339 |
2140 CACHE is the cache of already instantiated values. | 2340 CACHE is the cache of already instantiated values. |
2141 | 2341 |
2142 FOLD_CONVERSIONS should be set to true when the conversions that | 2342 Variable pointed by FOLD_CONVERSIONS is set to TRUE when the |
2143 may wrap in signed/pointer type are folded, as long as the value of | 2343 conversions that may wrap in signed/pointer type are folded, as long |
2144 the chrec is preserved. | 2344 as the value of the chrec is preserved. If FOLD_CONVERSIONS is NULL |
2345 then we don't do such fold. | |
2145 | 2346 |
2146 SIZE_EXPR is used for computing the size of the expression to be | 2347 SIZE_EXPR is used for computing the size of the expression to be |
2147 instantiated, and to stop if it exceeds some limit. */ | 2348 instantiated, and to stop if it exceeds some limit. */ |
2148 | 2349 |
2149 static tree | 2350 static tree |
2150 instantiate_scev_name (basic_block instantiate_below, | 2351 instantiate_scev_name (edge instantiate_below, |
2151 struct loop *evolution_loop, tree chrec, | 2352 struct loop *evolution_loop, struct loop *inner_loop, |
2152 bool fold_conversions, htab_t cache, int size_expr) | 2353 tree chrec, |
2354 bool *fold_conversions, | |
2355 int size_expr) | |
2153 { | 2356 { |
2154 tree res; | 2357 tree res; |
2155 struct loop *def_loop; | 2358 struct loop *def_loop; |
2156 basic_block def_bb = gimple_bb (SSA_NAME_DEF_STMT (chrec)); | 2359 basic_block def_bb = gimple_bb (SSA_NAME_DEF_STMT (chrec)); |
2157 | 2360 |
2158 /* A parameter (or loop invariant and we do not want to include | 2361 /* A parameter, nothing to do. */ |
2159 evolutions in outer loops), nothing to do. */ | |
2160 if (!def_bb | 2362 if (!def_bb |
2161 || loop_depth (def_bb->loop_father) == 0 | 2363 || !dominated_by_p (CDI_DOMINATORS, def_bb, instantiate_below->dest)) |
2162 || dominated_by_p (CDI_DOMINATORS, instantiate_below, def_bb)) | |
2163 return chrec; | 2364 return chrec; |
2164 | 2365 |
2165 /* We cache the value of instantiated variable to avoid exponential | 2366 /* We cache the value of instantiated variable to avoid exponential |
2166 time complexity due to reevaluations. We also store the convenient | 2367 time complexity due to reevaluations. We also store the convenient |
2167 value in the cache in order to prevent infinite recursion -- we do | 2368 value in the cache in order to prevent infinite recursion -- we do |
2169 structure. This is used for avoiding the instantiation of | 2370 structure. This is used for avoiding the instantiation of |
2170 recursively defined functions, such as: | 2371 recursively defined functions, such as: |
2171 | 2372 |
2172 | a_2 -> {0, +, 1, +, a_2}_1 */ | 2373 | a_2 -> {0, +, 1, +, a_2}_1 */ |
2173 | 2374 |
2174 res = get_instantiated_value (cache, instantiate_below, chrec); | 2375 unsigned si = get_instantiated_value_entry (*global_cache, |
2175 if (res) | 2376 chrec, instantiate_below); |
2176 return res; | 2377 if (global_cache->get (si) != chrec_not_analyzed_yet) |
2177 | 2378 return global_cache->get (si); |
2178 res = chrec_dont_know; | 2379 |
2179 set_instantiated_value (cache, instantiate_below, chrec, res); | 2380 /* On recursion return chrec_dont_know. */ |
2381 global_cache->set (si, chrec_dont_know); | |
2180 | 2382 |
2181 def_loop = find_common_loop (evolution_loop, def_bb->loop_father); | 2383 def_loop = find_common_loop (evolution_loop, def_bb->loop_father); |
2384 | |
2385 if (! dominated_by_p (CDI_DOMINATORS, | |
2386 def_loop->header, instantiate_below->dest)) | |
2387 { | |
2388 gimple *def = SSA_NAME_DEF_STMT (chrec); | |
2389 if (gassign *ass = dyn_cast <gassign *> (def)) | |
2390 { | |
2391 switch (gimple_assign_rhs_class (ass)) | |
2392 { | |
2393 case GIMPLE_UNARY_RHS: | |
2394 { | |
2395 tree op0 = instantiate_scev_r (instantiate_below, evolution_loop, | |
2396 inner_loop, gimple_assign_rhs1 (ass), | |
2397 fold_conversions, size_expr); | |
2398 if (op0 == chrec_dont_know) | |
2399 return chrec_dont_know; | |
2400 res = fold_build1 (gimple_assign_rhs_code (ass), | |
2401 TREE_TYPE (chrec), op0); | |
2402 break; | |
2403 } | |
2404 case GIMPLE_BINARY_RHS: | |
2405 { | |
2406 tree op0 = instantiate_scev_r (instantiate_below, evolution_loop, | |
2407 inner_loop, gimple_assign_rhs1 (ass), | |
2408 fold_conversions, size_expr); | |
2409 if (op0 == chrec_dont_know) | |
2410 return chrec_dont_know; | |
2411 tree op1 = instantiate_scev_r (instantiate_below, evolution_loop, | |
2412 inner_loop, gimple_assign_rhs2 (ass), | |
2413 fold_conversions, size_expr); | |
2414 if (op1 == chrec_dont_know) | |
2415 return chrec_dont_know; | |
2416 res = fold_build2 (gimple_assign_rhs_code (ass), | |
2417 TREE_TYPE (chrec), op0, op1); | |
2418 break; | |
2419 } | |
2420 default: | |
2421 res = chrec_dont_know; | |
2422 } | |
2423 } | |
2424 else | |
2425 res = chrec_dont_know; | |
2426 global_cache->set (si, res); | |
2427 return res; | |
2428 } | |
2182 | 2429 |
2183 /* If the analysis yields a parametric chrec, instantiate the | 2430 /* If the analysis yields a parametric chrec, instantiate the |
2184 result again. */ | 2431 result again. */ |
2185 res = analyze_scalar_evolution (def_loop, chrec); | 2432 res = analyze_scalar_evolution (def_loop, chrec); |
2186 | 2433 |
2205 if (res == NULL_TREE) | 2452 if (res == NULL_TREE) |
2206 { | 2453 { |
2207 loop_p loop = loop_containing_stmt (SSA_NAME_DEF_STMT (chrec)); | 2454 loop_p loop = loop_containing_stmt (SSA_NAME_DEF_STMT (chrec)); |
2208 res = analyze_scalar_evolution (loop, chrec); | 2455 res = analyze_scalar_evolution (loop, chrec); |
2209 res = compute_overall_effect_of_inner_loop (loop, res); | 2456 res = compute_overall_effect_of_inner_loop (loop, res); |
2210 res = instantiate_scev_r (instantiate_below, evolution_loop, res, | 2457 res = instantiate_scev_r (instantiate_below, evolution_loop, |
2211 fold_conversions, cache, size_expr); | 2458 inner_loop, res, |
2459 fold_conversions, size_expr); | |
2212 } | 2460 } |
2213 else if (!dominated_by_p (CDI_DOMINATORS, instantiate_below, | 2461 else if (dominated_by_p (CDI_DOMINATORS, |
2214 gimple_bb (SSA_NAME_DEF_STMT (res)))) | 2462 gimple_bb (SSA_NAME_DEF_STMT (res)), |
2463 instantiate_below->dest)) | |
2215 res = chrec_dont_know; | 2464 res = chrec_dont_know; |
2216 } | 2465 } |
2217 | 2466 |
2218 else if (res != chrec_dont_know) | 2467 else if (res != chrec_dont_know) |
2219 res = instantiate_scev_r (instantiate_below, evolution_loop, res, | 2468 { |
2220 fold_conversions, cache, size_expr); | 2469 if (inner_loop |
2470 && def_bb->loop_father != inner_loop | |
2471 && !flow_loop_nested_p (def_bb->loop_father, inner_loop)) | |
2472 /* ??? We could try to compute the overall effect of the loop here. */ | |
2473 res = chrec_dont_know; | |
2474 else | |
2475 res = instantiate_scev_r (instantiate_below, evolution_loop, | |
2476 inner_loop, res, | |
2477 fold_conversions, size_expr); | |
2478 } | |
2221 | 2479 |
2222 /* Store the correct value to the cache. */ | 2480 /* Store the correct value to the cache. */ |
2223 set_instantiated_value (cache, instantiate_below, chrec, res); | 2481 global_cache->set (si, res); |
2224 return res; | 2482 return res; |
2225 } | 2483 } |
2226 | 2484 |
2227 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW | 2485 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW |
2228 and EVOLUTION_LOOP, that were left under a symbolic form. | 2486 and EVOLUTION_LOOP, that were left under a symbolic form. |
2229 | 2487 |
2230 CHREC is a polynomial chain of recurrence to be instantiated. | 2488 CHREC is a polynomial chain of recurrence to be instantiated. |
2231 | 2489 |
2232 CACHE is the cache of already instantiated values. | 2490 CACHE is the cache of already instantiated values. |
2233 | 2491 |
2234 FOLD_CONVERSIONS should be set to true when the conversions that | 2492 Variable pointed by FOLD_CONVERSIONS is set to TRUE when the |
2235 may wrap in signed/pointer type are folded, as long as the value of | 2493 conversions that may wrap in signed/pointer type are folded, as long |
2236 the chrec is preserved. | 2494 as the value of the chrec is preserved. If FOLD_CONVERSIONS is NULL |
2495 then we don't do such fold. | |
2237 | 2496 |
2238 SIZE_EXPR is used for computing the size of the expression to be | 2497 SIZE_EXPR is used for computing the size of the expression to be |
2239 instantiated, and to stop if it exceeds some limit. */ | 2498 instantiated, and to stop if it exceeds some limit. */ |
2240 | 2499 |
2241 static tree | 2500 static tree |
2242 instantiate_scev_poly (basic_block instantiate_below, | 2501 instantiate_scev_poly (edge instantiate_below, |
2243 struct loop *evolution_loop, tree chrec, | 2502 struct loop *evolution_loop, struct loop *, |
2244 bool fold_conversions, htab_t cache, int size_expr) | 2503 tree chrec, bool *fold_conversions, int size_expr) |
2245 { | 2504 { |
2246 tree op1; | 2505 tree op1; |
2247 tree op0 = instantiate_scev_r (instantiate_below, evolution_loop, | 2506 tree op0 = instantiate_scev_r (instantiate_below, evolution_loop, |
2248 CHREC_LEFT (chrec), fold_conversions, cache, | 2507 get_chrec_loop (chrec), |
2508 CHREC_LEFT (chrec), fold_conversions, | |
2249 size_expr); | 2509 size_expr); |
2250 if (op0 == chrec_dont_know) | 2510 if (op0 == chrec_dont_know) |
2251 return chrec_dont_know; | 2511 return chrec_dont_know; |
2252 | 2512 |
2253 op1 = instantiate_scev_r (instantiate_below, evolution_loop, | 2513 op1 = instantiate_scev_r (instantiate_below, evolution_loop, |
2254 CHREC_RIGHT (chrec), fold_conversions, cache, | 2514 get_chrec_loop (chrec), |
2515 CHREC_RIGHT (chrec), fold_conversions, | |
2255 size_expr); | 2516 size_expr); |
2256 if (op1 == chrec_dont_know) | 2517 if (op1 == chrec_dont_know) |
2257 return chrec_dont_know; | 2518 return chrec_dont_know; |
2258 | 2519 |
2259 if (CHREC_LEFT (chrec) != op0 | 2520 if (CHREC_LEFT (chrec) != op0 |
2260 || CHREC_RIGHT (chrec) != op1) | 2521 || CHREC_RIGHT (chrec) != op1) |
2261 { | 2522 { |
2262 unsigned var = CHREC_VARIABLE (chrec); | |
2263 | |
2264 /* When the instantiated stride or base has an evolution in an | |
2265 innermost loop, return chrec_dont_know, as this is not a | |
2266 valid SCEV representation. In the reduced testcase for | |
2267 PR40281 we would have {0, +, {1, +, 1}_2}_1 that has no | |
2268 meaning. */ | |
2269 if ((tree_is_chrec (op0) && CHREC_VARIABLE (op0) > var) | |
2270 || (tree_is_chrec (op1) && CHREC_VARIABLE (op1) > var)) | |
2271 return chrec_dont_know; | |
2272 | |
2273 op1 = chrec_convert_rhs (chrec_type (op0), op1, NULL); | 2523 op1 = chrec_convert_rhs (chrec_type (op0), op1, NULL); |
2274 chrec = build_polynomial_chrec (var, op0, op1); | 2524 chrec = build_polynomial_chrec (CHREC_VARIABLE (chrec), op0, op1); |
2275 } | 2525 } |
2276 | 2526 |
2277 return chrec; | 2527 return chrec; |
2278 } | 2528 } |
2279 | 2529 |
2282 | 2532 |
2283 "C0 CODE C1" is a binary expression of type TYPE to be instantiated. | 2533 "C0 CODE C1" is a binary expression of type TYPE to be instantiated. |
2284 | 2534 |
2285 CACHE is the cache of already instantiated values. | 2535 CACHE is the cache of already instantiated values. |
2286 | 2536 |
2287 FOLD_CONVERSIONS should be set to true when the conversions that | 2537 Variable pointed by FOLD_CONVERSIONS is set to TRUE when the |
2288 may wrap in signed/pointer type are folded, as long as the value of | 2538 conversions that may wrap in signed/pointer type are folded, as long |
2289 the chrec is preserved. | 2539 as the value of the chrec is preserved. If FOLD_CONVERSIONS is NULL |
2540 then we don't do such fold. | |
2290 | 2541 |
2291 SIZE_EXPR is used for computing the size of the expression to be | 2542 SIZE_EXPR is used for computing the size of the expression to be |
2292 instantiated, and to stop if it exceeds some limit. */ | 2543 instantiated, and to stop if it exceeds some limit. */ |
2293 | 2544 |
2294 static tree | 2545 static tree |
2295 instantiate_scev_binary (basic_block instantiate_below, | 2546 instantiate_scev_binary (edge instantiate_below, |
2296 struct loop *evolution_loop, tree chrec, enum tree_code code, | 2547 struct loop *evolution_loop, struct loop *inner_loop, |
2548 tree chrec, enum tree_code code, | |
2297 tree type, tree c0, tree c1, | 2549 tree type, tree c0, tree c1, |
2298 bool fold_conversions, htab_t cache, int size_expr) | 2550 bool *fold_conversions, int size_expr) |
2299 { | 2551 { |
2300 tree op1; | 2552 tree op1; |
2301 tree op0 = instantiate_scev_r (instantiate_below, evolution_loop, | 2553 tree op0 = instantiate_scev_r (instantiate_below, evolution_loop, inner_loop, |
2302 c0, fold_conversions, cache, | 2554 c0, fold_conversions, size_expr); |
2303 size_expr); | |
2304 if (op0 == chrec_dont_know) | 2555 if (op0 == chrec_dont_know) |
2305 return chrec_dont_know; | 2556 return chrec_dont_know; |
2306 | 2557 |
2307 op1 = instantiate_scev_r (instantiate_below, evolution_loop, | 2558 op1 = instantiate_scev_r (instantiate_below, evolution_loop, inner_loop, |
2308 c1, fold_conversions, cache, | 2559 c1, fold_conversions, size_expr); |
2309 size_expr); | |
2310 if (op1 == chrec_dont_know) | 2560 if (op1 == chrec_dont_know) |
2311 return chrec_dont_know; | 2561 return chrec_dont_know; |
2312 | 2562 |
2313 if (c0 != op0 | 2563 if (c0 != op0 |
2314 || c1 != op1) | 2564 || c1 != op1) |
2337 } | 2587 } |
2338 | 2588 |
2339 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW | 2589 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW |
2340 and EVOLUTION_LOOP, that were left under a symbolic form. | 2590 and EVOLUTION_LOOP, that were left under a symbolic form. |
2341 | 2591 |
2342 "CHREC" is an array reference to be instantiated. | 2592 "CHREC" that stands for a convert expression "(TYPE) OP" is to be |
2593 instantiated. | |
2343 | 2594 |
2344 CACHE is the cache of already instantiated values. | 2595 CACHE is the cache of already instantiated values. |
2345 | 2596 |
2346 FOLD_CONVERSIONS should be set to true when the conversions that | 2597 Variable pointed by FOLD_CONVERSIONS is set to TRUE when the |
2347 may wrap in signed/pointer type are folded, as long as the value of | 2598 conversions that may wrap in signed/pointer type are folded, as long |
2348 the chrec is preserved. | 2599 as the value of the chrec is preserved. If FOLD_CONVERSIONS is NULL |
2600 then we don't do such fold. | |
2349 | 2601 |
2350 SIZE_EXPR is used for computing the size of the expression to be | 2602 SIZE_EXPR is used for computing the size of the expression to be |
2351 instantiated, and to stop if it exceeds some limit. */ | 2603 instantiated, and to stop if it exceeds some limit. */ |
2352 | 2604 |
2353 static tree | 2605 static tree |
2354 instantiate_array_ref (basic_block instantiate_below, | 2606 instantiate_scev_convert (edge instantiate_below, |
2355 struct loop *evolution_loop, tree chrec, | 2607 struct loop *evolution_loop, struct loop *inner_loop, |
2356 bool fold_conversions, htab_t cache, int size_expr) | 2608 tree chrec, tree type, tree op, |
2357 { | 2609 bool *fold_conversions, int size_expr) |
2358 tree res; | 2610 { |
2359 tree index = TREE_OPERAND (chrec, 1); | 2611 tree op0 = instantiate_scev_r (instantiate_below, evolution_loop, |
2360 tree op1 = instantiate_scev_r (instantiate_below, evolution_loop, index, | 2612 inner_loop, op, |
2361 fold_conversions, cache, size_expr); | 2613 fold_conversions, size_expr); |
2362 | |
2363 if (op1 == chrec_dont_know) | |
2364 return chrec_dont_know; | |
2365 | |
2366 if (chrec && op1 == index) | |
2367 return chrec; | |
2368 | |
2369 res = unshare_expr (chrec); | |
2370 TREE_OPERAND (res, 1) = op1; | |
2371 return res; | |
2372 } | |
2373 | |
2374 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW | |
2375 and EVOLUTION_LOOP, that were left under a symbolic form. | |
2376 | |
2377 "CHREC" that stands for a convert expression "(TYPE) OP" is to be | |
2378 instantiated. | |
2379 | |
2380 CACHE is the cache of already instantiated values. | |
2381 | |
2382 FOLD_CONVERSIONS should be set to true when the conversions that | |
2383 may wrap in signed/pointer type are folded, as long as the value of | |
2384 the chrec is preserved. | |
2385 | |
2386 SIZE_EXPR is used for computing the size of the expression to be | |
2387 instantiated, and to stop if it exceeds some limit. */ | |
2388 | |
2389 static tree | |
2390 instantiate_scev_convert (basic_block instantiate_below, | |
2391 struct loop *evolution_loop, tree chrec, | |
2392 tree type, tree op, | |
2393 bool fold_conversions, htab_t cache, int size_expr) | |
2394 { | |
2395 tree op0 = instantiate_scev_r (instantiate_below, evolution_loop, op, | |
2396 fold_conversions, cache, size_expr); | |
2397 | 2614 |
2398 if (op0 == chrec_dont_know) | 2615 if (op0 == chrec_dont_know) |
2399 return chrec_dont_know; | 2616 return chrec_dont_know; |
2400 | 2617 |
2401 if (fold_conversions) | 2618 if (fold_conversions) |
2402 { | 2619 { |
2403 tree tmp = chrec_convert_aggressive (type, op0); | 2620 tree tmp = chrec_convert_aggressive (type, op0, fold_conversions); |
2404 if (tmp) | 2621 if (tmp) |
2405 return tmp; | 2622 return tmp; |
2406 } | 2623 |
2407 | 2624 /* If we used chrec_convert_aggressive, we can no longer assume that |
2408 if (chrec && op0 == op) | 2625 signed chrecs do not overflow, as chrec_convert does, so avoid |
2409 return chrec; | 2626 calling it in that case. */ |
2410 | 2627 if (*fold_conversions) |
2411 /* If we used chrec_convert_aggressive, we can no longer assume that | 2628 { |
2412 signed chrecs do not overflow, as chrec_convert does, so avoid | 2629 if (chrec && op0 == op) |
2413 calling it in that case. */ | 2630 return chrec; |
2414 if (fold_conversions) | 2631 |
2415 return fold_convert (type, op0); | 2632 return fold_convert (type, op0); |
2633 } | |
2634 } | |
2416 | 2635 |
2417 return chrec_convert (type, op0, NULL); | 2636 return chrec_convert (type, op0, NULL); |
2418 } | 2637 } |
2419 | 2638 |
2420 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW | 2639 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW |
2424 Handle ~X as -1 - X. | 2643 Handle ~X as -1 - X. |
2425 Handle -X as -1 * X. | 2644 Handle -X as -1 * X. |
2426 | 2645 |
2427 CACHE is the cache of already instantiated values. | 2646 CACHE is the cache of already instantiated values. |
2428 | 2647 |
2429 FOLD_CONVERSIONS should be set to true when the conversions that | 2648 Variable pointed by FOLD_CONVERSIONS is set to TRUE when the |
2430 may wrap in signed/pointer type are folded, as long as the value of | 2649 conversions that may wrap in signed/pointer type are folded, as long |
2431 the chrec is preserved. | 2650 as the value of the chrec is preserved. If FOLD_CONVERSIONS is NULL |
2651 then we don't do such fold. | |
2432 | 2652 |
2433 SIZE_EXPR is used for computing the size of the expression to be | 2653 SIZE_EXPR is used for computing the size of the expression to be |
2434 instantiated, and to stop if it exceeds some limit. */ | 2654 instantiated, and to stop if it exceeds some limit. */ |
2435 | 2655 |
2436 static tree | 2656 static tree |
2437 instantiate_scev_not (basic_block instantiate_below, | 2657 instantiate_scev_not (edge instantiate_below, |
2438 struct loop *evolution_loop, tree chrec, | 2658 struct loop *evolution_loop, struct loop *inner_loop, |
2659 tree chrec, | |
2439 enum tree_code code, tree type, tree op, | 2660 enum tree_code code, tree type, tree op, |
2440 bool fold_conversions, htab_t cache, int size_expr) | 2661 bool *fold_conversions, int size_expr) |
2441 { | 2662 { |
2442 tree op0 = instantiate_scev_r (instantiate_below, evolution_loop, op, | 2663 tree op0 = instantiate_scev_r (instantiate_below, evolution_loop, |
2443 fold_conversions, cache, size_expr); | 2664 inner_loop, op, |
2665 fold_conversions, size_expr); | |
2444 | 2666 |
2445 if (op0 == chrec_dont_know) | 2667 if (op0 == chrec_dont_know) |
2446 return chrec_dont_know; | 2668 return chrec_dont_know; |
2447 | 2669 |
2448 if (op != op0) | 2670 if (op != op0) |
2468 } | 2690 } |
2469 | 2691 |
2470 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW | 2692 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW |
2471 and EVOLUTION_LOOP, that were left under a symbolic form. | 2693 and EVOLUTION_LOOP, that were left under a symbolic form. |
2472 | 2694 |
2473 CHREC is an expression with 3 operands to be instantiated. | 2695 CHREC is the scalar evolution to instantiate. |
2474 | 2696 |
2475 CACHE is the cache of already instantiated values. | 2697 CACHE is the cache of already instantiated values. |
2476 | 2698 |
2477 FOLD_CONVERSIONS should be set to true when the conversions that | 2699 Variable pointed by FOLD_CONVERSIONS is set to TRUE when the |
2478 may wrap in signed/pointer type are folded, as long as the value of | 2700 conversions that may wrap in signed/pointer type are folded, as long |
2479 the chrec is preserved. | 2701 as the value of the chrec is preserved. If FOLD_CONVERSIONS is NULL |
2702 then we don't do such fold. | |
2480 | 2703 |
2481 SIZE_EXPR is used for computing the size of the expression to be | 2704 SIZE_EXPR is used for computing the size of the expression to be |
2482 instantiated, and to stop if it exceeds some limit. */ | 2705 instantiated, and to stop if it exceeds some limit. */ |
2483 | 2706 |
2484 static tree | 2707 static tree |
2485 instantiate_scev_3 (basic_block instantiate_below, | 2708 instantiate_scev_r (edge instantiate_below, |
2486 struct loop *evolution_loop, tree chrec, | 2709 struct loop *evolution_loop, struct loop *inner_loop, |
2487 bool fold_conversions, htab_t cache, int size_expr) | 2710 tree chrec, |
2488 { | 2711 bool *fold_conversions, int size_expr) |
2489 tree op1, op2; | |
2490 tree op0 = instantiate_scev_r (instantiate_below, evolution_loop, | |
2491 TREE_OPERAND (chrec, 0), | |
2492 fold_conversions, cache, size_expr); | |
2493 if (op0 == chrec_dont_know) | |
2494 return chrec_dont_know; | |
2495 | |
2496 op1 = instantiate_scev_r (instantiate_below, evolution_loop, | |
2497 TREE_OPERAND (chrec, 1), | |
2498 fold_conversions, cache, size_expr); | |
2499 if (op1 == chrec_dont_know) | |
2500 return chrec_dont_know; | |
2501 | |
2502 op2 = instantiate_scev_r (instantiate_below, evolution_loop, | |
2503 TREE_OPERAND (chrec, 2), | |
2504 fold_conversions, cache, size_expr); | |
2505 if (op2 == chrec_dont_know) | |
2506 return chrec_dont_know; | |
2507 | |
2508 if (op0 == TREE_OPERAND (chrec, 0) | |
2509 && op1 == TREE_OPERAND (chrec, 1) | |
2510 && op2 == TREE_OPERAND (chrec, 2)) | |
2511 return chrec; | |
2512 | |
2513 return fold_build3 (TREE_CODE (chrec), | |
2514 TREE_TYPE (chrec), op0, op1, op2); | |
2515 } | |
2516 | |
2517 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW | |
2518 and EVOLUTION_LOOP, that were left under a symbolic form. | |
2519 | |
2520 CHREC is an expression with 2 operands to be instantiated. | |
2521 | |
2522 CACHE is the cache of already instantiated values. | |
2523 | |
2524 FOLD_CONVERSIONS should be set to true when the conversions that | |
2525 may wrap in signed/pointer type are folded, as long as the value of | |
2526 the chrec is preserved. | |
2527 | |
2528 SIZE_EXPR is used for computing the size of the expression to be | |
2529 instantiated, and to stop if it exceeds some limit. */ | |
2530 | |
2531 static tree | |
2532 instantiate_scev_2 (basic_block instantiate_below, | |
2533 struct loop *evolution_loop, tree chrec, | |
2534 bool fold_conversions, htab_t cache, int size_expr) | |
2535 { | |
2536 tree op1; | |
2537 tree op0 = instantiate_scev_r (instantiate_below, evolution_loop, | |
2538 TREE_OPERAND (chrec, 0), | |
2539 fold_conversions, cache, size_expr); | |
2540 if (op0 == chrec_dont_know) | |
2541 return chrec_dont_know; | |
2542 | |
2543 op1 = instantiate_scev_r (instantiate_below, evolution_loop, | |
2544 TREE_OPERAND (chrec, 1), | |
2545 fold_conversions, cache, size_expr); | |
2546 if (op1 == chrec_dont_know) | |
2547 return chrec_dont_know; | |
2548 | |
2549 if (op0 == TREE_OPERAND (chrec, 0) | |
2550 && op1 == TREE_OPERAND (chrec, 1)) | |
2551 return chrec; | |
2552 | |
2553 return fold_build2 (TREE_CODE (chrec), TREE_TYPE (chrec), op0, op1); | |
2554 } | |
2555 | |
2556 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW | |
2557 and EVOLUTION_LOOP, that were left under a symbolic form. | |
2558 | |
2559 CHREC is an expression with 2 operands to be instantiated. | |
2560 | |
2561 CACHE is the cache of already instantiated values. | |
2562 | |
2563 FOLD_CONVERSIONS should be set to true when the conversions that | |
2564 may wrap in signed/pointer type are folded, as long as the value of | |
2565 the chrec is preserved. | |
2566 | |
2567 SIZE_EXPR is used for computing the size of the expression to be | |
2568 instantiated, and to stop if it exceeds some limit. */ | |
2569 | |
2570 static tree | |
2571 instantiate_scev_1 (basic_block instantiate_below, | |
2572 struct loop *evolution_loop, tree chrec, | |
2573 bool fold_conversions, htab_t cache, int size_expr) | |
2574 { | |
2575 tree op0 = instantiate_scev_r (instantiate_below, evolution_loop, | |
2576 TREE_OPERAND (chrec, 0), | |
2577 fold_conversions, cache, size_expr); | |
2578 | |
2579 if (op0 == chrec_dont_know) | |
2580 return chrec_dont_know; | |
2581 | |
2582 if (op0 == TREE_OPERAND (chrec, 0)) | |
2583 return chrec; | |
2584 | |
2585 return fold_build1 (TREE_CODE (chrec), TREE_TYPE (chrec), op0); | |
2586 } | |
2587 | |
2588 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW | |
2589 and EVOLUTION_LOOP, that were left under a symbolic form. | |
2590 | |
2591 CHREC is the scalar evolution to instantiate. | |
2592 | |
2593 CACHE is the cache of already instantiated values. | |
2594 | |
2595 FOLD_CONVERSIONS should be set to true when the conversions that | |
2596 may wrap in signed/pointer type are folded, as long as the value of | |
2597 the chrec is preserved. | |
2598 | |
2599 SIZE_EXPR is used for computing the size of the expression to be | |
2600 instantiated, and to stop if it exceeds some limit. */ | |
2601 | |
2602 static tree | |
2603 instantiate_scev_r (basic_block instantiate_below, | |
2604 struct loop *evolution_loop, tree chrec, | |
2605 bool fold_conversions, htab_t cache, int size_expr) | |
2606 { | 2712 { |
2607 /* Give up if the expression is larger than the MAX that we allow. */ | 2713 /* Give up if the expression is larger than the MAX that we allow. */ |
2608 if (size_expr++ > PARAM_VALUE (PARAM_SCEV_MAX_EXPR_SIZE)) | 2714 if (size_expr++ > PARAM_VALUE (PARAM_SCEV_MAX_EXPR_SIZE)) |
2609 return chrec_dont_know; | 2715 return chrec_dont_know; |
2610 | 2716 |
2614 return chrec; | 2720 return chrec; |
2615 | 2721 |
2616 switch (TREE_CODE (chrec)) | 2722 switch (TREE_CODE (chrec)) |
2617 { | 2723 { |
2618 case SSA_NAME: | 2724 case SSA_NAME: |
2619 return instantiate_scev_name (instantiate_below, evolution_loop, chrec, | 2725 return instantiate_scev_name (instantiate_below, evolution_loop, |
2620 fold_conversions, cache, size_expr); | 2726 inner_loop, chrec, |
2727 fold_conversions, size_expr); | |
2621 | 2728 |
2622 case POLYNOMIAL_CHREC: | 2729 case POLYNOMIAL_CHREC: |
2623 return instantiate_scev_poly (instantiate_below, evolution_loop, chrec, | 2730 return instantiate_scev_poly (instantiate_below, evolution_loop, |
2624 fold_conversions, cache, size_expr); | 2731 inner_loop, chrec, |
2732 fold_conversions, size_expr); | |
2625 | 2733 |
2626 case POINTER_PLUS_EXPR: | 2734 case POINTER_PLUS_EXPR: |
2627 case PLUS_EXPR: | 2735 case PLUS_EXPR: |
2628 case MINUS_EXPR: | 2736 case MINUS_EXPR: |
2629 case MULT_EXPR: | 2737 case MULT_EXPR: |
2630 return instantiate_scev_binary (instantiate_below, evolution_loop, chrec, | 2738 return instantiate_scev_binary (instantiate_below, evolution_loop, |
2739 inner_loop, chrec, | |
2631 TREE_CODE (chrec), chrec_type (chrec), | 2740 TREE_CODE (chrec), chrec_type (chrec), |
2632 TREE_OPERAND (chrec, 0), | 2741 TREE_OPERAND (chrec, 0), |
2633 TREE_OPERAND (chrec, 1), | 2742 TREE_OPERAND (chrec, 1), |
2634 fold_conversions, cache, size_expr); | 2743 fold_conversions, size_expr); |
2635 | 2744 |
2636 CASE_CONVERT: | 2745 CASE_CONVERT: |
2637 return instantiate_scev_convert (instantiate_below, evolution_loop, chrec, | 2746 return instantiate_scev_convert (instantiate_below, evolution_loop, |
2747 inner_loop, chrec, | |
2638 TREE_TYPE (chrec), TREE_OPERAND (chrec, 0), | 2748 TREE_TYPE (chrec), TREE_OPERAND (chrec, 0), |
2639 fold_conversions, cache, size_expr); | 2749 fold_conversions, size_expr); |
2640 | 2750 |
2641 case NEGATE_EXPR: | 2751 case NEGATE_EXPR: |
2642 case BIT_NOT_EXPR: | 2752 case BIT_NOT_EXPR: |
2643 return instantiate_scev_not (instantiate_below, evolution_loop, chrec, | 2753 return instantiate_scev_not (instantiate_below, evolution_loop, |
2754 inner_loop, chrec, | |
2644 TREE_CODE (chrec), TREE_TYPE (chrec), | 2755 TREE_CODE (chrec), TREE_TYPE (chrec), |
2645 TREE_OPERAND (chrec, 0), | 2756 TREE_OPERAND (chrec, 0), |
2646 fold_conversions, cache, size_expr); | 2757 fold_conversions, size_expr); |
2647 | 2758 |
2759 case ADDR_EXPR: | |
2760 if (is_gimple_min_invariant (chrec)) | |
2761 return chrec; | |
2762 /* Fallthru. */ | |
2648 case SCEV_NOT_KNOWN: | 2763 case SCEV_NOT_KNOWN: |
2649 return chrec_dont_know; | 2764 return chrec_dont_know; |
2650 | 2765 |
2651 case SCEV_KNOWN: | 2766 case SCEV_KNOWN: |
2652 return chrec_known; | 2767 return chrec_known; |
2653 | 2768 |
2654 case ARRAY_REF: | |
2655 return instantiate_array_ref (instantiate_below, evolution_loop, chrec, | |
2656 fold_conversions, cache, size_expr); | |
2657 | |
2658 default: | 2769 default: |
2659 break; | 2770 if (CONSTANT_CLASS_P (chrec)) |
2660 } | 2771 return chrec; |
2661 | 2772 return chrec_dont_know; |
2662 if (VL_EXP_CLASS_P (chrec)) | 2773 } |
2663 return chrec_dont_know; | |
2664 | |
2665 switch (TREE_CODE_LENGTH (TREE_CODE (chrec))) | |
2666 { | |
2667 case 3: | |
2668 return instantiate_scev_3 (instantiate_below, evolution_loop, chrec, | |
2669 fold_conversions, cache, size_expr); | |
2670 | |
2671 case 2: | |
2672 return instantiate_scev_2 (instantiate_below, evolution_loop, chrec, | |
2673 fold_conversions, cache, size_expr); | |
2674 | |
2675 case 1: | |
2676 return instantiate_scev_1 (instantiate_below, evolution_loop, chrec, | |
2677 fold_conversions, cache, size_expr); | |
2678 | |
2679 case 0: | |
2680 return chrec; | |
2681 | |
2682 default: | |
2683 break; | |
2684 } | |
2685 | |
2686 /* Too complicated to handle. */ | |
2687 return chrec_dont_know; | |
2688 } | 2774 } |
2689 | 2775 |
2690 /* Analyze all the parameters of the chrec that were left under a | 2776 /* Analyze all the parameters of the chrec that were left under a |
2691 symbolic form. INSTANTIATE_BELOW is the basic block that stops the | 2777 symbolic form. INSTANTIATE_BELOW is the basic block that stops the |
2692 recursive instantiation of parameters: a parameter is a variable | 2778 recursive instantiation of parameters: a parameter is a variable |
2693 that is defined in a basic block that dominates INSTANTIATE_BELOW or | 2779 that is defined in a basic block that dominates INSTANTIATE_BELOW or |
2694 a function parameter. */ | 2780 a function parameter. */ |
2695 | 2781 |
2696 tree | 2782 tree |
2697 instantiate_scev (basic_block instantiate_below, struct loop *evolution_loop, | 2783 instantiate_scev (edge instantiate_below, struct loop *evolution_loop, |
2698 tree chrec) | 2784 tree chrec) |
2699 { | 2785 { |
2700 tree res; | 2786 tree res; |
2701 htab_t cache = htab_create (10, hash_scev_info, eq_scev_info, del_scev_info); | 2787 |
2702 | 2788 if (dump_file && (dump_flags & TDF_SCEV)) |
2703 if (dump_file && (dump_flags & TDF_DETAILS)) | |
2704 { | 2789 { |
2705 fprintf (dump_file, "(instantiate_scev \n"); | 2790 fprintf (dump_file, "(instantiate_scev \n"); |
2706 fprintf (dump_file, " (instantiate_below = %d)\n", instantiate_below->index); | 2791 fprintf (dump_file, " (instantiate_below = %d -> %d)\n", |
2707 fprintf (dump_file, " (evolution_loop = %d)\n", evolution_loop->num); | 2792 instantiate_below->src->index, instantiate_below->dest->index); |
2793 if (evolution_loop) | |
2794 fprintf (dump_file, " (evolution_loop = %d)\n", evolution_loop->num); | |
2708 fprintf (dump_file, " (chrec = "); | 2795 fprintf (dump_file, " (chrec = "); |
2709 print_generic_expr (dump_file, chrec, 0); | 2796 print_generic_expr (dump_file, chrec); |
2710 fprintf (dump_file, ")\n"); | 2797 fprintf (dump_file, ")\n"); |
2711 } | 2798 } |
2712 | 2799 |
2713 res = instantiate_scev_r (instantiate_below, evolution_loop, chrec, false, | 2800 bool destr = false; |
2714 cache, 0); | 2801 if (!global_cache) |
2715 | 2802 { |
2716 if (dump_file && (dump_flags & TDF_DETAILS)) | 2803 global_cache = new instantiate_cache_type; |
2804 destr = true; | |
2805 } | |
2806 | |
2807 res = instantiate_scev_r (instantiate_below, evolution_loop, | |
2808 NULL, chrec, NULL, 0); | |
2809 | |
2810 if (destr) | |
2811 { | |
2812 delete global_cache; | |
2813 global_cache = NULL; | |
2814 } | |
2815 | |
2816 if (dump_file && (dump_flags & TDF_SCEV)) | |
2717 { | 2817 { |
2718 fprintf (dump_file, " (res = "); | 2818 fprintf (dump_file, " (res = "); |
2719 print_generic_expr (dump_file, res, 0); | 2819 print_generic_expr (dump_file, res); |
2720 fprintf (dump_file, "))\n"); | 2820 fprintf (dump_file, "))\n"); |
2721 } | 2821 } |
2722 | |
2723 htab_delete (cache); | |
2724 | 2822 |
2725 return res; | 2823 return res; |
2726 } | 2824 } |
2727 | 2825 |
2728 /* Similar to instantiate_parameters, but does not introduce the | 2826 /* Similar to instantiate_parameters, but does not introduce the |
2729 evolutions in outer loops for LOOP invariants in CHREC, and does not | 2827 evolutions in outer loops for LOOP invariants in CHREC, and does not |
2730 care about causing overflows, as long as they do not affect value | 2828 care about causing overflows, as long as they do not affect value |
2731 of an expression. */ | 2829 of an expression. */ |
2732 | 2830 |
2733 tree | 2831 tree |
2734 resolve_mixers (struct loop *loop, tree chrec) | 2832 resolve_mixers (struct loop *loop, tree chrec, bool *folded_casts) |
2735 { | 2833 { |
2736 htab_t cache = htab_create (10, hash_scev_info, eq_scev_info, del_scev_info); | 2834 bool destr = false; |
2737 tree ret = instantiate_scev_r (block_before_loop (loop), loop, chrec, true, | 2835 bool fold_conversions = false; |
2738 cache, 0); | 2836 if (!global_cache) |
2739 htab_delete (cache); | 2837 { |
2838 global_cache = new instantiate_cache_type; | |
2839 destr = true; | |
2840 } | |
2841 | |
2842 tree ret = instantiate_scev_r (loop_preheader_edge (loop), loop, NULL, | |
2843 chrec, &fold_conversions, 0); | |
2844 | |
2845 if (folded_casts && !*folded_casts) | |
2846 *folded_casts = fold_conversions; | |
2847 | |
2848 if (destr) | |
2849 { | |
2850 delete global_cache; | |
2851 global_cache = NULL; | |
2852 } | |
2853 | |
2740 return ret; | 2854 return ret; |
2741 } | 2855 } |
2742 | 2856 |
2743 /* Entry point for the analysis of the number of iterations pass. | 2857 /* Entry point for the analysis of the number of iterations pass. |
2744 This function tries to safely approximate the number of iterations | 2858 This function tries to safely approximate the number of iterations |
2777 if (res) | 2891 if (res) |
2778 return res; | 2892 return res; |
2779 | 2893 |
2780 may_be_zero = NULL_TREE; | 2894 may_be_zero = NULL_TREE; |
2781 | 2895 |
2782 if (dump_file && (dump_flags & TDF_DETAILS)) | 2896 if (dump_file && (dump_flags & TDF_SCEV)) |
2783 fprintf (dump_file, "(number_of_iterations_in_loop = \n"); | 2897 fprintf (dump_file, "(number_of_iterations_in_loop = \n"); |
2784 | 2898 |
2785 res = chrec_dont_know; | 2899 res = chrec_dont_know; |
2786 exit = single_exit (loop); | 2900 exit = single_exit (loop); |
2787 | 2901 |
2802 res = fold_build3 (COND_EXPR, TREE_TYPE (res), may_be_zero, | 2916 res = fold_build3 (COND_EXPR, TREE_TYPE (res), may_be_zero, |
2803 build_int_cst (TREE_TYPE (res), 0), res); | 2917 build_int_cst (TREE_TYPE (res), 0), res); |
2804 else | 2918 else |
2805 res = chrec_dont_know; | 2919 res = chrec_dont_know; |
2806 | 2920 |
2807 if (dump_file && (dump_flags & TDF_DETAILS)) | 2921 if (dump_file && (dump_flags & TDF_SCEV)) |
2808 { | 2922 { |
2809 fprintf (dump_file, " (set_nb_iterations_in_loop = "); | 2923 fprintf (dump_file, " (set_nb_iterations_in_loop = "); |
2810 print_generic_expr (dump_file, res, 0); | 2924 print_generic_expr (dump_file, res); |
2811 fprintf (dump_file, "))\n"); | 2925 fprintf (dump_file, "))\n"); |
2812 } | 2926 } |
2813 | 2927 |
2814 loop->nb_iterations = res; | 2928 loop->nb_iterations = res; |
2815 return res; | 2929 return res; |
2816 } | 2930 } |
2817 | |
2818 /* Returns the number of executions of the exit condition of LOOP, | |
2819 i.e., the number by one higher than number_of_latch_executions. | |
2820 Note that unlike number_of_latch_executions, this number does | |
2821 not necessarily fit in the unsigned variant of the type of | |
2822 the control variable -- if the number of iterations is a constant, | |
2823 we return chrec_dont_know if adding one to number_of_latch_executions | |
2824 overflows; however, in case the number of iterations is symbolic | |
2825 expression, the caller is responsible for dealing with this | |
2826 the possible overflow. */ | |
2827 | |
2828 tree | |
2829 number_of_exit_cond_executions (struct loop *loop) | |
2830 { | |
2831 tree ret = number_of_latch_executions (loop); | |
2832 tree type = chrec_type (ret); | |
2833 | |
2834 if (chrec_contains_undetermined (ret)) | |
2835 return ret; | |
2836 | |
2837 ret = chrec_fold_plus (type, ret, build_int_cst (type, 1)); | |
2838 if (TREE_CODE (ret) == INTEGER_CST | |
2839 && TREE_OVERFLOW (ret)) | |
2840 return chrec_dont_know; | |
2841 | |
2842 return ret; | |
2843 } | |
2844 | |
2845 /* One of the drivers for testing the scalar evolutions analysis. | |
2846 This function computes the number of iterations for all the loops | |
2847 from the EXIT_CONDITIONS array. */ | |
2848 | |
2849 static void | |
2850 number_of_iterations_for_all_loops (VEC(gimple,heap) **exit_conditions) | |
2851 { | |
2852 unsigned int i; | |
2853 unsigned nb_chrec_dont_know_loops = 0; | |
2854 unsigned nb_static_loops = 0; | |
2855 gimple cond; | |
2856 | |
2857 FOR_EACH_VEC_ELT (gimple, *exit_conditions, i, cond) | |
2858 { | |
2859 tree res = number_of_latch_executions (loop_containing_stmt (cond)); | |
2860 if (chrec_contains_undetermined (res)) | |
2861 nb_chrec_dont_know_loops++; | |
2862 else | |
2863 nb_static_loops++; | |
2864 } | |
2865 | |
2866 if (dump_file) | |
2867 { | |
2868 fprintf (dump_file, "\n(\n"); | |
2869 fprintf (dump_file, "-----------------------------------------\n"); | |
2870 fprintf (dump_file, "%d\tnb_chrec_dont_know_loops\n", nb_chrec_dont_know_loops); | |
2871 fprintf (dump_file, "%d\tnb_static_loops\n", nb_static_loops); | |
2872 fprintf (dump_file, "%d\tnb_total_loops\n", number_of_loops ()); | |
2873 fprintf (dump_file, "-----------------------------------------\n"); | |
2874 fprintf (dump_file, ")\n\n"); | |
2875 | |
2876 print_loops (dump_file, 3); | |
2877 } | |
2878 } | |
2879 | |
2880 | 2931 |
2881 | 2932 |
2882 /* Counters for the stats. */ | 2933 /* Counters for the stats. */ |
2883 | 2934 |
2884 struct chrec_stats | 2935 struct chrec_stats |
2920 fprintf (file, "%d\ttotal chrecs\n", stats->nb_chrecs); | 2971 fprintf (file, "%d\ttotal chrecs\n", stats->nb_chrecs); |
2921 fprintf (file, "%d\twith undetermined coefficients\n", | 2972 fprintf (file, "%d\twith undetermined coefficients\n", |
2922 stats->nb_undetermined); | 2973 stats->nb_undetermined); |
2923 fprintf (file, "-----------------------------------------\n"); | 2974 fprintf (file, "-----------------------------------------\n"); |
2924 fprintf (file, "%d\tchrecs in the scev database\n", | 2975 fprintf (file, "%d\tchrecs in the scev database\n", |
2925 (int) htab_elements (scalar_evolution_info)); | 2976 (int) scalar_evolution_info->elements ()); |
2926 fprintf (file, "%d\tsets in the scev database\n", nb_set_scev); | 2977 fprintf (file, "%d\tsets in the scev database\n", nb_set_scev); |
2927 fprintf (file, "%d\tgets in the scev database\n", nb_get_scev); | 2978 fprintf (file, "%d\tgets in the scev database\n", nb_get_scev); |
2928 fprintf (file, "-----------------------------------------\n"); | 2979 fprintf (file, "-----------------------------------------\n"); |
2929 fprintf (file, ")\n\n"); | 2980 fprintf (file, ")\n\n"); |
2930 } | 2981 } |
2935 gather_chrec_stats (tree chrec, struct chrec_stats *stats) | 2986 gather_chrec_stats (tree chrec, struct chrec_stats *stats) |
2936 { | 2987 { |
2937 if (dump_file && (dump_flags & TDF_STATS)) | 2988 if (dump_file && (dump_flags & TDF_STATS)) |
2938 { | 2989 { |
2939 fprintf (dump_file, "(classify_chrec "); | 2990 fprintf (dump_file, "(classify_chrec "); |
2940 print_generic_expr (dump_file, chrec, 0); | 2991 print_generic_expr (dump_file, chrec); |
2941 fprintf (dump_file, "\n"); | 2992 fprintf (dump_file, "\n"); |
2942 } | 2993 } |
2943 | 2994 |
2944 stats->nb_chrecs++; | 2995 stats->nb_chrecs++; |
2945 | 2996 |
2986 | 3037 |
2987 if (dump_file && (dump_flags & TDF_STATS)) | 3038 if (dump_file && (dump_flags & TDF_STATS)) |
2988 fprintf (dump_file, ")\n"); | 3039 fprintf (dump_file, ")\n"); |
2989 } | 3040 } |
2990 | 3041 |
2991 /* One of the drivers for testing the scalar evolutions analysis. | |
2992 This function analyzes the scalar evolution of all the scalars | |
2993 defined as loop phi nodes in one of the loops from the | |
2994 EXIT_CONDITIONS array. | |
2995 | |
2996 TODO Optimization: A loop is in canonical form if it contains only | |
2997 a single scalar loop phi node. All the other scalars that have an | |
2998 evolution in the loop are rewritten in function of this single | |
2999 index. This allows the parallelization of the loop. */ | |
3000 | |
3001 static void | |
3002 analyze_scalar_evolution_for_all_loop_phi_nodes (VEC(gimple,heap) **exit_conditions) | |
3003 { | |
3004 unsigned int i; | |
3005 struct chrec_stats stats; | |
3006 gimple cond, phi; | |
3007 gimple_stmt_iterator psi; | |
3008 | |
3009 reset_chrecs_counters (&stats); | |
3010 | |
3011 FOR_EACH_VEC_ELT (gimple, *exit_conditions, i, cond) | |
3012 { | |
3013 struct loop *loop; | |
3014 basic_block bb; | |
3015 tree chrec; | |
3016 | |
3017 loop = loop_containing_stmt (cond); | |
3018 bb = loop->header; | |
3019 | |
3020 for (psi = gsi_start_phis (bb); !gsi_end_p (psi); gsi_next (&psi)) | |
3021 { | |
3022 phi = gsi_stmt (psi); | |
3023 if (is_gimple_reg (PHI_RESULT (phi))) | |
3024 { | |
3025 chrec = instantiate_parameters | |
3026 (loop, | |
3027 analyze_scalar_evolution (loop, PHI_RESULT (phi))); | |
3028 | |
3029 if (dump_file && (dump_flags & TDF_STATS)) | |
3030 gather_chrec_stats (chrec, &stats); | |
3031 } | |
3032 } | |
3033 } | |
3034 | |
3035 if (dump_file && (dump_flags & TDF_STATS)) | |
3036 dump_chrecs_stats (dump_file, &stats); | |
3037 } | |
3038 | |
3039 /* Callback for htab_traverse, gathers information on chrecs in the | |
3040 hashtable. */ | |
3041 | |
3042 static int | |
3043 gather_stats_on_scev_database_1 (void **slot, void *stats) | |
3044 { | |
3045 struct scev_info_str *entry = (struct scev_info_str *) *slot; | |
3046 | |
3047 gather_chrec_stats (entry->chrec, (struct chrec_stats *) stats); | |
3048 | |
3049 return 1; | |
3050 } | |
3051 | |
3052 /* Classify the chrecs of the whole database. */ | 3042 /* Classify the chrecs of the whole database. */ |
3053 | 3043 |
3054 void | 3044 void |
3055 gather_stats_on_scev_database (void) | 3045 gather_stats_on_scev_database (void) |
3056 { | 3046 { |
3059 if (!dump_file) | 3049 if (!dump_file) |
3060 return; | 3050 return; |
3061 | 3051 |
3062 reset_chrecs_counters (&stats); | 3052 reset_chrecs_counters (&stats); |
3063 | 3053 |
3064 htab_traverse (scalar_evolution_info, gather_stats_on_scev_database_1, | 3054 hash_table<scev_info_hasher>::iterator iter; |
3065 &stats); | 3055 scev_info_str *elt; |
3056 FOR_EACH_HASH_TABLE_ELEMENT (*scalar_evolution_info, elt, scev_info_str *, | |
3057 iter) | |
3058 gather_chrec_stats (elt->chrec, &stats); | |
3066 | 3059 |
3067 dump_chrecs_stats (dump_file, &stats); | 3060 dump_chrecs_stats (dump_file, &stats); |
3068 } | 3061 } |
3069 | 3062 |
3070 | 3063 |
3088 /* Initialize the analysis of scalar evolutions for LOOPS. */ | 3081 /* Initialize the analysis of scalar evolutions for LOOPS. */ |
3089 | 3082 |
3090 void | 3083 void |
3091 scev_initialize (void) | 3084 scev_initialize (void) |
3092 { | 3085 { |
3093 loop_iterator li; | |
3094 struct loop *loop; | 3086 struct loop *loop; |
3095 | 3087 |
3096 | 3088 gcc_assert (! scev_initialized_p ()); |
3097 scalar_evolution_info = htab_create_ggc (100, hash_scev_info, eq_scev_info, | 3089 |
3098 del_scev_info); | 3090 scalar_evolution_info = hash_table<scev_info_hasher>::create_ggc (100); |
3099 | 3091 |
3100 initialize_scalar_evolutions_analyzer (); | 3092 initialize_scalar_evolutions_analyzer (); |
3101 | 3093 |
3102 FOR_EACH_LOOP (li, loop, 0) | 3094 FOR_EACH_LOOP (loop, 0) |
3103 { | 3095 { |
3104 loop->nb_iterations = NULL_TREE; | 3096 loop->nb_iterations = NULL_TREE; |
3105 } | 3097 } |
3098 } | |
3099 | |
3100 /* Return true if SCEV is initialized. */ | |
3101 | |
3102 bool | |
3103 scev_initialized_p (void) | |
3104 { | |
3105 return scalar_evolution_info != NULL; | |
3106 } | 3106 } |
3107 | 3107 |
3108 /* Cleans up the information cached by the scalar evolutions analysis | 3108 /* Cleans up the information cached by the scalar evolutions analysis |
3109 in the hash table. */ | 3109 in the hash table. */ |
3110 | 3110 |
3112 scev_reset_htab (void) | 3112 scev_reset_htab (void) |
3113 { | 3113 { |
3114 if (!scalar_evolution_info) | 3114 if (!scalar_evolution_info) |
3115 return; | 3115 return; |
3116 | 3116 |
3117 htab_empty (scalar_evolution_info); | 3117 scalar_evolution_info->empty (); |
3118 } | 3118 } |
3119 | 3119 |
3120 /* Cleans up the information cached by the scalar evolutions analysis | 3120 /* Cleans up the information cached by the scalar evolutions analysis |
3121 in the hash table and in the loop->nb_iterations. */ | 3121 in the hash table and in the loop->nb_iterations. */ |
3122 | 3122 |
3123 void | 3123 void |
3124 scev_reset (void) | 3124 scev_reset (void) |
3125 { | 3125 { |
3126 loop_iterator li; | |
3127 struct loop *loop; | 3126 struct loop *loop; |
3128 | 3127 |
3129 scev_reset_htab (); | 3128 scev_reset_htab (); |
3130 | 3129 |
3131 if (!current_loops) | 3130 FOR_EACH_LOOP (loop, 0) |
3132 return; | |
3133 | |
3134 FOR_EACH_LOOP (li, loop, 0) | |
3135 { | 3131 { |
3136 loop->nb_iterations = NULL_TREE; | 3132 loop->nb_iterations = NULL_TREE; |
3137 } | 3133 } |
3134 } | |
3135 | |
3136 /* Return true if the IV calculation in TYPE can overflow based on the knowledge | |
3137 of the upper bound on the number of iterations of LOOP, the BASE and STEP | |
3138 of IV. | |
3139 | |
3140 We do not use information whether TYPE can overflow so it is safe to | |
3141 use this test even for derived IVs not computed every iteration or | |
3142 hypotetical IVs to be inserted into code. */ | |
3143 | |
3144 bool | |
3145 iv_can_overflow_p (struct loop *loop, tree type, tree base, tree step) | |
3146 { | |
3147 widest_int nit; | |
3148 wide_int base_min, base_max, step_min, step_max, type_min, type_max; | |
3149 signop sgn = TYPE_SIGN (type); | |
3150 | |
3151 if (integer_zerop (step)) | |
3152 return false; | |
3153 | |
3154 if (TREE_CODE (base) == INTEGER_CST) | |
3155 base_min = base_max = wi::to_wide (base); | |
3156 else if (TREE_CODE (base) == SSA_NAME | |
3157 && INTEGRAL_TYPE_P (TREE_TYPE (base)) | |
3158 && get_range_info (base, &base_min, &base_max) == VR_RANGE) | |
3159 ; | |
3160 else | |
3161 return true; | |
3162 | |
3163 if (TREE_CODE (step) == INTEGER_CST) | |
3164 step_min = step_max = wi::to_wide (step); | |
3165 else if (TREE_CODE (step) == SSA_NAME | |
3166 && INTEGRAL_TYPE_P (TREE_TYPE (step)) | |
3167 && get_range_info (step, &step_min, &step_max) == VR_RANGE) | |
3168 ; | |
3169 else | |
3170 return true; | |
3171 | |
3172 if (!get_max_loop_iterations (loop, &nit)) | |
3173 return true; | |
3174 | |
3175 type_min = wi::min_value (type); | |
3176 type_max = wi::max_value (type); | |
3177 | |
3178 /* Just sanity check that we don't see values out of the range of the type. | |
3179 In this case the arithmetics bellow would overflow. */ | |
3180 gcc_checking_assert (wi::ge_p (base_min, type_min, sgn) | |
3181 && wi::le_p (base_max, type_max, sgn)); | |
3182 | |
3183 /* Account the possible increment in the last ieration. */ | |
3184 bool overflow = false; | |
3185 nit = wi::add (nit, 1, SIGNED, &overflow); | |
3186 if (overflow) | |
3187 return true; | |
3188 | |
3189 /* NIT is typeless and can exceed the precision of the type. In this case | |
3190 overflow is always possible, because we know STEP is non-zero. */ | |
3191 if (wi::min_precision (nit, UNSIGNED) > TYPE_PRECISION (type)) | |
3192 return true; | |
3193 wide_int nit2 = wide_int::from (nit, TYPE_PRECISION (type), UNSIGNED); | |
3194 | |
3195 /* If step can be positive, check that nit*step <= type_max-base. | |
3196 This can be done by unsigned arithmetic and we only need to watch overflow | |
3197 in the multiplication. The right hand side can always be represented in | |
3198 the type. */ | |
3199 if (sgn == UNSIGNED || !wi::neg_p (step_max)) | |
3200 { | |
3201 bool overflow = false; | |
3202 if (wi::gtu_p (wi::mul (step_max, nit2, UNSIGNED, &overflow), | |
3203 type_max - base_max) | |
3204 || overflow) | |
3205 return true; | |
3206 } | |
3207 /* If step can be negative, check that nit*(-step) <= base_min-type_min. */ | |
3208 if (sgn == SIGNED && wi::neg_p (step_min)) | |
3209 { | |
3210 bool overflow = false, overflow2 = false; | |
3211 if (wi::gtu_p (wi::mul (wi::neg (step_min, &overflow2), | |
3212 nit2, UNSIGNED, &overflow), | |
3213 base_min - type_min) | |
3214 || overflow || overflow2) | |
3215 return true; | |
3216 } | |
3217 | |
3218 return false; | |
3219 } | |
3220 | |
3221 /* Given EV with form of "(type) {inner_base, inner_step}_loop", this | |
3222 function tries to derive condition under which it can be simplified | |
3223 into "{(type)inner_base, (type)inner_step}_loop". The condition is | |
3224 the maximum number that inner iv can iterate. */ | |
3225 | |
3226 static tree | |
3227 derive_simple_iv_with_niters (tree ev, tree *niters) | |
3228 { | |
3229 if (!CONVERT_EXPR_P (ev)) | |
3230 return ev; | |
3231 | |
3232 tree inner_ev = TREE_OPERAND (ev, 0); | |
3233 if (TREE_CODE (inner_ev) != POLYNOMIAL_CHREC) | |
3234 return ev; | |
3235 | |
3236 tree init = CHREC_LEFT (inner_ev); | |
3237 tree step = CHREC_RIGHT (inner_ev); | |
3238 if (TREE_CODE (init) != INTEGER_CST | |
3239 || TREE_CODE (step) != INTEGER_CST || integer_zerop (step)) | |
3240 return ev; | |
3241 | |
3242 tree type = TREE_TYPE (ev); | |
3243 tree inner_type = TREE_TYPE (inner_ev); | |
3244 if (TYPE_PRECISION (inner_type) >= TYPE_PRECISION (type)) | |
3245 return ev; | |
3246 | |
3247 /* Type conversion in "(type) {inner_base, inner_step}_loop" can be | |
3248 folded only if inner iv won't overflow. We compute the maximum | |
3249 number the inner iv can iterate before overflowing and return the | |
3250 simplified affine iv. */ | |
3251 tree delta; | |
3252 init = fold_convert (type, init); | |
3253 step = fold_convert (type, step); | |
3254 ev = build_polynomial_chrec (CHREC_VARIABLE (inner_ev), init, step); | |
3255 if (tree_int_cst_sign_bit (step)) | |
3256 { | |
3257 tree bound = lower_bound_in_type (inner_type, inner_type); | |
3258 delta = fold_build2 (MINUS_EXPR, type, init, fold_convert (type, bound)); | |
3259 step = fold_build1 (NEGATE_EXPR, type, step); | |
3260 } | |
3261 else | |
3262 { | |
3263 tree bound = upper_bound_in_type (inner_type, inner_type); | |
3264 delta = fold_build2 (MINUS_EXPR, type, fold_convert (type, bound), init); | |
3265 } | |
3266 *niters = fold_build2 (FLOOR_DIV_EXPR, type, delta, step); | |
3267 return ev; | |
3138 } | 3268 } |
3139 | 3269 |
3140 /* Checks whether use of OP in USE_LOOP behaves as a simple affine iv with | 3270 /* Checks whether use of OP in USE_LOOP behaves as a simple affine iv with |
3141 respect to WRTO_LOOP and returns its base and step in IV if possible | 3271 respect to WRTO_LOOP and returns its base and step in IV if possible |
3142 (see analyze_scalar_evolution_in_loop for more details on USE_LOOP | 3272 (see analyze_scalar_evolution_in_loop for more details on USE_LOOP |
3152 is only safe if IV->no_overflow is false, or TYPE_OVERFLOW_UNDEFINED is | 3282 is only safe if IV->no_overflow is false, or TYPE_OVERFLOW_UNDEFINED is |
3153 false for the type of the induction variable, or you can prove that i does | 3283 false for the type of the induction variable, or you can prove that i does |
3154 not wrap by some other argument. Otherwise, this might introduce undefined | 3284 not wrap by some other argument. Otherwise, this might introduce undefined |
3155 behavior, and | 3285 behavior, and |
3156 | 3286 |
3157 for (i = iv->base; ; i = (type) ((unsigned type) i + (unsigned type) iv->step)) | 3287 i = iv->base; |
3158 | 3288 for (; ; i = (type) ((unsigned type) i + (unsigned type) iv->step)) |
3159 must be used instead. */ | 3289 |
3290 must be used instead. | |
3291 | |
3292 When IV_NITERS is not NULL, this function also checks case in which OP | |
3293 is a conversion of an inner simple iv of below form: | |
3294 | |
3295 (outer_type){inner_base, inner_step}_loop. | |
3296 | |
3297 If type of inner iv has smaller precision than outer_type, it can't be | |
3298 folded into {(outer_type)inner_base, (outer_type)inner_step}_loop because | |
3299 the inner iv could overflow/wrap. In this case, we derive a condition | |
3300 under which the inner iv won't overflow/wrap and do the simplification. | |
3301 The derived condition normally is the maximum number the inner iv can | |
3302 iterate, and will be stored in IV_NITERS. This is useful in loop niter | |
3303 analysis, to derive break conditions when a loop must terminate, when is | |
3304 infinite. */ | |
3160 | 3305 |
3161 bool | 3306 bool |
3162 simple_iv (struct loop *wrto_loop, struct loop *use_loop, tree op, | 3307 simple_iv_with_niters (struct loop *wrto_loop, struct loop *use_loop, |
3163 affine_iv *iv, bool allow_nonconstant_step) | 3308 tree op, affine_iv *iv, tree *iv_niters, |
3164 { | 3309 bool allow_nonconstant_step) |
3165 tree type, ev; | 3310 { |
3166 bool folded_casts; | 3311 enum tree_code code; |
3312 tree type, ev, base, e; | |
3313 wide_int extreme; | |
3314 bool folded_casts, overflow; | |
3167 | 3315 |
3168 iv->base = NULL_TREE; | 3316 iv->base = NULL_TREE; |
3169 iv->step = NULL_TREE; | 3317 iv->step = NULL_TREE; |
3170 iv->no_overflow = false; | 3318 iv->no_overflow = false; |
3171 | 3319 |
3172 type = TREE_TYPE (op); | 3320 type = TREE_TYPE (op); |
3173 if (TREE_CODE (type) != INTEGER_TYPE | 3321 if (!POINTER_TYPE_P (type) |
3174 && TREE_CODE (type) != POINTER_TYPE) | 3322 && !INTEGRAL_TYPE_P (type)) |
3175 return false; | 3323 return false; |
3176 | 3324 |
3177 ev = analyze_scalar_evolution_in_loop (wrto_loop, use_loop, op, | 3325 ev = analyze_scalar_evolution_in_loop (wrto_loop, use_loop, op, |
3178 &folded_casts); | 3326 &folded_casts); |
3179 if (chrec_contains_undetermined (ev) | 3327 if (chrec_contains_undetermined (ev) |
3186 iv->step = build_int_cst (TREE_TYPE (ev), 0); | 3334 iv->step = build_int_cst (TREE_TYPE (ev), 0); |
3187 iv->no_overflow = true; | 3335 iv->no_overflow = true; |
3188 return true; | 3336 return true; |
3189 } | 3337 } |
3190 | 3338 |
3191 if (TREE_CODE (ev) != POLYNOMIAL_CHREC | 3339 /* If we can derive valid scalar evolution with assumptions. */ |
3192 || CHREC_VARIABLE (ev) != (unsigned) wrto_loop->num) | 3340 if (iv_niters && TREE_CODE (ev) != POLYNOMIAL_CHREC) |
3341 ev = derive_simple_iv_with_niters (ev, iv_niters); | |
3342 | |
3343 if (TREE_CODE (ev) != POLYNOMIAL_CHREC) | |
3344 return false; | |
3345 | |
3346 if (CHREC_VARIABLE (ev) != (unsigned) wrto_loop->num) | |
3193 return false; | 3347 return false; |
3194 | 3348 |
3195 iv->step = CHREC_RIGHT (ev); | 3349 iv->step = CHREC_RIGHT (ev); |
3196 if ((!allow_nonconstant_step && TREE_CODE (iv->step) != INTEGER_CST) | 3350 if ((!allow_nonconstant_step && TREE_CODE (iv->step) != INTEGER_CST) |
3197 || tree_contains_chrecs (iv->step, NULL)) | 3351 || tree_contains_chrecs (iv->step, NULL)) |
3199 | 3353 |
3200 iv->base = CHREC_LEFT (ev); | 3354 iv->base = CHREC_LEFT (ev); |
3201 if (tree_contains_chrecs (iv->base, NULL)) | 3355 if (tree_contains_chrecs (iv->base, NULL)) |
3202 return false; | 3356 return false; |
3203 | 3357 |
3204 iv->no_overflow = !folded_casts && TYPE_OVERFLOW_UNDEFINED (type); | 3358 iv->no_overflow = !folded_casts && nowrap_type_p (type); |
3205 | 3359 |
3360 if (!iv->no_overflow | |
3361 && !iv_can_overflow_p (wrto_loop, type, iv->base, iv->step)) | |
3362 iv->no_overflow = true; | |
3363 | |
3364 /* Try to simplify iv base: | |
3365 | |
3366 (signed T) ((unsigned T)base + step) ;; TREE_TYPE (base) == signed T | |
3367 == (signed T)(unsigned T)base + step | |
3368 == base + step | |
3369 | |
3370 If we can prove operation (base + step) doesn't overflow or underflow. | |
3371 Specifically, we try to prove below conditions are satisfied: | |
3372 | |
3373 base <= UPPER_BOUND (type) - step ;;step > 0 | |
3374 base >= LOWER_BOUND (type) - step ;;step < 0 | |
3375 | |
3376 This is done by proving the reverse conditions are false using loop's | |
3377 initial conditions. | |
3378 | |
3379 The is necessary to make loop niter, or iv overflow analysis easier | |
3380 for below example: | |
3381 | |
3382 int foo (int *a, signed char s, signed char l) | |
3383 { | |
3384 signed char i; | |
3385 for (i = s; i < l; i++) | |
3386 a[i] = 0; | |
3387 return 0; | |
3388 } | |
3389 | |
3390 Note variable I is firstly converted to type unsigned char, incremented, | |
3391 then converted back to type signed char. */ | |
3392 | |
3393 if (wrto_loop->num != use_loop->num) | |
3394 return true; | |
3395 | |
3396 if (!CONVERT_EXPR_P (iv->base) || TREE_CODE (iv->step) != INTEGER_CST) | |
3397 return true; | |
3398 | |
3399 type = TREE_TYPE (iv->base); | |
3400 e = TREE_OPERAND (iv->base, 0); | |
3401 if (TREE_CODE (e) != PLUS_EXPR | |
3402 || TREE_CODE (TREE_OPERAND (e, 1)) != INTEGER_CST | |
3403 || !tree_int_cst_equal (iv->step, | |
3404 fold_convert (type, TREE_OPERAND (e, 1)))) | |
3405 return true; | |
3406 e = TREE_OPERAND (e, 0); | |
3407 if (!CONVERT_EXPR_P (e)) | |
3408 return true; | |
3409 base = TREE_OPERAND (e, 0); | |
3410 if (!useless_type_conversion_p (type, TREE_TYPE (base))) | |
3411 return true; | |
3412 | |
3413 if (tree_int_cst_sign_bit (iv->step)) | |
3414 { | |
3415 code = LT_EXPR; | |
3416 extreme = wi::min_value (type); | |
3417 } | |
3418 else | |
3419 { | |
3420 code = GT_EXPR; | |
3421 extreme = wi::max_value (type); | |
3422 } | |
3423 overflow = false; | |
3424 extreme = wi::sub (extreme, wi::to_wide (iv->step), | |
3425 TYPE_SIGN (type), &overflow); | |
3426 if (overflow) | |
3427 return true; | |
3428 e = fold_build2 (code, boolean_type_node, base, | |
3429 wide_int_to_tree (type, extreme)); | |
3430 e = simplify_using_initial_conditions (use_loop, e); | |
3431 if (!integer_zerop (e)) | |
3432 return true; | |
3433 | |
3434 if (POINTER_TYPE_P (TREE_TYPE (base))) | |
3435 code = POINTER_PLUS_EXPR; | |
3436 else | |
3437 code = PLUS_EXPR; | |
3438 | |
3439 iv->base = fold_build2 (code, TREE_TYPE (base), base, iv->step); | |
3206 return true; | 3440 return true; |
3207 } | 3441 } |
3208 | 3442 |
3209 /* Runs the analysis of scalar evolutions. */ | 3443 /* Like simple_iv_with_niters, but return TRUE when OP behaves as a simple |
3210 | 3444 affine iv unconditionally. */ |
3211 void | 3445 |
3212 scev_analysis (void) | 3446 bool |
3213 { | 3447 simple_iv (struct loop *wrto_loop, struct loop *use_loop, tree op, |
3214 VEC(gimple,heap) *exit_conditions; | 3448 affine_iv *iv, bool allow_nonconstant_step) |
3215 | 3449 { |
3216 exit_conditions = VEC_alloc (gimple, heap, 37); | 3450 return simple_iv_with_niters (wrto_loop, use_loop, op, iv, |
3217 select_loops_exit_conditions (&exit_conditions); | 3451 NULL, allow_nonconstant_step); |
3218 | |
3219 if (dump_file && (dump_flags & TDF_STATS)) | |
3220 analyze_scalar_evolution_for_all_loop_phi_nodes (&exit_conditions); | |
3221 | |
3222 number_of_iterations_for_all_loops (&exit_conditions); | |
3223 VEC_free (gimple, heap, exit_conditions); | |
3224 } | 3452 } |
3225 | 3453 |
3226 /* Finalize the scalar evolution analysis. */ | 3454 /* Finalize the scalar evolution analysis. */ |
3227 | 3455 |
3228 void | 3456 void |
3229 scev_finalize (void) | 3457 scev_finalize (void) |
3230 { | 3458 { |
3231 if (!scalar_evolution_info) | 3459 if (!scalar_evolution_info) |
3232 return; | 3460 return; |
3233 htab_delete (scalar_evolution_info); | 3461 scalar_evolution_info->empty (); |
3234 scalar_evolution_info = NULL; | 3462 scalar_evolution_info = NULL; |
3463 free_numbers_of_iterations_estimates (cfun); | |
3235 } | 3464 } |
3236 | 3465 |
3237 /* Returns true if the expression EXPR is considered to be too expensive | 3466 /* Returns true if the expression EXPR is considered to be too expensive |
3238 for scev_const_prop. */ | 3467 for scev_const_prop. */ |
3239 | 3468 |
3276 default: | 3505 default: |
3277 return true; | 3506 return true; |
3278 } | 3507 } |
3279 } | 3508 } |
3280 | 3509 |
3510 /* Do final value replacement for LOOP. */ | |
3511 | |
3512 void | |
3513 final_value_replacement_loop (struct loop *loop) | |
3514 { | |
3515 /* If we do not know exact number of iterations of the loop, we cannot | |
3516 replace the final value. */ | |
3517 edge exit = single_exit (loop); | |
3518 if (!exit) | |
3519 return; | |
3520 | |
3521 tree niter = number_of_latch_executions (loop); | |
3522 if (niter == chrec_dont_know) | |
3523 return; | |
3524 | |
3525 /* Ensure that it is possible to insert new statements somewhere. */ | |
3526 if (!single_pred_p (exit->dest)) | |
3527 split_loop_exit_edge (exit); | |
3528 | |
3529 /* Set stmt insertion pointer. All stmts are inserted before this point. */ | |
3530 gimple_stmt_iterator gsi = gsi_after_labels (exit->dest); | |
3531 | |
3532 struct loop *ex_loop | |
3533 = superloop_at_depth (loop, | |
3534 loop_depth (exit->dest->loop_father) + 1); | |
3535 | |
3536 gphi_iterator psi; | |
3537 for (psi = gsi_start_phis (exit->dest); !gsi_end_p (psi); ) | |
3538 { | |
3539 gphi *phi = psi.phi (); | |
3540 tree rslt = PHI_RESULT (phi); | |
3541 tree def = PHI_ARG_DEF_FROM_EDGE (phi, exit); | |
3542 if (virtual_operand_p (def)) | |
3543 { | |
3544 gsi_next (&psi); | |
3545 continue; | |
3546 } | |
3547 | |
3548 if (!POINTER_TYPE_P (TREE_TYPE (def)) | |
3549 && !INTEGRAL_TYPE_P (TREE_TYPE (def))) | |
3550 { | |
3551 gsi_next (&psi); | |
3552 continue; | |
3553 } | |
3554 | |
3555 bool folded_casts; | |
3556 def = analyze_scalar_evolution_in_loop (ex_loop, loop, def, | |
3557 &folded_casts); | |
3558 def = compute_overall_effect_of_inner_loop (ex_loop, def); | |
3559 if (!tree_does_not_contain_chrecs (def) | |
3560 || chrec_contains_symbols_defined_in_loop (def, ex_loop->num) | |
3561 /* Moving the computation from the loop may prolong life range | |
3562 of some ssa names, which may cause problems if they appear | |
3563 on abnormal edges. */ | |
3564 || contains_abnormal_ssa_name_p (def) | |
3565 /* Do not emit expensive expressions. The rationale is that | |
3566 when someone writes a code like | |
3567 | |
3568 while (n > 45) n -= 45; | |
3569 | |
3570 he probably knows that n is not large, and does not want it | |
3571 to be turned into n %= 45. */ | |
3572 || expression_expensive_p (def)) | |
3573 { | |
3574 if (dump_file && (dump_flags & TDF_DETAILS)) | |
3575 { | |
3576 fprintf (dump_file, "not replacing:\n "); | |
3577 print_gimple_stmt (dump_file, phi, 0); | |
3578 fprintf (dump_file, "\n"); | |
3579 } | |
3580 gsi_next (&psi); | |
3581 continue; | |
3582 } | |
3583 | |
3584 /* Eliminate the PHI node and replace it by a computation outside | |
3585 the loop. */ | |
3586 if (dump_file) | |
3587 { | |
3588 fprintf (dump_file, "\nfinal value replacement:\n "); | |
3589 print_gimple_stmt (dump_file, phi, 0); | |
3590 fprintf (dump_file, " with\n "); | |
3591 } | |
3592 def = unshare_expr (def); | |
3593 remove_phi_node (&psi, false); | |
3594 | |
3595 /* If def's type has undefined overflow and there were folded | |
3596 casts, rewrite all stmts added for def into arithmetics | |
3597 with defined overflow behavior. */ | |
3598 if (folded_casts && ANY_INTEGRAL_TYPE_P (TREE_TYPE (def)) | |
3599 && TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (def))) | |
3600 { | |
3601 gimple_seq stmts; | |
3602 gimple_stmt_iterator gsi2; | |
3603 def = force_gimple_operand (def, &stmts, true, NULL_TREE); | |
3604 gsi2 = gsi_start (stmts); | |
3605 while (!gsi_end_p (gsi2)) | |
3606 { | |
3607 gimple *stmt = gsi_stmt (gsi2); | |
3608 gimple_stmt_iterator gsi3 = gsi2; | |
3609 gsi_next (&gsi2); | |
3610 gsi_remove (&gsi3, false); | |
3611 if (is_gimple_assign (stmt) | |
3612 && arith_code_with_undefined_signed_overflow | |
3613 (gimple_assign_rhs_code (stmt))) | |
3614 gsi_insert_seq_before (&gsi, | |
3615 rewrite_to_defined_overflow (stmt), | |
3616 GSI_SAME_STMT); | |
3617 else | |
3618 gsi_insert_before (&gsi, stmt, GSI_SAME_STMT); | |
3619 } | |
3620 } | |
3621 else | |
3622 def = force_gimple_operand_gsi (&gsi, def, false, NULL_TREE, | |
3623 true, GSI_SAME_STMT); | |
3624 | |
3625 gassign *ass = gimple_build_assign (rslt, def); | |
3626 gsi_insert_before (&gsi, ass, GSI_SAME_STMT); | |
3627 if (dump_file) | |
3628 { | |
3629 print_gimple_stmt (dump_file, ass, 0); | |
3630 fprintf (dump_file, "\n"); | |
3631 } | |
3632 } | |
3633 } | |
3634 | |
3281 /* Replace ssa names for that scev can prove they are constant by the | 3635 /* Replace ssa names for that scev can prove they are constant by the |
3282 appropriate constants. Also perform final value replacement in loops, | 3636 appropriate constants. Also perform final value replacement in loops, |
3283 in case the replacement expressions are cheap. | 3637 in case the replacement expressions are cheap. |
3284 | 3638 |
3285 We only consider SSA names defined by phi nodes; rest is left to the | 3639 We only consider SSA names defined by phi nodes; rest is left to the |
3288 unsigned int | 3642 unsigned int |
3289 scev_const_prop (void) | 3643 scev_const_prop (void) |
3290 { | 3644 { |
3291 basic_block bb; | 3645 basic_block bb; |
3292 tree name, type, ev; | 3646 tree name, type, ev; |
3293 gimple phi, ass; | 3647 gphi *phi; |
3294 struct loop *loop, *ex_loop; | 3648 struct loop *loop; |
3295 bitmap ssa_names_to_remove = NULL; | 3649 bitmap ssa_names_to_remove = NULL; |
3296 unsigned i; | 3650 unsigned i; |
3297 loop_iterator li; | 3651 gphi_iterator psi; |
3298 gimple_stmt_iterator psi; | 3652 |
3299 | 3653 if (number_of_loops (cfun) <= 1) |
3300 if (number_of_loops () <= 1) | |
3301 return 0; | 3654 return 0; |
3302 | 3655 |
3303 FOR_EACH_BB (bb) | 3656 FOR_EACH_BB_FN (bb, cfun) |
3304 { | 3657 { |
3305 loop = bb->loop_father; | 3658 loop = bb->loop_father; |
3306 | 3659 |
3307 for (psi = gsi_start_phis (bb); !gsi_end_p (psi); gsi_next (&psi)) | 3660 for (psi = gsi_start_phis (bb); !gsi_end_p (psi); gsi_next (&psi)) |
3308 { | 3661 { |
3309 phi = gsi_stmt (psi); | 3662 phi = psi.phi (); |
3310 name = PHI_RESULT (phi); | 3663 name = PHI_RESULT (phi); |
3311 | 3664 |
3312 if (!is_gimple_reg (name)) | 3665 if (virtual_operand_p (name)) |
3313 continue; | 3666 continue; |
3314 | 3667 |
3315 type = TREE_TYPE (name); | 3668 type = TREE_TYPE (name); |
3316 | 3669 |
3317 if (!POINTER_TYPE_P (type) | 3670 if (!POINTER_TYPE_P (type) |
3318 && !INTEGRAL_TYPE_P (type)) | 3671 && !INTEGRAL_TYPE_P (type)) |
3319 continue; | 3672 continue; |
3320 | 3673 |
3321 ev = resolve_mixers (loop, analyze_scalar_evolution (loop, name)); | 3674 ev = resolve_mixers (loop, analyze_scalar_evolution (loop, name), |
3675 NULL); | |
3322 if (!is_gimple_min_invariant (ev) | 3676 if (!is_gimple_min_invariant (ev) |
3323 || !may_propagate_copy (name, ev)) | 3677 || !may_propagate_copy (name, ev)) |
3324 continue; | 3678 continue; |
3325 | 3679 |
3326 /* Replace the uses of the name. */ | 3680 /* Replace the uses of the name. */ |
3327 if (name != ev) | 3681 if (name != ev) |
3328 replace_uses_by (name, ev); | 3682 { |
3683 if (dump_file && (dump_flags & TDF_DETAILS)) | |
3684 { | |
3685 fprintf (dump_file, "Replacing uses of: "); | |
3686 print_generic_expr (dump_file, name); | |
3687 fprintf (dump_file, " with: "); | |
3688 print_generic_expr (dump_file, ev); | |
3689 fprintf (dump_file, "\n"); | |
3690 } | |
3691 replace_uses_by (name, ev); | |
3692 } | |
3329 | 3693 |
3330 if (!ssa_names_to_remove) | 3694 if (!ssa_names_to_remove) |
3331 ssa_names_to_remove = BITMAP_ALLOC (NULL); | 3695 ssa_names_to_remove = BITMAP_ALLOC (NULL); |
3332 bitmap_set_bit (ssa_names_to_remove, SSA_NAME_VERSION (name)); | 3696 bitmap_set_bit (ssa_names_to_remove, SSA_NAME_VERSION (name)); |
3333 } | 3697 } |
3342 | 3706 |
3343 EXECUTE_IF_SET_IN_BITMAP (ssa_names_to_remove, 0, i, bi) | 3707 EXECUTE_IF_SET_IN_BITMAP (ssa_names_to_remove, 0, i, bi) |
3344 { | 3708 { |
3345 gimple_stmt_iterator psi; | 3709 gimple_stmt_iterator psi; |
3346 name = ssa_name (i); | 3710 name = ssa_name (i); |
3347 phi = SSA_NAME_DEF_STMT (name); | 3711 phi = as_a <gphi *> (SSA_NAME_DEF_STMT (name)); |
3348 | 3712 |
3349 gcc_assert (gimple_code (phi) == GIMPLE_PHI); | 3713 gcc_assert (gimple_code (phi) == GIMPLE_PHI); |
3350 psi = gsi_for_stmt (phi); | 3714 psi = gsi_for_stmt (phi); |
3351 remove_phi_node (&psi, true); | 3715 remove_phi_node (&psi, true); |
3352 } | 3716 } |
3354 BITMAP_FREE (ssa_names_to_remove); | 3718 BITMAP_FREE (ssa_names_to_remove); |
3355 scev_reset (); | 3719 scev_reset (); |
3356 } | 3720 } |
3357 | 3721 |
3358 /* Now the regular final value replacement. */ | 3722 /* Now the regular final value replacement. */ |
3359 FOR_EACH_LOOP (li, loop, LI_FROM_INNERMOST) | 3723 FOR_EACH_LOOP (loop, LI_FROM_INNERMOST) |
3360 { | 3724 final_value_replacement_loop (loop); |
3361 edge exit; | 3725 |
3362 tree def, rslt, niter; | |
3363 gimple_stmt_iterator bsi; | |
3364 | |
3365 /* If we do not know exact number of iterations of the loop, we cannot | |
3366 replace the final value. */ | |
3367 exit = single_exit (loop); | |
3368 if (!exit) | |
3369 continue; | |
3370 | |
3371 niter = number_of_latch_executions (loop); | |
3372 if (niter == chrec_dont_know) | |
3373 continue; | |
3374 | |
3375 /* Ensure that it is possible to insert new statements somewhere. */ | |
3376 if (!single_pred_p (exit->dest)) | |
3377 split_loop_exit_edge (exit); | |
3378 bsi = gsi_after_labels (exit->dest); | |
3379 | |
3380 ex_loop = superloop_at_depth (loop, | |
3381 loop_depth (exit->dest->loop_father) + 1); | |
3382 | |
3383 for (psi = gsi_start_phis (exit->dest); !gsi_end_p (psi); ) | |
3384 { | |
3385 phi = gsi_stmt (psi); | |
3386 rslt = PHI_RESULT (phi); | |
3387 def = PHI_ARG_DEF_FROM_EDGE (phi, exit); | |
3388 if (!is_gimple_reg (def)) | |
3389 { | |
3390 gsi_next (&psi); | |
3391 continue; | |
3392 } | |
3393 | |
3394 if (!POINTER_TYPE_P (TREE_TYPE (def)) | |
3395 && !INTEGRAL_TYPE_P (TREE_TYPE (def))) | |
3396 { | |
3397 gsi_next (&psi); | |
3398 continue; | |
3399 } | |
3400 | |
3401 def = analyze_scalar_evolution_in_loop (ex_loop, loop, def, NULL); | |
3402 def = compute_overall_effect_of_inner_loop (ex_loop, def); | |
3403 if (!tree_does_not_contain_chrecs (def) | |
3404 || chrec_contains_symbols_defined_in_loop (def, ex_loop->num) | |
3405 /* Moving the computation from the loop may prolong life range | |
3406 of some ssa names, which may cause problems if they appear | |
3407 on abnormal edges. */ | |
3408 || contains_abnormal_ssa_name_p (def) | |
3409 /* Do not emit expensive expressions. The rationale is that | |
3410 when someone writes a code like | |
3411 | |
3412 while (n > 45) n -= 45; | |
3413 | |
3414 he probably knows that n is not large, and does not want it | |
3415 to be turned into n %= 45. */ | |
3416 || expression_expensive_p (def)) | |
3417 { | |
3418 gsi_next (&psi); | |
3419 continue; | |
3420 } | |
3421 | |
3422 /* Eliminate the PHI node and replace it by a computation outside | |
3423 the loop. */ | |
3424 def = unshare_expr (def); | |
3425 remove_phi_node (&psi, false); | |
3426 | |
3427 def = force_gimple_operand_gsi (&bsi, def, false, NULL_TREE, | |
3428 true, GSI_SAME_STMT); | |
3429 ass = gimple_build_assign (rslt, def); | |
3430 gsi_insert_before (&bsi, ass, GSI_SAME_STMT); | |
3431 } | |
3432 } | |
3433 return 0; | 3726 return 0; |
3434 } | 3727 } |
3435 | 3728 |
3436 #include "gt-tree-scalar-evolution.h" | 3729 #include "gt-tree-scalar-evolution.h" |