URL https://opencores.org/ocsvn/thor/thor/trunk

Subversion Repositories thor

[/] [thor/] [trunk/] [FT64v5/] [software/] [CC64/] [source/] [IGraph.cpp] - Blame information for rev 48

Details | Compare with Previous | View Log


// ============================================================================
//        __
//   \\__/ o\    (C) 2018  Robert Finch, Waterloo
//    \  __ /    All rights reserved.
//     \/_//     robfinch<remove>@finitron.ca
//       ||
//
// CC64 - 'C' derived language compiler
//  - 64 bit CPU
//
// This source file is free software: you can redistribute it and/or modify 
// it under the terms of the GNU Lesser General Public License as published 
// by the Free Software Foundation, either version 3 of the License, or     
// (at your option) any later version.                                      
//                                                                          
// This source file is distributed in the hope that it will be useful,      
// but WITHOUT ANY WARRANTY; without even the implied warranty of           
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the            
// GNU General Public License for more details.                             
//                                                                          
// You should have received a copy of the GNU General Public License        
// along with this program.  If not, see <http://www.gnu.org/licenses/>.    
//                                                                          
// ============================================================================
//
#include "stdafx.h"
 
 
// This interference graph uses a bit set to represent the adjacency vectors.
// Unless doing whole program optimizations the number of basic blocks 
// encountered in any function is likely to be a small number (< 100).
// 
 
void IGraph::MakeNew(int n)
{
        int bms;
 
        K = 17;
        size = n;
        bms = n * n / sizeof(int);
        bitmatrix = new int[bms];
        degrees = new short int[n];
        vecs = new int *[n];
        ZeroMemory(vecs, n * sizeof(int *));
        Clear();
}
 
IGraph::~IGraph()
{
//      Destroy();
}
 
void IGraph::Destroy()
{
        int n;
 
        delete[] bitmatrix;
        delete[] degrees;
        for (n = 0; n < size; n++) {
                //if (vecs[n])
                //      delete[] vecs[n];
        }
        delete[] vecs;
}
 
void IGraph::ClearBitmatrix()
{
        int j;
 
        j = size * size / sizeof(int);
        ZeroMemory(bitmatrix, j);
}
 
void IGraph::Clear()
{
        ClearBitmatrix();
        ZeroMemory(degrees, size * sizeof(short int));
}
 
 
// Called after the first fill pass to allocate storage for vectors.
 
void IGraph::AllocVecs()
{
        int x;
 
        for (x = 0; x < size; x++) {
                vecs[x] = new int[degrees[x]];
        }
}
 
int IGraph::BitIndex(int x, int y, int *intndx, int *bitndx)
{
        if (x > y)
                throw new C64PException(ERR_IGNODES, 1);
        *bitndx = x + (y * y + 1) / 2;
        *intndx = *bitndx / sizeof(int);
        *bitndx %= (sizeof(int) * 8);
        return (x + (y * y + 1) / 2);
}
 
// Two passes are made in order to determine the size of 
// the adjacency vector array for the node. The first pass
// just determines the degree.
// The number of adjacency vectors stored is stored in the
// first element of the array.
 
void IGraph::Add(int x, int y)
{
        int bitndx;
        int intndx;
 
        if (x == y)
                return;
        BitIndex(x,y,&intndx,&bitndx);
        bitmatrix[intndx] |= (1 << bitndx);
        AddToVec(x, y);
        AddToVec(y, x);
}
 
 
// Used to update the vector table.
 
void IGraph::AddToVec(int x, int y)
{
        int nn;
 
        if (pass > 1) {
                // ensure the y isn't already in the table
                for (nn = 0; nn < degrees[x]; nn++) {
                        if (vecs[x][nn] == y)
                                break;
                }
                if (nn >= degrees[x]) {
                        vecs[x][degrees[x]] = y;
                        degrees[x]++;
                }
        }
        else
                degrees[x]++;
}
 
// A slightly faster version of Add used when father and son nodes are united.
// We don't want to add back to the son's.
 
void IGraph::Add2(int x, int y)
{
        int bitndx;
        int intndx;
        int x1, y1;
 
        if (x == y)
                return;
        x1 = min(x, y);
        y1 = max(x, y);
        BitIndex(x1, y1, &intndx, &bitndx);
        bitmatrix[intndx] |= (1 << bitndx);
        AddToVec(x1, y1);
}
 
bool IGraph::Remove(int n)
{
        int bitndx;
        int intndx;
        int j, m, nn, mm, n1, m1;
        bool updated = false;
 
        for (j = 0; j < degrees[n]; j++) {
                m = vecs[n][j];
                if (degrees[m] > 0) {
                        for (mm = nn = 0; nn < degrees[m]; nn++) {
                                if (vecs[m][nn] != n) {
                                        vecs[m][mm] = vecs[m][nn];
                                        mm++;
                                }
                        }
                        degrees[m]--;
                        if (degrees[m] == K-1 && !frst->trees[m]->infinite) {
                                frst->high.remove(m);
                                frst->low.add(m);
                                updated = true;
                        }
                }
                //n1 = min(n, m);
                //m1 = max(n, m);
                //BitIndex(n1, m1, &intndx, &bitndx);
                //bitmatrix[intndx] &= ~(1 << bitndx);
        }
        return (updated);
}
 
bool IGraph::DoesInterfere(int x, int y)
{
        int bitndx;
        int intndx;
 
        if (x == y) return (true);
        //return !(frst->trees[x]->blocks->isDisjoint(*frst->trees[y]->blocks));
        bitndx = BitIndex(x, y, &intndx, &bitndx);
        return (((bitmatrix[intndx] >> bitndx) & 1)==1);
}
 
 
// Move adjacency vectors across graph from son to father.
 
void IGraph::Unite(int father, int son)
{
        int j;
        int *tmp;
 
        if (father > son)
                throw new C64PException(ERR_IGNODES, 2);
 
        // Increase the size of the adjacency vector allocation for the father as
        // the son's vectors will be added to them.
        tmp = new int [degrees[father] + degrees[son] + 1];
        ZeroMemory(tmp, (degrees[father] + degrees[son] + 1) * sizeof(int));
        if (vecs[father]) {
                memcpy(tmp, vecs[father], degrees[father] * sizeof(int));
                //delete[] vecs[father];
        }
        vecs[father] = tmp;
 
        if (vecs[son]) {
                for (j = 0; j < degrees[son]; j++) {
                        Add2(father, vecs[son][j]);
                }
                degrees[son] = 0;
        }
}
 
// Only consider adding trees that have not yet been colored to the live set.
 
void IGraph::AddToLive(BasicBlock *b, Operand *ap, OCODE *ip)
{
        int v;
 
        v = FindTreeno(ap->preg, ip->bb->num);
        if (v >= 0) {
                if (frst->trees[v]->color == K)
                        b->live->add(v);
        }
        if (ap->sreg) {
                v = FindTreeno(ap->sreg, ip->bb->num);
                if (v >= 0) {
                        if (frst->trees[v]->color == K)
                                b->live->add(v);
                }
        }
}
 
void IGraph::Fill()
{
        int n, n1;
        BasicBlock *b;
        int v, v1;
        OCODE *ip;
        bool eol;
        int K = 17;
 
        // For each block 
        for (b = currentFn->RootBlock; b; b = b->next) {
                b->BuildLivesetFromLiveout();
                eol = false;
                for (ip = b->lcode; ip && !eol; ip = ip->back) {
                        if (ip->opcode != op_label) {
                                // examine instruction ip and update graph and live
                                if (ip->opcode == op_mov) {
                                        v = FindTreeno(ip->oper1->preg, ip->bb->num);
                                        if (v >= 0 && frst->trees[v]->color == K) {
                                                b->live->remove(v);
                                        }
                                }
                                if (ip->insn->HasTarget()) {
                                        v = FindTreeno(ip->oper1->preg, ip->bb->num);
                                        if (v >= 0 && frst->trees[v]->color==K) {
                                                b->live->resetPtr();
                                                for (n = b->live->nextMember(); n >= 0; n = b->live->nextMember()) {
                                                        n1 = min(n, v);
                                                        v1 = max(n, v);
                                                        iGraph.Add(n1, v1);
                                                }
                                                b->live->remove(v);
                                        }
                                }
                                // Unrolled loop
                                // while (p < ik->uses)
                                if (!ip->insn->HasTarget() && ip->oper1)
                                        AddToLive(b, ip->oper1, ip);
                                if (ip->oper2)
                                        AddToLive(b, ip->oper2, ip);
                                if (ip->oper3)
                                        AddToLive(b, ip->oper3, ip);
                                if (ip->oper4)
                                        AddToLive(b, ip->oper4, ip);
                        }
                        eol = ip == b->code;
                }
        }
}
 
 
void IGraph::InsertArgumentMoves()
{
        int nn, mm, blk;
        Var *v;
        Tree *t;
 
        for (nn = regFirstArg; nn <= regLastArg; nn++) {
                mm = map.newnums[nn];
                if (mm >= 0) {
                        if (v = Var::Find2(mm)) {                               // find the forest
                                for (mm = 0; mm < v->trees.treecount; mm++) {    // search the trees
                                        t = v->trees.trees[mm];
                                        t->blocks->resetPtr();
                                        blk = t->blocks->nextMember();  // The lowest block # will be the head of the tree
                                        if (blk >= 0)
                                                BasicBlock::InsertMove(map.newnums[nn], t->var, blk);
                                }
                        }
                }
        }
}
 
void IGraph::BuildAndCoalesce()
{
        bool improved = false;
 
        MakeNew(frst->treecount);
        frst->CalcRegclass();
 
        // Insert move operations to handle register parameters. We want to do this
        // only once.
        if (forest.pass == 1)
                InsertArgumentMoves();
 
        // Vist high-priority blocks (blocks in nested loops) first, so sort the
        // blocks according to depth.
        BasicBlock::DepthSort();
 
        // On the first pass we just want to determine the degree of the nodes so
        // that storage for vectors can be allocated.
        pass = 1;
        Clear();
        Fill();
        AllocVecs();
 
        pass = 2;
        do {
                Clear();
                Fill();
                Print(2);
                improved = BasicBlock::Coalesce();
                //improved = Var::Coalesce2();
                //IRemove();
        } while (improved);
        //Destroy();    // needed in Simplify()
}
 
void IGraph::Print(int n)
{
        int nn, mm;
 
        dfs.printf("<IGraph>%d\n", n);
        for (nn = 0; nn < size; nn++) {
                dfs.printf("Degrees[%d]=%d ", nn, degrees[nn]);
                dfs.printf("Neighbours are: ");
                for (mm = 0; mm < degrees[nn]; mm++) {
                        dfs.printf("%d ", vecs[nn][mm]);
                }
                dfs.printf("\n");
        }
        dfs.printf("</IGraph>\n");
}

Browse

Tools

Subversion Repositories thor

[/] [thor/] [trunk/] [FT64v5/] [software/] [CC64/] [source/] [IGraph.cpp] - Blame information for rev 48

Line No.	Rev	Author	Line
1	48	robfinch	`// ============================================================================`
2			`// __`
3			`// \\__/ o\ (C) 2018 Robert Finch, Waterloo`
4			`// \ __ / All rights reserved.`
5			`// \/_// robfinch<remove>@finitron.ca`
6			`// \|\|`
7			`//`
8			`// CC64 - 'C' derived language compiler`
9			`// - 64 bit CPU`
10			`//`
11			`// This source file is free software: you can redistribute it and/or modify`
12			`// it under the terms of the GNU Lesser General Public License as published`
13			`// by the Free Software Foundation, either version 3 of the License, or`
14			`// (at your option) any later version.`
15			`//`
16			`// This source file is distributed in the hope that it will be useful,`
17			`// but WITHOUT ANY WARRANTY; without even the implied warranty of`
18			`// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the`
19			`// GNU General Public License for more details.`
20			`//`
21			`// You should have received a copy of the GNU General Public License`
22			`// along with this program. If not, see <http://www.gnu.org/licenses/>.`
23			`//`
24			`// ============================================================================`
25			`//`
26			`#include "stdafx.h"`
27
28
29			`// This interference graph uses a bit set to represent the adjacency vectors.`
30			`// Unless doing whole program optimizations the number of basic blocks`
31			`// encountered in any function is likely to be a small number (< 100).`
32			`//`
33
34			`void IGraph::MakeNew(int n)`
35			`{`
36			`int bms;`
37
38			`K = 17;`
39			`size = n;`
40			`bms = n * n / sizeof(int);`
41			`bitmatrix = new int[bms];`
42			`degrees = new short int[n];`
43			`vecs = new int *[n];`
44			`ZeroMemory(vecs, n * sizeof(int *));`
45			`Clear();`
46			`}`
47
48			`IGraph::~IGraph()`
49			`{`
50			`// Destroy();`
51			`}`
52
53			`void IGraph::Destroy()`
54			`{`
55			`int n;`
56
57			`delete[] bitmatrix;`
58			`delete[] degrees;`
59			`for (n = 0; n < size; n++) {`
60			`//if (vecs[n])`
61			`// delete[] vecs[n];`
62			`}`
63			`delete[] vecs;`
64			`}`
65
66			`void IGraph::ClearBitmatrix()`
67			`{`
68			`int j;`
69
70			`j = size * size / sizeof(int);`
71			`ZeroMemory(bitmatrix, j);`
72			`}`
73
74			`void IGraph::Clear()`
75			`{`
76			`ClearBitmatrix();`
77			`ZeroMemory(degrees, size * sizeof(short int));`
78			`}`
79
80
81			`// Called after the first fill pass to allocate storage for vectors.`
82
83			`void IGraph::AllocVecs()`
84			`{`
85			`int x;`
86
87			`for (x = 0; x < size; x++) {`
88			`vecs[x] = new int[degrees[x]];`
89			`}`
90			`}`
91
92			`int IGraph::BitIndex(int x, int y, int intndx, int bitndx)`
93			`{`
94			`if (x > y)`
95			`throw new C64PException(ERR_IGNODES, 1);`
96			`bitndx = x + (y y + 1) / 2;`
97			`intndx = bitndx / sizeof(int);`
98			`bitndx %= (sizeof(int) 8);`
99			`return (x + (y * y + 1) / 2);`
100			`}`
101
102			`// Two passes are made in order to determine the size of`
103			`// the adjacency vector array for the node. The first pass`
104			`// just determines the degree.`
105			`// The number of adjacency vectors stored is stored in the`
106			`// first element of the array.`
107
108			`void IGraph::Add(int x, int y)`
109			`{`
110			`int bitndx;`
111			`int intndx;`
112
113			`if (x == y)`
114			`return;`
115			`BitIndex(x,y,&intndx,&bitndx);`
116			`bitmatrix[intndx] \|= (1 << bitndx);`
117			`AddToVec(x, y);`
118			`AddToVec(y, x);`
119			`}`
120
121
122			`// Used to update the vector table.`
123
124			`void IGraph::AddToVec(int x, int y)`
125			`{`
126			`int nn;`
127
128			`if (pass > 1) {`
129			`// ensure the y isn't already in the table`
130			`for (nn = 0; nn < degrees[x]; nn++) {`
131			`if (vecs[x][nn] == y)`
132			`break;`
133			`}`
134			`if (nn >= degrees[x]) {`
135			`vecs[x][degrees[x]] = y;`
136			`degrees[x]++;`
137			`}`
138			`}`
139			`else`
140			`degrees[x]++;`
141			`}`
142
143			`// A slightly faster version of Add used when father and son nodes are united.`
144			`// We don't want to add back to the son's.`
145
146			`void IGraph::Add2(int x, int y)`
147			`{`
148			`int bitndx;`
149			`int intndx;`
150			`int x1, y1;`
151
152			`if (x == y)`
153			`return;`
154			`x1 = min(x, y);`
155			`y1 = max(x, y);`
156			`BitIndex(x1, y1, &intndx, &bitndx);`
157			`bitmatrix[intndx] \|= (1 << bitndx);`
158			`AddToVec(x1, y1);`
159			`}`
160
161			`bool IGraph::Remove(int n)`
162			`{`
163			`int bitndx;`
164			`int intndx;`
165			`int j, m, nn, mm, n1, m1;`
166			`bool updated = false;`
167
168			`for (j = 0; j < degrees[n]; j++) {`
169			`m = vecs[n][j];`
170			`if (degrees[m] > 0) {`
171			`for (mm = nn = 0; nn < degrees[m]; nn++) {`
172			`if (vecs[m][nn] != n) {`
173			`vecs[m][mm] = vecs[m][nn];`
174			`mm++;`
175			`}`
176			`}`
177			`degrees[m]--;`
178			`if (degrees[m] == K-1 && !frst->trees[m]->infinite) {`
179			`frst->high.remove(m);`
180			`frst->low.add(m);`
181			`updated = true;`
182			`}`
183			`}`
184			`//n1 = min(n, m);`
185			`//m1 = max(n, m);`
186			`//BitIndex(n1, m1, &intndx, &bitndx);`
187			`//bitmatrix[intndx] &= ~(1 << bitndx);`
188			`}`
189			`return (updated);`
190			`}`
191
192			`bool IGraph::DoesInterfere(int x, int y)`
193			`{`
194			`int bitndx;`
195			`int intndx;`
196
197			`if (x == y) return (true);`
198			`//return !(frst->trees[x]->blocks->isDisjoint(*frst->trees[y]->blocks));`
199			`bitndx = BitIndex(x, y, &intndx, &bitndx);`
200			`return (((bitmatrix[intndx] >> bitndx) & 1)==1);`
201			`}`
202
203
204			`// Move adjacency vectors across graph from son to father.`
205
206			`void IGraph::Unite(int father, int son)`
207			`{`
208			`int j;`
209			`int *tmp;`
210
211			`if (father > son)`
212			`throw new C64PException(ERR_IGNODES, 2);`
213
214			`// Increase the size of the adjacency vector allocation for the father as`
215			`// the son's vectors will be added to them.`
216			`tmp = new int [degrees[father] + degrees[son] + 1];`
217			`ZeroMemory(tmp, (degrees[father] + degrees[son] + 1) * sizeof(int));`
218			`if (vecs[father]) {`
219			`memcpy(tmp, vecs[father], degrees[father] * sizeof(int));`
220			`//delete[] vecs[father];`
221			`}`
222			`vecs[father] = tmp;`
223
224			`if (vecs[son]) {`
225			`for (j = 0; j < degrees[son]; j++) {`
226			`Add2(father, vecs[son][j]);`
227			`}`
228			`degrees[son] = 0;`
229			`}`
230			`}`
231
232			`// Only consider adding trees that have not yet been colored to the live set.`
233
234			`void IGraph::AddToLive(BasicBlock b, Operand ap, OCODE *ip)`
235			`{`
236			`int v;`
237
238			`v = FindTreeno(ap->preg, ip->bb->num);`
239			`if (v >= 0) {`
240			`if (frst->trees[v]->color == K)`
241			`b->live->add(v);`
242			`}`
243			`if (ap->sreg) {`
244			`v = FindTreeno(ap->sreg, ip->bb->num);`
245			`if (v >= 0) {`
246			`if (frst->trees[v]->color == K)`
247			`b->live->add(v);`
248			`}`
249			`}`
250			`}`
251
252			`void IGraph::Fill()`
253			`{`
254			`int n, n1;`
255			`BasicBlock *b;`
256			`int v, v1;`
257			`OCODE *ip;`
258			`bool eol;`
259			`int K = 17;`
260
261			`// For each block`
262			`for (b = currentFn->RootBlock; b; b = b->next) {`
263			`b->BuildLivesetFromLiveout();`
264			`eol = false;`
265			`for (ip = b->lcode; ip && !eol; ip = ip->back) {`
266			`if (ip->opcode != op_label) {`
267			`// examine instruction ip and update graph and live`
268			`if (ip->opcode == op_mov) {`
269			`v = FindTreeno(ip->oper1->preg, ip->bb->num);`
270			`if (v >= 0 && frst->trees[v]->color == K) {`
271			`b->live->remove(v);`
272			`}`
273			`}`
274			`if (ip->insn->HasTarget()) {`
275			`v = FindTreeno(ip->oper1->preg, ip->bb->num);`
276			`if (v >= 0 && frst->trees[v]->color==K) {`
277			`b->live->resetPtr();`
278			`for (n = b->live->nextMember(); n >= 0; n = b->live->nextMember()) {`
279			`n1 = min(n, v);`
280			`v1 = max(n, v);`
281			`iGraph.Add(n1, v1);`
282			`}`
283			`b->live->remove(v);`
284			`}`
285			`}`
286			`// Unrolled loop`
287			`// while (p < ik->uses)`
288			`if (!ip->insn->HasTarget() && ip->oper1)`
289			`AddToLive(b, ip->oper1, ip);`
290			`if (ip->oper2)`
291			`AddToLive(b, ip->oper2, ip);`
292			`if (ip->oper3)`
293			`AddToLive(b, ip->oper3, ip);`
294			`if (ip->oper4)`
295			`AddToLive(b, ip->oper4, ip);`
296			`}`
297			`eol = ip == b->code;`
298			`}`
299			`}`
300			`}`
301
302
303			`void IGraph::InsertArgumentMoves()`
304			`{`
305			`int nn, mm, blk;`
306			`Var *v;`
307			`Tree *t;`
308
309			`for (nn = regFirstArg; nn <= regLastArg; nn++) {`
310			`mm = map.newnums[nn];`
311			`if (mm >= 0) {`
312			`if (v = Var::Find2(mm)) { // find the forest`
313			`for (mm = 0; mm < v->trees.treecount; mm++) { // search the trees`
314			`t = v->trees.trees[mm];`
315			`t->blocks->resetPtr();`
316			`blk = t->blocks->nextMember(); // The lowest block # will be the head of the tree`
317			`if (blk >= 0)`
318			`BasicBlock::InsertMove(map.newnums[nn], t->var, blk);`
319			`}`
320			`}`
321			`}`
322			`}`
323			`}`
324
325			`void IGraph::BuildAndCoalesce()`
326			`{`
327			`bool improved = false;`
328
329			`MakeNew(frst->treecount);`
330			`frst->CalcRegclass();`
331
332			`// Insert move operations to handle register parameters. We want to do this`
333			`// only once.`
334			`if (forest.pass == 1)`
335			`InsertArgumentMoves();`
336
337			`// Vist high-priority blocks (blocks in nested loops) first, so sort the`
338			`// blocks according to depth.`
339			`BasicBlock::DepthSort();`
340
341			`// On the first pass we just want to determine the degree of the nodes so`
342			`// that storage for vectors can be allocated.`
343			`pass = 1;`
344			`Clear();`
345			`Fill();`
346			`AllocVecs();`
347
348			`pass = 2;`
349			`do {`
350			`Clear();`
351			`Fill();`
352			`Print(2);`
353			`improved = BasicBlock::Coalesce();`
354			`//improved = Var::Coalesce2();`
355			`//IRemove();`
356			`} while (improved);`
357			`//Destroy(); // needed in Simplify()`
358			`}`
359
360			`void IGraph::Print(int n)`
361			`{`
362			`int nn, mm;`
363
364			`dfs.printf("<IGraph>%d\n", n);`
365			`for (nn = 0; nn < size; nn++) {`
366			`dfs.printf("Degrees[%d]=%d ", nn, degrees[nn]);`
367			`dfs.printf("Neighbours are: ");`
368			`for (mm = 0; mm < degrees[nn]; mm++) {`
369			`dfs.printf("%d ", vecs[nn][mm]);`
370			`}`
371			`dfs.printf("\n");`
372			`}`
373			`dfs.printf("</IGraph>\n");`
374			`}`