1 #include "ucl.h"
2 #include "ast.h"
3 #include "stmt.h"
4 #include "expr.h"
5 #include "decl.h"
6 #include "gen.h"
7
8 static void TranslateStatement(AstStatement stmt);
9
10 /**
11 * This function decides if an expression has side effect.
12 * Side effect means changes in the state of execution environment.
13 * e.g. modifying an object or accessing a volatile object
14 */
HasSideEffect(AstExpression expr)15 static int HasSideEffect(AstExpression expr)
16 {
17 if (expr == NULL)
18 return 0;
19
20 // accessing a volatile object
21 if (expr->op == OP_ID && expr->ty->qual & VOLATILE)
22 return 1;
23
24 // function call, a function may not have side effect but ucc doesn't check this
25 if (expr->op == OP_CALL)
26 return 1;
27
28 // modifying an object
29 if (expr->op >= OP_ASSIGN && expr->op <= OP_MOD_ASSIGN ||
30 expr->op == OP_PREINC || expr->op == OP_PREDEC ||
31 expr->op == OP_POSTINC || expr->op == OP_POSTDEC)
32 return 1;
33
34 return HasSideEffect(expr->kids[0]) || HasSideEffect(expr->kids[1]);
35 }
36
37 /**
38 * This function translates an expression statement
39 */
TranslateExpressionStatement(AstStatement stmt)40 static void TranslateExpressionStatement(AstStatement stmt)
41 {
42 AstExpressionStatement exprStmt = AsExpr(stmt);
43
44 if (exprStmt->expr != NULL)
45 {
46 TranslateExpression(exprStmt->expr);
47 }
48 }
49
50 /**
51 * This function translates a labeled statement
52 */
TranslateLabelStatement(AstStatement stmt)53 static void TranslateLabelStatement(AstStatement stmt)
54 {
55 AstLabelStatement labelStmt = AsLabel(stmt);
56
57 // ignore unreferenced label
58 if (labelStmt->label->ref > 0)
59 {
60 /// if the label is not associated with a basic block,
61 /// create a new basic block to associate with it
62 if (labelStmt->label->respBB == NULL)
63 {
64 labelStmt->label->respBB = CreateBBlock();
65 }
66 StartBBlock(labelStmt->label->respBB);
67 }
68 TranslateStatement(labelStmt->stmt);
69 }
70
71 /**
72 * This function translates a case statement.
73 */
TranslateCaseStatement(AstStatement stmt)74 static void TranslateCaseStatement(AstStatement stmt)
75 {
76 AstCaseStatement caseStmt = AsCase(stmt);
77
78 /// see TranslateSwitchStatement, which already creates a basic block
79 /// to associate with each case statement in a switch
80 StartBBlock(caseStmt->respBB);
81 TranslateStatement(caseStmt->stmt);
82 }
83
84 /**
85 * This function translates a default statement
86 */
TranslateDefaultStatement(AstStatement stmt)87 static void TranslateDefaultStatement(AstStatement stmt)
88 {
89 AstDefaultStatement defStmt = AsDef(stmt);
90
91 /// see TranslateSwitchStatement, which already creates a basic block
92 /// to associate with the default statement in a switch
93 StartBBlock(defStmt->respBB);
94 TranslateStatement(defStmt->stmt);
95 }
96
97 /**
98 * This function translates an if statement.
99 *
100 * if (expr) stmt is translated into:
101 * if ! expr goto nextBB
102 * trueBB:
103 * stmt
104 * nextBB:
105 * ...
106 *
107 * if (expr) stmt1 else stmt2 is translated into:
108 * if ! expr goto falseBB
109 * trueBB:
110 * stmt1
111 * goto nextBB
112 * falseBB:
113 * stmt2
114 * nextBB:
115 * ...
116 */
TranslateIfStatement(AstStatement stmt)117 static void TranslateIfStatement(AstStatement stmt)
118 {
119 AstIfStatement ifStmt = AsIf(stmt);
120 BBlock nextBB;
121 BBlock trueBB;
122 BBlock falseBB;
123
124 nextBB = CreateBBlock();
125 trueBB = CreateBBlock();
126
127 if (ifStmt->elseStmt == NULL)
128 {
129 TranslateBranch(Not(ifStmt->expr), nextBB, trueBB);
130
131 StartBBlock(trueBB);
132 TranslateStatement(ifStmt->thenStmt);
133 }
134 else
135 {
136 falseBB = CreateBBlock();
137
138 TranslateBranch(Not(ifStmt->expr), falseBB, trueBB);
139
140 StartBBlock(trueBB);
141 TranslateStatement(ifStmt->thenStmt);
142 GenerateJump(nextBB);
143
144 StartBBlock(falseBB);
145 TranslateStatement(ifStmt->elseStmt);
146 }
147
148 StartBBlock(nextBB);
149 }
150
151 /**
152 * This function translates a while statement.
153 *
154 * while (expr) stmt is translated into:
155 * goto contBB
156 * loopBB:
157 * stmt
158 * contBB:
159 * if (expr) goto loopBB
160 * nextBB:
161 * ...
162 */
TranslateWhileStatement(AstStatement stmt)163 static void TranslateWhileStatement(AstStatement stmt)
164 {
165 AstLoopStatement whileStmt = AsLoop(stmt);
166
167 whileStmt->loopBB = CreateBBlock();
168 whileStmt->contBB = CreateBBlock();
169 whileStmt->nextBB = CreateBBlock();
170
171 GenerateJump(whileStmt->contBB);
172
173 StartBBlock(whileStmt->loopBB);
174 TranslateStatement(whileStmt->stmt);
175
176 StartBBlock(whileStmt->contBB);
177 TranslateBranch(whileStmt->expr, whileStmt->loopBB, whileStmt->nextBB);
178
179 StartBBlock(whileStmt->nextBB);
180 }
181
182 /**
183 * This function translates a do statement.
184 *
185 * do stmt while (expr) is translated into:
186 * loopBB:
187 * stmt
188 * contBB:
189 * if (expr) goto loopBB
190 * nextBB:
191 * ...
192 */
TranslateDoStatement(AstStatement stmt)193 static void TranslateDoStatement(AstStatement stmt)
194 {
195 AstLoopStatement doStmt = AsLoop(stmt);
196
197 doStmt->loopBB = CreateBBlock();
198 doStmt->contBB = CreateBBlock();
199 doStmt->nextBB = CreateBBlock();
200
201 StartBBlock(doStmt->loopBB);
202 TranslateStatement(doStmt->stmt);
203
204 StartBBlock(doStmt->contBB);
205 TranslateBranch(doStmt->expr, doStmt->loopBB, doStmt->nextBB);
206
207 StartBBlock(doStmt->nextBB);
208 }
209
210 /**
211 * This function translates a for statement.
212 *
213 * for (expr1; expr2; expr3) stmt is translated into
214 * expr1
215 * goto testBB
216 * loopBB:
217 * stmt
218 * contBB:
219 * expr3
220 * testBB:
221 * if expr2 goto loopBB (goto loopBB if expr2 is NULL)
222 * nextBB:
223 * ...
224 * Please pay attention to the difference between for and while
225 * The continue point and loop test point is same for a while statemnt,
226 * but different for a for statment.
227 */
TranslateForStatement(AstStatement stmt)228 static void TranslateForStatement(AstStatement stmt)
229 {
230 AstForStatement forStmt = AsFor(stmt);
231
232 forStmt->loopBB = CreateBBlock();
233 forStmt->contBB = CreateBBlock();
234 forStmt->testBB = CreateBBlock();
235 forStmt->nextBB = CreateBBlock();
236
237 if (forStmt->initExpr)
238 {
239 TranslateExpression(forStmt->initExpr);
240 }
241 GenerateJump(forStmt->testBB);
242
243 StartBBlock(forStmt->loopBB);
244 TranslateStatement(forStmt->stmt);
245
246 StartBBlock(forStmt->contBB);
247 if (forStmt->incrExpr)
248 {
249 TranslateExpression(forStmt->incrExpr);
250 }
251
252 StartBBlock(forStmt->testBB);
253 if (forStmt->expr)
254 {
255 TranslateBranch(forStmt->expr, forStmt->loopBB, forStmt->nextBB);
256 }
257 else
258 {
259 GenerateJump(forStmt->loopBB);
260 }
261
262 StartBBlock(forStmt->nextBB);
263 }
264
265 /**
266 * This funtion translates a goto statement
267 *
268 * goto label is translation into:
269 * goto labelBB
270 * nextBB:
271 * ...
272 */
TranslateGotoStatement(AstStatement stmt)273 static void TranslateGotoStatement(AstStatement stmt)
274 {
275 AstGotoStatement gotoStmt = AsGoto(stmt);
276
277 /// if there is no basic block associated with the label,
278 /// create a basic block to associate with it
279 if (gotoStmt->label->respBB == NULL)
280 {
281 gotoStmt->label->respBB = CreateBBlock();
282 }
283 GenerateJump(gotoStmt->label->respBB);
284 StartBBlock(CreateBBlock());
285 }
286
287 /**
288 * This function translates a break statement.
289 * A break statement terminates the execution of associated
290 * switch or loop.
291 *
292 * break is translated into:
293 * goto switch or loop's nextBB
294 * nextBB:
295 * ...
296 */
TranslateBreakStatement(AstStatement stmt)297 static void TranslateBreakStatement(AstStatement stmt)
298 {
299 AstBreakStatement brkStmt = AsBreak(stmt);
300
301 if (brkStmt->target->kind == NK_SwitchStatement)
302 {
303 GenerateJump(AsSwitch(brkStmt->target)->nextBB);
304 }
305 else
306 {
307 GenerateJump(AsLoop(brkStmt->target)->nextBB);
308 }
309 StartBBlock(CreateBBlock());
310 }
311
312 /**
313 * This function translates a continue statement.
314 * A continue statement causes next iteration of associated loop.
315 *
316 * continue is translate into:
317 * goto loop's contBB
318 * nextBB:
319 * ...
320 */
TranslateContinueStatement(AstStatement stmt)321 static void TranslateContinueStatement(AstStatement stmt)
322 {
323 AstContinueStatement contStmt = AsCont(stmt);
324
325 GenerateJump(contStmt->target->contBB);
326 StartBBlock(CreateBBlock());
327 }
328
329 /**
330 * Translates a return statement.
331 * A return statement terminates execution of current function.
332 */
TranslateReturnStatement(AstStatement stmt)333 static void TranslateReturnStatement(AstStatement stmt)
334 {
335 AstReturnStatement retStmt = AsRet(stmt);
336
337 if (retStmt->expr)
338 {
339 GenerateReturn(retStmt->expr->ty, TranslateExpression(retStmt->expr));
340 }
341 GenerateJump(FSYM->exitBB);
342 StartBBlock(CreateBBlock());
343 }
344
345 /**
346 * Merge the switch buckets.
347 */
MergeSwitchBucket(SwitchBucket * pBucket)348 static int MergeSwitchBucket(SwitchBucket *pBucket)
349 {
350 SwitchBucket bucket = *pBucket;
351 int count = 0;
352
353 while (bucket->prev)
354 {
355 if ((bucket->prev->ncase + bucket->ncase + 1) * 2 <= (bucket->maxVal - bucket->prev->minVal))
356 break;
357
358 bucket->prev->ncase += bucket->ncase;
359 bucket->prev->maxVal = bucket->maxVal;
360 *bucket->prev->tail = bucket->cases;
361 bucket->prev->tail = bucket->tail;
362 bucket= bucket->prev;
363 count++;
364 }
365
366 *pBucket = bucket;
367 return count;
368 }
369
370 /**
371 * Generates selection and jump code for an array of switch buckets using a binary search.
372 * Given the following bucket array:
373 * [0, 1, 2] [9, 11] [24]
374 * First select [9, 11].
375 * if choice < 9, goto left half [0, 1, 2]
376 * if choice > 11, goto right half [24]
377 * generate indirect jump to each case statement and default label
378 */
TranslateSwitchBuckets(SwitchBucket * bucketArray,int left,int right,Symbol choice,BBlock currBB,BBlock defBB)379 static void TranslateSwitchBuckets(SwitchBucket *bucketArray, int left, int right,
380 Symbol choice, BBlock currBB, BBlock defBB)
381 {
382 int mid, len, i;
383 AstCaseStatement p;
384 BBlock lhalfBB, rhalfBB;
385 BBlock *dstBBs;
386 Symbol index;
387
388 if (left > right)
389 return;
390
391 mid = (left + right) / 2;
392 lhalfBB = (left > mid - 1) ? defBB : CreateBBlock();
393 rhalfBB = (mid + 1 > right) ? defBB : CreateBBlock();
394
395 len = bucketArray[mid]->maxVal - bucketArray[mid]->minVal + 1;
396
397 dstBBs = HeapAllocate(CurrentHeap, (len + 1)* sizeof(BBlock));
398 for (i = 0; i < len; ++i)
399 dstBBs[i] = defBB;
400 dstBBs[len] = NULL;
401
402 p = bucketArray[mid]->cases;
403 while (p)
404 {
405 i = p->expr->val.i[0] - bucketArray[mid]->minVal;
406 dstBBs[i] = p->respBB;
407 p = p->nextCase;
408 }
409
410 if (currBB != NULL)
411 {
412 StartBBlock(currBB);
413 }
414 GenerateBranch(choice->ty, lhalfBB, JL, choice, IntConstant(bucketArray[mid]->minVal));
415
416 StartBBlock(CreateBBlock());
417 GenerateBranch(choice->ty, rhalfBB, JG, choice, IntConstant(bucketArray[mid]->maxVal));
418
419 StartBBlock(CreateBBlock());
420
421 if (len != 1)
422 {
423 index = CreateTemp(choice->ty);
424 GenerateAssign(choice->ty, index, SUB, choice, IntConstant(bucketArray[mid]->minVal));
425 GenerateIndirectJump(dstBBs, len, index);
426 }
427 else
428 {
429 GenerateJump(dstBBs[0]);
430 }
431
432 StartBBlock(CreateBBlock());
433
434 TranslateSwitchBuckets(bucketArray, left, mid - 1, choice, lhalfBB, defBB);
435 TranslateSwitchBuckets(bucketArray, mid + 1, right, choice, rhalfBB, defBB);
436
437 }
438
439 /**
440 * Generate intermediate code for switch statement.
441 * During semantic check, the case statements in a switch statement is already ordered in ascending order.
442 * The first step of this function is to divide these case statements into switch buckets.
443 * The dividing criteria is:
444 * Each switch bucket holds some case statements, there must be a case statement with minimum value(minVal)
445 * and a case statement with maximum value(maxVal). We define the density of the switch bucket to be:
446 * density = number of case statements / (maxVal - minVal). The density of a switch bucket must be greater
447 * than 1/2.
448 * And when adding new case statements into a switch bucket, there is a chance that the switch bucket can be
449 * merged with previous switch buckets.
450 *
451 * Given the following switch statement:
452 * switch (a) { case 0: case 1: case 4: case 9: case 10: case 11: ... };
453 * [0, 1, 4] will be the first bucket, since 3 / (4 - 0) > 1/2.
454 * 9 will starts a new bucket, since 4 / (9 - 0) < 1/2. But when encountering 11, 6 / (11 - 0) > 1/2
455 * So the merged bucket will be [0, 1, 4, 9, 10, 11]
456 *
457 * The second step generates the selection and jump code to different switch buckets(See TranslateSwitchBuckets)
458 *
459 * The final step generates the intermediate code for the enclosed statement.
460 */
TranslateSwitchStatement(AstStatement stmt)461 static void TranslateSwitchStatement(AstStatement stmt)
462 {
463 AstSwitchStatement swtchStmt = AsSwitch(stmt);
464 AstCaseStatement p, q;
465 SwitchBucket bucket, b;
466 SwitchBucket *bucketArray;
467 int i, val;
468 Symbol sym;
469
470 sym = TranslateExpression(swtchStmt->expr);
471
472 bucket = b = NULL;
473 p = swtchStmt->cases;
474 while (p)
475 {
476 q = p;
477 p = p->nextCase;
478
479 q->respBB = CreateBBlock();
480 val = q->expr->val.i[0];
481 if (bucket && (bucket->ncase + 1) * 2 > (val - bucket->minVal))
482 {
483 bucket->ncase++;
484 bucket->maxVal = val;
485 *bucket->tail = q;
486 bucket->tail = &(q->nextCase);
487 swtchStmt->nbucket -= MergeSwitchBucket(&bucket);
488 }
489 else
490 {
491 ALLOC(b);
492
493 b->cases = q;
494 b->ncase = 1;
495 b->minVal = b->maxVal = val;
496 b->tail = &(q->nextCase);
497 b->prev = bucket;
498 bucket = b;
499 swtchStmt->nbucket++;
500 }
501 }
502 swtchStmt->buckets = bucket;
503
504 bucketArray = HeapAllocate(CurrentHeap, swtchStmt->nbucket * sizeof(SwitchBucket));
505
506 for (i = swtchStmt->nbucket - 1; i >= 0; i--)
507 {
508 bucketArray[i] = bucket;
509 *bucket->tail = NULL;
510 bucket = bucket->prev;
511 }
512
513 swtchStmt->defBB = CreateBBlock();
514 if (swtchStmt->defStmt)
515 {
516 swtchStmt->defStmt->respBB = swtchStmt->defBB;
517 swtchStmt->nextBB = CreateBBlock();
518 }
519 else
520 {
521 swtchStmt->nextBB = swtchStmt->defBB;
522 }
523 TranslateSwitchBuckets(bucketArray, 0, swtchStmt->nbucket - 1, sym, NULL, swtchStmt->defBB);
524 TranslateStatement(swtchStmt->stmt);
525 StartBBlock(swtchStmt->nextBB);
526 }
527
TranslateCompoundStatement(AstStatement stmt)528 static void TranslateCompoundStatement(AstStatement stmt)
529 {
530 AstCompoundStatement compStmt = AsComp(stmt);
531 AstNode p = compStmt->stmts;
532 Vector ilocals = compStmt->ilocals;
533 Symbol v;
534 int i;
535
536 for (i = 0; i < LEN(ilocals); ++i)
537 {
538 InitData initd;
539 Type ty;
540 Symbol dst, src;
541 int size;
542
543 v = GET_ITEM(ilocals, i);
544 initd = AsVar(v)->idata;
545 size = 0;
546 while (initd != NULL)
547 {
548 if (initd->offset != size)
549 {
550 dst = CreateOffset(T(UCHAR), v, size);
551 GenerateClear(dst, initd->offset - size);
552 }
553 ty = initd->expr->ty;
554 if (initd->expr->op == OP_STR)
555 {
556 String str = initd->expr->val.p;
557
558 src = AddString(ArrayOf(str->len + 1, ty->bty), str);
559 }
560 else
561 {
562 src = TranslateExpression(initd->expr);
563 }
564 dst = CreateOffset(ty, v, initd->offset);
565 GenerateMove(ty, dst, src);
566
567 size = initd->offset + ty->size;
568 initd = initd->next;
569 }
570 if (size < v->ty->size)
571 {
572 dst = CreateOffset(T(UCHAR), v, size);
573 GenerateClear(dst, v->ty->size - size);
574 }
575 }
576
577 while (p)
578 {
579 TranslateStatement((AstStatement)p);
580 p = p->next;
581 }
582
583 }
584
585 static void (* StmtTrans[])(AstStatement) =
586 {
587 TranslateExpressionStatement,
588 TranslateLabelStatement,
589 TranslateCaseStatement,
590 TranslateDefaultStatement,
591 TranslateIfStatement,
592 TranslateSwitchStatement,
593 TranslateWhileStatement,
594 TranslateDoStatement,
595 TranslateForStatement,
596 TranslateGotoStatement,
597 TranslateBreakStatement,
598 TranslateContinueStatement,
599 TranslateReturnStatement,
600 TranslateCompoundStatement
601 };
602
TranslateStatement(AstStatement stmt)603 static void TranslateStatement(AstStatement stmt)
604 {
605 (* StmtTrans[stmt->kind - NK_ExpressionStatement])(stmt);
606 }
607
TranslateFunction(AstFunction func)608 static void TranslateFunction(AstFunction func)
609 {
610 BBlock bb;
611
612 FSYM = func->fsym;
613 if (! FSYM->defined)
614 return;
615
616 TempNum = 0;
617 FSYM->entryBB = CreateBBlock();
618 FSYM->exitBB = CreateBBlock();
619
620 CurrentBB = FSYM->entryBB;
621 TranslateStatement(func->stmt);
622 StartBBlock(FSYM->exitBB);
623
624 Optimize(FSYM);
625
626 bb = FSYM->entryBB;
627 while (bb != NULL)
628 {
629 if (bb->ref != 0)
630 {
631 bb->sym = CreateLabel();
632 }
633 bb = bb->next;
634 }
635 }
636
Translate(AstTranslationUnit transUnit)637 void Translate(AstTranslationUnit transUnit)
638 {
639 AstNode p = transUnit->extDecls;
640
641 while (p)
642 {
643 if (p->kind == NK_Function && ((AstFunction)p)->stmt)
644 {
645 TranslateFunction((AstFunction)p);
646 }
647 p = p->next;
648 }
649 }
650