optdfa.pas 37 KB

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991001011021031041051061071081091101111121131141151161171181191201211221231241251261271281291301311321331341351361371381391401411421431441451461471481491501511521531541551561571581591601611621631641651661671681691701711721731741751761771781791801811821831841851861871881891901911921931941951961971981992002012022032042052062072082092102112122132142152162172182192202212222232242252262272282292302312322332342352362372382392402412422432442452462472482492502512522532542552562572582592602612622632642652662672682692702712722732742752762772782792802812822832842852862872882892902912922932942952962972982993003013023033043053063073083093103113123133143153163173183193203213223233243253263273283293303313323333343353363373383393403413423433443453463473483493503513523533543553563573583593603613623633643653663673683693703713723733743753763773783793803813823833843853863873883893903913923933943953963973983994004014024034044054064074084094104114124134144154164174184194204214224234244254264274284294304314324334344354364374384394404414424434444454464474484494504514524534544554564574584594604614624634644654664674684694704714724734744754764774784794804814824834844854864874884894904914924934944954964974984995005015025035045055065075085095105115125135145155165175185195205215225235245255265275285295305315325335345355365375385395405415425435445455465475485495505515525535545555565575585595605615625635645655665675685695705715725735745755765775785795805815825835845855865875885895905915925935945955965975985996006016026036046056066076086096106116126136146156166176186196206216226236246256266276286296306316326336346356366376386396406416426436446456466476486496506516526536546556566576586596606616626636646656666676686696706716726736746756766776786796806816826836846856866876886896906916926936946956966976986997007017027037047057067077087097107117127137147157167177187197207217227237247257267277287297307317327337347357367377387397407417427437447457467477487497507517527537547557567577587597607617627637647657667677687697707717727737747757767777787797807817827837847857867877887897907917927937947957967977987998008018028038048058068078088098108118128138148158168178188198208218228238248258268278288298308318328338348358368378388398408418428438448458468478488498508518528538548558568578588598608618628638648658668678688698708718728738748758768778788798808818828838848858868878888898908918928938948958968978988999009019029039049059069079089099109119129139149159169179189199209219229239249259269279289299309319329339349359369379389399409419429439449459469479489499509519529539549559569579589599609619629639649659669679689699709719729739749759769779789799809819829839849859869879889899909919929939949959969979989991000100110021003100410051006100710081009
  1. {
  2. DFA
  3. Copyright (c) 2007 by Florian Klaempfl
  4. This program is free software; you can redistribute it and/or modify
  5. it under the terms of the GNU General Public License as published by
  6. the Free Software Foundation; either version 2 of the License, or
  7. (at your option) any later version.
  8. This program is distributed in the hope that it will be useful,
  9. but WITHOUT ANY WARRANTY; without even the implied warranty of
  10. MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
  11. GNU General Public License for more details.
  12. You should have received a copy of the GNU General Public License
  13. along with this program; if not, write to the Free Software
  14. Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  15. ****************************************************************************
  16. }
  17. { $define DEBUG_DFA}
  18. { $define EXTDEBUG_DFA}
  19. { this unit implements routines to perform dfa }
  20. unit optdfa;
  21. {$i fpcdefs.inc}
  22. interface
  23. uses
  24. node,optutils;
  25. type
  26. TDFABuilder = class
  27. protected
  28. procedure CreateLifeInfo(node : tnode;map : TIndexedNodeSet);
  29. public
  30. resultnode : tnode;
  31. nodemap : TIndexedNodeSet;
  32. { reset all dfa info, this is required before creating dfa info
  33. if the tree has been changed without updating dfa }
  34. procedure resetdfainfo(node : tnode);
  35. procedure createdfainfo(node : tnode);
  36. procedure redodfainfo(node : tnode);
  37. destructor destroy;override;
  38. end;
  39. procedure CheckAndWarn(code : tnode;nodetosearch : tnode);
  40. implementation
  41. uses
  42. globtype,constexp,
  43. verbose,
  44. symconst,symdef,symsym,
  45. defutil,
  46. procinfo,
  47. nutils,htypechk,
  48. nbas,nflw,ncal,nset,nld,nadd,
  49. optbase;
  50. (*
  51. function initnodes(var n:tnode; arg: pointer) : foreachnoderesult;
  52. begin
  53. { node worth to add? }
  54. if (node_complexity(n)>1) and (tstoreddef(n.resultdef).is_intregable or tstoreddef(n.resultdef).is_fpuregable) then
  55. begin
  56. plists(arg)^.nodelist.Add(n);
  57. plists(arg)^.locationlist.Add(@n);
  58. result:=fen_false;
  59. end
  60. else
  61. result:=fen_norecurse_false;
  62. end;
  63. *)
  64. {
  65. x:=f; read: [f]
  66. while x do read: []
  67. a:=b; read: [a,b,d] def: [a] life: read*def=[a]
  68. c:=d; read: [a,d] def: [a,c] life: read*def=[a]
  69. e:=a; read: [a] def: [a,c,e] life: read*def=[a]
  70. function f(b,d,x : type) : type;
  71. begin
  72. while x do alive: b,d,x
  73. begin
  74. a:=b; alive: b,d,x
  75. c:=d; alive: a,d,x
  76. e:=a+c; alive: a,c,x
  77. dec(x); alive: c,e,x
  78. end;
  79. result:=c+e; alive: c,e
  80. end; alive: result
  81. }
  82. type
  83. tdfainfo = record
  84. use : PDFASet;
  85. def : PDFASet;
  86. map : TIndexedNodeSet
  87. end;
  88. pdfainfo = ^tdfainfo;
  89. function AddDefUse(var n: tnode; arg: pointer): foreachnoderesult;
  90. begin
  91. case n.nodetype of
  92. tempcreaten:
  93. begin
  94. if assigned(ttempcreatenode(n).tempinfo^.tempinitcode) then
  95. begin
  96. pdfainfo(arg)^.map.Add(n);
  97. DFASetInclude(pdfainfo(arg)^.def^,n.optinfo^.index);
  98. end;
  99. end;
  100. temprefn,
  101. loadn:
  102. begin
  103. pdfainfo(arg)^.map.Add(n);
  104. if nf_modify in n.flags then
  105. begin
  106. DFASetInclude(pdfainfo(arg)^.use^,n.optinfo^.index);
  107. DFASetInclude(pdfainfo(arg)^.def^,n.optinfo^.index)
  108. end
  109. else if nf_write in n.flags then
  110. DFASetInclude(pdfainfo(arg)^.def^,n.optinfo^.index)
  111. else
  112. DFASetInclude(pdfainfo(arg)^.use^,n.optinfo^.index);
  113. end;
  114. else
  115. ;
  116. end;
  117. result:=fen_false;
  118. end;
  119. function ResetProcessing(var n: tnode; arg: pointer): foreachnoderesult;
  120. begin
  121. exclude(n.flags,nf_processing);
  122. { dfa works only on normalized trees, so do not recurse into expressions, because
  123. ResetProcessing eats a signififcant amount of time of CheckAndWarn
  124. the following set contains (hopefully) most of the expression nodes }
  125. if n.nodetype in [calln,inlinen,assignn,callparan,andn,addn,orn,subn,muln,divn,slashn,notn,equaln,unequaln,gtn,ltn,lten,gten,loadn,
  126. typeconvn,vecn,subscriptn,addrn,derefn] then
  127. result:=fen_norecurse_false
  128. else
  129. result:=fen_false;
  130. end;
  131. function ResetDFA(var n: tnode; arg: pointer): foreachnoderesult;
  132. begin
  133. if assigned(n.optinfo) then
  134. begin
  135. with n.optinfo^ do
  136. begin
  137. life:=nil;
  138. def:=nil;
  139. use:=nil;
  140. defsum:=nil;
  141. end;
  142. end;
  143. result:=fen_false;
  144. end;
  145. procedure TDFABuilder.CreateLifeInfo(node : tnode;map : TIndexedNodeSet);
  146. var
  147. changed : boolean;
  148. procedure CreateInfo(node : tnode);
  149. { update life entry of a node with l, set changed if this changes
  150. life info for the node
  151. }
  152. procedure updatelifeinfo(n : tnode;const l : TDFASet);
  153. var
  154. b : boolean;
  155. begin
  156. b:=DFASetNotEqual(l,n.optinfo^.life);
  157. {$ifdef DEBUG_DFA}
  158. if not(changed) and b then
  159. begin
  160. writeln('Another DFA pass caused by: ',nodetype2str[n.nodetype],'(',n.fileinfo.line,',',n.fileinfo.column,')');
  161. write(' Life info set was: ');PrintDFASet(Output,n.optinfo^.life);writeln;
  162. write(' Life info set will be: ');PrintDFASet(Output,l);writeln;
  163. end;
  164. {$endif DEBUG_DFA}
  165. changed:=changed or b;
  166. n.optinfo^.life:=l;
  167. end;
  168. procedure calclife(n : tnode);
  169. var
  170. l : TDFASet;
  171. begin
  172. if assigned(n.successor) then
  173. begin
  174. { ensure we can access optinfo }
  175. DFASetDiff(l,n.successor.optinfo^.life,n.optinfo^.def);
  176. DFASetIncludeSet(l,n.optinfo^.use);
  177. DFASetIncludeSet(l,n.optinfo^.life);
  178. end
  179. else
  180. begin
  181. l:=n.optinfo^.use;
  182. DFASetIncludeSet(l,n.optinfo^.life);
  183. end;
  184. updatelifeinfo(n,l);
  185. end;
  186. var
  187. dfainfo : tdfainfo;
  188. l : TDFASet;
  189. save: TDFASet;
  190. lv, hv: TConstExprInt;
  191. i : longint;
  192. counteruse_after_loop : boolean;
  193. begin
  194. if node=nil then
  195. exit;
  196. { ensure we've already optinfo set }
  197. node.allocoptinfo;
  198. if nf_processing in node.flags then
  199. exit;
  200. include(node.flags,nf_processing);
  201. if assigned(node.successor) then
  202. CreateInfo(node.successor);
  203. {$ifdef EXTDEBUG_DFA}
  204. writeln('Handling: ',nodetype2str[node.nodetype],'(',node.fileinfo.line,',',node.fileinfo.column,')');
  205. {$endif EXTDEBUG_DFA}
  206. { life:=succesorlive-definition+use }
  207. case node.nodetype of
  208. whilerepeatn:
  209. begin
  210. { analyze the loop condition }
  211. if not(assigned(node.optinfo^.def)) and
  212. not(assigned(node.optinfo^.use)) then
  213. begin
  214. dfainfo.use:[email protected]^.use;
  215. dfainfo.def:[email protected]^.def;
  216. dfainfo.map:=map;
  217. foreachnodestatic(pm_postprocess,twhilerepeatnode(node).left,@AddDefUse,@dfainfo);
  218. end;
  219. { NB: this node should typically have empty def set }
  220. if assigned(node.successor) then
  221. DFASetDiff(l,node.successor.optinfo^.life,node.optinfo^.def)
  222. else if assigned(resultnode) then
  223. DFASetDiff(l,resultnode.optinfo^.life,node.optinfo^.def)
  224. else
  225. l:=nil;
  226. { for repeat..until, node use set in included at the end of loop }
  227. if not (lnf_testatbegin in twhilerepeatnode(node).loopflags) then
  228. DFASetIncludeSet(l,node.optinfo^.use);
  229. DFASetIncludeSet(l,node.optinfo^.life);
  230. save:=node.optinfo^.life;
  231. { to process body correctly, we need life info in place (because
  232. whilerepeatnode is successor of its body). }
  233. node.optinfo^.life:=l;
  234. { now process the body }
  235. CreateInfo(twhilerepeatnode(node).right);
  236. { restore, to prevent infinite recursion via changed flag }
  237. node.optinfo^.life:=save;
  238. { for while loops, node use set is included at the beginning of loop }
  239. l:=twhilerepeatnode(node).right.optinfo^.life;
  240. if lnf_testatbegin in twhilerepeatnode(node).loopflags then
  241. begin
  242. DFASetIncludeSet(l,node.optinfo^.use);
  243. { ... loop body could be skipped, so include life info of the successsor node }
  244. if assigned(node.successor) then
  245. DFASetIncludeSet(l,node.successor.optinfo^.life);
  246. end;
  247. UpdateLifeInfo(node,l);
  248. { ... and a second iteration for fast convergence }
  249. CreateInfo(twhilerepeatnode(node).right);
  250. end;
  251. forn:
  252. begin
  253. {
  254. left: loopvar
  255. right: from
  256. t1: to
  257. t2: body
  258. }
  259. node.allocoptinfo;
  260. tfornode(node).loopiteration.allocoptinfo;
  261. if not(assigned(node.optinfo^.def)) and
  262. not(assigned(node.optinfo^.use)) then
  263. begin
  264. dfainfo.use:[email protected]^.use;
  265. dfainfo.def:[email protected]^.def;
  266. dfainfo.map:=map;
  267. foreachnodestatic(pm_postprocess,tfornode(node).left,@AddDefUse,@dfainfo);
  268. foreachnodestatic(pm_postprocess,tfornode(node).right,@AddDefUse,@dfainfo);
  269. foreachnodestatic(pm_postprocess,tfornode(node).t1,@AddDefUse,@dfainfo);
  270. end;
  271. { create life for the body }
  272. CreateInfo(tfornode(node).t2);
  273. { is the counter living after the loop?
  274. if left is a record element, it might not be tracked by dfa, so
  275. optinfo might not be assigned
  276. }
  277. counteruse_after_loop:=assigned(tfornode(node).left.optinfo) and assigned(node.successor) and
  278. DFASetIn(node.successor.optinfo^.life,tfornode(node).left.optinfo^.index);
  279. if counteruse_after_loop then
  280. begin
  281. { if yes, then we should warn }
  282. { !!!!!! }
  283. end
  284. else
  285. Include(tfornode(node).loopflags,lnf_dont_mind_loopvar_on_exit);
  286. { first update the dummy node }
  287. { get the life of the loop block }
  288. l:=copy(tfornode(node).t2.optinfo^.life);
  289. { take care of the sucessor }
  290. if assigned(node.successor) then
  291. DFASetIncludeSet(l,node.successor.optinfo^.life);
  292. { the counter variable is living as well inside the for loop
  293. if left is a record element, it might not be tracked by dfa, so
  294. optinfo might not be assigned
  295. }
  296. if assigned(tfornode(node).left.optinfo) then
  297. DFASetInclude(l,tfornode(node).left.optinfo^.index);
  298. { force block node life info }
  299. UpdateLifeInfo(tfornode(node).loopiteration,l);
  300. { now update the for node itself }
  301. { get the life of the loop block }
  302. l:=copy(tfornode(node).t2.optinfo^.life);
  303. { take care of the sucessor as it's possible that we don't have one execution of the body }
  304. if (not(tfornode(node).right.nodetype=ordconstn) or not(tfornode(node).t1.nodetype=ordconstn)) and
  305. assigned(node.successor) then
  306. DFASetIncludeSet(l,node.successor.optinfo^.life);
  307. {
  308. the counter variable is not living at the entry of the for node
  309. if left is a record element, it might not be tracked by dfa, so
  310. optinfo might not be assigned
  311. }
  312. if assigned(tfornode(node).left.optinfo) then
  313. DFASetExclude(l,tfornode(node).left.optinfo^.index);
  314. { ... but it could be that left/right use it, so do this after
  315. removing the def of the counter variable }
  316. DFASetIncludeSet(l,node.optinfo^.use);
  317. UpdateLifeInfo(node,l);
  318. { ... and a second iteration for fast convergence }
  319. CreateInfo(tfornode(node).t2);
  320. end;
  321. temprefn,
  322. loadn,
  323. typeconvn,
  324. derefn,
  325. assignn:
  326. begin
  327. if not(assigned(node.optinfo^.def)) and
  328. not(assigned(node.optinfo^.use)) then
  329. begin
  330. dfainfo.use:[email protected]^.use;
  331. dfainfo.def:[email protected]^.def;
  332. dfainfo.map:=map;
  333. foreachnodestatic(pm_postprocess,node,@AddDefUse,@dfainfo);
  334. end;
  335. calclife(node);
  336. end;
  337. statementn:
  338. begin
  339. { nested statement }
  340. CreateInfo(tstatementnode(node).statement);
  341. { inherit info }
  342. node.optinfo^.life:=tstatementnode(node).statement.optinfo^.life;
  343. end;
  344. blockn:
  345. begin
  346. CreateInfo(tblocknode(node).statements);
  347. { ensure that we don't remove life info }
  348. l:=node.optinfo^.life;
  349. if assigned(node.successor) then
  350. DFASetIncludeSet(l,node.successor.optinfo^.life);
  351. UpdateLifeInfo(node,l);
  352. end;
  353. ifn:
  354. begin
  355. { get information from cond. expression }
  356. if not(assigned(node.optinfo^.def)) and
  357. not(assigned(node.optinfo^.use)) then
  358. begin
  359. dfainfo.use:[email protected]^.use;
  360. dfainfo.def:[email protected]^.def;
  361. dfainfo.map:=map;
  362. foreachnodestatic(pm_postprocess,tifnode(node).left,@AddDefUse,@dfainfo);
  363. end;
  364. { create life info for then and else node }
  365. CreateInfo(tifnode(node).right);
  366. CreateInfo(tifnode(node).t1);
  367. { ensure that we don't remove life info }
  368. l:=node.optinfo^.life;
  369. { get life info from then branch }
  370. if assigned(tifnode(node).right) then
  371. DFASetIncludeSet(l,tifnode(node).right.optinfo^.life);
  372. { get life info from else branch }
  373. if assigned(tifnode(node).t1) then
  374. DFASetIncludeSet(l,tifnode(node).t1.optinfo^.life)
  375. else if assigned(node.successor) then
  376. DFASetIncludeSet(l,node.successor.optinfo^.life);
  377. { remove def info from the cond. expression }
  378. DFASetExcludeSet(l,tifnode(node).optinfo^.def);
  379. { add use info from the cond. expression }
  380. DFASetIncludeSet(l,tifnode(node).optinfo^.use);
  381. { finally, update the life info of the node }
  382. UpdateLifeInfo(node,l);
  383. end;
  384. casen:
  385. begin
  386. { get information from "case" expression }
  387. if not(assigned(node.optinfo^.def)) and
  388. not(assigned(node.optinfo^.use)) then
  389. begin
  390. dfainfo.use:[email protected]^.use;
  391. dfainfo.def:[email protected]^.def;
  392. dfainfo.map:=map;
  393. foreachnodestatic(pm_postprocess,tcasenode(node).left,@AddDefUse,@dfainfo);
  394. end;
  395. { create life info for block and else nodes }
  396. for i:=0 to tcasenode(node).blocks.count-1 do
  397. CreateInfo(pcaseblock(tcasenode(node).blocks[i])^.statement);
  398. CreateInfo(tcasenode(node).elseblock);
  399. { ensure that we don't remove life info }
  400. l:=node.optinfo^.life;
  401. { get life info from case branches }
  402. for i:=0 to tcasenode(node).blocks.count-1 do
  403. DFASetIncludeSet(l,pcaseblock(tcasenode(node).blocks[i])^.statement.optinfo^.life);
  404. { get life info from else branch or the succesor }
  405. if assigned(tcasenode(node).elseblock) then
  406. DFASetIncludeSet(l,tcasenode(node).elseblock.optinfo^.life)
  407. else if assigned(node.successor) then
  408. begin
  409. if is_ordinal(tcasenode(node).left.resultdef) then
  410. begin
  411. getrange(tcasenode(node).left.resultdef,lv,hv);
  412. if tcasenode(node).labelcoverage<(hv-lv) then
  413. DFASetIncludeSet(l,node.successor.optinfo^.life);
  414. end
  415. else
  416. DFASetIncludeSet(l,node.successor.optinfo^.life);
  417. end;
  418. { add use info from the "case" expression }
  419. DFASetIncludeSet(l,tcasenode(node).optinfo^.use);
  420. { finally, update the life info of the node }
  421. UpdateLifeInfo(node,l);
  422. end;
  423. exitn:
  424. begin
  425. { in case of inlining, an exit node can have a successor, in this case, we do not have to
  426. use the faked resultnode }
  427. if assigned(node.successor) then
  428. begin
  429. l:=node.optinfo^.life;
  430. DFASetIncludeSet(l,node.successor.optinfo^.life);
  431. UpdateLifeInfo(node,l);
  432. end
  433. else if assigned(resultnode) and (resultnode.nodetype<>nothingn) then
  434. begin
  435. if not(assigned(node.optinfo^.def)) and
  436. not(assigned(node.optinfo^.use)) then
  437. begin
  438. if assigned(texitnode(node).left) then
  439. begin
  440. { this should never happen as
  441. texitnode.pass_typecheck converts the left node into a separate node already
  442. node.optinfo^.def:=resultnode.optinfo^.def;
  443. dfainfo.use:[email protected]^.use;
  444. dfainfo.def:[email protected]^.def;
  445. dfainfo.map:=map;
  446. foreachnodestatic(pm_postprocess,texitnode(node).left,@AddDefUse,@dfainfo);
  447. calclife(node); }
  448. Internalerror(2020122901);
  449. end
  450. else
  451. begin
  452. { get info from faked resultnode }
  453. node.optinfo^.use:=resultnode.optinfo^.use;
  454. node.optinfo^.life:=node.optinfo^.use;
  455. changed:=true;
  456. end;
  457. end;
  458. end;
  459. end;
  460. {$ifdef JVM}
  461. { all other platforms except jvm translate raise nodes into call nodes during pass_1 }
  462. raisen,
  463. {$endif JVM}
  464. asn,
  465. inlinen,
  466. calln:
  467. begin
  468. if not(assigned(node.optinfo^.def)) and
  469. not(assigned(node.optinfo^.use)) then
  470. begin
  471. dfainfo.use:[email protected]^.use;
  472. dfainfo.def:[email protected]^.def;
  473. dfainfo.map:=map;
  474. foreachnodestatic(pm_postprocess,node,@AddDefUse,@dfainfo);
  475. end;
  476. calclife(node);
  477. end;
  478. labeln:
  479. begin
  480. calclife(node);
  481. if assigned(tlabelnode(node).left) then
  482. begin
  483. l:=node.optinfo^.life;
  484. DFASetIncludeSet(l,tlabelnode(node).optinfo^.life);
  485. UpdateLifeInfo(node,l);
  486. end;
  487. end;
  488. tempcreaten,
  489. tempdeleten,
  490. nothingn,
  491. continuen,
  492. goton,
  493. breakn:
  494. begin
  495. calclife(node);
  496. end;
  497. else
  498. internalerror(2007050502);
  499. end;
  500. end;
  501. var
  502. runs : integer;
  503. begin
  504. runs:=0;
  505. repeat
  506. inc(runs);
  507. changed:=false;
  508. CreateInfo(node);
  509. foreachnodestatic(pm_postprocess,node,@ResetProcessing,nil);
  510. { the result node is not reached by foreachnodestatic }
  511. exclude(resultnode.flags,nf_processing);
  512. {$ifdef DEBUG_DFA}
  513. PrintIndexedNodeSet(output,map);
  514. PrintDFAInfo(output,node);
  515. {$endif DEBUG_DFA}
  516. until not(changed);
  517. {$ifdef DEBUG_DFA}
  518. writeln('DFA solver iterations: ',runs);
  519. {$endif DEBUG_DFA}
  520. end;
  521. { reset all dfa info, this is required before creating dfa info
  522. if the tree has been changed without updating dfa }
  523. procedure TDFABuilder.resetdfainfo(node : tnode);
  524. begin
  525. nodemap.Free;
  526. nodemap:=nil;
  527. resultnode.Free;
  528. resultnode:=nil;
  529. foreachnodestatic(pm_postprocess,node,@ResetDFA,nil);
  530. end;
  531. procedure TDFABuilder.createdfainfo(node : tnode);
  532. var
  533. dfarec : tdfainfo;
  534. begin
  535. if not(assigned(nodemap)) then
  536. nodemap:=TIndexedNodeSet.Create;
  537. { create a fake node using the result which will be the last node }
  538. if not(is_void(current_procinfo.procdef.returndef)) then
  539. begin
  540. if current_procinfo.procdef.proctypeoption=potype_constructor then
  541. resultnode:=load_self_node
  542. else
  543. resultnode:=load_result_node;
  544. resultnode.allocoptinfo;
  545. dfarec.use:[email protected]^.use;
  546. dfarec.def:[email protected]^.def;
  547. dfarec.map:=nodemap;
  548. AddDefUse(resultnode,@dfarec);
  549. resultnode.optinfo^.life:=resultnode.optinfo^.use;
  550. end
  551. else
  552. begin
  553. resultnode:=cnothingnode.create;
  554. resultnode.allocoptinfo;
  555. end;
  556. { add controll flow information }
  557. SetNodeSucessors(node,resultnode);
  558. { now, collect life information }
  559. CreateLifeInfo(node,nodemap);
  560. end;
  561. procedure TDFABuilder.redodfainfo(node: tnode);
  562. begin
  563. resetdfainfo(node);
  564. createdfainfo(node);
  565. include(current_procinfo.flags,pi_dfaavailable);
  566. end;
  567. destructor TDFABuilder.Destroy;
  568. begin
  569. Resultnode.free;
  570. nodemap.free;
  571. inherited destroy;
  572. end;
  573. type
  574. { helper structure to be able to pass more than one variable to the iterator function }
  575. TSearchNodeInfo = record
  576. nodetosearch : tnode;
  577. { this contains a list of all file locations where a warning was thrown already,
  578. the same location might appear multiple times because nodes might have been copied }
  579. warnedfilelocs : array of tfileposinfo;
  580. end;
  581. PSearchNodeInfo = ^TSearchNodeInfo;
  582. { searches for a given node n and warns if the node is found as being uninitialized. If a node is
  583. found, searching is stopped so each call issues only one warning/hint }
  584. function SearchNode(var n: tnode; arg: pointer): foreachnoderesult;
  585. function WarnedForLocation(f : tfileposinfo) : boolean;
  586. var
  587. i : longint;
  588. begin
  589. result:=true;
  590. for i:=0 to high(PSearchNodeInfo(arg)^.warnedfilelocs) do
  591. with PSearchNodeInfo(arg)^.warnedfilelocs[i] do
  592. begin
  593. if (f.column=column) and (f.fileindex=fileindex) and (f.line=line) and (f.moduleindex=moduleindex) then
  594. exit;
  595. end;
  596. result:=false;
  597. end;
  598. procedure AddFilepos(const f : tfileposinfo);
  599. begin
  600. Setlength(PSearchNodeInfo(arg)^.warnedfilelocs,length(PSearchNodeInfo(arg)^.warnedfilelocs)+1);
  601. PSearchNodeInfo(arg)^.warnedfilelocs[high(PSearchNodeInfo(arg)^.warnedfilelocs)]:=f;
  602. end;
  603. { Checks if the symbol is a candidate for a warning.
  604. Emit warning/note for living locals, result and parameters, but only about the current
  605. symtables }
  606. function SymbolCandidateForWarningOrHint(sym : tabstractnormalvarsym) : Boolean;
  607. begin
  608. Result:=(((sym.owner=current_procinfo.procdef.localst) and
  609. (current_procinfo.procdef.localst.symtablelevel=sym.owner.symtablelevel)
  610. ) or
  611. ((sym.owner=current_procinfo.procdef.parast) and
  612. (sym.typ=paravarsym) and
  613. (current_procinfo.procdef.parast.symtablelevel=sym.owner.symtablelevel) and
  614. { all parameters except out parameters are initialized by the caller }
  615. (tparavarsym(sym).varspez=vs_out)
  616. ) or
  617. ((vo_is_funcret in sym.varoptions) and
  618. (current_procinfo.procdef.parast.symtablelevel=sym.owner.symtablelevel)
  619. )
  620. ) and
  621. not(vo_is_external in sym.varoptions) and
  622. not sym.inparentfpstruct and
  623. not(vo_is_internal in sym.varoptions);
  624. end;
  625. var
  626. varsym : tabstractnormalvarsym;
  627. methodpointer,
  628. hpt : tnode;
  629. begin
  630. result:=fen_false;
  631. case n.nodetype of
  632. callparan:
  633. begin
  634. { do not warn about variables passed by var, just issue a hint, this
  635. is a workaround for old code e.g. using fillchar }
  636. if assigned(tcallparanode(n).parasym) and (tcallparanode(n).parasym.varspez in [vs_var,vs_out]) then
  637. begin
  638. hpt:=tcallparanode(n).left;
  639. while assigned(hpt) and (hpt.nodetype in [subscriptn,vecn,typeconvn]) do
  640. hpt:=tunarynode(hpt).left;
  641. if assigned(hpt) and (hpt.nodetype=loadn) and not(WarnedForLocation(hpt.fileinfo)) and
  642. SymbolCandidateForWarningOrHint(tabstractnormalvarsym(tloadnode(hpt).symtableentry)) and
  643. PSearchNodeInfo(arg)^.nodetosearch.isequal(hpt) then
  644. begin
  645. { issue only a hint for var, when encountering the node passed as out, we need only to stop searching }
  646. if tcallparanode(n).parasym.varspez=vs_var then
  647. UninitializedVariableMessage(hpt.fileinfo,false,
  648. tloadnode(hpt).symtable.symtabletype=localsymtable,
  649. is_managed_type(tloadnode(hpt).resultdef),
  650. tloadnode(hpt).symtableentry.RealName);
  651. AddFilepos(hpt.fileinfo);
  652. result:=fen_norecurse_true;
  653. end
  654. end;
  655. end;
  656. orn,
  657. andn:
  658. begin
  659. { take care of short boolean evaluation: if the expression to be search is found in left,
  660. we do not need to search right }
  661. if foreachnodestatic(pm_postprocess,taddnode(n).left,@optdfa.SearchNode,arg) or
  662. foreachnodestatic(pm_postprocess,taddnode(n).right,@optdfa.SearchNode,arg) then
  663. result:=fen_norecurse_true
  664. else
  665. result:=fen_norecurse_false;
  666. end;
  667. calln:
  668. begin
  669. methodpointer:=tcallnode(n).methodpointer;
  670. if assigned(methodpointer) and (methodpointer.nodetype<>typen) then
  671. begin
  672. { Remove all postfix operators }
  673. hpt:=methodpointer;
  674. while assigned(hpt) and (hpt.nodetype in [subscriptn,vecn]) do
  675. hpt:=tunarynode(hpt).left;
  676. { skip (absolute and other simple) type conversions -- only now,
  677. because the checks above have to take type conversions into
  678. e.g. class reference types account }
  679. hpt:=actualtargetnode(@hpt)^;
  680. { R.Init then R will be initialized by the constructor,
  681. Also allow it for simple loads }
  682. if (tcallnode(n).procdefinition.proctypeoption=potype_constructor) or
  683. (PSearchNodeInfo(arg)^.nodetosearch.isequal(hpt) and
  684. (((methodpointer.resultdef.typ=objectdef) and
  685. not(oo_has_virtual in tobjectdef(methodpointer.resultdef).objectoptions)) or
  686. (methodpointer.resultdef.typ=recorddef)
  687. )
  688. ) then
  689. begin
  690. { don't warn about the method pointer }
  691. AddFilepos(hpt.fileinfo);
  692. if not(foreachnodestatic(pm_postprocess,tcallnode(n).left,@optdfa.SearchNode,arg)) then
  693. foreachnodestatic(pm_postprocess,tcallnode(n).right,@optdfa.SearchNode,arg);
  694. result:=fen_norecurse_true
  695. end;
  696. end;
  697. end;
  698. loadn:
  699. begin
  700. if (tloadnode(n).symtableentry.typ in [localvarsym,paravarsym,staticvarsym]) and
  701. PSearchNodeInfo(arg)^.nodetosearch.isequal(n) and ((nf_modify in n.flags) or not(nf_write in n.flags)) then
  702. begin
  703. varsym:=tabstractnormalvarsym(tloadnode(n).symtableentry);
  704. if assigned(varsym.owner) and SymbolCandidateForWarningOrHint(varsym) then
  705. begin
  706. if (vo_is_funcret in varsym.varoptions) and not(WarnedForLocation(n.fileinfo)) then
  707. begin
  708. if is_managed_type(varsym.vardef) then
  709. MessagePos(n.fileinfo,sym_w_managed_function_result_uninitialized)
  710. else
  711. MessagePos(n.fileinfo,sym_w_function_result_uninitialized);
  712. AddFilepos(n.fileinfo);
  713. result:=fen_norecurse_true;
  714. end
  715. else
  716. begin
  717. { typed consts are initialized, further, warn only once per location }
  718. if not (vo_is_typed_const in varsym.varoptions) and not(WarnedForLocation(n.fileinfo)) then
  719. begin
  720. UninitializedVariableMessage(n.fileinfo,true,varsym.typ=localvarsym,is_managed_type(varsym.vardef),varsym.realname);
  721. AddFilepos(n.fileinfo);
  722. result:=fen_norecurse_true;
  723. end;
  724. end;
  725. end
  726. {$ifdef dummy}
  727. { if a the variable we are looking for is passed as a var parameter, we stop searching }
  728. else if assigned(varsym.owner) and
  729. (varsym.owner=current_procinfo.procdef.parast) and
  730. (varsym.typ=paravarsym) and
  731. (current_procinfo.procdef.parast.symtablelevel=varsym.owner.symtablelevel) and
  732. (tparavarsym(varsym).varspez=vs_var) then
  733. result:=fen_norecurse_true;
  734. {$endif dummy}
  735. end;
  736. end;
  737. else
  738. ;
  739. end;
  740. end;
  741. procedure CheckAndWarn(code : tnode;nodetosearch : tnode);
  742. var
  743. SearchNodeInfo : TSearchNodeInfo;
  744. function DoCheck(node : tnode) : boolean;
  745. var
  746. i : longint;
  747. touchesnode : Boolean;
  748. procedure MaybeDoCheck(n : tnode);inline;
  749. begin
  750. Result:=Result or DoCheck(n);
  751. end;
  752. procedure MaybeSearchIn(n : tnode);
  753. begin
  754. if touchesnode then
  755. Result:=Result or foreachnodestatic(pm_postprocess,n,@SearchNode,@SearchNodeInfo);
  756. end;
  757. begin
  758. result:=false;
  759. if node=nil then
  760. exit;
  761. if nf_processing in node.flags then
  762. exit;
  763. include(node.flags,nf_processing);
  764. if not(assigned(node.optinfo)) or not(DFASetIn(node.optinfo^.life,nodetosearch.optinfo^.index)) then
  765. exit;
  766. { we do not need this info always, so try to safe some time here, CheckAndWarn
  767. takes a lot of time anyways }
  768. if not(node.nodetype in [statementn,blockn]) then
  769. touchesnode:=DFASetIn(node.optinfo^.use,nodetosearch.optinfo^.index) or
  770. DFASetIn(node.optinfo^.def,nodetosearch.optinfo^.index)
  771. else
  772. touchesnode:=false;
  773. case node.nodetype of
  774. whilerepeatn:
  775. begin
  776. MaybeSearchIn(twhilerepeatnode(node).left);
  777. MaybeDoCheck(twhilerepeatnode(node).right);
  778. end;
  779. forn:
  780. begin
  781. MaybeSearchIn(tfornode(node).right);
  782. MaybeSearchIn(tfornode(node).t1);
  783. MaybeDoCheck(tfornode(node).t2);
  784. end;
  785. statementn:
  786. MaybeDoCheck(tstatementnode(node).statement);
  787. blockn:
  788. MaybeDoCheck(tblocknode(node).statements);
  789. ifn:
  790. begin
  791. MaybeSearchIn(tifnode(node).left);
  792. MaybeDoCheck(tifnode(node).right);
  793. MaybeDoCheck(tifnode(node).t1);
  794. end;
  795. casen:
  796. begin
  797. MaybeSearchIn(tcasenode(node).left);
  798. for i:=0 to tcasenode(node).blocks.count-1 do
  799. MaybeDoCheck(pcaseblock(tcasenode(node).blocks[i])^.statement);
  800. MaybeDoCheck(tcasenode(node).elseblock);
  801. end;
  802. labeln:
  803. MaybeDoCheck(tlabelnode(node).left);
  804. { we are aware of the following nodes so if new node types are added to the compiler
  805. and pop up in the search, the ie below kicks in as a reminder }
  806. exitn:
  807. begin
  808. MaybeSearchIn(texitnode(node).left);
  809. { exit uses the resultnode implicitly, so searching for a matching node is
  810. useless, if we reach the exit node and found the living node not in left, then
  811. it can be only the resultnode
  812. successor might be assigned in case of an inlined exit node, in this case we do not warn about an unassigned
  813. result as this had happened already when the routine has been compiled }
  814. if not(assigned(node.successor)) and not(Result) and not(is_void(current_procinfo.procdef.returndef)) and
  815. not(assigned(texitnode(node).resultexpr)) and
  816. { don't warn about constructors }
  817. not(current_procinfo.procdef.proctypeoption in [potype_class_constructor,potype_constructor]) then
  818. begin
  819. if is_managed_type(current_procinfo.procdef.returndef) then
  820. MessagePos(node.fileinfo,sym_w_managed_function_result_uninitialized)
  821. else
  822. MessagePos(node.fileinfo,sym_w_function_result_uninitialized);
  823. Setlength(SearchNodeInfo.warnedfilelocs,length(SearchNodeInfo.warnedfilelocs)+1);
  824. SearchNodeInfo.warnedfilelocs[high(SearchNodeInfo.warnedfilelocs)]:=node.fileinfo;
  825. end
  826. end;
  827. { could be the implicitly generated load node for the result }
  828. {$ifdef JVM}
  829. { all other platforms except jvm translate raise nodes into call nodes during pass_1 }
  830. raisen,
  831. {$endif JVM}
  832. loadn,
  833. assignn,
  834. calln,
  835. temprefn,
  836. typeconvn,
  837. inlinen,
  838. tempcreaten,
  839. tempdeleten:
  840. MaybeSearchIn(node);
  841. nothingn,
  842. continuen,
  843. goton,
  844. breakn:
  845. ;
  846. else
  847. internalerror(2013111301);
  848. end;
  849. { if already a warning has been issued, then stop }
  850. if Result then
  851. exit;
  852. if assigned(node.successor) then
  853. MaybeDoCheck(node.successor);
  854. end;
  855. begin
  856. SearchNodeInfo.nodetosearch:=nodetosearch;
  857. DoCheck(code);
  858. foreachnodestatic(pm_postprocess,code,@ResetProcessing,nil);
  859. end;
  860. end.