#include "config.h"
#include "system.h"
#include "coretypes.h"
#include "tm.h"
#include "tree.h"
#include "tree-flow.h"
#include "tree-inline.h"
#include "tree-pass.h"
#include "langhooks.h"
#include "pointer-set.h"
#include "ggc.h"
#include "ipa-utils.h"
#include "ipa-type-escape.h"
#include "c-common.h"
#include "tree-gimple.h"
#include "cgraph.h"
#include "output.h"
#include "flags.h"
#include "timevar.h"
#include "diagnostic.h"
#include "langhooks.h"
static bool initialized = false;
static bitmap results_of_malloc;
static bitmap been_there_done_that;
static bitmap bitmap_tmp;
enum escape_t
{
EXPOSED_PARAMETER,
FULL_ESCAPE
};
static bitmap global_types_exposed_parameter;
static bitmap global_types_full_escape;
static bitmap global_types_seen;
static splay_tree uid_to_canon_type;
static splay_tree all_canon_types;
static splay_tree type_to_canon_type;
static splay_tree uid_to_addressof_down_map;
static splay_tree uid_to_addressof_up_map;
static splay_tree uid_to_subtype_map;
static struct pointer_set_t *visited_nodes;
static bitmap_obstack ipa_obstack;
static char*
get_name_of_type (tree type)
{
tree name = TYPE_NAME (type);
if (!name)
return (char*)"<UNNAMED>";
if (TREE_CODE (name) == TYPE_DECL)
{
if (DECL_NAME (name))
return (char*)IDENTIFIER_POINTER (DECL_NAME (name));
else
return (char*)"<UNNAMED>";
}
else if (TREE_CODE (name) == IDENTIFIER_NODE)
return (char*)IDENTIFIER_POINTER (name);
else
return (char*)"<UNNAMED>";
}
struct type_brand_s
{
char* name;
int seq;
};
static int
compare_type_brand (splay_tree_key sk1, splay_tree_key sk2)
{
struct type_brand_s * k1 = (struct type_brand_s *) sk1;
struct type_brand_s * k2 = (struct type_brand_s *) sk2;
int value = strcmp(k1->name, k2->name);
if (value == 0)
return k2->seq - k1->seq;
else
return value;
}
static tree
discover_unique_type (tree type)
{
struct type_brand_s * brand = XNEW (struct type_brand_s);
int i = 0;
splay_tree_node result;
brand->name = get_name_of_type (type);
while (1)
{
brand->seq = i++;
result = splay_tree_lookup (all_canon_types, (splay_tree_key) brand);
if (result)
{
tree other_type = (tree) result->value;
if (lang_hooks.types_compatible_p (type, other_type) == 1)
{
free (brand);
splay_tree_insert (type_to_canon_type,
(splay_tree_key) type,
(splay_tree_value) other_type);
return other_type;
}
}
else
{
brand->seq = i++;
splay_tree_insert (all_canon_types,
(splay_tree_key) brand,
(splay_tree_value) type);
splay_tree_insert (type_to_canon_type,
(splay_tree_key) type,
(splay_tree_value) type);
splay_tree_insert (uid_to_canon_type,
(splay_tree_key) TYPE_UID (type),
(splay_tree_value) type);
bitmap_set_bit (global_types_seen, TYPE_UID (type));
return type;
}
}
}
static bool
type_to_consider (tree type)
{
type = TYPE_MAIN_VARIANT (type);
while (POINTER_TYPE_P (type) || TREE_CODE (type) == ARRAY_TYPE)
type = TYPE_MAIN_VARIANT (TREE_TYPE (type));
switch (TREE_CODE (type))
{
case BOOLEAN_TYPE:
case COMPLEX_TYPE:
case ENUMERAL_TYPE:
case INTEGER_TYPE:
case QUAL_UNION_TYPE:
case REAL_TYPE:
case RECORD_TYPE:
case UNION_TYPE:
case VECTOR_TYPE:
case VOID_TYPE:
return true;
default:
return false;
}
}
static tree
get_canon_type (tree type, bool see_thru_ptrs, bool see_thru_arrays)
{
splay_tree_node result;
if (!type || !type_to_consider (type))
return NULL;
type = TYPE_MAIN_VARIANT (type);
if (see_thru_arrays)
while (POINTER_TYPE_P (type) || TREE_CODE (type) == ARRAY_TYPE)
type = TYPE_MAIN_VARIANT (TREE_TYPE (type));
else if (see_thru_ptrs)
while (POINTER_TYPE_P (type))
type = TYPE_MAIN_VARIANT (TREE_TYPE (type));
result = splay_tree_lookup(type_to_canon_type, (splay_tree_key) type);
if (result == NULL)
return discover_unique_type (type);
else return (tree) result->value;
}
static int
get_canon_type_uid (tree type, bool see_thru_ptrs, bool see_thru_arrays)
{
type = get_canon_type (type, see_thru_ptrs, see_thru_arrays);
if (type)
return TYPE_UID(type);
else return 0;
}
int
ipa_type_escape_star_count_of_interesting_type (tree type)
{
int count = 0;
if (!type)
return -1;
type = TYPE_MAIN_VARIANT (type);
while (POINTER_TYPE_P (type))
{
type = TYPE_MAIN_VARIANT (TREE_TYPE (type));
count++;
}
if (TREE_CODE (type) == RECORD_TYPE
|| TREE_CODE (type) == QUAL_UNION_TYPE
|| TREE_CODE (type) == UNION_TYPE)
return count;
else
return -1;
}
int
ipa_type_escape_star_count_of_interesting_or_array_type (tree type)
{
int count = 0;
if (!type)
return -1;
type = TYPE_MAIN_VARIANT (type);
while (POINTER_TYPE_P (type) || TREE_CODE (type) == ARRAY_TYPE)
{
type = TYPE_MAIN_VARIANT (TREE_TYPE (type));
count++;
}
if (TREE_CODE (type) == RECORD_TYPE
|| TREE_CODE (type) == QUAL_UNION_TYPE
|| TREE_CODE (type) == UNION_TYPE)
return count;
else
return -1;
}
bool
ipa_type_escape_type_contained_p (tree type)
{
if (!initialized)
return false;
return !bitmap_bit_p (global_types_full_escape,
get_canon_type_uid (type, true, false));
}
bool
ipa_type_escape_field_does_not_clobber_p (tree record_type, tree field_type)
{
splay_tree_node result;
int uid;
if (!initialized)
return false;
record_type = TYPE_MAIN_VARIANT (record_type);
field_type = TYPE_MAIN_VARIANT (field_type);
while (POINTER_TYPE_P (record_type))
{
record_type = TYPE_MAIN_VARIANT (TREE_TYPE (record_type));
if (POINTER_TYPE_P (field_type))
field_type = TYPE_MAIN_VARIANT (TREE_TYPE (field_type));
else
if (TREE_CODE (field_type) == QUAL_UNION_TYPE
|| TREE_CODE (field_type) == UNION_TYPE)
{
while (POINTER_TYPE_P (record_type))
record_type = TYPE_MAIN_VARIANT (TREE_TYPE (record_type));
break;
}
else
return true;
}
record_type = get_canon_type (record_type, true, true);
if (!ipa_type_escape_type_contained_p (record_type))
return false;
uid = TYPE_UID (record_type);
result = splay_tree_lookup (uid_to_addressof_down_map, (splay_tree_key) uid);
if (result)
{
bitmap field_type_map = (bitmap) result->value;
uid = get_canon_type_uid (field_type, true, true);
return !bitmap_bit_p (field_type_map, uid);
}
else
return true;
}
static tree
mark_type (tree type, enum escape_t escape_status)
{
bitmap map = NULL;
int uid;
type = get_canon_type (type, true, true);
if (!type)
return NULL;
switch (escape_status)
{
case EXPOSED_PARAMETER:
map = global_types_exposed_parameter;
break;
case FULL_ESCAPE:
map = global_types_full_escape;
break;
}
uid = TYPE_UID (type);
if (bitmap_bit_p (map, uid))
return type;
else
{
bitmap_set_bit (map, uid);
if (escape_status == FULL_ESCAPE)
{
bitmap_set_bit (global_types_exposed_parameter, uid);
}
}
return type;
}
static void
mark_interesting_type (tree type, enum escape_t escape_status)
{
if (!type) return;
if (ipa_type_escape_star_count_of_interesting_type (type) >= 0)
{
if ((escape_status == EXPOSED_PARAMETER)
&& POINTER_TYPE_P (type))
mark_type (type, FULL_ESCAPE);
else
mark_type (type, escape_status);
}
}
static bool
parent_type_p (tree parent, tree child)
{
int i;
tree binfo, base_binfo;
if (TYPE_BINFO (parent))
for (binfo = TYPE_BINFO (parent), i = 0;
BINFO_BASE_ITERATE (binfo, i, base_binfo); i++)
{
tree binfotype = BINFO_TYPE (base_binfo);
if (binfotype == child)
return true;
else if (parent_type_p (binfotype, child))
return true;
}
if (TREE_CODE (parent) == UNION_TYPE
|| TREE_CODE (parent) == QUAL_UNION_TYPE)
{
tree field;
for (field = TYPE_FIELDS (parent);
field;
field = TREE_CHAIN (field))
{
tree field_type;
if (TREE_CODE (field) != FIELD_DECL)
continue;
field_type = TREE_TYPE (field);
if (field_type == child)
return true;
}
for (field = TYPE_FIELDS (parent);
field;
field = TREE_CHAIN (field))
{
tree field_type;
if (TREE_CODE (field) != FIELD_DECL)
continue;
field_type = TREE_TYPE (field);
if (TREE_CODE (field_type) == RECORD_TYPE
|| TREE_CODE (field_type) == QUAL_UNION_TYPE
|| TREE_CODE (field_type) == UNION_TYPE)
if (parent_type_p (field_type, child))
return true;
}
}
if (TREE_CODE (parent) == RECORD_TYPE)
{
tree field;
for (field = TYPE_FIELDS (parent);
field;
field = TREE_CHAIN (field))
{
tree field_type;
if (TREE_CODE (field) != FIELD_DECL)
continue;
field_type = TREE_TYPE (field);
if (field_type == child)
return true;
if (TREE_CODE (field_type) == RECORD_TYPE
|| TREE_CODE (field_type) == QUAL_UNION_TYPE
|| TREE_CODE (field_type) == UNION_TYPE)
{
if (parent_type_p (field_type, child))
return true;
else
break;
}
}
}
return false;
}
static int
count_stars (tree* type_ptr)
{
tree type = *type_ptr;
int i = 0;
type = TYPE_MAIN_VARIANT (type);
while (POINTER_TYPE_P (type))
{
type = TYPE_MAIN_VARIANT (TREE_TYPE (type));
i++;
}
*type_ptr = type;
return i;
}
enum cast_type {
CT_UP,
CT_DOWN,
CT_SIDEWAYS,
CT_USELESS
};
static enum cast_type
check_cast_type (tree to_type, tree from_type)
{
int to_stars = count_stars (&to_type);
int from_stars = count_stars (&from_type);
if (to_stars != from_stars)
return CT_SIDEWAYS;
if (to_type == from_type)
return CT_USELESS;
if (parent_type_p (to_type, from_type)) return CT_UP;
if (parent_type_p (from_type, to_type)) return CT_DOWN;
return CT_SIDEWAYS;
}
static void
check_cast (tree to_type, tree from)
{
tree from_type = get_canon_type (TREE_TYPE (from), false, false);
bool to_interesting_type, from_interesting_type;
to_type = get_canon_type (to_type, false, false);
if (!from_type || !to_type || from_type == to_type)
return;
to_interesting_type =
ipa_type_escape_star_count_of_interesting_type (to_type) >= 0;
from_interesting_type =
ipa_type_escape_star_count_of_interesting_type (from_type) >= 0;
if (to_interesting_type)
if (from_interesting_type)
{
switch (check_cast_type (to_type, from_type))
{
case CT_UP:
case CT_USELESS:
case CT_DOWN:
break;
case CT_SIDEWAYS:
mark_type (to_type, FULL_ESCAPE);
mark_type (from_type, FULL_ESCAPE);
break;
}
}
else
{
if (DECL_P (from) && !bitmap_bit_p (results_of_malloc, DECL_UID (from)))
mark_type (to_type, FULL_ESCAPE);
}
else if (from_interesting_type)
mark_type (from_type, FULL_ESCAPE);
}
static void
check_function_parameter_and_return_types (tree fn, bool escapes)
{
tree arg;
if (TYPE_ARG_TYPES (TREE_TYPE (fn)))
{
for (arg = TYPE_ARG_TYPES (TREE_TYPE (fn));
arg && TREE_VALUE (arg) != void_type_node;
arg = TREE_CHAIN (arg))
{
tree type = get_canon_type (TREE_VALUE (arg), false, false);
if (escapes)
mark_interesting_type (type, EXPOSED_PARAMETER);
}
}
else
{
for (arg = DECL_ARGUMENTS (fn); arg; arg = TREE_CHAIN (arg))
{
tree type = get_canon_type (TREE_TYPE (arg), false, false);
if (escapes)
mark_interesting_type (type, EXPOSED_PARAMETER);
}
}
if (escapes)
{
tree type = get_canon_type (TREE_TYPE (TREE_TYPE (fn)), false, false);
mark_interesting_type (type, EXPOSED_PARAMETER);
}
}
static inline void
has_proper_scope_for_analysis (tree t)
{
tree type = get_canon_type (TREE_TYPE (t), false, false);
if (!type) return;
if (lookup_attribute ("used", DECL_ATTRIBUTES (t)))
{
mark_interesting_type (type, FULL_ESCAPE);
return;
}
if (TREE_THIS_VOLATILE (t))
return;
if (!TREE_STATIC (t) && !DECL_EXTERNAL (t))
return;
if (DECL_EXTERNAL (t) || TREE_PUBLIC (t))
{
if (TREE_READONLY (t)
&& DECL_INITIAL (t)
&& is_gimple_min_invariant (DECL_INITIAL (t)))
;
else
{
mark_interesting_type (type, FULL_ESCAPE);
}
}
}
static void
check_operand (tree t)
{
if (!t) return;
if (TREE_CODE (t) == FUNCTION_DECL)
check_function_parameter_and_return_types (t, true);
else if (TREE_CODE (t) == VAR_DECL)
has_proper_scope_for_analysis (t);
}
static void
check_tree (tree t)
{
if ((TREE_CODE (t) == EXC_PTR_EXPR) || (TREE_CODE (t) == FILTER_EXPR))
return;
while (TREE_CODE (t) == REALPART_EXPR
|| TREE_CODE (t) == IMAGPART_EXPR
|| handled_component_p (t))
{
if (TREE_CODE (t) == ARRAY_REF)
check_operand (TREE_OPERAND (t, 1));
t = TREE_OPERAND (t, 0);
}
if (INDIRECT_REF_P (t))
check_tree (TREE_OPERAND (t, 0));
if (SSA_VAR_P (t) || (TREE_CODE (t) == FUNCTION_DECL))
check_operand (t);
}
static void
mark_interesting_addressof (tree to_type, tree from_type)
{
int from_uid;
int to_uid;
bitmap type_map;
splay_tree_node result;
from_type = get_canon_type (from_type, false, false);
to_type = get_canon_type (to_type, false, false);
if (!from_type || !to_type)
return;
from_uid = TYPE_UID (from_type);
to_uid = TYPE_UID (to_type);
gcc_assert (ipa_type_escape_star_count_of_interesting_type (from_type) == 0);
result = splay_tree_lookup (uid_to_addressof_down_map,
(splay_tree_key) from_uid);
if (result)
type_map = (bitmap) result->value;
else
{
type_map = BITMAP_ALLOC (&ipa_obstack);
splay_tree_insert (uid_to_addressof_down_map,
from_uid,
(splay_tree_value)type_map);
}
bitmap_set_bit (type_map, TYPE_UID (to_type));
result =
splay_tree_lookup (uid_to_addressof_up_map, (splay_tree_key) to_uid);
if (result)
type_map = (bitmap) result->value;
else
{
type_map = BITMAP_ALLOC (&ipa_obstack);
splay_tree_insert (uid_to_addressof_up_map,
to_uid,
(splay_tree_value)type_map);
}
bitmap_set_bit (type_map, TYPE_UID (to_type));
}
static void
look_for_address_of (tree t)
{
if (TREE_CODE (t) == ADDR_EXPR)
{
tree x = get_base_var (t);
tree cref = TREE_OPERAND (t, 0);
tree fielddecl = NULL_TREE;
while (cref!= x)
{
if (TREE_CODE (cref) == COMPONENT_REF)
{
fielddecl = TREE_OPERAND (cref, 1);
mark_interesting_addressof (TREE_TYPE (fielddecl),
DECL_FIELD_CONTEXT (fielddecl));
}
else if (TREE_CODE (cref) == ARRAY_REF)
get_canon_type (TREE_TYPE (cref), false, false);
cref = TREE_OPERAND (cref, 0);
}
if (TREE_CODE (x) == VAR_DECL)
has_proper_scope_for_analysis (x);
}
}
static void
look_for_casts (tree lhs __attribute__((unused)), tree t)
{
if (is_gimple_cast (t) || TREE_CODE (t) == VIEW_CONVERT_EXPR)
{
tree castfromvar = TREE_OPERAND (t, 0);
check_cast (TREE_TYPE (t), castfromvar);
}
else if (TREE_CODE (t) == COMPONENT_REF
|| TREE_CODE (t) == INDIRECT_REF
|| TREE_CODE (t) == BIT_FIELD_REF)
{
tree base = get_base_address (t);
while (t != base)
{
t = TREE_OPERAND (t, 0);
if (TREE_CODE (t) == VIEW_CONVERT_EXPR)
{
tree castfromref = TREE_OPERAND (t, 0);
check_cast (TREE_TYPE (t), castfromref);
}
else if (TREE_CODE (t) == COMPONENT_REF)
get_canon_type (TREE_TYPE (TREE_OPERAND (t, 1)), false, false);
}
}
}
static void
check_rhs_var (tree t)
{
look_for_address_of (t);
check_tree(t);
}
static void
check_lhs_var (tree t)
{
check_tree(t);
}
static void
get_asm_expr_operands (tree stmt)
{
int noutputs = list_length (ASM_OUTPUTS (stmt));
const char **oconstraints
= (const char **) alloca ((noutputs) * sizeof (const char *));
int i;
tree link;
const char *constraint;
bool allows_mem, allows_reg, is_inout;
for (i=0, link = ASM_OUTPUTS (stmt); link; ++i, link = TREE_CHAIN (link))
{
oconstraints[i] = constraint
= TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (link)));
parse_output_constraint (&constraint, i, 0, 0,
&allows_mem, &allows_reg, &is_inout);
check_lhs_var (TREE_VALUE (link));
}
for (link = ASM_INPUTS (stmt); link; link = TREE_CHAIN (link))
{
constraint
= TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (link)));
parse_input_constraint (&constraint, 0, 0, noutputs, 0,
oconstraints, &allows_mem, &allows_reg);
check_rhs_var (TREE_VALUE (link));
}
}
static bool
check_call (tree call_expr)
{
int flags = call_expr_flags(call_expr);
tree operand_list = TREE_OPERAND (call_expr, 1);
tree operand;
tree callee_t = get_callee_fndecl (call_expr);
tree argument;
struct cgraph_node* callee;
enum availability avail = AVAIL_NOT_AVAILABLE;
for (operand = operand_list;
operand != NULL_TREE;
operand = TREE_CHAIN (operand))
{
tree argument = TREE_VALUE (operand);
check_rhs_var (argument);
}
if (callee_t)
{
tree arg_type;
tree last_arg_type = NULL;
callee = cgraph_node(callee_t);
avail = cgraph_function_body_availability (callee);
if (TYPE_ARG_TYPES (TREE_TYPE (callee_t)))
{
operand = operand_list;
for (arg_type = TYPE_ARG_TYPES (TREE_TYPE (callee_t));
arg_type && TREE_VALUE (arg_type) != void_type_node;
arg_type = TREE_CHAIN (arg_type))
{
if (operand)
{
argument = TREE_VALUE (operand);
last_arg_type = TREE_VALUE(arg_type);
check_cast (last_arg_type, argument);
operand = TREE_CHAIN (operand);
}
else
break;
}
}
else
{
operand = operand_list;
for (arg_type = DECL_ARGUMENTS (callee_t);
arg_type;
arg_type = TREE_CHAIN (arg_type))
{
if (operand)
{
argument = TREE_VALUE (operand);
last_arg_type = TREE_TYPE(arg_type);
check_cast (last_arg_type, argument);
operand = TREE_CHAIN (operand);
}
else
break;
}
}
arg_type = last_arg_type;
for (;
operand != NULL_TREE;
operand = TREE_CHAIN (operand))
{
argument = TREE_VALUE (operand);
if (arg_type)
check_cast (arg_type, argument);
else
{
tree type = get_canon_type (TREE_TYPE (argument), false, false);
mark_interesting_type (type, FULL_ESCAPE);
}
}
}
if (avail == AVAIL_NOT_AVAILABLE || avail == AVAIL_OVERWRITABLE)
{
for (operand = operand_list;
operand != NULL_TREE;
operand = TREE_CHAIN (operand))
{
tree type =
get_canon_type (TREE_TYPE (TREE_VALUE (operand)), false, false);
mark_interesting_type (type, EXPOSED_PARAMETER);
}
if (callee_t)
{
tree type =
get_canon_type (TREE_TYPE (TREE_TYPE (callee_t)), false, false);
mark_interesting_type (type, EXPOSED_PARAMETER);
}
}
return (flags & ECF_MALLOC);
}
static bool
okay_pointer_operation (enum tree_code code, tree op0, tree op1)
{
tree op0type = TYPE_MAIN_VARIANT (TREE_TYPE (op0));
tree op1type = TYPE_MAIN_VARIANT (TREE_TYPE (op1));
if (POINTER_TYPE_P (op1type))
return false;
switch (code)
{
case MULT_EXPR:
case PLUS_EXPR:
case MINUS_EXPR:
if (operand_equal_p (size_in_bytes (op0type), op1, 0))
return true;
default:
return false;
}
return false;
}
static tree
scan_for_refs (tree *tp, int *walk_subtrees, void *data)
{
struct cgraph_node *fn = data;
tree t = *tp;
switch (TREE_CODE (t))
{
case VAR_DECL:
if (DECL_INITIAL (t))
walk_tree (&DECL_INITIAL (t), scan_for_refs, fn, visited_nodes);
*walk_subtrees = 0;
break;
case MODIFY_EXPR:
{
tree lhs = TREE_OPERAND (t, 0);
tree rhs = TREE_OPERAND (t, 1);
check_lhs_var (lhs);
check_cast (TREE_TYPE (lhs), rhs);
switch (TREE_CODE_CLASS (TREE_CODE (rhs)))
{
case tcc_binary:
{
tree op0 = TREE_OPERAND (rhs, 0);
tree type0 = get_canon_type (TREE_TYPE (op0), false, false);
tree op1 = TREE_OPERAND (rhs, 1);
tree type1 = get_canon_type (TREE_TYPE (op1), false, false);
if (type0 && POINTER_TYPE_P (type0)
&& !okay_pointer_operation (TREE_CODE (rhs), op0, op1))
mark_interesting_type (type0, FULL_ESCAPE);
if (type1 && POINTER_TYPE_P (type1)
&& !okay_pointer_operation (TREE_CODE (rhs), op1, op0))
mark_interesting_type (type1, FULL_ESCAPE);
look_for_casts (lhs, op0);
look_for_casts (lhs, op1);
check_rhs_var (op0);
check_rhs_var (op1);
}
break;
case tcc_unary:
{
tree op0 = TREE_OPERAND (rhs, 0);
tree type0 = get_canon_type (TREE_TYPE (op0), false, false);
if (type0 && (TREE_CODE (op0) == NEGATE_EXPR
|| TREE_CODE (op0) == ABS_EXPR)
&& POINTER_TYPE_P (type0))
{
mark_interesting_type (type0, FULL_ESCAPE);
}
check_rhs_var (op0);
look_for_casts (lhs, op0);
look_for_casts (lhs, rhs);
}
break;
case tcc_reference:
look_for_casts (lhs, rhs);
check_rhs_var (rhs);
break;
case tcc_declaration:
check_rhs_var (rhs);
break;
case tcc_expression:
switch (TREE_CODE (rhs))
{
case ADDR_EXPR:
look_for_casts (lhs, TREE_OPERAND (rhs, 0));
check_rhs_var (rhs);
break;
case CALL_EXPR:
if (check_call (rhs))
bitmap_set_bit (results_of_malloc, DECL_UID (lhs));
break;
default:
break;
}
break;
default:
break;
}
*walk_subtrees = 0;
}
break;
case ADDR_EXPR:
check_rhs_var (t);
*walk_subtrees = 0;
break;
case CALL_EXPR:
check_call (t);
*walk_subtrees = 0;
break;
case ASM_EXPR:
get_asm_expr_operands (t);
*walk_subtrees = 0;
break;
default:
break;
}
return NULL;
}
static void
ipa_init (void)
{
bitmap_obstack_initialize (&ipa_obstack);
global_types_exposed_parameter = BITMAP_ALLOC (&ipa_obstack);
global_types_full_escape = BITMAP_ALLOC (&ipa_obstack);
global_types_seen = BITMAP_ALLOC (&ipa_obstack);
results_of_malloc = BITMAP_ALLOC (&ipa_obstack);
uid_to_canon_type = splay_tree_new (splay_tree_compare_ints, 0, 0);
all_canon_types = splay_tree_new (compare_type_brand, 0, 0);
type_to_canon_type = splay_tree_new (splay_tree_compare_pointers, 0, 0);
uid_to_subtype_map = splay_tree_new (splay_tree_compare_ints, 0, 0);
uid_to_addressof_down_map = splay_tree_new (splay_tree_compare_ints, 0, 0);
uid_to_addressof_up_map = splay_tree_new (splay_tree_compare_ints, 0, 0);
visited_nodes = pointer_set_create ();
initialized = true;
}
static void
analyze_variable (struct cgraph_varpool_node *vnode)
{
tree global = vnode->decl;
tree type = get_canon_type (TREE_TYPE (global), false, false);
if (vnode->externally_visible)
mark_interesting_type (type, FULL_ESCAPE);
gcc_assert (TREE_CODE (global) == VAR_DECL);
if (DECL_INITIAL (global))
walk_tree (&DECL_INITIAL (global), scan_for_refs, NULL, visited_nodes);
}
static void
analyze_function (struct cgraph_node *fn)
{
tree decl = fn->decl;
check_function_parameter_and_return_types (decl,
fn->local.externally_visible);
if (dump_file)
fprintf (dump_file, "\n local analysis of %s", cgraph_node_name (fn));
{
struct function *this_cfun = DECL_STRUCT_FUNCTION (decl);
basic_block this_block;
FOR_EACH_BB_FN (this_block, this_cfun)
{
block_stmt_iterator bsi;
for (bsi = bsi_start (this_block); !bsi_end_p (bsi); bsi_next (&bsi))
walk_tree (bsi_stmt_ptr (bsi), scan_for_refs,
fn, visited_nodes);
}
}
if (DECL_STRUCT_FUNCTION (decl))
{
tree step;
for (step = DECL_STRUCT_FUNCTION (decl)->unexpanded_var_list;
step;
step = TREE_CHAIN (step))
{
tree var = TREE_VALUE (step);
if (TREE_CODE (var) == VAR_DECL
&& DECL_INITIAL (var)
&& !TREE_STATIC (var))
walk_tree (&DECL_INITIAL (var), scan_for_refs,
fn, visited_nodes);
get_canon_type (TREE_TYPE (var), false, false);
}
}
}
static tree
type_for_uid (int uid)
{
splay_tree_node result =
splay_tree_lookup (uid_to_canon_type, (splay_tree_key) uid);
if (result)
return (tree) result->value;
else return NULL;
}
static bitmap
subtype_map_for_uid (int uid, bool create)
{
splay_tree_node result = splay_tree_lookup (uid_to_subtype_map,
(splay_tree_key) uid);
if (result)
return (bitmap) result->value;
else if (create)
{
bitmap subtype_map = BITMAP_ALLOC (&ipa_obstack);
splay_tree_insert (uid_to_subtype_map,
uid,
(splay_tree_value)subtype_map);
return subtype_map;
}
else return NULL;
}
static void
close_type_seen (tree type)
{
tree field;
int i, uid;
tree binfo, base_binfo;
type = get_canon_type (type, true, true);
if (!type)
return;
uid = TYPE_UID (type);
if (bitmap_bit_p (been_there_done_that, uid))
return;
bitmap_set_bit (been_there_done_that, uid);
if (TYPE_BINFO (type))
for (binfo = TYPE_BINFO (type), i = 0;
BINFO_BASE_ITERATE (binfo, i, base_binfo); i++)
{
tree binfo_type = BINFO_TYPE (base_binfo);
bitmap subtype_map = subtype_map_for_uid
(TYPE_UID (TYPE_MAIN_VARIANT (binfo_type)), true);
bitmap_set_bit (subtype_map, uid);
close_type_seen (get_canon_type (binfo_type, true, true));
}
for (field = TYPE_FIELDS (type);
field;
field = TREE_CHAIN (field))
{
tree field_type;
if (TREE_CODE (field) != FIELD_DECL)
continue;
field_type = TREE_TYPE (field);
if (ipa_type_escape_star_count_of_interesting_or_array_type (field_type) >= 0)
close_type_seen (get_canon_type (field_type, true, true));
}
}
static void
close_type_exposed_parameter (tree type)
{
tree field;
int uid;
type = get_canon_type (type, false, false);
if (!type)
return;
uid = TYPE_UID (type);
gcc_assert (!POINTER_TYPE_P (type));
if (bitmap_bit_p (been_there_done_that, uid))
return;
bitmap_set_bit (been_there_done_that, uid);
for (field = TYPE_FIELDS (type);
field;
field = TREE_CHAIN (field))
{
tree field_type;
if (TREE_CODE (field) != FIELD_DECL)
continue;
field_type = get_canon_type (TREE_TYPE (field), false, false);
mark_interesting_type (field_type, EXPOSED_PARAMETER);
if (ipa_type_escape_star_count_of_interesting_type (field_type) == 0)
close_type_exposed_parameter (field_type);
}
}
static void
close_type_full_escape (tree type)
{
tree field;
unsigned int i;
int uid;
tree binfo, base_binfo;
bitmap_iterator bi;
bitmap subtype_map;
splay_tree_node address_result;
type = get_canon_type (type, true, true);
if (!type)
return;
uid = TYPE_UID (type);
if (bitmap_bit_p (been_there_done_that, uid))
return;
bitmap_set_bit (been_there_done_that, uid);
subtype_map = subtype_map_for_uid (uid, false);
if (TYPE_BINFO (type))
for (binfo = TYPE_BINFO (type), i = 0;
BINFO_BASE_ITERATE (binfo, i, base_binfo); i++)
{
tree binfotype = BINFO_TYPE (base_binfo);
binfotype = mark_type (binfotype, FULL_ESCAPE);
close_type_full_escape (binfotype);
}
if (subtype_map)
EXECUTE_IF_SET_IN_BITMAP (subtype_map, 0, i, bi)
{
tree subtype = type_for_uid (i);
subtype = mark_type (subtype, FULL_ESCAPE);
close_type_full_escape (subtype);
}
for (field = TYPE_FIELDS (type);
field;
field = TREE_CHAIN (field))
{
tree field_type;
if (TREE_CODE (field) != FIELD_DECL)
continue;
field_type = TREE_TYPE (field);
if (ipa_type_escape_star_count_of_interesting_or_array_type (field_type) >= 0)
{
field_type = mark_type (field_type, FULL_ESCAPE);
close_type_full_escape (field_type);
}
}
address_result = splay_tree_lookup (uid_to_addressof_up_map,
(splay_tree_key) uid);
if (address_result)
{
bitmap containing_classes = (bitmap) address_result->value;
EXECUTE_IF_SET_IN_BITMAP (containing_classes, 0, i, bi)
{
close_type_full_escape (type_for_uid (i));
}
}
}
static bitmap
close_addressof_down (int uid)
{
bitmap_iterator bi;
splay_tree_node result =
splay_tree_lookup (uid_to_addressof_down_map, (splay_tree_key) uid);
bitmap map = NULL;
bitmap new_map;
unsigned int i;
if (result)
map = (bitmap) result->value;
else
return NULL;
if (bitmap_bit_p (been_there_done_that, uid))
return map;
bitmap_set_bit (been_there_done_that, uid);
if (bitmap_bit_p (global_types_full_escape, uid))
{
BITMAP_FREE (map);
splay_tree_remove (uid_to_addressof_down_map, (splay_tree_key) uid);
return NULL;
}
new_map = BITMAP_ALLOC (&ipa_obstack);
EXECUTE_IF_SET_IN_BITMAP (map, 0, i, bi)
{
bitmap submap = close_addressof_down (i);
bitmap_set_bit (new_map, i);
if (submap)
bitmap_ior_into (new_map, submap);
}
result->value = (splay_tree_value) new_map;
BITMAP_FREE (map);
return new_map;
}
static unsigned int
type_escape_execute (void)
{
struct cgraph_node *node;
struct cgraph_varpool_node *vnode;
unsigned int i;
bitmap_iterator bi;
splay_tree_node result;
ipa_init ();
for (vnode = cgraph_varpool_nodes_queue; vnode; vnode = vnode->next_needed)
analyze_variable (vnode);
for (node = cgraph_nodes; node; node = node->next)
if (node->analyzed
&& (cgraph_is_master_clone (node)
|| (cgraph_function_body_availability (node) == AVAIL_OVERWRITABLE)))
analyze_function (node);
pointer_set_destroy (visited_nodes);
visited_nodes = NULL;
been_there_done_that = BITMAP_ALLOC (&ipa_obstack);
bitmap_tmp = BITMAP_ALLOC (&ipa_obstack);
bitmap_copy (bitmap_tmp, global_types_seen);
EXECUTE_IF_SET_IN_BITMAP (bitmap_tmp, 0, i, bi)
{
tree type = type_for_uid (i);
if (ipa_type_escape_star_count_of_interesting_or_array_type (type) >= 0)
close_type_seen (type);
}
bitmap_clear (been_there_done_that);
bitmap_copy (bitmap_tmp, global_types_exposed_parameter);
EXECUTE_IF_SET_IN_BITMAP (bitmap_tmp, 0, i, bi)
{
close_type_exposed_parameter (type_for_uid (i));
}
bitmap_clear (been_there_done_that);
bitmap_copy (bitmap_tmp, global_types_full_escape);
EXECUTE_IF_SET_IN_BITMAP (bitmap_tmp, 0, i, bi)
{
close_type_full_escape (type_for_uid (i));
}
bitmap_clear (been_there_done_that);
result = splay_tree_min (uid_to_addressof_down_map);
while (result)
{
int uid = result->key;
close_addressof_down (uid);
result = splay_tree_successor (uid_to_addressof_down_map, uid);
}
result = splay_tree_min (all_canon_types);
while (result)
{
tree type = (tree) result->value;
tree key = (tree) result->key;
if (POINTER_TYPE_P (type)
|| TREE_CODE (type) == ARRAY_TYPE)
{
splay_tree_remove (all_canon_types, (splay_tree_key) result->key);
splay_tree_remove (type_to_canon_type, (splay_tree_key) type);
splay_tree_remove (uid_to_canon_type, (splay_tree_key) TYPE_UID (type));
bitmap_clear_bit (global_types_seen, TYPE_UID (type));
}
result = splay_tree_successor (all_canon_types, (splay_tree_key) key);
}
if (dump_file)
{
EXECUTE_IF_SET_IN_BITMAP (global_types_seen, 0, i, bi)
{
tree type = type_for_uid (i);
fprintf(dump_file, "type %d ", i);
print_generic_expr (dump_file, type, 0);
if (bitmap_bit_p (global_types_full_escape, i))
fprintf(dump_file, " escaped\n");
else
fprintf(dump_file, " contained\n");
}
}
result = splay_tree_min (uid_to_addressof_up_map);
while (result)
{
int uid = (int)result->key;
bitmap bm = (bitmap)result->value;
BITMAP_FREE (bm);
splay_tree_remove (uid_to_addressof_up_map, (splay_tree_key) uid);
result = splay_tree_successor (uid_to_addressof_up_map, uid);
}
result = splay_tree_min (uid_to_subtype_map);
while (result)
{
bitmap b = (bitmap)result->value;
BITMAP_FREE(b);
splay_tree_remove (uid_to_subtype_map, result->key);
result = splay_tree_min (uid_to_subtype_map);
}
splay_tree_delete (uid_to_subtype_map);
uid_to_subtype_map = NULL;
BITMAP_FREE (global_types_exposed_parameter);
BITMAP_FREE (been_there_done_that);
BITMAP_FREE (bitmap_tmp);
BITMAP_FREE (results_of_malloc);
return 0;
}
static bool
gate_type_escape_vars (void)
{
return (flag_unit_at_a_time != 0 && flag_ipa_type_escape
&& !(errorcount || sorrycount));
}
struct tree_opt_pass pass_ipa_type_escape =
{
"type-escape-var",
gate_type_escape_vars,
type_escape_execute,
NULL,
NULL,
0,
TV_IPA_TYPE_ESCAPE,
0,
0,
0,
0,
0,
0
};