I did not receive any feedback on this patch. Did anyone get a chance
to review it?
On Tue, Jun 21, 2011 at 2:25 PM, David Coakley <dcoak...@gmail.com> wrote:
> The attached patch is a minor revision to a patch that I posted a few
> weeks ago. The code in lower_if() was modified to make it more clear
> when the transformation is applied:
>
> if (Action(LOWER_SHORTCIRCUIT) &&
> OPT_Lower_Splitsinglecand && WOPT_Enable_Simple_If_Conv >= 1)
> {
> lower_split_single_cand(tree, actions);
> }
>
> I have added more detail to the description in an attempt to address
> some questions raised by the earlier patch:
>
> Convert:
> if (a && b)
> x = ...
> To:
> if (a)
> if (b)
> x = ...
> To enable more if-conversion.
>
> 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.
>
>
> Sun and others, please let me know if it looks ok.
>
> -David Coakley / AMD Open Source Compiler Engineering
>
Index: osprey/be/com/fb_whirl.h
===================================================================
--- osprey/be/com/fb_whirl.h (revision 3660)
+++ osprey/be/com/fb_whirl.h (working copy)
@@ -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,
Index: osprey/be/com/wn_lower.cxx
===================================================================
--- osprey/be/com/wn_lower.cxx (revision 3660)
+++ osprey/be/com/wn_lower.cxx (working copy)
@@ -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>
@@ -13689,6 +13690,112 @@
}
#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);
+}
+
+/* Very similar to CFG::wn_is_assign from opt_cfg.cxx.
+ * See if wn is a single assignment, since this is the condition under
+ * which WOPT will perform if_conversion.
+ * Ideally, this code would not have to be duplicated, but it seems
+ * difficult to re-structure WOPT to create a single helper function.
+ * If these functions get out of synch, it's only a performance issue - not
+ * a correctness issue.
+ */
+static 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)));
+}
+
+/* ===================================================================
+ * 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)
@@ -13734,7 +13841,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
Index: osprey/be/com/fb_whirl.cxx
===================================================================
--- osprey/be/com/fb_whirl.cxx (revision 3660)
+++ osprey/be/com/fb_whirl.cxx (working copy)
@@ -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.
Index: osprey/common/com/fb_freq.h
===================================================================
--- osprey/common/com/fb_freq.h (revision 3660)
+++ osprey/common/com/fb_freq.h (working copy)
@@ -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 ) {
Index: osprey/common/com/config_opt.cxx
===================================================================
--- osprey/common/com/config_opt.cxx (revision 3660)
+++ osprey/common/com/config_opt.cxx (working copy)
@@ -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.
*/
/*
@@ -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
@@ -715,6 +717,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" },
Index: osprey/common/com/config.h
===================================================================
--- osprey/common/com/config.h (revision 3660)
+++ osprey/common/com/config.h (working copy)
@@ -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;
------------------------------------------------------------------------------
All of the data generated in your IT infrastructure is seriously valuable.
Why? It contains a definitive record of application performance, security
threats, fraudulent activity, and more. Splunk takes this data and makes
sense of it. IT sense. And common sense.
http://p.sf.net/sfu/splunk-d2d-c2
_______________________________________________
Open64-devel mailing list
Open64-devel@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/open64-devel
