From 6be6768e9051c498bf7358789c3c8c0e9d2114f9 Mon Sep 17 00:00:00 2001 From: Tobias Grosser Date: Thu, 30 Apr 2015 08:31:42 +0200 Subject: [PATCH] Exploit zeros in isl_mat_product The matrices passed to mat_product have commonly a large number of zero elements. By avoiding multiplications that are known to yield a zero contribution we can get a compile-time reduction of almost 6%, e.g., when running Polly on Polybench-c-3.2's 2mm kernel. Signed-off-by: Tobias Grosser Signed-off-by: Sven Verdoolaege --- isl_mat.c | 12 ++++++++++-- 1 file changed, 10 insertions(+), 2 deletions(-) diff --git a/isl_mat.c b/isl_mat.c index f4ed3701..f859601e 100644 --- a/isl_mat.c +++ b/isl_mat.c @@ -1035,6 +1035,11 @@ struct isl_mat *isl_mat_swap_rows(struct isl_mat *mat, unsigned i, unsigned j) return mat; } +/* Calculate the product of two matrices. + * + * This function is optimized for operand matrices that contain many zeros and + * skips multiplications where we know one of the operands is zero. + */ __isl_give isl_mat *isl_mat_product(__isl_take isl_mat *left, __isl_take isl_mat *right) { @@ -1055,10 +1060,13 @@ __isl_give isl_mat *isl_mat_product(__isl_take isl_mat *left, return prod; } for (i = 0; i < prod->n_row; ++i) { - for (j = 0; j < prod->n_col; ++j) { + for (j = 0; j < prod->n_col; ++j) isl_int_mul(prod->row[i][j], left->row[i][0], right->row[0][j]); - for (k = 1; k < left->n_col; ++k) + for (k = 1; k < left->n_col; ++k) { + if (isl_int_is_zero(left->row[i][k])) + continue; + for (j = 0; j < prod->n_col; ++j) isl_int_addmul(prod->row[i][j], left->row[i][k], right->row[k][j]); } -- 2.11.4.GIT