Re: [PATCH] Matrix Flattening and Transposing optimizations

[Razya Ladelsky <RAZYA at il dot ibm dot com>]

> >   tmp = GIMPLE_STMT_OPERAND (stmt, 1);
> >   malloc_fn_decl = CALL_EXPR_FN (tmp);
> >   if (TREE_CODE (malloc_fn_decl) != ADDR_EXPR
> >       || TREE_CODE (TREE_OPERAND (malloc_fn_decl, 0)) != FUNCTION_DECL
> >       || DECL_FUNCTION_CODE (TREE_OPERAND (malloc_fn_decl, 0)) !=
> >       BUILT_IN_MALLOC)
> 
> Better use get_call_expr_in and call_expr_flags as in is_malloc_result.

I am Looking for the particular C malloc function, therefore looking at 
the flags 
is not enough. 

> >   /* The type of the matrix elements. this is not important actually
> >      we care about the size of the elements only. */
> >   tree type;
> 
> If it's not important, why keep track of it?  It's currently write-only.
> Are there any other write-only fields in this structure?

Deleted. There were a couple more, which I got rid of. Thanks for 
noticing.

> > };
> >
> > /* In each phi node we want to record the indirection level we have
> when we
> >    get to the phi node.  Usually we will have phi nodes with more than 
two
> >    arguments, then we must assure that all of them get to the phi node
> with
> >    the same indirection level, otherwise it's not safe to do the
> flattening.
> >    So we record the information regarding the indirection level each
> time we
> >    get to the phi node in this hash table.  */
> > struct matrix_access_phi_node
> > {
> >   tree phi;
> >   int indirection_level;
> > };
> 
> Why not have a dense array indexed by SSA index number?
>

We discussed this privately.
This would take more space but less time.
If you do not object, I'll leave it as it is now. 
 
> > static bool
> > flatten_matrices (struct cgraph_node *node)
> 
> Rename to may_flatten_matrices and rename can_flatten_matrices to
> may_flatten_matrices_1.
> 

Done.
 
> > {
> >   tree new_decl;
> >   struct varpool_node *new_node;
> >
> >   new_decl = create_tmp_var (type, NULL);
> >   DECL_NAME (new_decl) = create_tmp_var_name (NULL);
> >   TREE_READONLY (new_decl) = 0;
> >   TREE_STATIC (new_decl) = 1;
> >   TREE_USED (new_decl) = 1;
> >   DECL_CONTEXT (new_decl) = NULL_TREE;
> >   DECL_ABSTRACT (new_decl) = 0;
> >   lang_hooks.dup_lang_specific_decl (new_decl);
> >   create_var_ann (new_decl);
> >   new_node = varpool_node (new_decl);
> >   notice_global_symbol (new_decl);
> >   varpool_mark_needed_node (new_node);
> >   add_referenced_var (new_decl);
> >   varpool_finalize_decl (new_decl);
> >
> >   return new_node->decl;
> > }
> 
> This probably belongs in the generic cgraph files.  Jan?
>

Discussed this with Jan.
Moved it to varpool.c. Declared in cgraph.h.
The name was changed to add_new_static_var
notice_global_symbol was removed because the variable is static and 
not exported. 
Thanks, Jan

> >
> >   /* Now go over the uses of the SSA_NAME and check how it is used in
> >      each one of them.  We are mainly looking for the pattern
> INDIRECT_REF,
> >      then a PLUS_EXPR, then INDIRECT_REF etc.  while in between there
> could
> >      be any number of copies and casts.  */
> >   gcc_assert (TREE_CODE (ssa_var) == SSA_NAME);
> >
> >   FOR_EACH_IMM_USE_FAST (use_p, imm_iter, ssa_var)
> >   {
> 
> This would be more readable if these individual checks were factored
> out of this function.

Split the three checks to individual functions:
analyze_accesses_for_call_expr
analyze_accesses_for_phi_node
analyze_accesses_for_modify_stmt

> 
> > /* Go backwords in the use-def chains and find out the expresion
> >    represented by the possible SSA name in EXPR, until it is composed
> >    of only VAR_DECL, PARM_DECL and INT_CST.  In case of phi nodes
> >    we make sure that all the arguments represet the same subexpresion,
> >    otherwise we fail.  */
> > static tree
> > can_calculate_expr_before_stmt (tree expr, sbitmap visited)
> > {
> 
> It may be easier to use the use-def chain walker for this.

I'm not sure it would help much. I need a deeper level of recursion.

> 
> >     if (node->analyzed)
> >       {
> >    tree temp_fn;
> >
> >    temp_fn = current_function_decl;
> >    current_function_decl = node->decl;
> >    push_cfun (DECL_STRUCT_FUNCTION (node->decl));
> >    bitmap_obstack_initialize (NULL);
> >    tree_register_cfg_hooks ();
> 
> Don't we already register tree_cfg_hooks in IPA mode?

Waiting for Jan's answer here.

> 
> > struct tree_opt_pass pass_ipa_mreorg = {
> >   "mreorg",         /* name */
> >   gate_matt_flatten,      /* gate */
> 
> I'd rather use gate_matrix_reorg for consistency.  Flattening is only 
*one*
> of the possible reorganizations we can make here, after all.

Changed it. Also changed the name of the pass to pass_ipa_matrix_reorg, 
and 
the flag to fipa-matrix-reorg. Changed the matrix testsuite accordingly.

I Fixed the typos, spacing and comments. Sorry about them...
I'm resubmitting the patch. I Retested it, and it passed.
(Except for ada, I did not manage to build ada compiler on 
my machine yet. Troubles with GNAT)

OK for mainline?


2007-05-07  Razya Ladelsky  <razya@il.ibm.com> 
        
        * matrix-reorg.c: New file. Implement matrix flattening and 
transposing
            optimization.
        * tree-pass.h: Add matrix reorg pass.
        * common.opt: Add fipa-mreorg flag.
        * Makefile.in: Add matrix-reorg.c.
        * passes.c: Add matrix reorg pass.
          * varpool.c (add_new_static_var): New function.
          * cgraph.h (add_new_static_var): Declare.

Attachment: matrix-reorg.c
Description: Binary data

Attachment: matrix.tgz
Description: Binary data

Attachment: matrix.diff
Description: Binary data