From 4f9998257ad85b59113d4ee99367de3d4d90eca6 Mon Sep 17 00:00:00 2001 From: Sven Verdoolaege Date: Thu, 25 Feb 2016 17:19:21 +0100 Subject: [PATCH] add pet_expr_get_hash This will be needed for defining pet_expr_to_isl_pw_aff objects in the next commit. Signed-off-by: Sven Verdoolaege --- expr.c | 76 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++- expr.h | 9 ++++++++ 2 files changed, 84 insertions(+), 1 deletion(-) diff --git a/expr.c b/expr.c index 1324947..ec177eb 100644 --- a/expr.c +++ b/expr.c @@ -34,6 +34,7 @@ #include +#include #include #include "aff.h" @@ -545,13 +546,21 @@ static __isl_give pet_expr *pet_expr_dup(__isl_keep pet_expr *expr) return dup; } +/* Return a pet_expr that is equal to "expr" and that has only + * a single reference. + * + * If "expr" itself only has one reference, then clear its hash value + * since the returned pet_expr will be modified. + */ __isl_give pet_expr *pet_expr_cow(__isl_take pet_expr *expr) { if (!expr) return NULL; - if (expr->ref == 1) + if (expr->ref == 1) { + expr->hash = 0; return expr; + } expr->ref--; return pet_expr_dup(expr); } @@ -915,6 +924,8 @@ static __isl_give isl_union_map *construct_access_relation( * * We do not cow since adding an explicit access relation * does not change the meaning of the expression. + * However, the explicit access relations may modify the hash value, + * so the cached value is reset. */ static __isl_give pet_expr *introduce_access_relations( __isl_take pet_expr *expr) @@ -933,6 +944,7 @@ static __isl_give pet_expr *introduce_access_relations( if (!access) return pet_expr_free(expr); + expr->hash = 0; kill = expr->acc.kill; read = expr->acc.read; write = expr->acc.write; @@ -957,6 +969,68 @@ static __isl_give pet_expr *introduce_access_relations( return expr; } +/* Return a hash value that digests "expr". + * If a hash value was computed already, then return that value. + * Otherwise, compute the hash value and store a copy in expr->hash. + */ +uint32_t pet_expr_get_hash(__isl_keep pet_expr *expr) +{ + int i; + enum pet_expr_access_type type; + uint32_t hash, hash_f; + + if (!expr) + return 0; + if (expr->hash) + return expr->hash; + + hash = isl_hash_init(); + isl_hash_byte(hash, expr->type & 0xFF); + isl_hash_byte(hash, expr->n_arg & 0xFF); + for (i = 0; i < expr->n_arg; ++i) { + uint32_t hash_i; + hash_i = pet_expr_get_hash(expr->args[i]); + isl_hash_hash(hash, hash_i); + } + switch (expr->type) { + case pet_expr_error: + return 0; + case pet_expr_double: + hash = isl_hash_string(hash, expr->d.s); + break; + case pet_expr_int: + hash_f = isl_val_get_hash(expr->i); + isl_hash_hash(hash, hash_f); + break; + case pet_expr_access: + isl_hash_byte(hash, expr->acc.read & 0xFF); + isl_hash_byte(hash, expr->acc.write & 0xFF); + isl_hash_byte(hash, expr->acc.kill & 0xFF); + hash_f = isl_id_get_hash(expr->acc.ref_id); + isl_hash_hash(hash, hash_f); + hash_f = isl_multi_pw_aff_get_hash(expr->acc.index); + isl_hash_hash(hash, hash_f); + isl_hash_byte(hash, expr->acc.depth & 0xFF); + for (type = pet_expr_access_begin; + type < pet_expr_access_end; ++type) { + hash_f = isl_union_map_get_hash(expr->acc.access[type]); + isl_hash_hash(hash, hash_f); + } + break; + case pet_expr_op: + isl_hash_byte(hash, expr->op & 0xFF); + break; + case pet_expr_call: + hash = isl_hash_string(hash, expr->c.name); + break; + case pet_expr_cast: + hash = isl_hash_string(hash, expr->type_name); + break; + } + expr->hash = hash; + return hash; +} + /* Return 1 if the two pet_exprs are equivalent. */ int pet_expr_is_equal(__isl_keep pet_expr *expr1, __isl_keep pet_expr *expr2) diff --git a/expr.h b/expr.h index ff61746..2a35408 100644 --- a/expr.h +++ b/expr.h @@ -90,6 +90,11 @@ struct pet_expr_double { * type is valid when type == pet_expr_cast * op is valid otherwise * + * "hash" is a copy of the hash value computed by pet_expr_get_hash. + * It is zero when it has not been computed yet. The value is reset + * whenever the pet_expr is modified (in pet_expr_cow and + * introduce_access_relations). + * * If type_size is not zero, then the expression is of an integer type * and type_size represents the size of the type in bits. * If type_size is greater than zero, then the type is unsigned @@ -102,6 +107,8 @@ struct pet_expr { int ref; isl_ctx *ctx; + uint32_t hash; + enum pet_expr_type type; int type_size; @@ -150,6 +157,8 @@ __isl_give isl_pw_aff *pet_expr_extract_comparison(enum pet_op_type op, __isl_give pet_expr *pet_expr_resolve_assume(__isl_take pet_expr *expr, __isl_keep pet_context *pc); +uint32_t pet_expr_get_hash(__isl_keep pet_expr *expr); + int pet_expr_is_address_of(__isl_keep pet_expr *expr); int pet_expr_is_assume(__isl_keep pet_expr *expr); int pet_expr_is_boolean(__isl_keep pet_expr *expr); -- 2.11.4.GIT