util/ego/cf/cf_succ.c

   1 /* $Id: cf_succ.c,v 1.6 1994/06/24 10:20:29 ceriel Exp $ */
   2 /*
   3  * (c) copyright 1987 by the Vrije Universiteit, Amsterdam, The Netherlands.
   4  * See the copyright notice in the ACK home directory, in the file "Copyright".
   5  */
   6 /*  C O N T R O L   F L O W
   7  *
   8  *  C F _ S U C C . C
   9  */
  10
  11
  12 #include <stdio.h>
  13 #include <em_spec.h>
  14 #include <em_pseu.h>
  15 #include <em_flag.h>
  16 #include <em_mnem.h>
  17 #include "../share/types.h"
  18 #include "../share/def.h"
  19 #include "../share/debug.h"
  20 #include "../share/global.h"
  21 #include "../share/lset.h"
  22 #include "../share/cset.h"
  23 #include "cf.h"
  24 #include "../share/map.h"
  25
  26 extern char em_flag[];
  27
  28
  29 STATIC succeeds(succ,pred)
  30         bblock_p succ, pred;
  31 {
  32         assert(pred != (bblock_p) 0);
  33         if (succ != (bblock_p) 0) {
  34                 Ladd(succ, &pred->b_succ);
  35                 Ladd(pred, &succ->b_pred);
  36         }
  37 }
  38
  39
  40 #define IS_RETURN(i)    (i == op_ret || i == op_rtt)
  41 #define IS_CASE_JUMP(i) (i == op_csa || i == op_csb)
  42 #define IS_UNCOND_JUMP(i) (i <= sp_lmnem && (em_flag[i-sp_fmnem] & EM_FLO) == FLO_T)
  43 #define IS_COND_JUMP(i) (i <= sp_lmnem && (em_flag[i-sp_fmnem] & EM_FLO) == FLO_C)
  44 #define TARGET(lnp)     (lbmap[INSTRLAB(lnp)])
  45 #define ATARGET(arg)    (lbmap[arg->a_a.a_instrlab])
  46
  47
  48
  49 STATIC arg_p skip_const(arg)
  50         arg_p arg;
  51 {
  52         assert(arg != (arg_p) 0);
  53         switch(arg->a_type) {
  54                 case ARGOFF:
  55                 case ARGICN:
  56                 case ARGUCN:
  57                         break;
  58                 default:
  59                         error("bad case descriptor");
  60         }
  61         return arg->a_next;
  62 }
  63
  64
  65 STATIC arg_p use_label(arg,b)
  66         arg_p arg;
  67         bblock_p b;
  68 {
  69         if (arg->a_type == ARGINSTRLAB) {
  70                 /* arg is a non-null label */
  71                 succeeds(ATARGET(arg),b);
  72         }
  73         return arg->a_next;
  74 }
  75
  76
  77
  78 STATIC case_flow(instr,desc,b)
  79         short    instr;
  80         line_p   desc;
  81         bblock_p b;
  82 {
  83         /* Analyse the case descriptor (given as a ROM pseudo instruction).
  84          * Every instruction label appearing in the descriptor
  85          * heads a basic block that is a successor of the block
  86          * in which the case instruction appears (b).
  87          */
  88
  89         register arg_p arg;
  90
  91         assert(instr == op_csa || instr == op_csb);
  92         assert(TYPE(desc) == OPLIST);
  93         arg = ARG(desc);
  94         arg = use_label(arg,b);
  95         /* See if there is a default label. If so, then
  96          * its block is a successor of b. Set arg to
  97          * next argument.
  98          */
  99         if (instr == op_csa) {
 100                 arg = skip_const(arg); /* skip lower bound */
 101                 arg = skip_const(arg); /* skip lower-upper bound */
 102                 while (arg != (arg_p) 0) {
 103                         /* All following arguments are case labels
 104                          * or zeroes.
 105                          */
 106                         arg = use_label(arg,b);
 107                 }
 108         } else {
 109                 /* csb instruction */
 110                 arg = skip_const(arg);  /* skip #entries */
 111                 while (arg != (arg_p) 0) {
 112                         /* All following arguments are alternatively
 113                          * an index and an instruction label (possibly 0).
 114                          */
 115                         arg = skip_const(arg);  /* skip index */
 116                         arg = use_label(arg,b);
 117                 }
 118         }
 119 }
 120
 121
 122
 123 STATIC line_p case_descr(lnp)
 124         line_p lnp;
 125 {
 126         /* lnp is the instruction just before a csa or csb,
 127          * so it is the instruction that pushes the address
 128          * of a case descriptor on the stack. Find that
 129          * descriptor, i.e. a rom pseudo instruction.
 130          * Note that this instruction will always be part
 131          * of the procedure in which the csa/csb occurs.
 132          */
 133
 134         register line_p l;
 135         dblock_p d;
 136         obj_p    obj;
 137         dblock_id id;
 138
 139         if (lnp == (line_p) 0 || (INSTR(lnp)) != op_lae) {
 140                 error("cannot find 'lae descr' before csa/csb");
 141         }
 142         /* We'll first find the ROM and its dblock_id */
 143         obj = OBJ(lnp);
 144         if (obj->o_off != (offset) 0) {
 145                 error("bad 'lae descr' before csa/csb");
 146                 /* We require a descriptor to be an entire rom,
 147                  * not part of a rom.
 148                  */
 149         }
 150         d = obj->o_dblock;
 151         assert(d != (dblock_p) 0);
 152         if (d->d_pseudo != DROM) {
 153                 error("case descriptor must be in rom");
 154         }
 155         id = d->d_id;
 156         /* We'll use the dblock_id to find the defining occurrence
 157          * of the rom in the EM text (i.e. a rom pseudo). As all
 158          * pseudos appear at the beginning of a procedure, we only
 159          * have to look in its first basic block.
 160          */
 161         assert(curproc != (proc_p) 0);
 162         assert(curproc->p_start != (bblock_p) 0);
 163         l = curproc->p_start->b_start; /* first instruction of curproc */
 164         while (l != (line_p) 0) {
 165                 if ((INSTR(l)) == ps_sym &&
 166                     SHORT(l) == id) {
 167                         /* found! */
 168                         assert((INSTR(l->l_next)) == ps_rom);
 169                         return l->l_next;
 170                 }
 171                 l = l->l_next;
 172         }
 173         error("cannot find rom pseudo for case descriptor");
 174         /* NOTREACHED */
 175 }
 176
 177
 178
 179 STATIC last2_instrs(b,last_out,prev_out)
 180         bblock_p b;
 181         line_p   *last_out,*prev_out;
 182 {
 183         /* Determine the last and one-but-last instruction
 184          * of basic block b. An end-pseudo is not regarded
 185          * as an instruction. If the block contains only 1
 186          * instruction, prev_out is 0.
 187          */
 188
 189         register line_p l1,l2;
 190
 191         l2 = b->b_start;  /* first instruction of b */
 192         assert(l2 != (line_p) 0); /* block can not be empty */
 193         if ((l1 = l2->l_next) == (line_p) 0 || INSTR(l1) == ps_end) {
 194                 *last_out = l2; /* single instruction */
 195                 *prev_out = (line_p) 0;
 196         } else {
 197                 while(l1->l_next != (line_p) 0 && INSTR(l1->l_next) != ps_end) {
 198                         l2 = l1;
 199                         l1 = l1->l_next;
 200                 }
 201                 *last_out = l1;
 202                 *prev_out = l2;
 203         }
 204 }
 205
 206
 207
 208 control_flow(head)
 209         bblock_p head;
 210 {
 211         /* compute the successor and predecessor relation
 212          * for every basic block.
 213          */
 214
 215         register bblock_p b;
 216         line_p lnp, prev;
 217         short instr;
 218
 219         for (b = head; b != (bblock_p) 0; b = b->b_next) {
 220                 /* for every basic block, in textual order, do */
 221                 last2_instrs(b, &lnp, &prev);
 222                 /* find last and one-but-last instruction */
 223                 instr = INSTR(lnp);
 224                 /* The last instruction of the basic block
 225                  * determines the set of successors of the block.
 226                  */
 227                 if (IS_CASE_JUMP(instr)) {
 228                         case_flow(instr,case_descr(prev),b);
 229                         /* If lnp is a csa or csb, then the instruction
 230                          * just before it (i.e. prev) must be the
 231                          * instruction that pushes the address of the
 232                          * case descriptor. This descriptor is found
 233                          * and analysed in order to build the successor
 234                          * and predecessor sets of b.
 235                          */
 236                 } else {
 237                    if (!IS_RETURN(instr)) {
 238                         if (IS_UNCOND_JUMP(instr)) {
 239                                 if (instr != op_gto) {
 240                                         succeeds(TARGET(lnp),b);
 241                                 }
 242                         } else {
 243                                 if (IS_COND_JUMP(instr)) {
 244                                         succeeds(TARGET(lnp),b);
 245                                         succeeds(b->b_next, b);
 246                                         /* Textually next block is
 247                                          * a successor of b.
 248                                          */
 249                                 } else {
 250                                         /* normal instruction */
 251                                         succeeds(b->b_next, b);
 252                                 }
 253                         }
 254                    }
 255                 }
 256         }
 257 }