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

Last change on this file since 4035 was 4035, checked in by matszpk, 12 months ago

CLRadeonExtender: AsmRegAlloc?: Use start of cblock and section offset as livetime. Remove codeBlocksLiveTimes.

File size: 52.0 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, const LastVRegMap& lastVRegMap,
733        std::vector<Liveness>* livenesses, const VarIndexMap* vregIndexMaps,
734        size_t regTypesNum, const cxuint* regRanges)
735{
736    const CodeBlock& cblock = codeBlocks[flowStack.back().blockIndex];
737    for (const auto& entry: cblock.ssaInfoMap)
738        if (entry.second.readBeforeWrite)
739        {
740            // find last
741            auto lvrit = lastVRegMap.find(entry.first);
742            if (lvrit == lastVRegMap.end())
743                continue; // not found
744            const VRegLastPos& lastPos = lvrit->second;
745            FlowStackCIter flit = lastPos.blockChain.back();
746            cxuint regType = getRegType(regTypesNum, regRanges, entry.first);
747            const VarIndexMap& vregIndexMap = vregIndexMaps[regType];
748            const std::vector<size_t>& ssaIdIndices =
749                        vregIndexMap.find(entry.first)->second;
750            Liveness& lv = livenesses[regType][ssaIdIndices[entry.second.ssaIdBefore]];
751            FlowStackCIter flitEnd = flowStack.end();
752            --flitEnd; // before last element
753            // insert live time to last seen position
754            const CodeBlock& lastBlk = codeBlocks[flit->blockIndex];
755            lv.insert(lastBlk.ssaInfoMap.find(entry.first)->second.lastPos, lastBlk.end);
756            for (++flit; flit != flitEnd; ++flit)
757            {
758                const CodeBlock& cblock = codeBlocks[flit->blockIndex];
759                size_t blockLiveTime = cblock.start;
760                lv.insert(blockLiveTime, cblock.end-cblock.start + blockLiveTime);
761            }
762        }
763}
764
765static void putCrossBlockForLoop(const std::deque<FlowStackEntry3>& flowStack,
766        const std::vector<CodeBlock>& codeBlocks,
767        std::vector<Liveness>* livenesses, const VarIndexMap* vregIndexMaps,
768        size_t regTypesNum, const cxuint* regRanges)
769{
770    auto flitStart = flowStack.end();
771    --flitStart;
772    size_t curBlock = flitStart->blockIndex;
773    // find step in way
774    while (flitStart->blockIndex != curBlock) --flitStart;
775    auto flitEnd = flowStack.end();
776    --flitEnd;
777    std::unordered_map<AsmSingleVReg, std::pair<size_t, size_t> > varMap;
778   
779    // collect var to check
780    size_t flowPos = 0;
781    for (auto flit = flitStart; flit != flitEnd; ++flit, flowPos++)
782    {
783        const CodeBlock& cblock = codeBlocks[flit->blockIndex];
784        for (const auto& entry: cblock.ssaInfoMap)
785        {
786            const SSAInfo& sinfo = entry.second;
787            size_t lastSSAId = (sinfo.ssaIdChange != 0) ? sinfo.ssaIdLast :
788                    (sinfo.readBeforeWrite) ? sinfo.ssaIdBefore : 0;
789            varMap[entry.first] = { lastSSAId, flowPos };
790        }
791    }
792    // find connections
793    flowPos = 0;
794    for (auto flit = flitStart; flit != flitEnd; ++flit, flowPos++)
795    {
796        const CodeBlock& cblock = codeBlocks[flit->blockIndex];
797        for (const auto& entry: cblock.ssaInfoMap)
798        {
799            const SSAInfo& sinfo = entry.second;
800            auto varMapIt = varMap.find(entry.first);
801            if (!sinfo.readBeforeWrite || varMapIt == varMap.end() ||
802                flowPos > varMapIt->second.second ||
803                sinfo.ssaIdBefore != varMapIt->second.first)
804                continue;
805            // just connect
806           
807            cxuint regType = getRegType(regTypesNum, regRanges, entry.first);
808            const VarIndexMap& vregIndexMap = vregIndexMaps[regType];
809            const std::vector<size_t>& ssaIdIndices =
810                        vregIndexMap.find(entry.first)->second;
811            Liveness& lv = livenesses[regType][ssaIdIndices[entry.second.ssaIdBefore]];
812           
813            if (flowPos == varMapIt->second.second)
814            {
815                // fill whole loop
816                for (auto flit2 = flitStart; flit != flitEnd; ++flit)
817                {
818                    const CodeBlock& cblock = codeBlocks[flit2->blockIndex];
819                    size_t blockLiveTime = cblock.start;
820                    lv.insert(blockLiveTime, cblock.end-cblock.start + blockLiveTime);
821                }
822                continue;
823            }
824           
825            size_t flowPos2 = 0;
826            for (auto flit2 = flitStart; flowPos2 < flowPos; ++flit2, flowPos++)
827            {
828                const CodeBlock& cblock = codeBlocks[flit2->blockIndex];
829                size_t blockLiveTime = cblock.start;
830                lv.insert(blockLiveTime, cblock.end-cblock.start + blockLiveTime);
831            }
832            // insert liveness for last block in loop of last SSAId (prev round)
833            auto flit2 = flitStart + flowPos;
834            const CodeBlock& firstBlk = codeBlocks[flit2->blockIndex];
835            lv.insert(firstBlk.start,
836                    firstBlk.ssaInfoMap.find(entry.first)->second.firstPos);
837            // insert liveness for first block in loop of last SSAId
838            flit2 = flitStart + (varMapIt->second.second+1);
839            const CodeBlock& lastBlk = codeBlocks[flit2->blockIndex];
840            lv.insert(lastBlk.ssaInfoMap.find(entry.first)->second.lastPos, lastBlk.end);
841            // fill up loop end
842            for (++flit2; flit2 != flitEnd; ++flit2)
843            {
844                const CodeBlock& cblock = codeBlocks[flit2->blockIndex];
845                size_t blockLiveTime = cblock.start;
846                lv.insert(blockLiveTime, cblock.end-cblock.start + blockLiveTime);
847            }
848        }
849    }
850}
851
852static void addUsageDeps(const cxbyte* ldeps, cxuint rvusNum,
853            const AsmRegVarUsage* rvus, LinearDepMap* ldepsOut,
854            const VarIndexMap* vregIndexMaps,
855            const std::unordered_map<AsmSingleVReg, size_t>& ssaIdIdxMap,
856            size_t regTypesNum, const cxuint* regRanges)
857{
858    // add linear deps
859    cxuint count = ldeps[0];
860    cxuint pos = 1;
861    cxbyte rvuAdded = 0;
862    for (cxuint i = 0; i < count; i++)
863    {
864        cxuint ccount = ldeps[pos++];
865        std::vector<size_t> vidxes;
866        cxuint regType = UINT_MAX;
867        cxbyte align = rvus[ldeps[pos]].align;
868        for (cxuint j = 0; j < ccount; j++)
869        {
870            rvuAdded |= 1U<<ldeps[pos];
871            const AsmRegVarUsage& rvu = rvus[ldeps[pos++]];
872            for (uint16_t k = rvu.rstart; k < rvu.rend; k++)
873            {
874                AsmSingleVReg svreg = {rvu.regVar, k};
875                auto sit = ssaIdIdxMap.find(svreg);
876                if (regType==UINT_MAX)
877                    regType = getRegType(regTypesNum, regRanges, svreg);
878                const VarIndexMap& vregIndexMap = vregIndexMaps[regType];
879                const std::vector<size_t>& ssaIdIndices =
880                            vregIndexMap.find(svreg)->second;
881                // push variable index
882                vidxes.push_back(ssaIdIndices[sit->second]);
883            }
884        }
885        ldepsOut[regType][vidxes[0]].align = align;
886        for (size_t k = 1; k < vidxes.size(); k++)
887        {
888            ldepsOut[regType][vidxes[k-1]].nextVidxes.push_back(vidxes[k]);
889            ldepsOut[regType][vidxes[k]].prevVidxes.push_back(vidxes[k-1]);
890        }
891    }
892    // add single arg linear dependencies
893    for (cxuint i = 0; i < rvusNum; i++)
894        if ((rvuAdded & (1U<<i)) == 0 && rvus[i].rstart+1<rvus[i].rend)
895        {
896            const AsmRegVarUsage& rvu = rvus[i];
897            std::vector<size_t> vidxes;
898            cxuint regType = UINT_MAX;
899            cxbyte align = rvus[i].align;
900            for (uint16_t k = rvu.rstart; k < rvu.rend; k++)
901            {
902                AsmSingleVReg svreg = {rvu.regVar, k};
903                auto sit = ssaIdIdxMap.find(svreg);
904                assert(sit != ssaIdIdxMap.end());
905                if (regType==UINT_MAX)
906                    regType = getRegType(regTypesNum, regRanges, svreg);
907                const VarIndexMap& vregIndexMap = vregIndexMaps[regType];
908                const std::vector<size_t>& ssaIdIndices =
909                            vregIndexMap.find(svreg)->second;
910                // push variable index
911                vidxes.push_back(ssaIdIndices[sit->second]);
912            }
913            ldepsOut[regType][vidxes[0]].align = align;
914            for (size_t j = 1; j < vidxes.size(); j++)
915            {
916                ldepsOut[regType][vidxes[j-1]].nextVidxes.push_back(vidxes[j]);
917                ldepsOut[regType][vidxes[j]].prevVidxes.push_back(vidxes[j-1]);
918            }
919        }
920}
921
922void AsmRegAllocator::createLivenesses(ISAUsageHandler& usageHandler,
923            size_t codeSize, const cxbyte* code)
924{
925    ISAAssembler* isaAsm = assembler.isaAssembler;
926    // construct var index maps
927    cxuint regRanges[MAX_REGTYPES_NUM*2];
928    std::fill(graphVregsCounts, graphVregsCounts+MAX_REGTYPES_NUM, size_t(0));
929    size_t regTypesNum;
930    assembler.isaAssembler->getRegisterRanges(regTypesNum, regRanges);
931   
932    for (const CodeBlock& cblock: codeBlocks)
933        for (const auto& entry: cblock.ssaInfoMap)
934        {
935            const SSAInfo& sinfo = entry.second;
936            cxuint regType = getRegType(regTypesNum, regRanges, entry.first);
937            VarIndexMap& vregIndices = vregIndexMaps[regType];
938            size_t& graphVregsCount = graphVregsCounts[regType];
939            std::vector<size_t>& ssaIdIndices = vregIndices[entry.first];
940            size_t ssaIdCount = 0;
941            if (sinfo.readBeforeWrite)
942                ssaIdCount = sinfo.ssaIdBefore+1;
943            if (sinfo.ssaIdChange!=0)
944            {
945                ssaIdCount = std::max(ssaIdCount, sinfo.ssaIdLast+1);
946                ssaIdCount = std::max(ssaIdCount, sinfo.ssaId+sinfo.ssaIdChange-1);
947                ssaIdCount = std::max(ssaIdCount, sinfo.ssaIdFirst+1);
948            }
949            if (ssaIdIndices.size() < ssaIdCount)
950                ssaIdIndices.resize(ssaIdCount, SIZE_MAX);
951           
952            if (sinfo.readBeforeWrite)
953            {
954                if (ssaIdIndices[sinfo.ssaIdBefore] == SIZE_MAX)
955                    ssaIdIndices[sinfo.ssaIdBefore] = graphVregsCount++;
956            }
957            if (sinfo.ssaIdChange!=0)
958            {
959                // fill up ssaIdIndices (with graph Ids)
960                if (ssaIdIndices[sinfo.ssaIdFirst] == SIZE_MAX)
961                    ssaIdIndices[sinfo.ssaIdFirst] = graphVregsCount++;
962                for (size_t ssaId = sinfo.ssaId+1;
963                        ssaId < sinfo.ssaId+sinfo.ssaIdChange-1; ssaId++)
964                    ssaIdIndices[ssaId] = graphVregsCount++;
965                if (ssaIdIndices[sinfo.ssaIdLast] == SIZE_MAX)
966                    ssaIdIndices[sinfo.ssaIdLast] = graphVregsCount++;
967            }
968        }
969   
970    // construct vreg liveness
971    std::deque<FlowStackEntry3> flowStack;
972    std::vector<bool> visited(codeBlocks.size(), false);
973    // hold last vreg ssaId and position
974    LastVRegMap lastVRegMap;
975    // hold start live time position for every code block
976    std::unordered_set<size_t> blockInWay;
977   
978    std::vector<Liveness> livenesses[MAX_REGTYPES_NUM];
979   
980    for (size_t i = 0; i < regTypesNum; i++)
981        livenesses[i].resize(graphVregsCounts[i]);
982   
983    size_t curLiveTime = 0;
984    flowStack.push_back({ 0, 0 });
985   
986    while (!flowStack.empty())
987    {
988        FlowStackEntry3& entry = flowStack.back();
989        CodeBlock& cblock = codeBlocks[entry.blockIndex];
990       
991        if (entry.nextIndex == 0)
992        {
993            curLiveTime = cblock.start;
994            // process current block
995            if (!blockInWay.insert(entry.blockIndex).second)
996            {
997                // if loop
998                putCrossBlockForLoop(flowStack, codeBlocks,
999                        livenesses, vregIndexMaps, regTypesNum, regRanges);
1000                flowStack.pop_back();
1001                continue;
1002            }
1003           
1004            putCrossBlockLivenesses(flowStack, codeBlocks,
1005                    lastVRegMap, livenesses, vregIndexMaps, regTypesNum, regRanges);
1006           
1007            for (const auto& sentry: cblock.ssaInfoMap)
1008            {
1009                const SSAInfo& sinfo = sentry.second;
1010                // update
1011                size_t lastSSAId =  (sinfo.ssaIdChange != 0) ? sinfo.ssaIdLast :
1012                        (sinfo.readBeforeWrite) ? sinfo.ssaIdBefore : 0;
1013                FlowStackCIter flit = flowStack.end();
1014                --flit; // to last position
1015                auto res = lastVRegMap.insert({ sentry.first, 
1016                            { lastSSAId, { flit } } });
1017                if (!res.second) // if not first seen, just update
1018                {
1019                    // update last
1020                    res.first->second.ssaId = lastSSAId;
1021                    res.first->second.blockChain.push_back(flit);
1022                }
1023            }
1024           
1025            size_t curBlockLiveEnd = cblock.end;
1026            if (!visited[entry.blockIndex])
1027            {
1028                visited[entry.blockIndex] = true;
1029                std::unordered_map<AsmSingleVReg, size_t> ssaIdIdxMap;
1030                AsmRegVarUsage instrRVUs[8];
1031                cxuint instrRVUsCount = 0;
1032               
1033                size_t oldOffset = cblock.usagePos.readOffset;
1034                std::vector<AsmSingleVReg> readSVRegs;
1035                std::vector<AsmSingleVReg> writtenSVRegs;
1036               
1037                usageHandler.setReadPos(cblock.usagePos);
1038                // register in liveness
1039                while (true)
1040                {
1041                    AsmRegVarUsage rvu = { 0U, nullptr, 0U, 0U };
1042                    size_t liveTimeNext = SIZE_MAX;
1043                    bool hasNext = false;
1044                    if (usageHandler.hasNext())
1045                    {
1046                        hasNext = true;
1047                        rvu = usageHandler.nextUsage();
1048                    }
1049                    size_t liveTime = oldOffset;
1050                    if (!hasNext || rvu.offset > oldOffset)
1051                    {
1052                        if (!writtenSVRegs.empty())
1053                            // calculate livetime for next instruction
1054                            liveTimeNext = liveTime + isaAsm->getInstructionSize(
1055                                    codeSize - oldOffset, code + oldOffset);
1056                       
1057                        ARDOut << "apply to liveness. offset: " << oldOffset << "\n";
1058                        // apply to liveness
1059                        for (AsmSingleVReg svreg: readSVRegs)
1060                        {
1061                            auto svrres = ssaIdIdxMap.insert({ svreg, 0 });
1062                            Liveness& lv = getLiveness(svreg, svrres.first->second,
1063                                    cblock.ssaInfoMap.find(svreg)->second,
1064                                    livenesses, vregIndexMaps, regTypesNum, regRanges);
1065                            if (svrres.second)
1066                                // begin region from this block
1067                                lv.newRegion(curLiveTime);
1068                            lv.expand(liveTime);
1069                        }
1070                        for (AsmSingleVReg svreg: writtenSVRegs)
1071                        {
1072                            size_t& ssaIdIdx = ssaIdIdxMap[svreg];
1073                            ssaIdIdx++;
1074                            SSAInfo& sinfo = cblock.ssaInfoMap.find(svreg)->second;
1075                            Liveness& lv = getLiveness(svreg, ssaIdIdx, sinfo,
1076                                    livenesses, vregIndexMaps, regTypesNum, regRanges);
1077                            if (liveTimeNext != curBlockLiveEnd)
1078                                // because live after this instr
1079                                lv.insert(liveTimeNext, liveTimeNext+1);
1080                            sinfo.lastPos = liveTimeNext;
1081                        }
1082                        // get linear deps and equal to
1083                        cxbyte lDeps[16];
1084                        usageHandler.getUsageDependencies(instrRVUsCount, instrRVUs, lDeps);
1085                       
1086                        addUsageDeps(lDeps, instrRVUsCount, instrRVUs,
1087                                linearDepMaps, vregIndexMaps, ssaIdIdxMap,
1088                                regTypesNum, regRanges);
1089                       
1090                        readSVRegs.clear();
1091                        writtenSVRegs.clear();
1092                        if (!hasNext)
1093                            break;
1094                        oldOffset = rvu.offset;
1095                        instrRVUsCount = 0;
1096                    }
1097                    if (hasNext && rvu.offset < cblock.end && !rvu.useRegMode)
1098                        instrRVUs[instrRVUsCount++] = rvu;
1099                    if (rvu.offset >= cblock.end)
1100                        break;
1101                   
1102                    for (uint16_t rindex = rvu.rstart; rindex < rvu.rend; rindex++)
1103                    {
1104                        // per register/singlvreg
1105                        AsmSingleVReg svreg{ rvu.regVar, rindex };
1106                        if (rvu.rwFlags == ASMRVU_WRITE && rvu.regField!=ASMFIELD_NONE)
1107                            writtenSVRegs.push_back(svreg);
1108                        else // read or treat as reading // expand previous region
1109                            readSVRegs.push_back(svreg);
1110                    }
1111                }
1112                curLiveTime += cblock.end-cblock.start;
1113            }
1114            else
1115            {
1116                // back, already visited
1117                flowStack.pop_back();
1118                continue;
1119            }
1120        }
1121        if (entry.nextIndex < cblock.nexts.size())
1122        {
1123            flowStack.push_back({ cblock.nexts[entry.nextIndex].block, 0 });
1124            entry.nextIndex++;
1125        }
1126        else if (entry.nextIndex==0 && cblock.nexts.empty() && !cblock.haveEnd)
1127        {
1128            flowStack.push_back({ entry.blockIndex+1, 0 });
1129            entry.nextIndex++;
1130        }
1131        else // back
1132        {
1133            // revert lastSSAIdMap
1134            blockInWay.erase(entry.blockIndex);
1135            flowStack.pop_back();
1136            if (!flowStack.empty())
1137            {
1138                for (const auto& sentry: cblock.ssaInfoMap)
1139                {
1140                    auto lvrit = lastVRegMap.find(sentry.first);
1141                    if (lvrit != lastVRegMap.end())
1142                    {
1143                        VRegLastPos& lastPos = lvrit->second;
1144                        lastPos.ssaId = sentry.second.ssaIdBefore;
1145                        lastPos.blockChain.pop_back();
1146                        if (lastPos.blockChain.empty()) // just remove from lastVRegs
1147                            lastVRegMap.erase(lvrit);
1148                    }
1149                }
1150            }
1151        }
1152    }
1153   
1154    // move livenesses to AsmRegAllocator outLivenesses
1155    for (size_t regType = 0; regType < regTypesNum; regType++)
1156    {
1157        std::vector<Liveness>& livenesses2 = livenesses[regType];
1158        Array<OutLiveness>& outLivenesses2 = outLivenesses[regType];
1159        outLivenesses2.resize(livenesses2.size());
1160        for (size_t li = 0; li < livenesses2.size(); li++)
1161        {
1162            outLivenesses2[li].resize(livenesses2[li].l.size());
1163            std::copy(livenesses2[li].l.begin(), livenesses2[li].l.end(),
1164                      outLivenesses2[li].begin());
1165            livenesses2[li].clear();
1166        }
1167        livenesses2.clear();
1168    }
1169}
1170
1171void AsmRegAllocator::createInterferenceGraph()
1172{
1173    /// construct liveBlockMaps
1174    std::set<LiveBlock> liveBlockMaps[MAX_REGTYPES_NUM];
1175    for (size_t regType = 0; regType < regTypesNum; regType++)
1176    {
1177        std::set<LiveBlock>& liveBlockMap = liveBlockMaps[regType];
1178        Array<OutLiveness>& liveness = outLivenesses[regType];
1179        for (size_t li = 0; li < liveness.size(); li++)
1180        {
1181            OutLiveness& lv = liveness[li];
1182            for (const std::pair<size_t, size_t>& blk: lv)
1183                if (blk.first != blk.second)
1184                    liveBlockMap.insert({ blk.first, blk.second, li });
1185            lv.clear();
1186        }
1187        liveness.clear();
1188    }
1189   
1190    // create interference graphs
1191    for (size_t regType = 0; regType < regTypesNum; regType++)
1192    {
1193        InterGraph& interGraph = interGraphs[regType];
1194        interGraph.resize(graphVregsCounts[regType]);
1195        std::set<LiveBlock>& liveBlockMap = liveBlockMaps[regType];
1196       
1197        auto lit = liveBlockMap.begin();
1198        size_t rangeStart = 0;
1199        if (lit != liveBlockMap.end())
1200            rangeStart = lit->start;
1201        while (lit != liveBlockMap.end())
1202        {
1203            const size_t blkStart = lit->start;
1204            const size_t blkEnd = lit->end;
1205            size_t rangeEnd = blkEnd;
1206            auto liStart = liveBlockMap.lower_bound({ rangeStart, 0, 0 });
1207            auto liEnd = liveBlockMap.lower_bound({ rangeEnd, 0, 0 });
1208            // collect from this range, variable indices
1209            std::set<size_t> varIndices;
1210            for (auto lit2 = liStart; lit2 != liEnd; ++lit2)
1211                varIndices.insert(lit2->vidx);
1212            // push to intergraph as full subgGraph
1213            for (auto vit = varIndices.begin(); vit != varIndices.end(); ++vit)
1214                for (auto vit2 = varIndices.begin(); vit2 != varIndices.end(); ++vit2)
1215                    if (vit != vit2)
1216                        interGraph[*vit].insert(*vit2);
1217            // go to next live blocks
1218            rangeStart = rangeEnd;
1219            for (; lit != liveBlockMap.end(); ++lit)
1220                if (lit->start != blkStart && lit->end != blkEnd)
1221                    break;
1222            if (lit == liveBlockMap.end())
1223                break; //
1224            rangeStart = std::max(rangeStart, lit->start);
1225        }
1226    }
1227}
1228
1229/* algorithm to allocate regranges:
1230 * from smallest regranges to greatest regranges:
1231 *   choosing free register: from smallest free regranges
1232 *      to greatest regranges:
1233 *         in this same regrange:
1234 *               try to find free regs in regranges
1235 *               try to link free ends of two distinct regranges
1236 */
1237
1238void AsmRegAllocator::colorInterferenceGraph()
1239{
1240    const GPUArchitecture arch = getGPUArchitectureFromDeviceType(
1241                    assembler.deviceType);
1242   
1243    for (size_t regType = 0; regType < regTypesNum; regType++)
1244    {
1245        const size_t maxColorsNum = getGPUMaxRegistersNum(arch, regType);
1246        InterGraph& interGraph = interGraphs[regType];
1247        const VarIndexMap& vregIndexMap = vregIndexMaps[regType];
1248        Array<cxuint>& gcMap = graphColorMaps[regType];
1249       
1250        const size_t nodesNum = interGraph.size();
1251        gcMap.resize(nodesNum);
1252        std::fill(gcMap.begin(), gcMap.end(), cxuint(UINT_MAX));
1253        Array<size_t> sdoCounts(nodesNum);
1254        std::fill(sdoCounts.begin(), sdoCounts.end(), 0);
1255       
1256        SDOLDOCompare compare(interGraph, sdoCounts);
1257        std::set<size_t, SDOLDOCompare> nodeSet(compare);
1258        for (size_t i = 0; i < nodesNum; i++)
1259            nodeSet.insert(i);
1260       
1261        cxuint colorsNum = 0;
1262        // firstly, allocate real registers
1263        for (const auto& entry: vregIndexMap)
1264            if (entry.first.regVar == nullptr)
1265                gcMap[entry.second[0]] = colorsNum++;
1266       
1267        for (size_t colored = 0; colored < nodesNum; colored++)
1268        {
1269            size_t node = *nodeSet.begin();
1270            if (gcMap[node] != UINT_MAX)
1271                continue; // already colored
1272            size_t color = 0;
1273           
1274            for (color = 0; color <= colorsNum; color++)
1275            {
1276                // find first usable color
1277                bool thisSame = false;
1278                for (size_t nb: interGraph[node])
1279                    if (gcMap[nb] == color)
1280                    {
1281                        thisSame = true;
1282                        break;
1283                    }
1284                if (!thisSame)
1285                    break;
1286            }
1287            if (color==colorsNum) // add new color if needed
1288            {
1289                if (colorsNum >= maxColorsNum)
1290                    throw AsmException("Too many register is needed");
1291                colorsNum++;
1292            }
1293           
1294            gcMap[node] = color;
1295            // update SDO for node
1296            bool colorExists = false;
1297            for (size_t nb: interGraph[node])
1298                if (gcMap[nb] == color)
1299                {
1300                    colorExists = true;
1301                    break;
1302                }
1303            if (!colorExists)
1304                sdoCounts[node]++;
1305            // update SDO for neighbors
1306            for (size_t nb: interGraph[node])
1307            {
1308                colorExists = false;
1309                for (size_t nb2: interGraph[nb])
1310                    if (gcMap[nb2] == color)
1311                    {
1312                        colorExists = true;
1313                        break;
1314                    }
1315                if (!colorExists)
1316                {
1317                    if (gcMap[nb] == UINT_MAX)
1318                        nodeSet.erase(nb);  // before update we erase from nodeSet
1319                    sdoCounts[nb]++;
1320                    if (gcMap[nb] == UINT_MAX)
1321                        nodeSet.insert(nb); // after update, insert again
1322                }
1323            }
1324           
1325            gcMap[node] = color;
1326        }
1327    }
1328}
1329
1330void AsmRegAllocator::allocateRegisters(cxuint sectionId)
1331{
1332    // before any operation, clear all
1333    codeBlocks.clear();
1334    for (size_t i = 0; i < MAX_REGTYPES_NUM; i++)
1335    {
1336        graphVregsCounts[i] = 0;
1337        vregIndexMaps[i].clear();
1338        interGraphs[i].clear();
1339        linearDepMaps[i].clear();
1340        graphColorMaps[i].clear();
1341    }
1342    ssaReplacesMap.clear();
1343    cxuint maxRegs[MAX_REGTYPES_NUM];
1344    assembler.isaAssembler->getMaxRegistersNum(regTypesNum, maxRegs);
1345   
1346    // set up
1347    const AsmSection& section = assembler.sections[sectionId];
1348    createCodeStructure(section.codeFlow, section.content.size(), section.content.data());
1349    createSSAData(*section.usageHandler);
1350    applySSAReplaces();
1351    createLivenesses(*section.usageHandler, section.content.size(), section.content.data());
1352    createInterferenceGraph();
1353    colorInterferenceGraph();
1354}
Note: See TracBrowser for help on using the repository browser.