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

Last change on this file since 4009 was 4009, checked in by matszpk, 7 months ago

CLRadeonExtender: AsmRegAlloc?: Fixes in the Liveness class.

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