Could a gatekeeper please review the attached change that enables more
if-conversion?
Here is the proposed log message:
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). No if-conversion code was touched -
only lowering code.
I have also attached a small test program that demonstrates when the
transformation occurs. Thanks,
-David Coakley / AMD Open Source Compiler Engineering
Index: osprey/be/com/fb_whirl.h
===================================================================
--- osprey/be/com/fb_whirl.h (revision 3639)
+++ 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 3639)
+++ 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>
@@ -13613,6 +13614,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)
@@ -13658,7 +13765,18 @@
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
+ // (Opt_Level < 2 || WOPT_Enable_Simple_If_Conv < 1)
+ if (Opt_Level >= 2 &&
+ 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 3639)
+++ 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 3639)
+++ 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 3639)
+++ 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 3639)
+++ 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;
/* regular if-conversion should occur */
int
sub1 (int x)
{
int z = 10;
if (x != 13) {
z -= 5;
}
return z;
}
/* if-conversion should occur, given new optimization */
int
sub2and (int x, int y)
{
int z = 10;
if (x != 28 && y != 29) {
z -= 3;
}
return z;
}
/* regular if-conversion should occur - there are 2 moves in if condition */
int
sub2move (int x)
{
int z = 10;
int y = 20;
if (x != 13) {
z -= 5;
y -=6;
}
return z+y;
}
/* optimization should not kick in - there are 2 moves in if condition */
int
sub2andmove (int x, int y)
{
int z = 10;
int z1 = 20;
if (x != 28 && y != 29) {
z -= 3;
z1 -= 6;
}
return z+z1;
}
/* regular if-conversion should occur, the nested if is explicit in
the source */
int
sub2nest (int x, int y)
{
int z = 10;
if (x != 28) {
if (y != 29) {
z -= 3;
}
}
return z;
}
/* optimization should not kick in, because of the ! outside the && */
int
sub2andnot (int x, int y)
{
int z = 10;
if (!(x == 28 && y == 29)) {
z -= 3;
}
return z;
}
/* optimization should not kick in, because of nested condition */
int
sub2and3nest (int x, int y, int a)
{
int z = 10;
if (x == 28 && (y == 29 || a == 30)) {
z -= 3;
}
return z;
}
/* optimization should not kick in, because of 2 && */
int
sub3and (int x, int y, int a)
{
int z = 10;
if (x == 28 && y == 29 && a == 30) {
z -= 3;
}
return z;
}
/* optimization should not kick in, else block not empty */
int
sub2andelse (int x, int y)
{
int z = 10;
if (x != 28 && y != 29) {
z -= 3;
}
else {
z -= 6;
}
return z;
}
#include <stdio.h>
extern int sub1(int x);
extern int sub2and(int x, int y);
extern int sub2move(int x);
extern int sub2andmove(int x, int y);
extern int sub2nest(int x, int y);
extern int sub2andnot(int x, int y);
extern int sub2and3nest(int x, int y, int a);
extern int sub3and(int x, int y, int a);
extern int sub2andelse(int x, int y);
main ()
{
if (sub1(10) != 5)
printf("Error in sub1\n");
if (sub2and(10, 11) != 7)
printf("Error in sub2and\n");
if (sub2move(10) != 19)
printf("Error in sub2move\n");
if (sub2andmove(10, 21) != 21)
printf("Error in sub2andmove\n");
if (sub2nest(10, 11) != 7)
printf("Error in sub2nest\n");
if (sub2andnot(10, 11) != 7)
printf("Error in sub2andnot\n");
if (sub2and3nest(28, 29, 1) != 7)
printf("Error in sub2and3nest\n");
if (sub3and(28, 29, 30) != 7)
printf("Error in sub3and\n");
if (sub2andelse(10, 11) != 7)
printf("Error in sub2andelse\n");
}
------------------------------------------------------------------------------
Simplify data backup and recovery for your virtual environment with vRanger.
Installation's a snap, and flexible recovery options mean your data is safe,
secure and there when you need it. Discover what all the cheering's about.
Get your free trial download today.
http://p.sf.net/sfu/quest-dev2dev2
_______________________________________________
Open64-devel mailing list
[email protected]
https://lists.sourceforge.net/lists/listinfo/open64-devel
