linearize.c

   1 /*
   2  * Linearize - walk the statement tree (but _not_ the expressions)
   3  * to generate a linear version of it and the basic blocks.
   4  *
   5  * NOTE! We're not interested in the actual sub-expressions yet,
   6  * even though they can generate conditional branches and
   7  * subroutine calls. That's all "local" behaviour.
   8  *
   9  * Copyright (C) 2004 Linus Torvalds
  10  */
  11
  12 #include <string.h>
  13 #include <stdarg.h>
  14 #include <stdlib.h>
  15 #include <stdio.h>
  16
  17 #include "parse.h"
  18 #include "expression.h"
  19 #include "linearize.h"
  20
  21 static struct entrypoint *alloc_entrypoint(void)
  22 {
  23         return __alloc_entrypoint(0);
  24 }
  25
  26 static struct basic_block *alloc_basic_block(void)
  27 {
  28         return __alloc_basic_block(0);
  29 }
  30
  31 static void show_bb(struct basic_block *bb)
  32 {
  33         struct statement *stmt;
  34
  35         printf("bb: %p%s\n", bb, bb->this ? "" : " UNREACHABLE!!");
  36         FOR_EACH_PTR(bb->stmts, stmt) {
  37                 show_statement(stmt);
  38         } END_FOR_EACH_PTR;
  39
  40         if (bb->next) {
  41                 printf("\tgoto\t\t.L%p\n", bb->next->bb_target);
  42         } else {
  43                 printf("\tEND\n");
  44         }
  45         printf("\n");
  46 }
  47
  48 static void show_entry(struct entrypoint *ep)
  49 {
  50         struct symbol *sym;
  51         struct basic_block *bb;
  52
  53         printf("ep %p: %s\n", ep, show_ident(ep->name->ident));
  54
  55         FOR_EACH_PTR(ep->syms, sym) {
  56                 printf("   sym: %p %s\n", sym, show_ident(sym->ident));
  57         } END_FOR_EACH_PTR;
  58
  59         printf("\n");
  60
  61         FOR_EACH_PTR(ep->bbs, bb) {
  62                 show_bb(bb);
  63         } END_FOR_EACH_PTR;
  64
  65         printf("\n");
  66 }
  67
  68 #define bb_reachable(bb) ((bb)->this != NULL)
  69
  70 static struct basic_block * new_basic_block(struct entrypoint *ep, struct symbol *owner)
  71 {
  72         struct basic_block *bb;
  73
  74         if (!owner) {
  75                 static struct basic_block unreachable;
  76                 return &unreachable;
  77         }
  78
  79         bb = alloc_basic_block();
  80         add_bb(&ep->bbs, bb);
  81         bb->this = owner;
  82         if (owner->bb_target)
  83                 warn(owner->pos, "Symbol already has a basic block %p", owner->bb_target);
  84         owner->bb_target = bb;
  85         return bb;
  86 }
  87
  88 static struct basic_block * linearize_statement(struct entrypoint *ep,
  89         struct basic_block *bb,
  90         struct statement *stmt)
  91 {
  92         if (!stmt)
  93                 return bb;
  94
  95         switch (stmt->type) {
  96         case STMT_NONE:
  97                 break;
  98
  99         case STMT_ASM:
 100         case STMT_EXPRESSION:
 101                 add_statement(&bb->stmts, stmt);
 102                 break;
 103
 104         case STMT_RETURN:
 105                 add_statement(&bb->stmts, stmt);
 106                 bb = new_basic_block(ep, NULL);
 107                 break;
 108
 109         case STMT_CASE: {
 110                 struct symbol *sym = stmt->case_label;
 111                 struct basic_block *new_bb = new_basic_block(ep, sym);
 112
 113                 bb->next = sym;
 114                 bb = linearize_statement(ep, new_bb, stmt->case_statement);
 115                 break;
 116         }
 117
 118         case STMT_LABEL: {
 119                 struct symbol *sym = stmt->label_identifier;
 120                 struct basic_block *new_bb = new_basic_block(ep, sym);
 121
 122                 bb->next = sym;
 123
 124                 bb = linearize_statement(ep, new_bb, stmt->label_statement);
 125                 break;
 126         }
 127
 128         case STMT_GOTO: {
 129                 struct basic_block *new_bb = new_basic_block(ep, NULL);
 130                 struct symbol *sym = stmt->goto_label;
 131
 132                 bb->next = sym;
 133                 bb = new_bb;
 134                 break;
 135         }
 136
 137         case STMT_COMPOUND: {
 138                 struct statement *s;
 139                 concat_symbol_list(stmt->syms, &ep->syms);
 140                 FOR_EACH_PTR(stmt->stmts, s) {
 141                         bb = linearize_statement(ep, bb, s);
 142                 } END_FOR_EACH_PTR;
 143                 break;
 144         }
 145
 146         /*
 147          * This could take 'likely/unlikely' into account, and
 148          * switch the arms around appropriately..
 149          */
 150         case STMT_IF: {
 151                 struct symbol *target;
 152                 struct statement *goto_bb;
 153                 struct basic_block *last_bb;
 154                 struct expression *cond = stmt->if_conditional;
 155
 156                 if (cond->type == EXPR_VALUE) {
 157                         struct statement *always = stmt->if_true;
 158                         struct statement *never = stmt->if_false;
 159                         if (!cond->value) {
 160                                 never = always;
 161                                 always = stmt->if_false;
 162                         }
 163                         if (always)
 164                                 bb = linearize_statement(ep, bb, always);
 165                         if (never) {
 166                                 struct basic_block *n = new_basic_block(ep, NULL);
 167                                 n = linearize_statement(ep, n, never);
 168                                 if (bb_reachable(n)) {
 169                                         struct symbol *merge = alloc_symbol(never->pos, SYM_LABEL);
 170                                         n->next = merge;
 171                                         bb->next = merge;
 172                                         bb = new_basic_block(ep, merge);
 173                                 }
 174                         }
 175                         break;
 176                 }
 177
 178
 179                 target = alloc_symbol(stmt->pos, SYM_LABEL);
 180                 goto_bb = alloc_statement(stmt->pos, STMT_CONDFALSE);
 181
 182                 add_statement(&bb->stmts, goto_bb);
 183                 last_bb = new_basic_block(ep, target);
 184
 185                 goto_bb->bb_conditional = cond;
 186                 goto_bb->bb_target = target;
 187
 188                 bb = linearize_statement(ep, bb, stmt->if_true);
 189                 bb->next = target;
 190
 191                 if (stmt->if_false) {
 192                         struct symbol *else_target = alloc_symbol(stmt->pos, SYM_LABEL);
 193                         struct basic_block *else_bb = new_basic_block(ep, else_target);
 194
 195                         else_bb = linearize_statement(ep, else_bb, stmt->if_false);
 196                         goto_bb->bb_target = else_target;
 197                         else_bb->next = target;
 198                 }
 199
 200                 bb = last_bb;
 201                 break;
 202         }
 203
 204         case STMT_SWITCH: {
 205                 struct symbol *sym;
 206                 struct statement *switch_value;
 207
 208                 /* Create the "head node" */
 209                 switch_value = alloc_statement(stmt->pos, STMT_MULTIVALUE);
 210                 switch_value->expression = stmt->switch_expression;
 211                 add_statement(&bb->stmts, switch_value);
 212
 213                 /* Create all the sub-jumps */
 214                 FOR_EACH_PTR(stmt->switch_case->symbol_list, sym) {
 215                         struct statement *case_stmt = sym->stmt;
 216                         struct statement *sw_bb = alloc_statement(case_stmt->pos, STMT_MULTIJMP);
 217                         sw_bb->multi_from = case_stmt->case_expression;
 218                         sw_bb->multi_to = case_stmt->case_to;
 219                         sw_bb->multi_target = sym;
 220                         add_statement(&bb->stmts, sw_bb);
 221                 } END_FOR_EACH_PTR;
 222
 223                 /* Default fall-through case */
 224                 bb->next = stmt->switch_break;
 225
 226                 /* And linearize the actual statement */
 227                 bb = linearize_statement(ep, new_basic_block(ep, NULL), stmt->switch_statement);
 228
 229                 /* ..then tie it all together at the end.. */
 230                 bb->next = stmt->switch_break;
 231                 bb = new_basic_block(ep, stmt->switch_break);
 232
 233                 break;
 234         }
 235
 236         case STMT_ITERATOR: {
 237                 struct statement  *pre_statement = stmt->iterator_pre_statement;
 238                 struct expression *pre_condition = stmt->iterator_pre_condition;
 239                 struct statement  *statement = stmt->iterator_statement;
 240                 struct statement  *post_statement = stmt->iterator_post_statement;
 241                 struct expression *post_condition = stmt->iterator_post_condition;
 242                 struct symbol *loop_top = NULL, *loop_bottom = NULL;
 243
 244                 concat_symbol_list(stmt->iterator_syms, &ep->syms);
 245                 bb = linearize_statement(ep, bb, pre_statement);
 246                 if (pre_condition) {
 247                         if (pre_condition->type == EXPR_VALUE) {
 248                                 if (!pre_condition->value) {
 249                                         loop_bottom = alloc_symbol(stmt->pos, SYM_LABEL);
 250                                         bb->next = loop_bottom;
 251                                         bb = new_basic_block(ep, loop_bottom);
 252                                 }
 253                         } else {
 254                                 struct statement *pre_cond = alloc_statement(stmt->pos, STMT_CONDFALSE);
 255                                 loop_bottom = alloc_symbol(stmt->pos, SYM_LABEL);
 256                                 pre_cond->bb_conditional = pre_condition;
 257                                 pre_cond->bb_target = loop_bottom;
 258                                 add_statement(&bb->stmts, pre_cond);
 259                         }
 260                 }
 261
 262                 if (!post_condition || post_condition->type != EXPR_VALUE || post_condition->value) {
 263                         struct basic_block *loop;
 264
 265                         loop_top = alloc_symbol(stmt->pos, SYM_LABEL);
 266                         loop = new_basic_block(ep, loop_top);
 267                         bb->next = loop_top;
 268                         bb = loop;
 269                 }
 270
 271                 bb = linearize_statement(ep, bb, statement);
 272
 273                 if (stmt->iterator_continue->used) {
 274                         struct basic_block *cont = new_basic_block(ep, stmt->iterator_continue);
 275                         bb->next = stmt->iterator_continue;
 276                         bb = cont;
 277                 }
 278
 279                 bb = linearize_statement(ep, bb, post_statement);
 280
 281                 if (!post_condition) {
 282                         bb->next = loop_top;
 283                 } else {
 284                         if (post_condition->type != EXPR_VALUE || post_condition->value) {
 285                                 struct statement *post_cond = alloc_statement(stmt->pos, STMT_CONDTRUE);
 286                                 post_cond->bb_conditional = post_condition;
 287                                 post_cond->bb_target = loop_top;
 288                                 add_statement(&bb->stmts, post_cond);
 289                         }
 290                 }
 291
 292                 if (stmt->iterator_break->used) {
 293                         struct basic_block *brk = new_basic_block(ep, stmt->iterator_break);
 294                         bb->next = stmt->iterator_break;
 295                         bb = brk;
 296                 }
 297                 break;
 298         }
 299
 300         default:
 301                 break;
 302         }
 303         return bb;
 304 }
 305
 306 void linearize_symbol(struct symbol *sym)
 307 {
 308         struct symbol *base_type;
 309
 310         if (!sym)
 311                 return;
 312         base_type = sym->ctype.base_type;
 313         if (!base_type)
 314                 return;
 315         if (base_type->type == SYM_FN) {
 316                 if (base_type->stmt) {
 317                         struct entrypoint *ep = alloc_entrypoint();
 318                         struct basic_block *bb;
 319
 320                         ep->name = sym;
 321                         bb = new_basic_block(ep, sym);
 322                         concat_symbol_list(base_type->arguments, &ep->syms);
 323                         linearize_statement(ep, bb, base_type->stmt);
 324                         show_entry(ep);
 325                 }
 326         }
 327 }