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\n", bb);
  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 static struct basic_block * new_basic_block(struct basic_block_list **bbs)
  69 {
  70         struct basic_block *bb = alloc_basic_block();
  71         add_bb(bbs, bb);
  72         return bb;
  73 }
  74
  75 static struct basic_block * linearize_statement(struct symbol_list **syms,
  76         struct basic_block_list **bbs,
  77         struct basic_block *bb,
  78         struct statement *stmt)
  79 {
  80         if (!stmt)
  81                 return bb;
  82
  83         switch (stmt->type) {
  84         case STMT_NONE:
  85                 break;
  86
  87         case STMT_ASM:
  88         case STMT_EXPRESSION:
  89                 add_statement(&bb->stmts, stmt);
  90                 break;
  91
  92         case STMT_RETURN:
  93                 add_statement(&bb->stmts, stmt);
  94                 bb = new_basic_block(bbs);
  95                 break;
  96
  97         case STMT_CASE: {
  98                 struct basic_block *new_bb = new_basic_block(bbs);
  99                 struct symbol *sym = stmt->case_label;
 100
 101                 bb->next = sym;
 102                 sym->bb_target = new_bb;
 103
 104                 bb = linearize_statement(syms, bbs, new_bb, stmt->case_statement);
 105                 break;
 106         }
 107
 108         case STMT_LABEL: {
 109                 struct basic_block *new_bb = new_basic_block(bbs);
 110                 struct symbol *sym = stmt->label_identifier;
 111
 112                 bb->next = sym;
 113                 sym->bb_target = new_bb;
 114
 115                 bb = linearize_statement(syms, bbs, new_bb, stmt->label_statement);
 116                 break;
 117         }
 118
 119         case STMT_GOTO: {
 120                 struct basic_block *new_bb = new_basic_block(bbs);
 121                 struct symbol *sym = stmt->goto_label;
 122
 123                 bb->next = sym;
 124                 bb = new_bb;
 125                 break;
 126         }
 127
 128         case STMT_COMPOUND: {
 129                 struct statement *s;
 130                 concat_symbol_list(stmt->syms, syms);
 131                 FOR_EACH_PTR(stmt->stmts, s) {
 132                         bb = linearize_statement(syms, bbs, bb, s);
 133                 } END_FOR_EACH_PTR;
 134                 break;
 135         }
 136
 137         /*
 138          * This could take 'likely/unlikely' into account, and
 139          * switch the arms around appropriately..
 140          */
 141         case STMT_IF: {
 142                 struct symbol *target = alloc_symbol(stmt->pos, SYM_LABEL);
 143                 struct statement *goto_bb = alloc_statement(stmt->pos, STMT_CONDFALSE);
 144                 struct basic_block *last_bb;
 145
 146                 add_statement(&bb->stmts, goto_bb);
 147                 last_bb = new_basic_block(bbs);
 148
 149                 goto_bb->bb_conditional = stmt->if_conditional;
 150                 goto_bb->bb_target = target;
 151
 152                 bb = linearize_statement(syms, bbs, bb, stmt->if_true);
 153                 bb->next = target;
 154                 target->bb_target = last_bb;
 155
 156                 if (stmt->if_false) {
 157                         struct symbol *else_target = alloc_symbol(stmt->pos, SYM_LABEL);
 158                         struct basic_block *else_bb = new_basic_block(bbs);
 159
 160                         else_target->bb_target = else_bb;
 161                         else_bb = linearize_statement(syms, bbs, else_bb, stmt->if_false);
 162                         goto_bb->bb_target = else_target;
 163                         else_bb->next = target;
 164                 }
 165
 166                 bb = last_bb;
 167                 break;
 168         }
 169
 170         case STMT_SWITCH: {
 171                 struct symbol *sym;
 172                 struct statement *switch_value;
 173
 174                 /* Create the "head node" */
 175                 switch_value = alloc_statement(stmt->pos, STMT_MULTIVALUE);
 176                 switch_value->expression = stmt->switch_expression;
 177                 add_statement(&bb->stmts, switch_value);
 178
 179                 /* Create all the sub-jumps */
 180                 FOR_EACH_PTR(stmt->switch_case->symbol_list, sym) {
 181                         struct statement *case_stmt = sym->stmt;
 182                         struct statement *sw_bb = alloc_statement(case_stmt->pos, STMT_MULTIJMP);
 183                         sw_bb->multi_from = case_stmt->case_expression;
 184                         sw_bb->multi_to = case_stmt->case_to;
 185                         sw_bb->multi_target = sym;
 186                         add_statement(&bb->stmts, sw_bb);
 187                 } END_FOR_EACH_PTR;
 188
 189                 /* And linearize the actual statement */
 190                 bb = linearize_statement(syms, bbs, new_basic_block(bbs), stmt->switch_statement);
 191
 192                 /* ..then tie it all together at the end.. */
 193                 bb->next = stmt->switch_break;
 194                 bb = new_basic_block(bbs);
 195                 stmt->switch_break->bb_target = bb;
 196
 197                 break;
 198         }
 199
 200         case STMT_ITERATOR: {
 201                 struct statement  *pre_statement = stmt->iterator_pre_statement;
 202                 struct expression *pre_condition = stmt->iterator_pre_condition;
 203                 struct statement  *statement = stmt->iterator_statement;
 204                 struct statement  *post_statement = stmt->iterator_post_statement;
 205                 struct expression *post_condition = stmt->iterator_post_condition;
 206                 struct symbol *loop_top = NULL, *loop_bottom = NULL;
 207
 208                 concat_symbol_list(stmt->iterator_syms, syms);
 209                 bb = linearize_statement(syms, bbs, bb, pre_statement);
 210                 if (pre_condition) {
 211                         if (pre_condition->type == EXPR_VALUE) {
 212                                 if (!pre_condition->value) {
 213                                         loop_bottom = alloc_symbol(stmt->pos, SYM_LABEL);
 214                                         bb->next = loop_bottom;
 215                                         bb = new_basic_block(bbs);
 216                                 }
 217                         } else {
 218                                 struct statement *pre_cond = alloc_statement(stmt->pos, STMT_CONDFALSE);
 219                                 loop_bottom = alloc_symbol(stmt->pos, SYM_LABEL);
 220                                 pre_cond->bb_conditional = pre_condition;
 221                                 pre_cond->bb_target = loop_bottom;
 222                                 add_statement(&bb->stmts, pre_cond);
 223                         }
 224                 }
 225
 226                 if (!post_condition || post_condition->type != EXPR_VALUE || post_condition->value) {
 227                         struct basic_block *loop = new_basic_block(bbs);
 228                         loop_top = alloc_symbol(stmt->pos, SYM_LABEL);
 229                         loop_top->bb_target = loop;
 230                         bb->next = loop_top;
 231                         bb = loop;
 232                 }
 233
 234                 bb = linearize_statement(syms, bbs, bb, statement);
 235
 236                 if (stmt->iterator_continue->used) {
 237                         struct basic_block *cont = new_basic_block(bbs);
 238                         stmt->iterator_continue->bb_target = cont;
 239                         bb->next = stmt->iterator_continue;
 240                         bb = cont;
 241                 }
 242
 243                 bb = linearize_statement(syms, bbs, bb, post_statement);
 244
 245                 if (!post_condition) {
 246                         bb->next = loop_top;
 247                 } else {
 248                         if (post_condition->type != EXPR_VALUE || post_condition->value) {
 249                                 struct statement *post_cond = alloc_statement(stmt->pos, STMT_CONDTRUE);
 250                                 post_cond->bb_conditional = post_condition;
 251                                 post_cond->bb_target = loop_top;
 252                                 add_statement(&bb->stmts, post_cond);
 253                         }
 254                 }
 255
 256                 if (stmt->iterator_break->used) {
 257                         struct basic_block *brk = new_basic_block(bbs);
 258                         stmt->iterator_break->bb_target = brk;
 259                         bb->next = stmt->iterator_break;
 260                         bb = brk;
 261                 }
 262                 break;
 263         }
 264
 265         default:
 266                 break;
 267         }
 268         return bb;
 269 }
 270
 271 void linearize_symbol(struct symbol *sym)
 272 {
 273         struct symbol *base_type;
 274
 275         if (!sym)
 276                 return;
 277         base_type = sym->ctype.base_type;
 278         if (!base_type)
 279                 return;
 280         if (base_type->type == SYM_FN) {
 281                 if (base_type->stmt) {
 282                         struct entrypoint *ep = alloc_entrypoint();
 283                         struct basic_block *bb;
 284
 285                         ep->name = sym;
 286                         bb = new_basic_block(&ep->bbs);
 287                         concat_symbol_list(base_type->arguments, &ep->syms);
 288                         linearize_statement(&ep->syms, &ep->bbs, bb, base_type->stmt);
 289                         show_entry(ep);
 290                 }
 291         }
 292 }