#include "tree.h"
#include "diagnostic.h"
#include "varray.h"
+#include "cfgloop.h"
+#include "tree-flow.h"
#include "tree-chrec.h"
#include "tree-pass.h"
#include "params.h"
}
}
+/* Recursive helper function. */
+
+static bool
+evolution_function_is_invariant_rec_p (tree chrec, int loopnum)
+{
+ if (evolution_function_is_constant_p (chrec))
+ return true;
+
+ if (TREE_CODE (chrec) == SSA_NAME
+ && expr_invariant_in_loop_p (current_loops->parray[loopnum],
+ chrec))
+ return true;
+
+ if (TREE_CODE (chrec) == POLYNOMIAL_CHREC
+ && CHREC_VARIABLE (chrec) == (unsigned) loopnum)
+ return false;
+
+ switch (TREE_CODE_LENGTH (TREE_CODE (chrec)))
+ {
+ case 2:
+ if (!evolution_function_is_invariant_rec_p (TREE_OPERAND (chrec, 1),
+ loopnum))
+ return false;
+
+ case 1:
+ if (!evolution_function_is_invariant_rec_p (TREE_OPERAND (chrec, 0),
+ loopnum))
+ return false;
+ return true;
+
+ default:
+ return false;
+ }
+
+ return false;
+}
+
+/* Return true if CHREC is invariant in loop LOOPNUM, false otherwise. */
+
+bool
+evolution_function_is_invariant_p (tree chrec, int loopnum)
+{
+ if (evolution_function_is_constant_p (chrec))
+ return true;
+
+ if (current_loops != NULL)
+ return evolution_function_is_invariant_rec_p (chrec, loopnum);
+
+ return false;
+}
+
/* Determine whether the given tree is an affine multivariate
evolution. */
\f
-/* Convert CHREC to TYPE. The following is rule is always true:
- TREE_TYPE (chrec) == TREE_TYPE (CHREC_LEFT (chrec)) == TREE_TYPE
- (CHREC_RIGHT (chrec)). An example of what could happen when adding
- two chrecs and the type of the CHREC_RIGHT is different than
- CHREC_LEFT is:
+/* Convert CHREC to TYPE. When the analyzer knows the context in
+ which the CHREC is built, it sets AT_STMT to the statement that
+ contains the definition of the analyzed variable, otherwise the
+ conversion is less accurate: the information is used for
+ determining a more accurate estimation of the number of iterations.
+ By default AT_STMT could be safely set to NULL_TREE.
+
+ The following rule is always true: TREE_TYPE (chrec) ==
+ TREE_TYPE (CHREC_LEFT (chrec)) == TREE_TYPE (CHREC_RIGHT (chrec)).
+ An example of what could happen when adding two chrecs and the type
+ of the CHREC_RIGHT is different than CHREC_LEFT is:
{(uint) 0, +, (uchar) 10} +
{(uint) 0, +, (uchar) 250}
*/
tree
-chrec_convert (tree type,
- tree chrec)
+chrec_convert (tree type, tree chrec, tree at_stmt)
{
- tree ct;
-
+ tree ct, res;
+
if (automatically_generated_chrec_p (chrec))
return chrec;
if (ct == type)
return chrec;
- if (TYPE_PRECISION (ct) < TYPE_PRECISION (type))
- return count_ev_in_wider_type (type, chrec);
-
- switch (TREE_CODE (chrec))
+ if (evolution_function_is_affine_p (chrec))
{
- case POLYNOMIAL_CHREC:
+ tree step = convert_step (current_loops->parray[CHREC_VARIABLE (chrec)],
+ type, CHREC_LEFT (chrec), CHREC_RIGHT (chrec),
+ at_stmt);
+ if (!step)
+ return fold_convert (type, chrec);
+
return build_polynomial_chrec (CHREC_VARIABLE (chrec),
- chrec_convert (type,
- CHREC_LEFT (chrec)),
- chrec_convert (type,
- CHREC_RIGHT (chrec)));
+ chrec_convert (type, CHREC_LEFT (chrec),
+ at_stmt),
+ step);
+ }
- default:
- {
- tree res = fold_convert (type, chrec);
+ if (TREE_CODE (chrec) == POLYNOMIAL_CHREC)
+ return chrec_dont_know;
- /* Don't propagate overflows. */
- if (CONSTANT_CLASS_P (res))
- {
- TREE_CONSTANT_OVERFLOW (res) = 0;
- TREE_OVERFLOW (res) = 0;
- }
+ res = fold_convert (type, chrec);
- /* But reject constants that don't fit in their type after conversion.
- This can happen if TYPE_MIN_VALUE or TYPE_MAX_VALUE are not the
- natural values associated with TYPE_PRECISION and TYPE_UNSIGNED,
- and can cause problems later when computing niters of loops. Note
- that we don't do the check before converting because we don't want
- to reject conversions of negative chrecs to unsigned types. */
- if (TREE_CODE (res) == INTEGER_CST
- && TREE_CODE (type) == INTEGER_TYPE
- && !int_fits_type_p (res, type))
- res = chrec_dont_know;
-
- return res;
- }
+ /* Don't propagate overflows. */
+ if (CONSTANT_CLASS_P (res))
+ {
+ TREE_CONSTANT_OVERFLOW (res) = 0;
+ TREE_OVERFLOW (res) = 0;
}
+
+ /* But reject constants that don't fit in their type after conversion.
+ This can happen if TYPE_MIN_VALUE or TYPE_MAX_VALUE are not the
+ natural values associated with TYPE_PRECISION and TYPE_UNSIGNED,
+ and can cause problems later when computing niters of loops. Note
+ that we don't do the check before converting because we don't want
+ to reject conversions of negative chrecs to unsigned types. */
+ if (TREE_CODE (res) == INTEGER_CST
+ && TREE_CODE (type) == INTEGER_TYPE
+ && !int_fits_type_p (res, type))
+ res = chrec_dont_know;
+
+ return res;
}
/* Returns the type of the chrec. */