epsilon.soag.optimizer source code

1 module epsilon.soag.optimizer;
2 
3 import EAG = epsilon.eag;
4 import runtime;
5 import ALists = epsilon.soag.alists;
6 import SOAG = epsilon.soag.soag;
7 import Protocol = epsilon.soag.protocol;
8 import VisitSeq = epsilon.soag.visitseq;
9 import std.stdio;
10 
11 const firstGlobalVar = 1;
12 const firstStackVar = 1;
13 int GlobalVar;
14 int StackVar;
15 int[] PN;
16 bool admissible;
17 bool disjoint;
18 ALists.AList VDS;
19 ALists.AList VS;
20 
21 /**
22  * IN:  Tripel
23  * OUT: -
24  * SEM: bed. Einfügen des Tripels in die modulglobale Liste VDS, die als Menge interpretiert wird,
25  *      deshalb wird das Tripel nur dann eingefügt, wenn es nicht schon Bestandteil der Liste ist.
26  */
27 void IncludeVDS(int S, int VN1, int VN2) nothrow @safe
28 {
29     int i = ALists.firstIndex;
30     bool notisElement = true;
31 
32     while (i < VDS.Last && notisElement)
33     {
34         notisElement = VDS.Elem[i] != S || VDS.Elem[i + 1] != VN1 || VDS.Elem[i + 2] != VN2;
35         i += 3;
36     }
37     if (notisElement)
38     {
39         ALists.Append(VDS, S);
40         ALists.Append(VDS, VN1);
41         ALists.Append(VDS, VN2);
42     }
43 }
44 
45 void WriteVDS()
46 {
47     stdout.writeln("Inhalt VDS:");
48     for (size_t i = ALists.firstIndex; i <= VDS.Last; i += 3)
49         stdout.writeln(EAG.HNontRepr(VDS.Elem[i]), ", ", VDS.Elem[i + 1], ", ", VDS.Elem[i + 2]);
50         stdout.writeln;
51 }
52 
53 /**
54  * IN:  Tupel
55  * OUT: -
56  * SEM: bed. Einfügen des Tupels in die modulglobale Liste VS, die als Menge interpretiert wird,
57  *      deshalb wird das Tupel nur dann eingefügt, wenn es nicht schon Bestandteil der Liste ist.
58  */
59 void IncludeVS(int S, int VN) nothrow @safe
60 {
61     int i = ALists.firstIndex;
62     bool notisElement = true;
63 
64     while (i < VS.Last && notisElement)
65     {
66         notisElement = VS.Elem[i] != S || VS.Elem[i + 1] != VN;
67         i += 2;
68     }
69     if (notisElement)
70     {
71         ALists.Append(VS, S);
72         ALists.Append(VS, VN);
73     }
74 }
75 
76 void WriteVS()
77 {
78     stdout.writeln("Inhalt VS:");
79     for (size_t i = ALists.firstIndex; i <= VS.Last; i += 2)
80         stdout.writeln(EAG.HNontRepr(VS.Elem[i]), ", ", VS.Elem[i + 1]);
81         stdout.writeln;
82 }
83 
84 /**
85  * IN:  Regel, Affixparameter
86  * OUT: Plannummer
87  * SEM: Ermittelt die Nummer des Visitplanes, während dessen Auswertung der Affixparameter berechnet wird
88  */
89 int GetPlanNo(int R, int AP) @nogc nothrow @safe
90 {
91     const SO = SOAG.AffOcc[AP].SymOccInd;
92 
93     if (SO == SOAG.Rule[R].SymOcc.Beg)
94         return VisitSeq.GetVisitNo(AP);
95 
96     const VN = VisitSeq.GetVisitNo(AP);
97 
98     return PN[VisitSeq.GetVisit(R, SO, VN)];
99 }
100 
101 /**
102  * IN:  Regel, Affixparameter
103  * OUT: Position in der virtuellen extended visit sequence (EVS)
104  * SEM: Ermittelt der Position des Affixparameter in der EVS (entspricht set(a) aus der Theorie)
105  */
106 int GetEVSPosforAffOcc(int R, int AP) @nogc nothrow @safe
107 {
108     int SO = SOAG.AffOcc[AP].SymOccInd;
109     int VN = VisitSeq.GetVisitNo(AP);
110     const S = SOAG.SymOcc[SO].SymInd;
111     const AN = SOAG.AffOcc[AP].AffOccNum.InSym;
112     int V;
113 
114     if (SO == SOAG.Rule[R].SymOcc.Beg && SOAG.IsInherited(S, AN))
115     {
116         if (VN == 1)
117             return 0;
118         V = VisitSeq.GetVisit(R, SO, VN - 1);
119         return V * 3 + 1;
120     }
121     V = VisitSeq.GetVisit(R, SO, VN);
122     return SOAG.IsInherited(S, AN) ? V * 3 + 1 : V * 3 + 3;
123 }
124 
125 /**
126  * IN:  Regel, Symbolvorkommen, Visit-Nummer
127  * OUT: Position in der virtuellen extended visit sequence (EVS)
128  * SEM: Ermittelt der Position des durch Symbolvorkommen und Visitnummer eindeutig gekennzeichneten Visits
129  *      in der EVS (entspricht visit(j,m) aus der Theorie)
130  */
131 int GetEVSPosforVisit(int R, int SO, int VN) @nogc nothrow @safe
132 {
133     const V = VisitSeq.GetVisit(R, SO, VN);
134 
135     return V * 3 + 2;
136 }
137 
138 /**
139  * SEM: Initialisierung der Struktur PN - Berechnung der Plannummer jedes Visits
140  */
141 void Init() nothrow @safe
142 {
143     PN = new int[SOAG.NextVS];
144     foreach (R; SOAG.firstRule .. SOAG.NextRule)
145     {
146         int PlanNo = 1;
147 
148         foreach (V; SOAG.Rule[R].VS.Beg .. SOAG.Rule[R].VS.End + 1)
149         {
150             PN[V] = PlanNo;
151             if (cast(SOAG.Leave) SOAG.VS[V])
152                 ++PlanNo;
153         }
154     }
155     SOAG.StorageName = new int[SOAG.NextPartNum];
156     SOAG.NextStorageName = SOAG.NextPartNum;
157     foreach (V; SOAG.firstStorageName .. SOAG.NextStorageName)
158         SOAG.StorageName[V] = 0;
159     ALists.New(VDS, 16);
160     ALists.New(VS, 16);
161 }
162 
163 /**
164 * IN:  Symbol, Affixpositionsnummer
165 * OUT: -
166 * SEM: Initialisierung der Mengen VDS und VS für eine Affixposition (analog Step 1 Theorie)
167 */
168 void InitVDSandVS(size_t S, int A) nothrow
169 {
170     int SO;
171     int AP;
172     int PN;
173     int R;
174     int RS;
175     int AP1;
176     int PN1;
177     int AN;
178     int AN1;
179 
180     ALists.Reset(VDS);
181     ALists.Reset(VS);
182     SO = SOAG.Sym[S].FirstOcc;
183     while (SO != SOAG.nil)
184     {
185         AP = SOAG.SymOcc[SO].AffOcc.Beg + A;
186         R = SOAG.SymOcc[SO].RuleInd;
187         if (SOAG.IsEvaluatorRule(R))
188         {
189             PN = GetPlanNo(R, AP);
190             RS = SOAG.SymOcc[SOAG.Rule[R].SymOcc.Beg].SymInd;
191             IncludeVS(RS, PN);
192             for (AP1 = SOAG.Rule[R].AffOcc.Beg; AP1 <= SOAG.Rule[R].AffOcc.End; ++AP1)
193             {
194                 AN1 = SOAG.AffOcc[AP1].AffOccNum.InRule;
195                 AN = SOAG.AffOcc[AP].AffOccNum.InRule;
196                 if (SOAG.Rule[R].DP[AN][AN1])
197                 {
198                     PN1 = GetPlanNo(R, AP1);
199                     if (PN < PN1)
200                         IncludeVDS(RS, PN, PN1);
201                 }
202             }
203         }
204         SO = SOAG.SymOcc[SO].Next;
205     }
206 }
207 
208 /**
209  * SEM: Kompletiert die Initialisierung der Menge VDS (analog Step 2 der Theorie)
210  */
211 void CompleteInitVDS() nothrow
212 {
213     int R;
214     int S;
215     int SO;
216     int VN1;
217     int VN2;
218     int V1;
219     int V2;
220     int RS;
221     int i = ALists.firstIndex;
222 
223     while (i < VDS.Last)
224     {
225         S = VDS.Elem[i];
226         ++i;
227         VN1 = VDS.Elem[i];
228         ++i;
229         VN2 = VDS.Elem[i];
230         ++i;
231         SO = SOAG.Sym[S].FirstOcc;
232         while (SO != SOAG.nil)
233         {
234             R = SOAG.SymOcc[SO].RuleInd;
235             if (SOAG.IsEvaluatorRule(R))
236             {
237                 if (SOAG.Rule[R].SymOcc.Beg != SO)
238                 {
239                     V1 = VisitSeq.GetVisit(R, SO, VN1);
240                     V2 = VisitSeq.GetNextVisit(V1, R, SO, VN2);
241                     if (PN[V1] < PN[V2])
242                     {
243                         RS = SOAG.SymOcc[SOAG.Rule[SOAG.SymOcc[SO].RuleInd].SymOcc.Beg].SymInd;
244                         IncludeVDS(RS, PN[V1], PN[V2]);
245                     }
246                 }
247             }
248             SO = SOAG.SymOcc[SO].Next;
249         }
250     }
251 }
252 
253 /**
254  * IN: Symbol, Affixpos.Nr.
255  * OUT: -
256  * SEM: Test, ob Affixposition als Stack oder als globale Variable abgespeichert werden kann -
257  *      nach Theorem 1 und 3 der Theorie
258  */
259 void CheckStorageType(size_t S, int A) @nogc nothrow
260 {
261     int R;
262     int SO;
263     int AP1;
264     int AN1;
265     int VN1;
266     int AP2;
267     int AN2;
268     int VN2;
269     int S1;
270     int SO1;
271     int PN1;
272     int PN2;
273 
274     /**
275      * IN: Symbol, Affixpos.Nr., aktuelle Regel, zwei Positionen der EVS
276      */
277     void CheckT2P1andT1P1(size_t S, int A, int R, int PN1, int PN2)
278     {
279         int AP3;
280         int AN3;
281         int AP4;
282         int AN4;
283         int PN3;
284         int PN4;
285         int SO1 = SOAG.Sym[S].FirstOcc;
286 
287         while (SO1 != SOAG.nil)
288         {
289             if (R == SOAG.SymOcc[SO1].RuleInd)
290             {
291                 AP3 = SOAG.SymOcc[SO1].AffOcc.Beg + A;
292                 AN3 = SOAG.AffOcc[AP3].AffOccNum.InRule;
293                 PN3 = GetEVSPosforAffOcc(R, AP3);
294                 if (PN1 < PN3 && PN3 < PN2)
295                     disjoint = false;
296                 for (AP4 = SOAG.Rule[R].AffOcc.Beg; AP4 <= SOAG.Rule[R].AffOcc.End; ++AP4)
297                 {
298                     AN4 = SOAG.AffOcc[AP4].AffOccNum.InRule;
299                     if (SOAG.Rule[R].DP[AN3][AN4])
300                     {
301                         PN4 = GetEVSPosforAffOcc(R, AP4);
302                         if (PN1 < PN3 && PN3 < PN2 && PN2 <= PN4)
303                             admissible = false;
304                     }
305                 }
306             }
307             SO1 = SOAG.SymOcc[SO1].Next;
308         }
309     }
310 
311     /**
312      * IN: aktuelle Regel, zwei Positionen in der EVS
313      */
314     void CheckT2P2(int R, int PN1, int PN2)
315     {
316         int S1;
317         int SO1;
318         int PN;
319         int VN;
320 
321         for (size_t t = ALists.firstIndex; t <= VS.Last; t += 2)
322         {
323             S1 = VS.Elem[t];
324             VN = VS.Elem[t + 1];
325             SO1 = SOAG.Sym[S1].FirstOcc;
326             while (SO1 != SOAG.nil)
327             {
328                 if (R == SOAG.SymOcc[SO1].RuleInd && SOAG.Rule[R].SymOcc.Beg != SO1)
329                 {
330                     PN = GetEVSPosforVisit(R, SO1, VN);
331                     if (PN1 < PN && PN < PN2)
332                         disjoint = false;
333                 }
334                 SO1 = SOAG.SymOcc[SO1].Next;
335             }
336         }
337     }
338 
339     /**
340      * IN: aktuelle Regel, zwei Positionen in der EVS
341      */
342     void CheckT1P2andP3(int R, int PN1, int PN2)
343     {
344         int S1;
345         int SO1;
346         int VN3;
347         int VN4;
348         int PN3;
349         int PN4;
350 
351         for (int t = ALists.firstIndex; t <= VDS.Last; t += 3)
352         {
353             S1 = VDS.Elem[t];
354             VN3 = VDS.Elem[t + 1];
355             VN4 = VDS.Elem[t + 2];
356             SO1 = SOAG.Sym[S1].FirstOcc;
357             while (SO1 != SOAG.nil)
358             {
359                 if (R == SOAG.SymOcc[SO1].RuleInd && SOAG.Rule[R].SymOcc.Beg != SO1)
360                 {
361                     PN3 = GetEVSPosforVisit(R, SO1, VN3);
362                     PN4 = GetEVSPosforVisit(R, SO1, VN4);
363                     if (PN1 < PN3 && PN3 < PN2 && PN2 < PN4 || PN3 < PN1 && PN1 < PN4 && PN4 < PN2)
364                         admissible = false;
365                 }
366                 SO1 = SOAG.SymOcc[SO1].Next;
367             }
368         }
369     }
370 
371     /**
372      * IN: Affixpos.Nr., aktuelle Regel, zwei Position in der EVS
373      */
374     void CheckT2P3(size_t S, int A, int R, int PN1, int PN2)
375     {
376         int SO2;
377         int AP1;
378         int PN3;
379 
380         for (SO2 = SOAG.Rule[R].SymOcc.Beg; SO2 <= SOAG.Rule[R].SymOcc.End; ++SO2)
381         {
382             if (SOAG.SymOcc[SO2].SymInd == S)
383             {
384                 AP1 = SOAG.SymOcc[SO2].AffOcc.Beg + A;
385                 PN3 = GetEVSPosforAffOcc(R, AP1);
386                 if (PN1 < PN3 && PN3 < PN2)
387                     disjoint = false;
388             }
389         }
390     }
391 
392     /**
393      * IN: aktuelle Regel, zwei Position in der EVS
394      */
395     void CheckT2P4(int R, int SO, int PN1, int PN2)
396     {
397         int S2;
398         int SO2;
399         int VN3;
400         int PN3;
401 
402         for (int t = ALists.firstIndex; t <= VS.Last; t += 2)
403         {
404             S2 = VS.Elem[t];
405             VN3 = VS.Elem[t + 1];
406             SO2 = SOAG.Sym[S2].FirstOcc;
407             while (SO2 != SOAG.nil)
408             {
409                 if (R == SOAG.SymOcc[SO2].RuleInd && SOAG.Rule[R].SymOcc.Beg != SO2 && SO != SO2)
410                 {
411                     PN3 = GetEVSPosforVisit(R, SO2, VN3);
412                     if (PN1 < PN3 && PN3 < PN2)
413                         disjoint = false;
414                 }
415                 SO2 = SOAG.SymOcc[SO2].Next;
416             }
417         }
418     }
419 
420     /**
421      * IN: aktuelle Regel, zwei Position in der EVS
422      */
423     void CheckT1P4(int R, int SO, int PN1, int PN2)
424     {
425         int S2;
426         int SO2;
427         int VN3;
428         int VN4;
429         int PN3;
430         int PN4;
431 
432         for (int t = ALists.firstIndex; t <= VDS.Last; t += 3)
433         {
434             S2 = VDS.Elem[t];
435             VN3 = VDS.Elem[t + 1];
436             VN4 = VDS.Elem[t + 2];
437             SO2 = SOAG.Sym[S2].FirstOcc;
438             while (SO2 != SOAG.nil)
439             {
440                 if (R == SOAG.SymOcc[SO2].RuleInd && SOAG.Rule[R].SymOcc.Beg != SO2 && SO != SO2)
441                 {
442                     PN3 = GetEVSPosforVisit(R, SO2, VN3);
443                     PN4 = GetEVSPosforVisit(R, SO2, VN4);
444                     if (PN1 < PN3 && PN3 < PN2 && PN2 < PN4)
445                         admissible = false;
446                 }
447                 SO2 = SOAG.SymOcc[SO2].Next;
448             }
449         }
450     }
451 
452     SO = SOAG.Sym[S].FirstOcc;
453     while (SO != SOAG.nil)
454     {
455         AP1 = SOAG.SymOcc[SO].AffOcc.Beg + A;
456         AN1 = SOAG.AffOcc[AP1].AffOccNum.InRule;
457         R = SOAG.SymOcc[SO].RuleInd;
458         if (SOAG.IsEvaluatorRule(R))
459         {
460             PN1 = GetEVSPosforAffOcc(R, AP1);
461             for (AP2 = SOAG.Rule[R].AffOcc.Beg; AP2 <= SOAG.Rule[R].AffOcc.End; ++AP2)
462             {
463                 AN2 = SOAG.AffOcc[AP2].AffOccNum.InRule;
464                 if (SOAG.Rule[R].DP[AN1][AN2])
465                 {
466                     PN2 = GetEVSPosforAffOcc(R, AP2);
467                     CheckT2P1andT1P1(S, A, R, PN1, PN2);
468                     CheckT2P2(R, PN1, PN2);
469                     CheckT1P2andP3(R, PN1, PN2);
470                 }
471             }
472         }
473         SO = SOAG.SymOcc[SO].Next;
474     }
475     for (int t = ALists.firstIndex; t <= VDS.Last; t += 3)
476     {
477         S1 = VDS.Elem[t];
478         VN1 = VDS.Elem[t + 1];
479         VN2 = VDS.Elem[t + 2];
480         SO1 = SOAG.Sym[S1].FirstOcc;
481         while (SO1 != SOAG.nil)
482         {
483             R = SOAG.SymOcc[SO1].RuleInd;
484             if (SOAG.IsEvaluatorRule(R))
485             {
486                 if (SOAG.Rule[R].SymOcc.Beg != SO1)
487                 {
488                     PN1 = GetEVSPosforVisit(R, SO1, VN1);
489                     PN2 = GetEVSPosforVisit(R, SO1, VN2);
490                     CheckT2P3(S, A, R, PN1, PN2);
491                     CheckT2P4(R, SO1, PN1, PN2);
492                     CheckT1P4(R, SO1, PN1, PN2);
493                 }
494             }
495             SO1 = SOAG.SymOcc[SO1].Next;
496         }
497     }
498 }
499 
500 void Optimize() nothrow
501 {
502     Init;
503     GlobalVar = firstGlobalVar - 1;
504     StackVar = firstStackVar - 1;
505     foreach (S; EAG.All.bitsSet)
506     {
507         for (int AP = SOAG.Sym[S].AffPos.Beg; AP <= SOAG.Sym[S].AffPos.End; ++AP)
508         {
509             const A = AP - SOAG.Sym[S].AffPos.Beg;
510 
511             if (!EAG.Pred[S] || SOAG.IsSynthesized(S, A))
512             {
513                 disjoint = true;
514                 admissible = true;
515                 InitVDSandVS(S, A);
516                 CompleteInitVDS;
517                 CheckStorageType(S, A);
518                 if (disjoint)
519                 {
520                     ++GlobalVar;
521                     SOAG.StorageName[AP] = -GlobalVar;
522                 }
523                 else if (admissible)
524                 {
525                     ++StackVar;
526                     SOAG.StorageName[AP] = StackVar;
527                 }
528             }
529         }
530     }
531 }