OpenCores
URL https://opencores.org/ocsvn/openrisc/openrisc/trunk

Subversion Repositories openrisc

[/] [openrisc/] [trunk/] [gnu-stable/] [gcc-4.5.1/] [gcc/] [tree-tailcall.c] - Blame information for rev 847

Go to most recent revision | Details | Compare with Previous | View Log

Line No. Rev Author Line
1 280 jeremybenn
/* Tail call optimization on trees.
2
   Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010
3
   Free Software Foundation, Inc.
4
 
5
This file is part of GCC.
6
 
7
GCC is free software; you can redistribute it and/or modify
8
it under the terms of the GNU General Public License as published by
9
the Free Software Foundation; either version 3, or (at your option)
10
any later version.
11
 
12
GCC is distributed in the hope that it will be useful,
13
but WITHOUT ANY WARRANTY; without even the implied warranty of
14
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15
GNU General Public License for more details.
16
 
17
You should have received a copy of the GNU General Public License
18
along with GCC; see the file COPYING3.  If not see
19
<http://www.gnu.org/licenses/>.  */
20
 
21
#include "config.h"
22
#include "system.h"
23
#include "coretypes.h"
24
#include "tm.h"
25
#include "tree.h"
26
#include "rtl.h"
27
#include "tm_p.h"
28
#include "hard-reg-set.h"
29
#include "basic-block.h"
30
#include "function.h"
31
#include "tree-flow.h"
32
#include "tree-dump.h"
33
#include "diagnostic.h"
34
#include "except.h"
35
#include "tree-pass.h"
36
#include "flags.h"
37
#include "langhooks.h"
38
#include "dbgcnt.h"
39
 
40
/* The file implements the tail recursion elimination.  It is also used to
41
   analyze the tail calls in general, passing the results to the rtl level
42
   where they are used for sibcall optimization.
43
 
44
   In addition to the standard tail recursion elimination, we handle the most
45
   trivial cases of making the call tail recursive by creating accumulators.
46
   For example the following function
47
 
48
   int sum (int n)
49
   {
50
     if (n > 0)
51
       return n + sum (n - 1);
52
     else
53
       return 0;
54
   }
55
 
56
   is transformed into
57
 
58
   int sum (int n)
59
   {
60
     int acc = 0;
61
 
62
     while (n > 0)
63
       acc += n--;
64
 
65
     return acc;
66
   }
67
 
68
   To do this, we maintain two accumulators (a_acc and m_acc) that indicate
69
   when we reach the return x statement, we should return a_acc + x * m_acc
70
   instead.  They are initially initialized to 0 and 1, respectively,
71
   so the semantics of the function is obviously preserved.  If we are
72
   guaranteed that the value of the accumulator never change, we
73
   omit the accumulator.
74
 
75
   There are three cases how the function may exit.  The first one is
76
   handled in adjust_return_value, the other two in adjust_accumulator_values
77
   (the second case is actually a special case of the third one and we
78
   present it separately just for clarity):
79
 
80
   1) Just return x, where x is not in any of the remaining special shapes.
81
      We rewrite this to a gimple equivalent of return m_acc * x + a_acc.
82
 
83
   2) return f (...), where f is the current function, is rewritten in a
84
      classical tail-recursion elimination way, into assignment of arguments
85
      and jump to the start of the function.  Values of the accumulators
86
      are unchanged.
87
 
88
   3) return a + m * f(...), where a and m do not depend on call to f.
89
      To preserve the semantics described before we want this to be rewritten
90
      in such a way that we finally return
91
 
92
      a_acc + (a + m * f(...)) * m_acc = (a_acc + a * m_acc) + (m * m_acc) * f(...).
93
 
94
      I.e. we increase a_acc by a * m_acc, multiply m_acc by m and
95
      eliminate the tail call to f.  Special cases when the value is just
96
      added or just multiplied are obtained by setting a = 0 or m = 1.
97
 
98
   TODO -- it is possible to do similar tricks for other operations.  */
99
 
100
/* A structure that describes the tailcall.  */
101
 
102
struct tailcall
103
{
104
  /* The iterator pointing to the call statement.  */
105
  gimple_stmt_iterator call_gsi;
106
 
107
  /* True if it is a call to the current function.  */
108
  bool tail_recursion;
109
 
110
  /* The return value of the caller is mult * f + add, where f is the return
111
     value of the call.  */
112
  tree mult, add;
113
 
114
  /* Next tailcall in the chain.  */
115
  struct tailcall *next;
116
};
117
 
118
/* The variables holding the value of multiplicative and additive
119
   accumulator.  */
120
static tree m_acc, a_acc;
121
 
122
static bool suitable_for_tail_opt_p (void);
123
static bool optimize_tail_call (struct tailcall *, bool);
124
static void eliminate_tail_call (struct tailcall *);
125
static void find_tail_calls (basic_block, struct tailcall **);
126
 
127
/* Returns false when the function is not suitable for tail call optimization
128
   from some reason (e.g. if it takes variable number of arguments).  */
129
 
130
static bool
131
suitable_for_tail_opt_p (void)
132
{
133
  referenced_var_iterator rvi;
134
  tree var;
135
 
136
  if (cfun->stdarg)
137
    return false;
138
 
139
  /* No local variable nor structure field should be call-used.  */
140
  FOR_EACH_REFERENCED_VAR (var, rvi)
141
    {
142
      if (!is_global_var (var)
143
          && is_call_used (var))
144
        return false;
145
    }
146
 
147
  return true;
148
}
149
/* Returns false when the function is not suitable for tail call optimization
150
   from some reason (e.g. if it takes variable number of arguments).
151
   This test must pass in addition to suitable_for_tail_opt_p in order to make
152
   tail call discovery happen.  */
153
 
154
static bool
155
suitable_for_tail_call_opt_p (void)
156
{
157
  tree param;
158
 
159
  /* alloca (until we have stack slot life analysis) inhibits
160
     sibling call optimizations, but not tail recursion.  */
161
  if (cfun->calls_alloca)
162
    return false;
163
 
164
  /* If we are using sjlj exceptions, we may need to add a call to
165
     _Unwind_SjLj_Unregister at exit of the function.  Which means
166
     that we cannot do any sibcall transformations.  */
167
  if (USING_SJLJ_EXCEPTIONS && current_function_has_exception_handlers ())
168
    return false;
169
 
170
  /* Any function that calls setjmp might have longjmp called from
171
     any called function.  ??? We really should represent this
172
     properly in the CFG so that this needn't be special cased.  */
173
  if (cfun->calls_setjmp)
174
    return false;
175
 
176
  /* ??? It is OK if the argument of a function is taken in some cases,
177
     but not in all cases.  See PR15387 and PR19616.  Revisit for 4.1.  */
178
  for (param = DECL_ARGUMENTS (current_function_decl);
179
       param;
180
       param = TREE_CHAIN (param))
181
    if (TREE_ADDRESSABLE (param))
182
      return false;
183
 
184
  return true;
185
}
186
 
187
/* Checks whether the expression EXPR in stmt AT is independent of the
188
   statement pointed to by GSI (in a sense that we already know EXPR's value
189
   at GSI).  We use the fact that we are only called from the chain of
190
   basic blocks that have only single successor.  Returns the expression
191
   containing the value of EXPR at GSI.  */
192
 
193
static tree
194
independent_of_stmt_p (tree expr, gimple at, gimple_stmt_iterator gsi)
195
{
196
  basic_block bb, call_bb, at_bb;
197
  edge e;
198
  edge_iterator ei;
199
 
200
  if (is_gimple_min_invariant (expr))
201
    return expr;
202
 
203
  if (TREE_CODE (expr) != SSA_NAME)
204
    return NULL_TREE;
205
 
206
  /* Mark the blocks in the chain leading to the end.  */
207
  at_bb = gimple_bb (at);
208
  call_bb = gimple_bb (gsi_stmt (gsi));
209
  for (bb = call_bb; bb != at_bb; bb = single_succ (bb))
210
    bb->aux = &bb->aux;
211
  bb->aux = &bb->aux;
212
 
213
  while (1)
214
    {
215
      at = SSA_NAME_DEF_STMT (expr);
216
      bb = gimple_bb (at);
217
 
218
      /* The default definition or defined before the chain.  */
219
      if (!bb || !bb->aux)
220
        break;
221
 
222
      if (bb == call_bb)
223
        {
224
          for (; !gsi_end_p (gsi); gsi_next (&gsi))
225
            if (gsi_stmt (gsi) == at)
226
              break;
227
 
228
          if (!gsi_end_p (gsi))
229
            expr = NULL_TREE;
230
          break;
231
        }
232
 
233
      if (gimple_code (at) != GIMPLE_PHI)
234
        {
235
          expr = NULL_TREE;
236
          break;
237
        }
238
 
239
      FOR_EACH_EDGE (e, ei, bb->preds)
240
        if (e->src->aux)
241
          break;
242
      gcc_assert (e);
243
 
244
      expr = PHI_ARG_DEF_FROM_EDGE (at, e);
245
      if (TREE_CODE (expr) != SSA_NAME)
246
        {
247
          /* The value is a constant.  */
248
          break;
249
        }
250
    }
251
 
252
  /* Unmark the blocks.  */
253
  for (bb = call_bb; bb != at_bb; bb = single_succ (bb))
254
    bb->aux = NULL;
255
  bb->aux = NULL;
256
 
257
  return expr;
258
}
259
 
260
/* Simulates the effect of an assignment STMT on the return value of the tail
261
   recursive CALL passed in ASS_VAR.  M and A are the multiplicative and the
262
   additive factor for the real return value.  */
263
 
264
static bool
265
process_assignment (gimple stmt, gimple_stmt_iterator call, tree *m,
266
                    tree *a, tree *ass_var)
267
{
268
  tree op0, op1, non_ass_var;
269
  tree dest = gimple_assign_lhs (stmt);
270
  enum tree_code code = gimple_assign_rhs_code (stmt);
271
  enum gimple_rhs_class rhs_class = get_gimple_rhs_class (code);
272
  tree src_var = gimple_assign_rhs1 (stmt);
273
 
274
  /* See if this is a simple copy operation of an SSA name to the function
275
     result.  In that case we may have a simple tail call.  Ignore type
276
     conversions that can never produce extra code between the function
277
     call and the function return.  */
278
  if ((rhs_class == GIMPLE_SINGLE_RHS || gimple_assign_cast_p (stmt))
279
      && (TREE_CODE (src_var) == SSA_NAME))
280
    {
281
      /* Reject a tailcall if the type conversion might need
282
         additional code.  */
283
      if (gimple_assign_cast_p (stmt)
284
          && TYPE_MODE (TREE_TYPE (dest)) != TYPE_MODE (TREE_TYPE (src_var)))
285
        return false;
286
 
287
      if (src_var != *ass_var)
288
        return false;
289
 
290
      *ass_var = dest;
291
      return true;
292
    }
293
 
294
  if (rhs_class != GIMPLE_BINARY_RHS)
295
    return false;
296
 
297
  /* Accumulator optimizations will reverse the order of operations.
298
     We can only do that for floating-point types if we're assuming
299
     that addition and multiplication are associative.  */
300
  if (!flag_associative_math)
301
    if (FLOAT_TYPE_P (TREE_TYPE (DECL_RESULT (current_function_decl))))
302
      return false;
303
 
304
  /* We only handle the code like
305
 
306
     x = call ();
307
     y = m * x;
308
     z = y + a;
309
     return z;
310
 
311
     TODO -- Extend it for cases where the linear transformation of the output
312
     is expressed in a more complicated way.  */
313
 
314
  op0 = gimple_assign_rhs1 (stmt);
315
  op1 = gimple_assign_rhs2 (stmt);
316
 
317
  if (op0 == *ass_var
318
      && (non_ass_var = independent_of_stmt_p (op1, stmt, call)))
319
    ;
320
  else if (op1 == *ass_var
321
           && (non_ass_var = independent_of_stmt_p (op0, stmt, call)))
322
    ;
323
  else
324
    return false;
325
 
326
  switch (code)
327
    {
328
    case PLUS_EXPR:
329
      *a = non_ass_var;
330
      *ass_var = dest;
331
      return true;
332
 
333
    case MULT_EXPR:
334
      *m = non_ass_var;
335
      *ass_var = dest;
336
      return true;
337
 
338
      /* TODO -- Handle other codes (NEGATE_EXPR, MINUS_EXPR,
339
         POINTER_PLUS_EXPR).  */
340
 
341
    default:
342
      return false;
343
    }
344
}
345
 
346
/* Propagate VAR through phis on edge E.  */
347
 
348
static tree
349
propagate_through_phis (tree var, edge e)
350
{
351
  basic_block dest = e->dest;
352
  gimple_stmt_iterator gsi;
353
 
354
  for (gsi = gsi_start_phis (dest); !gsi_end_p (gsi); gsi_next (&gsi))
355
    {
356
      gimple phi = gsi_stmt (gsi);
357
      if (PHI_ARG_DEF_FROM_EDGE (phi, e) == var)
358
        return PHI_RESULT (phi);
359
    }
360
  return var;
361
}
362
 
363
/* Finds tailcalls falling into basic block BB. The list of found tailcalls is
364
   added to the start of RET.  */
365
 
366
static void
367
find_tail_calls (basic_block bb, struct tailcall **ret)
368
{
369
  tree ass_var = NULL_TREE, ret_var, func, param;
370
  gimple stmt, call = NULL;
371
  gimple_stmt_iterator gsi, agsi;
372
  bool tail_recursion;
373
  struct tailcall *nw;
374
  edge e;
375
  tree m, a;
376
  basic_block abb;
377
  size_t idx;
378
  tree var;
379
  referenced_var_iterator rvi;
380
 
381
  if (!single_succ_p (bb))
382
    return;
383
 
384
  for (gsi = gsi_last_bb (bb); !gsi_end_p (gsi); gsi_prev (&gsi))
385
    {
386
      stmt = gsi_stmt (gsi);
387
 
388
      /* Ignore labels.  */
389
      if (gimple_code (stmt) == GIMPLE_LABEL || is_gimple_debug (stmt))
390
        continue;
391
 
392
      /* Check for a call.  */
393
      if (is_gimple_call (stmt))
394
        {
395
          call = stmt;
396
          ass_var = gimple_call_lhs (stmt);
397
          break;
398
        }
399
 
400
      /* If the statement references memory or volatile operands, fail.  */
401
      if (gimple_references_memory_p (stmt)
402
          || gimple_has_volatile_ops (stmt))
403
        return;
404
    }
405
 
406
  if (gsi_end_p (gsi))
407
    {
408
      edge_iterator ei;
409
      /* Recurse to the predecessors.  */
410
      FOR_EACH_EDGE (e, ei, bb->preds)
411
        find_tail_calls (e->src, ret);
412
 
413
      return;
414
    }
415
 
416
  /* If the LHS of our call is not just a simple register, we can't
417
     transform this into a tail or sibling call.  This situation happens,
418
     in (e.g.) "*p = foo()" where foo returns a struct.  In this case
419
     we won't have a temporary here, but we need to carry out the side
420
     effect anyway, so tailcall is impossible.
421
 
422
     ??? In some situations (when the struct is returned in memory via
423
     invisible argument) we could deal with this, e.g. by passing 'p'
424
     itself as that argument to foo, but it's too early to do this here,
425
     and expand_call() will not handle it anyway.  If it ever can, then
426
     we need to revisit this here, to allow that situation.  */
427
  if (ass_var && !is_gimple_reg (ass_var))
428
    return;
429
 
430
  /* We found the call, check whether it is suitable.  */
431
  tail_recursion = false;
432
  func = gimple_call_fndecl (call);
433
  if (func == current_function_decl)
434
    {
435
      tree arg;
436
      for (param = DECL_ARGUMENTS (func), idx = 0;
437
           param && idx < gimple_call_num_args (call);
438
           param = TREE_CHAIN (param), idx ++)
439
        {
440
          arg = gimple_call_arg (call, idx);
441
          if (param != arg)
442
            {
443
              /* Make sure there are no problems with copying.  The parameter
444
                 have a copyable type and the two arguments must have reasonably
445
                 equivalent types.  The latter requirement could be relaxed if
446
                 we emitted a suitable type conversion statement.  */
447
              if (!is_gimple_reg_type (TREE_TYPE (param))
448
                  || !useless_type_conversion_p (TREE_TYPE (param),
449
                                                 TREE_TYPE (arg)))
450
                break;
451
 
452
              /* The parameter should be a real operand, so that phi node
453
                 created for it at the start of the function has the meaning
454
                 of copying the value.  This test implies is_gimple_reg_type
455
                 from the previous condition, however this one could be
456
                 relaxed by being more careful with copying the new value
457
                 of the parameter (emitting appropriate GIMPLE_ASSIGN and
458
                 updating the virtual operands).  */
459
              if (!is_gimple_reg (param))
460
                break;
461
            }
462
        }
463
      if (idx == gimple_call_num_args (call) && !param)
464
        tail_recursion = true;
465
    }
466
 
467
  /* Make sure the tail invocation of this function does not refer
468
     to local variables.  */
469
  FOR_EACH_REFERENCED_VAR (var, rvi)
470
    {
471
      if (TREE_CODE (var) != PARM_DECL
472
          && auto_var_in_fn_p (var, cfun->decl)
473
          && ref_maybe_used_by_stmt_p (call, var))
474
        return;
475
    }
476
 
477
  /* Now check the statements after the call.  None of them has virtual
478
     operands, so they may only depend on the call through its return
479
     value.  The return value should also be dependent on each of them,
480
     since we are running after dce.  */
481
  m = NULL_TREE;
482
  a = NULL_TREE;
483
 
484
  abb = bb;
485
  agsi = gsi;
486
  while (1)
487
    {
488
      tree tmp_a = NULL_TREE;
489
      tree tmp_m = NULL_TREE;
490
      gsi_next (&agsi);
491
 
492
      while (gsi_end_p (agsi))
493
        {
494
          ass_var = propagate_through_phis (ass_var, single_succ_edge (abb));
495
          abb = single_succ (abb);
496
          agsi = gsi_start_bb (abb);
497
        }
498
 
499
      stmt = gsi_stmt (agsi);
500
 
501
      if (gimple_code (stmt) == GIMPLE_LABEL)
502
        continue;
503
 
504
      if (gimple_code (stmt) == GIMPLE_RETURN)
505
        break;
506
 
507
      if (is_gimple_debug (stmt))
508
        continue;
509
 
510
      if (gimple_code (stmt) != GIMPLE_ASSIGN)
511
        return;
512
 
513
      /* This is a gimple assign. */
514
      if (! process_assignment (stmt, gsi, &tmp_m, &tmp_a, &ass_var))
515
        return;
516
 
517
      if (tmp_a)
518
        {
519
          if (a)
520
            a = fold_build2 (PLUS_EXPR, TREE_TYPE (tmp_a), a, tmp_a);
521
          else
522
            a = tmp_a;
523
        }
524
      if (tmp_m)
525
        {
526
          if (m)
527
            m = fold_build2 (MULT_EXPR, TREE_TYPE (tmp_m), m, tmp_m);
528
          else
529
            m = tmp_m;
530
 
531
          if (a)
532
            a = fold_build2 (MULT_EXPR, TREE_TYPE (tmp_m), a, tmp_m);
533
        }
534
    }
535
 
536
  /* See if this is a tail call we can handle.  */
537
  ret_var = gimple_return_retval (stmt);
538
 
539
  /* We may proceed if there either is no return value, or the return value
540
     is identical to the call's return.  */
541
  if (ret_var
542
      && (ret_var != ass_var))
543
    return;
544
 
545
  /* If this is not a tail recursive call, we cannot handle addends or
546
     multiplicands.  */
547
  if (!tail_recursion && (m || a))
548
    return;
549
 
550
  nw = XNEW (struct tailcall);
551
 
552
  nw->call_gsi = gsi;
553
 
554
  nw->tail_recursion = tail_recursion;
555
 
556
  nw->mult = m;
557
  nw->add = a;
558
 
559
  nw->next = *ret;
560
  *ret = nw;
561
}
562
 
563
/* Helper to insert PHI_ARGH to the phi of VAR in the destination of edge E.  */
564
 
565
static void
566
add_successor_phi_arg (edge e, tree var, tree phi_arg)
567
{
568
  gimple_stmt_iterator gsi;
569
 
570
  for (gsi = gsi_start_phis (e->dest); !gsi_end_p (gsi); gsi_next (&gsi))
571
    if (PHI_RESULT (gsi_stmt (gsi)) == var)
572
      break;
573
 
574
  gcc_assert (!gsi_end_p (gsi));
575
  add_phi_arg (gsi_stmt (gsi), phi_arg, e, UNKNOWN_LOCATION);
576
}
577
 
578
/* Creates a GIMPLE statement which computes the operation specified by
579
   CODE, OP0 and OP1 to a new variable with name LABEL and inserts the
580
   statement in the position specified by GSI and UPDATE.  Returns the
581
   tree node of the statement's result.  */
582
 
583
static tree
584
adjust_return_value_with_ops (enum tree_code code, const char *label,
585
                              tree acc, tree op1, gimple_stmt_iterator gsi)
586
{
587
 
588
  tree ret_type = TREE_TYPE (DECL_RESULT (current_function_decl));
589
  tree tmp = create_tmp_var (ret_type, label);
590
  gimple stmt;
591
  tree result;
592
 
593
  if (TREE_CODE (ret_type) == COMPLEX_TYPE
594
      || TREE_CODE (ret_type) == VECTOR_TYPE)
595
    DECL_GIMPLE_REG_P (tmp) = 1;
596
  add_referenced_var (tmp);
597
 
598
  if (types_compatible_p (TREE_TYPE (acc), TREE_TYPE (op1)))
599
    stmt = gimple_build_assign_with_ops (code, tmp, acc, op1);
600
  else
601
    {
602
      tree rhs = fold_convert (TREE_TYPE (acc),
603
                               fold_build2 (code,
604
                                            TREE_TYPE (op1),
605
                                            fold_convert (TREE_TYPE (op1), acc),
606
                                            op1));
607
      rhs = force_gimple_operand_gsi (&gsi, rhs,
608
                                      false, NULL, true, GSI_CONTINUE_LINKING);
609
      stmt = gimple_build_assign (NULL_TREE, rhs);
610
    }
611
 
612
  result = make_ssa_name (tmp, stmt);
613
  gimple_assign_set_lhs (stmt, result);
614
  update_stmt (stmt);
615
  gsi_insert_before (&gsi, stmt, GSI_NEW_STMT);
616
  return result;
617
}
618
 
619
/* Creates a new GIMPLE statement that adjusts the value of accumulator ACC by
620
   the computation specified by CODE and OP1 and insert the statement
621
   at the position specified by GSI as a new statement.  Returns new SSA name
622
   of updated accumulator.  */
623
 
624
static tree
625
update_accumulator_with_ops (enum tree_code code, tree acc, tree op1,
626
                             gimple_stmt_iterator gsi)
627
{
628
  gimple stmt;
629
  tree var;
630
  if (types_compatible_p (TREE_TYPE (acc), TREE_TYPE (op1)))
631
    stmt = gimple_build_assign_with_ops (code, SSA_NAME_VAR (acc), acc, op1);
632
  else
633
    {
634
      tree rhs = fold_convert (TREE_TYPE (acc),
635
                               fold_build2 (code,
636
                                            TREE_TYPE (op1),
637
                                            fold_convert (TREE_TYPE (op1), acc),
638
                                            op1));
639
      rhs = force_gimple_operand_gsi (&gsi, rhs,
640
                                      false, NULL, false, GSI_CONTINUE_LINKING);
641
      stmt = gimple_build_assign (NULL_TREE, rhs);
642
    }
643
  var = make_ssa_name (SSA_NAME_VAR (acc), stmt);
644
  gimple_assign_set_lhs (stmt, var);
645
  update_stmt (stmt);
646
  gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);
647
  return var;
648
}
649
 
650
/* Adjust the accumulator values according to A and M after GSI, and update
651
   the phi nodes on edge BACK.  */
652
 
653
static void
654
adjust_accumulator_values (gimple_stmt_iterator gsi, tree m, tree a, edge back)
655
{
656
  tree var, a_acc_arg, m_acc_arg;
657
 
658
  if (m)
659
    m = force_gimple_operand_gsi (&gsi, m, true, NULL, true, GSI_SAME_STMT);
660
  if (a)
661
    a = force_gimple_operand_gsi (&gsi, a, true, NULL, true, GSI_SAME_STMT);
662
 
663
  a_acc_arg = a_acc;
664
  m_acc_arg = m_acc;
665
  if (a)
666
    {
667
      if (m_acc)
668
        {
669
          if (integer_onep (a))
670
            var = m_acc;
671
          else
672
            var = adjust_return_value_with_ops (MULT_EXPR, "acc_tmp", m_acc,
673
                                                a, gsi);
674
        }
675
      else
676
        var = a;
677
 
678
      a_acc_arg = update_accumulator_with_ops (PLUS_EXPR, a_acc, var, gsi);
679
    }
680
 
681
  if (m)
682
    m_acc_arg = update_accumulator_with_ops (MULT_EXPR, m_acc, m, gsi);
683
 
684
  if (a_acc)
685
    add_successor_phi_arg (back, a_acc, a_acc_arg);
686
 
687
  if (m_acc)
688
    add_successor_phi_arg (back, m_acc, m_acc_arg);
689
}
690
 
691
/* Adjust value of the return at the end of BB according to M and A
692
   accumulators.  */
693
 
694
static void
695
adjust_return_value (basic_block bb, tree m, tree a)
696
{
697
  tree retval;
698
  gimple ret_stmt = gimple_seq_last_stmt (bb_seq (bb));
699
  gimple_stmt_iterator gsi = gsi_last_bb (bb);
700
 
701
  gcc_assert (gimple_code (ret_stmt) == GIMPLE_RETURN);
702
 
703
  retval = gimple_return_retval (ret_stmt);
704
  if (!retval || retval == error_mark_node)
705
    return;
706
 
707
  if (m)
708
    retval = adjust_return_value_with_ops (MULT_EXPR, "mul_tmp", m_acc, retval,
709
                                           gsi);
710
  if (a)
711
    retval = adjust_return_value_with_ops (PLUS_EXPR, "acc_tmp", a_acc, retval,
712
                                           gsi);
713
  gimple_return_set_retval (ret_stmt, retval);
714
  update_stmt (ret_stmt);
715
}
716
 
717
/* Subtract COUNT and FREQUENCY from the basic block and it's
718
   outgoing edge.  */
719
static void
720
decrease_profile (basic_block bb, gcov_type count, int frequency)
721
{
722
  edge e;
723
  bb->count -= count;
724
  if (bb->count < 0)
725
    bb->count = 0;
726
  bb->frequency -= frequency;
727
  if (bb->frequency < 0)
728
    bb->frequency = 0;
729
  if (!single_succ_p (bb))
730
    {
731
      gcc_assert (!EDGE_COUNT (bb->succs));
732
      return;
733
    }
734
  e = single_succ_edge (bb);
735
  e->count -= count;
736
  if (e->count < 0)
737
    e->count = 0;
738
}
739
 
740
/* Returns true if argument PARAM of the tail recursive call needs to be copied
741
   when the call is eliminated.  */
742
 
743
static bool
744
arg_needs_copy_p (tree param)
745
{
746
  tree def;
747
 
748
  if (!is_gimple_reg (param) || !var_ann (param))
749
    return false;
750
 
751
  /* Parameters that are only defined but never used need not be copied.  */
752
  def = gimple_default_def (cfun, param);
753
  if (!def)
754
    return false;
755
 
756
  return true;
757
}
758
 
759
/* Eliminates tail call described by T.  TMP_VARS is a list of
760
   temporary variables used to copy the function arguments.  */
761
 
762
static void
763
eliminate_tail_call (struct tailcall *t)
764
{
765
  tree param, rslt;
766
  gimple stmt, call;
767
  tree arg;
768
  size_t idx;
769
  basic_block bb, first;
770
  edge e;
771
  gimple phi;
772
  gimple_stmt_iterator gsi;
773
  gimple orig_stmt;
774
 
775
  stmt = orig_stmt = gsi_stmt (t->call_gsi);
776
  bb = gsi_bb (t->call_gsi);
777
 
778
  if (dump_file && (dump_flags & TDF_DETAILS))
779
    {
780
      fprintf (dump_file, "Eliminated tail recursion in bb %d : ",
781
               bb->index);
782
      print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
783
      fprintf (dump_file, "\n");
784
    }
785
 
786
  gcc_assert (is_gimple_call (stmt));
787
 
788
  first = single_succ (ENTRY_BLOCK_PTR);
789
 
790
  /* Remove the code after call_gsi that will become unreachable.  The
791
     possibly unreachable code in other blocks is removed later in
792
     cfg cleanup.  */
793
  gsi = t->call_gsi;
794
  gsi_next (&gsi);
795
  while (!gsi_end_p (gsi))
796
    {
797
      gimple t = gsi_stmt (gsi);
798
      /* Do not remove the return statement, so that redirect_edge_and_branch
799
         sees how the block ends.  */
800
      if (gimple_code (t) == GIMPLE_RETURN)
801
        break;
802
 
803
      gsi_remove (&gsi, true);
804
      release_defs (t);
805
    }
806
 
807
  /* Number of executions of function has reduced by the tailcall.  */
808
  e = single_succ_edge (gsi_bb (t->call_gsi));
809
  decrease_profile (EXIT_BLOCK_PTR, e->count, EDGE_FREQUENCY (e));
810
  decrease_profile (ENTRY_BLOCK_PTR, e->count, EDGE_FREQUENCY (e));
811
  if (e->dest != EXIT_BLOCK_PTR)
812
    decrease_profile (e->dest, e->count, EDGE_FREQUENCY (e));
813
 
814
  /* Replace the call by a jump to the start of function.  */
815
  e = redirect_edge_and_branch (single_succ_edge (gsi_bb (t->call_gsi)),
816
                                first);
817
  gcc_assert (e);
818
  PENDING_STMT (e) = NULL;
819
 
820
  /* Add phi node entries for arguments.  The ordering of the phi nodes should
821
     be the same as the ordering of the arguments.  */
822
  for (param = DECL_ARGUMENTS (current_function_decl),
823
         idx = 0, gsi = gsi_start_phis (first);
824
       param;
825
       param = TREE_CHAIN (param), idx++)
826
    {
827
      if (!arg_needs_copy_p (param))
828
        continue;
829
 
830
      arg = gimple_call_arg (stmt, idx);
831
      phi = gsi_stmt (gsi);
832
      gcc_assert (param == SSA_NAME_VAR (PHI_RESULT (phi)));
833
 
834
      add_phi_arg (phi, arg, e, gimple_location (stmt));
835
      gsi_next (&gsi);
836
    }
837
 
838
  /* Update the values of accumulators.  */
839
  adjust_accumulator_values (t->call_gsi, t->mult, t->add, e);
840
 
841
  call = gsi_stmt (t->call_gsi);
842
  rslt = gimple_call_lhs (call);
843
  if (rslt != NULL_TREE)
844
    {
845
      /* Result of the call will no longer be defined.  So adjust the
846
         SSA_NAME_DEF_STMT accordingly.  */
847
      SSA_NAME_DEF_STMT (rslt) = gimple_build_nop ();
848
    }
849
 
850
  gsi_remove (&t->call_gsi, true);
851
  release_defs (call);
852
}
853
 
854
/* Add phi nodes for the virtual operands defined in the function to the
855
   header of the loop created by tail recursion elimination.
856
 
857
   Originally, we used to add phi nodes only for call clobbered variables,
858
   as the value of the non-call clobbered ones obviously cannot be used
859
   or changed within the recursive call.  However, the local variables
860
   from multiple calls now share the same location, so the virtual ssa form
861
   requires us to say that the location dies on further iterations of the loop,
862
   which requires adding phi nodes.
863
*/
864
static void
865
add_virtual_phis (void)
866
{
867
  referenced_var_iterator rvi;
868
  tree var;
869
 
870
  /* The problematic part is that there is no way how to know what
871
     to put into phi nodes (there in fact does not have to be such
872
     ssa name available).  A solution would be to have an artificial
873
     use/kill for all virtual operands in EXIT node.  Unless we have
874
     this, we cannot do much better than to rebuild the ssa form for
875
     possibly affected virtual ssa names from scratch.  */
876
 
877
  FOR_EACH_REFERENCED_VAR (var, rvi)
878
    {
879
      if (!is_gimple_reg (var) && gimple_default_def (cfun, var) != NULL_TREE)
880
        mark_sym_for_renaming (var);
881
    }
882
}
883
 
884
/* Optimizes the tailcall described by T.  If OPT_TAILCALLS is true, also
885
   mark the tailcalls for the sibcall optimization.  */
886
 
887
static bool
888
optimize_tail_call (struct tailcall *t, bool opt_tailcalls)
889
{
890
  if (t->tail_recursion)
891
    {
892
      eliminate_tail_call (t);
893
      return true;
894
    }
895
 
896
  if (opt_tailcalls)
897
    {
898
      gimple stmt = gsi_stmt (t->call_gsi);
899
 
900
      gimple_call_set_tail (stmt, true);
901
      if (dump_file && (dump_flags & TDF_DETAILS))
902
        {
903
          fprintf (dump_file, "Found tail call ");
904
          print_gimple_stmt (dump_file, stmt, 0, dump_flags);
905
          fprintf (dump_file, " in bb %i\n", (gsi_bb (t->call_gsi))->index);
906
        }
907
    }
908
 
909
  return false;
910
}
911
 
912
/* Creates a tail-call accumulator of the same type as the return type of the
913
   current function.  LABEL is the name used to creating the temporary
914
   variable for the accumulator.  The accumulator will be inserted in the
915
   phis of a basic block BB with single predecessor with an initial value
916
   INIT converted to the current function return type.  */
917
 
918
static tree
919
create_tailcall_accumulator (const char *label, basic_block bb, tree init)
920
{
921
  tree ret_type = TREE_TYPE (DECL_RESULT (current_function_decl));
922
  tree tmp = create_tmp_var (ret_type, label);
923
  gimple phi;
924
 
925
  if (TREE_CODE (ret_type) == COMPLEX_TYPE
926
      || TREE_CODE (ret_type) == VECTOR_TYPE)
927
    DECL_GIMPLE_REG_P (tmp) = 1;
928
  add_referenced_var (tmp);
929
  phi = create_phi_node (tmp, bb);
930
  /* RET_TYPE can be a float when -ffast-maths is enabled.  */
931
  add_phi_arg (phi, fold_convert (ret_type, init), single_pred_edge (bb),
932
               UNKNOWN_LOCATION);
933
  return PHI_RESULT (phi);
934
}
935
 
936
/* Optimizes tail calls in the function, turning the tail recursion
937
   into iteration.  */
938
 
939
static unsigned int
940
tree_optimize_tail_calls_1 (bool opt_tailcalls)
941
{
942
  edge e;
943
  bool phis_constructed = false;
944
  struct tailcall *tailcalls = NULL, *act, *next;
945
  bool changed = false;
946
  basic_block first = single_succ (ENTRY_BLOCK_PTR);
947
  tree param;
948
  gimple stmt;
949
  edge_iterator ei;
950
 
951
  if (!suitable_for_tail_opt_p ())
952
    return 0;
953
  if (opt_tailcalls)
954
    opt_tailcalls = suitable_for_tail_call_opt_p ();
955
 
956
  FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
957
    {
958
      /* Only traverse the normal exits, i.e. those that end with return
959
         statement.  */
960
      stmt = last_stmt (e->src);
961
 
962
      if (stmt
963
          && gimple_code (stmt) == GIMPLE_RETURN)
964
        find_tail_calls (e->src, &tailcalls);
965
    }
966
 
967
  /* Construct the phi nodes and accumulators if necessary.  */
968
  a_acc = m_acc = NULL_TREE;
969
  for (act = tailcalls; act; act = act->next)
970
    {
971
      if (!act->tail_recursion)
972
        continue;
973
 
974
      if (!phis_constructed)
975
        {
976
          /* Ensure that there is only one predecessor of the block
977
             or if there are existing degenerate PHI nodes.  */
978
          if (!single_pred_p (first)
979
              || !gimple_seq_empty_p (phi_nodes (first)))
980
            first = split_edge (single_succ_edge (ENTRY_BLOCK_PTR));
981
 
982
          /* Copy the args if needed.  */
983
          for (param = DECL_ARGUMENTS (current_function_decl);
984
               param;
985
               param = TREE_CHAIN (param))
986
            if (arg_needs_copy_p (param))
987
              {
988
                tree name = gimple_default_def (cfun, param);
989
                tree new_name = make_ssa_name (param, SSA_NAME_DEF_STMT (name));
990
                gimple phi;
991
 
992
                set_default_def (param, new_name);
993
                phi = create_phi_node (name, first);
994
                SSA_NAME_DEF_STMT (name) = phi;
995
                add_phi_arg (phi, new_name, single_pred_edge (first),
996
                             EXPR_LOCATION (param));
997
              }
998
          phis_constructed = true;
999
        }
1000
 
1001
      if (act->add && !a_acc)
1002
        a_acc = create_tailcall_accumulator ("add_acc", first,
1003
                                             integer_zero_node);
1004
 
1005
      if (act->mult && !m_acc)
1006
        m_acc = create_tailcall_accumulator ("mult_acc", first,
1007
                                             integer_one_node);
1008
    }
1009
 
1010
  for (; tailcalls; tailcalls = next)
1011
    {
1012
      next = tailcalls->next;
1013
      changed |= optimize_tail_call (tailcalls, opt_tailcalls);
1014
      free (tailcalls);
1015
    }
1016
 
1017
  if (a_acc || m_acc)
1018
    {
1019
      /* Modify the remaining return statements.  */
1020
      FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
1021
        {
1022
          stmt = last_stmt (e->src);
1023
 
1024
          if (stmt
1025
              && gimple_code (stmt) == GIMPLE_RETURN)
1026
            adjust_return_value (e->src, m_acc, a_acc);
1027
        }
1028
    }
1029
 
1030
  if (changed)
1031
    free_dominance_info (CDI_DOMINATORS);
1032
 
1033
  if (phis_constructed)
1034
    add_virtual_phis ();
1035
  if (changed)
1036
    return TODO_cleanup_cfg | TODO_update_ssa_only_virtuals;
1037
  return 0;
1038
}
1039
 
1040
static unsigned int
1041
execute_tail_recursion (void)
1042
{
1043
  return tree_optimize_tail_calls_1 (false);
1044
}
1045
 
1046
static bool
1047
gate_tail_calls (void)
1048
{
1049
  return flag_optimize_sibling_calls != 0 && dbg_cnt (tail_call);
1050
}
1051
 
1052
static unsigned int
1053
execute_tail_calls (void)
1054
{
1055
  return tree_optimize_tail_calls_1 (true);
1056
}
1057
 
1058
struct gimple_opt_pass pass_tail_recursion =
1059
{
1060
 {
1061
  GIMPLE_PASS,
1062
  "tailr",                              /* name */
1063
  gate_tail_calls,                      /* gate */
1064
  execute_tail_recursion,               /* execute */
1065
  NULL,                                 /* sub */
1066
  NULL,                                 /* next */
1067
  0,                                     /* static_pass_number */
1068
  TV_NONE,                              /* tv_id */
1069
  PROP_cfg | PROP_ssa,                  /* properties_required */
1070
  0,                                     /* properties_provided */
1071
  0,                                     /* properties_destroyed */
1072
  0,                                     /* todo_flags_start */
1073
  TODO_dump_func | TODO_verify_ssa      /* todo_flags_finish */
1074
 }
1075
};
1076
 
1077
struct gimple_opt_pass pass_tail_calls =
1078
{
1079
 {
1080
  GIMPLE_PASS,
1081
  "tailc",                              /* name */
1082
  gate_tail_calls,                      /* gate */
1083
  execute_tail_calls,                   /* execute */
1084
  NULL,                                 /* sub */
1085
  NULL,                                 /* next */
1086
  0,                                     /* static_pass_number */
1087
  TV_NONE,                              /* tv_id */
1088
  PROP_cfg | PROP_ssa,                  /* properties_required */
1089
  0,                                     /* properties_provided */
1090
  0,                                     /* properties_destroyed */
1091
  0,                                     /* todo_flags_start */
1092
  TODO_dump_func | TODO_verify_ssa      /* todo_flags_finish */
1093
 }
1094
};

powered by: WebSVN 2.1.0

© copyright 1999-2024 OpenCores.org, equivalent to Oliscience, all rights reserved. OpenCores®, registered trademark.