2
0

optbase.pas 5.8 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232
  1. {
  2. Basic node optimizer stuff
  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. unit optbase;
  18. {$i fpcdefs.inc}
  19. interface
  20. uses
  21. globtype;
  22. type
  23. { this should maybe replaced by a spare set,
  24. using a dyn. array makes assignments cheap }
  25. tdfaset = array of byte;
  26. PDFASet = ^TDFASet;
  27. toptinfo = record
  28. { index of the current node inside the dfa sets, aword(-1) if no entry }
  29. index : aword;
  30. { dfa }
  31. def : tdfaset;
  32. use : tdfaset;
  33. life : tdfaset;
  34. defsum : tdfaset;
  35. avail : tdfaset;
  36. { estimation, how often the node is executed per subroutine call times 100, calculated by optutils.CalcExecutionWeight }
  37. executionweight : longint;
  38. end;
  39. poptinfo = ^toptinfo;
  40. { basic set operations for dfa sets }
  41. { add e to s }
  42. procedure DFASetInclude(var s : tdfaset;e : integer);
  43. { add s to d }
  44. procedure DFASetIncludeSet(var d : tdfaset;const s : tdfaset);
  45. { remove s to d }
  46. procedure DFASetExcludeSet(var d : tdfaset;const s : tdfaset);
  47. { remove e from s }
  48. procedure DFASetExclude(var s : tdfaset;e : integer);
  49. { test if s contains e }
  50. function DFASetIn(const s : tdfaset;e : integer) : boolean;
  51. { d:=s1+s2; }
  52. procedure DFASetUnion(var d : tdfaset;const s1,s2 : tdfaset);
  53. { d:=s1*s2; }
  54. procedure DFASetIntersect(var d : tdfaset;const s1,s2 : tdfaset);
  55. { d:=s1-s2; }
  56. procedure DFASetDiff(var d : tdfaset;const s1,s2 : tdfaset);
  57. { s1<>s2; }
  58. function DFASetNotEqual(const s1,s2 : tdfaset) : boolean;
  59. { output DFA set }
  60. procedure PrintDFASet(var f : text;s : TDFASet);
  61. implementation
  62. uses
  63. cutils;
  64. procedure DFASetInclude(var s : tdfaset;e : integer);
  65. var
  66. e8 : Integer;
  67. begin
  68. e8:=e div 8;
  69. if e8>high(s) then
  70. SetLength(s,e8+1);
  71. s[e8]:=s[e8] or (1 shl (e mod 8));
  72. end;
  73. procedure DFASetIncludeSet(var d : tdfaset;const s : tdfaset);
  74. var
  75. i : integer;
  76. begin
  77. if length(s)>length(d) then
  78. SetLength(d,length(s));
  79. for i:=0 to high(s) do
  80. d[i]:=d[i] or s[i];
  81. end;
  82. procedure DFASetExcludeSet(var d : tdfaset;const s : tdfaset);
  83. var
  84. i : integer;
  85. begin
  86. if length(s)>length(d) then
  87. SetLength(d,length(s));
  88. for i:=0 to high(s) do
  89. d[i]:=d[i] and not(s[i]);
  90. end;
  91. procedure DFASetExclude(var s : tdfaset;e : integer);
  92. var
  93. e8 : Integer;
  94. begin
  95. e8:=e div 8;
  96. if e8<=high(s) then
  97. s[e8]:=s[e8] and not(1 shl (e mod 8));
  98. end;
  99. function DFASetIn(const s : tdfaset;e : integer) : boolean;
  100. var
  101. e8 : Integer;
  102. begin
  103. e8:=e div 8;
  104. if e8<=high(s) then
  105. result:=(s[e8] and (1 shl (e mod 8)))<>0
  106. else
  107. result:=false;
  108. end;
  109. procedure DFASetUnion(var d : tdfaset;const s1,s2 : tdfaset);
  110. var
  111. i : integer;
  112. begin
  113. SetLength(d,max(Length(s1),Length(s2)));
  114. for i:=0 to min(high(s1),high(s2)) do
  115. d[i]:=s1[i] or s2[i];
  116. if high(s1)<high(s2) then
  117. for i:=high(s1)+1 to high(s2) do
  118. d[i]:=s2[i]
  119. else
  120. for i:=high(s2)+1 to high(s1) do
  121. d[i]:=s1[i];
  122. end;
  123. procedure DFASetIntersect(var d : tdfaset;const s1,s2 : tdfaset);
  124. var
  125. i : integer;
  126. begin
  127. SetLength(d,min(Length(s1),Length(s2)));
  128. for i:=0 to high(d) do
  129. d[i]:=s1[i] and s2[i];
  130. end;
  131. procedure DFASetDiff(var d : tdfaset;const s1,s2 : tdfaset);
  132. var
  133. i : integer;
  134. begin
  135. SetLength(d,length(s1));
  136. for i:=0 to high(d) do
  137. if i>high(s2) then
  138. d[i]:=s1[i]
  139. else
  140. d[i]:=s1[i] and not(s2[i]);
  141. end;
  142. function DFASetNotEqual(const s1,s2 : tdfaset) : boolean;
  143. var
  144. i : integer;
  145. begin
  146. result:=true;
  147. { one set could be larger than the other }
  148. if length(s1)>length(s2) then
  149. begin
  150. for i:=0 to high(s2) do
  151. if s1[i]<>s2[i] then
  152. exit;
  153. { check remaining part being zero }
  154. for i:=length(s2) to high(s1) do
  155. if s1[i]<>0 then
  156. exit;
  157. end
  158. else
  159. begin
  160. for i:=0 to high(s1) do
  161. if s1[i]<>s2[i] then
  162. exit;
  163. { check remaining part being zero }
  164. for i:=length(s1) to high(s2) do
  165. if s2[i]<>0 then
  166. exit;
  167. end;
  168. result:=false;
  169. end;
  170. procedure PrintDFASet(var f : text;s : TDFASet);
  171. var
  172. i : integer;
  173. first : boolean;
  174. begin
  175. first:=true;
  176. for i:=0 to Length(s)*8 do
  177. begin
  178. if DFASetIn(s,i) then
  179. begin
  180. if not(first) then
  181. write(f,',');
  182. write(f,i);
  183. first:=false;
  184. end;
  185. end;
  186. end;
  187. end.