home *** CD-ROM | disk | FTP | other *** search
/ ftp.cs.arizona.edu / ftp.cs.arizona.edu.tar / ftp.cs.arizona.edu / icon / historic / v92.tgz / v92.tar / v92 / src / iconc / lifetime.c < prev    next >
C/C++ Source or Header  |  1996-03-22  |  14KB  |  497 lines
  1. /*
  2.  * lifetime.c - perform liveness analysis to determine lifetime of intermediate
  3.  *    results.
  4.  */
  5. #include "::h:gsupport.h"
  6. #include "::h:lexdef.h"
  7. #include "ctrans.h"
  8. #include "cglobals.h"
  9. #include "ctree.h"
  10. #include "ctoken.h"
  11. #include "csym.h"
  12. #include "ccode.h"
  13. #include "cproto.h"
  14.  
  15. /*
  16.  * Prototypes for static functions.
  17.  */
  18. hidden novalue arg_life Params((nodeptr n, long min_result, long max_result,
  19.                           int resume, int frst_arg, int nargs, nodeptr resumer,
  20.                           nodeptr *failer, int *gen));
  21.  
  22. static int postn = -1; /* relative position in execution order (all neg) */
  23.  
  24. /*
  25.  * liveness - compute lifetimes of intermediate results.
  26.  */
  27. novalue liveness(n, resumer, failer, gen)
  28. nodeptr n;
  29. nodeptr resumer;
  30. nodeptr *failer;
  31. int *gen;
  32.    {
  33.    struct loop {
  34.       nodeptr resumer;
  35.       int gen;
  36.       nodeptr lifetime;
  37.       int every_cntrl;
  38.       struct loop *prev;
  39.       } loop_info;
  40.    struct loop *loop_sav;
  41.    static struct loop *cur_loop = NULL;
  42.    nodeptr failer1;
  43.    nodeptr failer2;
  44.    int gen1 = 0;
  45.    int gen2 = 0;
  46.    struct node *cases;
  47.    struct node *clause;
  48.    long min_result;  /* minimum result sequence length */
  49.    long max_result;  /* maximum result sequence length */
  50.    int resume;         /* flag - resumption possible after last result */
  51.  
  52.    n->postn = postn--;
  53.  
  54.    switch (n->n_type) {
  55.       case N_Activat:
  56.          /*
  57.           * Activation can fail or succeed.
  58.            */
  59.          arg_life(n, 0L, 1L, 0, 1, 2, resumer, failer, gen);
  60.          break;
  61.  
  62.       case N_Alt:
  63.          Tree1(n)->lifetime = n->lifetime;
  64.          Tree0(n)->lifetime = n->lifetime;
  65.          liveness(Tree1(n), resumer, &failer2, &gen2);
  66.          liveness(Tree0(n), resumer, &failer1, &gen1);
  67.          *failer = failer2;
  68.          *gen = 1;
  69.          break;
  70.  
  71.       case N_Apply:
  72.          /* 
  73.           * Assume operation can suspend or fail.
  74.           */
  75.          arg_life(n, 0L, UnbndSeq, 1, 0, 2, resumer, failer, gen);
  76.          break;
  77.  
  78.       case N_Augop:
  79.          /*
  80.           * Impl0(n) is assignment. Impl1(n) is the augmented operation.
  81.           */
  82.          min_result = Impl0(n)->min_result * Impl1(n)->min_result;
  83.          max_result = Impl0(n)->max_result * Impl1(n)->max_result;
  84.          resume = Impl0(n)->resume | Impl1(n)->resume;
  85.          arg_life(n, min_result, max_result, resume, 2, 2, resumer, failer,
  86.             gen);
  87.          break;
  88.  
  89.       case N_Bar:
  90.          if (resumer == NULL)
  91.             n->intrnl_lftm = n;
  92.          else
  93.             n->intrnl_lftm = resumer;
  94.          Tree0(n)->lifetime = n->lifetime;
  95.          liveness(Tree0(n), resumer, failer, &gen1);
  96.          *gen = 1;
  97.          break;
  98.  
  99.       case N_Break:
  100.          if (cur_loop == NULL) {
  101.             nfatal(n, "invalid context for break", NULL);
  102.             return;
  103.             }
  104.          Tree0(n)->lifetime = cur_loop->lifetime;
  105.          loop_sav = cur_loop;
  106.          cur_loop = cur_loop->prev;
  107.          liveness(Tree0(n), loop_sav->resumer, &failer1, &gen1);
  108.          cur_loop = loop_sav;
  109.          cur_loop->gen |= gen1;
  110.          *failer = NULL;
  111.          *gen = 0;
  112.          break;
  113.  
  114.       case N_Case:
  115.          *failer = resumer;
  116.          *gen = 0;
  117.  
  118.          cases = Tree1(n);
  119.          while (cases != NULL) {
  120.             if (cases->n_type == N_Ccls) {
  121.                clause = cases;
  122.                cases = NULL;
  123.                }
  124.             else {
  125.                clause = Tree1(cases);
  126.                cases = Tree0(cases);
  127.                }
  128.  
  129.             /*
  130.              *  Body.
  131.              */
  132.             Tree1(clause)->lifetime = n->lifetime;
  133.             liveness(Tree1(clause), resumer, &failer2, &gen2);
  134.             if (resumer == NULL && failer2 != NULL)
  135.                *failer = n;
  136.             *gen |= gen2;
  137.       
  138.             /*
  139.              * The expression being compared can be resumed.
  140.              */
  141.             Tree0(clause)->lifetime = clause;
  142.             liveness(Tree0(clause), clause, &failer1, &gen1);
  143.             }
  144.  
  145.          if (Tree2(n) == NULL) {
  146.             if (resumer == NULL)
  147.                *failer = n;
  148.             }
  149.          else {
  150.             Tree2(n)->lifetime = n->lifetime;
  151.             liveness(Tree2(n), resumer, &failer2, &gen2);  /* default */
  152.             if (resumer == NULL && failer2 != NULL)
  153.                *failer = n;
  154.             *gen |= gen2;
  155.             }
  156.  
  157.          /*
  158.           * control clause is bounded
  159.           */
  160.          Tree0(n)->lifetime = n;
  161.          liveness(Tree0(n), NULL, &failer1, &gen1);
  162.          if (failer1 != NULL && *failer == NULL)
  163.             *failer = failer1;
  164.          break;
  165.  
  166.       case N_Create:
  167.          Tree0(n)->lifetime = n;
  168.          loop_sav = cur_loop;
  169.          cur_loop = NULL;        /* check for invalid break and next */
  170.          liveness(Tree0(n), n, &failer1, &gen1);
  171.          cur_loop = loop_sav;
  172.          *failer = NULL;
  173.          *gen = 0;
  174.          break;
  175.  
  176.       case N_Cset:
  177.       case N_Empty:
  178.       case N_Id: 
  179.       case N_Int:
  180.       case N_Real:
  181.       case N_Str:
  182.          *failer = resumer;
  183.          *gen = 0;
  184.          break;
  185.  
  186.       case N_Field:
  187.          Tree0(n)->lifetime = n;
  188.          liveness(Tree0(n), resumer, failer, gen);
  189.          break;
  190.  
  191.       case N_If:
  192.          Tree1(n)->lifetime = n->lifetime;
  193.          liveness(Tree1(n), resumer, failer, gen);
  194.          if (Tree2(n)->n_type != N_Empty) {
  195.             Tree2(n)->lifetime = n->lifetime;
  196.             liveness(Tree2(n), resumer, &failer2, &gen2);
  197.             if (failer2 != NULL) {
  198.                if (*failer == NULL)
  199.                   *failer = failer2;
  200.                else {
  201.                  if ((*failer)->postn < failer2->postn)
  202.                    *failer = failer2;
  203.                  if ((*failer)->postn < n->postn)
  204.                    *failer = n;
  205.                  }
  206.                }
  207.             *gen |= gen2;
  208.             }
  209.          /*
  210.           * control clause is bounded
  211.           */
  212.          Tree0(n)->lifetime = NULL;
  213.          liveness(Tree0(n), NULL, &failer1, &gen1);
  214.          if (Tree2(n)->n_type == N_Empty && failer1 != NULL && *failer == NULL)
  215.             *failer = failer1;
  216.          break;
  217.  
  218.       case N_Invok:
  219.          /*
  220.           * Assume operation can suspend and fail.
  221.           */
  222.          arg_life(n, 0L, UnbndSeq, 1, 1, Val0(n) + 1, resumer, failer, gen);
  223.          break;
  224.  
  225.       case N_InvOp:
  226.          arg_life(n, Impl1(n)->min_result, Impl1(n)->max_result,
  227.             Impl1(n)->resume, 2, Val0(n), resumer, failer, gen);
  228.          break;
  229.  
  230.       case N_InvProc:
  231.          if (Proc1(n)->ret_flag & DoesFail)
  232.              min_result = 0L;
  233.          else
  234.              min_result = 1L;
  235.          if (Proc1(n)->ret_flag & DoesSusp) {
  236.              max_result = UnbndSeq;
  237.              resume = 1;
  238.              }
  239.          else {
  240.              max_result = 1L;
  241.              resume = 0;
  242.              }
  243.          arg_life(n, min_result, max_result, resume, 2, Val0(n), resumer,
  244.             failer, gen);
  245.          break;
  246.  
  247.       case N_InvRec:
  248.          arg_life(n, err_conv ? 0L : 1L, 1L, 1, 2, Val0(n), resumer, failer,
  249.             gen);
  250.          break;
  251.  
  252.       case N_Limit:
  253.          if (resumer == NULL)
  254.             n->intrnl_lftm = n;
  255.          else
  256.             n->intrnl_lftm = resumer;
  257.          Tree0(n)->lifetime = n->lifetime;
  258.          liveness(Tree0(n), resumer, &failer1, &gen1);
  259.          Tree1(n)->lifetime = n;
  260.          liveness(Tree1(n), failer1 == NULL ? n : failer1, &failer2, &gen2);
  261.          *failer = failer2;
  262.          *gen = gen1 | gen2;
  263.          break;
  264.  
  265.       case N_Loop: {
  266.          loop_info.prev = cur_loop;
  267.          loop_info.resumer = resumer;
  268.          loop_info.gen = 0;
  269.          loop_info.every_cntrl = 0;
  270.          loop_info.lifetime = n->lifetime;
  271.          cur_loop = &loop_info;
  272.          switch ((int)Val0(Tree0(n))) {
  273.             case EVERY:
  274.                /*
  275.                 * The body is bounded. The control clause is resumed
  276.                 *  by the control structure.
  277.                 */
  278.                Tree2(n)->lifetime = NULL;
  279.                liveness(Tree2(n), NULL, &failer2, &gen2);
  280.                loop_info.every_cntrl = 1;
  281.                Tree1(n)->lifetime = NULL;
  282.                liveness(Tree1(n), n, &failer1, &gen1);
  283.                break;
  284.  
  285.             case REPEAT:
  286.                /*
  287.                 * The body is bounded.
  288.                 */
  289.                Tree1(n)->lifetime = NULL;
  290.                liveness(Tree1(n), NULL, &failer1, &gen1);
  291.                break;
  292.  
  293.             case SUSPEND:
  294.                /*
  295.                 * The body is bounded. The control clause is resumed
  296.                 *  by the control structure.
  297.                 */
  298.                Tree2(n)->lifetime = NULL;
  299.                liveness(Tree2(n), NULL, &failer2, &gen2);
  300.                loop_info.every_cntrl = 1;
  301.                Tree1(n)->lifetime = n;
  302.                liveness(Tree1(n), n, &failer1, &gen1);
  303.                break;
  304.  
  305.             case WHILE:
  306.             case UNTIL:
  307.                /*
  308.                 * The body and the control clause are each bounded.
  309.                 */
  310.                Tree2(n)->lifetime = NULL;
  311.                liveness(Tree2(n), NULL, &failer1, &gen1);
  312.                Tree1(n)->lifetime = NULL;
  313.                liveness(Tree1(n), NULL, &failer1, &gen1);
  314.                break;
  315.             }
  316.          *failer = (resumer == NULL ? n : resumer); /* assume a loop can fail */
  317.          *gen = cur_loop->gen;
  318.          cur_loop = cur_loop->prev;
  319.          }
  320.          break;
  321.  
  322.       case N_Next:
  323.          if (cur_loop == NULL) {
  324.             nfatal(n, "invalid context for next", NULL);
  325.             return;
  326.             }
  327.          if (cur_loop->every_cntrl)
  328.              *failer = n;
  329.          else
  330.              *failer = NULL;
  331.          *gen = 0;
  332.          break;
  333.  
  334.       case N_Not:
  335.          /*
  336.           * The expression is bounded.
  337.           */
  338.          Tree0(n)->lifetime = NULL;
  339.          liveness(Tree0(n), NULL, &failer1, &gen1);
  340.          *failer = (resumer == NULL ? n : resumer);
  341.          *gen = 0;
  342.          break;
  343.  
  344.       case N_Ret:
  345.          if (Val0(Tree0(n)) == RETURN)  {
  346.             /*
  347.              * The expression is bounded.
  348.              */
  349.             Tree1(n)->lifetime = n;
  350.             liveness(Tree1(n), NULL, &failer1, &gen1);
  351.             }
  352.          *failer = NULL;
  353.          *gen = 0;
  354.          break;
  355.  
  356.       case N_Scan: {
  357.          struct implement *asgn_impl;
  358.  
  359.          if (resumer == NULL)
  360.             n->intrnl_lftm = n;
  361.          else
  362.             n->intrnl_lftm = resumer;
  363.  
  364.          if (optab[Val0(Tree0(n))].tok.t_type == AUGQMARK) {
  365.             asgn_impl = optab[asgn_loc].binary;
  366.             arg_life(n, asgn_impl->min_result, asgn_impl->max_result,
  367.                asgn_impl->resume, 1, 2, resumer, failer, gen);
  368.             }
  369.          else {
  370.             Tree2(n)->lifetime = n->lifetime;
  371.             liveness(Tree2(n), resumer, &failer2, &gen2);  /* body */
  372.             Tree1(n)->lifetime = n;
  373.             liveness(Tree1(n), failer2, &failer1, &gen1);  /* subject */ 
  374.             *failer = failer1;
  375.             *gen = gen1 | gen2;
  376.             }
  377.          }
  378.          break;
  379.  
  380.       case N_Sect:
  381.          /*
  382.           * Impl0(n) is sectioning.
  383.           */
  384.          min_result = Impl0(n)->min_result;
  385.          max_result = Impl0(n)->max_result;
  386.          resume = Impl0(n)->resume;
  387.          if (Impl1(n) != NULL) {
  388.             /*
  389.              * Impl1(n) is plus or minus.
  390.              */
  391.             min_result *= Impl1(n)->min_result;
  392.             max_result *= Impl1(n)->max_result;
  393.             resume |= Impl1(n)->resume;
  394.             }
  395.          arg_life(n, min_result, max_result, resume, 2, 3, resumer, failer,
  396.             gen);
  397.          break;
  398.  
  399.       case N_Slist:
  400.          /*
  401.           * expr1 is not bounded, expr0 is bounded.
  402.           */
  403.          Tree1(n)->lifetime = n->lifetime;
  404.          liveness(Tree1(n), resumer, failer, gen);
  405.          Tree0(n)->lifetime = NULL;
  406.          liveness(Tree0(n), NULL, &failer1, &gen1);
  407.          break;
  408.  
  409.       case N_SmplAsgn:
  410.          Tree3(n)->lifetime = n;
  411.          liveness(Tree3(n), resumer, failer, gen);     /* 2nd operand */
  412.          Tree2(n)->lifetime = n->lifetime;             /* may be result of := */
  413.          liveness(Tree2(n), *failer, &failer1, &gen1); /* 1st operand */
  414.          break;
  415.  
  416.       case N_SmplAug:
  417.          /*
  418.           * Impl1(n) is the augmented operation.
  419.           */
  420.          arg_life(n, Impl1(n)->min_result, Impl1(n)->max_result,
  421.             Impl1(n)->resume, 2, 2, resumer, failer, gen);
  422.          break;
  423.  
  424.       default:
  425.          fprintf(stderr, "compiler error: node type %d unknown\n", n->n_type);
  426.          exit(ErrorExit);
  427.       }
  428.    }
  429.  
  430. /*
  431.  * arg_life - compute the lifetimes of an argument list.
  432.  */
  433. static novalue arg_life(n, min_result, max_result, resume, frst_arg, nargs,
  434.    resumer, failer, gen)
  435. nodeptr n;
  436. long min_result;  /* minimum result sequence length */
  437. long max_result;  /* maximum result sequence length */
  438. int resume;      /* flag - resumption possible after last result */
  439. int frst_arg;
  440. int nargs;
  441. nodeptr resumer;
  442. nodeptr *failer;
  443. int *gen;
  444.    {
  445.    nodeptr failer1;
  446.    nodeptr failer2;
  447.    nodeptr lifetime;
  448.    int inv_fail;    /* failure after operation in invoked */
  449.    int reuse;
  450.    int gen2;
  451.    int i;
  452.  
  453.    /*
  454.     * Determine what, if anything, can resume the rightmost argument.
  455.     */
  456.    if (resumer == NULL && min_result == 0)
  457.       failer1 = n;
  458.    else
  459.       failer1 = resumer;
  460.    if (failer1 == NULL)
  461.       inv_fail = 0;
  462.    else
  463.       inv_fail = 1;
  464.  
  465.    /*
  466.     * If the operation can be resumed, variables internal to the operation
  467.     *  have and extended lifetime.
  468.     */
  469.    if (resumer != NULL && (max_result > 1 || max_result == UnbndSeq || resume))
  470.       n->intrnl_lftm = resumer;
  471.    else
  472.       n->intrnl_lftm = n;
  473.  
  474.    /*
  475.     * Go through the parameter list right to left, propagating resumption
  476.     *  information, computing lifetimes, and determining whether anything
  477.     *  can generate.
  478.     */
  479.    lifetime = n;
  480.    reuse = 0;
  481.    *gen = 0;
  482.    for (i = frst_arg + nargs - 1; i >= frst_arg; --i) {
  483.       n->n_field[i].n_ptr->lifetime = lifetime;
  484.       n->n_field[i].n_ptr->reuse = reuse;
  485.       liveness(n->n_field[i].n_ptr, failer1, &failer2, &gen2);
  486.       if (resumer != NULL && gen2)
  487.          lifetime = resumer;
  488.       if (inv_fail && gen2)
  489.          reuse = 1;
  490.       failer1 = failer2;
  491.       *gen |= gen2;
  492.       }
  493.    *failer = failer1;
  494.    if (max_result > 1 || max_result == UnbndSeq)
  495.       *gen = 1;
  496.    }
  497.