source: CLRX/CLRadeonExtender/trunk/amdasm/AsmRegAlloc.cpp @ 4032

Last change on this file since 4032 was 4032, checked in by matszpk, 14 months ago

CLRadeonExtender: GCNAsm: Do not permit regvars and SGPRs to be equal in VOP2/VOP3/VOPC instructions (rule: only 1 SGPR can be read).
AsmRegAlloc?: Remove obsolete equalTo dependencies (obsolete, when SGPRs and regvars can not be same if this same live time).
Fixed some GCNRegVarUsage testcases. Remove obsolete equalTo stuff from AsmRegalloc3 testsuite.

File size: 52.8 KB
Line 
1/*
2 *  CLRadeonExtender - Unofficial OpenCL Radeon Extensions Library
3 *  Copyright (C) 2014-2018 Mateusz Szpakowski
4 *
5 *  This library is free software; you can redistribute it and/or
6 *  modify it under the terms of the GNU Lesser General Public
7 *  License as published by the Free Software Foundation; either
8 *  version 2.1 of the License, or (at your option) any later version.
9 *
10 *  This library is distributed in the hope that it will be useful,
11 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
12 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
13 *  Lesser General Public License for more details.
14 *
15 *  You should have received a copy of the GNU Lesser General Public
16 *  License along with this library; if not, write to the Free Software
17 *  Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
18 */
19
20#include <CLRX/Config.h>
21#include <assert.h>
22#include <iostream>
23#include <stack>
24#include <deque>
25#include <vector>
26#include <utility>
27#include <unordered_set>
28#include <map>
29#include <set>
30#include <unordered_map>
31#include <algorithm>
32#include <CLRX/utils/Utilities.h>
33#include <CLRX/utils/Containers.h>
34#include <CLRX/amdasm/Assembler.h>
35#include "AsmInternals.h"
36#include "AsmRegAlloc.h"
37
38using namespace CLRX;
39
40#if ASMREGALLOC_DEBUGDUMP
41std::ostream& operator<<(std::ostream& os, const CLRX::BlockIndex& v)
42{
43    if (v.pass==0)
44        return os << v.index;
45    else
46        return os << v.index << "#" << v.pass;
47}
48#endif
49
50ISAUsageHandler::ISAUsageHandler(const std::vector<cxbyte>& _content) :
51            content(_content), lastOffset(0), readOffset(0), instrStructPos(0),
52            regUsagesPos(0), regUsages2Pos(0), regVarUsagesPos(0),
53            pushedArgs(0), argPos(0), argFlags(0), isNext(false), useRegMode(false)
54{ }
55
56ISAUsageHandler::~ISAUsageHandler()
57{ }
58
59void ISAUsageHandler::rewind()
60{
61    readOffset = instrStructPos = 0;
62    regUsagesPos = regUsages2Pos = regVarUsagesPos = 0;
63    useRegMode = false;
64    pushedArgs = 0;
65    skipBytesInInstrStruct();
66}
67
68void ISAUsageHandler::skipBytesInInstrStruct()
69{
70    // do not add instruction size if usereg (usereg immediately before instr regusages)
71    if ((instrStructPos != 0 || argPos != 0) && !useRegMode)
72        readOffset += defaultInstrSize;
73    argPos = 0;
74    for (;instrStructPos < instrStruct.size() &&
75        instrStruct[instrStructPos] > 0x80; instrStructPos++)
76        readOffset += (instrStruct[instrStructPos] & 0x7f);
77    isNext = (instrStructPos < instrStruct.size());
78}
79
80void ISAUsageHandler::putSpace(size_t offset)
81{
82    if (lastOffset != offset)
83    {
84        flush(); // flush before new instruction
85        // useReg immediately before instruction regusages
86        size_t defaultInstrSize = (!useRegMode ? this->defaultInstrSize : 0);
87        if (lastOffset > offset)
88            throw AsmException("Offset before previous instruction");
89        if (!instrStruct.empty() && offset - lastOffset < defaultInstrSize)
90            throw AsmException("Offset between previous instruction");
91        size_t toSkip = !instrStruct.empty() ? 
92                offset - lastOffset - defaultInstrSize : offset;
93        while (toSkip > 0)
94        {
95            size_t skipped = std::min(toSkip, size_t(0x7f));
96            instrStruct.push_back(skipped | 0x80);
97            toSkip -= skipped;
98        }
99        lastOffset = offset;
100        argFlags = 0;
101        pushedArgs = 0;
102    } 
103}
104
105void ISAUsageHandler::pushUsage(const AsmRegVarUsage& rvu)
106{
107    if (lastOffset == rvu.offset && useRegMode)
108        flush(); // only flush if useRegMode and no change in offset
109    else // otherwise
110        putSpace(rvu.offset);
111    useRegMode = false;
112    if (rvu.regVar != nullptr)
113    {
114        argFlags |= (1U<<pushedArgs);
115        regVarUsages.push_back({ rvu.regVar, rvu.rstart, rvu.rend, rvu.regField,
116            rvu.rwFlags, rvu.align });
117    }
118    else // reg usages
119        regUsages.push_back({ rvu.regField,cxbyte(rvu.rwFlags |
120                    getRwFlags(rvu.regField, rvu.rstart, rvu.rend)) });
121    pushedArgs++;
122}
123
124void ISAUsageHandler::pushUseRegUsage(const AsmRegVarUsage& rvu)
125{
126    if (lastOffset == rvu.offset && !useRegMode)
127        flush(); // only flush if useRegMode and no change in offset
128    else // otherwise
129        putSpace(rvu.offset);
130    useRegMode = true;
131    if (pushedArgs == 0 || pushedArgs == 256)
132    {
133        argFlags = 0;
134        pushedArgs = 0;
135        instrStruct.push_back(0x80); // sign of regvarusage from usereg
136        instrStruct.push_back(0);
137    }
138    if (rvu.regVar != nullptr)
139    {
140        argFlags |= (1U<<(pushedArgs & 7));
141        regVarUsages.push_back({ rvu.regVar, rvu.rstart, rvu.rend, rvu.regField,
142            rvu.rwFlags, rvu.align });
143    }
144    else // reg usages
145        regUsages2.push_back({ rvu.rstart, rvu.rend, rvu.rwFlags });
146    pushedArgs++;
147    if ((pushedArgs & 7) == 0) // just flush per 8 bit
148    {
149        instrStruct.push_back(argFlags);
150        instrStruct[instrStruct.size() - ((pushedArgs+7) >> 3) - 1] = pushedArgs;
151        argFlags = 0;
152    }
153}
154
155void ISAUsageHandler::flush()
156{
157    if (pushedArgs != 0)
158    {
159        if (!useRegMode)
160        {
161            // normal regvarusages
162            instrStruct.push_back(argFlags);
163            if ((argFlags & (1U<<(pushedArgs-1))) != 0)
164                regVarUsages.back().rwFlags |= 0x80;
165            else // reg usages
166                regUsages.back().rwFlags |= 0x80;
167        }
168        else
169        {
170            // use reg regvarusages
171            if ((pushedArgs & 7) != 0) //if only not pushed args remains
172                instrStruct.push_back(argFlags);
173            instrStruct[instrStruct.size() - ((pushedArgs+7) >> 3) - 1] = pushedArgs;
174        }
175    }
176}
177
178AsmRegVarUsage ISAUsageHandler::nextUsage()
179{
180    if (!isNext)
181        throw AsmException("No reg usage in this code");
182    AsmRegVarUsage rvu;
183    // get regvarusage
184    bool lastRegUsage = false;
185    rvu.offset = readOffset;
186    if (!useRegMode && instrStruct[instrStructPos] == 0x80)
187    {
188        // useRegMode (begin fetching useregs)
189        useRegMode = true;
190        argPos = 0;
191        instrStructPos++;
192        // pushedArgs - numer of useregs, 0 - 256 useregs
193        pushedArgs = instrStruct[instrStructPos++];
194        argFlags = instrStruct[instrStructPos];
195    }
196    rvu.useRegMode = useRegMode; // no ArgPos
197   
198    if ((instrStruct[instrStructPos] & (1U << (argPos&7))) != 0)
199    {
200        // regvar usage
201        const AsmRegVarUsageInt& inRVU = regVarUsages[regVarUsagesPos++];
202        rvu.regVar = inRVU.regVar;
203        rvu.rstart = inRVU.rstart;
204        rvu.rend = inRVU.rend;
205        rvu.regField = inRVU.regField;
206        rvu.rwFlags = inRVU.rwFlags & ASMRVU_ACCESS_MASK;
207        rvu.align = inRVU.align;
208        if (!useRegMode)
209            lastRegUsage = ((inRVU.rwFlags&0x80) != 0);
210    }
211    else if (!useRegMode)
212    {
213        // simple reg usage
214        const AsmRegUsageInt& inRU = regUsages[regUsagesPos++];
215        rvu.regVar = nullptr;
216        const std::pair<uint16_t, uint16_t> regPair =
217                    getRegPair(inRU.regField, inRU.rwFlags);
218        rvu.rstart = regPair.first;
219        rvu.rend = regPair.second;
220        rvu.rwFlags = (inRU.rwFlags & ASMRVU_ACCESS_MASK);
221        rvu.regField = inRU.regField;
222        rvu.align = 0;
223        lastRegUsage = ((inRU.rwFlags&0x80) != 0);
224    }
225    else
226    {
227        // use reg (simple reg usage, second structure)
228        const AsmRegUsage2Int& inRU = regUsages2[regUsages2Pos++];
229        rvu.regVar = nullptr;
230        rvu.rstart = inRU.rstart;
231        rvu.rend = inRU.rend;
232        rvu.rwFlags = inRU.rwFlags;
233        rvu.regField = ASMFIELD_NONE;
234        rvu.align = 0;
235    }
236    argPos++;
237    if (useRegMode)
238    {
239        // if inside useregs
240        if (argPos == (pushedArgs&0xff))
241        {
242            instrStructPos++; // end
243            skipBytesInInstrStruct();
244            useRegMode = false;
245        }
246        else if ((argPos & 7) == 0) // fetch new flag
247        {
248            instrStructPos++;
249            argFlags = instrStruct[instrStructPos];
250        }
251    }
252    // after instr
253    if (lastRegUsage)
254    {
255        instrStructPos++;
256        skipBytesInInstrStruct();
257    }
258    return rvu;
259}
260
261AsmRegAllocator::AsmRegAllocator(Assembler& _assembler) : assembler(_assembler)
262{ }
263
264AsmRegAllocator::AsmRegAllocator(Assembler& _assembler,
265        const std::vector<CodeBlock>& _codeBlocks, const SSAReplacesMap& _ssaReplacesMap)
266        : assembler(_assembler), codeBlocks(_codeBlocks), ssaReplacesMap(_ssaReplacesMap)
267{ }
268
269static inline bool codeBlockStartLess(const AsmRegAllocator::CodeBlock& c1,
270                  const AsmRegAllocator::CodeBlock& c2)
271{ return c1.start < c2.start; }
272
273static inline bool codeBlockEndLess(const AsmRegAllocator::CodeBlock& c1,
274                  const AsmRegAllocator::CodeBlock& c2)
275{ return c1.end < c2.end; }
276
277void AsmRegAllocator::createCodeStructure(const std::vector<AsmCodeFlowEntry>& codeFlow,
278             size_t codeSize, const cxbyte* code)
279{
280    ISAAssembler* isaAsm = assembler.isaAssembler;
281    if (codeSize == 0)
282        return;
283    std::vector<size_t> splits;
284    std::vector<size_t> codeStarts;
285    std::vector<size_t> codeEnds;
286    codeStarts.push_back(0);
287    codeEnds.push_back(codeSize);
288    for (const AsmCodeFlowEntry& entry: codeFlow)
289    {
290        size_t instrAfter = 0;
291        if (entry.type == AsmCodeFlowType::JUMP || entry.type == AsmCodeFlowType::CJUMP ||
292            entry.type == AsmCodeFlowType::CALL || entry.type == AsmCodeFlowType::RETURN)
293            instrAfter = entry.offset + isaAsm->getInstructionSize(
294                        codeSize - entry.offset, code + entry.offset);
295       
296        switch(entry.type)
297        {
298            case AsmCodeFlowType::START:
299                codeStarts.push_back(entry.offset);
300                break;
301            case AsmCodeFlowType::END:
302                codeEnds.push_back(entry.offset);
303                break;
304            case AsmCodeFlowType::JUMP:
305                splits.push_back(entry.target);
306                codeEnds.push_back(instrAfter);
307                break;
308            case AsmCodeFlowType::CJUMP:
309                splits.push_back(entry.target);
310                splits.push_back(instrAfter);
311                break;
312            case AsmCodeFlowType::CALL:
313                splits.push_back(entry.target);
314                splits.push_back(instrAfter);
315                break;
316            case AsmCodeFlowType::RETURN:
317                codeEnds.push_back(instrAfter);
318                break;
319            default:
320                break;
321        }
322    }
323    std::sort(splits.begin(), splits.end());
324    splits.resize(std::unique(splits.begin(), splits.end()) - splits.begin());
325    std::sort(codeEnds.begin(), codeEnds.end());
326    codeEnds.resize(std::unique(codeEnds.begin(), codeEnds.end()) - codeEnds.begin());
327    // remove codeStarts between codeStart and codeEnd
328    size_t i = 0;
329    size_t ii = 0;
330    size_t ei = 0; // codeEnd i
331    while (i < codeStarts.size())
332    {
333        size_t end = (ei < codeEnds.size() ? codeEnds[ei] : SIZE_MAX);
334        if (ei < codeEnds.size())
335            ei++;
336        codeStarts[ii++] = codeStarts[i];
337        // skip codeStart to end
338        for (i++ ;i < codeStarts.size() && codeStarts[i] < end; i++);
339    }
340    codeStarts.resize(ii);
341    // add next codeStarts
342    auto splitIt = splits.begin();
343    for (size_t codeEnd: codeEnds)
344    {
345        auto it = std::lower_bound(splitIt, splits.end(), codeEnd);
346        if (it != splits.end())
347        {
348            codeStarts.push_back(*it);
349            splitIt = it;
350        }
351        else // if end
352            break;
353    }
354   
355    std::sort(codeStarts.begin(), codeStarts.end());
356    codeStarts.resize(std::unique(codeStarts.begin(), codeStarts.end()) -
357                codeStarts.begin());
358    // divide to blocks
359    splitIt = splits.begin();
360    for (size_t codeStart: codeStarts)
361    {
362        size_t codeEnd = *std::upper_bound(codeEnds.begin(), codeEnds.end(), codeStart);
363        splitIt = std::lower_bound(splitIt, splits.end(), codeStart);
364       
365        if (splitIt != splits.end() && *splitIt==codeStart)
366            ++splitIt; // skip split in codeStart
367       
368        for (size_t start = codeStart; start < codeEnd; )
369        {
370            size_t end = codeEnd;
371            if (splitIt != splits.end())
372            {
373                end = std::min(end, *splitIt);
374                ++splitIt;
375            }
376            codeBlocks.push_back({ start, end, { }, false, false, false });
377            start = end;
378        }
379    }
380    // force empty block at end if some jumps goes to its
381    if (!codeEnds.empty() && !codeStarts.empty() && !splits.empty() &&
382        codeStarts.back()==codeEnds.back() && codeStarts.back() == splits.back())
383        codeBlocks.push_back({ codeStarts.back(), codeStarts.back(), { },
384                             false, false, false });
385   
386    // construct flow-graph
387    for (const AsmCodeFlowEntry& entry: codeFlow)
388        if (entry.type == AsmCodeFlowType::CALL || entry.type == AsmCodeFlowType::JUMP ||
389            entry.type == AsmCodeFlowType::CJUMP || entry.type == AsmCodeFlowType::RETURN)
390        {
391            std::vector<CodeBlock>::iterator it;
392            size_t instrAfter = entry.offset + isaAsm->getInstructionSize(
393                        codeSize - entry.offset, code + entry.offset);
394           
395            if (entry.type != AsmCodeFlowType::RETURN)
396                it = binaryFind(codeBlocks.begin(), codeBlocks.end(),
397                        CodeBlock{ entry.target }, codeBlockStartLess);
398            else // return
399            {
400                it = binaryFind(codeBlocks.begin(), codeBlocks.end(),
401                        CodeBlock{ 0, instrAfter }, codeBlockEndLess);
402                // if block have return
403                if (it != codeBlocks.end())
404                    it->haveEnd = it->haveReturn = true;
405                continue;
406            }
407           
408            if (it == codeBlocks.end())
409                continue; // error!
410            auto it2 = std::lower_bound(codeBlocks.begin(), codeBlocks.end(),
411                    CodeBlock{ instrAfter }, codeBlockStartLess);
412            auto curIt = it2;
413            --curIt;
414           
415            curIt->nexts.push_back({ size_t(it - codeBlocks.begin()),
416                        entry.type == AsmCodeFlowType::CALL });
417            curIt->haveCalls |= entry.type == AsmCodeFlowType::CALL;
418            if (entry.type == AsmCodeFlowType::CJUMP ||
419                 entry.type == AsmCodeFlowType::CALL)
420            {
421                curIt->haveEnd = false; // revert haveEnd if block have cond jump or call
422                if (it2 != codeBlocks.end() && entry.type == AsmCodeFlowType::CJUMP)
423                    // add next next block (only for cond jump)
424                    curIt->nexts.push_back({ size_t(it2 - codeBlocks.begin()), false });
425            }
426            else if (entry.type == AsmCodeFlowType::JUMP)
427                curIt->haveEnd = true; // set end
428        }
429    // force haveEnd for block with cf_end
430    for (const AsmCodeFlowEntry& entry: codeFlow)
431        if (entry.type == AsmCodeFlowType::END)
432        {
433            auto it = binaryFind(codeBlocks.begin(), codeBlocks.end(),
434                    CodeBlock{ 0, entry.offset }, codeBlockEndLess);
435            if (it != codeBlocks.end())
436                it->haveEnd = true;
437        }
438   
439    if (!codeBlocks.empty()) // always set haveEnd to last block
440        codeBlocks.back().haveEnd = true;
441   
442    // reduce nexts
443    for (CodeBlock& block: codeBlocks)
444    {
445        // first non-call nexts, for correct resolving SSA conflicts
446        std::sort(block.nexts.begin(), block.nexts.end(),
447                  [](const NextBlock& n1, const NextBlock& n2)
448                  { return int(n1.isCall)<int(n2.isCall) ||
449                      (n1.isCall == n2.isCall && n1.block < n2.block); });
450        auto it = std::unique(block.nexts.begin(), block.nexts.end(),
451                  [](const NextBlock& n1, const NextBlock& n2)
452                  { return n1.block == n2.block && n1.isCall == n2.isCall; });
453        block.nexts.resize(it - block.nexts.begin());
454    }
455}
456
457
458void AsmRegAllocator::applySSAReplaces()
459{
460    if (ssaReplacesMap.empty())
461        return; // do nothing
462   
463    /* prepare SSA id replaces */
464    struct MinSSAGraphNode
465    {
466        size_t minSSAId;
467        bool visited;
468        std::unordered_set<size_t> nexts;
469        MinSSAGraphNode() : minSSAId(SIZE_MAX), visited(false)
470        { }
471    };
472   
473    typedef std::map<size_t, MinSSAGraphNode, std::greater<size_t> > SSAGraphNodesMap;
474   
475    struct MinSSAGraphStackEntry
476    {
477        SSAGraphNodesMap::iterator nodeIt;
478        std::unordered_set<size_t>::const_iterator nextIt;
479        size_t minSSAId;
480       
481        MinSSAGraphStackEntry(
482                SSAGraphNodesMap::iterator _nodeIt,
483                std::unordered_set<size_t>::const_iterator _nextIt,
484                size_t _minSSAId = SIZE_MAX)
485                : nodeIt(_nodeIt), nextIt(_nextIt), minSSAId(_minSSAId)
486        { }
487    };
488   
489    for (auto& entry: ssaReplacesMap)
490    {
491        ARDOut << "SSAReplace: " << entry.first.regVar << "." << entry.first.index << "\n";
492        VectorSet<SSAReplace>& replaces = entry.second;
493        std::sort(replaces.begin(), replaces.end(), std::greater<SSAReplace>());
494        replaces.resize(std::unique(replaces.begin(), replaces.end()) - replaces.begin());
495        VectorSet<SSAReplace> newReplaces;
496       
497        SSAGraphNodesMap ssaGraphNodes;
498       
499        auto it = replaces.begin();
500        while (it != replaces.end())
501        {
502            auto itEnd = std::upper_bound(it, replaces.end(),
503                    std::make_pair(it->first, size_t(0)), std::greater<SSAReplace>());
504            {
505                auto itLast = itEnd;
506                --itLast;
507                MinSSAGraphNode& node = ssaGraphNodes[it->first];
508                node.minSSAId = std::min(node.minSSAId, itLast->second);
509                for (auto it2 = it; it2 != itEnd; ++it2)
510                {
511                    node.nexts.insert(it2->second);
512                    ssaGraphNodes.insert({ it2->second, MinSSAGraphNode() });
513                }
514            }
515            it = itEnd;
516        }
517        /*for (const auto& v: ssaGraphNodes)
518            ARDOut << "  SSANode: " << v.first << ":" << &v.second << " minSSAID: " <<
519                            v.second.minSSAId << std::endl;*/
520        // propagate min value
521        std::stack<MinSSAGraphStackEntry> minSSAStack;
522       
523        // initialize parents and new nexts
524        for (auto ssaGraphNodeIt = ssaGraphNodes.begin();
525                 ssaGraphNodeIt!=ssaGraphNodes.end(); )
526        {
527            ARDOut << "  Start in " << ssaGraphNodeIt->first << "." << "\n";
528            minSSAStack.push({ ssaGraphNodeIt, ssaGraphNodeIt->second.nexts.begin() });
529            // traverse with minimalize SSA id
530            while (!minSSAStack.empty())
531            {
532                MinSSAGraphStackEntry& entry = minSSAStack.top();
533                MinSSAGraphNode& node = entry.nodeIt->second;
534                bool toPop = false;
535                if (entry.nextIt == node.nexts.begin())
536                {
537                    toPop = node.visited;
538                    node.visited = true;
539                }
540                if (!toPop && entry.nextIt != node.nexts.end())
541                {
542                    auto nodeIt = ssaGraphNodes.find(*entry.nextIt);
543                    if (nodeIt != ssaGraphNodes.end())
544                        minSSAStack.push({ nodeIt, nodeIt->second.nexts.begin(),
545                                    size_t(0) });
546                    ++entry.nextIt;
547                }
548                else
549                {
550                    minSSAStack.pop();
551                    if (!minSSAStack.empty())
552                        node.nexts.insert(minSSAStack.top().nodeIt->first);
553                }
554            }
555           
556            // skip visited nodes
557            for(; ssaGraphNodeIt != ssaGraphNodes.end(); ++ssaGraphNodeIt)
558                if (!ssaGraphNodeIt->second.visited)
559                    break;
560        }
561       
562        /*for (const auto& v: ssaGraphNodes)
563        {
564            ARDOut << "  Nexts: " << v.first << ":" << &v.second << " nexts:";
565            for (size_t p: v.second.nexts)
566                ARDOut << " " << p;
567            ARDOut << "\n";
568        }*/
569       
570        for (auto& entry: ssaGraphNodes)
571            entry.second.visited = false;
572       
573        std::vector<MinSSAGraphNode*> toClear; // nodes to clear
574       
575        for (auto ssaGraphNodeIt = ssaGraphNodes.begin();
576                 ssaGraphNodeIt!=ssaGraphNodes.end(); )
577        {
578            ARDOut << "  Start in " << ssaGraphNodeIt->first << "." << "\n";
579            minSSAStack.push({ ssaGraphNodeIt, ssaGraphNodeIt->second.nexts.begin() });
580            // traverse with minimalize SSA id
581            while (!minSSAStack.empty())
582            {
583                MinSSAGraphStackEntry& entry = minSSAStack.top();
584                MinSSAGraphNode& node = entry.nodeIt->second;
585                bool toPop = false;
586                if (entry.nextIt == node.nexts.begin())
587                {
588                    toPop = node.visited;
589                    if (!node.visited)
590                        // this flag visited for this node will be clear after this pass
591                        toClear.push_back(&node);
592                    node.visited = true;
593                }
594               
595                // try to children only all parents are visited and if parent has children
596                if (!toPop && entry.nextIt != node.nexts.end())
597                {
598                    auto nodeIt = ssaGraphNodes.find(*entry.nextIt);
599                    if (nodeIt != ssaGraphNodes.end())
600                    {
601                        ARDOut << "  Node: " <<
602                                entry.nodeIt->first << ":" << &node << " minSSAId: " <<
603                                node.minSSAId << " to " <<
604                                nodeIt->first << ":" << &(nodeIt->second) <<
605                                " minSSAId: " << nodeIt->second.minSSAId << "\n";
606                        nodeIt->second.minSSAId =
607                                std::min(nodeIt->second.minSSAId, node.minSSAId);
608                        minSSAStack.push({ nodeIt, nodeIt->second.nexts.begin(),
609                                nodeIt->second.minSSAId });
610                    }
611                    ++entry.nextIt;
612                }
613                else
614                {
615                    node.minSSAId = std::min(node.minSSAId, entry.minSSAId);
616                    ARDOut << "    Node: " <<
617                                entry.nodeIt->first << ":" << &node << " minSSAId: " <<
618                                node.minSSAId << "\n";
619                    minSSAStack.pop();
620                    if (!minSSAStack.empty())
621                    {
622                        MinSSAGraphStackEntry& pentry = minSSAStack.top();
623                        pentry.minSSAId = std::min(pentry.minSSAId, node.minSSAId);
624                    }
625                }
626            }
627           
628            const size_t minSSAId = ssaGraphNodeIt->second.minSSAId;
629           
630            // skip visited nodes
631            for(; ssaGraphNodeIt != ssaGraphNodes.end(); ++ssaGraphNodeIt)
632                if (!ssaGraphNodeIt->second.visited)
633                    break;
634            // zeroing visited
635            for (MinSSAGraphNode* node: toClear)
636            {
637                node->minSSAId = minSSAId; // fill up by minSSAId
638                node->visited = false;
639            }
640            toClear.clear();
641        }
642       
643        for (const auto& entry: ssaGraphNodes)
644            newReplaces.push_back({ entry.first, entry.second.minSSAId });
645       
646        std::sort(newReplaces.begin(), newReplaces.end());
647        entry.second = newReplaces;
648    }
649   
650    /* apply SSA id replaces */
651    for (CodeBlock& cblock: codeBlocks)
652        for (auto& ssaEntry: cblock.ssaInfoMap)
653        {
654            auto it = ssaReplacesMap.find(ssaEntry.first);
655            if (it == ssaReplacesMap.end())
656                continue;
657            SSAInfo& sinfo = ssaEntry.second;
658            VectorSet<SSAReplace>& replaces = it->second;
659            if (sinfo.readBeforeWrite)
660            {
661                auto rit = binaryMapFind(replaces.begin(), replaces.end(),
662                                 ssaEntry.second.ssaIdBefore);
663                if (rit != replaces.end())
664                    sinfo.ssaIdBefore = rit->second; // replace
665            }
666            if (sinfo.ssaIdFirst != SIZE_MAX)
667            {
668                auto rit = binaryMapFind(replaces.begin(), replaces.end(),
669                                 ssaEntry.second.ssaIdFirst);
670                if (rit != replaces.end())
671                    sinfo.ssaIdFirst = rit->second; // replace
672            }
673            if (sinfo.ssaIdLast != SIZE_MAX)
674            {
675                auto rit = binaryMapFind(replaces.begin(), replaces.end(),
676                                 ssaEntry.second.ssaIdLast);
677                if (rit != replaces.end())
678                    sinfo.ssaIdLast = rit->second; // replace
679            }
680        }
681   
682    // clear ssa replaces
683    ssaReplacesMap.clear();
684}
685
686static cxuint getRegType(size_t regTypesNum, const cxuint* regRanges,
687            const AsmSingleVReg& svreg)
688{
689    cxuint regType; // regtype
690    if (svreg.regVar!=nullptr)
691        regType = svreg.regVar->type;
692    else
693        for (regType = 0; regType < regTypesNum; regType++)
694            if (svreg.index >= regRanges[regType<<1] &&
695                svreg.index < regRanges[(regType<<1)+1])
696                break;
697    return regType;
698}
699
700static Liveness& getLiveness(const AsmSingleVReg& svreg, size_t ssaIdIdx,
701        const AsmRegAllocator::SSAInfo& ssaInfo, std::vector<Liveness>* livenesses,
702        const VarIndexMap* vregIndexMaps, size_t regTypesNum, const cxuint* regRanges)
703{
704    size_t ssaId;
705    if (svreg.regVar==nullptr)
706        ssaId = 0;
707    else if (ssaIdIdx==0)
708        ssaId = ssaInfo.ssaIdBefore;
709    else if (ssaIdIdx==1)
710        ssaId = ssaInfo.ssaIdFirst;
711    else if (ssaIdIdx<ssaInfo.ssaIdChange)
712        ssaId = ssaInfo.ssaId + ssaIdIdx-1;
713    else // last
714        ssaId = ssaInfo.ssaIdLast;
715   
716    cxuint regType = getRegType(regTypesNum, regRanges, svreg); // regtype
717    const VarIndexMap& vregIndexMap = vregIndexMaps[regType];
718    const std::vector<size_t>& ssaIdIndices =
719                vregIndexMap.find(svreg)->second;
720    ARDOut << "lvn[" << regType << "][" << ssaIdIndices[ssaId] << "]. ssaIdIdx: " <<
721            ssaIdIdx << ". ssaId: " << ssaId << ". svreg: " << svreg.regVar << ":" <<
722            svreg.index << "\n";
723    return livenesses[regType][ssaIdIndices[ssaId]];
724}
725
726/* TODO: add handling calls
727 * handle many start points in this code (for example many kernel's in same code)
728 * replace sets by vector, and sort and remove same values on demand
729 */
730
731static void putCrossBlockLivenesses(const std::deque<FlowStackEntry3>& flowStack,
732        const std::vector<CodeBlock>& codeBlocks,
733        const Array<size_t>& codeBlockLiveTimes, const LastVRegMap& lastVRegMap,
734        std::vector<Liveness>* livenesses, const VarIndexMap* vregIndexMaps,
735        size_t regTypesNum, const cxuint* regRanges)
736{
737    const CodeBlock& cblock = codeBlocks[flowStack.back().blockIndex];
738    for (const auto& entry: cblock.ssaInfoMap)
739        if (entry.second.readBeforeWrite)
740        {
741            // find last
742            auto lvrit = lastVRegMap.find(entry.first);
743            if (lvrit == lastVRegMap.end())
744                continue; // not found
745            const VRegLastPos& lastPos = lvrit->second;
746            FlowStackCIter flit = lastPos.blockChain.back();
747            cxuint regType = getRegType(regTypesNum, regRanges, entry.first);
748            const VarIndexMap& vregIndexMap = vregIndexMaps[regType];
749            const std::vector<size_t>& ssaIdIndices =
750                        vregIndexMap.find(entry.first)->second;
751            Liveness& lv = livenesses[regType][ssaIdIndices[entry.second.ssaIdBefore]];
752            FlowStackCIter flitEnd = flowStack.end();
753            --flitEnd; // before last element
754            // insert live time to last seen position
755            const CodeBlock& lastBlk = codeBlocks[flit->blockIndex];
756            size_t toLiveCvt = codeBlockLiveTimes[flit->blockIndex] - lastBlk.start;
757            lv.insert(lastBlk.ssaInfoMap.find(entry.first)->second.lastPos + toLiveCvt,
758                    toLiveCvt + lastBlk.end);
759            for (++flit; flit != flitEnd; ++flit)
760            {
761                const CodeBlock& cblock = codeBlocks[flit->blockIndex];
762                size_t blockLiveTime = codeBlockLiveTimes[flit->blockIndex];
763                lv.insert(blockLiveTime, cblock.end-cblock.start + blockLiveTime);
764            }
765        }
766}
767
768static void putCrossBlockForLoop(const std::deque<FlowStackEntry3>& flowStack,
769        const std::vector<CodeBlock>& codeBlocks,
770        const Array<size_t>& codeBlockLiveTimes,
771        std::vector<Liveness>* livenesses, const VarIndexMap* vregIndexMaps,
772        size_t regTypesNum, const cxuint* regRanges)
773{
774    auto flitStart = flowStack.end();
775    --flitStart;
776    size_t curBlock = flitStart->blockIndex;
777    // find step in way
778    while (flitStart->blockIndex != curBlock) --flitStart;
779    auto flitEnd = flowStack.end();
780    --flitEnd;
781    std::unordered_map<AsmSingleVReg, std::pair<size_t, size_t> > varMap;
782   
783    // collect var to check
784    size_t flowPos = 0;
785    for (auto flit = flitStart; flit != flitEnd; ++flit, flowPos++)
786    {
787        const CodeBlock& cblock = codeBlocks[flit->blockIndex];
788        for (const auto& entry: cblock.ssaInfoMap)
789        {
790            const SSAInfo& sinfo = entry.second;
791            size_t lastSSAId = (sinfo.ssaIdChange != 0) ? sinfo.ssaIdLast :
792                    (sinfo.readBeforeWrite) ? sinfo.ssaIdBefore : 0;
793            varMap[entry.first] = { lastSSAId, flowPos };
794        }
795    }
796    // find connections
797    flowPos = 0;
798    for (auto flit = flitStart; flit != flitEnd; ++flit, flowPos++)
799    {
800        const CodeBlock& cblock = codeBlocks[flit->blockIndex];
801        for (const auto& entry: cblock.ssaInfoMap)
802        {
803            const SSAInfo& sinfo = entry.second;
804            auto varMapIt = varMap.find(entry.first);
805            if (!sinfo.readBeforeWrite || varMapIt == varMap.end() ||
806                flowPos > varMapIt->second.second ||
807                sinfo.ssaIdBefore != varMapIt->second.first)
808                continue;
809            // just connect
810           
811            cxuint regType = getRegType(regTypesNum, regRanges, entry.first);
812            const VarIndexMap& vregIndexMap = vregIndexMaps[regType];
813            const std::vector<size_t>& ssaIdIndices =
814                        vregIndexMap.find(entry.first)->second;
815            Liveness& lv = livenesses[regType][ssaIdIndices[entry.second.ssaIdBefore]];
816           
817            if (flowPos == varMapIt->second.second)
818            {
819                // fill whole loop
820                for (auto flit2 = flitStart; flit != flitEnd; ++flit)
821                {
822                    const CodeBlock& cblock = codeBlocks[flit2->blockIndex];
823                    size_t blockLiveTime = codeBlockLiveTimes[flit2->blockIndex];
824                    lv.insert(blockLiveTime, cblock.end-cblock.start + blockLiveTime);
825                }
826                continue;
827            }
828           
829            size_t flowPos2 = 0;
830            for (auto flit2 = flitStart; flowPos2 < flowPos; ++flit2, flowPos++)
831            {
832                const CodeBlock& cblock = codeBlocks[flit2->blockIndex];
833                size_t blockLiveTime = codeBlockLiveTimes[flit2->blockIndex];
834                lv.insert(blockLiveTime, cblock.end-cblock.start + blockLiveTime);
835            }
836            // insert liveness for last block in loop of last SSAId (prev round)
837            auto flit2 = flitStart + flowPos;
838            const CodeBlock& firstBlk = codeBlocks[flit2->blockIndex];
839            size_t toLiveCvt = codeBlockLiveTimes[flit2->blockIndex] - firstBlk.start;
840            lv.insert(codeBlockLiveTimes[flit2->blockIndex],
841                    firstBlk.ssaInfoMap.find(entry.first)->second.firstPos + toLiveCvt);
842            // insert liveness for first block in loop of last SSAId
843            flit2 = flitStart + (varMapIt->second.second+1);
844            const CodeBlock& lastBlk = codeBlocks[flit2->blockIndex];
845            toLiveCvt = codeBlockLiveTimes[flit2->blockIndex] - lastBlk.start;
846            lv.insert(lastBlk.ssaInfoMap.find(entry.first)->second.lastPos + toLiveCvt,
847                    toLiveCvt + lastBlk.end);
848            // fill up loop end
849            for (++flit2; flit2 != flitEnd; ++flit2)
850            {
851                const CodeBlock& cblock = codeBlocks[flit2->blockIndex];
852                size_t blockLiveTime = codeBlockLiveTimes[flit2->blockIndex];
853                lv.insert(blockLiveTime, cblock.end-cblock.start + blockLiveTime);
854            }
855        }
856    }
857}
858
859static void addUsageDeps(const cxbyte* ldeps, cxuint rvusNum,
860            const AsmRegVarUsage* rvus, LinearDepMap* ldepsOut,
861            const VarIndexMap* vregIndexMaps,
862            const std::unordered_map<AsmSingleVReg, size_t>& ssaIdIdxMap,
863            size_t regTypesNum, const cxuint* regRanges)
864{
865    // add linear deps
866    cxuint count = ldeps[0];
867    cxuint pos = 1;
868    cxbyte rvuAdded = 0;
869    for (cxuint i = 0; i < count; i++)
870    {
871        cxuint ccount = ldeps[pos++];
872        std::vector<size_t> vidxes;
873        cxuint regType = UINT_MAX;
874        cxbyte align = rvus[ldeps[pos]].align;
875        for (cxuint j = 0; j < ccount; j++)
876        {
877            rvuAdded |= 1U<<ldeps[pos];
878            const AsmRegVarUsage& rvu = rvus[ldeps[pos++]];
879            for (uint16_t k = rvu.rstart; k < rvu.rend; k++)
880            {
881                AsmSingleVReg svreg = {rvu.regVar, k};
882                auto sit = ssaIdIdxMap.find(svreg);
883                if (regType==UINT_MAX)
884                    regType = getRegType(regTypesNum, regRanges, svreg);
885                const VarIndexMap& vregIndexMap = vregIndexMaps[regType];
886                const std::vector<size_t>& ssaIdIndices =
887                            vregIndexMap.find(svreg)->second;
888                // push variable index
889                vidxes.push_back(ssaIdIndices[sit->second]);
890            }
891        }
892        ldepsOut[regType][vidxes[0]].align = align;
893        for (size_t k = 1; k < vidxes.size(); k++)
894        {
895            ldepsOut[regType][vidxes[k-1]].nextVidxes.push_back(vidxes[k]);
896            ldepsOut[regType][vidxes[k]].prevVidxes.push_back(vidxes[k-1]);
897        }
898    }
899    // add single arg linear dependencies
900    for (cxuint i = 0; i < rvusNum; i++)
901        if ((rvuAdded & (1U<<i)) == 0 && rvus[i].rstart+1<rvus[i].rend)
902        {
903            const AsmRegVarUsage& rvu = rvus[i];
904            std::vector<size_t> vidxes;
905            cxuint regType = UINT_MAX;
906            cxbyte align = rvus[i].align;
907            for (uint16_t k = rvu.rstart; k < rvu.rend; k++)
908            {
909                AsmSingleVReg svreg = {rvu.regVar, k};
910                auto sit = ssaIdIdxMap.find(svreg);
911                assert(sit != ssaIdIdxMap.end());
912                if (regType==UINT_MAX)
913                    regType = getRegType(regTypesNum, regRanges, svreg);
914                const VarIndexMap& vregIndexMap = vregIndexMaps[regType];
915                const std::vector<size_t>& ssaIdIndices =
916                            vregIndexMap.find(svreg)->second;
917                // push variable index
918                vidxes.push_back(ssaIdIndices[sit->second]);
919            }
920            ldepsOut[regType][vidxes[0]].align = align;
921            for (size_t j = 1; j < vidxes.size(); j++)
922            {
923                ldepsOut[regType][vidxes[j-1]].nextVidxes.push_back(vidxes[j]);
924                ldepsOut[regType][vidxes[j]].prevVidxes.push_back(vidxes[j-1]);
925            }
926        }
927}
928
929void AsmRegAllocator::createLivenesses(ISAUsageHandler& usageHandler,
930            size_t codeSize, const cxbyte* code)
931{
932    ISAAssembler* isaAsm = assembler.isaAssembler;
933    // construct var index maps
934    cxuint regRanges[MAX_REGTYPES_NUM*2];
935    std::fill(graphVregsCounts, graphVregsCounts+MAX_REGTYPES_NUM, size_t(0));
936    size_t regTypesNum;
937    assembler.isaAssembler->getRegisterRanges(regTypesNum, regRanges);
938   
939    for (const CodeBlock& cblock: codeBlocks)
940        for (const auto& entry: cblock.ssaInfoMap)
941        {
942            const SSAInfo& sinfo = entry.second;
943            cxuint regType = getRegType(regTypesNum, regRanges, entry.first);
944            VarIndexMap& vregIndices = vregIndexMaps[regType];
945            size_t& graphVregsCount = graphVregsCounts[regType];
946            std::vector<size_t>& ssaIdIndices = vregIndices[entry.first];
947            size_t ssaIdCount = 0;
948            if (sinfo.readBeforeWrite)
949                ssaIdCount = sinfo.ssaIdBefore+1;
950            if (sinfo.ssaIdChange!=0)
951            {
952                ssaIdCount = std::max(ssaIdCount, sinfo.ssaIdLast+1);
953                ssaIdCount = std::max(ssaIdCount, sinfo.ssaId+sinfo.ssaIdChange-1);
954                ssaIdCount = std::max(ssaIdCount, sinfo.ssaIdFirst+1);
955            }
956            if (ssaIdIndices.size() < ssaIdCount)
957                ssaIdIndices.resize(ssaIdCount, SIZE_MAX);
958           
959            if (sinfo.readBeforeWrite)
960            {
961                if (ssaIdIndices[sinfo.ssaIdBefore] == SIZE_MAX)
962                    ssaIdIndices[sinfo.ssaIdBefore] = graphVregsCount++;
963            }
964            if (sinfo.ssaIdChange!=0)
965            {
966                // fill up ssaIdIndices (with graph Ids)
967                if (ssaIdIndices[sinfo.ssaIdFirst] == SIZE_MAX)
968                    ssaIdIndices[sinfo.ssaIdFirst] = graphVregsCount++;
969                for (size_t ssaId = sinfo.ssaId+1;
970                        ssaId < sinfo.ssaId+sinfo.ssaIdChange-1; ssaId++)
971                    ssaIdIndices[ssaId] = graphVregsCount++;
972                if (ssaIdIndices[sinfo.ssaIdLast] == SIZE_MAX)
973                    ssaIdIndices[sinfo.ssaIdLast] = graphVregsCount++;
974            }
975        }
976   
977    // construct vreg liveness
978    std::deque<FlowStackEntry3> flowStack;
979    std::vector<bool> visited(codeBlocks.size(), false);
980    // hold last vreg ssaId and position
981    LastVRegMap lastVRegMap;
982    // hold start live time position for every code block
983    Array<size_t> codeBlockLiveTimes(codeBlocks.size());
984    std::unordered_set<size_t> blockInWay;
985   
986    std::vector<Liveness> livenesses[MAX_REGTYPES_NUM];
987   
988    for (size_t i = 0; i < regTypesNum; i++)
989        livenesses[i].resize(graphVregsCounts[i]);
990   
991    size_t curLiveTime = 0;
992    flowStack.push_back({ 0, 0 });
993   
994    while (!flowStack.empty())
995    {
996        FlowStackEntry3& entry = flowStack.back();
997        CodeBlock& cblock = codeBlocks[entry.blockIndex];
998       
999        if (entry.nextIndex == 0)
1000        {
1001            // process current block
1002            if (!blockInWay.insert(entry.blockIndex).second)
1003            {
1004                // if loop
1005                putCrossBlockForLoop(flowStack, codeBlocks, codeBlockLiveTimes, 
1006                        livenesses, vregIndexMaps, regTypesNum, regRanges);
1007                flowStack.pop_back();
1008                continue;
1009            }
1010           
1011            codeBlockLiveTimes[entry.blockIndex] = curLiveTime;
1012            putCrossBlockLivenesses(flowStack, codeBlocks, codeBlockLiveTimes, 
1013                    lastVRegMap, livenesses, vregIndexMaps, regTypesNum, regRanges);
1014           
1015            for (const auto& sentry: cblock.ssaInfoMap)
1016            {
1017                const SSAInfo& sinfo = sentry.second;
1018                // update
1019                size_t lastSSAId =  (sinfo.ssaIdChange != 0) ? sinfo.ssaIdLast :
1020                        (sinfo.readBeforeWrite) ? sinfo.ssaIdBefore : 0;
1021                FlowStackCIter flit = flowStack.end();
1022                --flit; // to last position
1023                auto res = lastVRegMap.insert({ sentry.first, 
1024                            { lastSSAId, { flit } } });
1025                if (!res.second) // if not first seen, just update
1026                {
1027                    // update last
1028                    res.first->second.ssaId = lastSSAId;
1029                    res.first->second.blockChain.push_back(flit);
1030                }
1031            }
1032           
1033            size_t curBlockLiveEnd = cblock.end - cblock.start + curLiveTime;
1034            if (!visited[entry.blockIndex])
1035            {
1036                visited[entry.blockIndex] = true;
1037                std::unordered_map<AsmSingleVReg, size_t> ssaIdIdxMap;
1038                AsmRegVarUsage instrRVUs[8];
1039                cxuint instrRVUsCount = 0;
1040               
1041                size_t oldOffset = cblock.usagePos.readOffset;
1042                std::vector<AsmSingleVReg> readSVRegs;
1043                std::vector<AsmSingleVReg> writtenSVRegs;
1044               
1045                usageHandler.setReadPos(cblock.usagePos);
1046                // register in liveness
1047                while (true)
1048                {
1049                    AsmRegVarUsage rvu = { 0U, nullptr, 0U, 0U };
1050                    size_t liveTimeNext = SIZE_MAX;
1051                    bool hasNext = false;
1052                    if (usageHandler.hasNext())
1053                    {
1054                        hasNext = true;
1055                        rvu = usageHandler.nextUsage();
1056                    }
1057                    size_t liveTime = oldOffset - cblock.start + curLiveTime;
1058                    if (!hasNext || rvu.offset > oldOffset)
1059                    {
1060                        if (!writtenSVRegs.empty())
1061                            // calculate livetime for next instruction
1062                            liveTimeNext = liveTime + isaAsm->getInstructionSize(
1063                                    codeSize - oldOffset, code + oldOffset);
1064                       
1065                        ARDOut << "apply to liveness. offset: " << oldOffset << "\n";
1066                        // apply to liveness
1067                        for (AsmSingleVReg svreg: readSVRegs)
1068                        {
1069                            auto svrres = ssaIdIdxMap.insert({ svreg, 0 });
1070                            Liveness& lv = getLiveness(svreg, svrres.first->second,
1071                                    cblock.ssaInfoMap.find(svreg)->second,
1072                                    livenesses, vregIndexMaps, regTypesNum, regRanges);
1073                            if (svrres.second)
1074                                // begin region from this block
1075                                lv.newRegion(curLiveTime);
1076                            lv.expand(liveTime);
1077                        }
1078                        for (AsmSingleVReg svreg: writtenSVRegs)
1079                        {
1080                            size_t& ssaIdIdx = ssaIdIdxMap[svreg];
1081                            ssaIdIdx++;
1082                            SSAInfo& sinfo = cblock.ssaInfoMap.find(svreg)->second;
1083                            Liveness& lv = getLiveness(svreg, ssaIdIdx, sinfo,
1084                                    livenesses, vregIndexMaps, regTypesNum, regRanges);
1085                            if (liveTimeNext != curBlockLiveEnd)
1086                                // because live after this instr
1087                                lv.insert(liveTimeNext, liveTimeNext+1);
1088                            sinfo.lastPos = liveTimeNext - curLiveTime + cblock.start;
1089                        }
1090                        // get linear deps and equal to
1091                        cxbyte lDeps[16];
1092                        usageHandler.getUsageDependencies(instrRVUsCount, instrRVUs, lDeps);
1093                       
1094                        addUsageDeps(lDeps, instrRVUsCount, instrRVUs,
1095                                linearDepMaps, vregIndexMaps, ssaIdIdxMap,
1096                                regTypesNum, regRanges);
1097                       
1098                        readSVRegs.clear();
1099                        writtenSVRegs.clear();
1100                        if (!hasNext)
1101                            break;
1102                        oldOffset = rvu.offset;
1103                        instrRVUsCount = 0;
1104                    }
1105                    if (hasNext && rvu.offset < cblock.end && !rvu.useRegMode)
1106                        instrRVUs[instrRVUsCount++] = rvu;
1107                    if (rvu.offset >= cblock.end)
1108                        break;
1109                   
1110                    for (uint16_t rindex = rvu.rstart; rindex < rvu.rend; rindex++)
1111                    {
1112                        // per register/singlvreg
1113                        AsmSingleVReg svreg{ rvu.regVar, rindex };
1114                        if (rvu.rwFlags == ASMRVU_WRITE && rvu.regField!=ASMFIELD_NONE)
1115                            writtenSVRegs.push_back(svreg);
1116                        else // read or treat as reading // expand previous region
1117                            readSVRegs.push_back(svreg);
1118                    }
1119                }
1120                curLiveTime += cblock.end-cblock.start;
1121            }
1122            else
1123            {
1124                // back, already visited
1125                flowStack.pop_back();
1126                continue;
1127            }
1128        }
1129        if (entry.nextIndex < cblock.nexts.size())
1130        {
1131            flowStack.push_back({ cblock.nexts[entry.nextIndex].block, 0 });
1132            entry.nextIndex++;
1133        }
1134        else if (entry.nextIndex==0 && cblock.nexts.empty() && !cblock.haveEnd)
1135        {
1136            flowStack.push_back({ entry.blockIndex+1, 0 });
1137            entry.nextIndex++;
1138        }
1139        else // back
1140        {
1141            // revert lastSSAIdMap
1142            blockInWay.erase(entry.blockIndex);
1143            flowStack.pop_back();
1144            if (!flowStack.empty())
1145            {
1146                for (const auto& sentry: cblock.ssaInfoMap)
1147                {
1148                    auto lvrit = lastVRegMap.find(sentry.first);
1149                    if (lvrit != lastVRegMap.end())
1150                    {
1151                        VRegLastPos& lastPos = lvrit->second;
1152                        lastPos.ssaId = sentry.second.ssaIdBefore;
1153                        lastPos.blockChain.pop_back();
1154                        if (lastPos.blockChain.empty()) // just remove from lastVRegs
1155                            lastVRegMap.erase(lvrit);
1156                    }
1157                }
1158            }
1159        }
1160    }
1161   
1162    // move livenesses to AsmRegAllocator outLivenesses
1163    for (size_t regType = 0; regType < regTypesNum; regType++)
1164    {
1165        std::vector<Liveness>& livenesses2 = livenesses[regType];
1166        Array<OutLiveness>& outLivenesses2 = outLivenesses[regType];
1167        outLivenesses2.resize(livenesses2.size());
1168        for (size_t li = 0; li < livenesses2.size(); li++)
1169        {
1170            outLivenesses2[li].resize(livenesses2[li].l.size());
1171            std::copy(livenesses2[li].l.begin(), livenesses2[li].l.end(),
1172                      outLivenesses2[li].begin());
1173            livenesses2[li].clear();
1174        }
1175        livenesses2.clear();
1176    }
1177}
1178
1179void AsmRegAllocator::createInterferenceGraph()
1180{
1181    /// construct liveBlockMaps
1182    std::set<LiveBlock> liveBlockMaps[MAX_REGTYPES_NUM];
1183    for (size_t regType = 0; regType < regTypesNum; regType++)
1184    {
1185        std::set<LiveBlock>& liveBlockMap = liveBlockMaps[regType];
1186        Array<OutLiveness>& liveness = outLivenesses[regType];
1187        for (size_t li = 0; li < liveness.size(); li++)
1188        {
1189            OutLiveness& lv = liveness[li];
1190            for (const std::pair<size_t, size_t>& blk: lv)
1191                if (blk.first != blk.second)
1192                    liveBlockMap.insert({ blk.first, blk.second, li });
1193            lv.clear();
1194        }
1195        liveness.clear();
1196    }
1197   
1198    // create interference graphs
1199    for (size_t regType = 0; regType < regTypesNum; regType++)
1200    {
1201        InterGraph& interGraph = interGraphs[regType];
1202        interGraph.resize(graphVregsCounts[regType]);
1203        std::set<LiveBlock>& liveBlockMap = liveBlockMaps[regType];
1204       
1205        auto lit = liveBlockMap.begin();
1206        size_t rangeStart = 0;
1207        if (lit != liveBlockMap.end())
1208            rangeStart = lit->start;
1209        while (lit != liveBlockMap.end())
1210        {
1211            const size_t blkStart = lit->start;
1212            const size_t blkEnd = lit->end;
1213            size_t rangeEnd = blkEnd;
1214            auto liStart = liveBlockMap.lower_bound({ rangeStart, 0, 0 });
1215            auto liEnd = liveBlockMap.lower_bound({ rangeEnd, 0, 0 });
1216            // collect from this range, variable indices
1217            std::set<size_t> varIndices;
1218            for (auto lit2 = liStart; lit2 != liEnd; ++lit2)
1219                varIndices.insert(lit2->vidx);
1220            // push to intergraph as full subgGraph
1221            for (auto vit = varIndices.begin(); vit != varIndices.end(); ++vit)
1222                for (auto vit2 = varIndices.begin(); vit2 != varIndices.end(); ++vit2)
1223                    if (vit != vit2)
1224                        interGraph[*vit].insert(*vit2);
1225            // go to next live blocks
1226            rangeStart = rangeEnd;
1227            for (; lit != liveBlockMap.end(); ++lit)
1228                if (lit->start != blkStart && lit->end != blkEnd)
1229                    break;
1230            if (lit == liveBlockMap.end())
1231                break; //
1232            rangeStart = std::max(rangeStart, lit->start);
1233        }
1234    }
1235}
1236
1237/* algorithm to allocate regranges:
1238 * from smallest regranges to greatest regranges:
1239 *   choosing free register: from smallest free regranges
1240 *      to greatest regranges:
1241 *         in this same regrange:
1242 *               try to find free regs in regranges
1243 *               try to link free ends of two distinct regranges
1244 */
1245
1246void AsmRegAllocator::colorInterferenceGraph()
1247{
1248    const GPUArchitecture arch = getGPUArchitectureFromDeviceType(
1249                    assembler.deviceType);
1250   
1251    for (size_t regType = 0; regType < regTypesNum; regType++)
1252    {
1253        const size_t maxColorsNum = getGPUMaxRegistersNum(arch, regType);
1254        InterGraph& interGraph = interGraphs[regType];
1255        const VarIndexMap& vregIndexMap = vregIndexMaps[regType];
1256        Array<cxuint>& gcMap = graphColorMaps[regType];
1257       
1258        const size_t nodesNum = interGraph.size();
1259        gcMap.resize(nodesNum);
1260        std::fill(gcMap.begin(), gcMap.end(), cxuint(UINT_MAX));
1261        Array<size_t> sdoCounts(nodesNum);
1262        std::fill(sdoCounts.begin(), sdoCounts.end(), 0);
1263       
1264        SDOLDOCompare compare(interGraph, sdoCounts);
1265        std::set<size_t, SDOLDOCompare> nodeSet(compare);
1266        for (size_t i = 0; i < nodesNum; i++)
1267            nodeSet.insert(i);
1268       
1269        cxuint colorsNum = 0;
1270        // firstly, allocate real registers
1271        for (const auto& entry: vregIndexMap)
1272            if (entry.first.regVar == nullptr)
1273                gcMap[entry.second[0]] = colorsNum++;
1274       
1275        for (size_t colored = 0; colored < nodesNum; colored++)
1276        {
1277            size_t node = *nodeSet.begin();
1278            if (gcMap[node] != UINT_MAX)
1279                continue; // already colored
1280            size_t color = 0;
1281           
1282            for (color = 0; color <= colorsNum; color++)
1283            {
1284                // find first usable color
1285                bool thisSame = false;
1286                for (size_t nb: interGraph[node])
1287                    if (gcMap[nb] == color)
1288                    {
1289                        thisSame = true;
1290                        break;
1291                    }
1292                if (!thisSame)
1293                    break;
1294            }
1295            if (color==colorsNum) // add new color if needed
1296            {
1297                if (colorsNum >= maxColorsNum)
1298                    throw AsmException("Too many register is needed");
1299                colorsNum++;
1300            }
1301           
1302            gcMap[node] = color;
1303            // update SDO for node
1304            bool colorExists = false;
1305            for (size_t nb: interGraph[node])
1306                if (gcMap[nb] == color)
1307                {
1308                    colorExists = true;
1309                    break;
1310                }
1311            if (!colorExists)
1312                sdoCounts[node]++;
1313            // update SDO for neighbors
1314            for (size_t nb: interGraph[node])
1315            {
1316                colorExists = false;
1317                for (size_t nb2: interGraph[nb])
1318                    if (gcMap[nb2] == color)
1319                    {
1320                        colorExists = true;
1321                        break;
1322                    }
1323                if (!colorExists)
1324                {
1325                    if (gcMap[nb] == UINT_MAX)
1326                        nodeSet.erase(nb);  // before update we erase from nodeSet
1327                    sdoCounts[nb]++;
1328                    if (gcMap[nb] == UINT_MAX)
1329                        nodeSet.insert(nb); // after update, insert again
1330                }
1331            }
1332           
1333            gcMap[node] = color;
1334        }
1335    }
1336}
1337
1338void AsmRegAllocator::allocateRegisters(cxuint sectionId)
1339{
1340    // before any operation, clear all
1341    codeBlocks.clear();
1342    for (size_t i = 0; i < MAX_REGTYPES_NUM; i++)
1343    {
1344        graphVregsCounts[i] = 0;
1345        vregIndexMaps[i].clear();
1346        interGraphs[i].clear();
1347        linearDepMaps[i].clear();
1348        graphColorMaps[i].clear();
1349    }
1350    ssaReplacesMap.clear();
1351    cxuint maxRegs[MAX_REGTYPES_NUM];
1352    assembler.isaAssembler->getMaxRegistersNum(regTypesNum, maxRegs);
1353   
1354    // set up
1355    const AsmSection& section = assembler.sections[sectionId];
1356    createCodeStructure(section.codeFlow, section.content.size(), section.content.data());
1357    createSSAData(*section.usageHandler);
1358    applySSAReplaces();
1359    createLivenesses(*section.usageHandler, section.content.size(), section.content.data());
1360    createInterferenceGraph();
1361    colorInterferenceGraph();
1362}
Note: See TracBrowser for help on using the repository browser.