/* Single entry single exit control flow regions.
|
/* Single entry single exit control flow regions.
|
Copyright (C) 2008, 2009, 2010
|
Copyright (C) 2008, 2009, 2010
|
Free Software Foundation, Inc.
|
Free Software Foundation, Inc.
|
Contributed by Jan Sjodin <jan.sjodin@amd.com> and
|
Contributed by Jan Sjodin <jan.sjodin@amd.com> and
|
Sebastian Pop <sebastian.pop@amd.com>.
|
Sebastian Pop <sebastian.pop@amd.com>.
|
|
|
This file is part of GCC.
|
This file is part of GCC.
|
|
|
GCC is free software; you can redistribute it and/or modify
|
GCC is free software; you can redistribute it and/or modify
|
it under the terms of the GNU General Public License as published by
|
it under the terms of the GNU General Public License as published by
|
the Free Software Foundation; either version 3, or (at your option)
|
the Free Software Foundation; either version 3, or (at your option)
|
any later version.
|
any later version.
|
|
|
GCC is distributed in the hope that it will be useful,
|
GCC is distributed in the hope that it will be useful,
|
but WITHOUT ANY WARRANTY; without even the implied warranty of
|
but WITHOUT ANY WARRANTY; without even the implied warranty of
|
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
|
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
|
GNU General Public License for more details.
|
GNU General Public License for more details.
|
|
|
You should have received a copy of the GNU General Public License
|
You should have received a copy of the GNU General Public License
|
along with GCC; see the file COPYING3. If not see
|
along with GCC; see the file COPYING3. If not see
|
<http://www.gnu.org/licenses/>. */
|
<http://www.gnu.org/licenses/>. */
|
|
|
#include "config.h"
|
#include "config.h"
|
#include "system.h"
|
#include "system.h"
|
#include "coretypes.h"
|
#include "coretypes.h"
|
#include "tm.h"
|
#include "tm.h"
|
#include "ggc.h"
|
#include "ggc.h"
|
#include "tree.h"
|
#include "tree.h"
|
#include "rtl.h"
|
#include "rtl.h"
|
#include "basic-block.h"
|
#include "basic-block.h"
|
#include "diagnostic.h"
|
#include "diagnostic.h"
|
#include "tree-flow.h"
|
#include "tree-flow.h"
|
#include "toplev.h"
|
#include "toplev.h"
|
#include "tree-dump.h"
|
#include "tree-dump.h"
|
#include "timevar.h"
|
#include "timevar.h"
|
#include "cfgloop.h"
|
#include "cfgloop.h"
|
#include "tree-chrec.h"
|
#include "tree-chrec.h"
|
#include "tree-data-ref.h"
|
#include "tree-data-ref.h"
|
#include "tree-scalar-evolution.h"
|
#include "tree-scalar-evolution.h"
|
#include "tree-pass.h"
|
#include "tree-pass.h"
|
#include "domwalk.h"
|
#include "domwalk.h"
|
#include "value-prof.h"
|
#include "value-prof.h"
|
#include "pointer-set.h"
|
#include "pointer-set.h"
|
#include "gimple.h"
|
#include "gimple.h"
|
#include "sese.h"
|
#include "sese.h"
|
|
|
/* Print to stderr the element ELT. */
|
/* Print to stderr the element ELT. */
|
|
|
static void
|
static void
|
debug_rename_elt (rename_map_elt elt)
|
debug_rename_elt (rename_map_elt elt)
|
{
|
{
|
fprintf (stderr, "(");
|
fprintf (stderr, "(");
|
print_generic_expr (stderr, elt->old_name, 0);
|
print_generic_expr (stderr, elt->old_name, 0);
|
fprintf (stderr, ", ");
|
fprintf (stderr, ", ");
|
print_generic_expr (stderr, elt->expr, 0);
|
print_generic_expr (stderr, elt->expr, 0);
|
fprintf (stderr, ")\n");
|
fprintf (stderr, ")\n");
|
}
|
}
|
|
|
/* Helper function for debug_rename_map. */
|
/* Helper function for debug_rename_map. */
|
|
|
static int
|
static int
|
debug_rename_map_1 (void **slot, void *s ATTRIBUTE_UNUSED)
|
debug_rename_map_1 (void **slot, void *s ATTRIBUTE_UNUSED)
|
{
|
{
|
struct rename_map_elt_s *entry = (struct rename_map_elt_s *) *slot;
|
struct rename_map_elt_s *entry = (struct rename_map_elt_s *) *slot;
|
debug_rename_elt (entry);
|
debug_rename_elt (entry);
|
return 1;
|
return 1;
|
}
|
}
|
|
|
/* Print to stderr all the elements of MAP. */
|
/* Print to stderr all the elements of MAP. */
|
|
|
void
|
void
|
debug_rename_map (htab_t map)
|
debug_rename_map (htab_t map)
|
{
|
{
|
htab_traverse (map, debug_rename_map_1, NULL);
|
htab_traverse (map, debug_rename_map_1, NULL);
|
}
|
}
|
|
|
/* Computes a hash function for database element ELT. */
|
/* Computes a hash function for database element ELT. */
|
|
|
hashval_t
|
hashval_t
|
rename_map_elt_info (const void *elt)
|
rename_map_elt_info (const void *elt)
|
{
|
{
|
return SSA_NAME_VERSION (((const struct rename_map_elt_s *) elt)->old_name);
|
return SSA_NAME_VERSION (((const struct rename_map_elt_s *) elt)->old_name);
|
}
|
}
|
|
|
/* Compares database elements E1 and E2. */
|
/* Compares database elements E1 and E2. */
|
|
|
int
|
int
|
eq_rename_map_elts (const void *e1, const void *e2)
|
eq_rename_map_elts (const void *e1, const void *e2)
|
{
|
{
|
const struct rename_map_elt_s *elt1 = (const struct rename_map_elt_s *) e1;
|
const struct rename_map_elt_s *elt1 = (const struct rename_map_elt_s *) e1;
|
const struct rename_map_elt_s *elt2 = (const struct rename_map_elt_s *) e2;
|
const struct rename_map_elt_s *elt2 = (const struct rename_map_elt_s *) e2;
|
|
|
return (elt1->old_name == elt2->old_name);
|
return (elt1->old_name == elt2->old_name);
|
}
|
}
|
|
|
|
|
|
|
/* Print to stderr the element ELT. */
|
/* Print to stderr the element ELT. */
|
|
|
static void
|
static void
|
debug_ivtype_elt (ivtype_map_elt elt)
|
debug_ivtype_elt (ivtype_map_elt elt)
|
{
|
{
|
fprintf (stderr, "(%s, ", elt->cloog_iv);
|
fprintf (stderr, "(%s, ", elt->cloog_iv);
|
print_generic_expr (stderr, elt->type, 0);
|
print_generic_expr (stderr, elt->type, 0);
|
fprintf (stderr, ")\n");
|
fprintf (stderr, ")\n");
|
}
|
}
|
|
|
/* Helper function for debug_ivtype_map. */
|
/* Helper function for debug_ivtype_map. */
|
|
|
static int
|
static int
|
debug_ivtype_map_1 (void **slot, void *s ATTRIBUTE_UNUSED)
|
debug_ivtype_map_1 (void **slot, void *s ATTRIBUTE_UNUSED)
|
{
|
{
|
struct ivtype_map_elt_s *entry = (struct ivtype_map_elt_s *) *slot;
|
struct ivtype_map_elt_s *entry = (struct ivtype_map_elt_s *) *slot;
|
debug_ivtype_elt (entry);
|
debug_ivtype_elt (entry);
|
return 1;
|
return 1;
|
}
|
}
|
|
|
/* Print to stderr all the elements of MAP. */
|
/* Print to stderr all the elements of MAP. */
|
|
|
void
|
void
|
debug_ivtype_map (htab_t map)
|
debug_ivtype_map (htab_t map)
|
{
|
{
|
htab_traverse (map, debug_ivtype_map_1, NULL);
|
htab_traverse (map, debug_ivtype_map_1, NULL);
|
}
|
}
|
|
|
/* Computes a hash function for database element ELT. */
|
/* Computes a hash function for database element ELT. */
|
|
|
hashval_t
|
hashval_t
|
ivtype_map_elt_info (const void *elt)
|
ivtype_map_elt_info (const void *elt)
|
{
|
{
|
return htab_hash_pointer (((const struct ivtype_map_elt_s *) elt)->cloog_iv);
|
return htab_hash_pointer (((const struct ivtype_map_elt_s *) elt)->cloog_iv);
|
}
|
}
|
|
|
/* Compares database elements E1 and E2. */
|
/* Compares database elements E1 and E2. */
|
|
|
int
|
int
|
eq_ivtype_map_elts (const void *e1, const void *e2)
|
eq_ivtype_map_elts (const void *e1, const void *e2)
|
{
|
{
|
const struct ivtype_map_elt_s *elt1 = (const struct ivtype_map_elt_s *) e1;
|
const struct ivtype_map_elt_s *elt1 = (const struct ivtype_map_elt_s *) e1;
|
const struct ivtype_map_elt_s *elt2 = (const struct ivtype_map_elt_s *) e2;
|
const struct ivtype_map_elt_s *elt2 = (const struct ivtype_map_elt_s *) e2;
|
|
|
return (elt1->cloog_iv == elt2->cloog_iv);
|
return (elt1->cloog_iv == elt2->cloog_iv);
|
}
|
}
|
|
|
|
|
|
|
/* Record LOOP as occuring in REGION. */
|
/* Record LOOP as occuring in REGION. */
|
|
|
static void
|
static void
|
sese_record_loop (sese region, loop_p loop)
|
sese_record_loop (sese region, loop_p loop)
|
{
|
{
|
if (sese_contains_loop (region, loop))
|
if (sese_contains_loop (region, loop))
|
return;
|
return;
|
|
|
bitmap_set_bit (SESE_LOOPS (region), loop->num);
|
bitmap_set_bit (SESE_LOOPS (region), loop->num);
|
VEC_safe_push (loop_p, heap, SESE_LOOP_NEST (region), loop);
|
VEC_safe_push (loop_p, heap, SESE_LOOP_NEST (region), loop);
|
}
|
}
|
|
|
/* Build the loop nests contained in REGION. Returns true when the
|
/* Build the loop nests contained in REGION. Returns true when the
|
operation was successful. */
|
operation was successful. */
|
|
|
void
|
void
|
build_sese_loop_nests (sese region)
|
build_sese_loop_nests (sese region)
|
{
|
{
|
unsigned i;
|
unsigned i;
|
basic_block bb;
|
basic_block bb;
|
struct loop *loop0, *loop1;
|
struct loop *loop0, *loop1;
|
|
|
FOR_EACH_BB (bb)
|
FOR_EACH_BB (bb)
|
if (bb_in_sese_p (bb, region))
|
if (bb_in_sese_p (bb, region))
|
{
|
{
|
struct loop *loop = bb->loop_father;
|
struct loop *loop = bb->loop_father;
|
|
|
/* Only add loops if they are completely contained in the SCoP. */
|
/* Only add loops if they are completely contained in the SCoP. */
|
if (loop->header == bb
|
if (loop->header == bb
|
&& bb_in_sese_p (loop->latch, region))
|
&& bb_in_sese_p (loop->latch, region))
|
sese_record_loop (region, loop);
|
sese_record_loop (region, loop);
|
}
|
}
|
|
|
/* Make sure that the loops in the SESE_LOOP_NEST are ordered. It
|
/* Make sure that the loops in the SESE_LOOP_NEST are ordered. It
|
can be the case that an inner loop is inserted before an outer
|
can be the case that an inner loop is inserted before an outer
|
loop. To avoid this, semi-sort once. */
|
loop. To avoid this, semi-sort once. */
|
for (i = 0; VEC_iterate (loop_p, SESE_LOOP_NEST (region), i, loop0); i++)
|
for (i = 0; VEC_iterate (loop_p, SESE_LOOP_NEST (region), i, loop0); i++)
|
{
|
{
|
if (VEC_length (loop_p, SESE_LOOP_NEST (region)) == i + 1)
|
if (VEC_length (loop_p, SESE_LOOP_NEST (region)) == i + 1)
|
break;
|
break;
|
|
|
loop1 = VEC_index (loop_p, SESE_LOOP_NEST (region), i + 1);
|
loop1 = VEC_index (loop_p, SESE_LOOP_NEST (region), i + 1);
|
if (loop0->num > loop1->num)
|
if (loop0->num > loop1->num)
|
{
|
{
|
VEC_replace (loop_p, SESE_LOOP_NEST (region), i, loop1);
|
VEC_replace (loop_p, SESE_LOOP_NEST (region), i, loop1);
|
VEC_replace (loop_p, SESE_LOOP_NEST (region), i + 1, loop0);
|
VEC_replace (loop_p, SESE_LOOP_NEST (region), i + 1, loop0);
|
}
|
}
|
}
|
}
|
}
|
}
|
|
|
/* For a USE in BB, if BB is outside REGION, mark the USE in the
|
/* For a USE in BB, if BB is outside REGION, mark the USE in the
|
LIVEOUTS set. */
|
LIVEOUTS set. */
|
|
|
static void
|
static void
|
sese_build_liveouts_use (sese region, bitmap liveouts, basic_block bb,
|
sese_build_liveouts_use (sese region, bitmap liveouts, basic_block bb,
|
tree use)
|
tree use)
|
{
|
{
|
unsigned ver;
|
unsigned ver;
|
basic_block def_bb;
|
basic_block def_bb;
|
|
|
if (TREE_CODE (use) != SSA_NAME)
|
if (TREE_CODE (use) != SSA_NAME)
|
return;
|
return;
|
|
|
ver = SSA_NAME_VERSION (use);
|
ver = SSA_NAME_VERSION (use);
|
def_bb = gimple_bb (SSA_NAME_DEF_STMT (use));
|
def_bb = gimple_bb (SSA_NAME_DEF_STMT (use));
|
|
|
if (!def_bb
|
if (!def_bb
|
|| !bb_in_sese_p (def_bb, region)
|
|| !bb_in_sese_p (def_bb, region)
|
|| bb_in_sese_p (bb, region))
|
|| bb_in_sese_p (bb, region))
|
return;
|
return;
|
|
|
bitmap_set_bit (liveouts, ver);
|
bitmap_set_bit (liveouts, ver);
|
}
|
}
|
|
|
/* Marks for rewrite all the SSA_NAMES defined in REGION and that are
|
/* Marks for rewrite all the SSA_NAMES defined in REGION and that are
|
used in BB that is outside of the REGION. */
|
used in BB that is outside of the REGION. */
|
|
|
static void
|
static void
|
sese_build_liveouts_bb (sese region, bitmap liveouts, basic_block bb)
|
sese_build_liveouts_bb (sese region, bitmap liveouts, basic_block bb)
|
{
|
{
|
gimple_stmt_iterator bsi;
|
gimple_stmt_iterator bsi;
|
edge e;
|
edge e;
|
edge_iterator ei;
|
edge_iterator ei;
|
ssa_op_iter iter;
|
ssa_op_iter iter;
|
use_operand_p use_p;
|
use_operand_p use_p;
|
|
|
FOR_EACH_EDGE (e, ei, bb->succs)
|
FOR_EACH_EDGE (e, ei, bb->succs)
|
for (bsi = gsi_start_phis (e->dest); !gsi_end_p (bsi); gsi_next (&bsi))
|
for (bsi = gsi_start_phis (e->dest); !gsi_end_p (bsi); gsi_next (&bsi))
|
sese_build_liveouts_use (region, liveouts, bb,
|
sese_build_liveouts_use (region, liveouts, bb,
|
PHI_ARG_DEF_FROM_EDGE (gsi_stmt (bsi), e));
|
PHI_ARG_DEF_FROM_EDGE (gsi_stmt (bsi), e));
|
|
|
for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
|
for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
|
{
|
{
|
gimple stmt = gsi_stmt (bsi);
|
gimple stmt = gsi_stmt (bsi);
|
|
|
if (is_gimple_debug (stmt))
|
if (is_gimple_debug (stmt))
|
continue;
|
continue;
|
|
|
FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES)
|
FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES)
|
sese_build_liveouts_use (region, liveouts, bb, USE_FROM_PTR (use_p));
|
sese_build_liveouts_use (region, liveouts, bb, USE_FROM_PTR (use_p));
|
}
|
}
|
}
|
}
|
|
|
/* For a USE in BB, return true if BB is outside REGION and it's not
|
/* For a USE in BB, return true if BB is outside REGION and it's not
|
in the LIVEOUTS set. */
|
in the LIVEOUTS set. */
|
|
|
static bool
|
static bool
|
sese_bad_liveouts_use (sese region, bitmap liveouts, basic_block bb,
|
sese_bad_liveouts_use (sese region, bitmap liveouts, basic_block bb,
|
tree use)
|
tree use)
|
{
|
{
|
unsigned ver;
|
unsigned ver;
|
basic_block def_bb;
|
basic_block def_bb;
|
|
|
if (TREE_CODE (use) != SSA_NAME)
|
if (TREE_CODE (use) != SSA_NAME)
|
return false;
|
return false;
|
|
|
ver = SSA_NAME_VERSION (use);
|
ver = SSA_NAME_VERSION (use);
|
|
|
/* If it's in liveouts, the variable will get a new PHI node, and
|
/* If it's in liveouts, the variable will get a new PHI node, and
|
the debug use will be properly adjusted. */
|
the debug use will be properly adjusted. */
|
if (bitmap_bit_p (liveouts, ver))
|
if (bitmap_bit_p (liveouts, ver))
|
return false;
|
return false;
|
|
|
def_bb = gimple_bb (SSA_NAME_DEF_STMT (use));
|
def_bb = gimple_bb (SSA_NAME_DEF_STMT (use));
|
|
|
if (!def_bb
|
if (!def_bb
|
|| !bb_in_sese_p (def_bb, region)
|
|| !bb_in_sese_p (def_bb, region)
|
|| bb_in_sese_p (bb, region))
|
|| bb_in_sese_p (bb, region))
|
return false;
|
return false;
|
|
|
return true;
|
return true;
|
}
|
}
|
|
|
/* Reset debug stmts that reference SSA_NAMES defined in REGION that
|
/* Reset debug stmts that reference SSA_NAMES defined in REGION that
|
are not marked as liveouts. */
|
are not marked as liveouts. */
|
|
|
static void
|
static void
|
sese_reset_debug_liveouts_bb (sese region, bitmap liveouts, basic_block bb)
|
sese_reset_debug_liveouts_bb (sese region, bitmap liveouts, basic_block bb)
|
{
|
{
|
gimple_stmt_iterator bsi;
|
gimple_stmt_iterator bsi;
|
ssa_op_iter iter;
|
ssa_op_iter iter;
|
use_operand_p use_p;
|
use_operand_p use_p;
|
|
|
for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
|
for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
|
{
|
{
|
gimple stmt = gsi_stmt (bsi);
|
gimple stmt = gsi_stmt (bsi);
|
|
|
if (!is_gimple_debug (stmt))
|
if (!is_gimple_debug (stmt))
|
continue;
|
continue;
|
|
|
FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES)
|
FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES)
|
if (sese_bad_liveouts_use (region, liveouts, bb,
|
if (sese_bad_liveouts_use (region, liveouts, bb,
|
USE_FROM_PTR (use_p)))
|
USE_FROM_PTR (use_p)))
|
{
|
{
|
gimple_debug_bind_reset_value (stmt);
|
gimple_debug_bind_reset_value (stmt);
|
update_stmt (stmt);
|
update_stmt (stmt);
|
break;
|
break;
|
}
|
}
|
}
|
}
|
}
|
}
|
|
|
/* Build the LIVEOUTS of REGION: the set of variables defined inside
|
/* Build the LIVEOUTS of REGION: the set of variables defined inside
|
and used outside the REGION. */
|
and used outside the REGION. */
|
|
|
static void
|
static void
|
sese_build_liveouts (sese region, bitmap liveouts)
|
sese_build_liveouts (sese region, bitmap liveouts)
|
{
|
{
|
basic_block bb;
|
basic_block bb;
|
|
|
FOR_EACH_BB (bb)
|
FOR_EACH_BB (bb)
|
sese_build_liveouts_bb (region, liveouts, bb);
|
sese_build_liveouts_bb (region, liveouts, bb);
|
if (MAY_HAVE_DEBUG_INSNS)
|
if (MAY_HAVE_DEBUG_INSNS)
|
FOR_EACH_BB (bb)
|
FOR_EACH_BB (bb)
|
sese_reset_debug_liveouts_bb (region, liveouts, bb);
|
sese_reset_debug_liveouts_bb (region, liveouts, bb);
|
}
|
}
|
|
|
/* Builds a new SESE region from edges ENTRY and EXIT. */
|
/* Builds a new SESE region from edges ENTRY and EXIT. */
|
|
|
sese
|
sese
|
new_sese (edge entry, edge exit)
|
new_sese (edge entry, edge exit)
|
{
|
{
|
sese region = XNEW (struct sese_s);
|
sese region = XNEW (struct sese_s);
|
|
|
SESE_ENTRY (region) = entry;
|
SESE_ENTRY (region) = entry;
|
SESE_EXIT (region) = exit;
|
SESE_EXIT (region) = exit;
|
SESE_LOOPS (region) = BITMAP_ALLOC (NULL);
|
SESE_LOOPS (region) = BITMAP_ALLOC (NULL);
|
SESE_LOOP_NEST (region) = VEC_alloc (loop_p, heap, 3);
|
SESE_LOOP_NEST (region) = VEC_alloc (loop_p, heap, 3);
|
SESE_ADD_PARAMS (region) = true;
|
SESE_ADD_PARAMS (region) = true;
|
SESE_PARAMS (region) = VEC_alloc (tree, heap, 3);
|
SESE_PARAMS (region) = VEC_alloc (tree, heap, 3);
|
|
|
return region;
|
return region;
|
}
|
}
|
|
|
/* Deletes REGION. */
|
/* Deletes REGION. */
|
|
|
void
|
void
|
free_sese (sese region)
|
free_sese (sese region)
|
{
|
{
|
if (SESE_LOOPS (region))
|
if (SESE_LOOPS (region))
|
SESE_LOOPS (region) = BITMAP_ALLOC (NULL);
|
SESE_LOOPS (region) = BITMAP_ALLOC (NULL);
|
|
|
VEC_free (tree, heap, SESE_PARAMS (region));
|
VEC_free (tree, heap, SESE_PARAMS (region));
|
VEC_free (loop_p, heap, SESE_LOOP_NEST (region));
|
VEC_free (loop_p, heap, SESE_LOOP_NEST (region));
|
|
|
XDELETE (region);
|
XDELETE (region);
|
}
|
}
|
|
|
/* Add exit phis for USE on EXIT. */
|
/* Add exit phis for USE on EXIT. */
|
|
|
static void
|
static void
|
sese_add_exit_phis_edge (basic_block exit, tree use, edge false_e, edge true_e)
|
sese_add_exit_phis_edge (basic_block exit, tree use, edge false_e, edge true_e)
|
{
|
{
|
gimple phi = create_phi_node (use, exit);
|
gimple phi = create_phi_node (use, exit);
|
|
|
create_new_def_for (gimple_phi_result (phi), phi,
|
create_new_def_for (gimple_phi_result (phi), phi,
|
gimple_phi_result_ptr (phi));
|
gimple_phi_result_ptr (phi));
|
add_phi_arg (phi, use, false_e, UNKNOWN_LOCATION);
|
add_phi_arg (phi, use, false_e, UNKNOWN_LOCATION);
|
add_phi_arg (phi, use, true_e, UNKNOWN_LOCATION);
|
add_phi_arg (phi, use, true_e, UNKNOWN_LOCATION);
|
}
|
}
|
|
|
/* Insert in the block BB phi nodes for variables defined in REGION
|
/* Insert in the block BB phi nodes for variables defined in REGION
|
and used outside the REGION. The code generation moves REGION in
|
and used outside the REGION. The code generation moves REGION in
|
the else clause of an "if (1)" and generates code in the then
|
the else clause of an "if (1)" and generates code in the then
|
clause that is at this point empty:
|
clause that is at this point empty:
|
|
|
| if (1)
|
| if (1)
|
| empty;
|
| empty;
|
| else
|
| else
|
| REGION;
|
| REGION;
|
*/
|
*/
|
|
|
void
|
void
|
sese_insert_phis_for_liveouts (sese region, basic_block bb,
|
sese_insert_phis_for_liveouts (sese region, basic_block bb,
|
edge false_e, edge true_e)
|
edge false_e, edge true_e)
|
{
|
{
|
unsigned i;
|
unsigned i;
|
bitmap_iterator bi;
|
bitmap_iterator bi;
|
bitmap liveouts = BITMAP_ALLOC (NULL);
|
bitmap liveouts = BITMAP_ALLOC (NULL);
|
|
|
update_ssa (TODO_update_ssa);
|
update_ssa (TODO_update_ssa);
|
|
|
sese_build_liveouts (region, liveouts);
|
sese_build_liveouts (region, liveouts);
|
EXECUTE_IF_SET_IN_BITMAP (liveouts, 0, i, bi)
|
EXECUTE_IF_SET_IN_BITMAP (liveouts, 0, i, bi)
|
sese_add_exit_phis_edge (bb, ssa_name (i), false_e, true_e);
|
sese_add_exit_phis_edge (bb, ssa_name (i), false_e, true_e);
|
BITMAP_FREE (liveouts);
|
BITMAP_FREE (liveouts);
|
|
|
update_ssa (TODO_update_ssa);
|
update_ssa (TODO_update_ssa);
|
}
|
}
|
|
|
/* Get the definition of NAME before the SESE. Keep track of the
|
/* Get the definition of NAME before the SESE. Keep track of the
|
basic blocks that have been VISITED in a bitmap. */
|
basic blocks that have been VISITED in a bitmap. */
|
|
|
static tree
|
static tree
|
get_vdef_before_sese (sese region, tree name, sbitmap visited)
|
get_vdef_before_sese (sese region, tree name, sbitmap visited)
|
{
|
{
|
unsigned i;
|
unsigned i;
|
gimple stmt = SSA_NAME_DEF_STMT (name);
|
gimple stmt = SSA_NAME_DEF_STMT (name);
|
basic_block def_bb = gimple_bb (stmt);
|
basic_block def_bb = gimple_bb (stmt);
|
|
|
if (!def_bb || !bb_in_sese_p (def_bb, region))
|
if (!def_bb || !bb_in_sese_p (def_bb, region))
|
return name;
|
return name;
|
|
|
if (TEST_BIT (visited, def_bb->index))
|
if (TEST_BIT (visited, def_bb->index))
|
return NULL_TREE;
|
return NULL_TREE;
|
|
|
SET_BIT (visited, def_bb->index);
|
SET_BIT (visited, def_bb->index);
|
|
|
switch (gimple_code (stmt))
|
switch (gimple_code (stmt))
|
{
|
{
|
case GIMPLE_PHI:
|
case GIMPLE_PHI:
|
for (i = 0; i < gimple_phi_num_args (stmt); i++)
|
for (i = 0; i < gimple_phi_num_args (stmt); i++)
|
{
|
{
|
tree arg = gimple_phi_arg_def (stmt, i);
|
tree arg = gimple_phi_arg_def (stmt, i);
|
tree res;
|
tree res;
|
|
|
if (gimple_bb (SSA_NAME_DEF_STMT (arg))
|
if (gimple_bb (SSA_NAME_DEF_STMT (arg))
|
&& def_bb->index == gimple_bb (SSA_NAME_DEF_STMT (arg))->index)
|
&& def_bb->index == gimple_bb (SSA_NAME_DEF_STMT (arg))->index)
|
continue;
|
continue;
|
|
|
res = get_vdef_before_sese (region, arg, visited);
|
res = get_vdef_before_sese (region, arg, visited);
|
if (res)
|
if (res)
|
return res;
|
return res;
|
}
|
}
|
return NULL_TREE;
|
return NULL_TREE;
|
|
|
case GIMPLE_ASSIGN:
|
case GIMPLE_ASSIGN:
|
case GIMPLE_CALL:
|
case GIMPLE_CALL:
|
{
|
{
|
use_operand_p use_p = gimple_vuse_op (stmt);
|
use_operand_p use_p = gimple_vuse_op (stmt);
|
tree use = USE_FROM_PTR (use_p);
|
tree use = USE_FROM_PTR (use_p);
|
|
|
if (def_bb->index == gimple_bb (SSA_NAME_DEF_STMT (use))->index)
|
if (def_bb->index == gimple_bb (SSA_NAME_DEF_STMT (use))->index)
|
RESET_BIT (visited, def_bb->index);
|
RESET_BIT (visited, def_bb->index);
|
|
|
return get_vdef_before_sese (region, use, visited);
|
return get_vdef_before_sese (region, use, visited);
|
}
|
}
|
|
|
default:
|
default:
|
return NULL_TREE;
|
return NULL_TREE;
|
}
|
}
|
}
|
}
|
|
|
/* Adjust a virtual phi node PHI that is placed at the end of the
|
/* Adjust a virtual phi node PHI that is placed at the end of the
|
generated code for SCOP:
|
generated code for SCOP:
|
|
|
| if (1)
|
| if (1)
|
| generated code from REGION;
|
| generated code from REGION;
|
| else
|
| else
|
| REGION;
|
| REGION;
|
|
|
The FALSE_E edge comes from the original code, TRUE_E edge comes
|
The FALSE_E edge comes from the original code, TRUE_E edge comes
|
from the code generated for the SCOP. */
|
from the code generated for the SCOP. */
|
|
|
static void
|
static void
|
sese_adjust_vphi (sese region, gimple phi, edge true_e)
|
sese_adjust_vphi (sese region, gimple phi, edge true_e)
|
{
|
{
|
unsigned i;
|
unsigned i;
|
|
|
gcc_assert (gimple_phi_num_args (phi) == 2);
|
gcc_assert (gimple_phi_num_args (phi) == 2);
|
|
|
for (i = 0; i < gimple_phi_num_args (phi); i++)
|
for (i = 0; i < gimple_phi_num_args (phi); i++)
|
if (gimple_phi_arg_edge (phi, i) == true_e)
|
if (gimple_phi_arg_edge (phi, i) == true_e)
|
{
|
{
|
tree true_arg, false_arg, before_scop_arg;
|
tree true_arg, false_arg, before_scop_arg;
|
sbitmap visited;
|
sbitmap visited;
|
|
|
true_arg = gimple_phi_arg_def (phi, i);
|
true_arg = gimple_phi_arg_def (phi, i);
|
if (!SSA_NAME_IS_DEFAULT_DEF (true_arg))
|
if (!SSA_NAME_IS_DEFAULT_DEF (true_arg))
|
return;
|
return;
|
|
|
false_arg = gimple_phi_arg_def (phi, i == 0 ? 1 : 0);
|
false_arg = gimple_phi_arg_def (phi, i == 0 ? 1 : 0);
|
if (SSA_NAME_IS_DEFAULT_DEF (false_arg))
|
if (SSA_NAME_IS_DEFAULT_DEF (false_arg))
|
return;
|
return;
|
|
|
visited = sbitmap_alloc (last_basic_block);
|
visited = sbitmap_alloc (last_basic_block);
|
sbitmap_zero (visited);
|
sbitmap_zero (visited);
|
before_scop_arg = get_vdef_before_sese (region, false_arg, visited);
|
before_scop_arg = get_vdef_before_sese (region, false_arg, visited);
|
gcc_assert (before_scop_arg != NULL_TREE);
|
gcc_assert (before_scop_arg != NULL_TREE);
|
SET_PHI_ARG_DEF (phi, i, before_scop_arg);
|
SET_PHI_ARG_DEF (phi, i, before_scop_arg);
|
sbitmap_free (visited);
|
sbitmap_free (visited);
|
}
|
}
|
}
|
}
|
|
|
/* Returns the expression associated to OLD_NAME in MAP. */
|
/* Returns the expression associated to OLD_NAME in MAP. */
|
|
|
static tree
|
static tree
|
get_rename (htab_t map, tree old_name)
|
get_rename (htab_t map, tree old_name)
|
{
|
{
|
struct rename_map_elt_s tmp;
|
struct rename_map_elt_s tmp;
|
PTR *slot;
|
PTR *slot;
|
|
|
gcc_assert (TREE_CODE (old_name) == SSA_NAME);
|
gcc_assert (TREE_CODE (old_name) == SSA_NAME);
|
tmp.old_name = old_name;
|
tmp.old_name = old_name;
|
slot = htab_find_slot (map, &tmp, NO_INSERT);
|
slot = htab_find_slot (map, &tmp, NO_INSERT);
|
|
|
if (slot && *slot)
|
if (slot && *slot)
|
return ((rename_map_elt) *slot)->expr;
|
return ((rename_map_elt) *slot)->expr;
|
|
|
return old_name;
|
return old_name;
|
}
|
}
|
|
|
/* Register in MAP the rename tuple (OLD_NAME, EXPR). */
|
/* Register in MAP the rename tuple (OLD_NAME, EXPR). */
|
|
|
void
|
void
|
set_rename (htab_t map, tree old_name, tree expr)
|
set_rename (htab_t map, tree old_name, tree expr)
|
{
|
{
|
struct rename_map_elt_s tmp;
|
struct rename_map_elt_s tmp;
|
PTR *slot;
|
PTR *slot;
|
|
|
if (old_name == expr)
|
if (old_name == expr)
|
return;
|
return;
|
|
|
tmp.old_name = old_name;
|
tmp.old_name = old_name;
|
slot = htab_find_slot (map, &tmp, INSERT);
|
slot = htab_find_slot (map, &tmp, INSERT);
|
|
|
if (!slot)
|
if (!slot)
|
return;
|
return;
|
|
|
if (*slot)
|
if (*slot)
|
free (*slot);
|
free (*slot);
|
|
|
*slot = new_rename_map_elt (old_name, expr);
|
*slot = new_rename_map_elt (old_name, expr);
|
}
|
}
|
|
|
/* Renames the expression T following the tuples (OLD_NAME, EXPR) in
|
/* Renames the expression T following the tuples (OLD_NAME, EXPR) in
|
the rename map M. Returns the expression T after renaming. */
|
the rename map M. Returns the expression T after renaming. */
|
|
|
static tree
|
static tree
|
rename_variables_in_expr (htab_t m, tree t)
|
rename_variables_in_expr (htab_t m, tree t)
|
{
|
{
|
if (!t)
|
if (!t)
|
return t;
|
return t;
|
|
|
if (TREE_CODE (t) == SSA_NAME)
|
if (TREE_CODE (t) == SSA_NAME)
|
return get_rename (m, t);
|
return get_rename (m, t);
|
|
|
switch (TREE_CODE_LENGTH (TREE_CODE (t)))
|
switch (TREE_CODE_LENGTH (TREE_CODE (t)))
|
{
|
{
|
case 3:
|
case 3:
|
TREE_OPERAND (t, 2) = rename_variables_in_expr (m, TREE_OPERAND (t, 2));
|
TREE_OPERAND (t, 2) = rename_variables_in_expr (m, TREE_OPERAND (t, 2));
|
|
|
case 2:
|
case 2:
|
TREE_OPERAND (t, 1) = rename_variables_in_expr (m, TREE_OPERAND (t, 1));
|
TREE_OPERAND (t, 1) = rename_variables_in_expr (m, TREE_OPERAND (t, 1));
|
|
|
case 1:
|
case 1:
|
TREE_OPERAND (t, 0) = rename_variables_in_expr (m, TREE_OPERAND (t, 0));
|
TREE_OPERAND (t, 0) = rename_variables_in_expr (m, TREE_OPERAND (t, 0));
|
|
|
default:
|
default:
|
return t;
|
return t;
|
}
|
}
|
}
|
}
|
|
|
/* Renames all the loop->nb_iterations expressions following the
|
/* Renames all the loop->nb_iterations expressions following the
|
tuples (OLD_NAME, EXPR) in RENAME_MAP. */
|
tuples (OLD_NAME, EXPR) in RENAME_MAP. */
|
|
|
void
|
void
|
rename_nb_iterations (htab_t rename_map)
|
rename_nb_iterations (htab_t rename_map)
|
{
|
{
|
loop_iterator li;
|
loop_iterator li;
|
struct loop *loop;
|
struct loop *loop;
|
|
|
FOR_EACH_LOOP (li, loop, 0)
|
FOR_EACH_LOOP (li, loop, 0)
|
loop->nb_iterations = rename_variables_in_expr (rename_map,
|
loop->nb_iterations = rename_variables_in_expr (rename_map,
|
loop->nb_iterations);
|
loop->nb_iterations);
|
}
|
}
|
|
|
/* Renames all the parameters of SESE following the tuples (OLD_NAME,
|
/* Renames all the parameters of SESE following the tuples (OLD_NAME,
|
EXPR) in RENAME_MAP. */
|
EXPR) in RENAME_MAP. */
|
|
|
void
|
void
|
rename_sese_parameters (htab_t rename_map, sese region)
|
rename_sese_parameters (htab_t rename_map, sese region)
|
{
|
{
|
int i;
|
int i;
|
tree p;
|
tree p;
|
|
|
for (i = 0; VEC_iterate (tree, SESE_PARAMS (region), i, p); i++)
|
for (i = 0; VEC_iterate (tree, SESE_PARAMS (region), i, p); i++)
|
VEC_replace (tree, SESE_PARAMS (region), i,
|
VEC_replace (tree, SESE_PARAMS (region), i,
|
rename_variables_in_expr (rename_map, p));
|
rename_variables_in_expr (rename_map, p));
|
}
|
}
|
|
|
/* Adjusts the phi nodes in the block BB for variables defined in
|
/* Adjusts the phi nodes in the block BB for variables defined in
|
SCOP_REGION and used outside the SCOP_REGION. The code generation
|
SCOP_REGION and used outside the SCOP_REGION. The code generation
|
moves SCOP_REGION in the else clause of an "if (1)" and generates
|
moves SCOP_REGION in the else clause of an "if (1)" and generates
|
code in the then clause:
|
code in the then clause:
|
|
|
| if (1)
|
| if (1)
|
| generated code from REGION;
|
| generated code from REGION;
|
| else
|
| else
|
| REGION;
|
| REGION;
|
|
|
To adjust the phi nodes after the condition, the RENAME_MAP is
|
To adjust the phi nodes after the condition, the RENAME_MAP is
|
used. */
|
used. */
|
|
|
void
|
void
|
sese_adjust_liveout_phis (sese region, htab_t rename_map, basic_block bb,
|
sese_adjust_liveout_phis (sese region, htab_t rename_map, basic_block bb,
|
edge false_e, edge true_e)
|
edge false_e, edge true_e)
|
{
|
{
|
gimple_stmt_iterator si;
|
gimple_stmt_iterator si;
|
|
|
for (si = gsi_start_phis (bb); !gsi_end_p (si); gsi_next (&si))
|
for (si = gsi_start_phis (bb); !gsi_end_p (si); gsi_next (&si))
|
{
|
{
|
unsigned i;
|
unsigned i;
|
unsigned false_i = 0;
|
unsigned false_i = 0;
|
gimple phi = gsi_stmt (si);
|
gimple phi = gsi_stmt (si);
|
tree res = gimple_phi_result (phi);
|
tree res = gimple_phi_result (phi);
|
|
|
if (!is_gimple_reg (res))
|
if (!is_gimple_reg (res))
|
{
|
{
|
sese_adjust_vphi (region, phi, true_e);
|
sese_adjust_vphi (region, phi, true_e);
|
continue;
|
continue;
|
}
|
}
|
|
|
for (i = 0; i < gimple_phi_num_args (phi); i++)
|
for (i = 0; i < gimple_phi_num_args (phi); i++)
|
if (gimple_phi_arg_edge (phi, i) == false_e)
|
if (gimple_phi_arg_edge (phi, i) == false_e)
|
{
|
{
|
false_i = i;
|
false_i = i;
|
break;
|
break;
|
}
|
}
|
|
|
for (i = 0; i < gimple_phi_num_args (phi); i++)
|
for (i = 0; i < gimple_phi_num_args (phi); i++)
|
if (gimple_phi_arg_edge (phi, i) == true_e)
|
if (gimple_phi_arg_edge (phi, i) == true_e)
|
{
|
{
|
tree old_name = gimple_phi_arg_def (phi, false_i);
|
tree old_name = gimple_phi_arg_def (phi, false_i);
|
tree expr = get_rename (rename_map, old_name);
|
tree expr = get_rename (rename_map, old_name);
|
gimple_seq stmts;
|
gimple_seq stmts;
|
|
|
gcc_assert (old_name != expr);
|
gcc_assert (old_name != expr);
|
|
|
if (TREE_CODE (expr) != SSA_NAME
|
if (TREE_CODE (expr) != SSA_NAME
|
&& is_gimple_reg (old_name))
|
&& is_gimple_reg (old_name))
|
{
|
{
|
tree type = TREE_TYPE (old_name);
|
tree type = TREE_TYPE (old_name);
|
tree var = create_tmp_var (type, "var");
|
tree var = create_tmp_var (type, "var");
|
|
|
expr = build2 (MODIFY_EXPR, type, var, expr);
|
expr = build2 (MODIFY_EXPR, type, var, expr);
|
expr = force_gimple_operand (expr, &stmts, true, NULL);
|
expr = force_gimple_operand (expr, &stmts, true, NULL);
|
gsi_insert_seq_on_edge_immediate (true_e, stmts);
|
gsi_insert_seq_on_edge_immediate (true_e, stmts);
|
}
|
}
|
|
|
SET_PHI_ARG_DEF (phi, i, expr);
|
SET_PHI_ARG_DEF (phi, i, expr);
|
set_rename (rename_map, old_name, res);
|
set_rename (rename_map, old_name, res);
|
}
|
}
|
}
|
}
|
}
|
}
|
|
|
/* Rename the SSA_NAMEs used in STMT and that appear in MAP. */
|
/* Rename the SSA_NAMEs used in STMT and that appear in MAP. */
|
|
|
static void
|
static void
|
rename_variables_in_stmt (gimple stmt, htab_t map, gimple_stmt_iterator *insert_gsi)
|
rename_variables_in_stmt (gimple stmt, htab_t map, gimple_stmt_iterator *insert_gsi)
|
{
|
{
|
ssa_op_iter iter;
|
ssa_op_iter iter;
|
use_operand_p use_p;
|
use_operand_p use_p;
|
|
|
FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES)
|
FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES)
|
{
|
{
|
tree use = USE_FROM_PTR (use_p);
|
tree use = USE_FROM_PTR (use_p);
|
tree expr, type_use, type_expr;
|
tree expr, type_use, type_expr;
|
gimple_seq stmts;
|
gimple_seq stmts;
|
|
|
if (TREE_CODE (use) != SSA_NAME)
|
if (TREE_CODE (use) != SSA_NAME)
|
continue;
|
continue;
|
|
|
expr = get_rename (map, use);
|
expr = get_rename (map, use);
|
if (use == expr)
|
if (use == expr)
|
continue;
|
continue;
|
|
|
type_use = TREE_TYPE (use);
|
type_use = TREE_TYPE (use);
|
type_expr = TREE_TYPE (expr);
|
type_expr = TREE_TYPE (expr);
|
|
|
if (type_use != type_expr
|
if (type_use != type_expr
|
|| (TREE_CODE (expr) != SSA_NAME
|
|| (TREE_CODE (expr) != SSA_NAME
|
&& is_gimple_reg (use)))
|
&& is_gimple_reg (use)))
|
{
|
{
|
tree var;
|
tree var;
|
|
|
if (is_gimple_debug (stmt))
|
if (is_gimple_debug (stmt))
|
{
|
{
|
if (gimple_debug_bind_p (stmt))
|
if (gimple_debug_bind_p (stmt))
|
gimple_debug_bind_reset_value (stmt);
|
gimple_debug_bind_reset_value (stmt);
|
else
|
else
|
gcc_unreachable ();
|
gcc_unreachable ();
|
|
|
break;
|
break;
|
}
|
}
|
|
|
var = create_tmp_var (type_use, "var");
|
var = create_tmp_var (type_use, "var");
|
|
|
if (type_use != type_expr)
|
if (type_use != type_expr)
|
expr = fold_convert (type_use, expr);
|
expr = fold_convert (type_use, expr);
|
|
|
expr = build2 (MODIFY_EXPR, type_use, var, expr);
|
expr = build2 (MODIFY_EXPR, type_use, var, expr);
|
expr = force_gimple_operand (expr, &stmts, true, NULL);
|
expr = force_gimple_operand (expr, &stmts, true, NULL);
|
gsi_insert_seq_before (insert_gsi, stmts, GSI_SAME_STMT);
|
gsi_insert_seq_before (insert_gsi, stmts, GSI_SAME_STMT);
|
}
|
}
|
|
|
replace_exp (use_p, expr);
|
replace_exp (use_p, expr);
|
}
|
}
|
|
|
update_stmt (stmt);
|
update_stmt (stmt);
|
}
|
}
|
|
|
/* Returns true if NAME is a parameter of SESE. */
|
/* Returns true if NAME is a parameter of SESE. */
|
|
|
static bool
|
static bool
|
is_parameter (sese region, tree name)
|
is_parameter (sese region, tree name)
|
{
|
{
|
int i;
|
int i;
|
tree p;
|
tree p;
|
|
|
for (i = 0; VEC_iterate (tree, SESE_PARAMS (region), i, p); i++)
|
for (i = 0; VEC_iterate (tree, SESE_PARAMS (region), i, p); i++)
|
if (p == name)
|
if (p == name)
|
return true;
|
return true;
|
|
|
return false;
|
return false;
|
}
|
}
|
|
|
/* Returns true if NAME is an induction variable. */
|
/* Returns true if NAME is an induction variable. */
|
|
|
static bool
|
static bool
|
is_iv (tree name)
|
is_iv (tree name)
|
{
|
{
|
return gimple_code (SSA_NAME_DEF_STMT (name)) == GIMPLE_PHI;
|
return gimple_code (SSA_NAME_DEF_STMT (name)) == GIMPLE_PHI;
|
}
|
}
|
|
|
static void expand_scalar_variables_stmt (gimple, basic_block, sese,
|
static void expand_scalar_variables_stmt (gimple, basic_block, sese,
|
htab_t, gimple_stmt_iterator *);
|
htab_t, gimple_stmt_iterator *);
|
static tree
|
static tree
|
expand_scalar_variables_expr (tree, tree, enum tree_code, tree, basic_block,
|
expand_scalar_variables_expr (tree, tree, enum tree_code, tree, basic_block,
|
sese, htab_t, gimple_stmt_iterator *);
|
sese, htab_t, gimple_stmt_iterator *);
|
|
|
static tree
|
static tree
|
expand_scalar_variables_call (gimple stmt, basic_block bb, sese region,
|
expand_scalar_variables_call (gimple stmt, basic_block bb, sese region,
|
htab_t map, gimple_stmt_iterator *gsi)
|
htab_t map, gimple_stmt_iterator *gsi)
|
{
|
{
|
int i, nargs = gimple_call_num_args (stmt);
|
int i, nargs = gimple_call_num_args (stmt);
|
VEC (tree, gc) *args = VEC_alloc (tree, gc, nargs);
|
VEC (tree, gc) *args = VEC_alloc (tree, gc, nargs);
|
tree fn_type = TREE_TYPE (gimple_call_fn (stmt));
|
tree fn_type = TREE_TYPE (gimple_call_fn (stmt));
|
tree fn = gimple_call_fndecl (stmt);
|
tree fn = gimple_call_fndecl (stmt);
|
tree call_expr, var, lhs;
|
tree call_expr, var, lhs;
|
gimple call;
|
gimple call;
|
|
|
for (i = 0; i < nargs; i++)
|
for (i = 0; i < nargs; i++)
|
{
|
{
|
tree arg = gimple_call_arg (stmt, i);
|
tree arg = gimple_call_arg (stmt, i);
|
tree t = TREE_TYPE (arg);
|
tree t = TREE_TYPE (arg);
|
|
|
var = create_tmp_var (t, "var");
|
var = create_tmp_var (t, "var");
|
arg = expand_scalar_variables_expr (t, arg, TREE_CODE (arg), NULL,
|
arg = expand_scalar_variables_expr (t, arg, TREE_CODE (arg), NULL,
|
bb, region, map, gsi);
|
bb, region, map, gsi);
|
arg = build2 (MODIFY_EXPR, t, var, arg);
|
arg = build2 (MODIFY_EXPR, t, var, arg);
|
arg = force_gimple_operand_gsi (gsi, arg, true, NULL,
|
arg = force_gimple_operand_gsi (gsi, arg, true, NULL,
|
true, GSI_SAME_STMT);
|
true, GSI_SAME_STMT);
|
VEC_quick_push (tree, args, arg);
|
VEC_quick_push (tree, args, arg);
|
}
|
}
|
|
|
lhs = gimple_call_lhs (stmt);
|
lhs = gimple_call_lhs (stmt);
|
var = create_tmp_var (TREE_TYPE (lhs), "var");
|
var = create_tmp_var (TREE_TYPE (lhs), "var");
|
call_expr = build_call_vec (fn_type, fn, args);
|
call_expr = build_call_vec (fn_type, fn, args);
|
call = gimple_build_call_from_tree (call_expr);
|
call = gimple_build_call_from_tree (call_expr);
|
var = make_ssa_name (var, call);
|
var = make_ssa_name (var, call);
|
gimple_call_set_lhs (call, var);
|
gimple_call_set_lhs (call, var);
|
gsi_insert_before (gsi, call, GSI_SAME_STMT);
|
gsi_insert_before (gsi, call, GSI_SAME_STMT);
|
|
|
return var;
|
return var;
|
}
|
}
|
|
|
/* Copies at GSI all the scalar computations on which the ssa_name OP0
|
/* Copies at GSI all the scalar computations on which the ssa_name OP0
|
depends on in the SESE: these are all the scalar variables used in
|
depends on in the SESE: these are all the scalar variables used in
|
the definition of OP0, that are defined outside BB and still in the
|
the definition of OP0, that are defined outside BB and still in the
|
SESE, i.e. not a parameter of the SESE. The expression that is
|
SESE, i.e. not a parameter of the SESE. The expression that is
|
returned contains only induction variables from the generated code:
|
returned contains only induction variables from the generated code:
|
MAP contains the induction variables renaming mapping, and is used
|
MAP contains the induction variables renaming mapping, and is used
|
to translate the names of induction variables. */
|
to translate the names of induction variables. */
|
|
|
static tree
|
static tree
|
expand_scalar_variables_ssa_name (tree type, tree op0, basic_block bb,
|
expand_scalar_variables_ssa_name (tree type, tree op0, basic_block bb,
|
sese region, htab_t map,
|
sese region, htab_t map,
|
gimple_stmt_iterator *gsi)
|
gimple_stmt_iterator *gsi)
|
{
|
{
|
gimple def_stmt;
|
gimple def_stmt;
|
tree new_op;
|
tree new_op;
|
|
|
if (is_parameter (region, op0)
|
if (is_parameter (region, op0)
|
|| is_iv (op0))
|
|| is_iv (op0))
|
return fold_convert (type, get_rename (map, op0));
|
return fold_convert (type, get_rename (map, op0));
|
|
|
def_stmt = SSA_NAME_DEF_STMT (op0);
|
def_stmt = SSA_NAME_DEF_STMT (op0);
|
|
|
/* Check whether we already have a rename for OP0. */
|
/* Check whether we already have a rename for OP0. */
|
new_op = get_rename (map, op0);
|
new_op = get_rename (map, op0);
|
|
|
if (new_op != op0
|
if (new_op != op0
|
&& gimple_bb (SSA_NAME_DEF_STMT (new_op)) == bb)
|
&& gimple_bb (SSA_NAME_DEF_STMT (new_op)) == bb)
|
return fold_convert (type, new_op);
|
return fold_convert (type, new_op);
|
|
|
if (gimple_bb (def_stmt) == bb)
|
if (gimple_bb (def_stmt) == bb)
|
{
|
{
|
/* If the defining statement is in the basic block already
|
/* If the defining statement is in the basic block already
|
we do not need to create a new expression for it, we
|
we do not need to create a new expression for it, we
|
only need to ensure its operands are expanded. */
|
only need to ensure its operands are expanded. */
|
expand_scalar_variables_stmt (def_stmt, bb, region, map, gsi);
|
expand_scalar_variables_stmt (def_stmt, bb, region, map, gsi);
|
return fold_convert (type, new_op);
|
return fold_convert (type, new_op);
|
}
|
}
|
else
|
else
|
{
|
{
|
if (!gimple_bb (def_stmt)
|
if (!gimple_bb (def_stmt)
|
|| !bb_in_sese_p (gimple_bb (def_stmt), region))
|
|| !bb_in_sese_p (gimple_bb (def_stmt), region))
|
return fold_convert (type, new_op);
|
return fold_convert (type, new_op);
|
|
|
switch (gimple_code (def_stmt))
|
switch (gimple_code (def_stmt))
|
{
|
{
|
case GIMPLE_ASSIGN:
|
case GIMPLE_ASSIGN:
|
{
|
{
|
tree var0 = gimple_assign_rhs1 (def_stmt);
|
tree var0 = gimple_assign_rhs1 (def_stmt);
|
enum tree_code subcode = gimple_assign_rhs_code (def_stmt);
|
enum tree_code subcode = gimple_assign_rhs_code (def_stmt);
|
tree var1 = gimple_assign_rhs2 (def_stmt);
|
tree var1 = gimple_assign_rhs2 (def_stmt);
|
tree type = gimple_expr_type (def_stmt);
|
tree type = gimple_expr_type (def_stmt);
|
|
|
return expand_scalar_variables_expr (type, var0, subcode, var1, bb,
|
return expand_scalar_variables_expr (type, var0, subcode, var1, bb,
|
region, map, gsi);
|
region, map, gsi);
|
}
|
}
|
|
|
case GIMPLE_CALL:
|
case GIMPLE_CALL:
|
return expand_scalar_variables_call (def_stmt, bb, region, map, gsi);
|
return expand_scalar_variables_call (def_stmt, bb, region, map, gsi);
|
|
|
default:
|
default:
|
gcc_unreachable ();
|
gcc_unreachable ();
|
return new_op;
|
return new_op;
|
}
|
}
|
}
|
}
|
}
|
}
|
|
|
/* Copies at GSI all the scalar computations on which the expression
|
/* Copies at GSI all the scalar computations on which the expression
|
OP0 CODE OP1 depends on in the SESE: these are all the scalar
|
OP0 CODE OP1 depends on in the SESE: these are all the scalar
|
variables used in OP0 and OP1, defined outside BB and still defined
|
variables used in OP0 and OP1, defined outside BB and still defined
|
in the SESE, i.e. not a parameter of the SESE. The expression that
|
in the SESE, i.e. not a parameter of the SESE. The expression that
|
is returned contains only induction variables from the generated
|
is returned contains only induction variables from the generated
|
code: MAP contains the induction variables renaming mapping, and is
|
code: MAP contains the induction variables renaming mapping, and is
|
used to translate the names of induction variables. */
|
used to translate the names of induction variables. */
|
|
|
static tree
|
static tree
|
expand_scalar_variables_expr (tree type, tree op0, enum tree_code code,
|
expand_scalar_variables_expr (tree type, tree op0, enum tree_code code,
|
tree op1, basic_block bb, sese region,
|
tree op1, basic_block bb, sese region,
|
htab_t map, gimple_stmt_iterator *gsi)
|
htab_t map, gimple_stmt_iterator *gsi)
|
{
|
{
|
if (TREE_CODE_CLASS (code) == tcc_constant
|
if (TREE_CODE_CLASS (code) == tcc_constant
|
|| TREE_CODE_CLASS (code) == tcc_declaration)
|
|| TREE_CODE_CLASS (code) == tcc_declaration)
|
return op0;
|
return op0;
|
|
|
/* For data references we have to duplicate also its memory
|
/* For data references we have to duplicate also its memory
|
indexing. */
|
indexing. */
|
if (TREE_CODE_CLASS (code) == tcc_reference)
|
if (TREE_CODE_CLASS (code) == tcc_reference)
|
{
|
{
|
switch (code)
|
switch (code)
|
{
|
{
|
case REALPART_EXPR:
|
case REALPART_EXPR:
|
case IMAGPART_EXPR:
|
case IMAGPART_EXPR:
|
{
|
{
|
tree op = TREE_OPERAND (op0, 0);
|
tree op = TREE_OPERAND (op0, 0);
|
tree res = expand_scalar_variables_expr
|
tree res = expand_scalar_variables_expr
|
(type, op, TREE_CODE (op), NULL, bb, region, map, gsi);
|
(type, op, TREE_CODE (op), NULL, bb, region, map, gsi);
|
return build1 (code, type, res);
|
return build1 (code, type, res);
|
}
|
}
|
|
|
case INDIRECT_REF:
|
case INDIRECT_REF:
|
{
|
{
|
tree old_name = TREE_OPERAND (op0, 0);
|
tree old_name = TREE_OPERAND (op0, 0);
|
tree expr = expand_scalar_variables_ssa_name
|
tree expr = expand_scalar_variables_ssa_name
|
(type, old_name, bb, region, map, gsi);
|
(type, old_name, bb, region, map, gsi);
|
|
|
if (TREE_CODE (expr) != SSA_NAME
|
if (TREE_CODE (expr) != SSA_NAME
|
&& is_gimple_reg (old_name))
|
&& is_gimple_reg (old_name))
|
{
|
{
|
tree type = TREE_TYPE (old_name);
|
tree type = TREE_TYPE (old_name);
|
tree var = create_tmp_var (type, "var");
|
tree var = create_tmp_var (type, "var");
|
|
|
expr = build2 (MODIFY_EXPR, type, var, expr);
|
expr = build2 (MODIFY_EXPR, type, var, expr);
|
expr = force_gimple_operand_gsi (gsi, expr, true, NULL,
|
expr = force_gimple_operand_gsi (gsi, expr, true, NULL,
|
true, GSI_SAME_STMT);
|
true, GSI_SAME_STMT);
|
}
|
}
|
|
|
return fold_build1 (code, type, expr);
|
return fold_build1 (code, type, expr);
|
}
|
}
|
|
|
case ARRAY_REF:
|
case ARRAY_REF:
|
{
|
{
|
tree op00 = TREE_OPERAND (op0, 0);
|
tree op00 = TREE_OPERAND (op0, 0);
|
tree op01 = TREE_OPERAND (op0, 1);
|
tree op01 = TREE_OPERAND (op0, 1);
|
tree op02 = TREE_OPERAND (op0, 2);
|
tree op02 = TREE_OPERAND (op0, 2);
|
tree op03 = TREE_OPERAND (op0, 3);
|
tree op03 = TREE_OPERAND (op0, 3);
|
tree base = expand_scalar_variables_expr
|
tree base = expand_scalar_variables_expr
|
(TREE_TYPE (op00), op00, TREE_CODE (op00), NULL, bb, region,
|
(TREE_TYPE (op00), op00, TREE_CODE (op00), NULL, bb, region,
|
map, gsi);
|
map, gsi);
|
tree subscript = expand_scalar_variables_expr
|
tree subscript = expand_scalar_variables_expr
|
(TREE_TYPE (op01), op01, TREE_CODE (op01), NULL, bb, region,
|
(TREE_TYPE (op01), op01, TREE_CODE (op01), NULL, bb, region,
|
map, gsi);
|
map, gsi);
|
|
|
return build4 (ARRAY_REF, type, base, subscript, op02, op03);
|
return build4 (ARRAY_REF, type, base, subscript, op02, op03);
|
}
|
}
|
|
|
case COMPONENT_REF:
|
case COMPONENT_REF:
|
return op0;
|
return op0;
|
|
|
default:
|
default:
|
/* The above cases should catch everything. */
|
/* The above cases should catch everything. */
|
gcc_unreachable ();
|
gcc_unreachable ();
|
}
|
}
|
}
|
}
|
|
|
if (TREE_CODE_CLASS (code) == tcc_unary)
|
if (TREE_CODE_CLASS (code) == tcc_unary)
|
{
|
{
|
tree op0_type = TREE_TYPE (op0);
|
tree op0_type = TREE_TYPE (op0);
|
enum tree_code op0_code = TREE_CODE (op0);
|
enum tree_code op0_code = TREE_CODE (op0);
|
tree op0_expr = expand_scalar_variables_expr (op0_type, op0, op0_code,
|
tree op0_expr = expand_scalar_variables_expr (op0_type, op0, op0_code,
|
NULL, bb, region, map, gsi);
|
NULL, bb, region, map, gsi);
|
|
|
return fold_build1 (code, type, op0_expr);
|
return fold_build1 (code, type, op0_expr);
|
}
|
}
|
|
|
if (TREE_CODE_CLASS (code) == tcc_binary
|
if (TREE_CODE_CLASS (code) == tcc_binary
|
|| TREE_CODE_CLASS (code) == tcc_comparison)
|
|| TREE_CODE_CLASS (code) == tcc_comparison)
|
{
|
{
|
tree op0_type = TREE_TYPE (op0);
|
tree op0_type = TREE_TYPE (op0);
|
enum tree_code op0_code = TREE_CODE (op0);
|
enum tree_code op0_code = TREE_CODE (op0);
|
tree op0_expr = expand_scalar_variables_expr (op0_type, op0, op0_code,
|
tree op0_expr = expand_scalar_variables_expr (op0_type, op0, op0_code,
|
NULL, bb, region, map, gsi);
|
NULL, bb, region, map, gsi);
|
tree op1_type = TREE_TYPE (op1);
|
tree op1_type = TREE_TYPE (op1);
|
enum tree_code op1_code = TREE_CODE (op1);
|
enum tree_code op1_code = TREE_CODE (op1);
|
tree op1_expr = expand_scalar_variables_expr (op1_type, op1, op1_code,
|
tree op1_expr = expand_scalar_variables_expr (op1_type, op1, op1_code,
|
NULL, bb, region, map, gsi);
|
NULL, bb, region, map, gsi);
|
|
|
return fold_build2 (code, type, op0_expr, op1_expr);
|
return fold_build2 (code, type, op0_expr, op1_expr);
|
}
|
}
|
|
|
if (code == SSA_NAME)
|
if (code == SSA_NAME)
|
return expand_scalar_variables_ssa_name (type, op0, bb, region, map, gsi);
|
return expand_scalar_variables_ssa_name (type, op0, bb, region, map, gsi);
|
|
|
if (code == ADDR_EXPR)
|
if (code == ADDR_EXPR)
|
{
|
{
|
tree op00 = TREE_OPERAND (op0, 0);
|
tree op00 = TREE_OPERAND (op0, 0);
|
|
|
if (handled_component_p (op00)
|
if (handled_component_p (op00)
|
&& TREE_CODE (op00) == ARRAY_REF)
|
&& TREE_CODE (op00) == ARRAY_REF)
|
{
|
{
|
tree e = expand_scalar_variables_expr (TREE_TYPE (op00), op00,
|
tree e = expand_scalar_variables_expr (TREE_TYPE (op00), op00,
|
TREE_CODE (op00),
|
TREE_CODE (op00),
|
NULL, bb, region, map, gsi);
|
NULL, bb, region, map, gsi);
|
return fold_build1 (code, TREE_TYPE (op0), e);
|
return fold_build1 (code, TREE_TYPE (op0), e);
|
}
|
}
|
|
|
return op0;
|
return op0;
|
}
|
}
|
|
|
gcc_unreachable ();
|
gcc_unreachable ();
|
return NULL;
|
return NULL;
|
}
|
}
|
|
|
/* Copies at the beginning of BB all the scalar computations on which
|
/* Copies at the beginning of BB all the scalar computations on which
|
STMT depends on in the SESE: these are all the scalar variables used
|
STMT depends on in the SESE: these are all the scalar variables used
|
in STMT, defined outside BB and still defined in the SESE, i.e. not a
|
in STMT, defined outside BB and still defined in the SESE, i.e. not a
|
parameter of the SESE. The expression that is returned contains
|
parameter of the SESE. The expression that is returned contains
|
only induction variables from the generated code: MAP contains the
|
only induction variables from the generated code: MAP contains the
|
induction variables renaming mapping, and is used to translate the
|
induction variables renaming mapping, and is used to translate the
|
names of induction variables. */
|
names of induction variables. */
|
|
|
static void
|
static void
|
expand_scalar_variables_stmt (gimple stmt, basic_block bb, sese region,
|
expand_scalar_variables_stmt (gimple stmt, basic_block bb, sese region,
|
htab_t map, gimple_stmt_iterator *gsi)
|
htab_t map, gimple_stmt_iterator *gsi)
|
{
|
{
|
ssa_op_iter iter;
|
ssa_op_iter iter;
|
use_operand_p use_p;
|
use_operand_p use_p;
|
|
|
FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES)
|
FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES)
|
{
|
{
|
tree use = USE_FROM_PTR (use_p);
|
tree use = USE_FROM_PTR (use_p);
|
tree type = TREE_TYPE (use);
|
tree type = TREE_TYPE (use);
|
enum tree_code code = TREE_CODE (use);
|
enum tree_code code = TREE_CODE (use);
|
tree use_expr;
|
tree use_expr;
|
|
|
if (!is_gimple_reg (use))
|
if (!is_gimple_reg (use))
|
continue;
|
continue;
|
|
|
/* Don't expand USE if we already have a rename for it. */
|
/* Don't expand USE if we already have a rename for it. */
|
use_expr = get_rename (map, use);
|
use_expr = get_rename (map, use);
|
if (use_expr != use)
|
if (use_expr != use)
|
continue;
|
continue;
|
|
|
use_expr = expand_scalar_variables_expr (type, use, code, NULL, bb,
|
use_expr = expand_scalar_variables_expr (type, use, code, NULL, bb,
|
region, map, gsi);
|
region, map, gsi);
|
use_expr = fold_convert (type, use_expr);
|
use_expr = fold_convert (type, use_expr);
|
|
|
if (use_expr == use)
|
if (use_expr == use)
|
continue;
|
continue;
|
|
|
if (is_gimple_debug (stmt))
|
if (is_gimple_debug (stmt))
|
{
|
{
|
if (gimple_debug_bind_p (stmt))
|
if (gimple_debug_bind_p (stmt))
|
gimple_debug_bind_reset_value (stmt);
|
gimple_debug_bind_reset_value (stmt);
|
else
|
else
|
gcc_unreachable ();
|
gcc_unreachable ();
|
|
|
break;
|
break;
|
}
|
}
|
|
|
if (TREE_CODE (use_expr) != SSA_NAME)
|
if (TREE_CODE (use_expr) != SSA_NAME)
|
{
|
{
|
tree var = create_tmp_var (type, "var");
|
tree var = create_tmp_var (type, "var");
|
|
|
use_expr = build2 (MODIFY_EXPR, type, var, use_expr);
|
use_expr = build2 (MODIFY_EXPR, type, var, use_expr);
|
use_expr = force_gimple_operand_gsi (gsi, use_expr, true, NULL,
|
use_expr = force_gimple_operand_gsi (gsi, use_expr, true, NULL,
|
true, GSI_SAME_STMT);
|
true, GSI_SAME_STMT);
|
}
|
}
|
|
|
replace_exp (use_p, use_expr);
|
replace_exp (use_p, use_expr);
|
}
|
}
|
|
|
update_stmt (stmt);
|
update_stmt (stmt);
|
}
|
}
|
|
|
/* Copies at the beginning of BB all the scalar computations on which
|
/* Copies at the beginning of BB all the scalar computations on which
|
BB depends on in the SESE: these are all the scalar variables used
|
BB depends on in the SESE: these are all the scalar variables used
|
in BB, defined outside BB and still defined in the SESE, i.e. not a
|
in BB, defined outside BB and still defined in the SESE, i.e. not a
|
parameter of the SESE. The expression that is returned contains
|
parameter of the SESE. The expression that is returned contains
|
only induction variables from the generated code: MAP contains the
|
only induction variables from the generated code: MAP contains the
|
induction variables renaming mapping, and is used to translate the
|
induction variables renaming mapping, and is used to translate the
|
names of induction variables. */
|
names of induction variables. */
|
|
|
static void
|
static void
|
expand_scalar_variables (basic_block bb, sese region, htab_t map)
|
expand_scalar_variables (basic_block bb, sese region, htab_t map)
|
{
|
{
|
gimple_stmt_iterator gsi;
|
gimple_stmt_iterator gsi;
|
|
|
for (gsi = gsi_after_labels (bb); !gsi_end_p (gsi);)
|
for (gsi = gsi_after_labels (bb); !gsi_end_p (gsi);)
|
{
|
{
|
gimple stmt = gsi_stmt (gsi);
|
gimple stmt = gsi_stmt (gsi);
|
expand_scalar_variables_stmt (stmt, bb, region, map, &gsi);
|
expand_scalar_variables_stmt (stmt, bb, region, map, &gsi);
|
gsi_next (&gsi);
|
gsi_next (&gsi);
|
}
|
}
|
}
|
}
|
|
|
/* Rename all the SSA_NAMEs from block BB according to the MAP. */
|
/* Rename all the SSA_NAMEs from block BB according to the MAP. */
|
|
|
static void
|
static void
|
rename_variables (basic_block bb, htab_t map)
|
rename_variables (basic_block bb, htab_t map)
|
{
|
{
|
gimple_stmt_iterator gsi;
|
gimple_stmt_iterator gsi;
|
gimple_stmt_iterator insert_gsi = gsi_start_bb (bb);
|
gimple_stmt_iterator insert_gsi = gsi_start_bb (bb);
|
|
|
for (gsi = gsi_after_labels (bb); !gsi_end_p (gsi); gsi_next (&gsi))
|
for (gsi = gsi_after_labels (bb); !gsi_end_p (gsi); gsi_next (&gsi))
|
rename_variables_in_stmt (gsi_stmt (gsi), map, &insert_gsi);
|
rename_variables_in_stmt (gsi_stmt (gsi), map, &insert_gsi);
|
}
|
}
|
|
|
/* Remove condition from BB. */
|
/* Remove condition from BB. */
|
|
|
static void
|
static void
|
remove_condition (basic_block bb)
|
remove_condition (basic_block bb)
|
{
|
{
|
gimple last = last_stmt (bb);
|
gimple last = last_stmt (bb);
|
|
|
if (last && gimple_code (last) == GIMPLE_COND)
|
if (last && gimple_code (last) == GIMPLE_COND)
|
{
|
{
|
gimple_stmt_iterator gsi = gsi_last_bb (bb);
|
gimple_stmt_iterator gsi = gsi_last_bb (bb);
|
gsi_remove (&gsi, true);
|
gsi_remove (&gsi, true);
|
}
|
}
|
}
|
}
|
|
|
/* Returns the first successor edge of BB with EDGE_TRUE_VALUE flag set. */
|
/* Returns the first successor edge of BB with EDGE_TRUE_VALUE flag set. */
|
|
|
edge
|
edge
|
get_true_edge_from_guard_bb (basic_block bb)
|
get_true_edge_from_guard_bb (basic_block bb)
|
{
|
{
|
edge e;
|
edge e;
|
edge_iterator ei;
|
edge_iterator ei;
|
|
|
FOR_EACH_EDGE (e, ei, bb->succs)
|
FOR_EACH_EDGE (e, ei, bb->succs)
|
if (e->flags & EDGE_TRUE_VALUE)
|
if (e->flags & EDGE_TRUE_VALUE)
|
return e;
|
return e;
|
|
|
gcc_unreachable ();
|
gcc_unreachable ();
|
return NULL;
|
return NULL;
|
}
|
}
|
|
|
/* Returns the first successor edge of BB with EDGE_TRUE_VALUE flag cleared. */
|
/* Returns the first successor edge of BB with EDGE_TRUE_VALUE flag cleared. */
|
|
|
edge
|
edge
|
get_false_edge_from_guard_bb (basic_block bb)
|
get_false_edge_from_guard_bb (basic_block bb)
|
{
|
{
|
edge e;
|
edge e;
|
edge_iterator ei;
|
edge_iterator ei;
|
|
|
FOR_EACH_EDGE (e, ei, bb->succs)
|
FOR_EACH_EDGE (e, ei, bb->succs)
|
if (!(e->flags & EDGE_TRUE_VALUE))
|
if (!(e->flags & EDGE_TRUE_VALUE))
|
return e;
|
return e;
|
|
|
gcc_unreachable ();
|
gcc_unreachable ();
|
return NULL;
|
return NULL;
|
}
|
}
|
|
|
/* Returns true when NAME is defined in LOOP. */
|
/* Returns true when NAME is defined in LOOP. */
|
|
|
static bool
|
static bool
|
name_defined_in_loop_p (tree name, loop_p loop)
|
name_defined_in_loop_p (tree name, loop_p loop)
|
{
|
{
|
return !SSA_NAME_IS_DEFAULT_DEF (name)
|
return !SSA_NAME_IS_DEFAULT_DEF (name)
|
&& gimple_bb (SSA_NAME_DEF_STMT (name))->loop_father == loop;
|
&& gimple_bb (SSA_NAME_DEF_STMT (name))->loop_father == loop;
|
}
|
}
|
|
|
/* Returns true when EXPR contains SSA_NAMEs defined in LOOP. */
|
/* Returns true when EXPR contains SSA_NAMEs defined in LOOP. */
|
|
|
static bool
|
static bool
|
expr_defined_in_loop_p (tree expr, loop_p loop)
|
expr_defined_in_loop_p (tree expr, loop_p loop)
|
{
|
{
|
switch (TREE_CODE_LENGTH (TREE_CODE (expr)))
|
switch (TREE_CODE_LENGTH (TREE_CODE (expr)))
|
{
|
{
|
case 3:
|
case 3:
|
return expr_defined_in_loop_p (TREE_OPERAND (expr, 0), loop)
|
return expr_defined_in_loop_p (TREE_OPERAND (expr, 0), loop)
|
|| expr_defined_in_loop_p (TREE_OPERAND (expr, 1), loop)
|
|| expr_defined_in_loop_p (TREE_OPERAND (expr, 1), loop)
|
|| expr_defined_in_loop_p (TREE_OPERAND (expr, 2), loop);
|
|| expr_defined_in_loop_p (TREE_OPERAND (expr, 2), loop);
|
|
|
case 2:
|
case 2:
|
return expr_defined_in_loop_p (TREE_OPERAND (expr, 0), loop)
|
return expr_defined_in_loop_p (TREE_OPERAND (expr, 0), loop)
|
|| expr_defined_in_loop_p (TREE_OPERAND (expr, 1), loop);
|
|| expr_defined_in_loop_p (TREE_OPERAND (expr, 1), loop);
|
|
|
case 1:
|
case 1:
|
return expr_defined_in_loop_p (TREE_OPERAND (expr, 0), loop);
|
return expr_defined_in_loop_p (TREE_OPERAND (expr, 0), loop);
|
|
|
case 0:
|
case 0:
|
return TREE_CODE (expr) == SSA_NAME
|
return TREE_CODE (expr) == SSA_NAME
|
&& name_defined_in_loop_p (expr, loop);
|
&& name_defined_in_loop_p (expr, loop);
|
|
|
default:
|
default:
|
return false;
|
return false;
|
}
|
}
|
}
|
}
|
|
|
/* Returns the gimple statement that uses NAME outside the loop it is
|
/* Returns the gimple statement that uses NAME outside the loop it is
|
defined in, returns NULL if there is no such loop close phi node.
|
defined in, returns NULL if there is no such loop close phi node.
|
An invariant of the loop closed SSA form is that the only use of a
|
An invariant of the loop closed SSA form is that the only use of a
|
variable, outside the loop it is defined in, is in the loop close
|
variable, outside the loop it is defined in, is in the loop close
|
phi node that just follows the loop. */
|
phi node that just follows the loop. */
|
|
|
static gimple
|
static gimple
|
alive_after_loop (tree name)
|
alive_after_loop (tree name)
|
{
|
{
|
use_operand_p use_p;
|
use_operand_p use_p;
|
imm_use_iterator imm_iter;
|
imm_use_iterator imm_iter;
|
loop_p loop = gimple_bb (SSA_NAME_DEF_STMT (name))->loop_father;
|
loop_p loop = gimple_bb (SSA_NAME_DEF_STMT (name))->loop_father;
|
|
|
FOR_EACH_IMM_USE_FAST (use_p, imm_iter, name)
|
FOR_EACH_IMM_USE_FAST (use_p, imm_iter, name)
|
{
|
{
|
gimple stmt = USE_STMT (use_p);
|
gimple stmt = USE_STMT (use_p);
|
|
|
if (gimple_code (stmt) == GIMPLE_PHI
|
if (gimple_code (stmt) == GIMPLE_PHI
|
&& gimple_bb (stmt)->loop_father != loop)
|
&& gimple_bb (stmt)->loop_father != loop)
|
return stmt;
|
return stmt;
|
}
|
}
|
|
|
return NULL;
|
return NULL;
|
}
|
}
|
|
|
/* Return true if a close phi has not yet been inserted for the use of
|
/* Return true if a close phi has not yet been inserted for the use of
|
variable NAME on the single exit of LOOP. */
|
variable NAME on the single exit of LOOP. */
|
|
|
static bool
|
static bool
|
close_phi_not_yet_inserted_p (loop_p loop, tree name)
|
close_phi_not_yet_inserted_p (loop_p loop, tree name)
|
{
|
{
|
gimple_stmt_iterator psi;
|
gimple_stmt_iterator psi;
|
basic_block bb = single_exit (loop)->dest;
|
basic_block bb = single_exit (loop)->dest;
|
|
|
for (psi = gsi_start_phis (bb); !gsi_end_p (psi); gsi_next (&psi))
|
for (psi = gsi_start_phis (bb); !gsi_end_p (psi); gsi_next (&psi))
|
if (gimple_phi_arg_def (gsi_stmt (psi), 0) == name)
|
if (gimple_phi_arg_def (gsi_stmt (psi), 0) == name)
|
return false;
|
return false;
|
|
|
return true;
|
return true;
|
}
|
}
|
|
|
/* A structure for passing parameters to add_loop_exit_phis. */
|
/* A structure for passing parameters to add_loop_exit_phis. */
|
|
|
typedef struct alep {
|
typedef struct alep {
|
loop_p loop;
|
loop_p loop;
|
VEC (rename_map_elt, heap) *new_renames;
|
VEC (rename_map_elt, heap) *new_renames;
|
} *alep_p;
|
} *alep_p;
|
|
|
/* Helper function for htab_traverse in insert_loop_close_phis. */
|
/* Helper function for htab_traverse in insert_loop_close_phis. */
|
|
|
static int
|
static int
|
add_loop_exit_phis (void **slot, void *data)
|
add_loop_exit_phis (void **slot, void *data)
|
{
|
{
|
struct rename_map_elt_s *entry;
|
struct rename_map_elt_s *entry;
|
alep_p a;
|
alep_p a;
|
loop_p loop;
|
loop_p loop;
|
tree expr, new_name, old_name;
|
tree expr, new_name, old_name;
|
bool def_in_loop_p, used_outside_p, need_close_phi_p;
|
bool def_in_loop_p, used_outside_p, need_close_phi_p;
|
gimple old_close_phi;
|
gimple old_close_phi;
|
|
|
if (!slot || !*slot || !data)
|
if (!slot || !*slot || !data)
|
return 1;
|
return 1;
|
|
|
entry = (struct rename_map_elt_s *) *slot;
|
entry = (struct rename_map_elt_s *) *slot;
|
a = (alep_p) data;
|
a = (alep_p) data;
|
loop = a->loop;
|
loop = a->loop;
|
new_name = expr = entry->expr;
|
new_name = expr = entry->expr;
|
old_name = entry->old_name;
|
old_name = entry->old_name;
|
|
|
def_in_loop_p = expr_defined_in_loop_p (expr, loop);
|
def_in_loop_p = expr_defined_in_loop_p (expr, loop);
|
if (!def_in_loop_p)
|
if (!def_in_loop_p)
|
return 1;
|
return 1;
|
|
|
/* Remove the old rename from the map when the expression is defined
|
/* Remove the old rename from the map when the expression is defined
|
in the loop that we're closing. */
|
in the loop that we're closing. */
|
free (*slot);
|
free (*slot);
|
*slot = NULL;
|
*slot = NULL;
|
|
|
if (TREE_CODE (expr) != SSA_NAME)
|
if (TREE_CODE (expr) != SSA_NAME)
|
return 1;
|
return 1;
|
|
|
old_close_phi = alive_after_loop (old_name);
|
old_close_phi = alive_after_loop (old_name);
|
used_outside_p = (old_close_phi != NULL);
|
used_outside_p = (old_close_phi != NULL);
|
need_close_phi_p = (used_outside_p
|
need_close_phi_p = (used_outside_p
|
&& close_phi_not_yet_inserted_p (loop, new_name));
|
&& close_phi_not_yet_inserted_p (loop, new_name));
|
|
|
/* Insert a loop close phi node. */
|
/* Insert a loop close phi node. */
|
if (need_close_phi_p)
|
if (need_close_phi_p)
|
{
|
{
|
basic_block bb = single_exit (loop)->dest;
|
basic_block bb = single_exit (loop)->dest;
|
gimple phi = create_phi_node (new_name, bb);
|
gimple phi = create_phi_node (new_name, bb);
|
tree new_res = create_new_def_for (gimple_phi_result (phi), phi,
|
tree new_res = create_new_def_for (gimple_phi_result (phi), phi,
|
gimple_phi_result_ptr (phi));
|
gimple_phi_result_ptr (phi));
|
|
|
add_phi_arg (phi, new_name, single_pred_edge (bb), UNKNOWN_LOCATION);
|
add_phi_arg (phi, new_name, single_pred_edge (bb), UNKNOWN_LOCATION);
|
VEC_safe_push (rename_map_elt, heap, a->new_renames,
|
VEC_safe_push (rename_map_elt, heap, a->new_renames,
|
new_rename_map_elt (gimple_phi_result (old_close_phi),
|
new_rename_map_elt (gimple_phi_result (old_close_phi),
|
new_res));
|
new_res));
|
}
|
}
|
|
|
return 1;
|
return 1;
|
}
|
}
|
|
|
/* Traverses MAP and removes from it all the tuples (OLD, NEW) where
|
/* Traverses MAP and removes from it all the tuples (OLD, NEW) where
|
NEW is defined in LOOP. Inserts on the exit of LOOP the close phi
|
NEW is defined in LOOP. Inserts on the exit of LOOP the close phi
|
node "RES = phi (NEW)" corresponding to "OLD_RES = phi (OLD)" in
|
node "RES = phi (NEW)" corresponding to "OLD_RES = phi (OLD)" in
|
the original code. Inserts in MAP the tuple (OLD_RES, RES). */
|
the original code. Inserts in MAP the tuple (OLD_RES, RES). */
|
|
|
void
|
void
|
insert_loop_close_phis (htab_t map, loop_p loop)
|
insert_loop_close_phis (htab_t map, loop_p loop)
|
{
|
{
|
int i;
|
int i;
|
struct alep a;
|
struct alep a;
|
rename_map_elt elt;
|
rename_map_elt elt;
|
|
|
a.loop = loop;
|
a.loop = loop;
|
a.new_renames = VEC_alloc (rename_map_elt, heap, 3);
|
a.new_renames = VEC_alloc (rename_map_elt, heap, 3);
|
update_ssa (TODO_update_ssa);
|
update_ssa (TODO_update_ssa);
|
htab_traverse (map, add_loop_exit_phis, &a);
|
htab_traverse (map, add_loop_exit_phis, &a);
|
update_ssa (TODO_update_ssa);
|
update_ssa (TODO_update_ssa);
|
|
|
for (i = 0; VEC_iterate (rename_map_elt, a.new_renames, i, elt); i++)
|
for (i = 0; VEC_iterate (rename_map_elt, a.new_renames, i, elt); i++)
|
{
|
{
|
set_rename (map, elt->old_name, elt->expr);
|
set_rename (map, elt->old_name, elt->expr);
|
free (elt);
|
free (elt);
|
}
|
}
|
|
|
VEC_free (rename_map_elt, heap, a.new_renames);
|
VEC_free (rename_map_elt, heap, a.new_renames);
|
}
|
}
|
|
|
/* Helper structure for htab_traverse in insert_guard_phis. */
|
/* Helper structure for htab_traverse in insert_guard_phis. */
|
|
|
struct igp {
|
struct igp {
|
basic_block bb;
|
basic_block bb;
|
edge true_edge, false_edge;
|
edge true_edge, false_edge;
|
htab_t before_guard;
|
htab_t before_guard;
|
};
|
};
|
|
|
/* Return the default name that is before the guard. */
|
/* Return the default name that is before the guard. */
|
|
|
static tree
|
static tree
|
default_before_guard (htab_t before_guard, tree old_name)
|
default_before_guard (htab_t before_guard, tree old_name)
|
{
|
{
|
tree res = get_rename (before_guard, old_name);
|
tree res = get_rename (before_guard, old_name);
|
|
|
if (res == old_name)
|
if (res == old_name)
|
{
|
{
|
if (is_gimple_reg (res))
|
if (is_gimple_reg (res))
|
return fold_convert (TREE_TYPE (res), integer_zero_node);
|
return fold_convert (TREE_TYPE (res), integer_zero_node);
|
return gimple_default_def (cfun, SSA_NAME_VAR (res));
|
return gimple_default_def (cfun, SSA_NAME_VAR (res));
|
}
|
}
|
|
|
return res;
|
return res;
|
}
|
}
|
|
|
/* Prepares EXPR to be a good phi argument when the phi result is
|
/* Prepares EXPR to be a good phi argument when the phi result is
|
RES. Insert needed statements on edge E. */
|
RES. Insert needed statements on edge E. */
|
|
|
static tree
|
static tree
|
convert_for_phi_arg (tree expr, tree res, edge e)
|
convert_for_phi_arg (tree expr, tree res, edge e)
|
{
|
{
|
tree type = TREE_TYPE (res);
|
tree type = TREE_TYPE (res);
|
|
|
if (TREE_TYPE (expr) != type)
|
if (TREE_TYPE (expr) != type)
|
expr = fold_convert (type, expr);
|
expr = fold_convert (type, expr);
|
|
|
if (TREE_CODE (expr) != SSA_NAME
|
if (TREE_CODE (expr) != SSA_NAME
|
&& !is_gimple_min_invariant (expr))
|
&& !is_gimple_min_invariant (expr))
|
{
|
{
|
tree var = create_tmp_var (type, "var");
|
tree var = create_tmp_var (type, "var");
|
gimple_seq stmts;
|
gimple_seq stmts;
|
|
|
expr = build2 (MODIFY_EXPR, type, var, expr);
|
expr = build2 (MODIFY_EXPR, type, var, expr);
|
expr = force_gimple_operand (expr, &stmts, true, NULL);
|
expr = force_gimple_operand (expr, &stmts, true, NULL);
|
gsi_insert_seq_on_edge_immediate (e, stmts);
|
gsi_insert_seq_on_edge_immediate (e, stmts);
|
}
|
}
|
|
|
return expr;
|
return expr;
|
}
|
}
|
|
|
/* Helper function for htab_traverse in insert_guard_phis. */
|
/* Helper function for htab_traverse in insert_guard_phis. */
|
|
|
static int
|
static int
|
add_guard_exit_phis (void **slot, void *s)
|
add_guard_exit_phis (void **slot, void *s)
|
{
|
{
|
struct rename_map_elt_s *entry = (struct rename_map_elt_s *) *slot;
|
struct rename_map_elt_s *entry = (struct rename_map_elt_s *) *slot;
|
struct igp *i = (struct igp *) s;
|
struct igp *i = (struct igp *) s;
|
basic_block bb = i->bb;
|
basic_block bb = i->bb;
|
edge true_edge = i->true_edge;
|
edge true_edge = i->true_edge;
|
edge false_edge = i->false_edge;
|
edge false_edge = i->false_edge;
|
tree res = entry->old_name;
|
tree res = entry->old_name;
|
tree name1 = entry->expr;
|
tree name1 = entry->expr;
|
tree name2 = default_before_guard (i->before_guard, res);
|
tree name2 = default_before_guard (i->before_guard, res);
|
gimple phi;
|
gimple phi;
|
|
|
/* Nothing to be merged if the name before the guard is the same as
|
/* Nothing to be merged if the name before the guard is the same as
|
the one after. */
|
the one after. */
|
if (name1 == name2)
|
if (name1 == name2)
|
return 1;
|
return 1;
|
|
|
name1 = convert_for_phi_arg (name1, res, true_edge);
|
name1 = convert_for_phi_arg (name1, res, true_edge);
|
name2 = convert_for_phi_arg (name2, res, false_edge);
|
name2 = convert_for_phi_arg (name2, res, false_edge);
|
|
|
phi = create_phi_node (res, bb);
|
phi = create_phi_node (res, bb);
|
res = create_new_def_for (gimple_phi_result (phi), phi,
|
res = create_new_def_for (gimple_phi_result (phi), phi,
|
gimple_phi_result_ptr (phi));
|
gimple_phi_result_ptr (phi));
|
|
|
add_phi_arg (phi, name1, true_edge, UNKNOWN_LOCATION);
|
add_phi_arg (phi, name1, true_edge, UNKNOWN_LOCATION);
|
add_phi_arg (phi, name2, false_edge, UNKNOWN_LOCATION);
|
add_phi_arg (phi, name2, false_edge, UNKNOWN_LOCATION);
|
|
|
entry->expr = res;
|
entry->expr = res;
|
*slot = entry;
|
*slot = entry;
|
return 1;
|
return 1;
|
}
|
}
|
|
|
/* Iterate over RENAME_MAP and get tuples of the form (OLD, NAME1).
|
/* Iterate over RENAME_MAP and get tuples of the form (OLD, NAME1).
|
If there is a correspondent tuple (OLD, NAME2) in BEFORE_GUARD,
|
If there is a correspondent tuple (OLD, NAME2) in BEFORE_GUARD,
|
with NAME1 different than NAME2, then insert in BB the phi node:
|
with NAME1 different than NAME2, then insert in BB the phi node:
|
|
|
| RES = phi (NAME1 (on TRUE_EDGE), NAME2 (on FALSE_EDGE))"
|
| RES = phi (NAME1 (on TRUE_EDGE), NAME2 (on FALSE_EDGE))"
|
|
|
if there is no tuple for OLD in BEFORE_GUARD, insert
|
if there is no tuple for OLD in BEFORE_GUARD, insert
|
|
|
| RES = phi (NAME1 (on TRUE_EDGE),
|
| RES = phi (NAME1 (on TRUE_EDGE),
|
| DEFAULT_DEFINITION of NAME1 (on FALSE_EDGE))".
|
| DEFAULT_DEFINITION of NAME1 (on FALSE_EDGE))".
|
|
|
Finally register in RENAME_MAP the tuple (OLD, RES). */
|
Finally register in RENAME_MAP the tuple (OLD, RES). */
|
|
|
void
|
void
|
insert_guard_phis (basic_block bb, edge true_edge, edge false_edge,
|
insert_guard_phis (basic_block bb, edge true_edge, edge false_edge,
|
htab_t before_guard, htab_t rename_map)
|
htab_t before_guard, htab_t rename_map)
|
{
|
{
|
struct igp i;
|
struct igp i;
|
i.bb = bb;
|
i.bb = bb;
|
i.true_edge = true_edge;
|
i.true_edge = true_edge;
|
i.false_edge = false_edge;
|
i.false_edge = false_edge;
|
i.before_guard = before_guard;
|
i.before_guard = before_guard;
|
|
|
update_ssa (TODO_update_ssa);
|
update_ssa (TODO_update_ssa);
|
htab_traverse (rename_map, add_guard_exit_phis, &i);
|
htab_traverse (rename_map, add_guard_exit_phis, &i);
|
update_ssa (TODO_update_ssa);
|
update_ssa (TODO_update_ssa);
|
}
|
}
|
|
|
/* Create a duplicate of the basic block BB. NOTE: This does not
|
/* Create a duplicate of the basic block BB. NOTE: This does not
|
preserve SSA form. */
|
preserve SSA form. */
|
|
|
static void
|
static void
|
graphite_copy_stmts_from_block (basic_block bb, basic_block new_bb, htab_t map)
|
graphite_copy_stmts_from_block (basic_block bb, basic_block new_bb, htab_t map)
|
{
|
{
|
gimple_stmt_iterator gsi, gsi_tgt;
|
gimple_stmt_iterator gsi, gsi_tgt;
|
|
|
gsi_tgt = gsi_start_bb (new_bb);
|
gsi_tgt = gsi_start_bb (new_bb);
|
for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
|
for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
|
{
|
{
|
def_operand_p def_p;
|
def_operand_p def_p;
|
ssa_op_iter op_iter;
|
ssa_op_iter op_iter;
|
gimple stmt = gsi_stmt (gsi);
|
gimple stmt = gsi_stmt (gsi);
|
gimple copy;
|
gimple copy;
|
|
|
if (gimple_code (stmt) == GIMPLE_LABEL)
|
if (gimple_code (stmt) == GIMPLE_LABEL)
|
continue;
|
continue;
|
|
|
/* Create a new copy of STMT and duplicate STMT's virtual
|
/* Create a new copy of STMT and duplicate STMT's virtual
|
operands. */
|
operands. */
|
copy = gimple_copy (stmt);
|
copy = gimple_copy (stmt);
|
gsi_insert_after (&gsi_tgt, copy, GSI_NEW_STMT);
|
gsi_insert_after (&gsi_tgt, copy, GSI_NEW_STMT);
|
mark_sym_for_renaming (gimple_vop (cfun));
|
mark_sym_for_renaming (gimple_vop (cfun));
|
|
|
maybe_duplicate_eh_stmt (copy, stmt);
|
maybe_duplicate_eh_stmt (copy, stmt);
|
gimple_duplicate_stmt_histograms (cfun, copy, cfun, stmt);
|
gimple_duplicate_stmt_histograms (cfun, copy, cfun, stmt);
|
|
|
/* Create new names for all the definitions created by COPY and
|
/* Create new names for all the definitions created by COPY and
|
add replacement mappings for each new name. */
|
add replacement mappings for each new name. */
|
FOR_EACH_SSA_DEF_OPERAND (def_p, copy, op_iter, SSA_OP_ALL_DEFS)
|
FOR_EACH_SSA_DEF_OPERAND (def_p, copy, op_iter, SSA_OP_ALL_DEFS)
|
{
|
{
|
tree old_name = DEF_FROM_PTR (def_p);
|
tree old_name = DEF_FROM_PTR (def_p);
|
tree new_name = create_new_def_for (old_name, copy, def_p);
|
tree new_name = create_new_def_for (old_name, copy, def_p);
|
set_rename (map, old_name, new_name);
|
set_rename (map, old_name, new_name);
|
}
|
}
|
}
|
}
|
}
|
}
|
|
|
/* Copies BB and includes in the copied BB all the statements that can
|
/* Copies BB and includes in the copied BB all the statements that can
|
be reached following the use-def chains from the memory accesses,
|
be reached following the use-def chains from the memory accesses,
|
and returns the next edge following this new block. */
|
and returns the next edge following this new block. */
|
|
|
edge
|
edge
|
copy_bb_and_scalar_dependences (basic_block bb, sese region,
|
copy_bb_and_scalar_dependences (basic_block bb, sese region,
|
edge next_e, htab_t map)
|
edge next_e, htab_t map)
|
{
|
{
|
basic_block new_bb = split_edge (next_e);
|
basic_block new_bb = split_edge (next_e);
|
|
|
next_e = single_succ_edge (new_bb);
|
next_e = single_succ_edge (new_bb);
|
graphite_copy_stmts_from_block (bb, new_bb, map);
|
graphite_copy_stmts_from_block (bb, new_bb, map);
|
remove_condition (new_bb);
|
remove_condition (new_bb);
|
remove_phi_nodes (new_bb);
|
remove_phi_nodes (new_bb);
|
expand_scalar_variables (new_bb, region, map);
|
expand_scalar_variables (new_bb, region, map);
|
rename_variables (new_bb, map);
|
rename_variables (new_bb, map);
|
|
|
return next_e;
|
return next_e;
|
}
|
}
|
|
|
/* Returns the outermost loop in SCOP that contains BB. */
|
/* Returns the outermost loop in SCOP that contains BB. */
|
|
|
struct loop *
|
struct loop *
|
outermost_loop_in_sese (sese region, basic_block bb)
|
outermost_loop_in_sese (sese region, basic_block bb)
|
{
|
{
|
struct loop *nest;
|
struct loop *nest;
|
|
|
nest = bb->loop_father;
|
nest = bb->loop_father;
|
while (loop_outer (nest)
|
while (loop_outer (nest)
|
&& loop_in_sese_p (loop_outer (nest), region))
|
&& loop_in_sese_p (loop_outer (nest), region))
|
nest = loop_outer (nest);
|
nest = loop_outer (nest);
|
|
|
return nest;
|
return nest;
|
}
|
}
|
|
|
/* Sets the false region of an IF_REGION to REGION. */
|
/* Sets the false region of an IF_REGION to REGION. */
|
|
|
void
|
void
|
if_region_set_false_region (ifsese if_region, sese region)
|
if_region_set_false_region (ifsese if_region, sese region)
|
{
|
{
|
basic_block condition = if_region_get_condition_block (if_region);
|
basic_block condition = if_region_get_condition_block (if_region);
|
edge false_edge = get_false_edge_from_guard_bb (condition);
|
edge false_edge = get_false_edge_from_guard_bb (condition);
|
basic_block dummy = false_edge->dest;
|
basic_block dummy = false_edge->dest;
|
edge entry_region = SESE_ENTRY (region);
|
edge entry_region = SESE_ENTRY (region);
|
edge exit_region = SESE_EXIT (region);
|
edge exit_region = SESE_EXIT (region);
|
basic_block before_region = entry_region->src;
|
basic_block before_region = entry_region->src;
|
basic_block last_in_region = exit_region->src;
|
basic_block last_in_region = exit_region->src;
|
void **slot = htab_find_slot_with_hash (current_loops->exits, exit_region,
|
void **slot = htab_find_slot_with_hash (current_loops->exits, exit_region,
|
htab_hash_pointer (exit_region),
|
htab_hash_pointer (exit_region),
|
NO_INSERT);
|
NO_INSERT);
|
|
|
entry_region->flags = false_edge->flags;
|
entry_region->flags = false_edge->flags;
|
false_edge->flags = exit_region->flags;
|
false_edge->flags = exit_region->flags;
|
|
|
redirect_edge_pred (entry_region, condition);
|
redirect_edge_pred (entry_region, condition);
|
redirect_edge_pred (exit_region, before_region);
|
redirect_edge_pred (exit_region, before_region);
|
redirect_edge_pred (false_edge, last_in_region);
|
redirect_edge_pred (false_edge, last_in_region);
|
redirect_edge_succ (false_edge, single_succ (dummy));
|
redirect_edge_succ (false_edge, single_succ (dummy));
|
delete_basic_block (dummy);
|
delete_basic_block (dummy);
|
|
|
exit_region->flags = EDGE_FALLTHRU;
|
exit_region->flags = EDGE_FALLTHRU;
|
recompute_all_dominators ();
|
recompute_all_dominators ();
|
|
|
SESE_EXIT (region) = false_edge;
|
SESE_EXIT (region) = false_edge;
|
|
|
if (if_region->false_region)
|
if (if_region->false_region)
|
free (if_region->false_region);
|
free (if_region->false_region);
|
if_region->false_region = region;
|
if_region->false_region = region;
|
|
|
if (slot)
|
if (slot)
|
{
|
{
|
struct loop_exit *loop_exit = GGC_CNEW (struct loop_exit);
|
struct loop_exit *loop_exit = GGC_CNEW (struct loop_exit);
|
|
|
memcpy (loop_exit, *((struct loop_exit **) slot), sizeof (struct loop_exit));
|
memcpy (loop_exit, *((struct loop_exit **) slot), sizeof (struct loop_exit));
|
htab_clear_slot (current_loops->exits, slot);
|
htab_clear_slot (current_loops->exits, slot);
|
|
|
slot = htab_find_slot_with_hash (current_loops->exits, false_edge,
|
slot = htab_find_slot_with_hash (current_loops->exits, false_edge,
|
htab_hash_pointer (false_edge),
|
htab_hash_pointer (false_edge),
|
INSERT);
|
INSERT);
|
loop_exit->e = false_edge;
|
loop_exit->e = false_edge;
|
*slot = loop_exit;
|
*slot = loop_exit;
|
false_edge->src->loop_father->exits->next = loop_exit;
|
false_edge->src->loop_father->exits->next = loop_exit;
|
}
|
}
|
}
|
}
|
|
|
/* Creates an IFSESE with CONDITION on edge ENTRY. */
|
/* Creates an IFSESE with CONDITION on edge ENTRY. */
|
|
|
ifsese
|
ifsese
|
create_if_region_on_edge (edge entry, tree condition)
|
create_if_region_on_edge (edge entry, tree condition)
|
{
|
{
|
edge e;
|
edge e;
|
edge_iterator ei;
|
edge_iterator ei;
|
sese sese_region = XNEW (struct sese_s);
|
sese sese_region = XNEW (struct sese_s);
|
sese true_region = XNEW (struct sese_s);
|
sese true_region = XNEW (struct sese_s);
|
sese false_region = XNEW (struct sese_s);
|
sese false_region = XNEW (struct sese_s);
|
ifsese if_region = XNEW (struct ifsese_s);
|
ifsese if_region = XNEW (struct ifsese_s);
|
edge exit = create_empty_if_region_on_edge (entry, condition);
|
edge exit = create_empty_if_region_on_edge (entry, condition);
|
|
|
if_region->region = sese_region;
|
if_region->region = sese_region;
|
if_region->region->entry = entry;
|
if_region->region->entry = entry;
|
if_region->region->exit = exit;
|
if_region->region->exit = exit;
|
|
|
FOR_EACH_EDGE (e, ei, entry->dest->succs)
|
FOR_EACH_EDGE (e, ei, entry->dest->succs)
|
{
|
{
|
if (e->flags & EDGE_TRUE_VALUE)
|
if (e->flags & EDGE_TRUE_VALUE)
|
{
|
{
|
true_region->entry = e;
|
true_region->entry = e;
|
true_region->exit = single_succ_edge (e->dest);
|
true_region->exit = single_succ_edge (e->dest);
|
if_region->true_region = true_region;
|
if_region->true_region = true_region;
|
}
|
}
|
else if (e->flags & EDGE_FALSE_VALUE)
|
else if (e->flags & EDGE_FALSE_VALUE)
|
{
|
{
|
false_region->entry = e;
|
false_region->entry = e;
|
false_region->exit = single_succ_edge (e->dest);
|
false_region->exit = single_succ_edge (e->dest);
|
if_region->false_region = false_region;
|
if_region->false_region = false_region;
|
}
|
}
|
}
|
}
|
|
|
return if_region;
|
return if_region;
|
}
|
}
|
|
|
/* Moves REGION in a condition expression:
|
/* Moves REGION in a condition expression:
|
| if (1)
|
| if (1)
|
| ;
|
| ;
|
| else
|
| else
|
| REGION;
|
| REGION;
|
*/
|
*/
|
|
|
ifsese
|
ifsese
|
move_sese_in_condition (sese region)
|
move_sese_in_condition (sese region)
|
{
|
{
|
basic_block pred_block = split_edge (SESE_ENTRY (region));
|
basic_block pred_block = split_edge (SESE_ENTRY (region));
|
ifsese if_region;
|
ifsese if_region;
|
|
|
SESE_ENTRY (region) = single_succ_edge (pred_block);
|
SESE_ENTRY (region) = single_succ_edge (pred_block);
|
if_region = create_if_region_on_edge (single_pred_edge (pred_block), integer_one_node);
|
if_region = create_if_region_on_edge (single_pred_edge (pred_block), integer_one_node);
|
if_region_set_false_region (if_region, region);
|
if_region_set_false_region (if_region, region);
|
|
|
return if_region;
|
return if_region;
|
}
|
}
|
|
|
/* Replaces the condition of the IF_REGION with CONDITION:
|
/* Replaces the condition of the IF_REGION with CONDITION:
|
| if (CONDITION)
|
| if (CONDITION)
|
| true_region;
|
| true_region;
|
| else
|
| else
|
| false_region;
|
| false_region;
|
*/
|
*/
|
|
|
void
|
void
|
set_ifsese_condition (ifsese if_region, tree condition)
|
set_ifsese_condition (ifsese if_region, tree condition)
|
{
|
{
|
sese region = if_region->region;
|
sese region = if_region->region;
|
edge entry = region->entry;
|
edge entry = region->entry;
|
basic_block bb = entry->dest;
|
basic_block bb = entry->dest;
|
gimple last = last_stmt (bb);
|
gimple last = last_stmt (bb);
|
gimple_stmt_iterator gsi = gsi_last_bb (bb);
|
gimple_stmt_iterator gsi = gsi_last_bb (bb);
|
gimple cond_stmt;
|
gimple cond_stmt;
|
|
|
gcc_assert (gimple_code (last) == GIMPLE_COND);
|
gcc_assert (gimple_code (last) == GIMPLE_COND);
|
|
|
gsi_remove (&gsi, true);
|
gsi_remove (&gsi, true);
|
gsi = gsi_last_bb (bb);
|
gsi = gsi_last_bb (bb);
|
condition = force_gimple_operand_gsi (&gsi, condition, true, NULL,
|
condition = force_gimple_operand_gsi (&gsi, condition, true, NULL,
|
false, GSI_NEW_STMT);
|
false, GSI_NEW_STMT);
|
cond_stmt = gimple_build_cond_from_tree (condition, NULL_TREE, NULL_TREE);
|
cond_stmt = gimple_build_cond_from_tree (condition, NULL_TREE, NULL_TREE);
|
gsi = gsi_last_bb (bb);
|
gsi = gsi_last_bb (bb);
|
gsi_insert_after (&gsi, cond_stmt, GSI_NEW_STMT);
|
gsi_insert_after (&gsi, cond_stmt, GSI_NEW_STMT);
|
}
|
}
|
|
|
/* Returns the scalar evolution of T in REGION. Every variable that
|
/* Returns the scalar evolution of T in REGION. Every variable that
|
is not defined in the REGION is considered a parameter. */
|
is not defined in the REGION is considered a parameter. */
|
|
|
tree
|
tree
|
scalar_evolution_in_region (sese region, loop_p loop, tree t)
|
scalar_evolution_in_region (sese region, loop_p loop, tree t)
|
{
|
{
|
gimple def;
|
gimple def;
|
struct loop *def_loop;
|
struct loop *def_loop;
|
basic_block before = block_before_sese (region);
|
basic_block before = block_before_sese (region);
|
|
|
if (TREE_CODE (t) != SSA_NAME
|
if (TREE_CODE (t) != SSA_NAME
|
|| loop_in_sese_p (loop, region))
|
|| loop_in_sese_p (loop, region))
|
return instantiate_scev (before, loop,
|
return instantiate_scev (before, loop,
|
analyze_scalar_evolution (loop, t));
|
analyze_scalar_evolution (loop, t));
|
|
|
if (!defined_in_sese_p (t, region))
|
if (!defined_in_sese_p (t, region))
|
return t;
|
return t;
|
|
|
def = SSA_NAME_DEF_STMT (t);
|
def = SSA_NAME_DEF_STMT (t);
|
def_loop = loop_containing_stmt (def);
|
def_loop = loop_containing_stmt (def);
|
|
|
if (loop_in_sese_p (def_loop, region))
|
if (loop_in_sese_p (def_loop, region))
|
{
|
{
|
t = analyze_scalar_evolution (def_loop, t);
|
t = analyze_scalar_evolution (def_loop, t);
|
def_loop = superloop_at_depth (def_loop, loop_depth (loop) + 1);
|
def_loop = superloop_at_depth (def_loop, loop_depth (loop) + 1);
|
t = compute_overall_effect_of_inner_loop (def_loop, t);
|
t = compute_overall_effect_of_inner_loop (def_loop, t);
|
return t;
|
return t;
|
}
|
}
|
else
|
else
|
return instantiate_scev (before, loop, t);
|
return instantiate_scev (before, loop, t);
|
}
|
}
|
|
|