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

Subversion Repositories thor

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

Details | Compare with Previous | View Log


// ============================================================================
//        __
//   \\__/ o\    (C) 2017-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"
 
extern OCODE *peep_head;
extern BasicBlock *basicBlocks[10000];
extern Instruction *GetInsn(int);
 
void CFG::Create()
{
        OCODE *ip, *ip1;
        int nn;
        struct scase *cs;
 
        for (ip = peep_head; ip; ip = ip->fwd) {
                if (ip->leader) {
                if (ip->back) {
                // if not unconditional control transfer
                        if (ip->back->opcode != op_ret && ip->back->opcode != op_bra && ip->back->opcode!=op_jmp) {
                                ip->back->bb->MakeOutputEdge(ip->bb);
                                ip->bb->MakeInputEdge(ip->back->bb);
                        }
                }
                }
                //}
                switch(ip->opcode) {
                case op_bex:
                case op_bra:
                case op_jmp:
                        if (ip->oper1->offset) {
                                if (ip1 = FindLabel(ip->oper1->offset->i)) {
                                        ip->bb->MakeOutputEdge(ip1->bb);
                                        ip1->bb->MakeInputEdge(ip->bb);
                                }
                        }
                        break;
                case op_beq:
                case op_bne:
                case op_blt:
                case op_bge:
                case op_ble:
                case op_bgt:
                case op_bltu:
                case op_bgeu:
                case op_bleu:
                case op_bgtu:
                case op_bbs:
                case op_bbc:
                case op_beqi:
                case op_ibne:
                        if (0) {
                                if (ip->oper1->mode==am_reg && ip->back && ip->back->oper3) {
                                        if (ip1 = FindLabel(ip->back->oper3->offset->i)) {
                                                ip->bb->MakeOutputEdge(ip1->bb);
                                                ip1->bb->MakeInputEdge(ip->bb);
                                        }
                                }
                        }
                        else {
                                if (ip1 = FindLabel(ip->oper3->offset->i)) {
                                        ip->bb->MakeOutputEdge(ip1->bb);
                                        ip1->bb->MakeInputEdge(ip->bb);
                                }
                        }
                        break;
                case op_bchk:
                        if (ip1 = FindLabel(ip->oper4->offset->i)) {
                                ip->bb->MakeOutputEdge(ip1->bb);
                                ip1->bb->MakeInputEdge(ip->bb);
                        }
                        break;
                case op_jal:
                        // Was it a switch statement ?
                        if (ip->oper3) {
                                for (nn = 1; nn < ((struct scase *)(ip->oper3))->label; nn++) {
                                        cs = &((struct scase *)(ip->oper3))[1];
                                        ip1 = FindLabel(cs->label);
                                        if (ip1) {
                                                ip->bb->MakeOutputEdge(ip1->bb);
                                                ip1->bb->MakeInputEdge(ip->bb);
                                        }
                                }
                        }
                        else {
                                // Could be a jal [LR] for a ret statement in which case there's
                                // only one operand.
                                if (ip->oper2) {
                                        if (ip->oper2->mode != am_reg) {
                                                if (ip1 = FindLabel(ip->oper2->offset->i)) {
                                                        ip->bb->MakeOutputEdge(ip1->bb);
                                                        ip1->bb->MakeInputEdge(ip->bb);
                                                }
                                        }
                                }
                        }
                        break;
                }
        }
}
 
static CSet *visited;
static CSet *paths[1000];
static int npaths;
 
// Walk down the path beginning at block b.
 
static void DownPath(BasicBlock *b)
{
        Edge *e;
        int path;
        bool first;
 
        if (visited->isMember(b->num))
                return;
        path = npaths-1;
        paths[path]->add(b->num);
        visited->add(b->num);
        first = true;
        for (e = b->ohead; e; e = e->next) {
                if (!first) {
                        paths[npaths] = CSet::MakeNew();
                        paths[npaths]->add(paths[path]);
                        npaths++;
                }
//              if (!e->backedge) {
                        first = false;
                        DownPath(e->dst);
//              }
        }
}
 
// Discover all the paths in the CFG.
 
static void DiscoverPaths()
{
        BasicBlock *b;
        int n;
        char buf[2000];
 
        b = currentFn->RootBlock;
        visited = CSet::MakeNew();
        paths[0] = CSet::MakeNew();
        paths[0]->add(b->num);
        npaths = 1;
        DownPath(b);
        dfs.printf("<Paths>\n");
        for (n = 0; n < npaths; n++) {
                paths[n]->sprint(buf, sizeof(buf));
                dfs.printf("%d: ", n);
                dfs.printf("%s\n", buf);
        }
        dfs.printf("</Paths>\n");
}
 
 
void CFG::CalcDominatorTree()
{
        int n, m, o, ps;
        CSet *pathSet;
        bool oInAllPaths;
 
        DiscoverPaths();
        pathSet = CSet::MakeNew();
        for (n = currentFn->LastBlock->num; n >= 1; n--) {
                pathSet->clear();
                // Get all paths that contain n
                for (m = 0; m < npaths; m++)
                        if (paths[m]->isMember(n))
                                pathSet->add(m);
                // If o is in all paths to n, then o dominates over n. Note there could
                // be several o's that dominate over n. We only want the last one to do
                // so. So we start the search at n-1 and work backwards.
                for (o = n - 1; o >= 0; o--) {
                        oInAllPaths = true;
                        pathSet->resetPtr();
                        for (ps = pathSet->nextMember(); ps >= 0; ps=pathSet->nextMember()) {
                                if (!paths[ps]->isMember(o)) {
                                        oInAllPaths = false;
                                        break;
                                }
                        }
                        if (oInAllPaths)
                                break;
                }
                basicBlocks[o]->MakeDomEdge(basicBlocks[n]);
        }
}
 
void CFG::CalcDominanceFrontiers()
{
        BasicBlock *x;
        Edge *e;
        Edge *z;
        int y;
 
        CalcDominatorTree();
        for (x = currentFn->LastBlock; x; x = x->prev) {
                x->DF = nullptr;
                if (x->dhead) {
                        x->DF = CSet::MakeNew();
                        // Check the successors of X
                        for (e = x->ohead; e; e = e->next) {
                                if (!x->IsIdom(e->dst)) {
                                        x->DF->add(e->dst->num);
                                }
                        }
                        // Check the children of X
                        for (z = x->dhead; z; z = z->next) {
                                if (z->dst->DF) {
                                        z->dst->DF->resetPtr();
                                        for (y = z->dst->DF->nextMember(); y >= 0; y = z->dst->DF->nextMember()) {
                                                if (!x->IsIdom(basicBlocks[y]))
                                                        x->DF->add(y);
                                        }
                                }
                        }
                }
        }
}
 
void CFG::InsertPhiInsns()
{
        BasicBlock *x;
        OCODE *phiNode, *ip;
        CSet *w;
        Var *v;
        Edge *e;
        int IterCount = 0;
        int n, m, y;
 
        w = CSet::MakeNew();
        for (x = currentFn->RootBlock; x; x = x->next) {
                x->HasAlready = 0;
                x->Work = 0;
        }
        w->clear();
        for (v = currentFn->varlist; v; v = v->next) {
                // Don't bother considering r0 which always contains the constant zero.
                if (v->num==0)
                        continue;
                IterCount++;
                v->forest->resetPtr();
                for (n = v->forest->nextMember(); n >= 0; n = v->forest->nextMember()) {
                        x = basicBlocks[n];
                        x->Work = IterCount;
                        w->add(x->num);
                }
                w->resetPtr();
                while (w->NumMember() > 0) {
                        n = w->nextMember();
                        if (n < 0) {
                                w->resetPtr();
                                n = w->nextMember();
                                if (n < 0)
                                        break;
                        }
                        w->remove(n);
                        x = basicBlocks[n];
                        if (x->DF) {
                                x->DF->resetPtr();
                                for (y = x->DF->nextMember(); y >= 0; y = x->DF->nextMember()) {
                                        if (basicBlocks[y]->HasAlready < IterCount) {
                                                // Place phi node at Y
                                                phiNode = (OCODE *)allocx(sizeof(OCODE));
                                                phiNode->insn = GetInsn(op_phi);
                                                phiNode->opcode = op_phi;
                                                phiNode->oper1 = makereg(v->num);
                                                phiNode->bb = basicBlocks[y];
                                                m = 0;
                                                for (e = phiNode->bb->ihead; e && m < 100; e = e->next) {
                                                        phiNode->phiops[m] = e->src->num;
                                                        m++;
                                                }
                                                ip = basicBlocks[y]->code;
                                                while (ip && ip->opcode==op_label) ip = ip->fwd;
                                                // For now this is disabled.
                                                // Peep::InsertBefore(ip,phiNode);
                                                basicBlocks[y]->HasAlready = IterCount;
                                                if (basicBlocks[y]->Work < IterCount) {
                                                        basicBlocks[y]->Work = IterCount;
                                                        w->add(y);
                                                }
                                        }
                                }
                        }
                }
        }
}
 
 
// Get the ordinal of which predecessor X is of Y.
 
int CFG::WhichPred(BasicBlock *x, int y)
{
        BasicBlock *b;
        Edge *e;
        int n;
 
        b = basicBlocks[y];
        n = 0;
        for (e = b->ihead; e; e = e->next) {
                if (e->src==x)
                        return (n);
                n++;
        }
        return (-1);
}
 
// Set a subscript on a variable.
 
void CFG::Subscript(Operand *oper)
{
        Var *v;
 
        if (oper) {
                v = Var::FindByMac(oper->preg);
                if (v)
                        oper->pregs = v->istk->tos();
                v = Var::FindByMac(oper->sreg);
                if (v)
                        oper->sregs = v->istk->tos();
        }
}
 
void CFG::Search(BasicBlock *x)
{
        OCODE *s;
        BasicBlock *b;
        Var *v;
        Edge *e;
        int i, j, y;
        bool eol;
        int rg1, rg2;
 
        eol = false;
        for (s = x->code; s && !eol; s = s->fwd) {
                if (s->opcode!=op_label) {
                        if (s->oper1 && !s->HasTargetReg())
                                Subscript(s->oper1);
                        if (s->oper2)
                                Subscript(s->oper2);
                        if (s->oper3)
                                Subscript(s->oper3);
                        if (s->oper4)
                                Subscript(s->oper4);
                        if (s->oper1 && s->HasTargetReg()) {
                                s->GetTargetReg(&rg1, &rg2);
                                v = Var::FindByMac(rg1);
                                if (v) {
                                        i = v->subscript;
                                        s->oper1->pregs = i;
                                        v->istk->push(i);
                                        v->subscript++;
                                }
                                if (rg2) {
                                        v = Var::FindByMac(rg2);
                                        if (v) {
                                                i = v->subscript;
                                                s->oper1->sregs = i;
                                                v->istk->push(i);
                                                v->subscript++;
                                        }
                                }
                        }
                }
                eol = s == x->lcode;
        }
        for (e = x->ohead; e; e = e->next) {
                y = e->dst->num;
                j = WhichPred(x,y);
                if (j < 0 || j > 99) {   // Internal compiler error
                        printf("DIAG: CFG Rename j=%d out of range.\n", j);
                        fatal("");
                        continue;
                }
                b = basicBlocks[y];
                eol = false;
                for (s = b->code; s && !eol; s = s->fwd) {
                        if (s->opcode==op_phi) {
                                v = Var::FindByMac(s->oper1->preg);
                                if (v)
                                        s->phiops[j] = v->istk->tos();
                        }
                        eol = s == b->lcode;
                }
        }
        for (e = x->dhead; e; e = e->next)
                Search(e->dst);
        eol = false;
        for (s = x->code; s && !eol; s = s->fwd) {
                if (s->opcode!=op_label) {
                        if (s->HasTargetReg()) {
                                s->GetTargetReg(&rg1, &rg2);
                                v = Var::FindByMac(rg1);
                                if (v)
                                        v->istk->pop();
                                if (rg2) {
                                        v = Var::FindByMac(rg2);
                                        if (v)
                                                v->istk->pop();
                                }
                        }
                }
                eol = s == x->lcode;
        }
 
}
 
void CFG::Rename()
{
        Var *v;
 
        for (v = currentFn->varlist; v; v = v->next) {
                v->istk = IntStack::MakeNew();
                v->istk->push(0);
                v->subscript = 0;
        }
        Search(currentFn->RootBlock);
}

Browse

Tools

Subversion Repositories thor

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

Line No.	Rev	Author	Line
1	48	robfinch	`// ============================================================================`
2			`// __`
3			`// \\__/ o\ (C) 2017-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			`extern OCODE *peep_head;`
29			`extern BasicBlock *basicBlocks[10000];`
30			`extern Instruction *GetInsn(int);`
31
32			`void CFG::Create()`
33			`{`
34			`OCODE ip, ip1;`
35			`int nn;`
36			`struct scase *cs;`
37
38			`for (ip = peep_head; ip; ip = ip->fwd) {`
39			`if (ip->leader) {`
40			`if (ip->back) {`
41			`// if not unconditional control transfer`
42			`if (ip->back->opcode != op_ret && ip->back->opcode != op_bra && ip->back->opcode!=op_jmp) {`
43			`ip->back->bb->MakeOutputEdge(ip->bb);`
44			`ip->bb->MakeInputEdge(ip->back->bb);`
45			`}`
46			`}`
47			`}`
48			`//}`
49			`switch(ip->opcode) {`
50			`case op_bex:`
51			`case op_bra:`
52			`case op_jmp:`
53			`if (ip->oper1->offset) {`
54			`if (ip1 = FindLabel(ip->oper1->offset->i)) {`
55			`ip->bb->MakeOutputEdge(ip1->bb);`
56			`ip1->bb->MakeInputEdge(ip->bb);`
57			`}`
58			`}`
59			`break;`
60			`case op_beq:`
61			`case op_bne:`
62			`case op_blt:`
63			`case op_bge:`
64			`case op_ble:`
65			`case op_bgt:`
66			`case op_bltu:`
67			`case op_bgeu:`
68			`case op_bleu:`
69			`case op_bgtu:`
70			`case op_bbs:`
71			`case op_bbc:`
72			`case op_beqi:`
73			`case op_ibne:`
74			`if (0) {`
75			`if (ip->oper1->mode==am_reg && ip->back && ip->back->oper3) {`
76			`if (ip1 = FindLabel(ip->back->oper3->offset->i)) {`
77			`ip->bb->MakeOutputEdge(ip1->bb);`
78			`ip1->bb->MakeInputEdge(ip->bb);`
79			`}`
80			`}`
81			`}`
82			`else {`
83			`if (ip1 = FindLabel(ip->oper3->offset->i)) {`
84			`ip->bb->MakeOutputEdge(ip1->bb);`
85			`ip1->bb->MakeInputEdge(ip->bb);`
86			`}`
87			`}`
88			`break;`
89			`case op_bchk:`
90			`if (ip1 = FindLabel(ip->oper4->offset->i)) {`
91			`ip->bb->MakeOutputEdge(ip1->bb);`
92			`ip1->bb->MakeInputEdge(ip->bb);`
93			`}`
94			`break;`
95			`case op_jal:`
96			`// Was it a switch statement ?`
97			`if (ip->oper3) {`
98			`for (nn = 1; nn < ((struct scase *)(ip->oper3))->label; nn++) {`
99			`cs = &((struct scase *)(ip->oper3))[1];`
100			`ip1 = FindLabel(cs->label);`
101			`if (ip1) {`
102			`ip->bb->MakeOutputEdge(ip1->bb);`
103			`ip1->bb->MakeInputEdge(ip->bb);`
104			`}`
105			`}`
106			`}`
107			`else {`
108			`// Could be a jal [LR] for a ret statement in which case there's`
109			`// only one operand.`
110			`if (ip->oper2) {`
111			`if (ip->oper2->mode != am_reg) {`
112			`if (ip1 = FindLabel(ip->oper2->offset->i)) {`
113			`ip->bb->MakeOutputEdge(ip1->bb);`
114			`ip1->bb->MakeInputEdge(ip->bb);`
115			`}`
116			`}`
117			`}`
118			`}`
119			`break;`
120			`}`
121			`}`
122			`}`
123
124			`static CSet *visited;`
125			`static CSet *paths[1000];`
126			`static int npaths;`
127
128			`// Walk down the path beginning at block b.`
129
130			`static void DownPath(BasicBlock *b)`
131			`{`
132			`Edge *e;`
133			`int path;`
134			`bool first;`
135
136			`if (visited->isMember(b->num))`
137			`return;`
138			`path = npaths-1;`
139			`paths[path]->add(b->num);`
140			`visited->add(b->num);`
141			`first = true;`
142			`for (e = b->ohead; e; e = e->next) {`
143			`if (!first) {`
144			`paths[npaths] = CSet::MakeNew();`
145			`paths[npaths]->add(paths[path]);`
146			`npaths++;`
147			`}`
148			`// if (!e->backedge) {`
149			`first = false;`
150			`DownPath(e->dst);`
151			`// }`
152			`}`
153			`}`
154
155			`// Discover all the paths in the CFG.`
156
157			`static void DiscoverPaths()`
158			`{`
159			`BasicBlock *b;`
160			`int n;`
161			`char buf[2000];`
162
163			`b = currentFn->RootBlock;`
164			`visited = CSet::MakeNew();`
165			`paths[0] = CSet::MakeNew();`
166			`paths[0]->add(b->num);`
167			`npaths = 1;`
168			`DownPath(b);`
169			`dfs.printf("<Paths>\n");`
170			`for (n = 0; n < npaths; n++) {`
171			`paths[n]->sprint(buf, sizeof(buf));`
172			`dfs.printf("%d: ", n);`
173			`dfs.printf("%s\n", buf);`
174			`}`
175			`dfs.printf("</Paths>\n");`
176			`}`
177
178
179			`void CFG::CalcDominatorTree()`
180			`{`
181			`int n, m, o, ps;`
182			`CSet *pathSet;`
183			`bool oInAllPaths;`
184
185			`DiscoverPaths();`
186			`pathSet = CSet::MakeNew();`
187			`for (n = currentFn->LastBlock->num; n >= 1; n--) {`
188			`pathSet->clear();`
189			`// Get all paths that contain n`
190			`for (m = 0; m < npaths; m++)`
191			`if (paths[m]->isMember(n))`
192			`pathSet->add(m);`
193			`// If o is in all paths to n, then o dominates over n. Note there could`
194			`// be several o's that dominate over n. We only want the last one to do`
195			`// so. So we start the search at n-1 and work backwards.`
196			`for (o = n - 1; o >= 0; o--) {`
197			`oInAllPaths = true;`
198			`pathSet->resetPtr();`
199			`for (ps = pathSet->nextMember(); ps >= 0; ps=pathSet->nextMember()) {`
200			`if (!paths[ps]->isMember(o)) {`
201			`oInAllPaths = false;`
202			`break;`
203			`}`
204			`}`
205			`if (oInAllPaths)`
206			`break;`
207			`}`
208			`basicBlocks[o]->MakeDomEdge(basicBlocks[n]);`
209			`}`
210			`}`
211
212			`void CFG::CalcDominanceFrontiers()`
213			`{`
214			`BasicBlock *x;`
215			`Edge *e;`
216			`Edge *z;`
217			`int y;`
218
219			`CalcDominatorTree();`
220			`for (x = currentFn->LastBlock; x; x = x->prev) {`
221			`x->DF = nullptr;`
222			`if (x->dhead) {`
223			`x->DF = CSet::MakeNew();`
224			`// Check the successors of X`
225			`for (e = x->ohead; e; e = e->next) {`
226			`if (!x->IsIdom(e->dst)) {`
227			`x->DF->add(e->dst->num);`
228			`}`
229			`}`
230			`// Check the children of X`
231			`for (z = x->dhead; z; z = z->next) {`
232			`if (z->dst->DF) {`
233			`z->dst->DF->resetPtr();`
234			`for (y = z->dst->DF->nextMember(); y >= 0; y = z->dst->DF->nextMember()) {`
235			`if (!x->IsIdom(basicBlocks[y]))`
236			`x->DF->add(y);`
237			`}`
238			`}`
239			`}`
240			`}`
241			`}`
242			`}`
243
244			`void CFG::InsertPhiInsns()`
245			`{`
246			`BasicBlock *x;`
247			`OCODE phiNode, ip;`
248			`CSet *w;`
249			`Var *v;`
250			`Edge *e;`
251			`int IterCount = 0;`
252			`int n, m, y;`
253
254			`w = CSet::MakeNew();`
255			`for (x = currentFn->RootBlock; x; x = x->next) {`
256			`x->HasAlready = 0;`
257			`x->Work = 0;`
258			`}`
259			`w->clear();`
260			`for (v = currentFn->varlist; v; v = v->next) {`
261			`// Don't bother considering r0 which always contains the constant zero.`
262			`if (v->num==0)`
263			`continue;`
264			`IterCount++;`
265			`v->forest->resetPtr();`
266			`for (n = v->forest->nextMember(); n >= 0; n = v->forest->nextMember()) {`
267			`x = basicBlocks[n];`
268			`x->Work = IterCount;`
269			`w->add(x->num);`
270			`}`
271			`w->resetPtr();`
272			`while (w->NumMember() > 0) {`
273			`n = w->nextMember();`
274			`if (n < 0) {`
275			`w->resetPtr();`
276			`n = w->nextMember();`
277			`if (n < 0)`
278			`break;`
279			`}`
280			`w->remove(n);`
281			`x = basicBlocks[n];`
282			`if (x->DF) {`
283			`x->DF->resetPtr();`
284			`for (y = x->DF->nextMember(); y >= 0; y = x->DF->nextMember()) {`
285			`if (basicBlocks[y]->HasAlready < IterCount) {`
286			`// Place phi node at Y`
287			`phiNode = (OCODE *)allocx(sizeof(OCODE));`
288			`phiNode->insn = GetInsn(op_phi);`
289			`phiNode->opcode = op_phi;`
290			`phiNode->oper1 = makereg(v->num);`
291			`phiNode->bb = basicBlocks[y];`
292			`m = 0;`
293			`for (e = phiNode->bb->ihead; e && m < 100; e = e->next) {`
294			`phiNode->phiops[m] = e->src->num;`
295			`m++;`
296			`}`
297			`ip = basicBlocks[y]->code;`
298			`while (ip && ip->opcode==op_label) ip = ip->fwd;`
299			`// For now this is disabled.`
300			`// Peep::InsertBefore(ip,phiNode);`
301			`basicBlocks[y]->HasAlready = IterCount;`
302			`if (basicBlocks[y]->Work < IterCount) {`
303			`basicBlocks[y]->Work = IterCount;`
304			`w->add(y);`
305			`}`
306			`}`
307			`}`
308			`}`
309			`}`
310			`}`
311			`}`
312
313
314			`// Get the ordinal of which predecessor X is of Y.`
315
316			`int CFG::WhichPred(BasicBlock *x, int y)`
317			`{`
318			`BasicBlock *b;`
319			`Edge *e;`
320			`int n;`
321
322			`b = basicBlocks[y];`
323			`n = 0;`
324			`for (e = b->ihead; e; e = e->next) {`
325			`if (e->src==x)`
326			`return (n);`
327			`n++;`
328			`}`
329			`return (-1);`
330			`}`
331
332			`// Set a subscript on a variable.`
333
334			`void CFG::Subscript(Operand *oper)`
335			`{`
336			`Var *v;`
337
338			`if (oper) {`
339			`v = Var::FindByMac(oper->preg);`
340			`if (v)`
341			`oper->pregs = v->istk->tos();`
342			`v = Var::FindByMac(oper->sreg);`
343			`if (v)`
344			`oper->sregs = v->istk->tos();`
345			`}`
346			`}`
347
348			`void CFG::Search(BasicBlock *x)`
349			`{`
350			`OCODE *s;`
351			`BasicBlock *b;`
352			`Var *v;`
353			`Edge *e;`
354			`int i, j, y;`
355			`bool eol;`
356			`int rg1, rg2;`
357
358			`eol = false;`
359			`for (s = x->code; s && !eol; s = s->fwd) {`
360			`if (s->opcode!=op_label) {`
361			`if (s->oper1 && !s->HasTargetReg())`
362			`Subscript(s->oper1);`
363			`if (s->oper2)`
364			`Subscript(s->oper2);`
365			`if (s->oper3)`
366			`Subscript(s->oper3);`
367			`if (s->oper4)`
368			`Subscript(s->oper4);`
369			`if (s->oper1 && s->HasTargetReg()) {`
370			`s->GetTargetReg(&rg1, &rg2);`
371			`v = Var::FindByMac(rg1);`
372			`if (v) {`
373			`i = v->subscript;`
374			`s->oper1->pregs = i;`
375			`v->istk->push(i);`
376			`v->subscript++;`
377			`}`
378			`if (rg2) {`
379			`v = Var::FindByMac(rg2);`
380			`if (v) {`
381			`i = v->subscript;`
382			`s->oper1->sregs = i;`
383			`v->istk->push(i);`
384			`v->subscript++;`
385			`}`
386			`}`
387			`}`
388			`}`
389			`eol = s == x->lcode;`
390			`}`
391			`for (e = x->ohead; e; e = e->next) {`
392			`y = e->dst->num;`
393			`j = WhichPred(x,y);`
394			`if (j < 0 \|\| j > 99) { // Internal compiler error`
395			`printf("DIAG: CFG Rename j=%d out of range.\n", j);`
396			`fatal("");`
397			`continue;`
398			`}`
399			`b = basicBlocks[y];`
400			`eol = false;`
401			`for (s = b->code; s && !eol; s = s->fwd) {`
402			`if (s->opcode==op_phi) {`
403			`v = Var::FindByMac(s->oper1->preg);`
404			`if (v)`
405			`s->phiops[j] = v->istk->tos();`
406			`}`
407			`eol = s == b->lcode;`
408			`}`
409			`}`
410			`for (e = x->dhead; e; e = e->next)`
411			`Search(e->dst);`
412			`eol = false;`
413			`for (s = x->code; s && !eol; s = s->fwd) {`
414			`if (s->opcode!=op_label) {`
415			`if (s->HasTargetReg()) {`
416			`s->GetTargetReg(&rg1, &rg2);`
417			`v = Var::FindByMac(rg1);`
418			`if (v)`
419			`v->istk->pop();`
420			`if (rg2) {`
421			`v = Var::FindByMac(rg2);`
422			`if (v)`
423			`v->istk->pop();`
424			`}`
425			`}`
426			`}`
427			`eol = s == x->lcode;`
428			`}`
429
430			`}`
431
432			`void CFG::Rename()`
433			`{`
434			`Var *v;`
435
436			`for (v = currentFn->varlist; v; v = v->next) {`
437			`v->istk = IntStack::MakeNew();`
438			`v->istk->push(0);`
439			`v->subscript = 0;`
440			`}`
441			`Search(currentFn->RootBlock);`
442			`}`