Author: dcoakley
Date: 2011-07-18 19:22:29 -0400 (Mon, 18 Jul 2011)
New Revision: 3697
Modified:
trunk/osprey/be/com/fb_whirl.cxx
trunk/osprey/be/com/fb_whirl.h
trunk/osprey/be/com/wn_lower.cxx
trunk/osprey/be/opt/opt_cfg.cxx
trunk/osprey/be/opt/opt_cfg.h
trunk/osprey/common/com/config.h
trunk/osprey/common/com/config_opt.cxx
trunk/osprey/common/com/fb_freq.h
trunk/osprey/common/com/wn.cxx
trunk/osprey/common/com/wn.h
Log:
Enable more if-conversion in WOPT.
Convert:
if (a && b)
x = ...
To:
if (a)
if (b)
x = ...
Without this transformation, WHIRL-lowering creates control flow
that WOPT-if-conversion can't handle. With this transformation,
this now looks like any other if-conversion opportunity to WOPT.
So this transformation enables more if-conversion (i.e. replace
branch with conditional move).
The transformation is enabled when the internal flag
OPT_Lower_Splitsinglecand is on (the default) and when
if-conversion is enabled in WOPT. It is applied when the action
flag LOWER_SHORTCIRCUIT is set (mainopt phase).
As part of the transformation, all profile info is updated to
be consistent: in-edge weights equal out-edge weights, all new
edges have weights, overall incoming/outgoing frequency to the
original node does not change, and the frequency of "if a && b"
is true is equal to the frequency of "if a/if b" is true.
Approved by: Sun Chan
Modified: trunk/osprey/be/com/fb_whirl.cxx
===================================================================
--- trunk/osprey/be/com/fb_whirl.cxx 2011-07-18 20:10:34 UTC (rev 3696)
+++ trunk/osprey/be/com/fb_whirl.cxx 2011-07-18 23:22:29 UTC (rev 3697)
@@ -1,5 +1,5 @@
/*
- * Copyright (C) 2010 Advanced Micro Devices, Inc. All Rights Reserved.
+ * Copyright (C) 2010-2011 Advanced Micro Devices, Inc. All Rights Reserved.
*/
/*
@@ -1417,6 +1417,81 @@
}
}
+// When transforming:
+// From:
+// if (a && b) {
+// x = ...
+// }
+// else {
+// <empty>
+// }
+// To:
+// if (a) {
+// if (b) {
+// x = ...
+// }
+// else {
+// <empty>
+// }
+// }
+// else {
+// <empty>
+// }
+//
+// We adjust the frequency data as follows:
+// From:
+// if (a && b)
+// TK / \ NT
+// / \
+// To:
+//
+// if (a)
+// TKnew / \ NTnew
+// / \
+// if (b)
+// TKinner / \ NTinner
+// / \
+// Where:
+// TOT = TK + NT
+// TK% = TK / TOT
+// TK%new = sqrt(TK%)
+// TKnew = TOT * TK%new
+// NTnew = TOT - TKnew
+// TKinner = TKnew * TK%new
+// NTinner = TKnew - TKinner
+//
+void
+FEEDBACK::FB_split_cand_if( WN *wn_outer_if, WN *wn_inner_if )
+{
+ if ( _trace )
+ fprintf( TFile, "FEEDBACK::FB_split_cand(0x%p, 0x%p):\n",
+ wn_outer_if, wn_inner_if );
+
+ Is_True( wn_outer_if != NULL && wn_inner_if != NULL,
+ ( "FEEDBACK::FB_cplit_can expects non-NULL wn_outer_if and
wn_inner_if" ) );
+
+ Is_True( WN_operator( wn_outer_if ) == OPR_IF &&
+ WN_operator( wn_inner_if ) == OPR_IF,
+ ( "FEEDBACK::FB_split_cand expects IF wn_outer_if and wn_inner_if" )
);
+
+ const FB_Info_Branch& info_branch = Query_branch( wn_outer_if );
+ FB_FREQ freq_tkn = info_branch.freq_taken;
+ FB_FREQ freq_not = info_branch.freq_not_taken;
+ FB_FREQ freq_total = freq_tkn + freq_not;
+ FB_FREQ freq_tkn_pct = freq_tkn / freq_total;
+ FB_FREQ freq_tkn_pct_new = freq_tkn_pct.sqrt();
+ FB_FREQ freq_tkn_new_outer = freq_total * freq_tkn_pct_new;
+ FB_FREQ freq_not_new_outer = freq_total - freq_tkn_new_outer;
+ Annot_branch( wn_outer_if, FB_Info_Branch( freq_tkn_new_outer,
+ freq_not_new_outer,
+ OPR_IF ) );
+ FB_FREQ freq_tkn_new_inner = freq_tkn_new_outer * freq_tkn_pct_new;
+ FB_FREQ freq_not_new_inner = freq_tkn_new_outer - freq_tkn_new_inner;
+ Annot_branch( wn_inner_if, FB_Info_Branch( freq_tkn_new_inner,
+ freq_not_new_inner,
+ OPR_IF ) );
+}
+
// ====================================================================
// The following procedures update the feedback information for whirl
// nodes created or modified during lowering transformations.
Modified: trunk/osprey/be/com/fb_whirl.h
===================================================================
--- trunk/osprey/be/com/fb_whirl.h 2011-07-18 20:10:34 UTC (rev 3696)
+++ trunk/osprey/be/com/fb_whirl.h 2011-07-18 23:22:29 UTC (rev 3697)
@@ -1,5 +1,5 @@
/*
- * Copyright (C) 2010 Advanced Micro Devices, Inc. All Rights Reserved.
+ * Copyright (C) 2010-2011 Advanced Micro Devices, Inc. All Rights Reserved.
*/
/* -*- c++ -*-
@@ -271,6 +271,7 @@
// Lower feedback info
+ void FB_split_cand_if ( WN *wn_outer_if, WN *wn_inner_if );
void FB_lower_branch ( WN *wn_br, WN *wn_branch );
void FB_lower_circuit ( WN *wn_cand, WN *wn_left_br, WN *wn_right_br );
void FB_factor_circuit( WN *wn_left, WN *wn_right,
Modified: trunk/osprey/be/com/wn_lower.cxx
===================================================================
--- trunk/osprey/be/com/wn_lower.cxx 2011-07-18 20:10:34 UTC (rev 3696)
+++ trunk/osprey/be/com/wn_lower.cxx 2011-07-18 23:22:29 UTC (rev 3697)
@@ -1,5 +1,5 @@
/*
- * Copyright (C) 2008-2010 Advanced Micro Devices, Inc. All Rights Reserved.
+ * Copyright (C) 2008-2011 Advanced Micro Devices, Inc. All Rights Reserved.
*/
/*
@@ -118,6 +118,7 @@
#include "targ_const_private.h" // for TCON_R4, TCON_R8, ..
#endif
#include "be_memop_annot.h"
+#include "config_wopt.h" // for WOPT_Enable_Simple_If_Conv
#ifdef TARG_X8664
#include <ext/hash_set>
@@ -13694,6 +13695,96 @@
}
#endif
+/* Similar to above tree_has_cand_cior, but more specialized. Check if:
+ * - tree's op is a CAND
+ * - tree has no other nested cand/cor/cselect
+ */
+static BOOL tree_has_only_one_cand (WN *tree)
+{
+ WN_ITER *wni;
+ WN *wn;
+ INT count = 0;
+
+ if (WN_operator(tree) != OPR_CAND)
+ return 0;
+ for (wni = WN_WALK_TreeIter (tree);
+ wni != NULL;
+ wni = WN_WALK_TreeNext (wni))
+ {
+ wn = WN_ITER_wn (wni);
+ if (WN_operator_is(wn, OPR_CAND))
+ ++count;
+ if (WN_operator_is(wn, OPR_CIOR) ||
+ WN_operator_is(wn, OPR_CSELECT))
+ return 0;
+ }
+ return (count == 1);
+}
+
+/* ===================================================================
+ * In order to enable if-conversion in WOPT, tranform:
+ *
+ * From:
+ * if (a && b) {
+ * x = ...
+ * }
+ * else {
+ * <empty>
+ * }
+ *
+ * To:
+ * if (a) {
+ * if (b) {
+ * x = ...
+ * }
+ * else {
+ * <empty>
+ * }
+ * }
+ * else {
+ * <empty>
+ * }
+ * ==================================================================
+ */
+static void lower_split_single_cand(WN * tree, LOWER_ACTIONS actions)
+{
+ FmtAssert(WN_operator(tree) == OPR_IF, ("Expect a if-condition"));
+
+ if (WN_block_nonempty(WN_then(tree)) &&
+ !WN_block_nonempty(WN_else(tree)) &&
+ tree_has_only_one_cand(WN_if_test(tree)) &&
+ WN_is_assign(WN_then(tree)))
+ {
+ WN *outer_then = WN_then(tree);
+ INT64 if_line = WN_Get_Linenum(tree);
+ INT64 then_line = WN_Get_Linenum(WN_then(tree));
+ INT64 else_line = WN_Get_Linenum(WN_else(tree));
+ WN *outer_cond = lower_copy_tree(WN_kid0(WN_if_test(tree)), actions);
+ WN *inner_cond = lower_copy_tree(WN_kid1(WN_if_test(tree)), actions);
+ WN_DELETE_Tree(WN_if_test(tree));
+ WN_if_test(tree) = outer_cond;
+ WN *inner_then_block = WN_CreateBlock();
+ WN_Set_Linenum(inner_then_block, if_line);
+ WN *inner_else_block = WN_CreateBlock();
+ WN_Set_Linenum(inner_else_block, else_line);
+ WN *inner_if = WN_CreateIf(inner_cond, inner_then_block, inner_else_block);
+ WN_Set_Linenum(inner_if, if_line);
+ WN * wn_next;
+ // Move statements from outer-then clause to new inner-then clause.
+ for (WN * wn_tmp = WN_first(outer_then); wn_tmp; wn_tmp = wn_next)
+ {
+ wn_next = WN_next(wn_tmp);
+ WN_INSERT_BlockLast(inner_then_block, lower_copy_tree(wn_tmp, actions));
+ WN_DELETE_FromBlock(outer_then, wn_tmp);
+ }
+ WN_INSERT_BlockLast(outer_then, inner_if);
+ if (Cur_PU_Feedback)
+ {
+ Cur_PU_Feedback->FB_split_cand_if( tree, inner_if );
+ }
+ }
+}
+
/* ====================================================================
*
* WN *lower_if(WN *block, WN *tree, LOWER_ACTIONS actions, WN ** ret_next)
@@ -13739,7 +13830,17 @@
lower_simp_if_flip(tree, actions, ret_next);
lower_simp_bit_and(tree, actions);
}
-
+
+ // Check for special case, to enable more if-conversion. Do not check if:
+ // - disabled (OPT_Lower_Splitsinglecand == 0)
+ // or
+ // - if-conversion not enabled (WOPT_Enable_Simple_If_Conv < 1)
+ if (Action(LOWER_SHORTCIRCUIT) &&
+ OPT_Lower_Splitsinglecand && WOPT_Enable_Simple_If_Conv >= 1)
+ {
+ lower_split_single_cand(tree, actions);
+ }
+
#ifndef SHORTCIRCUIT_HACK
if (Action(LOWER_IF))
#else
Modified: trunk/osprey/be/opt/opt_cfg.cxx
===================================================================
--- trunk/osprey/be/opt/opt_cfg.cxx 2011-07-18 20:10:34 UTC (rev 3696)
+++ trunk/osprey/be/opt/opt_cfg.cxx 2011-07-18 23:22:29 UTC (rev 3697)
@@ -1602,28 +1602,6 @@
return FALSE;
}
-BOOL CFG::wn_is_assign(WN *wn)
-{
- WN *wn_first = WN_first(wn);
- WN *wn_last = WN_last(wn);
- return ((wn_first && (wn_first == wn_last) &&
OPERATOR_is_store(WN_operator(wn_first)))
- || WN_operator(wn) == OPR_SELECT);
-}
-
-BOOL CFG::wn_is_assign_return(WN *wn)
-{
- WN *wn_first = WN_first(wn);
- WN *wn_last = WN_last(wn);
-
- if (wn_last) {
- WN *wn_last_prev = WN_prev(WN_last(wn));
- return ((WN_operator(wn_last) == OPR_RETURN)
- && (wn_first == wn_last_prev) &&
OPERATOR_is_store(WN_operator(wn_first)));
- } else {
- return FALSE;
- }
-}
-
BOOL CFG::Cand_is_return_inside_select(WN *wn)
{
FmtAssert(WN_operator(wn) == OPR_IF, ("Extract_Return: Unexpected WN"));
@@ -1654,12 +1632,12 @@
return FALSE;
/* then is not empty and not assign-return, return FALSE */
- if (then_wn_prev && !wn_is_assign_return(then_wn)) {
+ if (then_wn_prev && !WN_is_assign_return(then_wn)) {
return FALSE;
}
/* then is not empty and not assign-return, return FALSE */
- if (else_wn_prev && !wn_is_assign_return(else_wn)) {
+ if (else_wn_prev && !WN_is_assign_return(else_wn)) {
return FALSE;
}
@@ -1720,11 +1698,11 @@
return FALSE;
// either the else-stmt is empty or has one assignment
- if (!empty_else && !(wn_is_assign(else_wn)))
+ if (!empty_else && !(WN_is_assign(else_wn)))
return FALSE;
// either the then-stmt is empty or has one assignment
- if (!empty_then && !wn_is_assign(then_wn))
+ if (!empty_then && !WN_is_assign(then_wn))
return FALSE;
// both the then and else are empty or has one assignment with same lhs
Modified: trunk/osprey/be/opt/opt_cfg.h
===================================================================
--- trunk/osprey/be/opt/opt_cfg.h 2011-07-18 20:10:34 UTC (rev 3696)
+++ trunk/osprey/be/opt/opt_cfg.h 2011-07-18 23:22:29 UTC (rev 3697)
@@ -378,8 +378,6 @@
INT Is_simple_expr(WN *wn);
void Lower_if_stmt(WN *wn, END_BLOCK *ends_bb );
WN *if_convert(WN *wn);
- BOOL wn_is_assign(WN *wn);
- BOOL wn_is_assign_return(WN *wn);
BOOL wn_is_return_convert(WN *wn);
// add various high-level construct statements to CFG so they can
// later be raised back up (mostly preopt phase)
Modified: trunk/osprey/common/com/config.h
===================================================================
--- trunk/osprey/common/com/config.h 2011-07-18 20:10:34 UTC (rev 3696)
+++ trunk/osprey/common/com/config.h 2011-07-18 23:22:29 UTC (rev 3697)
@@ -1,5 +1,5 @@
/*
- * Copyright (C) 2008-2010 Advanced Micro Devices, Inc. All Rights Reserved.
+ * Copyright (C) 2008-2011 Advanced Micro Devices, Inc. All Rights Reserved.
*/
/*
@@ -583,6 +583,7 @@
extern BOOL OPT_unroll_times_overridden;
extern INT32 OPT_unroll_size;
extern BOOL OPT_unroll_size_overridden;
+extern BOOL OPT_Lower_Splitsinglecand;
extern BOOL OPT_Lower_Speculate;
extern BOOL OPT_Lower_Treeheight;
extern BOOL OPT_Inline_Divide;
Modified: trunk/osprey/common/com/config_opt.cxx
===================================================================
--- trunk/osprey/common/com/config_opt.cxx 2011-07-18 20:10:34 UTC (rev
3696)
+++ trunk/osprey/common/com/config_opt.cxx 2011-07-18 23:22:29 UTC (rev
3697)
@@ -228,6 +228,8 @@
BOOL OPT_Reorg_Common_Set = FALSE; /* ... option seen? */
BOOL OPT_Unroll_Analysis = TRUE; /* Enable unroll limitations? */
BOOL OPT_Unroll_Analysis_Set = FALSE; /* ... option seen? */
+BOOL OPT_Lower_Splitsinglecand = TRUE;
+BOOL OPT_Lower_Splitsinglecand_Set = FALSE;
#if defined(TARG_NVISA)
BOOL OPT_Lower_Speculate = TRUE; /* speculate CAND/CIOR */
#else
@@ -720,6 +722,10 @@
0, 0, 0, &OPT_Space, NULL,
"Bias optimizations to minimize code space" },
+ { OVK_BOOL, OV_INTERNAL, TRUE, "split_single_cand", "",
+ 0, 0, 0, &OPT_Lower_Splitsinglecand, &OPT_Lower_Splitsinglecand_Set,
+ "Allow splitting of single CAND for enabling if_conversion" },
+
{ OVK_BOOL, OV_INTERNAL, TRUE, "speculate", "",
0, 0, 0, &OPT_Lower_Speculate, &OPT_Lower_Speculate_Set,
"Allow speculation for CAND/COR operators" },
Modified: trunk/osprey/common/com/fb_freq.h
===================================================================
--- trunk/osprey/common/com/fb_freq.h 2011-07-18 20:10:34 UTC (rev 3696)
+++ trunk/osprey/common/com/fb_freq.h 2011-07-18 23:22:29 UTC (rev 3697)
@@ -97,6 +97,7 @@
#ifndef fb_freq_INCLUDED
#define fb_freq_INCLUDED
+#include <math.h>
#include "defs.h"
#ifndef ERRORS_INCLUDED
#include "errors.h"
@@ -310,6 +311,17 @@
return FB_FREQ_TYPE_BETTER( _type, freq._type );
}
+ FB_FREQ sqrt() {
+ if ( Zero() && Exact() )
+ return FB_FREQ( FB_FREQ_TYPE_EXACT, 0.0 );
+ FB_FREQ_TYPE type = FB_FREQ_TYPE_COMBINE( _type, FB_FREQ_TYPE_GUESS );
+ if ( FB_FREQ_TYPE_NOT_KNOWN( type ) )
+ return FB_FREQ( type );
+ Is_True( _value >= 0, ( "FB_FREQ: negative value %ld", _value ) );
+ return FB_FREQ( type, ::sqrt((double)_value) );
+ return *this;
+ }
+
// Operators
FB_FREQ operator+= ( const FB_FREQ freq ) {
Modified: trunk/osprey/common/com/wn.cxx
===================================================================
--- trunk/osprey/common/com/wn.cxx 2011-07-18 20:10:34 UTC (rev 3696)
+++ trunk/osprey/common/com/wn.cxx 2011-07-18 23:22:29 UTC (rev 3697)
@@ -3753,3 +3753,27 @@
return NULL;
}
+
+BOOL
+WN_is_assign(WN * wn)
+{
+ WN *wn_first = WN_first(wn);
+ WN *wn_last = WN_last(wn);
+ return ((wn_first && (wn_first == wn_last) &&
OPERATOR_is_store(WN_operator(wn_first)))
+ || WN_operator(wn) == OPR_SELECT);
+}
+
+BOOL
+WN_is_assign_return(WN * wn)
+{
+ WN *wn_first = WN_first(wn);
+ WN *wn_last = WN_last(wn);
+
+ if (wn_last) {
+ WN *wn_last_prev = WN_prev(WN_last(wn));
+ return ((WN_operator(wn_last) == OPR_RETURN)
+ && (wn_first == wn_last_prev) &&
OPERATOR_is_store(WN_operator(wn_first)));
+ } else {
+ return FALSE;
+ }
+}
Modified: trunk/osprey/common/com/wn.h
===================================================================
--- trunk/osprey/common/com/wn.h 2011-07-18 20:10:34 UTC (rev 3696)
+++ trunk/osprey/common/com/wn.h 2011-07-18 23:22:29 UTC (rev 3697)
@@ -1546,7 +1546,9 @@
extern BOOL WN_has_const_diff(WN *, WN *, int *);
extern BOOL WN_has_compatible_iter_space(WN *, WN *, int *, int *, BOOL);
-
+extern BOOL WN_is_assign(WN *);
+extern BOOL WN_is_assign_return(WN *);
+
#if defined(TARG_SL)
extern WN* WN_CreateFork(INT32 label_number, BOOL major);
extern BOOL WN_Intrinsic_OP_Slave(WN * wn);
------------------------------------------------------------------------------
Storage Efficiency Calculator
This modeling tool is based on patent-pending intellectual property that
has been used successfully in hundreds of IBM storage optimization engage-
ments, worldwide. Store less, Store more with what you own, Move data to
the right place. Try It Now! http://www.accelacomm.com/jaw/sfnl/114/51427378/
_______________________________________________
Open64-devel mailing list
[email protected]
https://lists.sourceforge.net/lists/listinfo/open64-devel
