Author: meiye
Date: 2012-02-01 15:15:09 -0500 (Wed, 01 Feb 2012)
New Revision: 3865
Modified:
trunk/osprey/be/opt/opt_bb.cxx
trunk/osprey/be/opt/opt_proactive.cxx
trunk/osprey/be/opt/opt_proactive.h
trunk/osprey/be/opt/opt_wn.cxx
trunk/osprey/be/vho/vho_lower.cxx
trunk/osprey/common/com/wn.cxx
trunk/osprey/common/com/wn.h
Log:
Allow tail duplication of SC_Ifs to enable more if-merging. Enhance
extended-proactive-loop-opt phase to remove more bit-operations and if-regions.
Minor code-reorg for code sharing. CR:Michael Lai
Modified: trunk/osprey/be/opt/opt_bb.cxx
===================================================================
--- trunk/osprey/be/opt/opt_bb.cxx 2012-01-30 13:30:05 UTC (rev 3864)
+++ trunk/osprey/be/opt/opt_bb.cxx 2012-02-01 20:15:09 UTC (rev 3865)
@@ -1640,6 +1640,9 @@
WN * stmt1 = Firststmt();
WN * stmt2 = bb->Firststmt();
+ if (!stmt1 || !stmt2)
+ return FALSE;
+
while (stmt1 && stmt2) {
OPERATOR opr = WN_operator(stmt1);
@@ -1650,10 +1653,15 @@
if (WN_Simp_Compare_Trees(WN_kid0(stmt1), WN_kid0(stmt2)) != 0)
return FALSE;
}
- else if ((opr != OPR_LABEL) && (opr != OPR_PRAGMA)
- && WN_Simp_Compare_Trees(stmt1, stmt2) != 0)
- return FALSE;
-
+ else if ((opr != OPR_LABEL) && (opr != OPR_PRAGMA)) {
+ if (OPERATOR_is_store(opr)) {
+ if (!Identical_stmt(stmt1, stmt2))
+ return FALSE;
+ }
+ else if (WN_Simp_Compare_Trees(stmt1, stmt2) != 0)
+ return FALSE;
+ }
+
stmt1 = WN_next(stmt1);
stmt2 = WN_next(stmt2);
}
Modified: trunk/osprey/be/opt/opt_proactive.cxx
===================================================================
--- trunk/osprey/be/opt/opt_proactive.cxx 2012-01-30 13:30:05 UTC (rev
3864)
+++ trunk/osprey/be/opt/opt_proactive.cxx 2012-02-01 20:15:09 UTC (rev
3865)
@@ -214,6 +214,19 @@
}
+// Find the first kid that contains an executable block.
+SC_NODE *
+SC_NODE:: First_executable_kid()
+{
+ SC_LIST_ITER iter;
+ SC_NODE * tmp;
+ FOR_ALL_ELEM(tmp, iter, Init(kids)) {
+ if (tmp->First_executable_blk() != NULL)
+ return tmp;
+ }
+ return NULL;
+}
+
// Return next sibling SC_NODE from the same parent.
SC_NODE *
@@ -237,6 +250,19 @@
return NULL;
}
+// Return next executable sibling.
+SC_NODE *
+SC_NODE::Next_executable_sibling()
+{
+ SC_NODE * sc_iter = Next_sibling();
+ while (sc_iter) {
+ if (sc_iter->First_executable_blk() != NULL)
+ return sc_iter;
+ sc_iter = sc_iter->Next_sibling();
+ }
+ return NULL;
+}
+
// Return next SC_NODE in the SC tree that immediately succeeds this SC_NODE
in source order.
SC_NODE *
SC_NODE::Next_in_tree()
@@ -315,6 +341,24 @@
return std::pair<SC_NODE *, int> (sc_out, count);
}
+// Get outermost nesting SC_LOOP and number of nesting loops.
+std::pair<SC_NODE *, int>
+SC_NODE::Get_outermost_nesting_loop()
+{
+ SC_NODE * sc_tmp = Parent();
+ SC_NODE * outer_loop = NULL;
+ int nest_level = 0;
+ while (sc_tmp) {
+ if (sc_tmp->Type() == SC_LOOP) {
+ nest_level++;
+ outer_loop = sc_tmp;
+ }
+ sc_tmp = sc_tmp->Parent();
+ }
+
+ return std::pair<SC_NODE *, int> (outer_loop, nest_level);
+}
+
// Return closest next sibling SC_NODE of the given type
SC_NODE *
SC_NODE::Next_sibling_of_type(SC_TYPE match_type)
@@ -471,6 +515,35 @@
return NULL;
}
+// Return the first real statement's containing block in this SC_NODE.
+
+BB_NODE *
+SC_NODE::First_executable_blk()
+{
+ BB_NODE * bb_tmp = Get_bb_rep();
+ if (bb_tmp && (bb_tmp->First_executable_stmt() != NULL))
+ return bb_tmp;
+
+ BB_LIST * bb_list = Get_bbs();
+ if (bb_list) {
+ BB_LIST_ITER bb_list_iter(bb_list);
+ FOR_ALL_ELEM(bb_tmp, bb_list_iter, Init()) {
+ if (bb_tmp->First_executable_stmt() != NULL)
+ return bb_tmp;
+ }
+ }
+
+ SC_LIST_ITER sc_list_iter(kids);
+ SC_NODE * sc_tmp;
+ FOR_ALL_ELEM(sc_tmp, sc_list_iter, Init()) {
+ bb_tmp = sc_tmp->First_executable_blk();
+ if (bb_tmp)
+ return bb_tmp;
+ }
+
+ return NULL;
+}
+
// Walk upward in the ancestor sub-tree of this node and look for real nodes
that
// are not boundary delimiters.
SC_NODE *
@@ -922,7 +995,7 @@
bb_merge = Merge();
if (bb_head->Is_dom(this)
- && bb_merge->Is_postdom(this))
+ && bb_merge->Is_postdom(this))
ret_val= TRUE;
}
break;
@@ -1478,7 +1551,7 @@
if (!wn_last)
wn_last = wn_tmp;
- else
+ else if (wn_tmp)
wn_last = WN_CreateExp2(OPR_ADD, MTYPE_I4, MTYPE_V, wn_last, wn_tmp);
CXX_DELETE(l_stk, _pool);
@@ -1645,8 +1718,9 @@
SC_LIST_ITER sc_list_iter(this);
SC_NODE * tmp;
FOR_ALL_ELEM(tmp, sc_list_iter, Init()) {
- if (tmp)
- fprintf(fp, "%d ",tmp->Id());
+ if (tmp) {
+ fprintf(fp, "%d(%s) ",tmp->Id(), tmp->Type_name_abbr());
+ }
}
fprintf(fp, "\n ");
}
@@ -2015,6 +2089,7 @@
ALIAS_MANAGER * alias_mgr = _cu->Alias_mgr();
WN * call_wn = NULL;
WN * load_wn = NULL;
+ WN * store_wn = NULL;
TY_ITER i ;
ST *st;
int ii;
@@ -2127,10 +2202,16 @@
else if (OPERATOR_is_scalar_load(WN_operator(wn2)))
load_wn = wn2;
+ if (OPERATOR_is_scalar_store(WN_operator(wn1)))
+ store_wn = wn1;
+ else if (OPERATOR_is_scalar_store(WN_operator(wn2)))
+ store_wn = wn2;
+
if (Aliased(alias_mgr, wn1, wn2) != NOT_ALIASED) {
+ OPT_STAB * opt_stab = _cu->Opt_stab();
+
if (call_wn && load_wn) {
AUX_ID load_aux = WN_aux(load_wn);
- OPT_STAB * opt_stab = _cu->Opt_stab();
ST * load_st = NULL;
if (load_aux && (load_aux <= opt_stab->Lastidx()))
@@ -2158,6 +2239,19 @@
else if (load_st && (ST_class(load_st) == CLASS_PREG))
return FALSE;
}
+ else if (call_wn && store_wn) {
+ AUX_ID store_aux = WN_aux(store_wn);
+
+ if (store_aux && (store_aux <= opt_stab->Lastidx())) {
+ ST * store_st = opt_stab->Aux_stab_entry(store_aux)->St();
+ if (store_st && (ST_class(store_st) == CLASS_PREG)
+ && (WN_operator(WN_kid(store_wn, 0)) == OPR_INTCONST)) {
+ // Store of a constant to a preg does not alias with a call.
+ return FALSE;
+ }
+ }
+ }
+
return TRUE;
}
@@ -2420,7 +2514,7 @@
FOR_ALL_ELEM(tmp, kids_iter, Init(sc->Kids())) {
this->Top_down_trans(tmp);
}
-
+
if (do_analyze_loops && !cfg->Loops_valid())
cfg->Analyze_loops();
}
@@ -2740,6 +2834,15 @@
if (opc == OPC_IO)
return TRUE;
+ // Disambiguate bit-reduction operations on the same object.
+ WN * wn_red1 = WN_get_bit_reduction(wn1);
+ WN * wn_red2 = WN_get_bit_reduction(wn_root);
+ if (wn_red1 && wn_red2 && (WN_Simp_Compare_Trees(WN_kid0(wn_red1),
WN_kid0(wn_red2)) == 0)) {
+ if (!Maybe_assigned_expr(wn1, wn_red2)
+ && !Maybe_assigned_expr(wn_root, wn_red1))
+ return FALSE;
+ }
+
ALIAS_MANAGER * alias_mgr = _cu->Alias_mgr();
if ((OPCODE_is_store(opc) || OPCODE_is_call(opc))
@@ -3119,6 +3222,10 @@
if (sc1->Parent() != sc2->Parent())
return FALSE;
+ // Avoid compgoto complication.
+ if (sc1->Parent()->Find_kid_of_type(SC_COMPGOTO))
+ return FALSE;
+
BB_NODE * rep1 = sc1->Get_bb_rep();
BB_NODE * rep2 = sc2->Get_bb_rep();
@@ -3207,6 +3314,7 @@
BOOL do_flip = FALSE;
BOOL can_skip_taildup = FALSE;
+ SC_NODE * sc_flip = NULL;
if (!no_alias) {
if (!do_query && (_action == DO_IFFLIP)) {
@@ -3319,6 +3427,7 @@
}
do_flip = TRUE;
+ sc_flip = next_sibling;
}
next_sibling = next_sibling->Next_sibling();
}
@@ -3368,10 +3477,26 @@
return TRUE;
}
- if (do_flip && can_skip_taildup) {
- Delete_val_range_maps();
- Do_flip(sc2);
- return TRUE;
+ if (do_flip) {
+ if (can_skip_taildup) {
+ Delete_val_range_maps();
+ Do_flip(sc2);
+ return TRUE;
+ }
+
+ // Instead of tail-duplication, we can sink the flip statement to sc2's
merge block
+ // if it has no dependency on sc2's then-path and else-path.
+ if (!Has_dependency(sc2->First_kid(), sc_flip)
+ && !Has_dependency(sc2->Last_kid(), sc_flip)) {
+ BB_NODE * bb_merge = sc2->Merge();
+ BB_NODE * bb_tmp = sc_flip->First_executable_blk();
+ WN * wn_flip = bb_tmp->First_executable_stmt();
+ bb_tmp->Unlink_stmt(wn_flip);
+ bb_merge->Prepend_stmt(wn_flip);
+ Delete_val_range_maps();
+ Do_flip(sc2);
+ return TRUE;
+ }
}
// For every sibling between sc1 and sc2 (exclusive), if it has
@@ -3379,12 +3504,19 @@
// duplication.
BOOL has_dep = FALSE;
- BOOL all_blk = TRUE;
+ BOOL do_tail_dup = TRUE;
BOOL has_non_sp = FALSE;
- BOOL all_sese = TRUE;
next_sibling = sc1->Next_sibling();
+ SC_NODE * sc2_next_sibling = sc2->Next_sibling_of_type(SC_IF);
int count = 0;
+
+ // Get outermost nesting loop and nesting level.
+ std::pair<SC_NODE *, int> p_ret;
+ p_ret = sc1->Get_outermost_nesting_loop();
+ SC_NODE * outer_loop = p_ret.first;
+ int nest_level = p_ret.second;
+
while (next_sibling && (next_sibling != sc2)) {
count++;
FOR_ALL_ELEM(tmp, sc_list_iter, Init(sc2->Kids())) {
@@ -3395,10 +3527,56 @@
if (!Can_be_speculative(next_sibling))
has_non_sp = TRUE;
- if (next_sibling->Type() != SC_BLOCK)
- all_blk = FALSE;
- else if (!next_sibling->Is_sese())
- all_sese = FALSE;
+ SC_TYPE type = next_sibling->Type();
+ WN * cond1 = next_sibling->Get_cond();
+ WN * cond2 = NULL;
+
+ if (!next_sibling->Is_sese())
+ do_tail_dup = FALSE;
+ else if (type == SC_IF) {
+ BOOL can_merge = FALSE;
+ if (nest_level >= 2) {
+ // check whether next_sibling can potentially be if-merged with
+ // sc2's next sibling.
+ if (sc2_next_sibling) {
+ cond2 = sc2_next_sibling->Get_cond();
+ if( WN_Simp_Compare_Trees(cond1, cond2) == 0) {
+ can_merge = TRUE;
+ WN * wn_tmp = WN_kid0(expr1);
+ if (wn_tmp && WN_is_bit_op(wn_tmp) && !Is_invariant(outer_loop,
WN_kid1(wn_tmp), 0)) {
+ wn_tmp = WN_kid0(cond2);
+ if (WN_is_bit_op(wn_tmp) && Is_invariant(outer_loop,
WN_kid1(wn_tmp), 0)) {
+ can_merge = FALSE;
+ }
+ }
+ }
+ }
+ if (!can_merge) {
+ // check whether next_sibling can potentially be if-merged with sc1's
children.
+ for (int i = 0; i < 2; i++) {
+ SC_NODE * sc_tmp = NULL;
+ if (i == 0)
+ sc_tmp = sc1->Find_kid_of_type(SC_THEN)->Find_kid_of_type(SC_IF);
+ else
+ sc_tmp = sc1->Find_kid_of_type(SC_ELSE)->Find_kid_of_type(SC_IF);
+
+ while (sc_tmp) {
+ cond2 = sc_tmp->Get_cond();
+ if (WN_Simp_Compare_Trees(cond1, cond2) == 0) {
+ can_merge = TRUE;
+ break;
+ }
+ sc_tmp = sc_tmp->Next_sibling_of_type(SC_IF);
+ }
+ }
+ }
+ }
+
+ if (!can_merge)
+ do_tail_dup = FALSE;
+ }
+ else if (type != SC_BLOCK)
+ do_tail_dup = FALSE;
next_sibling = next_sibling->Next_sibling();
}
@@ -3418,7 +3596,7 @@
return TRUE;
}
- if (!all_blk || !all_sese)
+ if (!do_tail_dup)
return FALSE;
// Heuristic: in the global pass, avoid tail duplication unless both
@@ -3832,6 +4010,7 @@
SC_NODE * cand2 = NULL;
SC_NODE * tmp1;
SC_NODE * tmp2;
+ SC_NODE * tmp;
SC_LIST * list1;
SC_LIST * list2;
@@ -3906,6 +4085,20 @@
for (list2 = list1->Next(); list2; list2 = list2->Next()) {
tmp2 = list2->Node();
+ // Avoid picking candidates in a sequence of loops that are adjacent to
each other.
+ BOOL is_adjacent = TRUE;
+ tmp = tmp1->Next_sibling();
+ while (tmp && (tmp != tmp2)) {
+ if ((tmp->Type() != SC_LOOP)
+ || (tmp->Class_id() != tmp1->Class_id())) {
+ is_adjacent = FALSE;
+ break;
+ }
+ tmp = tmp->Next_sibling();
+ }
+ if (is_adjacent)
+ continue;
+
if (!sc_root->Is_pred_in_tree(tmp2))
continue;
@@ -3920,7 +4113,11 @@
// Condition 1.1
if (tmp1->Class_id() == tmp2->Class_id()) {
SC_NODE * lcp = tmp1->Find_lcp(tmp2);
-
+
+ // Avoid compgoto complication.
+ if (lcp->Find_kid_of_type(SC_COMPGOTO))
+ continue;
+
// Condition 1.3
if (lcp == sc_root) {
BB_NODE * bb1 = tmp1->First_bb();
@@ -4120,7 +4317,7 @@
stmt_count *= 2;
}
else if (next_type == SC_LOOP) {
- if (!Get_ext_trans()
+ if (!Do_ext_trans()
|| (cand1->Type() != SC_LOOP)
|| !Can_be_speculative(next)
|| Has_dependency(cand1, next)
@@ -4178,7 +4375,7 @@
_tmp_stack = NULL;
_def_map = NULL;
_def_cnt_map = NULL;
- _ext_trans = FALSE;
+ _ext_trans = EXT_TRANS_NONE;
_current_scope = NULL;
}
@@ -4296,12 +4493,6 @@
cfg->Feedback()->Move_edge_dest(tmp->Id(), bb_merge2->Id(),
first_bb1->Id());
}
- FOR_ALL_ELEM(tmp, bb_list_iter, Init(first_bb1->Pred())) {
- tmp->Replace_succ(first_bb1, first_bb2);
- if (cfg->Feedback())
- cfg->Feedback()->Move_edge_dest(tmp->Id(), first_bb1->Id(),
first_bb2->Id());
- }
-
BB_LIST * bb_list = first_bb2->Pred();
first_bb2->Set_pred(first_bb1->Pred());
first_bb1->Set_pred(bb_merge2->Pred());
@@ -4410,6 +4601,8 @@
BB_NODE * bb_exit = sc2->Exit();
WN * branch_wn = bb_exit->Branch_wn();
FmtAssert(WN_label_number(branch_wn), ("Null label"));
+ if (first_bb1->Labnam() == 0)
+ cfg->Add_label_with_wn(first_bb1);
WN_label_number(branch_wn) = first_bb1->Labnam();
}
else if (sc2_type == SC_IF) {
@@ -5394,9 +5587,9 @@
}
else if (sc_type == SC_LOOP) {
if (sc->Loopinfo()->Is_flag_set(LOOP_PRE_DO)) {
- if (Get_ext_trans()
- && sc->Is_ctrl_equiv(next)
- && !Has_dependency(sc, next)) {
+ if (sc->Is_ctrl_equiv(next)
+ && !Has_dependency(sc, next)
+ && Can_be_speculative(next)) {
Do_code_motion(sc, next);
}
else {
@@ -5433,7 +5626,7 @@
if (next != sc2) {
Do_code_motion(sc, next);
}
- else if (Get_ext_trans() && Can_fuse(sc)) {
+ else if (Do_ext_fusion() && Can_fuse(sc)) {
sc = Do_loop_fusion(sc, 1);
_loop_list = _loop_list->Remove(sc2, _pool);
}
@@ -5538,9 +5731,22 @@
PRO_LOOP_FUSION_TRANS::Top_down_trans(SC_NODE * sc_root)
{
if (sc_root->Has_flag(HAS_SYMM_LOOP)) {
- int orig_transform_count = _transform_count;
- Nonrecursive_trans(sc_root, TRUE);
+ int orig_transform_count = _transform_count;
+ if (!Do_ext_trans() || Do_ext_traverse())
+ Nonrecursive_trans(sc_root, TRUE);
+
+ if (Do_ext_fusion()) {
+ SC_NODE * sc_loop = sc_root->First_kid_of_type(SC_LOOP);
+ // Attempt loop fusion to expose if-merging opportunities.
+ while (sc_loop) {
+ if (Can_fuse(sc_loop))
+ sc_loop = Do_loop_fusion(sc_loop, 0);
+ if (sc_loop)
+ sc_loop = sc_loop->Next_sibling_of_type(SC_LOOP);
+ }
+ }
+
if (_transform_count > orig_transform_count) {
IF_MERGE_TRANS::Top_down_trans(sc_root);
Classify_loops(sc_root);
@@ -6990,9 +7196,15 @@
// - It is not the first kid of sc.
// - Every preceding sibling has no dependency on it.
// - Every succeeding sibling is either a loop fusion candidate or an empty
block.
+//
+// In addition, 'sc' should not have compgoto as its immediate child.
SC_NODE *
PRO_LOOP_INTERCHANGE_TRANS::Find_dist_cand(SC_NODE * sc)
{
+ // avoid compgoto complication.
+ if (sc->Find_kid_of_type(SC_COMPGOTO))
+ return NULL;
+
SC_NODE * sc_loop = sc->Find_kid_of_type(SC_LOOP);
SC_NODE * sc_cur;
@@ -7100,6 +7312,7 @@
// 4. Both the outer loop and the inner loop are a do-loop.
// 5. The outer loop and the inner loop are interchangable if there was no
intervening statement
// between them.
+// 6. None of its siblings and immediate child has SC_COMPGOTO type.
//
// Note that the restriction of "SC_BLOCK" is to simplify the low level
transformation machinery
// (head/tail duplication, code motion etc.). It is not a restriction of the
generic proactive
@@ -7132,6 +7345,12 @@
BOOL is_invar_outer = FALSE;
BOOL is_invar_inner = FALSE;
WN * wn_cond = NULL;
+
+ // Rule 6.
+ if (parent_node->Find_kid_of_type(SC_COMPGOTO)) {
+ is_cand = FALSE;
+ break;
+ }
// Rule 1.
switch (type) {
@@ -8584,10 +8803,6 @@
SC_NODE * sc_then = sc_if->Find_kid_of_type(SC_THEN);
SC_NODE * sc_else = sc_if->Find_kid_of_type(SC_ELSE);
-
- FmtAssert((sc_then->Is_empty() || sc_else->Is_empty()),
- ("Expect an empty then-path or else-path"));
-
SC_NODE * sc_p = sc_if->Parent();
SC_NODE * sc_prev = sc_if->Prev_sibling();
SC_NODE * sc_merge = sc_if->Next_sibling();
@@ -8596,26 +8811,46 @@
BB_NODE * bb_merge = sc_if->Merge();
BB_NODE * bb_first = NULL;
BB_NODE * bb_last = NULL;
+ BB_NODE * bb_tmp;
+ BB_LIST * bb_list_new;
+ BB_LIST_ITER bb_list_iter;
+ MEM_POOL * pool = cfg->Mem_pool();
for (int i = 0; i < 2; i ++) {
SC_NODE * sc_kid;
- if (i == 0)
+ if (i == 0) {
sc_kid = sc_then;
- else
+ bb_first = sc_kid->First_bb();
+ bb_last = sc_kid->Last_bb();
+ }
+ else {
sc_kid = sc_else;
+ BB_NODE * bb_cur = sc_kid->First_bb();
+ if (cfg->Feedback()) {
+ FOR_ALL_ELEM(bb_tmp, bb_list_iter, Init(bb_cur->Pred())) {
+ cfg->Feedback()->Delete_edge(bb_tmp->Id(), bb_cur->Id());
+ }
- if (sc_kid->Is_empty()) {
- continue;
+ FOR_ALL_ELEM(bb_tmp, bb_list_iter, Init(bb_last->Succ())) {
+ cfg->Feedback()->Move_edge_dest(bb_last->Id(), bb_tmp->Id(),
bb_first->Id());
+ }
+ }
+
+ bb_last->Remove_succs(pool);
+ bb_list_new = CXX_NEW(BB_LIST(bb_cur), pool);
+ bb_last->Set_succ(bb_list_new);
+ bb_cur->Remove_preds(pool);
+ bb_list_new = CXX_NEW(BB_LIST(bb_last), pool);
+ bb_cur->Set_pred(bb_list_new);
+ bb_cur->Set_prev(bb_last);
+ bb_last->Set_next(bb_cur);
+ bb_last = sc_kid->Last_bb();
}
SC_NODE * sc_tmp = sc_kid->First_kid();
-
while (sc_tmp) {
SC_NODE * sc_next = sc_tmp->Next_sibling();
- if (!bb_first)
- bb_first = sc_tmp->First_bb();
- bb_last = sc_tmp->Last_bb();
sc_tmp->Unlink();
sc_merge->Insert_before(sc_tmp);
sc_tmp = sc_next;
@@ -8625,15 +8860,18 @@
sc_if->Unlink();
sc_if->Delete();
- BB_NODE * bb_tmp;
- BB_LIST_ITER bb_list_iter;
FOR_ALL_ELEM(bb_tmp, bb_list_iter, Init(bb_head->Pred())) {
+ if (bb_tmp->Is_branch_to(bb_head)) {
+ WN * branch_wn = bb_tmp->Branch_wn();
+ cfg->Add_label_with_wn(bb_first);
+ WN_label_number(branch_wn) = bb_first->Labnam();
+ }
+
bb_tmp->Replace_succ(bb_head, bb_first);
if (cfg->Feedback())
cfg->Feedback()->Move_edge_dest(bb_tmp->Id(), bb_head->Id(),
bb_first->Id());
}
-
- MEM_POOL * pool = cfg->Mem_pool();
+
bb_first->Remove_preds(pool);
bb_first->Set_pred(bb_head->Pred());
bb_tmp = bb_head->Prev();
@@ -8657,13 +8895,14 @@
}
bb_last->Remove_succs(pool);
- BB_LIST * bb_list_new = CXX_NEW(BB_LIST(bb_merge), pool);
+ bb_list_new = CXX_NEW(BB_LIST(bb_merge), pool);
bb_last->Set_succ(bb_list_new);
bb_merge->Remove_preds(pool);
bb_list_new = CXX_NEW(BB_LIST(bb_last), pool);
bb_merge->Set_pred(bb_list_new);
bb_last->Set_next(bb_merge);
bb_merge->Set_prev(bb_last);
+ Delete_branch(bb_head);
if (sc_prev)
cfg->Fix_info(sc_prev);
@@ -8755,10 +8994,16 @@
// WN_aux(wn) may not be set correctly in the memory references
// in the expression trees for IO statements, so we should avoid
// traversing these statements.
- if (opr == OPR_IO)
+ if (opr == OPR_IO) {
+ if (wn_addr)
+ *wn_addr = NULL;
return FALSE;
+ }
+
if (OPERATOR_is_load(opr) || OPERATOR_is_store(opr)) {
if (OPERATOR_is_scalar_store(opr)) {
+ if (wn_addr)
+ *wn_addr = NULL;
return FALSE;
}
else if (OPERATOR_is_scalar_load(opr)) {
@@ -8775,25 +9020,47 @@
}
sc_iter = sc_iter->Parent();
}
- if (!is_index)
- return Is_invariant(sc_loop, wn, 0);
+ if (!is_index) {
+ if (Is_invariant(sc_loop, wn, 0))
+ return TRUE;
+ else {
+ if (wn_addr)
+ *wn_addr = NULL;
+ return FALSE;
+ }
+ }
}
else {
WN * wn_tmp = OPERATOR_is_load(opr) ? WN_kid0(wn) : WN_kid1(wn);
-
+
if ((*wn_addr) == NULL)
*wn_addr = wn_tmp;
else if (WN_Simp_Compare_Trees(*wn_addr, wn_tmp) != 0) {
+ if (wn_addr)
+ *wn_addr = NULL;
return FALSE;
}
+
+ if (OPERATOR_is_load(opr))
+ return TRUE;
+ else {
+ if (Get_unique_ref(WN_kid0(wn), sc_loop, wn_addr, sc_loc))
+ return TRUE;
+ else {
+ if (wn_addr)
+ *wn_addr = NULL;
+ return FALSE;
+ }
+ }
}
-
- return TRUE;
}
for (int i = 0; i < WN_kid_count(wn); i++) {
- if (!Get_unique_ref(WN_kid(wn, i), sc_loop, wn_addr, sc_loc))
+ if (!Get_unique_ref(WN_kid(wn, i), sc_loop, wn_addr, sc_loc)) {
+ if (wn_addr)
+ *wn_addr = NULL;
return FALSE;
+ }
}
return TRUE;
@@ -9393,9 +9660,10 @@
return TRUE;
}
-// Remove consecutive bitop operations that flip the same bit.
+// Prune WHIRLs in SC_BLOCKs.
+// - Remove consecutive bitop operations that flip the same bit.
void
-IF_MERGE_TRANS::Remove_redundant_bitops(SC_NODE * sc)
+IF_MERGE_TRANS::Prune_block(SC_NODE * sc)
{
if (sc->Type() == SC_BLOCK) {
BB_LIST * bb_list = sc->Get_bbs();
@@ -9436,17 +9704,65 @@
wn_iter = wn_next;
}
}
+
+ if (wn1) {
+ // Find next sibling which is a non-empty SC_BLOCK.
+ SC_NODE * sc2 = sc->Next_sibling_of_type(SC_BLOCK);
+ while (sc2 && sc2->Is_empty()) {
+ sc2 = sc2->Next_sibling_of_type(SC_BLOCK);
+ }
+
+ if (sc2) {
+ BB_NODE * bb2 = sc2->First_executable_blk();
+ if (bb2) {
+ WN * wn2 = bb2->First_executable_stmt();
+ if (wn2 && WN_get_bit_reduction(wn2)
+ && (WN_Simp_Compare_Trees(WN_kid0(wn1), WN_kid0(wn2)) == 0)
+ && sc->Is_ctrl_equiv(sc2)) {
+ SC_NODE * sc_tmp = sc->Next_sibling();
+ BOOL has_dep = FALSE;
+
+ Infer_val_range(sc, sc2);
+
+ // Check whether wn1 has dependency on siblings between sc and sc2.
+ while (sc_tmp && (sc_tmp != sc2)) {
+ if (Has_dependency(sc_tmp, wn1)) {
+ has_dep = TRUE;
+ break;
+ }
+ sc_tmp = sc_tmp->Next_sibling();
+ }
+
+ Delete_val_range_maps();
+
+ if (!has_dep) {
+ bb1->Unlink_stmt(wn1);
+ bb2->Unlink_stmt(wn2);
+ WN_Delete(wn1);
+ WN_Delete(wn2);
+ }
+ }
+ }
+ }
+ }
}
}
// Bottom-up prune dead codes for the SC tree rooted at 'sc'.
-void
+// Return TRUE if 'sc' is unlinked or deleted.
+BOOL
IF_MERGE_TRANS::Bottom_up_prune(SC_NODE * sc)
{
SC_NODE * tmp = sc->First_kid();
+ SC_NODE * sc_next;
+
+ if ((WOPT_Enable_Pro_Loop_Limit >= 0)
+ && (Transform_count() >= WOPT_Enable_Pro_Loop_Limit))
+ return FALSE;
+
while (tmp) {
// Merge consecutive blocks if possible.
- SC_NODE * sc_next = tmp->Next_sibling();
+ sc_next = tmp->Next_sibling();
if (tmp->Type() == SC_BLOCK) {
SC_NODE * sc_cur = tmp;
while (sc_next && (sc_next->Type() == SC_BLOCK)) {
@@ -9458,22 +9774,52 @@
}
}
+ // Remove unused label statements.
+ BB_NODE * bb_rep = tmp->Get_bb_rep();
+ if (bb_rep) {
+ WN * wn_label = bb_rep->Firststmt();
+ if (wn_label && (WN_operator(wn_label) == OPR_LABEL)) {
+ BOOL is_branch_target = FALSE;
+ BB_NODE * bb_tmp;
+ BB_LIST_ITER bb_list_iter;
+ FOR_ALL_ELEM(bb_tmp, bb_list_iter, Init(bb_rep->Pred())) {
+ WN * wn_branch = bb_tmp->Branch_wn();
+ if (wn_branch) {
+ OPERATOR opr = WN_operator(wn_branch);
+ if (((opr != OPR_FALSEBR) && (opr != OPR_TRUEBR)
+ && (opr != OPR_GOTO))
+ || bb_tmp->Is_branch_to(bb_rep)) {
+ is_branch_target = TRUE;
+ break;
+ }
+ }
+ }
+ if (!is_branch_target)
+ bb_rep->Unlink_stmt(wn_label);
+ }
+ }
+
sc_next = tmp->Next_sibling();
- Bottom_up_prune(tmp);
+ if (Bottom_up_prune(tmp))
+ break;
tmp = sc_next;
}
-
+
SC_TYPE type = sc->Type();
- BOOL do_iter = FALSE;
+ BOOL unlinked = FALSE;
SC_NODE * sc_prev = sc->Prev_sibling();
SC_NODE * sc_parent = sc->Get_real_parent();
+ SC_NODE * first_kid = sc->First_kid();
+ SC_NODE * last_kid = sc->Last_kid();
CFG * cfg = _cu->Cfg();
- tmp = sc->Parent();
-
+ SC_NODE * sc_p = sc->Parent();
+ IDTYPE id = sc->Id();
+
switch (type) {
case SC_IF:
- if (sc->First_kid()->Is_empty()
- && sc->Last_kid()->Is_empty()) {
+ if (sc->Head()->Executable_stmt_count() == 1) {
+ if (first_kid->Is_empty()
+ && last_kid->Is_empty()) {
BB_NODE * bb_tmp;
BB_LIST_ITER bb_list_iter;
BB_NODE * bb_head = sc->Head();
@@ -9485,7 +9831,7 @@
cfg->Add_label_with_wn(bb_merge);
WN_label_number(branch_wn) = bb_merge->Labnam();
}
-
+
bb_tmp->Replace_succ(bb_head, bb_merge);
if (cfg->Feedback())
cfg->Feedback()->Move_edge_dest(bb_tmp->Id(), bb_head->Id(),
bb_merge->Id());
@@ -9498,25 +9844,79 @@
sc->Unlink();
sc->Delete();
- do_iter = TRUE;
- if (sc_prev)
- cfg->Fix_info(sc_prev);
- cfg->Fix_info(sc_parent);
- cfg->Invalidate_and_update_aux_info(FALSE);
- cfg->Invalidate_loops();
- Inc_transform_count();
+ unlinked = TRUE;
}
- break;
+ else if (sc->Is_sese()) {
+ SC_NODE * sc_iter1 = first_kid->First_executable_kid();
+ SC_NODE * sc_iter2 = last_kid->First_executable_kid();
+ BOOL is_same = TRUE;
+
+ while (sc_iter1 && sc_iter2) {
+ if (!sc_iter1->Compare_Trees(sc_iter2)) {
+ is_same = FALSE;
+ break;
+ }
+ sc_iter1 = sc_iter1->Next_executable_sibling();
+ sc_iter2 = sc_iter2->Next_executable_sibling();
+ }
+
+ BB_NODE * bb_prev;
+ BB_NODE * bb_iter1;
+ BB_NODE * bb_iter2;
+ BB_NODE * bb_merge = sc->Merge();
+
+ // If sc's then-path and else-path are identical, remove the condition.
+ if (is_same && (sc_iter1 == NULL) && (sc_iter2 == NULL)) {
+ sc_iter1 = last_kid->First_kid();
+ sc_iter2 = last_kid->Last_kid();
+ FmtAssert((first_kid->Last_kid()->Type() == SC_BLOCK), ("Expect a
SC_BLOCK."));
+ bb_prev = first_kid->Last_bb();
+ bb_iter1 = last_kid->First_bb();
+ bb_iter2 = last_kid->Last_bb();
+
+ Do_if_cond_unwrap(sc);
+
+ tmp = sc_iter1;
+ SC_NODE * sc_end = sc_iter2->Next_sibling();
+ while (tmp && (tmp != sc_end)) {
+ sc_next = tmp->Next_sibling();
+ tmp->Unlink();
+ tmp->Delete();
+ tmp = sc_next;
+ }
+
+ bb_prev->Set_succ(bb_iter2->Succ());
+ bb_merge->Set_pred(bb_iter1->Pred());
+ bb_iter2->Set_succ(NULL);
+ bb_iter1->Set_pred(NULL);
+ bb_prev->Set_next(bb_merge);
+ bb_merge->Set_prev(bb_prev);
+ unlinked = TRUE;
+ }
+ }
+ }
+ break;
case SC_BLOCK:
- Remove_redundant_bitops(sc);
+ Prune_block(sc);
break;
default:
;
}
- if (do_iter) {
- Bottom_up_prune(tmp);
+ if (unlinked) {
+ if (sc_prev)
+ cfg->Fix_info(sc_prev);
+ cfg->Fix_info(sc_parent);
+ cfg->Invalidate_and_update_aux_info(FALSE);
+ cfg->Invalidate_loops();
+ Inc_transform_count();
+
+ if (_trace)
+ printf("\n\t\t Prune IF (SC%d)\n", id);
+ Bottom_up_prune(sc_p);
}
+
+ return unlinked;
}
// Check whether the expression tree rooted at the given wn has the following
characteristic:
@@ -9586,7 +9986,7 @@
{
if ((sc->Type() != SC_IF) || (sc->Head()->Executable_stmt_count() != 1))
return FALSE;
-
+
SC_NODE * sc_p = sc->Get_real_parent();
SC_NODE * sc_prev = sc->Prev_sibling();
@@ -10368,13 +10768,20 @@
PRO_LOOP_EXT_TRANS::Init();
SC_NODE * sc_lcp = Normalize(sc_root);
PRO_LOOP_EXT_TRANS::Delete();
+ SC_NODE * sc_iter;
if (sc_lcp) {
IF_MERGE_TRANS::Top_down_trans(sc_lcp);
- Set_ext_trans(TRUE);
- PRO_LOOP_FUSION_TRANS::Doit(sc_lcp);
- PRO_LOOP_EXT_TRANS::Top_down_trans(sc_lcp);
+ sc_iter = sc_lcp;
+ Set_ext_trans(EXT_TRANS_TRAVERSE | EXT_TRANS_FUSION);
}
+ else {
+ sc_iter = sc_root;
+ Set_ext_trans(EXT_TRANS_FUSION);
+ }
+
+ PRO_LOOP_FUSION_TRANS::Doit(sc_iter);
+ PRO_LOOP_EXT_TRANS::Top_down_trans(sc_iter);
}
// Obtain hash key for 'wn'.
@@ -10593,14 +11000,15 @@
sc_last->Set_next(sc);
}
}
- // Only do it for the outermost loop at this time.
- return;
}
- SC_LIST_ITER kids_iter;
- SC_NODE * tmp;
- FOR_ALL_ELEM(tmp, kids_iter, Init(sc->Kids())) {
- Hash_if_conds(tmp);
+ if (sc->Type() != SC_LOOP) {
+ // Only do it for the outermost loop at this time.
+ SC_LIST_ITER kids_iter;
+ SC_NODE * tmp;
+ FOR_ALL_ELEM(tmp, kids_iter, Init(sc->Kids())) {
+ Hash_if_conds(tmp);
+ }
}
}
@@ -10799,9 +11207,10 @@
// Find a pair of candidates among the child nodes of 'sc' to invoke
// extended transformations. Such candidates satisfy the following criteria:
// 1. The type is either a SC_IF or a SC_LOOP.
-// 2. The pair are separated by a SC_IF with an empty else-path or an empty
if-path.
+// 2. The pair are separated by a SC_IF with an empty else-path or an empty
if-path
+// and the SC_IF is a SESE.
// 3. The pair are if-merging candidates or loops with same trip counts
-//
+// 'sc' should not have any immediate child having SC_COMPGOTO type.
// If found, return the SC_IF node between the candidates.
SC_NODE *
@@ -10810,6 +11219,9 @@
*cand1 = NULL;
*cand2 = NULL;
+ if (sc->Find_kid_of_type(SC_COMPGOTO))
+ return NULL;
+
CFG * cfg = Get_cu()->Cfg();
SC_LIST_ITER kids_iter;
SC_NODE * tmp;
@@ -10819,7 +11231,8 @@
if ((type != SC_IF)
|| (!tmp->First_kid()->Is_empty()
- && !tmp->Last_kid()->Is_empty()))
+ && !tmp->Last_kid()->Is_empty())
+ || !tmp->Is_sese())
continue;
SC_NODE * prev = tmp->Prev_sibling();
@@ -10832,7 +11245,8 @@
next = next->Next_sibling();
}
- if (!prev || !next || (prev->Type() != next->Type()))
+ if (!prev || !next || (prev->Type() != next->Type())
+ || !prev->Is_sese() || !next->Is_sese())
continue;
IF_MERGE_PASS s_pass = Get_pass();
@@ -11047,8 +11461,13 @@
SC_NODE * tmp;
SC_NODE * cand1 = NULL;
SC_NODE * cand2 = NULL;
+ SC_TYPE type = sc->Type();
- if (sc->Type() == SC_LP_BODY) {
+ // Avoid COMPGOTO complication.
+ if (sc->Find_kid_of_type(SC_COMPGOTO))
+ return;
+
+ if (type == SC_LP_BODY) {
SC_NODE * sc_if = Find_cand(sc, &cand1, &cand2);
while (sc_if) {
@@ -11109,9 +11528,16 @@
sc_if = Find_cand(sc, &cand1, &cand2);
}
}
+ else if (type == SC_IF) {
+ if (Bottom_up_prune(sc))
+ return;
+ }
- FOR_ALL_ELEM(tmp, kids_iter, Init(sc->Kids())) {
- this->Top_down_trans(tmp);
+ SC_NODE * sc_iter = sc->First_kid();
+ while (sc_iter) {
+ SC_NODE * sc_next = sc_iter->Next_sibling();
+ this->Top_down_trans(sc_iter);
+ sc_iter = sc_next;
}
}
@@ -11172,6 +11598,57 @@
return in_order;
}
+// Compare this SC_NODE to 'sc', return TRUE if they are identical, return
FALSE otherwise.
+BOOL
+SC_NODE::Compare_Trees(SC_NODE * sc)
+{
+ if (this == sc)
+ return TRUE;
+
+ if (Type() != sc->Type())
+ return FALSE;
+
+ BB_NODE * bb_tmp1 = Get_bb_rep();
+ BB_NODE * bb_tmp2 = sc->Get_bb_rep();
+
+ if (bb_tmp1 && bb_tmp2 &&
+ !bb_tmp1->Compare_Trees(bb_tmp2))
+ return FALSE;
+
+ BB_LIST * bb_list1 = Get_bbs();
+ BB_LIST * bb_list2 = sc->Get_bbs();
+
+ if (bb_list1 && bb_list2) {
+ BB_LIST_ITER bb_iter1(bb_list1);
+ BB_LIST_ITER bb_iter2(bb_list2);
+ bb_tmp1 = bb_iter1.First_elem();
+ bb_tmp2 = bb_iter2.First_elem();
+
+ while ((bb_tmp1 != NULL)
+ && (bb_tmp2 != NULL)) {
+ if (!bb_tmp1->Compare_Trees(bb_tmp2))
+ return FALSE;
+
+ bb_tmp1 =(!bb_iter1.Is_Empty()) ? bb_iter1.Next_elem() : NULL;
+ bb_tmp2 =(!bb_iter2.Is_Empty()) ? bb_iter2.Next_elem() : NULL;
+ }
+ }
+
+ SC_NODE * tmp1;
+ SC_NODE * tmp2;
+ tmp1 = First_executable_kid();
+ tmp2 = sc->First_executable_kid();
+
+ while (tmp1 && tmp2) {
+ if (!tmp1->Compare_Trees(tmp2))
+ return FALSE;
+ tmp1 = tmp1->Next_executable_sibling();
+ tmp2 = tmp2->Next_executable_sibling();
+ }
+
+ return ((tmp1 == NULL) && (tmp2 == NULL));
+}
+
// Do normalization in lock-step for nesting if-conditions of 'sc1' and 'sc2'.
// 'action' gives the portion of if-condition tree to apply
tree-height-reduction.
void
@@ -11327,6 +11804,7 @@
// no dependencies on all SC_IF nodes on the successor part of the path
(head duplication
// legality). If there exists a succeeding sibling, the succeeding sibling
must be a SC_BLOCK
// or a SC_LOOP.
+// 3. None of its sibings and immediate child has SC_COMPGOTO type.
BOOL
PRO_LOOP_EXT_TRANS::Is_candidate(SC_NODE * outer, SC_NODE * inner)
{
@@ -11336,11 +11814,17 @@
if (sc_iter == outer)
return FALSE;
+
+ if (outer->Find_kid_of_type(SC_COMPGOTO))
+ return FALSE;
while (sc_iter && (sc_iter != outer)) {
if (!sc_iter->Is_well_behaved())
return FALSE;
+ if (sc_iter->Find_kid_of_type(SC_COMPGOTO))
+ return FALSE;
+
SC_NODE * sc_tmp = sc_iter->Next_sibling();
while (sc_tmp) {
if ((sc_tmp->Type() != SC_BLOCK)
@@ -11634,8 +12118,8 @@
return wn;
}
-// Given a 'wn_key' whose value is greater or equal to 'val',
-// set up map.
+// Set the lower bound for 'wn_key', if 'wn_key' already has a lower bound,
+// tighten it if possible.
void
CFG_TRANS::Set_lo(WN_MAP & map, WN * wn_key, int val)
{
@@ -11646,7 +12130,7 @@
std::pair<bool,int> p_val = WN_get_val(wn_key, map);
val_tmp = p_val.second;
if (p_val.first
- && (val_tmp < val))
+ && (val_tmp > val))
return;
}
@@ -11705,12 +12189,25 @@
val = p_val.second;
if (p_val.first) {
- Set_map(_low_map, op1, op2);
+ wn_tmp = Get_const_wn(val + 1);
+ Set_map(_low_map, op1, wn_tmp);
Infer_val_range(op1, TRUE, TRUE);
}
break;
+ case OPR_GE:
+ op1 = WN_kid(wn, 0);
+ op2 = WN_kid(wn, 1);
+ p_val = WN_get_val(op2, _low_map);
+ val = p_val.second;
+
+ if (p_val.first) {
+ Set_map(_low_map, op1, op2);
+ Infer_val_range(op1, TRUE, TRUE);
+ }
+ break;
+
case OPR_LT:
op1 = WN_kid(wn, 0);
op2 = WN_kid(wn, 1);
@@ -11718,7 +12215,8 @@
val = p_val.second;
if (p_val.first) {
- Set_map(_low_map, op2, op1);
+ wn_tmp = Get_const_wn(val + 1);
+ Set_map(_low_map, op2, wn_tmp);
Infer_val_range(op2, TRUE, TRUE);
}
break;
@@ -11730,8 +12228,7 @@
val = p_val.second;
if (p_val.first) {
- wn_tmp = Get_const_wn(val - 1);
- Set_map(_low_map, op2, wn_tmp);
+ Set_map(_low_map, op2, op1);
Infer_val_range(op2, TRUE, TRUE);
}
break;
@@ -11860,14 +12357,15 @@
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);
+ if (WN_operator(wn_tmp) == OPR_INTCONST) {
+ if ((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:
@@ -11952,7 +12450,7 @@
{
SC_NODE * sc_lcp = sc1->Find_lcp(sc2);
- if (_invar_map || Get_ext_trans()) {
+ if (_invar_map || Do_ext_trans()) {
_low_map = WN_MAP_Create(_pool);
_high_map = WN_MAP_Create(_pool);
_def_wn_map = CXX_NEW(MAP(CFG_BB_TAB_SIZE, _pool), _pool);
@@ -11964,7 +12462,7 @@
&& sc_lcp->Loopinfo()->Is_flag_set(LOOP_PRE_DO)) {
Infer_lp_bound_val(sc_lcp);
- if (Get_ext_trans()) {
+ if (Do_ext_trans()) {
// Infer value ranges from the loop entry.
SC_NODE * sc_body = sc_lcp->Find_kid_of_type(SC_LP_BODY);
SC_NODE * sc_tmp = sc_body->First_kid();
@@ -11988,7 +12486,7 @@
sc_lcp = sc_lcp->Parent();
}
- if (nesting_lp) {
+ if (nesting_lp && (sc1->Type() == SC_IF)) {
WN * wn_cond = sc1->Get_cond();
Infer_shift_count_val(wn_cond, nesting_lp);
}
@@ -12153,8 +12651,8 @@
}
// Given a SC_IF node 'sc' and a bit-operation expression 'wn', if both the
then-path and
-// the else-path contain only SC_BLOCKs whose statements are bit reductions on
the same object,
-// and each path has only one statement that alters the same bit as 'wn', sink
that statement to
+// the else-path end with a SC_BLOCK whose statements are bit reductions on
the same object,
+// and there exists only one statement that alters the same bit as 'wn', sink
that statement to
// the merge block.
BOOL CFG_TRANS::Do_flip_tail_merge(SC_NODE * sc, WN * wn)
{
@@ -12168,10 +12666,13 @@
SC_NODE * tmp;
for (int i = 0; i < 2; i++) {
tmp = (i == 0) ? sc->First_kid() : sc->Last_kid();
- if (tmp->First_kid() != tmp->Last_kid())
+ SC_NODE * first_kid = tmp->First_kid();
+ SC_NODE * last_kid = tmp->Last_kid();
+
+ if (!first_kid->Is_ctrl_equiv(last_kid))
return FALSE;
- tmp = tmp->First_kid();
- if (tmp->Type() != SC_BLOCK)
+
+ if (last_kid->Type() != SC_BLOCK)
return FALSE;
}
@@ -12186,11 +12687,11 @@
for (int i = 0; i < 2; i++) {
tmp = (i == 0) ? sc->First_kid() : sc->Last_kid();
- tmp = tmp->First_kid();
-
+ tmp = tmp->Last_kid();
+
BB_LIST_ITER bb_list_iter(tmp->Get_bbs());
BB_NODE * bb_iter;
-
+
FOR_ALL_ELEM(bb_iter, bb_list_iter, Init()) {
WN * wn_iter;
STMT_ITER stmt_iter;
Modified: trunk/osprey/be/opt/opt_proactive.h
===================================================================
--- trunk/osprey/be/opt/opt_proactive.h 2012-01-30 13:30:05 UTC (rev 3864)
+++ trunk/osprey/be/opt/opt_proactive.h 2012-02-01 20:15:09 UTC (rev 3865)
@@ -137,12 +137,22 @@
{"NONE", "IF", "THEN", "ELSE", "LOOP", "BLOCK", "FUNC",
"LP_START", "LP_COND", "LP_STEP", "LP_BACKEDGE", "LP_BODY", "COMPGOTO",
"OTHER"};
+static const char * sc_type_name_abbr[] =
+ {"", "^", "", "", "o", "-", "",
+ "", "", "", "", "", "", ""};
+
// bit mask.
enum SC_NODE_FLAG
{
HAS_SYMM_LOOP = 0x1
};
+// bit mask for transformations at the extended transformation (EXT) phase.
+enum EXT_TRANS_KIND {
+ EXT_TRANS_NONE = 0, // Do not do EXT.
+ EXT_TRANS_FUSION = 1, // Do loop fusions at the EXT phase.
+ EXT_TRANS_TRAVERSE = 2 // Do traversal transformations at the EXT
phase.
+};
// Structure component nodes.
class SC_NODE {
@@ -182,6 +192,7 @@
SC_TYPE Type(void) const { return type; }
void Set_type(SC_TYPE i) { type = i; }
const char * Type_name(void) const { return sc_type_name[type]; }
+ const char * Type_name_abbr(void) const { return sc_type_name_abbr[type];
}
BB_NODE * Get_bb_rep() const { return (SC_type_has_rep(type) ?
u1.bb_rep : NULL); }
void Set_bb_rep(BB_NODE * i)
{
@@ -237,13 +248,16 @@
void Insert_after(SC_NODE * sc);
SC_NODE * Last_kid();
SC_NODE * First_kid();
+ SC_NODE * First_executable_kid();
SC_NODE * Next_sibling();
SC_NODE * Prev_sibling();
SC_NODE * Next_sibling_of_type(SC_TYPE);
SC_NODE * Next_in_tree();
+ SC_NODE * Next_executable_sibling();
SC_NODE * Get_nesting_if(SC_NODE *);
std::pair<SC_NODE *, bool> Get_nesting_if();
std::pair<SC_NODE *, int> Get_outermost_nesting_if();
+ std::pair<SC_NODE *, int> Get_outermost_nesting_loop();
SC_NODE * First_kid_of_type(SC_TYPE);
BOOL Contains(BB_NODE *);
BB_NODE * Then();
@@ -269,6 +283,8 @@
BB_NODE * Last_bb();
// Find first executable statement in this SC_NODE.
WN * First_executable_stmt();
+ // Find first executable statement's containing block in this SC_NODE.
+ BB_NODE * First_executable_blk();
BOOL Is_pred_in_tree(SC_NODE *);
int Num_of_loops(SC_NODE *, BOOL, BOOL);
int Executable_stmt_count();
@@ -279,6 +295,7 @@
WN * Get_cond();
BOOL Is_ctrl_equiv(SC_NODE *);
BOOL Get_bounds(WN **, WN **, WN **);
+ BOOL Compare_Trees(SC_NODE *);
};
class SC_LIST : public SLIST_NODE {
@@ -355,8 +372,8 @@
MAP * _def_map; // Map symbol auxiliary Id to definition WN *.
MAP * _const_wn_map; // map an integer constant to WHIRL.
MAP * _def_cnt_map; // hash aux id to def count
- BOOL _ext_trans; // do extended transformations.
-
+ int _ext_trans; // do extended transformations.
+
protected:
COMP_UNIT * _cu;
BOOL _trace;
@@ -469,14 +486,19 @@
BOOL Hoist_succ_blocks(SC_NODE *);
SC_NODE * Merge_block(SC_NODE *, SC_NODE *);
BOOL Have_same_trip_count(SC_NODE *, SC_NODE *);
- BOOL Get_ext_trans() { return _ext_trans; }
void Replace_wn(SC_NODE *, WN *, WN *);
void Replace_wn(BB_NODE *, WN *, WN *);
BOOL Replace_wn(WN *, WN *, WN *);
WN * Simplify_wn(WN *);
BOOL Do_flip_tail_merge(SC_NODE *, WN *);
void Do_flip(SC_NODE *);
-
+ // Whether to do EXT.
+ BOOL Do_ext_trans() { return (_ext_trans != EXT_TRANS_NONE); }
+ // Whether to do traverse transformations at the EXT phase.
+ BOOL Do_ext_traverse() { return ((_ext_trans & EXT_TRANS_TRAVERSE) != 0); }
+ // Whether to do loop fusions at the EXT phase.
+ BOOL Do_ext_fusion() { return ((_ext_trans & EXT_TRANS_FUSION) != 0); }
+
public:
void Set_trace(BOOL i) { _trace = i; }
void Set_dump(BOOL i) { _dump = i; }
@@ -487,7 +509,7 @@
void Do_tail_duplication(SC_NODE *, SC_NODE *);
void Hash_def_cnt_map(SC_NODE *);
void Init();
- void Set_ext_trans(BOOL in) { _ext_trans = in; }
+ void Set_ext_trans(int in) { _ext_trans = in; }
};
// bit mask for if-merging actions.
@@ -519,7 +541,7 @@
void Merge_CFG(SC_NODE *, SC_NODE *);
void Merge_SC(SC_NODE *, SC_NODE *);
BOOL Is_if_collapse_cand(SC_NODE * sc1, SC_NODE * sc2);
- void Remove_redundant_bitops(SC_NODE *);
+ void Prune_block(SC_NODE *);
protected:
void Set_region_id(int i) { _region_id = i; }
@@ -527,7 +549,7 @@
BOOL Is_candidate(SC_NODE *, SC_NODE *, BOOL);
void Clear(void);
BOOL Do_reverse_loop_unswitching(SC_NODE *, SC_NODE *, SC_NODE *);
- void Bottom_up_prune(SC_NODE *);
+ BOOL Bottom_up_prune(SC_NODE *);
public:
void Top_down_trans(SC_NODE * sc);
Modified: trunk/osprey/be/opt/opt_wn.cxx
===================================================================
--- trunk/osprey/be/opt/opt_wn.cxx 2012-01-30 13:30:05 UTC (rev 3864)
+++ trunk/osprey/be/opt/opt_wn.cxx 2012-02-01 20:15:09 UTC (rev 3865)
@@ -1856,56 +1856,6 @@
return std::pair<bool,int>(FALSE,0);
}
-// Walk nodes in the given WHIRL tree, collect operands for ADD operators.
-//
-// For example, given the following tree,
-// I4I4LDID 0 <st 2>
-// I4I4LDID 49 <st 80>
-// I4SUB
-// I4INTCONST -1 (0xffffffffffffffff)
-// I4ADD
-//
-// We will collect two nodes:
-// I4I4LDID 0 <st 2>
-// I4I4LDID 49 <st 80>
-// I4SUB
-//
-// I4INTCONST -1 (0xffffffffffffffff)
-
-static STACK<WN *> *
-Collect_operands(WN * wn, MEM_POOL * pool)
-{
- STACK<WN *> * stack1 = NULL;
- STACK<WN *> * stack2 = NULL;
- OPERATOR opr = WN_operator(wn);
-
- if ((opr == OPR_ADD) || (OPERATOR_is_load(opr))) {
- stack1 = CXX_NEW(STACK<WN *>(pool), pool);
- stack1->Push(wn);
- }
-
- while (stack1 && !stack1->Is_Empty()) {
- WN * wn_iter = stack1->Pop();
- OPERATOR opr_iter = WN_operator(wn_iter);
-
- if (opr_iter == OPR_ADD) {
- stack1->Push(WN_kid(wn_iter, 0));
- stack1->Push(WN_kid(wn_iter, 1));
- }
- else {
- if (stack2 == NULL)
- stack2 = CXX_NEW(STACK<WN *>(pool), pool);
-
- stack2->Push(wn_iter);
- }
- }
-
- if (stack1)
- CXX_DELETE(stack1, pool);
-
- return stack2;
-}
-
// Query whether two integral WHIRLs have disjointed value ranges.
// Return FALSE if this is not the case or if we can't tell.
// lo_map and hi_map are maps from "WN *" to "UNSIGNED long long" that
@@ -1967,17 +1917,58 @@
}
else {
MEM_POOL * pool = Malloc_Mem_Pool;
- STACK<WN *> * stack1 = Collect_operands(wn1, pool);
- STACK<WN *> * stack2 = Collect_operands(wn2, pool);
- STACK<WN *> * stack_tmp = NULL;
+ STACK<WN *> * add_stk = CXX_NEW(STACK<WN *> (pool), pool);
+ STACK<WN *> * sub_stk = CXX_NEW(STACK<WN *> (pool), pool);
+ STACK<WN *> * stack1 = NULL;
+ STACK<WN *> * stack2 = NULL;
+ WN * wn_iter;
+
+ Collect_operands(wn1, add_stk, sub_stk);
+ while (!add_stk->Is_Empty()) {
+ wn_iter = add_stk->Pop();
+ if (!stack1)
+ stack1 = CXX_NEW(STACK<WN *>(pool), pool);
+ stack1->Push(wn_iter);
+ }
+
+ while (!sub_stk->Is_Empty()) {
+ wn_iter = sub_stk->Pop();
+ if (!stack2)
+ stack2 = CXX_NEW(STACK<WN *>(pool), pool);
+
+ stack2->Push(wn_iter);
+ }
+
+ Collect_operands(wn2, add_stk, sub_stk);
+ while (!add_stk->Is_Empty()) {
+ wn_iter = add_stk->Pop();
+ if (!stack2)
+ stack2 = CXX_NEW(STACK<WN *>(pool), pool);
+
+ stack2->Push(wn_iter);
+ }
+
+ while (!sub_stk->Is_Empty()) {
+ wn_iter = sub_stk->Pop();
+ if (!stack1)
+ stack1 = CXX_NEW(STACK<WN *>(pool), pool);
+
+ stack1->Push(wn_iter);
+ }
+
+ CXX_DELETE(add_stk, pool);
+ CXX_DELETE(sub_stk, pool);
+
+ STACK<WN *> * stack_tmp1 = NULL;
+
// Shuffle stack1 and stack2 so that stack1 contains more elements.
if ((!stack1 && stack2)
|| ((stack1 && stack2)
&& (stack1->Elements() < stack2->Elements()))) {
- stack_tmp = stack1;
+ stack_tmp1 = stack1;
stack1 = stack2;
- stack2 = stack_tmp;
+ stack2 = stack_tmp1;
}
// Evaluate diff of stack1 and stack2.
@@ -2003,6 +1994,7 @@
int delta_lo = delta;
int delta_hi = delta;
std::pair<bool, int> p_val;
+ stack_tmp1 = CXX_NEW(STACK<WN *>(pool), pool);
if (stack2) {
for (int i = 0; i < stack2->Elements(); i++) {
@@ -2011,16 +2003,52 @@
if (WN_operator(wn2_iter) == OPR_INTCONST)
continue;
+ WN * wn_mul = NULL;
BOOL found = FALSE;
+
+ if ((WN_operator(wn2_iter) == OPR_MPY)
+ && (WN_operator(WN_kid1(wn2_iter)) == OPR_INTCONST))
+ wn_mul = WN_kid0(wn2_iter);
for (int j = 0; j < stack1->Elements(); j++) {
WN * wn1_iter = stack1->Top_nth(j);
- if (wn1_iter && (WN_Simp_Compare_Trees(wn1_iter, wn2_iter) == 0)) {
+ if (WN_Simp_Compare_Trees(wn1_iter, wn2_iter) == 0) {
stack1->DeleteTop(j);
found = TRUE;
break;
}
+ else if (wn_mul
+ && (WN_Simp_Compare_Trees(wn1_iter, wn_mul) == 0)) {
+ // Identify expressions like 'x+x' is equal to '2*x'.
+ int cnt = 0;
+ WN * wn_tmp;
+
+ while (!stack_tmp1->Is_Empty())
+ stack_tmp1->Pop();
+
+ for (int k = 0; k < stack1->Elements(); k++) {
+ wn_tmp = stack1->Top_nth(k);
+ if (WN_Simp_Compare_Trees(wn_mul, wn_tmp) == 0)
+ cnt++;
+ else
+ stack_tmp1->Push(wn_tmp);
+ }
+
+ if (cnt == WN_const_val(WN_kid1(wn2_iter))) {
+ // Remove matched elements from 'stack1'.
+ while (!stack1->Is_Empty())
+ stack1->Pop();
+
+ while (!stack_tmp1->Is_Empty()) {
+ wn_tmp = stack_tmp1->Pop();
+ stack1->Push(wn_tmp);
+ }
+
+ found = TRUE;
+ break;
+ }
+ }
}
if (!found) {
@@ -2038,6 +2066,7 @@
else {
CXX_DELETE(stack1, pool);
CXX_DELETE(stack2, pool);
+ CXX_DELETE(stack_tmp1, pool);
return FALSE;
}
}
@@ -2066,6 +2095,7 @@
CXX_DELETE(stack1, pool);
if (stack2)
CXX_DELETE(stack2, pool);
+ CXX_DELETE(stack_tmp1, pool);
return FALSE;
}
}
@@ -2078,6 +2108,8 @@
if (stack2)
CXX_DELETE(stack2, pool);
+ CXX_DELETE(stack_tmp1, pool);
+
if ((delta_lo > 0) || (delta_hi < 0))
return TRUE;
}
Modified: trunk/osprey/be/vho/vho_lower.cxx
===================================================================
--- trunk/osprey/be/vho/vho_lower.cxx 2012-01-30 13:30:05 UTC (rev 3864)
+++ trunk/osprey/be/vho/vho_lower.cxx 2012-02-01 20:15:09 UTC (rev 3865)
@@ -8236,84 +8236,6 @@
return wn;
} /* vho_lower_if */
-#ifdef KEY // bug 8581
-// determine if two WHIRL statements are identical; only handle store
statements
-// for now
-static BOOL
-Identical_stmt(WN *stmt1, WN *stmt2)
-{
- if (stmt1 == NULL || stmt2 == NULL)
- return FALSE;
- if (WN_opcode(stmt1) != WN_opcode(stmt2))
- return FALSE;
- switch(WN_operator(stmt1)) {
- case OPR_STID:
- if (WN_store_offset(stmt1) != WN_store_offset(stmt2))
- return FALSE;
- if (WN_field_id(stmt1) != WN_field_id(stmt2))
- return FALSE;
- if (WN_desc(stmt1) != WN_desc(stmt2))
- return FALSE;
- if (WN_st_idx(stmt1) != WN_st_idx(stmt2))
- return FALSE;
- return WN_Simp_Compare_Trees(WN_kid0(stmt1), WN_kid0(stmt2)) == 0;
- case OPR_STBITS:
- if (WN_store_offset(stmt1) != WN_store_offset(stmt2))
- return FALSE;
- if (WN_bit_offset(stmt1) != WN_bit_offset(stmt2))
- return FALSE;
- if (WN_bit_size(stmt1) != WN_bit_size(stmt2))
- return FALSE;
- if (WN_st_idx(stmt1) != WN_st_idx(stmt2))
- return FALSE;
- return WN_Simp_Compare_Trees(WN_kid0(stmt1), WN_kid0(stmt2)) == 0;
- case OPR_ISTORE:
- if (WN_store_offset(stmt1) != WN_store_offset(stmt2))
- return FALSE;
- if (WN_field_id(stmt1) != WN_field_id(stmt2))
- return FALSE;
- if (WN_desc(stmt1) != WN_desc(stmt2))
- return FALSE;
- if (WN_Simp_Compare_Trees(WN_kid0(stmt1), WN_kid0(stmt2)) != 0)
- return FALSE;
- return WN_Simp_Compare_Trees(WN_kid1(stmt1), WN_kid1(stmt2)) == 0;
- case OPR_ISTBITS:
- if (WN_store_offset(stmt1) != WN_store_offset(stmt2))
- return FALSE;
- if (WN_bit_offset(stmt1) != WN_bit_offset(stmt2))
- return FALSE;
- if (WN_bit_size(stmt1) != WN_bit_size(stmt2))
- return FALSE;
- if (WN_Simp_Compare_Trees(WN_kid0(stmt1), WN_kid0(stmt2)) != 0)
- return FALSE;
- return WN_Simp_Compare_Trees(WN_kid1(stmt1), WN_kid1(stmt2)) == 0;
- case OPR_MSTORE:
- if (WN_store_offset(stmt1) != WN_store_offset(stmt2))
- return FALSE;
- if (WN_field_id(stmt1) != WN_field_id(stmt2))
- return FALSE;
- if (WN_Simp_Compare_Trees(WN_kid0(stmt1), WN_kid0(stmt2)) != 0)
- return FALSE;
- if (WN_Simp_Compare_Trees(WN_kid1(stmt1), WN_kid1(stmt2)) != 0)
- return FALSE;
- return WN_Simp_Compare_Trees(WN_kid2(stmt1), WN_kid2(stmt2)) == 0;
- case OPR_BLOCK: {
- WN *s1 = WN_first(stmt1);
- WN *s2 = WN_first(stmt2);
- for ( ; ; ) {
- if (s1 == NULL && s2 == NULL)
- return TRUE;
- if (! Identical_stmt(s1, s2))
- return FALSE;
- s1 = WN_next(s1);
- s2 = WN_next(s2);
- }
- }
- default: ;
- }
- return FALSE;
-}
-
// If the given IF has a nested IF in the ELSE part with identical THEN stmt:
//
// IF (A) THEN S1; ELSE { if (B) THEN S1; ELSE S2; }
@@ -8433,7 +8355,6 @@
WN_DELETE_Tree(then_wn);
return wn;
}
-#endif
static WN *
vho_lower_block ( WN * old_block )
Modified: trunk/osprey/common/com/wn.cxx
===================================================================
--- trunk/osprey/common/com/wn.cxx 2012-01-30 13:30:05 UTC (rev 3864)
+++ trunk/osprey/common/com/wn.cxx 2012-02-01 20:15:09 UTC (rev 3865)
@@ -3765,7 +3765,85 @@
return NULL;
}
+// bug 8581
+// determine if two WHIRL statements are identical; only handle store
statements
+// for now
BOOL
+Identical_stmt(WN *stmt1, WN *stmt2)
+{
+ if (stmt1 == NULL || stmt2 == NULL)
+ return FALSE;
+ if (WN_opcode(stmt1) != WN_opcode(stmt2))
+ return FALSE;
+ switch(WN_operator(stmt1)) {
+ case OPR_STID:
+ if (WN_store_offset(stmt1) != WN_store_offset(stmt2))
+ return FALSE;
+ if (WN_field_id(stmt1) != WN_field_id(stmt2))
+ return FALSE;
+ if (WN_desc(stmt1) != WN_desc(stmt2))
+ return FALSE;
+ if (WN_st_idx(stmt1) != WN_st_idx(stmt2))
+ return FALSE;
+ return WN_Simp_Compare_Trees(WN_kid0(stmt1), WN_kid0(stmt2)) == 0;
+ case OPR_STBITS:
+ if (WN_store_offset(stmt1) != WN_store_offset(stmt2))
+ return FALSE;
+ if (WN_bit_offset(stmt1) != WN_bit_offset(stmt2))
+ return FALSE;
+ if (WN_bit_size(stmt1) != WN_bit_size(stmt2))
+ return FALSE;
+ if (WN_st_idx(stmt1) != WN_st_idx(stmt2))
+ return FALSE;
+ return WN_Simp_Compare_Trees(WN_kid0(stmt1), WN_kid0(stmt2)) == 0;
+ case OPR_ISTORE:
+ if (WN_store_offset(stmt1) != WN_store_offset(stmt2))
+ return FALSE;
+ if (WN_field_id(stmt1) != WN_field_id(stmt2))
+ return FALSE;
+ if (WN_desc(stmt1) != WN_desc(stmt2))
+ return FALSE;
+ if (WN_Simp_Compare_Trees(WN_kid0(stmt1), WN_kid0(stmt2)) != 0)
+ return FALSE;
+ return WN_Simp_Compare_Trees(WN_kid1(stmt1), WN_kid1(stmt2)) == 0;
+ case OPR_ISTBITS:
+ if (WN_store_offset(stmt1) != WN_store_offset(stmt2))
+ return FALSE;
+ if (WN_bit_offset(stmt1) != WN_bit_offset(stmt2))
+ return FALSE;
+ if (WN_bit_size(stmt1) != WN_bit_size(stmt2))
+ return FALSE;
+ if (WN_Simp_Compare_Trees(WN_kid0(stmt1), WN_kid0(stmt2)) != 0)
+ return FALSE;
+ return WN_Simp_Compare_Trees(WN_kid1(stmt1), WN_kid1(stmt2)) == 0;
+ case OPR_MSTORE:
+ if (WN_store_offset(stmt1) != WN_store_offset(stmt2))
+ return FALSE;
+ if (WN_field_id(stmt1) != WN_field_id(stmt2))
+ return FALSE;
+ if (WN_Simp_Compare_Trees(WN_kid0(stmt1), WN_kid0(stmt2)) != 0)
+ return FALSE;
+ if (WN_Simp_Compare_Trees(WN_kid1(stmt1), WN_kid1(stmt2)) != 0)
+ return FALSE;
+ return WN_Simp_Compare_Trees(WN_kid2(stmt1), WN_kid2(stmt2)) == 0;
+ case OPR_BLOCK: {
+ WN *s1 = WN_first(stmt1);
+ WN *s2 = WN_first(stmt2);
+ for ( ; ; ) {
+ if (s1 == NULL && s2 == NULL)
+ return TRUE;
+ if (! Identical_stmt(s1, s2))
+ return FALSE;
+ s1 = WN_next(s1);
+ s2 = WN_next(s2);
+ }
+ }
+ default: ;
+ }
+ return FALSE;
+}
+
+BOOL
WN_is_assign(WN * wn)
{
WN *wn_first = WN_first(wn);
Modified: trunk/osprey/common/com/wn.h
===================================================================
--- trunk/osprey/common/com/wn.h 2012-01-30 13:30:05 UTC (rev 3864)
+++ trunk/osprey/common/com/wn.h 2012-02-01 20:15:09 UTC (rev 3865)
@@ -1545,7 +1545,7 @@
extern WN * WN_find_loop_by_index(WN *, ST *, WN_MAP);
extern BOOL WN_has_const_diff(WN *, WN *, int *);
extern BOOL WN_has_compatible_iter_space(WN *, WN *, int *, int *, BOOL);
-
+extern BOOL Identical_stmt(WN *, WN *);
extern BOOL WN_is_assign(WN *);
extern BOOL WN_is_assign_return(WN *);
------------------------------------------------------------------------------
Keep Your Developer Skills Current with LearnDevNow!
The most comprehensive online learning library for Microsoft developers
is just $99.99! Visual Studio, SharePoint, SQL - plus HTML5, CSS3, MVC3,
Metro Style Apps, more. Free future releases when you subscribe now!
http://p.sf.net/sfu/learndevnow-d2d
_______________________________________________
Open64-devel mailing list
[email protected]
https://lists.sourceforge.net/lists/listinfo/open64-devel
