#include "config.h"
#include "system.h"
#include "coretypes.h"
#include "tm.h"
#include "tree.h"
#include "tm_p.h"
#include "basic-block.h"
#include "tree-ssa-alias.h"
#include "internal-fn.h"
#include "gimple-expr.h"
#include "is-a.h"
#include "gimple.h"
#include "gimplify.h"
#include "gimple-ssa.h"
#include "tree-cfg.h"
#include "tree-phinodes.h"
#include "ssa-iterators.h"
#include "tree-ssa-loop-niter.h"
#include "tree-ssa-loop.h"
#include "tree-into-ssa.h"
#include "cfgloop.h"
#include "params.h"
#include "tree-pass.h"
#include "tree-inline.h"
#include "cgraph.h"

#include "gimple-pretty-print.h"
#include "gimple-iterator.h"
#include "stringpool.h"
#include "pointer-set.h"

void
print_generic_expr (FILE *file, tree t, int flags);

typedef vec <tree> expr_vec;

static bool
is_defined_in_stmt (gimple stmt, tree var)
{
  tree lhs;
  if (gimple_code (stmt) == GIMPLE_ASSIGN)
    {

      lhs = gimple_assign_lhs (stmt);
      if (lhs == var)
        return true;
    }
  return false;
}

static bool
is_defined_in_bb (gimple_stmt_iterator gsi, tree var)
{
  for (; !gsi_end_p (gsi); gsi_prev (&gsi))
    {
      if (is_defined_in_stmt (gsi_stmt (gsi), var))
        return true;
    }
  return false;
}

static bool
is_defined_outside (gimple use, tree var)
{
  gimple_stmt_iterator gsi;
  gsi = gsi_for_stmt (use);
  gsi_prev (&gsi);
  /* FIXME Right now we only consider single bb loops. */
  /*       We have to expand that, once the first try works. */
  return !is_defined_in_bb (gsi, var);
}

/* FIXME Is there a standard function to do this? */
static bool
contained (expr_vec v, tree var)
{
  int i = 0;
  tree u;

  FOR_EACH_VEC_ELT (v, i, u)
    {
      if (u == var)
        return true;
    }
  return false;
}

typedef void (*op_callback) (void * g, tree op, gimple stmt, unsigned index);

static void
for_all_operands_in_loop (struct loop * loop, op_callback cb, void * g)
{
  basic_block * bbs;
  basic_block bb;
  unsigned num_nodes;
  unsigned i;
  unsigned j;
  gimple stmt;
  tree op;

  bbs = get_loop_body (loop);
  num_nodes = loop->num_nodes;
  for (i = 0; i < num_nodes; i++)
    {
      bb = bbs[i];
      gimple_stmt_iterator iter = gsi_start_bb (bb);
      while (!gsi_end_p (iter))
        {
          stmt = gsi_stmt (iter);
          for (j = 0; j < gimple_num_ops (stmt); j++)
            {
              op = gimple_op (stmt, j);
              if (op)
                {
                  cb (g, op, stmt, j);
                }
            }
          gsi_next (&iter);
        }
     }
  free (bbs);
}

static void
collect_cb (void * g, tree op, gimple stmt, unsigned index)
{
  expr_vec * v = (expr_vec *) g;
  enum tree_code code;

  if (gimple_code (stmt) == GIMPLE_ASSIGN && index == 0)
    {
      /* I assume operand 0 of an assignment is the lhs. */
      return;
    }

  code = TREE_CODE (op);
  if ((code == VAR_DECL || code == PARM_DECL) &&
      ! contained (*v, op)  &&
      is_defined_outside (stmt, op))
    {
      v->safe_push (op);
    }
}

static expr_vec
collect_def_outside (struct loop * loop)
{
  expr_vec v = vNULL;
  for_all_operands_in_loop (loop, collect_cb, (void *) & v);
  return v;
}

struct var_to_parm_cb_p
{
  tree d;
  tree d_parm;
};

static void
var_to_parm_cb (void * g, tree op, gimple stmt, unsigned index)
{
  struct var_to_parm_cb_p * p = (struct var_to_parm_cb_p *) g;

  if (p->d == op)
    {
      gimple_set_op (stmt, index, p->d_parm);
    }
}

static void
convert_var_to_parm_uses (struct loop * loop, tree d, tree d_parm)
{
  struct var_to_parm_cb_p c;
  c.d = d;
  c.d_parm = d_parm;
  for_all_operands_in_loop (loop, var_to_parm_cb, (void *) & c);
}

static void
body_to_fun (struct loop * loop, expr_vec uv)
{
  tree name, decl, type, t, block;
  gimple_seq body = NULL;
  gimple bind;
  int i;
  vec<tree> args;
  struct function *fun;
  basic_block new_bb, preheader;
  edge out;
  basic_block in_bb, out_bb;

  /* Dump the original function before transformation. */
  if (dump_file)
    dump_function_to_file (cfun->decl, dump_file, 0);

  /* Make the new function similar to create_omp_child_function. */
  type = build_function_type_list (void_type_node, ptr_type_node, NULL_TREE);
  name = get_file_function_name ("N");
  decl = build_decl (input_location, FUNCTION_DECL, name, type);

  TREE_STATIC (decl) = 1;
  TREE_USED (decl) = 1;
  DECL_ARTIFICIAL (decl) = 1;
  DECL_NAMELESS (decl) = 0;
  DECL_IGNORED_P (decl) = 0;
  TREE_PUBLIC (decl) = 0;
  DECL_UNINLINABLE (decl) = 1;
  DECL_EXTERNAL (decl) = 0;
  DECL_CONTEXT (decl) = NULL_TREE;

  block = make_node (BLOCK);
  DECL_INITIAL (decl) = block;

  t = build_decl (DECL_SOURCE_LOCATION (decl),
                  RESULT_DECL, NULL_TREE, void_type_node);

  DECL_ARTIFICIAL (t) = 1;
  DECL_IGNORED_P (t) = 1;
  DECL_CONTEXT (t) = decl;
  DECL_RESULT (decl) = t;

  tree d_parm = NULL;
  tree d = NULL;
  tree t_first = NULL;
  t = NULL;

  args = vNULL;

  /* Prepare the arguments collected earlier on. */
  i = 0;
  FOR_EACH_VEC_ELT (uv, i, d)
    {
      args.safe_push (d);

      d_parm = build_decl (DECL_SOURCE_LOCATION (decl), PARM_DECL,
                           DECL_NAME (d), copy_node (TREE_TYPE (d)));
      DECL_ARG_TYPE (d_parm) = TREE_TYPE (d);
      DECL_ARTIFICIAL (d_parm) = 1;
      DECL_CONTEXT (d_parm) = decl;
      TYPE_RESTRICT (TREE_TYPE (d_parm)) = 1;
      convert_var_to_parm_uses (loop, d, d_parm);

      if (!t_first)
        {
          t = d_parm;
          t_first = d_parm;
        }
      else
        {
          DECL_CHAIN (t) = d_parm;
          t = d_parm;
        }
    }

  DECL_ARGUMENTS (decl) = t_first;

  push_struct_function (decl);
  cfun->function_end_locus = DECL_SOURCE_LOCATION (decl);
  pop_cfun ();

  /* Fill the function body. */
  bind = gimple_build_bind (NULL, body, block);
  gimple_seq_add_stmt (&body, bind);
  gimple_set_body (decl, body);

  record_loop_exits ();
  fun = DECL_STRUCT_FUNCTION (decl);
  out = single_exit (loop);
  out_bb = split_edge (out);

  /* FIXME I patched this function such that
           it always creates the
           preheader.
           Maybe this is the problem?
  */
  preheader = create_preheader (loop, 0);
  in_bb = preheader;

  new_bb = move_sese_region_to_fn (fun, in_bb,
                                   out_bb, NULL_TREE);

  DECL_STRUCT_FUNCTION (decl)->curr_properties = cfun->curr_properties;

  /* Make the new function known. */
  cgraph_add_new_function (decl, true);

  gimple_stmt_iterator call_iter = gsi_start_bb (new_bb);

  gimple call_stmt;
  call_stmt = gimple_build_call_vec (decl, args);

  gsi_insert_after (&call_iter, call_stmt,
                    GSI_NEW_STMT);

  rebuild_cgraph_edges ();

  if (dump_file)
    dump_function_to_file (decl, dump_file, 0);
}

static unsigned int
extract_loop_to_function (void)
{
  struct loop *loop;
  expr_vec v = vNULL;

  FOR_EACH_LOOP (loop, LI_ONLY_INNERMOST)
    {
      v = collect_def_outside (loop);
      body_to_fun (loop, v);
    }

  return 0;
}

static bool
gate_uninline_innermost_loops (void)
{
  return flag_uninline_innermost_loops != 0;
}

namespace {

const pass_data pass_data_uninline_innermost_loops =
{
  GIMPLE_PASS, /* type */
  "uninline-innermost-loops", /* name */
  OPTGROUP_NONE, /* optinfo_flags */
  true, /* has_execute */
  TV_UNINLINE_INNERMOST_LOOPS, /* tv_id */
  0, /* properties_required */
  0, /* properties_provided */
  0, /* properties_destroyed */
  0, /* todo_flags_start */
  0, /* todo_flags_finish */
};

class pass_uninline_innermost_loops: public gimple_opt_pass
{
public:
  pass_uninline_innermost_loops (gcc::context *ctxt)
    : gimple_opt_pass (pass_data_uninline_innermost_loops, ctxt)
  {}

  /* opt_pass methods: */
  virtual bool gate (function *) { return gate_uninline_innermost_loops (); }
  virtual unsigned int execute (function *) { return extract_loop_to_function (); }

};

} // anon namespace

gimple_opt_pass *
make_pass_uninline_innermost_loops (gcc::context *ctxt)
{
  return new pass_uninline_innermost_loops (ctxt);
}