Author: meiye
Date: 2011-05-23 13:14:34 -0400 (Mon, 23 May 2011)
New Revision: 3615
Modified:
trunk/osprey/be/opt/opt_cfg.cxx
trunk/osprey/be/opt/opt_cfg.h
trunk/osprey/be/opt/opt_proactive.cxx
trunk/osprey/be/opt/opt_wn.cxx
Log:
Add conditional expression to check runtime values to remove conversions to
enable if-merging which leads to more loop fusion opportunites. Also add codes
to evaluate multiply operations. CR: Sun Chan
Modified: trunk/osprey/be/opt/opt_cfg.cxx
===================================================================
--- trunk/osprey/be/opt/opt_cfg.cxx 2011-05-20 21:21:26 UTC (rev 3614)
+++ trunk/osprey/be/opt/opt_cfg.cxx 2011-05-23 17:14:34 UTC (rev 3615)
@@ -6548,6 +6548,93 @@
return sc_new;
}
+// Insert a SC_IF before 'sc_insert', 'bb_head' is the new SC_IF's head.
+SC_NODE *
+CFG::Insert_if_before(SC_NODE * sc_insert, BB_NODE * bb_head)
+{
+ SC_NODE * sc_prev = sc_insert->Prev_sibling();
+ BB_NODE * bb_then = Create_and_allocate_bb(BB_GOTO);
+ BB_NODE * bb_else = Create_and_allocate_bb(BB_GOTO);
+ BB_NODE * bb_merge = sc_insert->First_bb();
+
+ bb_head->Append_succ(bb_else, _mem_pool);
+ bb_head->Append_succ(bb_then, _mem_pool);
+ bb_then->Append_pred(bb_head, _mem_pool);
+ bb_else->Append_pred(bb_head, _mem_pool);
+ bb_then->Append_succ(bb_merge, _mem_pool);
+ bb_else->Append_succ(bb_merge, _mem_pool);
+
+ BB_NODE * bb_tmp;
+ BB_LIST_ITER bb_list_iter;
+ FOR_ALL_ELEM(bb_tmp, bb_list_iter, Init(bb_merge->Pred())) {
+ bb_tmp->Replace_succ(bb_merge, bb_head);
+ if (bb_tmp->Is_branch_to(bb_merge)) {
+ WN * branch_wn = bb_tmp->Branch_wn();
+ Add_label_with_wn(bb_head);
+ WN_label_number(branch_wn) = bb_head->Labnam();
+ }
+ if (Feedback())
+ Feedback()->Move_edge_dest(bb_tmp->Id(), bb_merge->Id(), bb_head->Id());
+ }
+
+ bb_head->Set_pred(bb_merge->Pred());
+ bb_merge->Set_pred(NULL);
+ bb_merge->Append_pred(bb_then, _mem_pool);
+ bb_merge->Append_pred(bb_else, _mem_pool);
+
+ bb_tmp = bb_merge->Prev();
+ if (bb_tmp) {
+ bb_tmp->Set_next(bb_head);
+ bb_head->Set_prev(bb_tmp);
+ }
+
+ bb_head->Set_next(bb_then);
+ bb_then->Set_prev(bb_head);
+ bb_then->Set_next(bb_else);
+ bb_else->Set_prev(bb_then);
+ bb_else->Set_next(bb_merge);
+ bb_merge->Set_prev(bb_else);
+
+ Add_label_with_wn(bb_else);
+ WN * wn_tmp = bb_head->Branch_wn();
+ WN_label_number(wn_tmp) = bb_else->Labnam();
+
+ SC_NODE * sc_if = Create_sc(SC_IF);
+ SC_NODE * sc_then = Create_sc(SC_THEN);
+ SC_NODE * sc_else = Create_sc(SC_ELSE);
+ SC_NODE * sc_b1 = Create_sc(SC_BLOCK);
+ SC_NODE * sc_b2 = Create_sc(SC_BLOCK);
+
+ sc_if->Set_bb_rep(bb_head);
+ sc_b1->Append_bbs(bb_then);
+ sc_b2->Append_bbs(bb_else);
+
+ BB_IFINFO * ifinfo = bb_head->Ifinfo();
+ ifinfo->Set_cond(bb_head);
+ ifinfo->Set_merge(bb_merge);
+ ifinfo->Set_then(bb_then);
+ ifinfo->Set_else(bb_else);
+
+ sc_if->Append_kid(sc_then);
+ sc_if->Append_kid(sc_else);
+ sc_then->Set_parent(sc_if);
+ sc_else->Set_parent(sc_if);
+ sc_then->Append_kid(sc_b1);
+ sc_else->Append_kid(sc_b2);
+ sc_b1->Set_parent(sc_then);
+ sc_b2->Set_parent(sc_else);
+
+ sc_insert->Insert_before(sc_if);
+
+ if (sc_prev)
+ Fix_info(sc_prev);
+
+ Fix_info(sc_insert->Get_real_parent());
+ Invalidate_and_update_aux_info(FALSE);
+ Invalidate_loops();
+ return sc_if;
+}
+
// Obtained cloned equivalent of given bb
BB_NODE *
CFG::Get_cloned_bb(BB_NODE * bb)
Modified: trunk/osprey/be/opt/opt_cfg.h
===================================================================
--- trunk/osprey/be/opt/opt_cfg.h 2011-05-20 21:21:26 UTC (rev 3614)
+++ trunk/osprey/be/opt/opt_cfg.h 2011-05-23 17:14:34 UTC (rev 3615)
@@ -744,6 +744,7 @@
SC_NODE * Split(SC_NODE *);
SC_NODE * Insert_block_after(SC_NODE *);
SC_NODE * Insert_block_before(SC_NODE *);
+ SC_NODE * Insert_if_before(SC_NODE *, BB_NODE *);
void Fix_info(SC_NODE *);
// Create a new block and allocate it.
Modified: trunk/osprey/be/opt/opt_proactive.cxx
===================================================================
--- trunk/osprey/be/opt/opt_proactive.cxx 2011-05-20 21:21:26 UTC (rev
3614)
+++ trunk/osprey/be/opt/opt_proactive.cxx 2011-05-23 17:14:34 UTC (rev
3615)
@@ -10742,6 +10742,7 @@
*cand1 = NULL;
*cand2 = NULL;
+ CFG * cfg = Get_cu()->Cfg();
SC_LIST_ITER kids_iter;
SC_NODE * tmp;
@@ -10776,6 +10777,92 @@
Set_pass(s_pass);
return tmp;
}
+ else {
+ WN * cond1 = prev->Get_cond();
+ WN * cond2 = next->Get_cond();
+ if ((WN_operator(cond1) == WN_operator(cond2))
+ && (WN_kid_count(cond1) == 2)
+ && (WN_Simp_Compare_Trees(WN_kid1(cond1), WN_kid1(cond2)) == 0)
+ && ((WN_operator(cond1) == OPR_NE) || (WN_operator(cond1) ==
OPR_EQ))
+ && (WN_operator(WN_kid1(cond1)) == OPR_INTCONST)
+ && (WN_const_val(WN_kid1(cond1)) == 0)) {
+ cond1 = WN_kid0(cond1);
+ cond2 = WN_kid0(cond2);
+ // match patterns like: "(a bitop (1 << cnt)) == 0" or
+ // "(a bitop (1 << cnt)) != 0",
+ // where 'a' is a 4-byte, one of 'cond1' and 'cond2' is a 8 byte, and
+ // the other one is a 4-byte.
+ if ((WN_operator(cond1) == WN_operator(cond2))
+ && WN_is_bit_op(cond1)) {
+ SC_NODE * sc_l = NULL;
+ SC_NODE * sc_s = NULL;
+
+ if (MTYPE_byte_size(WN_rtype(cond1)) == 8)
+ sc_l = prev;
+ else if (MTYPE_byte_size(WN_rtype(cond2)) == 8)
+ sc_l = next;
+
+ if (MTYPE_byte_size(WN_rtype(cond1)) == 4)
+ sc_s = prev;
+ else if (MTYPE_byte_size(WN_rtype(cond2)) == 4)
+ sc_s = next;
+
+ if (sc_l && sc_s) {
+ WN * op1 = WN_kid0(cond1);
+ WN * op2 = WN_kid0(cond2);
+ op1 = (WN_operator(op1) == OPR_CVT) ? WN_kid0(op1) : op1;
+ op2 = (WN_operator(op2) == OPR_CVT) ? WN_kid0(op2) : op2;
+ if ((WN_Simp_Compare_Trees(op1, op2) == 0)
+ && (MTYPE_byte_size(WN_desc(op1)) == 4)) {
+ op1 = WN_kid1(cond1);
+ op2 = WN_kid1(cond2);
+ if (WN_is_power_of_2(op1) && WN_is_power_of_2(op2)
+ && (WN_operator(op1) == OPR_SHL)) {
+ op1 = WN_get_bit_from_expr(op1);
+ op2 = WN_get_bit_from_expr(op2);
+ // Create a new SC_IF with comparision expression "if (cnt <
32)"
+ // and wrap it around 'prev' and 'next'.
+ if (op1 && op2 && (WN_Simp_Compare_Trees(op1, op2) == 0)
+ && !Has_dependency(prev, op1)
+ && !Has_dependency(next, op2)) {
+ for (int i = 0; i < 2; i++) {
+ // Create a comparison expression 'if (cnt < 32)'.
+ WN * wn_tmp = WN_COPY_Tree_With_Map((i == 0) ? op1 : op2);
+ wn_tmp = WN_CreateExp2(OPR_LT, MTYPE_I4, MTYPE_I4, wn_tmp,
+ WN_CreateIntconst(OPR_INTCONST,
MTYPE_I4, MTYPE_V, 32));
+ // Create a CFG block to host 'wn_tmp'.
+ BB_NODE * bb_new = NULL;
+ SC_NODE * sc_cur = ( i == 0) ? prev : next;
+ cfg->Clone_bbs(sc_cur->Head(), sc_cur->Head(), &bb_new,
&bb_new, TRUE, 1.0);
+ WN * wn_branch = bb_new->Laststmt();
+ WN_kid0(wn_branch) = wn_tmp;
+ // Insert a new if-region before 'prev'.
+ SC_NODE * sc_tmp = cfg->Insert_if_before(sc_cur, bb_new);
+ Do_tail_duplication(sc_cur, sc_tmp);
+ if (i == 0)
+ *cand1 = sc_tmp;
+ else
+ *cand2 = sc_tmp;
+
+ if (sc_cur == sc_l) {
+ sc_tmp = sc_tmp->Find_kid_of_type(SC_THEN);
+ sc_tmp = sc_tmp->Find_kid_of_type(SC_IF);
+ FmtAssert(sc_tmp, ("Expect a SC_IF"));
+ WN * branch_l = sc_tmp->Head()->Branch_wn();
+ WN * branch_s = sc_s->Head()->Branch_wn();
+ WN_kid0(branch_l) =
WN_COPY_Tree_With_Map(WN_kid0(branch_s));
+ }
+ }
+ Set_pass(s_pass);
+ return tmp;
+ }
+ }
+ }
+ }
+ }
+ }
+ }
+
Set_pass(s_pass);
break;
case SC_LOOP:
@@ -11655,14 +11742,33 @@
WN * op1 = WN_kid0(wn_tmp);
WN * op2 = WN_kid1(wn_tmp);
int val;
- if ((WN_operator(op2) == OPR_INTCONST)
- && (OPERATOR_is_scalar_load(WN_operator(op1)))
- && Is_invariant(sc_loop, op1, 0)
- ) {
- val = WN_const_val(op2);
+ WN * wn_tmp;
+ if (WN_operator(op2) == OPR_INTCONST) {
+ val = WN_const_val(op2);
if (opr == OPR_ADD)
val = val * -1;
- Set_lo(_low_map, op1, val);
+ if (Is_invariant(sc_loop, op1, 0)) {
+ opr = WN_operator(op1);
+ switch (opr) {
+ case OPR_LDID:
+ Set_lo(_low_map, op1, val);
+ break;
+ case OPR_MPY:
+ wn_tmp = WN_kid1(op1);
+ if ((WN_operator(wn_tmp) == OPR_INTCONST)
+ && (val > 0)
+ && (val < WN_const_val(wn_tmp))) {
+ // From pattern: c1 * x >= c2, where c1 > 0, c2 > 0 and c1 > c2,
+ // we can infer that x >= 1.
+ wn_tmp = WN_kid0(op1);
+ if (WN_operator(wn_tmp) == OPR_LDID)
+ Set_lo(_low_map, wn_tmp, 1);
+ }
+ break;
+ default:
+ ;
+ }
+ }
}
}
else if (OPERATOR_is_scalar_load(opr)
@@ -11743,6 +11849,7 @@
_low_map = WN_MAP_Create(_pool);
_high_map = WN_MAP_Create(_pool);
_def_wn_map = CXX_NEW(MAP(CFG_BB_TAB_SIZE, _pool), _pool);
+ SC_NODE * nesting_lp = NULL;
while (sc_lcp) {
SC_TYPE type = sc_lcp->Type();
@@ -11769,9 +11876,15 @@
&& sc_lcp->Is_pred_in_tree(_current_scope)) {
Infer_lp_bound_val(_current_scope);
}
+ nesting_lp = sc_lcp;
}
sc_lcp = sc_lcp->Parent();
}
+
+ if (nesting_lp) {
+ WN * wn_cond = sc1->Get_cond();
+ Infer_shift_count_val(wn_cond, nesting_lp);
+ }
}
}
Modified: trunk/osprey/be/opt/opt_wn.cxx
===================================================================
--- trunk/osprey/be/opt/opt_wn.cxx 2011-05-20 21:21:26 UTC (rev 3614)
+++ trunk/osprey/be/opt/opt_wn.cxx 2011-05-23 17:14:34 UTC (rev 3615)
@@ -1801,6 +1801,8 @@
{
int val1, val2;
OPERATOR opr = WN_operator(wn);
+ WN * op1;
+ WN * op2;
if (opr == OPR_INTCONST) {
*val = WN_const_val(wn);
@@ -1820,7 +1822,24 @@
return TRUE;
}
break;
+ case OPR_MPY:
+ op1 = WN_kid(wn, 0);
+ op2 = WN_kid(wn, 1);
+ if (WN_get_val(op1, &val1, wn_map)
+ && WN_get_val(op2, &val2, wn_map)
+ && (val1 > 0)
+ && (val2 > 0)
+ && ((WN_operator(op1) == OPR_INTCONST)
+ || (WN_operator(op2) == OPR_INTCONST))) {
+ // Note that we evaluate "c0 * b" based on ""b <= c1"
+ // Or "b >= c2", where c0, c1, c2 are constants.
+ // The inferred value can be incorrect if either "c0",
+ // "c1" or "c2" is non-positive.
+ *val = val1 * val2;
+ return TRUE;
+ }
+ break;
default:
;
}
------------------------------------------------------------------------------
What Every C/C++ and Fortran developer Should Know!
Read this article and learn how Intel has extended the reach of its
next-generation tools to help Windows* and Linux* C/C++ and Fortran
developers boost performance applications - including clusters.
http://p.sf.net/sfu/intel-dev2devmay
_______________________________________________
Open64-devel mailing list
Open64-devel@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/open64-devel
