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 void add_label(struct entrypoint *ep, struct symbol *sym)
  89 {
  90         struct basic_block *new_bb = new_basic_block(ep, sym);
  91
  92         ep->active->next = sym;
  93         ep->active = new_bb;
  94 }
  95
  96 static void linearize_simple_statement(struct entrypoint *ep, struct statement *stmt)
  97 {
  98         struct basic_block *bb = ep->active;
  99
 100         if (bb_reachable(bb)) {
 101                 if (bb->flags & BB_HASBRANCH) {
 102                         add_label(ep, alloc_symbol(stmt->pos, SYM_LABEL));
 103                         bb = ep->active;
 104                 }
 105                 add_statement(&bb->stmts, stmt);
 106         }
 107 }
 108
 109 static void set_unreachable(struct entrypoint *ep)
 110 {
 111         ep->active = new_basic_block(ep, NULL);
 112 }
 113
 114 static void add_branch(struct entrypoint *ep, struct statement *stmt, int true, struct expression *cond, struct symbol *target)
 115 {
 116         struct basic_block *bb = ep->active;
 117
 118         if (bb_reachable(bb)) {
 119                 struct statement *jump = alloc_statement(stmt->pos, true);
 120                 jump->bb_conditional = cond;
 121                 jump->bb_target = target;
 122                 bb->flags |= BB_HASBRANCH;
 123                 add_statement(&bb->stmts, jump);
 124         }
 125 }
 126
 127 void linearize_statement(struct entrypoint *ep, struct statement *stmt)
 128 {
 129         if (!stmt)
 130                 return;
 131
 132         switch (stmt->type) {
 133         case STMT_NONE:
 134                 break;
 135
 136         case STMT_ASM:
 137         case STMT_EXPRESSION:
 138                 linearize_simple_statement(ep, stmt);
 139                 break;
 140
 141         case STMT_RETURN:
 142                 linearize_simple_statement(ep, stmt);
 143                 set_unreachable(ep);
 144                 break;
 145
 146         case STMT_CASE: {
 147                 add_label(ep, stmt->case_label);
 148                 linearize_statement(ep, stmt->case_statement);
 149                 break;
 150         }
 151
 152         case STMT_LABEL: {
 153                 add_label(ep, stmt->label_identifier);
 154                 linearize_statement(ep, stmt->label_statement);
 155                 break;
 156         }
 157
 158         case STMT_GOTO: {
 159                 ep->active->next = stmt->goto_label;
 160                 set_unreachable(ep);
 161                 break;
 162         }
 163
 164         case STMT_COMPOUND: {
 165                 struct statement *s;
 166                 concat_symbol_list(stmt->syms, &ep->syms);
 167                 FOR_EACH_PTR(stmt->stmts, s) {
 168                         linearize_statement(ep, s);
 169                 } END_FOR_EACH_PTR;
 170                 break;
 171         }
 172
 173         /*
 174          * This could take 'likely/unlikely' into account, and
 175          * switch the arms around appropriately..
 176          */
 177         case STMT_IF: {
 178                 struct symbol *target;
 179                 struct basic_block *if_block;
 180                 struct expression *cond = stmt->if_conditional;
 181
 182                 if (cond->type == EXPR_VALUE) {
 183                         struct statement *always = stmt->if_true;
 184                         struct statement *never = stmt->if_false;
 185
 186                         if (!cond->value) {
 187                                 never = always;
 188                                 always = stmt->if_false;
 189                         }
 190                         if (always)
 191                                 linearize_statement(ep, always);
 192                         if (never) {
 193                                 struct basic_block *bb = ep->active;
 194                                 set_unreachable(ep);
 195                                 linearize_statement(ep, never);
 196
 197                                 /*
 198                                  * If the "never case" is reachable some other
 199                                  * way, we need to merge the old always case
 200                                  * with the fallthrough of the never case.
 201                                  */
 202                                 if (bb_reachable(ep->active)) {
 203                                         struct symbol *merge = alloc_symbol(never->pos, SYM_LABEL);
 204                                         add_label(ep, merge);
 205                                         bb->next = merge;
 206                                         break;
 207                                 }
 208
 209                                 /* Otherwise we just continue with the old always case.. */
 210                                 ep->active = bb;
 211                         }
 212                         break;
 213                 }
 214
 215
 216                 target = alloc_symbol(stmt->pos, SYM_LABEL);
 217                 add_branch(ep, stmt, STMT_CONDFALSE, cond, target);
 218
 219                 linearize_statement(ep, stmt->if_true);
 220
 221                 if_block = ep->active;
 222                 add_label(ep, target);
 223
 224                 if (stmt->if_false) {
 225                         struct symbol *else_target = alloc_symbol(stmt->pos, SYM_LABEL);
 226                         if_block->next = else_target;
 227                         linearize_statement(ep, stmt->if_false);
 228                         add_label(ep, else_target);
 229                 }
 230                 break;
 231         }
 232
 233         case STMT_SWITCH: {
 234                 struct symbol *sym;
 235                 struct statement *switch_value;
 236
 237                 /* Create the "head node" */
 238                 switch_value = alloc_statement(stmt->pos, STMT_MULTIVALUE);
 239                 switch_value->expression = stmt->switch_expression;
 240                 linearize_simple_statement(ep, switch_value);
 241
 242                 /* Create all the sub-jumps */
 243                 FOR_EACH_PTR(stmt->switch_case->symbol_list, sym) {
 244                         struct statement *case_stmt = sym->stmt;
 245                         struct statement *sw_bb = alloc_statement(case_stmt->pos, STMT_MULTIJMP);
 246                         sw_bb->multi_from = case_stmt->case_expression;
 247                         sw_bb->multi_to = case_stmt->case_to;
 248                         sw_bb->multi_target = sym;
 249                         linearize_simple_statement(ep, sw_bb);
 250                 } END_FOR_EACH_PTR;
 251
 252                 /* Default fall-through case */
 253                 ep->active->next = stmt->switch_break;
 254                 set_unreachable(ep);
 255
 256                 /* And linearize the actual statement */
 257                 linearize_statement(ep, stmt->switch_statement);
 258
 259                 /* ..then tie it all together at the end.. */
 260                 add_label(ep, stmt->switch_break);
 261                 break;
 262         }
 263
 264         case STMT_ITERATOR: {
 265                 struct statement  *pre_statement = stmt->iterator_pre_statement;
 266                 struct expression *pre_condition = stmt->iterator_pre_condition;
 267                 struct statement  *statement = stmt->iterator_statement;
 268                 struct statement  *post_statement = stmt->iterator_post_statement;
 269                 struct expression *post_condition = stmt->iterator_post_condition;
 270                 struct symbol *loop_top = NULL, *loop_bottom = NULL;
 271
 272                 concat_symbol_list(stmt->iterator_syms, &ep->syms);
 273                 linearize_statement(ep, pre_statement);
 274                 if (pre_condition) {
 275                         if (pre_condition->type == EXPR_VALUE) {
 276                                 if (!pre_condition->value) {
 277                                         loop_bottom = alloc_symbol(stmt->pos, SYM_LABEL);
 278                                         ep->active->next = loop_bottom;
 279                                         set_unreachable(ep);
 280                                 }
 281                         } else {
 282                                 loop_bottom = alloc_symbol(stmt->pos, SYM_LABEL);
 283                                 add_branch(ep, stmt, STMT_CONDFALSE, pre_condition, loop_bottom);
 284                         }
 285                 }
 286
 287                 if (!post_condition || post_condition->type != EXPR_VALUE || post_condition->value) {
 288                         loop_top = alloc_symbol(stmt->pos, SYM_LABEL);
 289                         add_label(ep, loop_top);
 290                 }
 291
 292                 linearize_statement(ep, statement);
 293
 294                 if (stmt->iterator_continue->used)
 295                         add_label(ep, stmt->iterator_continue);
 296
 297                 linearize_statement(ep, post_statement);
 298
 299                 if (!post_condition) {
 300                         ep->active->next = loop_top;
 301                         set_unreachable(ep);
 302                 } else {
 303                         if (post_condition->type != EXPR_VALUE || post_condition->value)
 304                                 add_branch(ep, stmt, STMT_CONDTRUE, post_condition, loop_top);
 305                 }
 306
 307                 if (stmt->iterator_break->used)
 308                         add_label(ep, stmt->iterator_break);
 309                 if (loop_bottom)
 310                         add_label(ep, loop_bottom);
 311                 break;
 312         }
 313
 314         default:
 315                 break;
 316         }
 317 }
 318
 319 void linearize_symbol(struct symbol *sym)
 320 {
 321         struct symbol *base_type;
 322
 323         if (!sym)
 324                 return;
 325         base_type = sym->ctype.base_type;
 326         if (!base_type)
 327                 return;
 328         if (base_type->type == SYM_FN) {
 329                 if (base_type->stmt) {
 330                         struct entrypoint *ep = alloc_entrypoint();
 331
 332                         ep->name = sym;
 333                         ep->active = new_basic_block(ep, sym);
 334                         concat_symbol_list(base_type->arguments, &ep->syms);
 335                         linearize_statement(ep, base_type->stmt);
 336                         show_entry(ep);
 337                 }
 338         }
 339 }