Please give your comments on the following idea.
Currently, the two children of binary expression tree nodes
are always expanded into rtl in the same order: left child;
right child; parent operator.
We noticed that if this evaluation order could be influenced
and reversed the order of evaluation of the children, some
optimization algorithms could benefit from the changed order.
For example, if we have an expression (sub)tree:
...
|
BIT_IOR_EXPR
/ \
/ \
/ \
LSHIFT_EXPR CALL_EXPR
/ \
... ...
for the source code fragment:
u = (u << 8) | func(18);
the generated rtl code will be something like:
u <- u<<8
call func(8)
r0 <- return value
u <- u|r0
Now, in the case of arm target, combine cannot do its job
for merging
the bit-ior with left-shift because they are not subsequent.
However, if we change the evaluation order of the children,
like this:
call func(8)
r0 <- return value
u <- u<<8
u <- u|r0
it will result in a parellel instruction in arm.
The two assembly code fragments are the following:
original:
...
bl func
mov r4, r4, asl #8
orr r4, r4, r0
...
with swapped operands:
...
bl func
orr r4, r0, r4, asl #8
...
We implemented an experimental patch that is able to replace
the children of such commutable binary expressions, and this
way influence the evaluation order of the subexpressions.
The method is of course target dependent, therefore the
possible swappings can be given in md.h using two macros
(SWP_PTRN and SWP_OPER). If nothing is given for a specific
target, no swapping will be performed.
After that a function in expr.c (swap_binary_expr) uses this
information to swap all matching subexpressions' children
(or parent with a child). (See the attached patch to
gcc-snapshot-20030317, which is regtested.)
Of course, these swappings are not guaranteed to bring any
gains, because it depends on what certain optimization
stages will do. However, maybe the method can be utilized by
some target. (For arm target the attached swappings bring
significant improvement on most test sources.)
Any ideas? Is the method useful in general?
(Attached is the patch and a simple example.)
Regards,
Gábor Lóki
------------------------------------------------------------------------
*** ./sources/gcc-20030317/gcc/config/arm/arm.h.orig Fri Nov 15 12:21:36 2002
--- ./sources/gcc-20030317/gcc/config/arm/arm.h Fri Mar 21 08:40:15 2003
*************** enum arm_builtins
*** 2788,2791 ****
--- 2788,2804 ----
ARM_BUILTIN_CLZ,
ARM_BUILTIN_MAX
};
+
+
+ /* Define pattern for swap_binary_expr in expr.c */
+ #define SWP_PTRN {{LSHIFT_EXPR,0,BIT_IOR_EXPR},{RSHIFT_EXPR,0,BIT_IOR_EXPR}, \
+ {LSHIFT_EXPR,0,BIT_XOR_EXPR},{RSHIFT_EXPR,0,BIT_XOR_EXPR}, \
+ {LSHIFT_EXPR,0,BIT_AND_EXPR},{RSHIFT_EXPR,0,BIT_AND_EXPR}, \
+ {LROTATE_EXPR,0,BIT_IOR_EXPR},{RROTATE_EXPR,0,BIT_IOR_EXPR}, \
+ {LROTATE_EXPR,0,BIT_XOR_EXPR},{RROTATE_EXPR,0,BIT_XOR_EXPR}, \
+ {LROTATE_EXPR,0,BIT_AND_EXPR},{RROTATE_EXPR,0,BIT_AND_EXPR}, \
+ {0,0,0}}
+ /* Define pattern operations for swap_binary_expr in expr.c */
+ #define SWP_OPER {0,0,0,0,0,0,0,0,0,0,0,0,-1}
+
#endif /* ! GCC_ARM_H */
*** ./sources/gcc-20030317/gcc/expr.c.orig Wed Mar 12 23:51:50 2003
--- ./sources/gcc-20030317/gcc/expr.c Fri Mar 21 08:46:06 2003
*************** find_placeholder (exp, plist)
*** 6416,6421 ****
--- 6416,6510 ----
return 0;
}
+
+
+ #ifndef SWP_PTRN
+ /* SWP_PTRN should be defined in md.h, if requied.
+ It can be used to declare a target specific patterns
+ to be used by swap_binary_expr. SWP_PTRN is a list of
+ three tree_codes.
+ The 1st is the tree_code of the left child,
+ the 2nd is the tree_code of the right child, and
+ the 3rd is the tree_code of the parent node.
+ The parent must be a binary expression node.
+ This list has to be ended by {0,0,0}. */
+ #define SWP_PTRN {{0,0,0}}
+ #endif
+ #ifndef SWP_OPER
+ /* SWP_OPER should be defined in md.h, if requied.
+ It defines the patern operations for SWP_PTRN.
+ Available operation codes:
+ 0 : swap the children positions in the operands vector
+ 1 : swap the parent node with its left child
+ 2 : swap the parent node with its right child
+ -1 : no operation
+ The size of SWP_OPER must be the as the size of SWP_PTRN. */
+ #define SWP_OPER {-1}
+ #endif
+
+ /* Find a pattern described by SWP_PTRN in a sub-tree,
+ and perform an operation defined by SWP_OPER.
+ This mechanism is available for binary expression tree nodes only. */
+ void
+ swap_binary_expr(ptr_exp)
+ tree* ptr_exp;
+ {
+ int swp = 1;
+ tree exp = *ptr_exp;
+ enum tree_code ptrn[][3] = SWP_PTRN;
+ int mask[] = SWP_OPER;
+ int i;
+ /* Try to find another swap until no new swap occurs.
+ Do something only if exp is a binary expression. */
+ while(exp && swp && TREE_CODE_CLASS(TREE_CODE(exp)) == '2')
+ {
+ swp = 0;
+ /* Find all possible patterns. */
+ for(i=0;ptrn[i][0] != 0 || ptrn[i][1] != 0 || ptrn[i][2] != 0;i++)
+ {
+ /*If any possible operation can be done and the pattern is matching with
+ exp, do the operation. */
+ if(mask[i] != -1 && (TREE_CODE (TREE_OPERAND (exp, 0)) == ptrn[i][0] || ptrn[i][0] == 0) &&
+ (TREE_CODE (TREE_OPERAND (exp, 1)) == ptrn[i][1] || ptrn[i][1] == 0) &&
+ (TREE_CODE (exp) == ptrn[i][2]))
+ {
+ /* Swap the children positions in the operands vector */
+ if(mask[i] == 0)
+ {
+ tree temp = TREE_OPERAND (exp, 0);
+ TREE_OPERAND (exp, 0) = TREE_OPERAND (exp, 1);
+ TREE_OPERAND (exp, 1) = temp;
+ swp = 1;
+ mask[i] = -1;
+ }
+ /* Swap the parent node with its left/right child
+ the other sibling of the parent and the child isn't changed. */
+ if(mask[i] == 1 || mask[i] == 2)
+ {
+ tree swp_child = TREE_OPERAND(exp,mask[i]-1);
+ tree swp_parent = exp;
+ /* Do something if the child and the parent are binary expressions. */
+ if(swp_child && swp_parent &&
+ TREE_CODE_CLASS(TREE_CODE(swp_child)) == '2' &&
+ TREE_CODE_CLASS(TREE_CODE(swp_parent)) == '2')
+ {
+ tree temp = swp_parent;
+ tree child_side = TREE_OPERAND(swp_child,mask[i]-1);
+ swp_parent = swp_child;
+ swp_child = temp;
+ TREE_OPERAND(swp_parent,mask[i]-1) = swp_child;
+ TREE_OPERAND(swp_child,mask[i]-1) = child_side;
+ swp = 1;
+ mask[i] = -1;
+ }
+ exp = swp_parent;
+ }
+ }
+ }
+ }
+ *ptr_exp = exp;
+ }
+
/* expand_expr: generate code for computing expression EXP.
An rtx for the computed value is returned. The value is never null.
*************** expand_expr (exp, target, tmode, modifie
*** 6484,6489 ****
--- 6573,6590 ----
return op0;
return const0_rtx;
}
+
+ /* Swap binary expression sub-trees (see at swap_bainary_expr) */
+ if(flag_swap_binary_expr && IS_EXPR_CODE_CLASS(TREE_CODE_CLASS(TREE_CODE(exp))))
+ {
+ int i = 0;
+ int length = first_rtl_op(TREE_CODE(exp));
+ for(;i<length;i++)
+ swap_binary_expr(&TREE_OPERAND(exp,i));
+ type = TREE_TYPE (exp);
+ unsignedp = TREE_UNSIGNED (type);
+ code = TREE_CODE (exp);
+ }
mode = TYPE_MODE (type);
/* Use subtarget as the target for operand 0 of a binary operation. */
*** ./sources/gcc-20030317/gcc/expr.h.orig Sun Feb 23 23:24:13 2003
--- ./sources/gcc-20030317/gcc/expr.h Fri Mar 21 08:43:34 2003
*************** extern rtx force_operand PARAMS ((rtx, r
*** 508,513 ****
--- 508,518 ----
the placeholder list at which the object is found is placed. */
extern tree find_placeholder PARAMS ((tree, tree *));
+ /* Find a pattern described by SWP_PTRN in a sub-tree,
+ and perform an operation defined by SWP_OPER.
+ This mechanism is available for binary expression tree nodes only. */
+ extern void swap_binary_expr PARAMS ((tree*));
+
/* Generate code for computing expression EXP.
An rtx for the computed value is returned. The value is never null.
In the case of a void EXP, const0_rtx is returned. */
*** ./sources/gcc-20030317/gcc/flags.h.orig Sun Oct 20 21:18:29 2002
--- ./sources/gcc-20030317/gcc/flags.h Fri Mar 21 08:42:33 2003
*************** extern int flag_signaling_nans;
*** 685,688 ****
--- 685,691 ----
#define HONOR_SIGN_DEPENDENT_ROUNDING(MODE) \
(MODE_HAS_SIGN_DEPENDENT_ROUNDING (MODE) && !flag_unsafe_math_optimizations)
+ /* Nonzero means enable swap binary expression sub-trees. */
+ extern int flag_swap_binary_expr;
+
#endif /* ! GCC_FLAGS_H */
*** ./sources/gcc-20030317/gcc/toplev.c.orig Thu Mar 13 01:55:24 2003
--- ./sources/gcc-20030317/gcc/toplev.c Fri Mar 21 08:41:41 2003
*************** int flag_renumber_insns = 1;
*** 879,884 ****
--- 879,887 ----
/* If nonzero, use the graph coloring register allocator. */
int flag_new_regalloc = 0;
+ /* Nonzero means enable swap binary expression sub-trees. */
+ int flag_swap_binary_expr = 0;
+
/* Nonzero if we perform superblock formation. */
int flag_tracer = 0;
*************** static const lang_independent_options f_
*** 1188,1193 ****
--- 1191,1198 ----
N_("Trap for signed overflow in addition / subtraction / multiplication") },
{ "new-ra", &flag_new_regalloc, 1,
N_("Use graph coloring register allocation.") },
+ { "swp-bin", &flag_swap_binary_expr, 1,
+ N_("Use sub-tree swapping for binary expressions") },
};
/* Table of language-specific options. */