1 /** 2 * Flow analysis for Ownership/Borrowing 3 * 4 * Copyright: Copyright (C) 1999-2021 by The D Language Foundation, All Rights Reserved 5 * Authors: $(LINK2 http://www.digitalmars.com, Walter Bright) 6 * License: $(LINK2 http://www.boost.org/LICENSE_1_0.txt, Boost License 1.0) 7 * Source: $(LINK2 https://github.com/dlang/dmd/blob/master/src/dmd/ob.d, _ob.d) 8 * Documentation: https://dlang.org/phobos/dmd_escape.html 9 * Coverage: https://codecov.io/gh/dlang/dmd/src/master/src/dmd/ob.d 10 */ 11 12 module dmd.ob; 13 14 import core.stdc.stdio : printf; 15 import core.stdc.stdlib; 16 import core.stdc.string; 17 18 import dmd.root.array; 19 import dmd.root.rootobject; 20 import dmd.root.rmem; 21 22 import dmd.aggregate; 23 import dmd.apply; 24 import dmd.arraytypes; 25 import dmd.declaration; 26 import dmd.dscope; 27 import dmd.dsymbol; 28 import dmd.dtemplate; 29 import dmd.errors; 30 import dmd.escape; 31 import dmd.expression; 32 import dmd.foreachvar; 33 import dmd.func; 34 import dmd.globals; 35 import dmd.identifier; 36 import dmd.init; 37 import dmd.mtype; 38 import dmd.printast; 39 import dmd.statement; 40 import dmd.stmtstate; 41 import dmd.tokens; 42 import dmd.visitor; 43 44 import dmd.root.bitarray; 45 import dmd.root.outbuffer; 46 47 /********************************** 48 * Perform ownership/borrowing checks for funcdecl. 49 * Does not modify the AST, just checks for errors. 50 */ 51 52 void oblive(FuncDeclaration funcdecl) 53 { 54 //printf("oblive() %s\n", funcdecl.toChars()); 55 //printf("fbody: %s\n", funcdecl.fbody.toChars()); 56 ObState obstate; 57 58 /* Build the flow graph 59 */ 60 setLabelStatementExtraFields(funcdecl.labtab); 61 toObNodes(obstate.nodes, funcdecl.fbody); 62 insertFinallyBlockCalls(obstate.nodes); 63 insertFinallyBlockGotos(obstate.nodes); 64 removeUnreachable(obstate.nodes); 65 computePreds(obstate.nodes); 66 67 numberNodes(obstate.nodes); 68 //foreach (ob; obstate.nodes) ob.print(); 69 70 collectVars(funcdecl, obstate.vars); 71 allocStates(obstate); 72 doDataFlowAnalysis(obstate); 73 74 checkObErrors(obstate); 75 } 76 77 alias ObNodes = Array!(ObNode*); 78 79 alias StmtState = dmd.stmtstate.StmtState!ObNode; 80 81 /******************************************* 82 * Collect the state information. 83 */ 84 struct ObState 85 { 86 ObNodes nodes; 87 VarDeclarations vars; 88 89 Array!size_t varStack; /// temporary storage 90 Array!bool mutableStack; /// parallel to varStack[], is type mutable? 91 92 PtrVarState[] varPool; /// memory pool 93 94 ~this() 95 { 96 mem.xfree(varPool.ptr); 97 } 98 } 99 100 /*********************************************** 101 * A node in the function's expression graph, and its edges to predecessors and successors. 102 */ 103 struct ObNode 104 { 105 Expression exp; /// expression for the node 106 ObNodes preds; /// predecessors 107 ObNodes succs; /// successors 108 ObNode* tryBlock; /// try-finally block we're inside 109 ObType obtype; 110 uint index; /// index of this in obnodes 111 112 PtrVarState[] gen; /// new states generated for this node 113 PtrVarState[] input; /// variable states on entry to exp 114 PtrVarState[] output; /// variable states on exit to exp 115 116 this(ObNode* tryBlock) 117 { 118 this.tryBlock = tryBlock; 119 } 120 121 void print() 122 { 123 printf("%d: %s %s\n", index, obtype.toString.ptr, exp ? exp.toChars() : "-"); 124 printf(" preds: "); 125 foreach (ob; preds) 126 printf(" %d", ob.index); 127 printf("\n succs: "); 128 foreach (ob; succs) 129 printf(" %d", ob.index); 130 printf("\n\n"); 131 } 132 } 133 134 135 enum ObType : ubyte 136 { 137 goto_, /// goto one of the succs[] 138 return_, /// returns from function 139 retexp, /// returns expression from function 140 throw_, /// exits with throw 141 exit, /// exits program 142 try_, 143 finally_, 144 fend, 145 } 146 147 string toString(ObType obtype) 148 { 149 return obtype == ObType.goto_ ? "goto " : 150 obtype == ObType.return_ ? "ret " : 151 obtype == ObType.retexp ? "retexp" : 152 obtype == ObType.throw_ ? "throw" : 153 obtype == ObType.exit ? "exit" : 154 obtype == ObType.try_ ? "try" : 155 obtype == ObType.finally_ ? "finally" : 156 obtype == ObType.fend ? "fend" : 157 "---"; 158 } 159 160 /*********** 161 Pointer variable states: 162 163 Initial state is not known; ignore for now 164 165 Undefined not in a usable state 166 167 T* p = void; 168 169 Owner mutable pointer 170 171 T* p = initializer; 172 173 Borrowed scope mutable pointer, borrowed from [p] 174 175 T* p = initializer; 176 scope T* b = p; 177 178 Readonly scope const pointer, copied from [p] 179 180 T* p = initializer; 181 scope const(T)* cp = p; 182 183 Examples: 184 185 T* p = initializer; // p is owner 186 T** pp = &p; // pp borrows from p 187 188 T* p = initialize; // p is owner 189 T* q = p; // transfer: q is owner, p is undefined 190 */ 191 192 enum PtrState : ubyte 193 { 194 Initial, Undefined, Owner, Borrowed, Readonly 195 } 196 197 /************ 198 */ 199 const(char)* toChars(PtrState state) 200 { 201 return toString(state).ptr; 202 } 203 204 string toString(PtrState state) 205 { 206 return ["Initial", "Undefined", "Owner", "Borrowed", "Readonly"][state]; 207 } 208 209 /****** 210 * Carries the state of a pointer variable. 211 */ 212 struct PtrVarState 213 { 214 BitArray deps; /// dependencies 215 PtrState state; /// state the pointer variable is in 216 217 void opAssign(const ref PtrVarState pvs) 218 { 219 state = pvs.state; 220 deps = pvs.deps; 221 } 222 223 /* Combine `this` and `pvs` into `this`, 224 * on the idea that the `this` and the `pvs` paths 225 * are being merged 226 * Params: 227 * pvs = path to be merged with `this` 228 */ 229 void combine(ref PtrVarState pvs, size_t vi, PtrVarState[] gen) 230 { 231 static uint X(PtrState x1, PtrState x2) { return x1 * (PtrState.max + 1) + x2; } 232 233 with (PtrState) 234 { 235 switch (X(state, pvs.state)) 236 { 237 case X(Initial, Initial): 238 break; 239 240 case X(Initial, Owner ): 241 case X(Initial, Borrowed ): 242 case X(Initial, Readonly ): 243 // Transfer state to `this` 244 state = pvs.state; 245 deps = pvs.deps; 246 break; 247 248 case X(Owner, Initial): 249 case X(Borrowed, Initial): 250 case X(Readonly, Initial): 251 break; 252 253 case X(Undefined, Initial): 254 case X(Undefined, Undefined): 255 case X(Undefined, Owner ): 256 case X(Undefined, Borrowed ): 257 case X(Undefined, Readonly ): 258 break; 259 260 case X(Owner , Owner ): 261 break; 262 263 case X(Borrowed , Borrowed): 264 case X(Readonly , Readonly): 265 deps.or(pvs.deps); 266 break; 267 268 default: 269 makeUndefined(vi, gen); 270 break; 271 } 272 } 273 } 274 275 bool opEquals(const ref PtrVarState pvs) const 276 { 277 return state == pvs.state && 278 deps == pvs.deps; 279 } 280 281 /*********************** 282 */ 283 void print(VarDeclaration[] vars) 284 { 285 string s = toString(state); 286 printf("%.*s [", cast(int)s.length, s.ptr); 287 assert(vars.length == deps.length); 288 OutBuffer buf; 289 depsToBuf(buf, vars); 290 string t = buf[]; 291 printf("%.*s]\n", cast(int)t.length, t.ptr); 292 } 293 294 /***************************** 295 * Produce a user-readable comma separated string of the 296 * dependencies. 297 * Params: 298 * buf = write resulting string here 299 * vars = array from which to get the variable names 300 */ 301 void depsToBuf(ref OutBuffer buf, const VarDeclaration[] vars) 302 { 303 bool any = false; 304 foreach (i; 0 .. deps.length) 305 { 306 if (deps[i]) 307 { 308 if (any) 309 buf.writestring(", "); 310 buf.writestring(vars[i].toString()); 311 any = true; 312 } 313 } 314 } 315 } 316 317 318 /***************************************** 319 * Set the `.extra` field for LabelStatements in labtab[]. 320 */ 321 void setLabelStatementExtraFields(DsymbolTable labtab) 322 { 323 if (labtab) 324 foreach (keyValue; labtab.tab.asRange) 325 { 326 //printf(" KV: %s = %s\n", keyValue.key.toChars(), keyValue.value.toChars()); 327 auto label = cast(LabelDsymbol)keyValue.value; 328 if (label.statement) 329 label.statement.extra = cast(void*) new ObNode(null); 330 } 331 } 332 333 /***************************************** 334 * Convert statement into ObNodes. 335 */ 336 337 void toObNodes(ref ObNodes obnodes, Statement s) 338 { 339 ObNode* curblock = new ObNode(null); 340 obnodes.push(curblock); 341 342 void visit(Statement s, StmtState* stmtstate) 343 { 344 if (!s) 345 return; 346 347 ObNode* newNode() 348 { 349 return new ObNode(stmtstate.tryBlock); 350 } 351 352 ObNode* nextNodeIs(ObNode* ob) 353 { 354 obnodes.push(ob); 355 curblock = ob; 356 return ob; 357 } 358 359 ObNode* nextNode() 360 { 361 return nextNodeIs(newNode()); 362 } 363 364 ObNode* gotoNextNodeIs(ObNode* ob) 365 { 366 obnodes.push(ob); 367 curblock.succs.push(ob); 368 curblock = ob; 369 return ob; 370 } 371 372 // block_goto(blx, BCgoto, null) 373 ObNode* gotoNextNode() 374 { 375 return gotoNextNodeIs(newNode()); 376 } 377 378 /*** 379 * Doing a goto to dest 380 */ 381 ObNode* gotoDest(ObNode* dest) 382 { 383 curblock.succs.push(dest); 384 return nextNode(); 385 } 386 387 void visitExp(ExpStatement s) 388 { 389 curblock.obtype = ObType.goto_; 390 curblock.exp = s.exp; 391 gotoNextNode(); 392 } 393 394 void visitDtorExp(DtorExpStatement s) 395 { 396 visitExp(s); 397 } 398 399 void visitCompound(CompoundStatement s) 400 { 401 if (s.statements) 402 { 403 foreach (s2; *s.statements) 404 { 405 visit(s2, stmtstate); 406 } 407 } 408 } 409 410 void visitCompoundDeclaration(CompoundDeclarationStatement s) 411 { 412 visitCompound(s); 413 } 414 415 void visitUnrolledLoop(UnrolledLoopStatement s) 416 { 417 StmtState mystate = StmtState(stmtstate, s); 418 mystate.breakBlock = newNode(); 419 420 gotoNextNode(); 421 422 foreach (s2; *s.statements) 423 { 424 if (s2) 425 { 426 mystate.contBlock = newNode(); 427 428 visit(s2, &mystate); 429 430 gotoNextNodeIs(mystate.contBlock); 431 } 432 } 433 434 gotoNextNodeIs(mystate.breakBlock); 435 } 436 437 void visitScope(ScopeStatement s) 438 { 439 if (s.statement) 440 { 441 StmtState mystate = StmtState(stmtstate, s); 442 443 if (mystate.prev.ident) 444 mystate.ident = mystate.prev.ident; 445 446 visit(s.statement, &mystate); 447 448 if (mystate.breakBlock) 449 gotoNextNodeIs(mystate.breakBlock); 450 } 451 } 452 453 void visitDo(DoStatement s) 454 { 455 StmtState mystate = StmtState(stmtstate, s); 456 mystate.breakBlock = newNode(); 457 mystate.contBlock = newNode(); 458 459 auto bpre = curblock; 460 461 auto ob = newNode(); 462 obnodes.push(ob); 463 curblock.succs.push(ob); 464 curblock = ob; 465 bpre.succs.push(curblock); 466 467 mystate.contBlock.succs.push(curblock); 468 mystate.contBlock.succs.push(mystate.breakBlock); 469 470 visit(s._body, &mystate); 471 472 gotoNextNodeIs(mystate.contBlock); 473 mystate.contBlock.exp = s.condition; 474 nextNodeIs(mystate.breakBlock); 475 } 476 477 void visitFor(ForStatement s) 478 { 479 //printf("visit(ForStatement)) %u..%u\n", s.loc.linnum, s.endloc.linnum); 480 StmtState mystate = StmtState(stmtstate, s); 481 mystate.breakBlock = newNode(); 482 mystate.contBlock = newNode(); 483 484 visit(s._init, &mystate); 485 486 auto bcond = gotoNextNode(); 487 mystate.contBlock.succs.push(bcond); 488 489 if (s.condition) 490 { 491 bcond.exp = s.condition; 492 auto ob = newNode(); 493 obnodes.push(ob); 494 bcond.succs.push(ob); 495 bcond.succs.push(mystate.breakBlock); 496 curblock = ob; 497 } 498 else 499 { /* No conditional, it's a straight goto 500 */ 501 bcond.exp = s.condition; 502 bcond.succs.push(nextNode()); 503 } 504 505 visit(s._body, &mystate); 506 /* End of the body goes to the continue block 507 */ 508 curblock.succs.push(mystate.contBlock); 509 nextNodeIs(mystate.contBlock); 510 511 if (s.increment) 512 curblock.exp = s.increment; 513 514 /* The 'break' block follows the for statement. 515 */ 516 nextNodeIs(mystate.breakBlock); 517 } 518 519 void visitIf(IfStatement s) 520 { 521 StmtState mystate = StmtState(stmtstate, s); 522 523 // bexit is the block that gets control after this IfStatement is done 524 auto bexit = mystate.breakBlock ? mystate.breakBlock : newNode(); 525 526 curblock.exp = s.condition; 527 528 auto bcond = curblock; 529 gotoNextNode(); 530 531 visit(s.ifbody, &mystate); 532 curblock.succs.push(bexit); 533 534 if (s.elsebody) 535 { 536 bcond.succs.push(nextNode()); 537 538 visit(s.elsebody, &mystate); 539 540 gotoNextNodeIs(bexit); 541 } 542 else 543 { 544 bcond.succs.push(bexit); 545 nextNodeIs(bexit); 546 } 547 } 548 549 void visitSwitch(SwitchStatement s) 550 { 551 StmtState mystate = StmtState(stmtstate, s); 552 553 mystate.switchBlock = curblock; 554 555 /* Block for where "break" goes to 556 */ 557 mystate.breakBlock = newNode(); 558 559 /* Block for where "default" goes to. 560 * If there is a default statement, then that is where default goes. 561 * If not, then do: 562 * default: break; 563 * by making the default block the same as the break block. 564 */ 565 mystate.defaultBlock = s.sdefault ? newNode() : mystate.breakBlock; 566 567 const numcases = s.cases ? s.cases.dim : 0; 568 569 /* allocate a block for each case 570 */ 571 if (numcases) 572 foreach (cs; *s.cases) 573 { 574 cs.extra = cast(void*)newNode(); 575 } 576 577 curblock.exp = s.condition; 578 579 if (s.hasVars) 580 { /* Generate a sequence of if-then-else blocks for the cases. 581 */ 582 if (numcases) 583 foreach (cs; *s.cases) 584 { 585 auto ecase = newNode(); 586 obnodes.push(ecase); 587 ecase.exp = cs.exp; 588 curblock.succs.push(ecase); 589 590 auto cn = cast(ObNode*)cs.extra; 591 ecase.succs.push(cn); 592 ecase.succs.push(nextNode()); 593 } 594 595 /* The final 'else' clause goes to the default 596 */ 597 curblock.succs.push(mystate.defaultBlock); 598 nextNode(); 599 600 visit(s._body, &mystate); 601 602 /* Have the end of the switch body fall through to the block 603 * following the switch statement. 604 */ 605 gotoNextNodeIs(mystate.breakBlock); 606 return; 607 } 608 609 auto ob = newNode(); 610 obnodes.push(ob); 611 curblock = ob; 612 613 mystate.switchBlock.succs.push(mystate.defaultBlock); 614 615 visit(s._body, &mystate); 616 617 /* Have the end of the switch body fall through to the block 618 * following the switch statement. 619 */ 620 gotoNextNodeIs(mystate.breakBlock); 621 } 622 623 void visitCase(CaseStatement s) 624 { 625 auto cb = cast(ObNode*)s.extra; 626 cb.tryBlock = stmtstate.tryBlock; 627 auto bsw = stmtstate.getSwitchBlock(); 628 bsw.succs.push(cb); 629 gotoNextNodeIs(cb); 630 631 visit(s.statement, stmtstate); 632 } 633 634 void visitDefault(DefaultStatement s) 635 { 636 auto bdefault = stmtstate.getDefaultBlock; 637 bdefault.tryBlock = stmtstate.tryBlock; 638 gotoNextNodeIs(bdefault); 639 visit(s.statement, stmtstate); 640 } 641 642 void visitGotoDefault(GotoDefaultStatement s) 643 { 644 gotoDest(stmtstate.getDefaultBlock); 645 } 646 647 void visitGotoCase(GotoCaseStatement s) 648 { 649 gotoDest(cast(ObNode*)s.cs.extra); 650 } 651 652 void visitSwitchError(SwitchErrorStatement s) 653 { 654 curblock.obtype = ObType.throw_; 655 curblock.exp = s.exp; 656 657 nextNode(); 658 } 659 660 void visitReturn(ReturnStatement s) 661 { 662 //printf("visitReturn() %s\n", s.toChars()); 663 curblock.obtype = s.exp && s.exp.type.toBasetype().ty != Tvoid 664 ? ObType.retexp 665 : ObType.return_; 666 curblock.exp = s.exp; 667 668 nextNode(); 669 } 670 671 void visitBreak(BreakStatement s) 672 { 673 gotoDest(stmtstate.getBreakBlock(s.ident)); 674 } 675 676 void visitContinue(ContinueStatement s) 677 { 678 gotoDest(stmtstate.getContBlock(s.ident)); 679 } 680 681 void visitWith(WithStatement s) 682 { 683 visit(s._body, stmtstate); 684 } 685 686 void visitTryCatch(TryCatchStatement s) 687 { 688 /* tryblock 689 * body 690 * breakBlock 691 * catches 692 * breakBlock2 693 */ 694 695 StmtState mystate = StmtState(stmtstate, s); 696 mystate.breakBlock = newNode(); 697 698 auto tryblock = gotoNextNode(); 699 700 visit(s._body, &mystate); 701 702 gotoNextNodeIs(mystate.breakBlock); 703 704 // create new break block that follows all the catches 705 auto breakBlock2 = newNode(); 706 707 gotoDest(breakBlock2); 708 709 foreach (cs; *s.catches) 710 { 711 /* Each catch block is a successor to tryblock 712 * and the last block of try body 713 */ 714 StmtState catchState = StmtState(stmtstate, s); 715 716 auto bcatch = curblock; 717 tryblock.succs.push(bcatch); 718 mystate.breakBlock.succs.push(bcatch); 719 720 nextNode(); 721 722 visit(cs.handler, &catchState); 723 724 gotoDest(breakBlock2); 725 } 726 727 curblock.succs.push(breakBlock2); 728 obnodes.push(breakBlock2); 729 curblock = breakBlock2; 730 } 731 732 void visitTryFinally(TryFinallyStatement s) 733 { 734 /* Build this: 735 * 1 goto [2] 736 * 2 try_ [3] [5] [7] 737 * 3 body 738 * 4 goto [8] 739 * 5 finally_ [6] 740 * 6 finalbody 741 * 7 fend [8] 742 * 8 lastblock 743 */ 744 745 StmtState bodyState = StmtState(stmtstate, s); 746 747 auto b2 = gotoNextNode(); 748 b2.obtype = ObType.try_; 749 bodyState.tryBlock = b2; 750 751 gotoNextNode(); 752 753 visit(s._body, &bodyState); 754 755 auto b4 = gotoNextNode(); 756 757 auto b5 = newNode(); 758 b5.obtype = ObType.finally_; 759 nextNodeIs(b5); 760 gotoNextNode(); 761 762 StmtState finallyState = StmtState(stmtstate, s); 763 visit(s.finalbody, &finallyState); 764 765 auto b7 = gotoNextNode(); 766 b7.obtype = ObType.fend; 767 768 auto b8 = gotoNextNode(); 769 770 b2.succs.push(b5); 771 b2.succs.push(b7); 772 773 b4.succs.push(b8); 774 } 775 776 void visitThrow(ThrowStatement s) 777 { 778 curblock.obtype = ObType.throw_; 779 curblock.exp = s.exp; 780 nextNode(); 781 } 782 783 void visitGoto(GotoStatement s) 784 { 785 gotoDest(cast(ObNode*)s.label.statement.extra); 786 } 787 788 void visitLabel(LabelStatement s) 789 { 790 StmtState mystate = StmtState(stmtstate, s); 791 mystate.ident = s.ident; 792 793 auto ob = cast(ObNode*)s.extra; 794 ob.tryBlock = mystate.tryBlock; 795 visit(s.statement, &mystate); 796 } 797 798 final switch (s.stmt) 799 { 800 case STMT.Exp: visitExp(s.isExpStatement()); break; 801 case STMT.DtorExp: visitDtorExp(s.isDtorExpStatement()); break; 802 case STMT.Compound: visitCompound(s.isCompoundStatement()); break; 803 case STMT.CompoundDeclaration: visitCompoundDeclaration(s.isCompoundDeclarationStatement()); break; 804 case STMT.UnrolledLoop: visitUnrolledLoop(s.isUnrolledLoopStatement()); break; 805 case STMT.Scope: visitScope(s.isScopeStatement()); break; 806 case STMT.Do: visitDo(s.isDoStatement()); break; 807 case STMT.For: visitFor(s.isForStatement()); break; 808 case STMT.If: visitIf(s.isIfStatement()); break; 809 case STMT.Switch: visitSwitch(s.isSwitchStatement()); break; 810 case STMT.Case: visitCase(s.isCaseStatement()); break; 811 case STMT.Default: visitDefault(s.isDefaultStatement()); break; 812 case STMT.GotoDefault: visitGotoDefault(s.isGotoDefaultStatement()); break; 813 case STMT.GotoCase: visitGotoCase(s.isGotoCaseStatement()); break; 814 case STMT.SwitchError: visitSwitchError(s.isSwitchErrorStatement()); break; 815 case STMT.Return: visitReturn(s.isReturnStatement()); break; 816 case STMT.Break: visitBreak(s.isBreakStatement()); break; 817 case STMT.Continue: visitContinue(s.isContinueStatement()); break; 818 case STMT.With: visitWith(s.isWithStatement()); break; 819 case STMT.TryCatch: visitTryCatch(s.isTryCatchStatement()); break; 820 case STMT.TryFinally: visitTryFinally(s.isTryFinallyStatement()); break; 821 case STMT.Throw: visitThrow(s.isThrowStatement()); break; 822 case STMT.Goto: visitGoto(s.isGotoStatement()); break; 823 case STMT.Label: visitLabel(s.isLabelStatement()); break; 824 825 case STMT.CompoundAsm: 826 case STMT.Asm: 827 case STMT.InlineAsm: 828 case STMT.GccAsm: 829 830 case STMT.Pragma: 831 case STMT.Import: 832 case STMT.ScopeGuard: 833 case STMT.Error: 834 break; // ignore these 835 836 case STMT.Foreach: 837 case STMT.ForeachRange: 838 case STMT.Debug: 839 case STMT.CaseRange: 840 case STMT.StaticForeach: 841 case STMT.StaticAssert: 842 case STMT.Conditional: 843 case STMT.While: 844 case STMT.Forwarding: 845 case STMT.Compile: 846 case STMT.Peel: 847 case STMT.Synchronized: 848 debug printf("s: %s\n", s.toChars()); 849 assert(0); // should have been rewritten 850 } 851 } 852 853 StmtState stmtstate; 854 visit(s, &stmtstate); 855 curblock.obtype = ObType.return_; 856 857 static if (0) 858 { 859 printf("toObNodes()\n"); 860 printf("------- before ----------\n"); 861 numberNodes(obnodes); 862 foreach (ob; obnodes) ob.print(); 863 printf("-------------------------\n"); 864 } 865 866 assert(stmtstate.breakBlock is null); 867 assert(stmtstate.contBlock is null); 868 assert(stmtstate.switchBlock is null); 869 assert(stmtstate.defaultBlock is null); 870 assert(stmtstate.tryBlock is null); 871 } 872 873 /*************************************************** 874 * Insert finally block calls when doing a goto from 875 * inside a try block to outside. 876 * Done after blocks are generated because then we know all 877 * the edges of the graph, but before the pred's are computed. 878 * Params: 879 * obnodes = graph of the function 880 */ 881 882 void insertFinallyBlockCalls(ref ObNodes obnodes) 883 { 884 ObNode* bcret = null; 885 ObNode* bcretexp = null; 886 887 enum log = false; 888 889 static if (log) 890 { 891 printf("insertFinallyBlockCalls()\n"); 892 printf("------- before ----------\n"); 893 numberNodes(obnodes); 894 foreach (ob; obnodes) ob.print(); 895 printf("-------------------------\n"); 896 } 897 898 foreach (ob; obnodes) 899 { 900 if (!ob.tryBlock) 901 continue; 902 903 switch (ob.obtype) 904 { 905 case ObType.return_: 906 // Rewrite into a ObType.goto_ => ObType.return_ 907 if (!bcret) 908 { 909 bcret = new ObNode(); 910 bcret.obtype = ob.obtype; 911 } 912 ob.obtype = ObType.goto_; 913 ob.succs.push(bcret); 914 goto case_goto; 915 916 case ObType.retexp: 917 // Rewrite into a ObType.goto_ => ObType.retexp 918 if (!bcretexp) 919 { 920 bcretexp = new ObNode(); 921 bcretexp.obtype = ob.obtype; 922 } 923 ob.obtype = ObType.goto_; 924 ob.succs.push(bcretexp); 925 goto case_goto; 926 927 case ObType.goto_: 928 if (ob.succs.length != 1) 929 break; 930 931 case_goto: 932 { 933 auto target = ob.succs[0]; // destination of goto 934 ob.succs.setDim(0); 935 auto lasttry = target.tryBlock; 936 auto blast = ob; 937 for (auto bt = ob.tryBlock; bt != lasttry; bt = bt.tryBlock) 938 { 939 assert(bt.obtype == ObType.try_); 940 auto bf = bt.succs[1]; 941 assert(bf.obtype == ObType.finally_); 942 auto bfend = bt.succs[2]; 943 assert(bfend.obtype == ObType.fend); 944 945 if (!blast.succs.contains(bf.succs[0])) 946 blast.succs.push(bf.succs[0]); 947 948 blast = bfend; 949 } 950 if (!blast.succs.contains(target)) 951 blast.succs.push(target); 952 953 break; 954 } 955 956 default: 957 break; 958 } 959 } 960 if (bcret) 961 obnodes.push(bcret); 962 if (bcretexp) 963 obnodes.push(bcretexp); 964 965 static if (log) 966 { 967 printf("------- after ----------\n"); 968 numberNodes(obnodes); 969 foreach (ob; obnodes) ob.print(); 970 printf("-------------------------\n"); 971 } 972 } 973 974 /*************************************************** 975 * Remove try-finally scaffolding. 976 * Params: 977 * obnodes = nodes for the function 978 */ 979 980 void insertFinallyBlockGotos(ref ObNodes obnodes) 981 { 982 /* Remove all the try_, finally_, lpad and ret nodes. 983 * Actually, just make them into no-ops. 984 */ 985 foreach (ob; obnodes) 986 { 987 ob.tryBlock = null; 988 switch (ob.obtype) 989 { 990 case ObType.try_: 991 ob.obtype = ObType.goto_; 992 ob.succs.remove(2); // remove fend 993 ob.succs.remove(1); // remove finally_ 994 break; 995 996 case ObType.finally_: 997 ob.obtype = ObType.goto_; 998 break; 999 1000 case ObType.fend: 1001 ob.obtype = ObType.goto_; 1002 break; 1003 1004 default: 1005 break; 1006 } 1007 } 1008 } 1009 1010 /********************************* 1011 * Set the `index` field of each ObNode 1012 * to its index in the `obnodes[]` array. 1013 */ 1014 void numberNodes(ref ObNodes obnodes) 1015 { 1016 //printf("numberNodes()\n"); 1017 foreach (i, ob; obnodes) 1018 { 1019 //printf("ob = %d, %p\n", i, ob); 1020 ob.index = cast(uint)i; 1021 } 1022 1023 // Verify that nodes do not appear more than once in obnodes[] 1024 debug 1025 foreach (i, ob; obnodes) 1026 { 1027 assert(ob.index == cast(uint)i); 1028 } 1029 } 1030 1031 1032 /********************************* 1033 * Remove unreachable nodes and compress 1034 * them out of obnodes[]. 1035 * Params: 1036 * obnodes = array of nodes 1037 */ 1038 void removeUnreachable(ref ObNodes obnodes) 1039 { 1040 if (!obnodes.length) 1041 return; 1042 1043 /* Mark all nodes as unreachable, 1044 * temporarilly reusing ObNode.index 1045 */ 1046 foreach (ob; obnodes) 1047 ob.index = 0; 1048 1049 /* Recursively mark ob and all its successors as reachable 1050 */ 1051 static void mark(ObNode* ob) 1052 { 1053 ob.index = 1; 1054 foreach (succ; ob.succs) 1055 { 1056 if (!succ.index) 1057 mark(succ); 1058 } 1059 } 1060 1061 mark(obnodes[0]); // first node is entry point 1062 1063 /* Remove unreachable nodes by shifting the remainder left 1064 */ 1065 size_t j = 1; 1066 foreach (i; 1 .. obnodes.length) 1067 { 1068 if (obnodes[i].index) 1069 { 1070 if (i != j) 1071 obnodes[j] = obnodes[i]; 1072 ++j; 1073 } 1074 else 1075 { 1076 obnodes[i].destroy(); 1077 } 1078 } 1079 obnodes.setDim(j); 1080 } 1081 1082 1083 1084 /************************************* 1085 * Compute predecessors. 1086 */ 1087 void computePreds(ref ObNodes obnodes) 1088 { 1089 foreach (ob; obnodes) 1090 { 1091 foreach (succ; ob.succs) 1092 { 1093 succ.preds.push(ob); 1094 } 1095 } 1096 } 1097 1098 /******************************* 1099 * Are we interested in tracking variable `v`? 1100 */ 1101 bool isTrackableVar(VarDeclaration v) 1102 { 1103 //printf("isTrackableVar() %s\n", v.toChars()); 1104 auto tb = v.type.toBasetype(); 1105 1106 /* Assume class references are managed by the GC, 1107 * don't need to track them 1108 */ 1109 if (tb.ty == Tclass) 1110 return false; 1111 1112 /* Assume types with a destructor are doing their own tracking, 1113 * such as being a ref counted type 1114 */ 1115 if (v.needsScopeDtor()) 1116 return false; 1117 1118 /* Not tracking function parameters that are not mutable 1119 */ 1120 if (v.storage_class & STC.parameter && !tb.hasPointersToMutableFields()) 1121 return false; 1122 1123 /* Not tracking global variables 1124 */ 1125 return !v.isDataseg(); 1126 } 1127 1128 /******************************* 1129 * Are we interested in tracking this expression? 1130 * Returns: 1131 * variable if so, null if not 1132 */ 1133 VarDeclaration isTrackableVarExp(Expression e) 1134 { 1135 if (auto ve = e.isVarExp()) 1136 { 1137 if (auto v = ve.var.isVarDeclaration()) 1138 if (isTrackableVar(v)) 1139 return v; 1140 } 1141 return null; 1142 } 1143 1144 1145 /************** 1146 * Find the pointer variable declarations in this function, 1147 * and fill `vars` with them. 1148 * Params: 1149 * funcdecl = function we are in 1150 * vars = array to fill in 1151 */ 1152 void collectVars(FuncDeclaration funcdecl, out VarDeclarations vars) 1153 { 1154 enum log = false; 1155 if (log) 1156 printf("----------------collectVars()---------------\n"); 1157 1158 if (funcdecl.parameters) 1159 foreach (v; (*funcdecl.parameters)[]) 1160 { 1161 if (isTrackableVar(v)) 1162 vars.push(v); 1163 } 1164 1165 void dgVar(VarDeclaration v) 1166 { 1167 if (isTrackableVar(v)) 1168 vars.push(v); 1169 } 1170 1171 void dgExp(Expression e) 1172 { 1173 foreachVar(e, &dgVar); 1174 } 1175 1176 foreachExpAndVar(funcdecl.fbody, &dgExp, &dgVar); 1177 1178 static if (log) 1179 { 1180 foreach (i, v; vars[]) 1181 { 1182 printf("vars[%d] = %s\n", cast(int)i, v.toChars()); 1183 } 1184 } 1185 } 1186 1187 /*********************************** 1188 * Allocate BitArrays in PtrVarState. 1189 * Can be allocated much more efficiently by subdividing a single 1190 * large array of bits 1191 */ 1192 void allocDeps(PtrVarState[] pvss) 1193 { 1194 //printf("allocDeps()\n"); 1195 foreach (ref pvs; pvss) 1196 { 1197 pvs.deps.length = pvss.length; 1198 } 1199 } 1200 1201 1202 /************************************** 1203 * Allocate state variables foreach node. 1204 */ 1205 void allocStates(ref ObState obstate) 1206 { 1207 //printf("---------------allocStates()------------------\n"); 1208 const vlen = obstate.vars.length; 1209 PtrVarState* p = cast(PtrVarState*) mem.xcalloc(obstate.nodes.length * 3 * vlen, PtrVarState.sizeof); 1210 obstate.varPool = p[0 .. obstate.nodes.length * 3 * vlen]; 1211 foreach (i, ob; obstate.nodes) 1212 { 1213 //printf(" [%d]\n", cast(int)i); 1214 // ob.kill.length = obstate.vars.length; 1215 // ob.comb.length = obstate.vars.length; 1216 ob.gen = p[0 .. vlen]; p += vlen; 1217 ob.input = p[0 .. vlen]; p += vlen; 1218 ob.output = p[0 .. vlen]; p += vlen; 1219 1220 allocDeps(ob.gen); 1221 allocDeps(ob.input); 1222 allocDeps(ob.output); 1223 } 1224 } 1225 1226 /****************************** 1227 * Does v meet the definiton of a `Borrowed` pointer? 1228 * Returns: 1229 * true if it does 1230 */ 1231 bool isBorrowedPtr(VarDeclaration v) 1232 { 1233 return v.isScope() && !v.isowner && v.type.nextOf().isMutable(); 1234 } 1235 1236 /****************************** 1237 * Does v meet the definiton of a `Readonly` pointer? 1238 * Returns: 1239 * true if it does 1240 */ 1241 bool isReadonlyPtr(VarDeclaration v) 1242 { 1243 return v.isScope() && !v.type.nextOf().isMutable(); 1244 } 1245 1246 /*************************************** 1247 * Compute the gen vector for ob. 1248 */ 1249 void genKill(ref ObState obstate, ObNode* ob) 1250 { 1251 enum log = false; 1252 if (log) 1253 printf("-----------computeGenKill()-----------\n"); 1254 1255 /*************** 1256 * Assigning result of expression `e` to variable `v`. 1257 */ 1258 void dgWriteVar(ObNode* ob, VarDeclaration v, Expression e, bool initializer) 1259 { 1260 if (log) 1261 printf("dgWriteVar() %s := %s %d\n", v.toChars(), e.toChars(), initializer); 1262 const vi = obstate.vars.find(v); 1263 assert(vi != size_t.max); 1264 PtrVarState* pvs = &ob.gen[vi]; 1265 readVar(ob, vi, true, ob.gen); 1266 if (e) 1267 { 1268 if (isBorrowedPtr(v)) 1269 pvs.state = PtrState.Borrowed; 1270 else if (isReadonlyPtr(v)) 1271 pvs.state = PtrState.Readonly; 1272 else 1273 pvs.state = PtrState.Owner; 1274 pvs.deps.zero(); 1275 1276 EscapeByResults er; 1277 escapeByValue(e, &er, true); 1278 bool any = false; // if any variables are assigned to v 1279 1280 void by(VarDeclaration r) 1281 { 1282 const ri = obstate.vars.find(r); 1283 if (ri != size_t.max && ri != vi) 1284 { 1285 pvs.deps[ri] = true; // v took from r 1286 auto pvsr = &ob.gen[ri]; 1287 any = true; 1288 1289 if (isBorrowedPtr(v)) 1290 { 1291 // v is borrowing from r 1292 pvs.state = PtrState.Borrowed; 1293 } 1294 else if (isReadonlyPtr(v)) 1295 { 1296 pvs.state = PtrState.Readonly; 1297 } 1298 else 1299 { 1300 // move r to v, which "consumes" r 1301 pvsr.state = PtrState.Undefined; 1302 pvsr.deps.zero(); 1303 } 1304 } 1305 } 1306 1307 foreach (VarDeclaration v2; er.byvalue) 1308 by(v2); 1309 foreach (VarDeclaration v2; er.byref) 1310 by(v2); 1311 1312 /* Make v an Owner for initializations like: 1313 * scope v = malloc(); 1314 */ 1315 if (initializer && !any && isBorrowedPtr(v)) 1316 { 1317 v.isowner = true; 1318 pvs.state = PtrState.Owner; 1319 } 1320 } 1321 else 1322 { 1323 if (isBorrowedPtr(v)) 1324 pvs.state = PtrState.Borrowed; 1325 else if (isReadonlyPtr(v)) 1326 pvs.state = PtrState.Readonly; 1327 else 1328 pvs.state = PtrState.Owner; 1329 pvs.deps.zero(); 1330 } 1331 } 1332 1333 void dgReadVar(const ref Loc loc, ObNode* ob, VarDeclaration v, bool mutable) 1334 { 1335 if (log) 1336 printf("dgReadVar() %s %d\n", v.toChars(), mutable); 1337 const vi = obstate.vars.find(v); 1338 assert(vi != size_t.max); 1339 readVar(ob, vi, mutable, ob.gen); 1340 } 1341 1342 void foreachExp(ObNode* ob, Expression e) 1343 { 1344 extern (C++) final class ExpWalker : Visitor 1345 { 1346 alias visit = typeof(super).visit; 1347 extern (D) void delegate(ObNode*, VarDeclaration, Expression, bool) dgWriteVar; 1348 extern (D) void delegate(const ref Loc loc, ObNode* ob, VarDeclaration v, bool mutable) dgReadVar; 1349 ObNode* ob; 1350 ObState* obstate; 1351 1352 extern (D) this(void delegate(ObNode*, VarDeclaration, Expression, bool) dgWriteVar, 1353 void delegate(const ref Loc loc, ObNode* ob, VarDeclaration v, bool mutable) dgReadVar, 1354 ObNode* ob, ref ObState obstate) 1355 { 1356 this.dgWriteVar = dgWriteVar; 1357 this.dgReadVar = dgReadVar; 1358 this.ob = ob; 1359 this.obstate = &obstate; 1360 } 1361 1362 override void visit(Expression e) 1363 { 1364 //printf("[%s] %s: %s\n", e.loc.toChars(), Token.toChars(e.op), e.toChars()); 1365 //assert(0); 1366 } 1367 1368 void visitAssign(AssignExp ae, bool initializer) 1369 { 1370 ae.e2.accept(this); 1371 if (auto ve = ae.e1.isVarExp()) 1372 { 1373 if (auto v = ve.var.isVarDeclaration()) 1374 if (isTrackableVar(v)) 1375 dgWriteVar(ob, v, ae.e2, initializer); 1376 } 1377 else 1378 ae.e1.accept(this); 1379 } 1380 1381 override void visit(AssignExp ae) 1382 { 1383 visitAssign(ae, false); 1384 } 1385 1386 override void visit(DeclarationExp e) 1387 { 1388 void Dsymbol_visit(Dsymbol s) 1389 { 1390 if (auto vd = s.isVarDeclaration()) 1391 { 1392 s = s.toAlias(); 1393 if (s != vd) 1394 return Dsymbol_visit(s); 1395 if (!isTrackableVar(vd)) 1396 return; 1397 1398 if (!(vd._init && vd._init.isVoidInitializer())) 1399 { 1400 auto ei = vd._init ? vd._init.isExpInitializer() : null; 1401 if (ei) 1402 visitAssign(cast(AssignExp)ei.exp, true); 1403 else 1404 dgWriteVar(ob, vd, null, false); 1405 } 1406 } 1407 else if (auto td = s.isTupleDeclaration()) 1408 { 1409 foreach (o; *td.objects) 1410 { 1411 if (auto eo = o.isExpression()) 1412 { 1413 if (auto se = eo.isDsymbolExp()) 1414 { 1415 Dsymbol_visit(se.s); 1416 } 1417 } 1418 } 1419 } 1420 } 1421 1422 Dsymbol_visit(e.declaration); 1423 } 1424 1425 override void visit(VarExp ve) 1426 { 1427 //printf("VarExp: %s\n", ve.toChars()); 1428 if (auto v = ve.var.isVarDeclaration()) 1429 if (isTrackableVar(v)) 1430 { 1431 dgReadVar(ve.loc, ob, v, isMutableRef(ve.type)); 1432 } 1433 } 1434 1435 override void visit(CallExp ce) 1436 { 1437 //printf("CallExp() %s\n", ce.toChars()); 1438 ce.e1.accept(this); 1439 auto t = ce.e1.type.toBasetype(); 1440 auto tf = t.isTypeFunction(); 1441 if (!tf) 1442 { 1443 assert(t.ty == Tdelegate); 1444 tf = t.nextOf().isTypeFunction(); 1445 assert(tf); 1446 } 1447 1448 // j=1 if _arguments[] is first argument 1449 const int j = tf.isDstyleVariadic(); 1450 bool hasOut; 1451 const varStackSave = obstate.varStack.length; 1452 1453 foreach (const i, arg; (*ce.arguments)[]) 1454 { 1455 if (i - j < tf.parameterList.length && 1456 i >= j) 1457 { 1458 Parameter p = tf.parameterList[i - j]; 1459 auto pt = p.type.toBasetype(); 1460 1461 EscapeByResults er; 1462 escapeByValue(arg, &er, true); 1463 1464 if (!(p.storageClass & STC.out_ && arg.isVarExp())) 1465 arg.accept(this); 1466 1467 void by(VarDeclaration v) 1468 { 1469 if (!isTrackableVar(v)) 1470 return; 1471 1472 const vi = obstate.vars.find(v); 1473 if (vi == size_t.max) 1474 return; 1475 1476 if (p.storageClass & STC.out_) 1477 { 1478 /// initialize 1479 hasOut = true; 1480 makeUndefined(vi, ob.gen); 1481 } 1482 else if (p.storageClass & STC.scope_) 1483 { 1484 // borrow 1485 obstate.varStack.push(vi); 1486 obstate.mutableStack.push(isMutableRef(pt)); 1487 } 1488 else 1489 { 1490 // move (i.e. consume arg) 1491 makeUndefined(vi, ob.gen); 1492 } 1493 } 1494 1495 foreach (VarDeclaration v2; er.byvalue) 1496 by(v2); 1497 foreach (VarDeclaration v2; er.byref) 1498 by(v2); 1499 } 1500 else // variadic args 1501 { 1502 arg.accept(this); 1503 1504 EscapeByResults er; 1505 escapeByValue(arg, &er, true); 1506 1507 void byv(VarDeclaration v) 1508 { 1509 if (!isTrackableVar(v)) 1510 return; 1511 1512 const vi = obstate.vars.find(v); 1513 if (vi == size_t.max) 1514 return; 1515 1516 if (tf.parameterList.stc & STC.scope_) 1517 { 1518 // borrow 1519 obstate.varStack.push(vi); 1520 obstate.mutableStack.push(isMutableRef(arg.type) && 1521 !(tf.parameterList.stc & (STC.const_ | STC.immutable_))); 1522 } 1523 else 1524 // move (i.e. consume arg) 1525 makeUndefined(vi, ob.gen); 1526 } 1527 1528 foreach (VarDeclaration v2; er.byvalue) 1529 byv(v2); 1530 foreach (VarDeclaration v2; er.byref) 1531 byv(v2); 1532 } 1533 } 1534 1535 /* Do a dummy 'read' of each variable passed to the function, 1536 * to detect O/B errors 1537 */ 1538 assert(obstate.varStack.length == obstate.mutableStack.length); 1539 foreach (i; varStackSave .. obstate.varStack.length) 1540 { 1541 const vi = obstate.varStack[i]; 1542 // auto pvs = &ob.gen[vi]; 1543 auto v = obstate.vars[vi]; 1544 //if (pvs.state == PtrState.Undefined) 1545 //v.error(ce.loc, "is Undefined, cannot pass to function"); 1546 1547 dgReadVar(ce.loc, ob, v, obstate.mutableStack[i]); 1548 } 1549 1550 /* Pop off stack all variables for this function call 1551 */ 1552 obstate.varStack.setDim(varStackSave); 1553 obstate.mutableStack.setDim(varStackSave); 1554 1555 if (hasOut) 1556 // Initialization of out's only happens after the function call 1557 foreach (const i, arg; (*ce.arguments)[]) 1558 { 1559 if (i - j < tf.parameterList.length && 1560 i >= j) 1561 { 1562 Parameter p = tf.parameterList[i - j]; 1563 if (p.storageClass & STC.out_) 1564 { 1565 if (auto v = isTrackableVarExp(arg)) 1566 dgWriteVar(ob, v, null, true); 1567 } 1568 } 1569 } 1570 } 1571 1572 override void visit(SymOffExp e) 1573 { 1574 if (auto v = e.var.isVarDeclaration()) 1575 if (isTrackableVar(v)) 1576 { 1577 dgReadVar(e.loc, ob, v, isMutableRef(e.type)); 1578 } 1579 } 1580 1581 override void visit(LogicalExp e) 1582 { 1583 e.e1.accept(this); 1584 1585 const vlen = obstate.vars.length; 1586 auto p = cast(PtrVarState*)mem.xcalloc(vlen, PtrVarState.sizeof); 1587 PtrVarState[] gen1 = p[0 .. vlen]; 1588 foreach (i, ref pvs; gen1) 1589 { 1590 pvs = ob.gen[i]; 1591 } 1592 1593 e.e2.accept(this); 1594 1595 // Merge gen1 into ob.gen 1596 foreach (i; 0 .. vlen) 1597 { 1598 ob.gen[i].combine(gen1[i], i, ob.gen); 1599 } 1600 1601 mem.xfree(p); // should free .deps too 1602 } 1603 1604 override void visit(CondExp e) 1605 { 1606 e.econd.accept(this); 1607 1608 const vlen = obstate.vars.length; 1609 auto p = cast(PtrVarState*)mem.xcalloc(vlen, PtrVarState.sizeof); 1610 PtrVarState[] gen1 = p[0 .. vlen]; 1611 foreach (i, ref pvs; gen1) 1612 { 1613 pvs = ob.gen[i]; 1614 } 1615 1616 e.e1.accept(this); 1617 1618 // Swap gen1 with ob.gen 1619 foreach (i; 0 .. vlen) 1620 { 1621 gen1[i].deps.swap(ob.gen[i].deps); 1622 const state = gen1[i].state; 1623 gen1[i].state = ob.gen[i].state; 1624 ob.gen[i].state = state; 1625 } 1626 1627 e.e2.accept(this); 1628 1629 /* xxx1 is the state from expression e1, ob.xxx is the state from e2. 1630 * Merge xxx1 into ob.xxx to get the state from `e`. 1631 */ 1632 foreach (i; 0 .. vlen) 1633 { 1634 ob.gen[i].combine(gen1[i], i, ob.gen); 1635 } 1636 1637 mem.xfree(p); // should free .deps too 1638 } 1639 1640 override void visit(AddrExp e) 1641 { 1642 /* Taking the address of struct literal is normally not 1643 * allowed, but CTFE can generate one out of a new expression, 1644 * but it'll be placed in static data so no need to check it. 1645 */ 1646 if (e.e1.op != TOK.structLiteral) 1647 e.e1.accept(this); 1648 } 1649 1650 override void visit(UnaExp e) 1651 { 1652 e.e1.accept(this); 1653 } 1654 1655 override void visit(BinExp e) 1656 { 1657 e.e1.accept(this); 1658 e.e2.accept(this); 1659 } 1660 1661 override void visit(ArrayLiteralExp e) 1662 { 1663 Type tb = e.type.toBasetype(); 1664 if (tb.ty == Tsarray || tb.ty == Tarray) 1665 { 1666 if (e.basis) 1667 e.basis.accept(this); 1668 foreach (el; *e.elements) 1669 { 1670 if (el) 1671 el.accept(this); 1672 } 1673 } 1674 } 1675 1676 override void visit(StructLiteralExp e) 1677 { 1678 if (e.elements) 1679 { 1680 foreach (ex; *e.elements) 1681 { 1682 if (ex) 1683 ex.accept(this); 1684 } 1685 } 1686 } 1687 1688 override void visit(AssocArrayLiteralExp e) 1689 { 1690 if (e.keys) 1691 { 1692 foreach (i, key; *e.keys) 1693 { 1694 if (key) 1695 key.accept(this); 1696 if (auto value = (*e.values)[i]) 1697 value.accept(this); 1698 } 1699 } 1700 } 1701 1702 override void visit(NewExp e) 1703 { 1704 if (e.arguments) 1705 { 1706 foreach (ex; *e.arguments) 1707 { 1708 if (ex) 1709 ex.accept(this); 1710 } 1711 } 1712 } 1713 1714 override void visit(SliceExp e) 1715 { 1716 e.e1.accept(this); 1717 if (e.lwr) 1718 e.lwr.accept(this); 1719 if (e.upr) 1720 e.upr.accept(this); 1721 } 1722 } 1723 1724 if (e) 1725 { 1726 scope ExpWalker ew = new ExpWalker(&dgWriteVar, &dgReadVar, ob, obstate); 1727 e.accept(ew); 1728 } 1729 } 1730 1731 foreachExp(ob, ob.exp); 1732 } 1733 1734 /*************************************** 1735 * Determine the state of a variable based on 1736 * its type and storage class. 1737 */ 1738 PtrState toPtrState(VarDeclaration v) 1739 { 1740 /* pointer to mutable: Owner 1741 * pointer to mutable, scope: Borrowed 1742 * pointer to const: Owner 1743 * pointer to const, scope: Readonly 1744 * ref: Borrowed 1745 * const ref: Readonly 1746 */ 1747 1748 auto t = v.type; 1749 if (v.isRef()) 1750 { 1751 return t.hasMutableFields() ? PtrState.Borrowed : PtrState.Readonly; 1752 } 1753 if (v.isScope()) 1754 { 1755 return t.hasPointersToMutableFields() ? PtrState.Borrowed : PtrState.Readonly; 1756 } 1757 else 1758 return PtrState.Owner; 1759 } 1760 1761 /********************************** 1762 * Does type `t` contain any pointers to mutable? 1763 */ 1764 bool hasPointersToMutableFields(Type t) 1765 { 1766 auto tb = t.toBasetype(); 1767 if (!tb.isMutable()) 1768 return false; 1769 if (auto tsa = tb.isTypeSArray()) 1770 { 1771 return tsa.nextOf().hasPointersToMutableFields(); 1772 } 1773 if (auto ts = tb.isTypeStruct()) 1774 { 1775 foreach (v; ts.sym.fields) 1776 { 1777 if (v.isRef()) 1778 { 1779 if (v.type.hasMutableFields()) 1780 return true; 1781 } 1782 else if (v.type.hasPointersToMutableFields()) 1783 return true; 1784 } 1785 return false; 1786 } 1787 auto tbn = tb.nextOf(); 1788 return tbn && tbn.hasMutableFields(); 1789 } 1790 1791 /******************************** 1792 * Does type `t` have any mutable fields? 1793 */ 1794 bool hasMutableFields(Type t) 1795 { 1796 auto tb = t.toBasetype(); 1797 if (!tb.isMutable()) 1798 return false; 1799 if (auto tsa = tb.isTypeSArray()) 1800 { 1801 return tsa.nextOf().hasMutableFields(); 1802 } 1803 if (auto ts = tb.isTypeStruct()) 1804 { 1805 foreach (v; ts.sym.fields) 1806 { 1807 if (v.type.hasMutableFields()) 1808 return true; 1809 } 1810 return false; 1811 } 1812 return true; 1813 } 1814 1815 1816 1817 /*************************************** 1818 * Do the data flow analysis (i.e. compute the input[] 1819 * and output[] vectors for each ObNode). 1820 */ 1821 void doDataFlowAnalysis(ref ObState obstate) 1822 { 1823 enum log = false; 1824 if (log) 1825 { 1826 printf("-----------------doDataFlowAnalysis()-------------------------\n"); 1827 foreach (ob; obstate.nodes) ob.print(); 1828 printf("------------------------------------------\n"); 1829 } 1830 1831 if (!obstate.nodes.length) 1832 return; 1833 1834 auto startnode = obstate.nodes[0]; 1835 assert(startnode.preds.length == 0); 1836 1837 /* Set opening state `input[]` for first node 1838 */ 1839 foreach (i, ref ps; startnode.input) 1840 { 1841 auto v = obstate.vars[i]; 1842 auto state = toPtrState(v); 1843 if (v.isParameter()) 1844 { 1845 if (v.isOut()) 1846 state = PtrState.Undefined; 1847 else if (v.isBorrowedPtr()) 1848 state = PtrState.Borrowed; 1849 else 1850 state = PtrState.Owner; 1851 } 1852 else 1853 state = PtrState.Undefined; 1854 ps.state = state; 1855 ps.deps.zero(); 1856 startnode.gen[i] = ps; 1857 } 1858 1859 /* Set all output[]s to Initial 1860 */ 1861 foreach (ob; obstate.nodes[]) 1862 { 1863 foreach (ref ps; ob.output) 1864 { 1865 ps.state = PtrState.Initial; 1866 ps.deps.zero(); 1867 } 1868 } 1869 1870 const vlen = obstate.vars.length; 1871 PtrVarState pvs; 1872 pvs.deps.length = vlen; 1873 int counter = 0; 1874 bool changes; 1875 do 1876 { 1877 changes = false; 1878 assert(++counter <= 1000); // should converge, but don't hang if it doesn't 1879 foreach (ob; obstate.nodes[]) 1880 { 1881 /* Construct ob.gen[] by combining the .output[]s of each ob.preds[] 1882 * and set ob.input[] to the same state 1883 */ 1884 if (ob != startnode) 1885 { 1886 assert(ob.preds.length); 1887 1888 foreach (i; 0 .. vlen) 1889 { 1890 ob.gen[i] = ob.preds[0].output[i]; 1891 } 1892 1893 foreach (j; 1 .. ob.preds.length) 1894 { 1895 foreach (i; 0 .. vlen) 1896 { 1897 ob.gen[i].combine(ob.preds[j].output[i], i, ob.gen); 1898 } 1899 } 1900 1901 /* Set ob.input[] to ob.gen[], 1902 * if any changes were made we'll have to do another iteration 1903 */ 1904 foreach (i; 0 .. vlen) 1905 { 1906 if (ob.gen[i] != ob.input[i]) 1907 { 1908 ob.input[i] = ob.gen[i]; 1909 changes = true; 1910 } 1911 } 1912 } 1913 1914 /* Compute gen[] for node ob 1915 */ 1916 genKill(obstate, ob); 1917 1918 foreach (i; 0 .. vlen) 1919 { 1920 if (ob.gen[i] != ob.output[i]) 1921 { 1922 ob.output[i] = ob.gen[i]; 1923 changes = true; 1924 } 1925 } 1926 } 1927 } while (changes); 1928 1929 static if (log) 1930 { 1931 foreach (obi, ob; obstate.nodes) 1932 { 1933 printf("%d: %s\n", obi, ob.exp ? ob.exp.toChars() : "".ptr); 1934 printf(" input:\n"); 1935 foreach (i, ref pvs2; ob.input[]) 1936 { 1937 printf(" %s: ", obstate.vars[i].toChars()); pvs2.print(obstate.vars[]); 1938 } 1939 1940 printf(" gen:\n"); 1941 foreach (i, ref pvs2; ob.gen[]) 1942 { 1943 printf(" %s: ", obstate.vars[i].toChars()); pvs2.print(obstate.vars[]); 1944 } 1945 printf(" output:\n"); 1946 foreach (i, ref pvs2; ob.output[]) 1947 { 1948 printf(" %s: ", obstate.vars[i].toChars()); pvs2.print(obstate.vars[]); 1949 } 1950 } 1951 printf("\n"); 1952 } 1953 } 1954 1955 1956 /*************************************** 1957 * Check for Ownership/Borrowing errors. 1958 */ 1959 void checkObErrors(ref ObState obstate) 1960 { 1961 enum log = false; 1962 if (log) 1963 printf("------------checkObErrors()----------\n"); 1964 1965 void dgWriteVar(ObNode* ob, PtrVarState[] cpvs, VarDeclaration v, Expression e) 1966 { 1967 if (log) printf("dgWriteVar(v:%s, e:%s)\n", v.toChars(), e ? e.toChars() : "null"); 1968 const vi = obstate.vars.find(v); 1969 assert(vi != size_t.max); 1970 PtrVarState* pvs = &cpvs[vi]; 1971 readVar(ob, vi, true, cpvs); 1972 if (e) 1973 { 1974 if (isBorrowedPtr(v)) 1975 pvs.state = PtrState.Borrowed; 1976 else if (isReadonlyPtr(v)) 1977 pvs.state = PtrState.Readonly; 1978 else 1979 pvs.state = PtrState.Owner; 1980 pvs.deps.zero(); 1981 1982 EscapeByResults er; 1983 escapeByValue(e, &er, true); 1984 1985 void by(VarDeclaration r) // `v` = `r` 1986 { 1987 //printf(" by(%s)\n", r.toChars()); 1988 const ri = obstate.vars.find(r); 1989 if (ri == size_t.max) 1990 return; 1991 1992 with (PtrState) 1993 { 1994 pvs.deps[ri] = true; // v took from r 1995 auto pvsr = &cpvs[ri]; 1996 1997 if (pvsr.state == Undefined) 1998 { 1999 v.error(e.loc, "is reading from `%s` which is Undefined", r.toChars()); 2000 } 2001 else if (isBorrowedPtr(v)) // v is going to borrow from r 2002 { 2003 if (pvsr.state == Readonly) 2004 v.error(e.loc, "is borrowing from `%s` which is Readonly", r.toChars()); 2005 2006 pvs.state = Borrowed; 2007 } 2008 else if (isReadonlyPtr(v)) 2009 { 2010 pvs.state = Readonly; 2011 } 2012 else 2013 { 2014 // move from r to v 2015 pvsr.state = Undefined; 2016 pvsr.deps.zero(); 2017 } 2018 } 2019 } 2020 2021 foreach (VarDeclaration v2; er.byvalue) 2022 by(v2); 2023 foreach (VarDeclaration v2; er.byref) 2024 by(v2); 2025 } 2026 else 2027 { 2028 if (isBorrowedPtr(v)) 2029 pvs.state = PtrState.Borrowed; 2030 else if (isReadonlyPtr(v)) 2031 pvs.state = PtrState.Readonly; 2032 else 2033 pvs.state = PtrState.Owner; 2034 pvs.deps.zero(); 2035 } 2036 } 2037 2038 void dgReadVar(const ref Loc loc, ObNode* ob, VarDeclaration v, bool mutable, PtrVarState[] gen) 2039 { 2040 if (log) printf("dgReadVar() %s\n", v.toChars()); 2041 const vi = obstate.vars.find(v); 2042 assert(vi != size_t.max); 2043 auto pvs = &gen[vi]; 2044 if (pvs.state == PtrState.Undefined) 2045 v.error(loc, "has undefined state and cannot be read"); 2046 2047 readVar(ob, vi, mutable, gen); 2048 } 2049 2050 void foreachExp(ObNode* ob, Expression e, PtrVarState[] cpvs) 2051 { 2052 extern (C++) final class ExpWalker : Visitor 2053 { 2054 alias visit = typeof(super).visit; 2055 extern (D) void delegate(ObNode*, PtrVarState[], VarDeclaration, Expression) dgWriteVar; 2056 extern (D) void delegate(const ref Loc loc, ObNode* ob, VarDeclaration v, bool mutable, PtrVarState[]) dgReadVar; 2057 PtrVarState[] cpvs; 2058 ObNode* ob; 2059 ObState* obstate; 2060 2061 extern (D) this(void delegate(const ref Loc loc, ObNode* ob, VarDeclaration v, bool mutable, PtrVarState[]) dgReadVar, 2062 void delegate(ObNode*, PtrVarState[], VarDeclaration, Expression) dgWriteVar, 2063 PtrVarState[] cpvs, ObNode* ob, ref ObState obstate) 2064 { 2065 this.dgReadVar = dgReadVar; 2066 this.dgWriteVar = dgWriteVar; 2067 this.cpvs = cpvs; 2068 this.ob = ob; 2069 this.obstate = &obstate; 2070 } 2071 2072 override void visit(Expression) 2073 { 2074 } 2075 2076 override void visit(DeclarationExp e) 2077 { 2078 void Dsymbol_visit(Dsymbol s) 2079 { 2080 if (auto vd = s.isVarDeclaration()) 2081 { 2082 s = s.toAlias(); 2083 if (s != vd) 2084 return Dsymbol_visit(s); 2085 if (!isTrackableVar(vd)) 2086 return; 2087 2088 if (vd._init && vd._init.isVoidInitializer()) 2089 return; 2090 2091 auto ei = vd._init ? vd._init.isExpInitializer() : null; 2092 if (ei) 2093 { 2094 auto e = ei.exp; 2095 if (auto ae = e.isConstructExp()) 2096 e = ae.e2; 2097 dgWriteVar(ob, cpvs, vd, e); 2098 } 2099 else 2100 dgWriteVar(ob, cpvs, vd, null); 2101 } 2102 else if (auto td = s.isTupleDeclaration()) 2103 { 2104 foreach (o; *td.objects) 2105 { 2106 if (auto eo = o.isExpression()) 2107 { 2108 if (auto se = eo.isDsymbolExp()) 2109 { 2110 Dsymbol_visit(se.s); 2111 } 2112 } 2113 } 2114 } 2115 } 2116 2117 Dsymbol_visit(e.declaration); 2118 } 2119 2120 override void visit(AssignExp ae) 2121 { 2122 ae.e2.accept(this); 2123 if (auto ve = ae.e1.isVarExp()) 2124 { 2125 if (auto v = ve.var.isVarDeclaration()) 2126 if (isTrackableVar(v)) 2127 dgWriteVar(ob, cpvs, v, ae.e2); 2128 } 2129 else 2130 ae.e1.accept(this); 2131 } 2132 2133 override void visit(VarExp ve) 2134 { 2135 //printf("VarExp: %s\n", ve.toChars()); 2136 if (auto v = ve.var.isVarDeclaration()) 2137 if (isTrackableVar(v)) 2138 { 2139 dgReadVar(ve.loc, ob, v, isMutableRef(ve.type), cpvs); 2140 } 2141 } 2142 2143 override void visit(CallExp ce) 2144 { 2145 //printf("CallExp(%s)\n", ce.toChars()); 2146 ce.e1.accept(this); 2147 auto t = ce.e1.type.toBasetype(); 2148 auto tf = t.isTypeFunction(); 2149 if (!tf) 2150 { 2151 assert(t.ty == Tdelegate); 2152 tf = t.nextOf().isTypeFunction(); 2153 assert(tf); 2154 } 2155 2156 // j=1 if _arguments[] is first argument 2157 const int j = tf.isDstyleVariadic(); 2158 bool hasOut; 2159 const varStackSave = obstate.varStack.length; 2160 2161 foreach (const i, arg; (*ce.arguments)[]) 2162 { 2163 if (i - j < tf.parameterList.length && 2164 i >= j) 2165 { 2166 Parameter p = tf.parameterList[i - j]; 2167 auto pt = p.type.toBasetype(); 2168 2169 if (!(p.storageClass & STC.out_ && arg.isVarExp())) 2170 arg.accept(this); 2171 2172 EscapeByResults er; 2173 escapeByValue(arg, &er, true); 2174 2175 void by(VarDeclaration v) 2176 { 2177 if (!isTrackableVar(v)) 2178 return; 2179 2180 const vi = obstate.vars.find(v); 2181 if (vi == size_t.max) 2182 return; 2183 2184 auto pvs = &cpvs[vi]; 2185 2186 if (p.storageClass & STC.out_) 2187 { 2188 /// initialize 2189 hasOut = true; 2190 makeUndefined(vi, cpvs); 2191 } 2192 else if (p.storageClass & STC.scope_) 2193 { 2194 // borrow 2195 obstate.varStack.push(vi); 2196 obstate.mutableStack.push(isMutableRef(pt)); 2197 } 2198 else 2199 { 2200 // move (i.e. consume arg) 2201 if (pvs.state != PtrState.Owner) 2202 v.error(arg.loc, "is not Owner, cannot consume its value"); 2203 makeUndefined(vi, cpvs); 2204 } 2205 } 2206 2207 foreach (VarDeclaration v2; er.byvalue) 2208 by(v2); 2209 foreach (VarDeclaration v2; er.byref) 2210 by(v2); 2211 } 2212 else // variadic args 2213 { 2214 arg.accept(this); 2215 2216 EscapeByResults er; 2217 escapeByValue(arg, &er, true); 2218 2219 void byv(VarDeclaration v) 2220 { 2221 if (!isTrackableVar(v)) 2222 return; 2223 2224 const vi = obstate.vars.find(v); 2225 if (vi == size_t.max) 2226 return; 2227 2228 auto pvs = &cpvs[vi]; 2229 2230 if (tf.parameterList.stc & STC.scope_) 2231 { 2232 // borrow 2233 obstate.varStack.push(vi); 2234 obstate.mutableStack.push(isMutableRef(arg.type) && 2235 !(tf.parameterList.stc & (STC.const_ | STC.immutable_))); 2236 } 2237 else 2238 { 2239 // move (i.e. consume arg) 2240 if (pvs.state != PtrState.Owner) 2241 v.error(arg.loc, "is not Owner, cannot consume its value"); 2242 makeUndefined(vi, cpvs); 2243 } 2244 } 2245 2246 foreach (VarDeclaration v2; er.byvalue) 2247 byv(v2); 2248 foreach (VarDeclaration v2; er.byref) 2249 byv(v2); 2250 } 2251 } 2252 2253 /* Do a dummy 'read' of each variable passed to the function, 2254 * to detect O/B errors 2255 */ 2256 assert(obstate.varStack.length == obstate.mutableStack.length); 2257 foreach (i; varStackSave .. obstate.varStack.length) 2258 { 2259 const vi = obstate.varStack[i]; 2260 auto pvs = &cpvs[vi]; 2261 auto v = obstate.vars[vi]; 2262 //if (pvs.state == PtrState.Undefined) 2263 //v.error(ce.loc, "is Undefined, cannot pass to function"); 2264 2265 dgReadVar(ce.loc, ob, v, obstate.mutableStack[i], cpvs); 2266 2267 if (pvs.state == PtrState.Owner) 2268 { 2269 for (size_t k = i + 1; k < obstate.varStack.length;++k) 2270 { 2271 const vk = obstate.varStack[k]; 2272 if (vk == vi) 2273 { 2274 if (obstate.mutableStack[vi] || obstate.mutableStack[vk]) 2275 { 2276 v.error(ce.loc, "is passed as Owner more than once"); 2277 break; // no need to continue 2278 } 2279 } 2280 } 2281 } 2282 } 2283 2284 /* Pop off stack all variables for this function call 2285 */ 2286 obstate.varStack.setDim(varStackSave); 2287 obstate.mutableStack.setDim(varStackSave); 2288 2289 if (hasOut) 2290 // Initialization of out's only happens after the function call 2291 foreach (const i, arg; (*ce.arguments)[]) 2292 { 2293 if (i - j < tf.parameterList.length && 2294 i >= j) 2295 { 2296 Parameter p = tf.parameterList[i - j]; 2297 if (p.storageClass & STC.out_) 2298 { 2299 if (auto v = isTrackableVarExp(arg)) 2300 { 2301 dgWriteVar(ob, cpvs, v, null); 2302 } 2303 } 2304 } 2305 } 2306 } 2307 2308 override void visit(SymOffExp e) 2309 { 2310 if (auto v = e.var.isVarDeclaration()) 2311 if (isTrackableVar(v)) 2312 { 2313 dgReadVar(e.loc, ob, v, isMutableRef(e.type), cpvs); 2314 } 2315 } 2316 2317 override void visit(LogicalExp e) 2318 { 2319 e.e1.accept(this); 2320 2321 const vlen = obstate.vars.length; 2322 auto p = cast(PtrVarState*)mem.xcalloc(vlen, PtrVarState.sizeof); 2323 PtrVarState[] out1 = p[0 .. vlen]; 2324 foreach (i, ref pvs; out1) 2325 { 2326 pvs = cpvs[i]; 2327 } 2328 2329 e.e2.accept(this); 2330 2331 // Merge out1 into cpvs 2332 foreach (i; 0 .. vlen) 2333 { 2334 cpvs[i].combine(out1[i], i, cpvs); 2335 } 2336 2337 mem.xfree(p); // should free .deps too 2338 } 2339 2340 override void visit(CondExp e) 2341 { 2342 e.econd.accept(this); 2343 2344 const vlen = obstate.vars.length; 2345 auto p = cast(PtrVarState*)mem.xcalloc(vlen, PtrVarState.sizeof); 2346 PtrVarState[] out1 = p[0 .. vlen]; 2347 foreach (i, ref pvs; out1) 2348 { 2349 pvs = cpvs[i]; 2350 } 2351 2352 e.e1.accept(this); 2353 2354 // Swap out1 with cpvs 2355 foreach (i; 0 .. vlen) 2356 { 2357 out1[i].deps.swap(cpvs[i].deps); 2358 const state = out1[i].state; 2359 out1[i].state = cpvs[i].state; 2360 cpvs[i].state = state; 2361 } 2362 2363 e.e2.accept(this); 2364 2365 // Merge out1 into cpvs 2366 foreach (i; 0 .. vlen) 2367 { 2368 cpvs[i].combine(out1[i], i, cpvs); 2369 } 2370 2371 mem.xfree(p); // should free .deps too 2372 } 2373 2374 override void visit(AddrExp e) 2375 { 2376 /* Taking the address of struct literal is normally not 2377 * allowed, but CTFE can generate one out of a new expression, 2378 * but it'll be placed in static data so no need to check it. 2379 */ 2380 if (e.e1.op != TOK.structLiteral) 2381 e.e1.accept(this); 2382 } 2383 2384 override void visit(UnaExp e) 2385 { 2386 e.e1.accept(this); 2387 } 2388 2389 override void visit(BinExp e) 2390 { 2391 e.e1.accept(this); 2392 e.e2.accept(this); 2393 } 2394 2395 override void visit(ArrayLiteralExp e) 2396 { 2397 Type tb = e.type.toBasetype(); 2398 if (tb.ty == Tsarray || tb.ty == Tarray) 2399 { 2400 if (e.basis) 2401 e.basis.accept(this); 2402 foreach (el; *e.elements) 2403 { 2404 if (el) 2405 el.accept(this); 2406 } 2407 } 2408 } 2409 2410 override void visit(StructLiteralExp e) 2411 { 2412 if (e.elements) 2413 { 2414 foreach (ex; *e.elements) 2415 { 2416 if (ex) 2417 ex.accept(this); 2418 } 2419 } 2420 } 2421 2422 override void visit(AssocArrayLiteralExp e) 2423 { 2424 if (e.keys) 2425 { 2426 foreach (i, key; *e.keys) 2427 { 2428 if (key) 2429 key.accept(this); 2430 if (auto value = (*e.values)[i]) 2431 value.accept(this); 2432 } 2433 } 2434 } 2435 2436 override void visit(NewExp e) 2437 { 2438 if (e.arguments) 2439 { 2440 foreach (ex; *e.arguments) 2441 { 2442 if (ex) 2443 ex.accept(this); 2444 } 2445 } 2446 } 2447 2448 override void visit(SliceExp e) 2449 { 2450 e.e1.accept(this); 2451 if (e.lwr) 2452 e.lwr.accept(this); 2453 if (e.upr) 2454 e.upr.accept(this); 2455 } 2456 } 2457 2458 if (e) 2459 { 2460 scope ExpWalker ew = new ExpWalker(&dgReadVar, &dgWriteVar, cpvs, ob, obstate); 2461 e.accept(ew); 2462 } 2463 } 2464 2465 const vlen = obstate.vars.length; 2466 auto p = cast(PtrVarState*)mem.xcalloc(vlen, PtrVarState.sizeof); 2467 PtrVarState[] cpvs = p[0 .. vlen]; 2468 foreach (ref pvs; cpvs) 2469 pvs.deps.length = vlen; 2470 2471 foreach (obi, ob; obstate.nodes) 2472 { 2473 static if (log) 2474 { 2475 printf("%d: %s\n", obi, ob.exp ? ob.exp.toChars() : "".ptr); 2476 printf(" input:\n"); 2477 foreach (i, ref pvs; ob.input[]) 2478 { 2479 printf(" %s: ", obstate.vars[i].toChars()); pvs.print(obstate.vars[]); 2480 } 2481 } 2482 2483 /* Combine the .output[]s of each ob.preds[] looking for errors 2484 */ 2485 if (obi) // skip startnode 2486 { 2487 assert(ob.preds.length); 2488 2489 foreach (i; 0 .. vlen) 2490 { 2491 ob.gen[i] = ob.preds[0].output[i]; 2492 } 2493 2494 foreach (j; 1 .. ob.preds.length) 2495 { 2496 foreach (i; 0 .. vlen) 2497 { 2498 auto pvs1 = &ob.gen[i]; 2499 auto pvs2 = &ob.preds[j].output[i]; 2500 const s1 = pvs1.state; 2501 const s2 = pvs2.state; 2502 if (s1 != s2 && (s1 == PtrState.Owner || s2 == PtrState.Owner)) 2503 { 2504 auto v = obstate.vars[i]; 2505 v.error(ob.exp ? ob.exp.loc : v.loc, "is both %s and %s", s1.toChars(), s2.toChars()); 2506 } 2507 pvs1.combine(*pvs2, i, ob.gen); 2508 } 2509 } 2510 } 2511 2512 /* Prolly should use gen[] instead of cpvs[], or vice versa 2513 */ 2514 foreach (i, ref pvs; ob.input) 2515 { 2516 cpvs[i] = pvs; 2517 } 2518 2519 foreachExp(ob, ob.exp, cpvs); 2520 2521 static if (log) 2522 { 2523 printf(" cpvs:\n"); 2524 foreach (i, ref pvs; cpvs[]) 2525 { 2526 printf(" %s: ", obstate.vars[i].toChars()); pvs.print(obstate.vars[]); 2527 } 2528 printf(" output:\n"); 2529 foreach (i, ref pvs; ob.output[]) 2530 { 2531 printf(" %s: ", obstate.vars[i].toChars()); pvs.print(obstate.vars[]); 2532 } 2533 } 2534 2535 if (ob.obtype == ObType.retexp) 2536 { 2537 EscapeByResults er; 2538 escapeByValue(ob.exp, &er, true); 2539 2540 void by(VarDeclaration r) // `r` is the rvalue 2541 { 2542 const ri = obstate.vars.find(r); 2543 if (ri == size_t.max) 2544 return; 2545 with (PtrState) 2546 { 2547 auto pvsr = &ob.output[ri]; 2548 switch (pvsr.state) 2549 { 2550 case Undefined: 2551 r.error(ob.exp.loc, "is returned but is Undefined"); 2552 break; 2553 2554 case Owner: 2555 pvsr.state = Undefined; // returning a pointer "consumes" it 2556 break; 2557 2558 case Borrowed: 2559 case Readonly: 2560 break; 2561 2562 default: 2563 assert(0); 2564 } 2565 } 2566 } 2567 2568 foreach (VarDeclaration v2; er.byvalue) 2569 by(v2); 2570 foreach (VarDeclaration v2; er.byref) 2571 by(v2); 2572 } 2573 2574 if (ob.obtype == ObType.return_ || ob.obtype == ObType.retexp) 2575 { 2576 foreach (i, ref pvs; ob.output[]) 2577 { 2578 //printf("%s: ", obstate.vars[i].toChars()); pvs.print(obstate.vars[]); 2579 if (pvs.state == PtrState.Owner) 2580 { 2581 auto v = obstate.vars[i]; 2582 if (v.type.hasPointers()) 2583 v.error(v.loc, "is left dangling at return"); 2584 } 2585 } 2586 } 2587 } 2588 } 2589 2590 2591 /*************************************************** 2592 * Read from variable vi. 2593 * The beginning of the 'scope' of a variable is when it is first read. 2594 * Hence, when a read is done, instead of when assignment to the variable is done, the O/B rules are enforced. 2595 * (Also called "non-lexical scoping".) 2596 */ 2597 void readVar(ObNode* ob, const size_t vi, bool mutable, PtrVarState[] gen) 2598 { 2599 //printf("readVar(v%d)\n", cast(int)vi); 2600 auto pvso = &gen[vi]; 2601 switch (pvso.state) 2602 { 2603 case PtrState.Owner: 2604 //printf("t: %s\n", t.toChars()); 2605 if (mutable) // if mutable read 2606 { 2607 makeChildrenUndefined(vi, gen); 2608 } 2609 else // const read 2610 { 2611 // If there's a Borrow child, set that to Undefined 2612 foreach (di; 0 .. gen.length) 2613 { 2614 auto pvsd = &gen[di]; 2615 if (pvsd.deps[vi] && pvsd.state == PtrState.Borrowed) // if di borrowed vi 2616 { 2617 makeUndefined(di, gen); 2618 } 2619 } 2620 } 2621 break; 2622 2623 case PtrState.Borrowed: 2624 /* All children become Undefined 2625 */ 2626 makeChildrenUndefined(vi, gen); 2627 break; 2628 2629 case PtrState.Readonly: 2630 break; 2631 2632 case PtrState.Undefined: 2633 break; 2634 2635 default: 2636 break; 2637 } 2638 } 2639 2640 /******************** 2641 * Recursively make Undefined all who list vi as a dependency 2642 */ 2643 void makeChildrenUndefined(size_t vi, PtrVarState[] gen) 2644 { 2645 //printf("makeChildrenUndefined(%d)\n", vi); 2646 foreach (di; 0 .. gen.length) 2647 { 2648 if (gen[di].deps[vi]) // if di depends on vi 2649 { 2650 if (gen[di].state != PtrState.Undefined) 2651 { 2652 gen[di].state = PtrState.Undefined; // set this first to avoid infinite recursion 2653 makeChildrenUndefined(di, gen); 2654 gen[di].deps.zero(); 2655 } 2656 } 2657 } 2658 } 2659 2660 2661 /******************** 2662 * Recursively make Undefined vi undefined and all who list vi as a dependency 2663 */ 2664 void makeUndefined(size_t vi, PtrVarState[] gen) 2665 { 2666 auto pvs = &gen[vi]; 2667 pvs.state = PtrState.Undefined; // set this first to avoid infinite recursion 2668 makeChildrenUndefined(vi, gen); 2669 pvs.deps.zero(); 2670 } 2671 2672 /************************* 2673 * Is type `t` a reference to a const or a reference to a mutable? 2674 */ 2675 bool isMutableRef(Type t) 2676 { 2677 auto tb = t.toBasetype(); 2678 return (tb.nextOf() ? tb.nextOf() : tb).isMutable(); 2679 }