/* IPA Dead Field Elimination
   Copyright (C) 2019-2020 Free Software Foundation, Inc.

  Contributed by Erick Ochoa <erick.ochoa@theobroma-systems.com>

This file is part of GCC.

GCC is free software; you can redistribute it and/or modify it under
the terms of the GNU General Public License as published by the Free
Software Foundation; either version 3, or (at your option) any later
version.

GCC is distributed in the hope that it will be useful, but WITHOUT ANY
WARRANTY; without even the implied warranty of MERCHANTABILITY or
FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
for more details.

You should have received a copy of the GNU General Public License
along with GCC; see the file COPYING3.  If not see
<http://www.gnu.org/licenses/>.  */

#ifndef GCC_IPA_DFE
#define GCC_IPA_DFE

#include "ipa-type-escape-analysis.h"

/* Collect all types which point to a specific type set.  */
class specific_type_collector : public type_walker
{
public:
  /* C is the set of types that are to be looked for.  */
  specific_type_collector (std::set<tree> &c) : _collect_these_types (c)
  {};

  /* Get final result of all types which point to types in C.  */
  std::set<tree> get_set ();

private:
  /* _collect_these_types holds the input.  */
  const std::set<tree> &_collect_these_types;

  /* Working set that holds final result.  */
  std::set<tree> to_return;

  /* Sets which reach current subtype.  */
  std::set<tree> path;

  /* Push or pop from path.  */
  virtual void _walk_ARRAY_TYPE_pre (tree t);
  virtual void _walk_ARRAY_TYPE_post (tree t);
  virtual void _walk_UNION_TYPE_pre (tree t);
  virtual void _walk_UNION_TYPE_post (tree t);
  virtual void _walk_POINTER_TYPE_pre (tree t);
  virtual void _walk_POINTER_TYPE_post (tree t);

  /* If in input, place all parent types in to_return.  */
  virtual void _walk_RECORD_TYPE_pre (tree t);
  virtual void _walk_RECORD_TYPE_post (tree t);
};

/* Map old RECORD_TYPE -> new RECORD_TYPE.  */
typedef std::map<tree, tree> reorg_record_map_t;

/* Map RECORD_TYPE -> (FIELD_DECL -> delete).  */
typedef std::map<tree, std::pair<tree, bool> > reorg_field_map_t;

/* Class used to create new types derived from types that have fields
 * that can be deleted.  */
class type_reconstructor : public type_walker
{
public:
  type_reconstructor (record_field_offset_map_t records, const char *suffix)
    : _records (records), _suffix (suffix)
  {};

  /* Whether a type has already been modified.  */
  virtual bool is_memoized (tree t);

  // Final result for record map.
  reorg_record_map_t get_map ();

  /* Final result for field map.  */
  reorg_field_map_t get_field_map ();

  /* Map RECORD_TYPE -> is_modified.  */
  typedef std::map<tree, bool> is_modified_map_t;

protected:
  const char *get_new_suffix ();

  // Modifications to the current sub_type
  std::stack<tree> in_progress;

  // Path to current subtype
  std::stack<tree> for_reference;

  // OLD FIELD -> new FIELD
  typedef std::pair<tree, tree> field_tuple_t;

  // list of fields for new type
  typedef std::vector<field_tuple_t> field_tuple_list_t;

  // to deal with nested structures we need to have a stack
  // of field_tuple_list_t
  typedef std::stack<field_tuple_list_t> field_tuple_list_stack_t;

  // Which records can be modified.
  record_field_offset_map_t _records;

  // The new suffix
  const char *_suffix;

  // Which fields will be deleted.
  field_tuple_list_stack_t field_list_stack;

  // old RECORD_TYPE -> new RECORD_TYPE
  reorg_record_map_t _reorg_map;

  // old FIELD_DECL -> new FIELD_DECL
  reorg_field_map_t _reorg_fields;

  // old RECORD_TYPE -> is_modified
  is_modified_map_t modified_map;

  // Keep track of which types may need to be modified
  // defaults to not modified.
  void set_is_not_modified_yet (tree);

  // Mark all types reaching here will need to be modified.
  void mark_all_pointing_here_as_modified ();

  // If the type has been modified.
  bool get_is_modified (tree);

private:
  // Compute new FIELD_DECL list.
  virtual void _walk_field_pre (tree);
  virtual void _walk_field_post (tree);

  // Compute new RECORD_TYPE.
  virtual void _walk_RECORD_TYPE_pre (tree);
  virtual void _walk_RECORD_TYPE_post (tree);

  // Compute new type which points to new record type.
  virtual void _walk_ARRAY_TYPE_pre (tree);
  virtual void _walk_ARRAY_TYPE_post (tree);
  virtual void _walk_POINTER_TYPE_pre (tree);
  virtual void _walk_POINTER_TYPE_post (tree);
};

/* Modify expressions to match the new types.
 * Substitute old types with new types.
 * Handle pointer arithmetic.
 * Delete statements if needed.
 */
class expr_type_rewriter : public expr_walker
{
public:
  expr_type_rewriter (reorg_record_map_t map, reorg_field_map_t map2,
		    bool can_delete)
    : _delete (false), _can_delete (can_delete), _map (map), _map2 (map2)
  {
    /* Create an inverse map new RECORD_TYPE -> old RECORD_TYPE.  */
    for (reorg_record_map_t::iterator i = map.begin (),
	e = map.end (); i != e; ++i)
      {
	tree original = i->first;
	tree modified = i->second;
	_imap[modified] = original;
      }
  };

  // Handle pointer arithmetic with constants.
  void handle_pointer_arithmetic_constants (gimple *s, tree p, tree i);

  // Handle pointer POINTER_DIFF_EXPR.
  void handle_pointer_arithmetic_diff (gimple *s, tree p);

  // Handle POINTER_PLUS_EXPR.
  void handle_pointer_arithmetic_nonconstant (gimple *s, tree p, tree i, bool);

  // Find out if this type will be modified.
  bool is_interesting_type (tree);

  // Delete statement.
  bool delete_statement ();
  bool _delete;
  bool _can_delete;

private:
  // Old RECORD_TYPE -> new RECORD_TYPE.
  reorg_record_map_t _map;

  // Old FIELD_DECL -> new FIELD_DECL.
  reorg_field_map_t _map2;

  // New RECORD_TYPE -> old RECORD_TYPE.
  std::map<tree, tree> _imap;
  void _walk_post (tree e);

  // Substitute types and create new offset.
  void _walk_MEM_REF_post (tree e);

  // Substitute fields referred.
  void _walk_COMPONENT_REF_post (tree e);

  // Relayout parameters which are rewritten.
  void _walk_PARM_DECL_post (tree e);

  // Substitute return type.
  void _walk_FUNCTION_DECL_post (tree e);
};

// Walk all gimple and substitute types.
class gimple_type_rewriter : public gimple_walker
{
public:
  gimple_type_rewriter (reorg_record_map_t map, reorg_field_map_t map2,
		      bool can_delete)
    : exprTypeRewriter (map, map2, can_delete)
  {};

  void _rewrite_function_decl ();

private:
  // Substitute types in expressions
  expr_type_rewriter exprTypeRewriter;

  // handle pointer arithmetic
  void handle_pointer_arithmetic (gimple *s);

  // rewrite types in these statements
  virtual void _walk_pre_gphi (gphi *);
  virtual void _walk_pre_tree (tree);
  virtual void _walk_pre_greturn (greturn *s);
  virtual void _walk_pre_gassign (gassign *s);
};

// Get a set of all types pointing to types in RECORD_FIELD_OFFSET_MAP.
std::set<tree>
get_all_types_pointing_to (record_field_offset_map_t record_field_offset_map,
			   tpartitions_t casting);

typedef std::pair<reorg_record_map_t, reorg_field_map_t> reorg_maps_t;

// Compute the replacement types.
reorg_maps_t
get_types_replacement (record_field_offset_map_t record_field_offset_map,
		       std::set<tree> to_modify);

// Substitute types.
void
substitute_types_in_program (reorg_record_map_t map,
			     reorg_field_map_t field_map, bool _delete);

tree
get_new_identifier (tree type, const char *suffix);

#endif /* GCC_IPA_DFE */