optdfa.pas 11 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371
  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. { this unit implements routines to perform dfa }
  19. unit optdfa;
  20. {$i fpcdefs.inc}
  21. interface
  22. uses
  23. node;
  24. { reset all dfa info, this is required before creating dfa info
  25. if the tree has been changed without updating dfa }
  26. procedure resetdfainfo(node : tnode);
  27. procedure createdfainfo(node : tnode);
  28. implementation
  29. uses
  30. globtype,globals,
  31. verbose,
  32. cpuinfo,
  33. symdef,
  34. defutil,
  35. procinfo,
  36. nutils,
  37. nbas,nflw,ncon,ninl,ncal,
  38. optbase,optutils;
  39. (*
  40. function initnodes(var n:tnode; arg: pointer) : foreachnoderesult;
  41. begin
  42. { node worth to add? }
  43. if (node_complexity(n)>1) and (tstoreddef(n.resultdef).is_intregable or tstoreddef(n.resultdef).is_fpuregable) then
  44. begin
  45. plists(arg)^.nodelist.Add(n);
  46. plists(arg)^.locationlist.Add(@n);
  47. result:=fen_false;
  48. end
  49. else
  50. result:=fen_norecurse_false;
  51. end;
  52. *)
  53. {
  54. x:=f; read: [f]
  55. while x do read: []
  56. a:=b; read: [a,b,d] def: [a] life: read*def=[a]
  57. c:=d; read: [a,d] def: [a,c] life: read*def=[a]
  58. e:=a; read: [a] def: [a,c,e] life: read*def=[a]
  59. function f(b,d,x : type) : type;
  60. begin
  61. while x do alive: b,d,x
  62. begin
  63. a:=b; alive: b,d,x
  64. c:=d; alive: a,d,x
  65. e:=a+c; alive: a,c,x
  66. dec(x); alive: c,e,x
  67. end;
  68. result:=c+e; alive: c,e
  69. end; alive: result
  70. }
  71. type
  72. tdfainfo = record
  73. use : PDFASet;
  74. def : PDFASet;
  75. map : TIndexedNodeSet
  76. end;
  77. pdfainfo = ^tdfainfo;
  78. function AddDefUse(var n: tnode; arg: pointer): foreachnoderesult;
  79. begin
  80. case n.nodetype of
  81. loadn:
  82. begin
  83. pdfainfo(arg)^.map.Add(n);
  84. if nf_write in n.flags then
  85. DFASetInclude(pdfainfo(arg)^.def^,n.optinfo^.index)
  86. else
  87. DFASetInclude(pdfainfo(arg)^.use^,n.optinfo^.index);
  88. {
  89. write('Use Set: ');
  90. PrintDFASet(output,pdfainfo(arg)^.use^);
  91. write(' Def Set: ');
  92. PrintDFASet(output,pdfainfo(arg)^.def^);
  93. writeln;
  94. }
  95. end;
  96. end;
  97. result:=fen_false;
  98. end;
  99. procedure CreateLifeInfo(node : tnode;map : TIndexedNodeSet);
  100. var
  101. changed : boolean;
  102. Resultnode : TNode;
  103. procedure CreateInfo(node : tnode);
  104. { update life entry of a node with l, set changed if this changes
  105. life info for the node
  106. }
  107. procedure updatelifeinfo(n : tnode;l : TDFASet);
  108. var
  109. b : boolean;
  110. begin
  111. b:=DFASetNotEqual(l,n.optinfo^.life);
  112. {
  113. if b then
  114. begin
  115. printnode(output,n);
  116. printdfaset(output,l);
  117. writeln;
  118. printdfaset(output,n.optinfo^.life);
  119. writeln;
  120. end;
  121. }
  122. changed:=changed or b;
  123. node.optinfo^.life:=l;
  124. end;
  125. procedure calclife(n : tnode);
  126. var
  127. l : TDFASet;
  128. begin
  129. if assigned(n.successor) then
  130. begin
  131. {
  132. write('Successor Life: ');
  133. printdfaset(output,n.successor.optinfo^.life);
  134. writeln;
  135. write('Def.');
  136. printdfaset(output,n.optinfo^.def);
  137. writeln;
  138. }
  139. { ensure we can access optinfo }
  140. DFASetDiff(l,n.successor.optinfo^.life,n.optinfo^.def);
  141. {
  142. printdfaset(output,l);
  143. writeln;
  144. }
  145. DFASetIncludeSet(l,n.optinfo^.use);
  146. DFASetIncludeSet(l,n.optinfo^.life);
  147. end
  148. else
  149. l:=n.optinfo^.use;
  150. updatelifeinfo(n,l);
  151. end;
  152. var
  153. dfainfo : tdfainfo;
  154. l : TDFASet;
  155. begin
  156. if node=nil then
  157. exit;
  158. { ensure we've already optinfo set }
  159. node.allocoptinfo;
  160. if nf_processing in node.flags then
  161. exit;
  162. include(node.flags,nf_processing);
  163. if assigned(node.successor) then
  164. CreateInfo(node.successor);
  165. { life:=succesorlive-definition+use }
  166. case node.nodetype of
  167. whilerepeatn:
  168. begin
  169. calclife(node);
  170. if lnf_testatbegin in twhilerepeatnode(node).loopflags then
  171. begin
  172. node.allocoptinfo;
  173. if not(assigned(node.optinfo^.def)) and
  174. not(assigned(node.optinfo^.use)) then
  175. begin
  176. dfainfo.use:[email protected]^.use;
  177. dfainfo.def:[email protected]^.def;
  178. dfainfo.map:=map;
  179. foreachnodestatic(pm_postprocess,twhilerepeatnode(node).left,@AddDefUse,@dfainfo);
  180. end;
  181. calclife(node);
  182. { now iterate through the loop }
  183. CreateInfo(twhilerepeatnode(node).right);
  184. { update while node }
  185. { life:=life+use+right.life }
  186. l:=node.optinfo^.life;
  187. DFASetIncludeSet(l,node.optinfo^.use);
  188. DFASetIncludeSet(l,twhilerepeatnode(node).right.optinfo^.life);
  189. UpdateLifeInfo(node,l);
  190. { ... and a second iteration for fast convergence }
  191. CreateInfo(twhilerepeatnode(node).right);
  192. end;
  193. end;
  194. assignn:
  195. begin
  196. if not(assigned(node.optinfo^.def)) and
  197. not(assigned(node.optinfo^.use)) then
  198. begin
  199. dfainfo.use:[email protected]^.use;
  200. dfainfo.def:[email protected]^.def;
  201. dfainfo.map:=map;
  202. foreachnodestatic(pm_postprocess,node,@AddDefUse,@dfainfo);
  203. end;
  204. calclife(node);
  205. end;
  206. statementn:
  207. begin
  208. { nested statement }
  209. CreateInfo(tstatementnode(node).statement);
  210. { inherit info }
  211. node.optinfo^.life:=tstatementnode(node).statement.optinfo^.life;
  212. end;
  213. blockn:
  214. begin
  215. CreateInfo(tblocknode(node).statements);
  216. if assigned(tblocknode(node).statements) then
  217. node.optinfo^.life:=tblocknode(node).statements.optinfo^.life;
  218. end;
  219. ifn:
  220. begin
  221. { get information from cond. expression }
  222. if not(assigned(node.optinfo^.def)) and
  223. not(assigned(node.optinfo^.use)) then
  224. begin
  225. dfainfo.use:[email protected]^.use;
  226. dfainfo.def:[email protected]^.def;
  227. dfainfo.map:=map;
  228. foreachnodestatic(pm_postprocess,tifnode(node).left,@AddDefUse,@dfainfo);
  229. end;
  230. { create life info for left and right node }
  231. CreateInfo(tifnode(node).right);
  232. CreateInfo(tifnode(node).t1);
  233. { ensure that we don't remove life info }
  234. l:=node.optinfo^.life;
  235. { get life info from then branch }
  236. if assigned(tifnode(node).right) then
  237. DFASetIncludeSet(l,tifnode(node).right.optinfo^.life);
  238. { get life info from else branch }
  239. if assigned(tifnode(node).t1) then
  240. DFASetIncludeSet(l,tifnode(node).t1.optinfo^.life)
  241. else
  242. if assigned(node.successor) then
  243. DFASetIncludeSet(l,node.successor.optinfo^.life);
  244. { add use info from cond. expression }
  245. DFASetIncludeSet(l,tifnode(node).optinfo^.use);
  246. { finally, update the life info of the node }
  247. UpdateLifeInfo(node,l);
  248. end;
  249. exitn:
  250. begin
  251. if not(is_void(current_procinfo.procdef.returndef)) then
  252. begin
  253. { get info from faked resultnode }
  254. node.optinfo^.use:=resultnode.optinfo^.use;
  255. node.optinfo^.life:=node.optinfo^.use;
  256. end;
  257. end;
  258. nothingn,
  259. continuen,
  260. goton,
  261. breakn,
  262. labeln:
  263. begin
  264. calclife(node);
  265. end;
  266. else
  267. internalerror(2007050502);
  268. end;
  269. exclude(node.flags,nf_processing);
  270. end;
  271. var
  272. runs : integer;
  273. dfarec : tdfainfo;
  274. begin
  275. runs:=0;
  276. if not(is_void(current_procinfo.procdef.returndef)) then
  277. begin
  278. { create a fake node using the result }
  279. resultnode:=load_result_node;
  280. resultnode.allocoptinfo;
  281. dfarec.use:[email protected]^.use;
  282. dfarec.def:[email protected]^.def;
  283. dfarec.map:=map;
  284. AddDefUse(resultnode,@dfarec);
  285. end
  286. else
  287. resultnode:=nil;
  288. repeat
  289. inc(runs);
  290. changed:=false;
  291. CreateInfo(node);
  292. {$ifdef DEBUG_DFA}
  293. PrintIndexedNodeSet(output,map);
  294. PrintDFAInfo(output,node);
  295. {$endif DEBUG_DFA}
  296. until not(changed);
  297. {$ifdef DEBUG_DFA}
  298. writeln('DFA solver iterations: ',runs);
  299. {$endif DEBUG_DFA}
  300. resultnode.free;
  301. end;
  302. { reset all dfa info, this is required before creating dfa info
  303. if the tree has been changed without updating dfa }
  304. procedure resetdfainfo(node : tnode);
  305. begin
  306. end;
  307. procedure createdfainfo(node : tnode);
  308. var
  309. map : TIndexedNodeSet;
  310. begin
  311. map:=TIndexedNodeSet.Create;
  312. { add controll flow information }
  313. SetNodeSucessors(node);
  314. { now, collect life information }
  315. CreateLifeInfo(node,map);
  316. map.free;
  317. end;
  318. end.