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

Subversion Repositories thor

[/] [thor/] [trunk/] [FT64v5/] [software/] [CC64/] [source/] [Var.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"
 
// This class is currently only used by the CreateForest() function.
// It maintains a stack for tree traversal.
 
class WorkList
{
        int ndx;
        BasicBlock *p[10000];
public:
        WorkList() { ndx = 0; };
        void push(BasicBlock *q) {
                if (ndx < 9999) {
                        p[ndx] = q;
                        ndx++;
                }
        };
        BasicBlock *pop() {
                ndx--;
                return p[ndx];
        };
        bool IsEmpty() {
                return (ndx==0);
        };
};
 
WorkList wl;
Tree *tree;
int Var::nvar;
 
Var *Var::MakeNew()
{
        Var *p;
 
        p = (Var *)allocx(sizeof(Var));
        p->forest = CSet::MakeNew();
        p->visited = CSet::MakeNew();
        nvar++;
        return (p);
}
 
// Live ranges are represented as tree structures.
// Since there could be multiple live ranges (trees) for any given variable
// the group of ranges (or trees) is called a forest.
/*
void Var::CreateForest()
{
        Edge *ep;
        BasicBlock *p, *b;
        CSet *pushSet;
 
        pushSet = CSet::MakeNew();
        treeno = 0;
        tree = Tree::MakeNew();
        tree->next = trees;
        tree->num = treeno;
        treeno++;
        trees = tree;
        wl.push(LastBlock);
        pushSet->clear();
        while (!wl.IsEmpty()) {
                b = wl.pop();
                if (b->LiveOut->isMember(num)) {
                        tree->tree->add(b->num);
                        for (ep = b->ihead; ep; ep = ep->next) {
                                //if (ep->backedge)
                                //      continue;
                                p = ep->src;
                                if (p) {
//                                      if (p->LiveOut->isMember(num)) {
//                                              tree->tree->add(p->num);
                                                if (!pushSet->isMember(p->num)) {
                                                        wl.push(p);
                                                        pushSet->add(p->num);
                                                }
//                                      }
                                }
                        }
                        /*
                        for (ep = b->ohead; ep; ep = ep->next) {
                                //if (!ep->backedge)
                                //      continue;
                                p = ep->dst;
                                if (p) {
                                        if (p->LiveOut->isMember(num)) {
                                                tree->tree->add(p->num);
                                                if (!pushSet->isMember(p->num)) {
                                                        wl.push(p);
                                                        pushSet->add(p->num);
                                                }
                                        }
                                }
                        }
                        */
                        /*
                        if (b->prev) {
                                if (b->prev->LiveOut->isMember(num)) {
                                        tree->tree->add(b->prev->num);
                                }
                                else {
                                        tree = Tree::MakeNew();
                                        tree->next = trees;
                                        tree->num = treeno;
                                        treeno++;
                                        trees = tree;
                                }
                                wl.push(b->prev);
                        }
                        */
/*
                }
                else {
                        tree = Tree::MakeNew();
                        tree->next = trees;
                        tree->num = treeno;
                        treeno++;
                        trees = tree;
                        for (ep = b->ihead; ep; ep = ep->next) {
                                p = ep->src;
                                if (p) {
                                        if (!pushSet->isMember(p->num)) {
                                                wl.push(p);
                                                pushSet->add(p->num);
                                        }
                                }
                        }
                        //if (b->prev)
                        //      wl.push(b->prev);
                }
        }
}
*/
 
void Var::GrowTree(Tree *t, BasicBlock *b)
{
        Edge *ep;
        BasicBlock *p;
 
        for (ep = b->ihead; ep; ep = ep->next) {
//              if (!ep->backedge) {
                        p = ep->src;
                        if (!visited->isMember(p->num)) {
                                visited->add(p->num);
                                if (p->LiveOut->isMember(num)) {
                                        if (t==nullptr) {
                                                t = Tree::MakeNew();
                                                ::forest.PlantTree(t);
                                                trees.PlantTree(t);
                                                trees.map[num] = t->num;
                                                ::forest.map[num] = t->num;
                                                t->var = num;
                                                t->lattice = b->depth;
                                        }
                                        t->blocks->add(p->num);
                                        t->lattice = max(t->lattice, p->depth);
                                        forest->add(p->num);
                                        GrowTree(t, p);
                                }
                                else
                                        GrowTree(nullptr, p);
                        }
//              }
        }
        for (ep = b->ohead; ep; ep = ep->next) {
//              if (ep->backedge) {
                        p = ep->src;
                        if (!visited->isMember(p->num)) {
                                visited->add(p->num);
                                if (p->LiveOut->isMember(num)) {
                                        if (t==nullptr) {
                                                t = Tree::MakeNew();
                                                ::forest.PlantTree(t);
                                                trees.PlantTree(t);
                                                trees.map[num] = t->num;
                                                ::forest.map[num] = t->num;
                                                t->lattice = b->depth;
                                                t->var = num;
                                        }
                                        t->blocks->add(p->num);
                                        t->lattice = max(t->lattice, p->depth);
                                        forest->add(p->num);
                                        GrowTree(t, p);
                                }
                                else {
                                        GrowTree(nullptr, p);
                                }
                        }
//              }
        }
}
 
void Var::CreateForest()
{
        BasicBlock *b, *p;
        Edge *ep;
        Tree *t;
        char buf[2000];
 
        b = currentFn->LastBlock;
        visited->add(b->num);
        // First see if a tree starts right at the last basic block.
        if (b->LiveOut->isMember(num)) {
                t = Tree::MakeNew();
                ::forest.PlantTree(t);
                trees.PlantTree(t);
                trees.map[num] = t->num;
                ::forest.map[num] = t->num;
                t->var = num;
                t->lattice = b->depth;
                t->blocks->add(b->num);
                forest->add(b->num);
                GrowTree(t, b);
        }
        //else
        {
        // Next check all the input edges to the last block that
        // haven't yet been visited for additional trees.
        for (ep = b->ihead; ep; ep = ep->next) {
//              if (!ep->backedge) {
                        p = ep->src;
                        if (!visited->isMember(p->num)) {
                                visited->add(p->num);
                                if (p->LiveOut->isMember(num)) {
                                        t = Tree::MakeNew();
                                        ::forest.PlantTree(t);
                                        trees.PlantTree(t);
                                        trees.map[num] = t->num;
                                        ::forest.map[num] = t->num;
                                        t->var = num;
                                        t->lattice = p->depth;
                                        t->blocks->add(p->num);
                                        forest->add(p->num);
                                        GrowTree(t, p);
                                }
                                else {
                                        GrowTree(nullptr, p);
                                }
                        }
//              }
        }
        for (ep = b->ohead; ep; ep = ep->next) {
//              if (ep->backedge) {
                        p = ep->src;
                        if (!visited->isMember(p->num)) {
                                visited->add(p->num);
                                if (p->LiveOut->isMember(num)) {
                                        t = Tree::MakeNew();
                                        ::forest.PlantTree(t);
                                        trees.PlantTree(t);
                                        trees.map[num] = t->num;
                                        ::forest.map[num] = t->num;
                                        t->var = num;
                                        t->lattice = p->depth;
                                        t->blocks->add(p->num);
                                        forest->add(p->num);
                                        GrowTree(t, p);
                                }
                                else {
                                        GrowTree(nullptr, p);
                                }
                        }
//              }
        }
        }
        // Next try moving through the previous basic blocks, there may not be edges
        // to them.
        for (p = b->prev; p; p = p->prev)
        {
                if (!visited->isMember(p->num)) {
                        visited->add(p->num);
                        if (p->LiveOut->isMember(num)) {
                                t = Tree::MakeNew();
                                ::forest.PlantTree(t);
                                trees.PlantTree(t);
                                trees.map[num] = t->num;
                                ::forest.map[num] = t->num;
                                t->var = num;
                                t->lattice = p->depth;
                                t->blocks->add(p->num);
                                forest->add(p->num);
                                GrowTree(t, p);
                        }
                        else {
                                GrowTree(nullptr, p);
                        }
                }
        }
        dfs.printf("Visited r%d: ", num);
        visited->sprint(buf, sizeof(buf));
        dfs.printf(buf);
        dfs.printf("\n");
}
 
void Var::CreateForests()
{
        Var *v;
 
        Tree::treeno = 0;
        ::forest.treecount = 0;
        for (v = currentFn->varlist; v; v = v->next) {
                v->visited->clear();
                v->forest->clear();
                v->CreateForest();
        }
}
 
// Find variable info or create if not found.
 
Var *Var::Find(int num)
{
        Var *vp;
 
        for (vp = currentFn->varlist; vp; vp = vp->next) {
                if (vp->num == num)
                        break;
        }
        if (vp==nullptr) {
                vp = Var::MakeNew();
                vp->cnum = nvar-1;
                vp->num = num;
                vp->next = currentFn->varlist;
                currentFn->varlist = vp;
        }
        return (vp);
}
 
// Find variable info, but don't create
 
Var *Var::Find2(int num)
{
        Var *vp;
        Tree *t;
 
        for (vp = currentFn->varlist; vp; vp = vp->next) {
                //t = ::forest.trees[num];
                //if (t == nullptr)
                //      return (nullptr);
                if (vp->num == num)//map.newnums[num])
                        return(vp);
        }
        return (nullptr);
}
 
 
// Find by machine register. Not used after renumbering.
 
Var *Var::FindByMac(int num)
{
        Var *vp;
 
        for (vp = currentFn->varlist; vp; vp = vp->next) {
                if (vp->num == num)
                        return(vp);
        }
        return (nullptr);
}
 
Var *Var::FindByTreeno(int tn)
{
        Var *vp;
        Tree *t;
        int nn;
 
        for (vp = currentFn->varlist; vp; vp = vp->next) {
                for (nn = 0; nn < vp->trees.treecount; nn++) {
                        t = vp->trees.trees[nn];
                        if (t->treeno == tn)
                                return (vp);
                }
        }
        return (nullptr);
}
 
void Var::Renumber(int num, int nnum)
{
        Var *vp;
 
        for (vp = currentFn->varlist; vp; vp = vp->next) {
                if (vp->num == num) {
                        vp->num = -nnum;
                }
        }
}
 
void Var::RenumberNeg()
{
        Var *vp;
 
        for (vp = currentFn->varlist; vp; vp = vp->next) {
                vp->num = -vp->num;
        }
}
 
Var *Var::FindByCnum(int num)
{
        Var *vp;
 
        for (vp = currentFn->varlist; vp; vp = vp->next) {
                if (vp->cnum == num)
                        return(vp);
        }
        return (nullptr);
}
 
CSet *Var::Find3(int reg, int blocknum)
{
        Var *v;
        Tree *t;
        int n;
 
        v = Find2(reg);
        // Find the tree with the basic block
        for (n = 0; n < v->trees.treecount; n++) {
                t = v->trees.trees[n];
                if (t->blocks->isMember(blocknum)) {
                        return (t->blocks);
                }
        }
        // else error:
        return (nullptr);
}
 
 
// Find a specific tree that reg is associated with given
// the basic block number.
 
int Var::FindTreeno(int reg, int blocknum)
{
        Var *v;
        Tree *t;
        int n, m;
 
        // Find the associated variable
        v = Find2(reg);
        if (v == nullptr)
                return (-1);
 
        // Find the tree with the basic block. The individual trees in a given
        // var should be disjoint. Only one tree will contain the block.
        for (m = n = 0; n < v->trees.treecount; n++) {
                t = v->trees.trees[n];
                if (t->blocks->isMember(blocknum))
                        return(t->num);
        }
        return (-1);
}
 
 
// Copy trees from one var to another.
 
void Var::Transplant(Var *v)
{
        int nn;
 
        for (nn = 0; nn < v->trees.treecount; nn++) {
                if (trees.treecount < 500) {
                        trees.trees[trees.treecount] = v->trees.trees[nn];
                        trees.treecount++;
                }
                else
                        throw new C64PException(ERR_TOOMANY_TREES,1);
        }
}
 
 
// Coalescing currently doesn't make use of the interference graph.
// This algorithm is slow (n^2).
 
bool Var::Coalesce2()
{
        int reg1, reg2;
        Var *v1, *v2, *v3;
        Var *p, *q;
        Tree *t, *u;
        bool foundSameTree;
        bool improved;
        int nn, mm;
 
        improved = false;
        for (p = currentFn->varlist; p; p = p->next) {
                for (q = currentFn->varlist; q; q = q->next) {
                        if (p == q)
                                continue;
                        reg1 = p->num;
                        reg2 = q->num;
                        // Registers used as register parameters cannot be coalesced.
                        if ((reg1 >= regFirstArg && reg1 <= regLastArg)
                                || (reg2 >= regFirstArg && reg2 <= regLastArg))
                                continue;
                        // Coalesce the live ranges of the two variables into a single
                        // range.
                        //dfs.printf("Testing coalescence of live range r%d with ", reg1);
                        //dfs.printf("r%d \n", reg2);
                        //if (p->num)
                                v1 = Var::Find2(p->num);
                        //else
                        //      v1 = p;
                        //if (q->num)
                                v2 = Var::Find2(q->num);
                        //else
                        //      v2 = q;
                        if (v1 == nullptr || v2 == nullptr)
                                continue;
                        if (v1->trees.treecount == 0 || v2->trees.treecount == 0)
                                continue;
 
                        // Live ranges cannot be coalesced unless they are disjoint.
                        if (!v1->forest->isDisjoint(*v2->forest)) {
                                //dfs.printf("Live ranges overlap - no coalescence possible\n");
                                continue;
                        }
 
                        dfs.printf("Coalescing live range r%d with ", reg1);
                        dfs.printf("r%d \n", reg2);
                        improved = true;
                        //if (v1->trees.treecount == 0) {
                        //      v3 = v1;
                        //      v1 = v2;
                        //      v2 = v3;
                        //}
 
                        v1->Transplant(v2);
                        v1->forest->add(v2->forest);
/*
                        for (nn = 0; nn < v2->trees.treecount; nn++) {
                                t = v2->trees.trees[nn];
                                foundSameTree = false;
                                for (mm = 0; mm < v1->trees.treecount; mm++) {
                                        u = v1->trees.trees[mm];
                                        if (t->blocks->NumMember() >= u->blocks->NumMember()) {
                                                if (t->blocks->isSubset(*u->blocks)) {
                                                        u->blocks->add(t->blocks);
                                                        v1->forest->add(t->blocks);
                                                        foundSameTree = true;
                                                        break;
                                                }
                                        }
                                        else {
                                                if (u->blocks->isSubset(*t->blocks)) {
                                                        foundSameTree = true;
                                                        t->blocks->add(u->blocks);
                                                        v2->forest->add(u->blocks);
                                                        break;
                                                }
                                        }
                                }
 
                                if (!foundSameTree) {
                                        //t->next = v1->trees;
                                        //v1->trees = t;
                                        v1->Transplant(v2);
                                        v1->forest->add(v2->forest);
                                }
 
                        }
*/
                        v2->trees.treecount = 0;
                        v2->forest->clear();
                        //v2->num = v1->num;
                        //v2->Transplant(v1);
                        //v2->forest->add(v1->forest);
                }
        }
        return (improved);
}
 
int Var::PathCompress(int reg, int blocknum, int *tr)
{
        Var *v;
        Tree *t;
        int n;
 
        *tr = -1;
        v = Find2(reg);
        if (v == nullptr) {
                *tr = -1;
                return (-1);
        }
        // Find the tree with the basic block
        for (n = 0; n < v->trees.treecount; n++) {
                t = v->trees.trees[n];
                if (t->blocks->isMember(blocknum)) {
                        break;
                }
        }
        if (n < v->trees.treecount) {
                *tr = t->num;
                t->blocks->resetPtr();
                // The root of the tree is the lowest block number
                return (t->blocks->nextMember());
        }
        // else error: path not found
        return (-1);
}
 
void Var::DumpForests(int n)
{
        Var *vp;
        Tree *rg;
        int nn;
        char buf[2000];
 
        dfs.printf("<VarForests>%d\n", n);
        for (vp = currentFn->varlist; vp; vp = vp->next) {
                dfs.printf("Var%d:", vp->num);
                if (vp->trees.treecount > 0)
                        dfs.printf(" %d trees\n", vp->trees.treecount);
                else
                        dfs.printf(" no trees\n");
                for (nn = 0; nn < vp->trees.treecount; nn++) {
                        dfs.printf("<Tree>%d ", vp->trees.trees[nn]->num);
                        dfs.printf("Color:%d ", vp->trees.trees[nn]->color);
                        rg = vp->trees.trees[nn];
                        if (!rg->blocks->isEmpty()) {
                                rg->blocks->sprint(buf, sizeof(buf));
                                dfs.printf(buf);
                                dfs.printf("</Tree>\n");
                        }
                }
                dfs.printf("<Forest>");
                vp->forest->sprint(buf, sizeof(buf));
                dfs.printf(buf);
                dfs.printf("</Forest>\n");
        }
        dfs.printf("</VarForests>\n");
}
 
 
Var *Var::GetVarToSpill(CSet *exc)
{
        Var *vp;
        int tn, vn;
        int nn, mm;
 
        for (vp = currentFn->varlist; vp; vp = vp->next) {
                if (vp != this && vp->num > 2 && vp->num <= 17 && !exc->isMember(vp->num)) {
                        tn = ::forest.map[this->num];
                        vn = ::forest.map[vp->num];
                        nn = min(tn, vn);
                        mm = max(tn, vn);
                        if (!iGraph.DoesInterfere(nn, mm)) {
                                return (vp);
                        }
                }
        }
        // error: no register could be spilled.
        return (nullptr);
}
 

Browse

Tools

Subversion Repositories thor

[/] [thor/] [trunk/] [FT64v5/] [software/] [CC64/] [source/] [Var.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			`// This class is currently only used by the CreateForest() function.`
29			`// It maintains a stack for tree traversal.`
30
31			`class WorkList`
32			`{`
33			`int ndx;`
34			`BasicBlock *p[10000];`
35			`public:`
36			`WorkList() { ndx = 0; };`
37			`void push(BasicBlock *q) {`
38			`if (ndx < 9999) {`
39			`p[ndx] = q;`
40			`ndx++;`
41			`}`
42			`};`
43			`BasicBlock *pop() {`
44			`ndx--;`
45			`return p[ndx];`
46			`};`
47			`bool IsEmpty() {`
48			`return (ndx==0);`
49			`};`
50			`};`
51
52			`WorkList wl;`
53			`Tree *tree;`
54			`int Var::nvar;`
55
56			`Var *Var::MakeNew()`
57			`{`
58			`Var *p;`
59
60			`p = (Var *)allocx(sizeof(Var));`
61			`p->forest = CSet::MakeNew();`
62			`p->visited = CSet::MakeNew();`
63			`nvar++;`
64			`return (p);`
65			`}`
66
67			`// Live ranges are represented as tree structures.`
68			`// Since there could be multiple live ranges (trees) for any given variable`
69			`// the group of ranges (or trees) is called a forest.`
70			`/*`
71			`void Var::CreateForest()`
72			`{`
73			`Edge *ep;`
74			`BasicBlock p, b;`
75			`CSet *pushSet;`
76
77			`pushSet = CSet::MakeNew();`
78			`treeno = 0;`
79			`tree = Tree::MakeNew();`
80			`tree->next = trees;`
81			`tree->num = treeno;`
82			`treeno++;`
83			`trees = tree;`
84			`wl.push(LastBlock);`
85			`pushSet->clear();`
86			`while (!wl.IsEmpty()) {`
87			`b = wl.pop();`
88			`if (b->LiveOut->isMember(num)) {`
89			`tree->tree->add(b->num);`
90			`for (ep = b->ihead; ep; ep = ep->next) {`
91			`//if (ep->backedge)`
92			`// continue;`
93			`p = ep->src;`
94			`if (p) {`
95			`// if (p->LiveOut->isMember(num)) {`
96			`// tree->tree->add(p->num);`
97			`if (!pushSet->isMember(p->num)) {`
98			`wl.push(p);`
99			`pushSet->add(p->num);`
100			`}`
101			`// }`
102			`}`
103			`}`
104			`/*`
105			`for (ep = b->ohead; ep; ep = ep->next) {`
106			`//if (!ep->backedge)`
107			`// continue;`
108			`p = ep->dst;`
109			`if (p) {`
110			`if (p->LiveOut->isMember(num)) {`
111			`tree->tree->add(p->num);`
112			`if (!pushSet->isMember(p->num)) {`
113			`wl.push(p);`
114			`pushSet->add(p->num);`
115			`}`
116			`}`
117			`}`
118			`}`
119			`*/`
120			`/*`
121			`if (b->prev) {`
122			`if (b->prev->LiveOut->isMember(num)) {`
123			`tree->tree->add(b->prev->num);`
124			`}`
125			`else {`
126			`tree = Tree::MakeNew();`
127			`tree->next = trees;`
128			`tree->num = treeno;`
129			`treeno++;`
130			`trees = tree;`
131			`}`
132			`wl.push(b->prev);`
133			`}`
134			`*/`
135			`/*`
136			`}`
137			`else {`
138			`tree = Tree::MakeNew();`
139			`tree->next = trees;`
140			`tree->num = treeno;`
141			`treeno++;`
142			`trees = tree;`
143			`for (ep = b->ihead; ep; ep = ep->next) {`
144			`p = ep->src;`
145			`if (p) {`
146			`if (!pushSet->isMember(p->num)) {`
147			`wl.push(p);`
148			`pushSet->add(p->num);`
149			`}`
150			`}`
151			`}`
152			`//if (b->prev)`
153			`// wl.push(b->prev);`
154			`}`
155			`}`
156			`}`
157			`*/`
158
159			`void Var::GrowTree(Tree t, BasicBlock b)`
160			`{`
161			`Edge *ep;`
162			`BasicBlock *p;`
163
164			`for (ep = b->ihead; ep; ep = ep->next) {`
165			`// if (!ep->backedge) {`
166			`p = ep->src;`
167			`if (!visited->isMember(p->num)) {`
168			`visited->add(p->num);`
169			`if (p->LiveOut->isMember(num)) {`
170			`if (t==nullptr) {`
171			`t = Tree::MakeNew();`
172			`::forest.PlantTree(t);`
173			`trees.PlantTree(t);`
174			`trees.map[num] = t->num;`
175			`::forest.map[num] = t->num;`
176			`t->var = num;`
177			`t->lattice = b->depth;`
178			`}`
179			`t->blocks->add(p->num);`
180			`t->lattice = max(t->lattice, p->depth);`
181			`forest->add(p->num);`
182			`GrowTree(t, p);`
183			`}`
184			`else`
185			`GrowTree(nullptr, p);`
186			`}`
187			`// }`
188			`}`
189			`for (ep = b->ohead; ep; ep = ep->next) {`
190			`// if (ep->backedge) {`
191			`p = ep->src;`
192			`if (!visited->isMember(p->num)) {`
193			`visited->add(p->num);`
194			`if (p->LiveOut->isMember(num)) {`
195			`if (t==nullptr) {`
196			`t = Tree::MakeNew();`
197			`::forest.PlantTree(t);`
198			`trees.PlantTree(t);`
199			`trees.map[num] = t->num;`
200			`::forest.map[num] = t->num;`
201			`t->lattice = b->depth;`
202			`t->var = num;`
203			`}`
204			`t->blocks->add(p->num);`
205			`t->lattice = max(t->lattice, p->depth);`
206			`forest->add(p->num);`
207			`GrowTree(t, p);`
208			`}`
209			`else {`
210			`GrowTree(nullptr, p);`
211			`}`
212			`}`
213			`// }`
214			`}`
215			`}`
216
217			`void Var::CreateForest()`
218			`{`
219			`BasicBlock b, p;`
220			`Edge *ep;`
221			`Tree *t;`
222			`char buf[2000];`
223
224			`b = currentFn->LastBlock;`
225			`visited->add(b->num);`
226			`// First see if a tree starts right at the last basic block.`
227			`if (b->LiveOut->isMember(num)) {`
228			`t = Tree::MakeNew();`
229			`::forest.PlantTree(t);`
230			`trees.PlantTree(t);`
231			`trees.map[num] = t->num;`
232			`::forest.map[num] = t->num;`
233			`t->var = num;`
234			`t->lattice = b->depth;`
235			`t->blocks->add(b->num);`
236			`forest->add(b->num);`
237			`GrowTree(t, b);`
238			`}`
239			`//else`
240			`{`
241			`// Next check all the input edges to the last block that`
242			`// haven't yet been visited for additional trees.`
243			`for (ep = b->ihead; ep; ep = ep->next) {`
244			`// if (!ep->backedge) {`
245			`p = ep->src;`
246			`if (!visited->isMember(p->num)) {`
247			`visited->add(p->num);`
248			`if (p->LiveOut->isMember(num)) {`
249			`t = Tree::MakeNew();`
250			`::forest.PlantTree(t);`
251			`trees.PlantTree(t);`
252			`trees.map[num] = t->num;`
253			`::forest.map[num] = t->num;`
254			`t->var = num;`
255			`t->lattice = p->depth;`
256			`t->blocks->add(p->num);`
257			`forest->add(p->num);`
258			`GrowTree(t, p);`
259			`}`
260			`else {`
261			`GrowTree(nullptr, p);`
262			`}`
263			`}`
264			`// }`
265			`}`
266			`for (ep = b->ohead; ep; ep = ep->next) {`
267			`// if (ep->backedge) {`
268			`p = ep->src;`
269			`if (!visited->isMember(p->num)) {`
270			`visited->add(p->num);`
271			`if (p->LiveOut->isMember(num)) {`
272			`t = Tree::MakeNew();`
273			`::forest.PlantTree(t);`
274			`trees.PlantTree(t);`
275			`trees.map[num] = t->num;`
276			`::forest.map[num] = t->num;`
277			`t->var = num;`
278			`t->lattice = p->depth;`
279			`t->blocks->add(p->num);`
280			`forest->add(p->num);`
281			`GrowTree(t, p);`
282			`}`
283			`else {`
284			`GrowTree(nullptr, p);`
285			`}`
286			`}`
287			`// }`
288			`}`
289			`}`
290			`// Next try moving through the previous basic blocks, there may not be edges`
291			`// to them.`
292			`for (p = b->prev; p; p = p->prev)`
293			`{`
294			`if (!visited->isMember(p->num)) {`
295			`visited->add(p->num);`
296			`if (p->LiveOut->isMember(num)) {`
297			`t = Tree::MakeNew();`
298			`::forest.PlantTree(t);`
299			`trees.PlantTree(t);`
300			`trees.map[num] = t->num;`
301			`::forest.map[num] = t->num;`
302			`t->var = num;`
303			`t->lattice = p->depth;`
304			`t->blocks->add(p->num);`
305			`forest->add(p->num);`
306			`GrowTree(t, p);`
307			`}`
308			`else {`
309			`GrowTree(nullptr, p);`
310			`}`
311			`}`
312			`}`
313			`dfs.printf("Visited r%d: ", num);`
314			`visited->sprint(buf, sizeof(buf));`
315			`dfs.printf(buf);`
316			`dfs.printf("\n");`
317			`}`
318
319			`void Var::CreateForests()`
320			`{`
321			`Var *v;`
322
323			`Tree::treeno = 0;`
324			`::forest.treecount = 0;`
325			`for (v = currentFn->varlist; v; v = v->next) {`
326			`v->visited->clear();`
327			`v->forest->clear();`
328			`v->CreateForest();`
329			`}`
330			`}`
331
332			`// Find variable info or create if not found.`
333
334			`Var *Var::Find(int num)`
335			`{`
336			`Var *vp;`
337
338			`for (vp = currentFn->varlist; vp; vp = vp->next) {`
339			`if (vp->num == num)`
340			`break;`
341			`}`
342			`if (vp==nullptr) {`
343			`vp = Var::MakeNew();`
344			`vp->cnum = nvar-1;`
345			`vp->num = num;`
346			`vp->next = currentFn->varlist;`
347			`currentFn->varlist = vp;`
348			`}`
349			`return (vp);`
350			`}`
351
352			`// Find variable info, but don't create`
353
354			`Var *Var::Find2(int num)`
355			`{`
356			`Var *vp;`
357			`Tree *t;`
358
359			`for (vp = currentFn->varlist; vp; vp = vp->next) {`
360			`//t = ::forest.trees[num];`
361			`//if (t == nullptr)`
362			`// return (nullptr);`
363			`if (vp->num == num)//map.newnums[num])`
364			`return(vp);`
365			`}`
366			`return (nullptr);`
367			`}`
368
369
370			`// Find by machine register. Not used after renumbering.`
371
372			`Var *Var::FindByMac(int num)`
373			`{`
374			`Var *vp;`
375
376			`for (vp = currentFn->varlist; vp; vp = vp->next) {`
377			`if (vp->num == num)`
378			`return(vp);`
379			`}`
380			`return (nullptr);`
381			`}`
382
383			`Var *Var::FindByTreeno(int tn)`
384			`{`
385			`Var *vp;`
386			`Tree *t;`
387			`int nn;`
388
389			`for (vp = currentFn->varlist; vp; vp = vp->next) {`
390			`for (nn = 0; nn < vp->trees.treecount; nn++) {`
391			`t = vp->trees.trees[nn];`
392			`if (t->treeno == tn)`
393			`return (vp);`
394			`}`
395			`}`
396			`return (nullptr);`
397			`}`
398
399			`void Var::Renumber(int num, int nnum)`
400			`{`
401			`Var *vp;`
402
403			`for (vp = currentFn->varlist; vp; vp = vp->next) {`
404			`if (vp->num == num) {`
405			`vp->num = -nnum;`
406			`}`
407			`}`
408			`}`
409
410			`void Var::RenumberNeg()`
411			`{`
412			`Var *vp;`
413
414			`for (vp = currentFn->varlist; vp; vp = vp->next) {`
415			`vp->num = -vp->num;`
416			`}`
417			`}`
418
419			`Var *Var::FindByCnum(int num)`
420			`{`
421			`Var *vp;`
422
423			`for (vp = currentFn->varlist; vp; vp = vp->next) {`
424			`if (vp->cnum == num)`
425			`return(vp);`
426			`}`
427			`return (nullptr);`
428			`}`
429
430			`CSet *Var::Find3(int reg, int blocknum)`
431			`{`
432			`Var *v;`
433			`Tree *t;`
434			`int n;`
435
436			`v = Find2(reg);`
437			`// Find the tree with the basic block`
438			`for (n = 0; n < v->trees.treecount; n++) {`
439			`t = v->trees.trees[n];`
440			`if (t->blocks->isMember(blocknum)) {`
441			`return (t->blocks);`
442			`}`
443			`}`
444			`// else error:`
445			`return (nullptr);`
446			`}`
447
448
449			`// Find a specific tree that reg is associated with given`
450			`// the basic block number.`
451
452			`int Var::FindTreeno(int reg, int blocknum)`
453			`{`
454			`Var *v;`
455			`Tree *t;`
456			`int n, m;`
457
458			`// Find the associated variable`
459			`v = Find2(reg);`
460			`if (v == nullptr)`
461			`return (-1);`
462
463			`// Find the tree with the basic block. The individual trees in a given`
464			`// var should be disjoint. Only one tree will contain the block.`
465			`for (m = n = 0; n < v->trees.treecount; n++) {`
466			`t = v->trees.trees[n];`
467			`if (t->blocks->isMember(blocknum))`
468			`return(t->num);`
469			`}`
470			`return (-1);`
471			`}`
472
473
474			`// Copy trees from one var to another.`
475
476			`void Var::Transplant(Var *v)`
477			`{`
478			`int nn;`
479
480			`for (nn = 0; nn < v->trees.treecount; nn++) {`
481			`if (trees.treecount < 500) {`
482			`trees.trees[trees.treecount] = v->trees.trees[nn];`
483			`trees.treecount++;`
484			`}`
485			`else`
486			`throw new C64PException(ERR_TOOMANY_TREES,1);`
487			`}`
488			`}`
489
490
491			`// Coalescing currently doesn't make use of the interference graph.`
492			`// This algorithm is slow (n^2).`
493
494			`bool Var::Coalesce2()`
495			`{`
496			`int reg1, reg2;`
497			`Var v1, v2, *v3;`
498			`Var p, q;`
499			`Tree t, u;`
500			`bool foundSameTree;`
501			`bool improved;`
502			`int nn, mm;`
503
504			`improved = false;`
505			`for (p = currentFn->varlist; p; p = p->next) {`
506			`for (q = currentFn->varlist; q; q = q->next) {`
507			`if (p == q)`
508			`continue;`
509			`reg1 = p->num;`
510			`reg2 = q->num;`
511			`// Registers used as register parameters cannot be coalesced.`
512			`if ((reg1 >= regFirstArg && reg1 <= regLastArg)`
513			`\|\| (reg2 >= regFirstArg && reg2 <= regLastArg))`
514			`continue;`
515			`// Coalesce the live ranges of the two variables into a single`
516			`// range.`
517			`//dfs.printf("Testing coalescence of live range r%d with ", reg1);`
518			`//dfs.printf("r%d \n", reg2);`
519			`//if (p->num)`
520			`v1 = Var::Find2(p->num);`
521			`//else`
522			`// v1 = p;`
523			`//if (q->num)`
524			`v2 = Var::Find2(q->num);`
525			`//else`
526			`// v2 = q;`
527			`if (v1 == nullptr \|\| v2 == nullptr)`
528			`continue;`
529			`if (v1->trees.treecount == 0 \|\| v2->trees.treecount == 0)`
530			`continue;`
531
532			`// Live ranges cannot be coalesced unless they are disjoint.`
533			`if (!v1->forest->isDisjoint(*v2->forest)) {`
534			`//dfs.printf("Live ranges overlap - no coalescence possible\n");`
535			`continue;`
536			`}`
537
538			`dfs.printf("Coalescing live range r%d with ", reg1);`
539			`dfs.printf("r%d \n", reg2);`
540			`improved = true;`
541			`//if (v1->trees.treecount == 0) {`
542			`// v3 = v1;`
543			`// v1 = v2;`
544			`// v2 = v3;`
545			`//}`
546
547			`v1->Transplant(v2);`
548			`v1->forest->add(v2->forest);`
549			`/*`
550			`for (nn = 0; nn < v2->trees.treecount; nn++) {`
551			`t = v2->trees.trees[nn];`
552			`foundSameTree = false;`
553			`for (mm = 0; mm < v1->trees.treecount; mm++) {`
554			`u = v1->trees.trees[mm];`
555			`if (t->blocks->NumMember() >= u->blocks->NumMember()) {`
556			`if (t->blocks->isSubset(*u->blocks)) {`
557			`u->blocks->add(t->blocks);`
558			`v1->forest->add(t->blocks);`
559			`foundSameTree = true;`
560			`break;`
561			`}`
562			`}`
563			`else {`
564			`if (u->blocks->isSubset(*t->blocks)) {`
565			`foundSameTree = true;`
566			`t->blocks->add(u->blocks);`
567			`v2->forest->add(u->blocks);`
568			`break;`
569			`}`
570			`}`
571			`}`
572
573			`if (!foundSameTree) {`
574			`//t->next = v1->trees;`
575			`//v1->trees = t;`
576			`v1->Transplant(v2);`
577			`v1->forest->add(v2->forest);`
578			`}`
579
580			`}`
581			`*/`
582			`v2->trees.treecount = 0;`
583			`v2->forest->clear();`
584			`//v2->num = v1->num;`
585			`//v2->Transplant(v1);`
586			`//v2->forest->add(v1->forest);`
587			`}`
588			`}`
589			`return (improved);`
590			`}`
591
592			`int Var::PathCompress(int reg, int blocknum, int *tr)`
593			`{`
594			`Var *v;`
595			`Tree *t;`
596			`int n;`
597
598			`*tr = -1;`
599			`v = Find2(reg);`
600			`if (v == nullptr) {`
601			`*tr = -1;`
602			`return (-1);`
603			`}`
604			`// Find the tree with the basic block`
605			`for (n = 0; n < v->trees.treecount; n++) {`
606			`t = v->trees.trees[n];`
607			`if (t->blocks->isMember(blocknum)) {`
608			`break;`
609			`}`
610			`}`
611			`if (n < v->trees.treecount) {`
612			`*tr = t->num;`
613			`t->blocks->resetPtr();`
614			`// The root of the tree is the lowest block number`
615			`return (t->blocks->nextMember());`
616			`}`
617			`// else error: path not found`
618			`return (-1);`
619			`}`
620
621			`void Var::DumpForests(int n)`
622			`{`
623			`Var *vp;`
624			`Tree *rg;`
625			`int nn;`
626			`char buf[2000];`
627
628			`dfs.printf("<VarForests>%d\n", n);`
629			`for (vp = currentFn->varlist; vp; vp = vp->next) {`
630			`dfs.printf("Var%d:", vp->num);`
631			`if (vp->trees.treecount > 0)`
632			`dfs.printf(" %d trees\n", vp->trees.treecount);`
633			`else`
634			`dfs.printf(" no trees\n");`
635			`for (nn = 0; nn < vp->trees.treecount; nn++) {`
636			`dfs.printf("<Tree>%d ", vp->trees.trees[nn]->num);`
637			`dfs.printf("Color:%d ", vp->trees.trees[nn]->color);`
638			`rg = vp->trees.trees[nn];`
639			`if (!rg->blocks->isEmpty()) {`
640			`rg->blocks->sprint(buf, sizeof(buf));`
641			`dfs.printf(buf);`
642			`dfs.printf("</Tree>\n");`
643			`}`
644			`}`
645			`dfs.printf("<Forest>");`
646			`vp->forest->sprint(buf, sizeof(buf));`
647			`dfs.printf(buf);`
648			`dfs.printf("</Forest>\n");`
649			`}`
650			`dfs.printf("</VarForests>\n");`
651			`}`
652
653
654			`Var Var::GetVarToSpill(CSet exc)`
655			`{`
656			`Var *vp;`
657			`int tn, vn;`
658			`int nn, mm;`
659
660			`for (vp = currentFn->varlist; vp; vp = vp->next) {`
661			`if (vp != this && vp->num > 2 && vp->num <= 17 && !exc->isMember(vp->num)) {`
662			`tn = ::forest.map[this->num];`
663			`vn = ::forest.map[vp->num];`
664			`nn = min(tn, vn);`
665			`mm = max(tn, vn);`
666			`if (!iGraph.DoesInterfere(nn, mm)) {`
667			`return (vp);`
668			`}`
669			`}`
670			`}`
671			`// error: no register could be spilled.`
672			`return (nullptr);`
673			`}`
674