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

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

CLRadeonExtender: AsmRegAlloc?: Add new testcase (many routines and calls) - not fully verified.

File size: 89.2 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
686/*********
687 * createLivenesses stuff
688 *********/
689
690static cxuint getRegType(size_t regTypesNum, const cxuint* regRanges,
691            const AsmSingleVReg& svreg)
692{
693    cxuint regType; // regtype
694    if (svreg.regVar!=nullptr)
695        regType = svreg.regVar->type;
696    else
697        for (regType = 0; regType < regTypesNum; regType++)
698            if (svreg.index >= regRanges[regType<<1] &&
699                svreg.index < regRanges[(regType<<1)+1])
700                break;
701    return regType;
702}
703
704static void getVIdx(const AsmSingleVReg& svreg, size_t ssaIdIdx,
705        const AsmRegAllocator::SSAInfo& ssaInfo,
706        const VarIndexMap* vregIndexMaps, size_t regTypesNum, const cxuint* regRanges,
707        cxuint& regType, size_t& vidx)
708{
709    size_t ssaId;
710    if (svreg.regVar==nullptr)
711        ssaId = 0;
712    else if (ssaIdIdx==0)
713        ssaId = ssaInfo.ssaIdBefore;
714    else if (ssaIdIdx==1)
715        ssaId = ssaInfo.ssaIdFirst;
716    else if (ssaIdIdx<ssaInfo.ssaIdChange)
717        ssaId = ssaInfo.ssaId + ssaIdIdx-1;
718    else // last
719        ssaId = ssaInfo.ssaIdLast;
720   
721    regType = getRegType(regTypesNum, regRanges, svreg); // regtype
722    const VarIndexMap& vregIndexMap = vregIndexMaps[regType];
723    const std::vector<size_t>& vidxes = vregIndexMap.find(svreg)->second;
724    /*ARDOut << "lvn[" << regType << "][" << vidxes[ssaId] << "]. ssaIdIdx: " <<
725            ssaIdIdx << ". ssaId: " << ssaId << ". svreg: " << svreg.regVar << ":" <<
726            svreg.index << "\n";*/
727    //return livenesses[regType][ssaIdIndices[ssaId]];
728    vidx = vidxes[ssaId];
729}
730
731static inline Liveness& getLiveness(const AsmSingleVReg& svreg, size_t ssaIdIdx,
732        const AsmRegAllocator::SSAInfo& ssaInfo, std::vector<Liveness>* livenesses,
733        const VarIndexMap* vregIndexMaps, size_t regTypesNum, const cxuint* regRanges)
734{
735    cxuint regType;
736    size_t vidx;
737    getVIdx(svreg, ssaIdIdx, ssaInfo, vregIndexMaps, regTypesNum, regRanges,
738            regType, vidx);
739    return livenesses[regType][vidx];
740}
741
742static void getVIdx2(const AsmSingleVReg& svreg, size_t ssaId,
743        const VarIndexMap* vregIndexMaps, size_t regTypesNum, const cxuint* regRanges,
744        cxuint& regType, size_t& vidx)
745{
746    regType = getRegType(regTypesNum, regRanges, svreg); // regtype
747    const VarIndexMap& vregIndexMap = vregIndexMaps[regType];
748    const std::vector<size_t>& vidxes = vregIndexMap.find(svreg)->second;
749    /*ARDOut << "lvn[" << regType << "][" << vidxes[ssaId] << "]. ssaId: " <<
750            ssaId << ". svreg: " << svreg.regVar << ":" << svreg.index << "\n";*/
751    vidx = vidxes[ssaId];
752}
753
754
755static void addVIdxToCallEntry(size_t blockIndex, cxuint regType, size_t vidx,
756            const std::vector<CodeBlock>& codeBlocks,
757            std::unordered_map<size_t, VIdxSetEntry>& vidxCallMap,
758            const std::unordered_map<size_t, VIdxSetEntry>& vidxRoutineMap)
759{
760    const CodeBlock& cblock = codeBlocks[blockIndex];
761    if (cblock.haveCalls)
762    {
763        VIdxSetEntry& varCallEntry = vidxCallMap[blockIndex];
764        for (const NextBlock& next: cblock.nexts)
765            if (next.isCall)
766            {
767                const auto& allLvs = vidxRoutineMap.find(next.block)->second;
768                if (allLvs.vs[regType].find(vidx) == allLvs.vs[regType].end())
769                    // add callLiveTime only if vreg not present in routine
770                    varCallEntry.vs[regType].insert(vidx);
771            }
772    }
773}
774
775static void fillUpInsideRoutine(std::unordered_set<size_t>& visited,
776            const std::vector<CodeBlock>& codeBlocks,
777            std::unordered_map<size_t, VIdxSetEntry>& vidxCallMap,
778            const std::unordered_map<size_t, VIdxSetEntry>& vidxRoutineMap,
779            size_t startBlock, const AsmSingleVReg& svreg, Liveness& lv,
780            cxuint lvRType /* lv register type */, size_t vidx)
781{
782    std::deque<FlowStackEntry3> flowStack;
783    flowStack.push_back({ startBlock, 0 });
784   
785    //if (lv.contain(codeBlocks[startBlock].end-1))
786        // already filled, then do nothing
787        //return;
788   
789    while (!flowStack.empty())
790    {
791        FlowStackEntry3& entry = flowStack.back();
792        const CodeBlock& cblock = codeBlocks[entry.blockIndex];
793       
794        if (entry.nextIndex == 0)
795        {
796            if (visited.insert(entry.blockIndex).second)
797            {
798                size_t cbStart = cblock.start;
799                if (flowStack.size() == 1)
800                {
801                    // if first block, then get last occurrence in this path
802                    auto sinfoIt = cblock.ssaInfoMap.find(svreg);
803                    if (sinfoIt != cblock.ssaInfoMap.end())
804                        cbStart = sinfoIt->second.lastPos+1;
805                }
806                // just insert
807                lv.insert(cbStart, cblock.end);
808               
809                addVIdxToCallEntry(entry.blockIndex, lvRType, vidx,
810                        codeBlocks, vidxCallMap, vidxRoutineMap);
811            }
812            else
813            {
814                flowStack.pop_back();
815                continue;
816            }
817        }
818       
819        // skip calls
820        for (; entry.nextIndex < cblock.nexts.size() &&
821                    cblock.nexts[entry.nextIndex].isCall; entry.nextIndex++);
822       
823        if (entry.nextIndex < cblock.nexts.size())
824        {
825            flowStack.push_back({ cblock.nexts[entry.nextIndex].block, 0 });
826            entry.nextIndex++;
827        }
828        else if (((entry.nextIndex==0 && cblock.nexts.empty()) ||
829                // if have any call then go to next block
830                (cblock.haveCalls && entry.nextIndex==cblock.nexts.size())) &&
831                 !cblock.haveReturn && !cblock.haveEnd)
832        {
833            flowStack.push_back({ entry.blockIndex+1, 0 });
834            entry.nextIndex++;
835        }
836        else // back
837            flowStack.pop_back();
838    }
839}
840
841static void joinVRegRecur(const std::deque<FlowStackEntry3>& flowStack,
842            const std::vector<CodeBlock>& codeBlocks, const RoutineLvMap& routineMap,
843            std::unordered_map<size_t, VIdxSetEntry>& vidxCallMap,
844            const std::unordered_map<size_t, VIdxSetEntry>& vidxRoutineMap,
845            LastVRegStackPos flowStkStart, const AsmSingleVReg& svreg, size_t ssaId,
846            const VarIndexMap* vregIndexMaps, std::vector<Liveness>* livenesses,
847            size_t regTypesNum, const cxuint* regRanges, bool skipLastBlock = false)
848{
849    struct JoinEntry
850    {
851        size_t blockIndex; // block index where is call
852        size_t nextIndex; // next index of routine call
853        size_t lastAccessIndex; // last access pos index
854        bool inSubroutines;
855    };
856   
857    FlowStackCIter flitEnd = flowStack.end();
858    if (skipLastBlock)
859        --flitEnd; // before last element
860    cxuint lvRegType;
861    size_t vidx;
862    getVIdx2(svreg, ssaId, vregIndexMaps, regTypesNum, regRanges, lvRegType, vidx);
863    Liveness& lv = livenesses[lvRegType][vidx];
864   
865    std::unordered_set<size_t> visited;
866   
867    std::stack<JoinEntry> rjStack; // routine join stack
868    if (flowStkStart.inSubroutines)
869        rjStack.push({ flowStack[flowStkStart.stackPos].blockIndex, 0, 0, true });
870   
871    while (!rjStack.empty())
872    {
873        JoinEntry& entry = rjStack.top();
874        const CodeBlock& cblock = codeBlocks[entry.blockIndex];
875       
876        if (entry.inSubroutines && entry.nextIndex < cblock.nexts.size())
877        {
878            bool doNextIndex = false; // true if to next call
879            if (cblock.nexts[entry.nextIndex].isCall)
880            {
881                const RoutineDataLv& rdata =
882                        routineMap.find(cblock.nexts[entry.nextIndex].block)->second;
883                auto lastAccessIt = rdata.lastAccessMap.find(svreg);
884                if (lastAccessIt != rdata.lastAccessMap.end())
885                {
886                    if (entry.lastAccessIndex < lastAccessIt->second.size())
887                    {
888                        const auto& lastAccess =
889                                lastAccessIt->second[entry.lastAccessIndex];
890                        rjStack.push({ lastAccess.blockIndex, 0,
891                                    0, lastAccess.inSubroutines });
892                        entry.lastAccessIndex++;
893                        if (entry.lastAccessIndex == lastAccessIt->second.size())
894                            doNextIndex = true;
895                    }
896                    else
897                        doNextIndex = true;
898                }
899                else
900                    doNextIndex = true;
901            }
902            else
903                doNextIndex = true;
904           
905            if (doNextIndex)
906            {
907                // to next call
908                entry.nextIndex++;
909                entry.lastAccessIndex = 0;
910            }
911        }
912        else
913        {
914            // fill up next block in path (do not fill start block)
915            /* if inSubroutines, then first block
916             * (that with subroutines calls) will be skipped */
917            if (rjStack.size() > 1)
918                fillUpInsideRoutine(visited, codeBlocks, vidxCallMap, vidxRoutineMap,
919                        entry.blockIndex + (entry.inSubroutines), svreg,
920                        lv, lvRegType, vidx);
921            rjStack.pop();
922        }
923    }
924   
925    /*if (flitEnd != flowStack.begin())
926    {
927        const CodeBlock& cbLast = codeBlocks[(flitEnd-1)->blockIndex];
928        if (lv.contain(cbLast.end-1))
929            // if already filled up
930            return;
931    }*/
932   
933    auto flit = flowStack.begin() + flowStkStart.stackPos + (flowStkStart.inSubroutines);
934    const CodeBlock& lastBlk = codeBlocks[flit->blockIndex];
935   
936    if (flit != flitEnd)
937    {
938        auto sinfoIt = lastBlk.ssaInfoMap.find(svreg);
939        size_t lastPos = lastBlk.start;
940        if (sinfoIt != lastBlk.ssaInfoMap.end())
941        {
942            if (flit->nextIndex > lastBlk.nexts.size())
943                // only if pass this routine
944                addVIdxToCallEntry(flit->blockIndex, lvRegType, vidx,
945                        codeBlocks, vidxCallMap, vidxRoutineMap);
946            // if begin at some point at last block
947            lastPos = sinfoIt->second.lastPos;
948            lv.insert(lastPos + 1, lastBlk.end);
949            ++flit; // skip last block in stack
950        }
951    }
952    // fill up to this
953    for (; flit != flitEnd; ++flit)
954    {
955        const CodeBlock& cblock = codeBlocks[flit->blockIndex];
956        if (flit->nextIndex > cblock.nexts.size())
957            // only if pass this routine
958            addVIdxToCallEntry(flit->blockIndex, lvRegType, vidx, codeBlocks,
959                        vidxCallMap, vidxRoutineMap);
960        lv.insert(cblock.start, cblock.end);
961    }
962}
963
964/* handle many start points in this code (for example many kernel's in same code)
965 * replace sets by vector, and sort and remove same values on demand
966 */
967
968/* join livenesses between consecutive code blocks */
969static void putCrossBlockLivenesses(const std::deque<FlowStackEntry3>& flowStack,
970        const std::vector<CodeBlock>& codeBlocks, const RoutineLvMap& routineMap,
971        std::unordered_map<size_t, VIdxSetEntry>& vidxCallMap,
972        const std::unordered_map<size_t, VIdxSetEntry>& vidxRoutineMap,
973        const LastVRegMap& lastVRegMap, std::vector<Liveness>* livenesses,
974        const VarIndexMap* vregIndexMaps, size_t regTypesNum, const cxuint* regRanges)
975{
976    ARDOut << "putCrossBlockLv block: " << flowStack.back().blockIndex << "\n";
977    const CodeBlock& cblock = codeBlocks[flowStack.back().blockIndex];
978    for (const auto& entry: cblock.ssaInfoMap)
979        if (entry.second.readBeforeWrite)
980        {
981            // find last
982            auto lvrit = lastVRegMap.find(entry.first);
983            LastVRegStackPos flowStackStart = (lvrit != lastVRegMap.end()) ?
984                lvrit->second.back() : LastVRegStackPos{ 0, false };
985           
986            joinVRegRecur(flowStack, codeBlocks, routineMap, vidxCallMap, vidxRoutineMap,
987                    flowStackStart, entry.first, entry.second.ssaIdBefore,
988                    vregIndexMaps, livenesses, regTypesNum, regRanges, true);
989        }
990}
991
992// add new join second cache entry with readBeforeWrite for all encountered regvars
993static void addJoinSecCacheEntry(const RoutineLvMap& routineMap,
994                const std::vector<CodeBlock>& codeBlocks,
995                SimpleCache<size_t, SVRegMap>& joinSecondPointsCache,
996                size_t nextBlock)
997{
998    ARDOut << "addJoinSecCacheEntry: " << nextBlock << "\n";
999    //std::stack<CallStackEntry> callStack = prevCallStack;
1000    // traverse by graph from next block
1001    std::deque<FlowStackEntry3> flowStack;
1002    flowStack.push_back({ nextBlock, 0 });
1003    std::unordered_set<size_t> visited;
1004   
1005    SVRegBlockMap alreadyReadMap;
1006    SVRegMap cacheSecPoints;
1007   
1008    while (!flowStack.empty())
1009    {
1010        FlowStackEntry3& entry = flowStack.back();
1011        const CodeBlock& cblock = codeBlocks[entry.blockIndex];
1012       
1013        if (entry.nextIndex == 0)
1014        {
1015            // process current block
1016            if (visited.insert(entry.blockIndex).second)
1017            {
1018                ARDOut << "  resolv (cache): " << entry.blockIndex << "\n";
1019               
1020                const SVRegMap* resSecondPoints =
1021                            joinSecondPointsCache.use(entry.blockIndex);
1022                if (resSecondPoints == nullptr)
1023                {
1024                    // if joinSecondPointCache not found
1025                    for (auto& sentry: cblock.ssaInfoMap)
1026                    {
1027                        const SSAInfo& sinfo = sentry.second;
1028                        auto res = alreadyReadMap.insert(
1029                                    { sentry.first, entry.blockIndex });
1030                       
1031                        if (res.second && sinfo.readBeforeWrite)
1032                            cacheSecPoints[sentry.first] = sinfo.ssaIdBefore;
1033                    }
1034                }
1035                else // to use cache
1036                {
1037                    // add to current cache sec points
1038                    for (const auto& rsentry: *resSecondPoints)
1039                    {
1040                        const bool alreadyRead =
1041                            alreadyReadMap.find(rsentry.first) != alreadyReadMap.end();
1042                        if (!alreadyRead)
1043                            cacheSecPoints[rsentry.first] = rsentry.second;
1044                    }
1045                    flowStack.pop_back();
1046                    continue;
1047                }
1048            }
1049            else
1050            {
1051                // back, already visited
1052                ARDOut << "join already (cache): " << entry.blockIndex << "\n";
1053                flowStack.pop_back();
1054                continue;
1055            }
1056        }
1057       
1058        if (entry.nextIndex < cblock.nexts.size())
1059        {
1060            flowStack.push_back({ cblock.nexts[entry.nextIndex].block, 0 });
1061            entry.nextIndex++;
1062        }
1063        else if (((entry.nextIndex==0 && cblock.nexts.empty()) ||
1064                // if have any call then go to next block
1065                (cblock.haveCalls && entry.nextIndex==cblock.nexts.size())) &&
1066                 !cblock.haveReturn && !cblock.haveEnd)
1067        {
1068            // add toResolveMap ssaIds inside called routines
1069            for (const auto& next: cblock.nexts)
1070                if (next.isCall)
1071                {
1072                    const RoutineDataLv& rdata = routineMap.find(next.block)->second;
1073                    for (const auto& v: rdata.rbwSSAIdMap)
1074                        alreadyReadMap.insert({v.first, entry.blockIndex });
1075                    for (const auto& v: rdata.lastAccessMap)
1076                        alreadyReadMap.insert({v.first, entry.blockIndex });
1077                }
1078           
1079            flowStack.push_back({ entry.blockIndex+1, 0 });
1080            entry.nextIndex++;
1081        }
1082        else // back
1083        {
1084            // remove old to resolve in leaved way to allow collecting next ssaId
1085            // before write (can be different due to earlier visit)
1086            for (const auto& next: cblock.nexts)
1087                if (next.isCall)
1088                {
1089                    const RoutineDataLv& rdata = routineMap.find(next.block)->second;
1090                    for (const auto& v: rdata.rbwSSAIdMap)
1091                    {
1092                        auto it = alreadyReadMap.find(v.first);
1093                        if (it != alreadyReadMap.end() && it->second == entry.blockIndex)
1094                            alreadyReadMap.erase(it);
1095                    }
1096                    for (const auto& v: rdata.lastAccessMap)
1097                    {
1098                        auto it = alreadyReadMap.find(v.first);
1099                        if (it != alreadyReadMap.end() && it->second == entry.blockIndex)
1100                            alreadyReadMap.erase(it);
1101                    }
1102                }
1103           
1104            for (const auto& sentry: cblock.ssaInfoMap)
1105            {
1106                auto it = alreadyReadMap.find(sentry.first);
1107                if (it != alreadyReadMap.end() && it->second == entry.blockIndex)
1108                    // remove old to resolve in leaved way to allow collecting next ssaId
1109                    // before write (can be different due to earlier visit)
1110                    alreadyReadMap.erase(it);
1111            }
1112            ARDOut << "  popjoin (cache)\n";
1113            flowStack.pop_back();
1114        }
1115    }
1116   
1117    joinSecondPointsCache.put(nextBlock, cacheSecPoints);
1118}
1119
1120// apply calls (changes from these calls) from code blocks to stack var map
1121static void applyCallToStackVarMap(const CodeBlock& cblock, const RoutineLvMap& routineMap,
1122        LastStackPosMap& stackVarMap, size_t pfPos, size_t nextIndex)
1123{
1124    for (const NextBlock& next: cblock.nexts)
1125        if (next.isCall)
1126        {
1127            ARDOut << "  japplycall: " << pfPos << ": " <<
1128                    nextIndex << ": " << next.block << "\n";
1129            const LastAccessMap& regVarMap =
1130                    routineMap.find(next.block)->second.lastAccessMap;
1131            for (const auto& sentry: regVarMap)
1132            {
1133                // MSVC error fix
1134                auto& v = stackVarMap[sentry.first];
1135                v = LastVRegStackPos{ pfPos, true };
1136            }
1137        }
1138}
1139
1140static void joinRegVarLivenesses(const std::deque<FlowStackEntry3>& prevFlowStack,
1141        const std::vector<CodeBlock>& codeBlocks, const RoutineLvMap& routineMap,
1142        std::unordered_map<size_t, VIdxSetEntry>& vidxCallMap,
1143        const std::unordered_map<size_t, VIdxSetEntry>& vidxRoutineMap,
1144        const PrevWaysIndexMap& prevWaysIndexMap,
1145        const std::vector<bool>& waysToCache, ResSecondPointsToCache& cblocksToCache,
1146        SimpleCache<size_t, LastStackPosMap>& joinFirstPointsCache,
1147        SimpleCache<size_t, SVRegMap>& joinSecondPointsCache,
1148        const VarIndexMap* vregIndexMaps,
1149        std::vector<Liveness>* livenesses, size_t regTypesNum, const cxuint* regRanges)
1150{
1151    size_t nextBlock = prevFlowStack.back().blockIndex;
1152    auto pfEnd = prevFlowStack.end();
1153    --pfEnd;
1154    ARDOut << "startJoinLv: " << (pfEnd-1)->blockIndex << "," << nextBlock << "\n";
1155    // key - varreg, value - last position in previous flowStack
1156    LastStackPosMap stackVarMap;
1157   
1158    size_t pfStartIndex = 0;
1159    {
1160        auto pfPrev = pfEnd;
1161        --pfPrev;
1162        auto it = prevWaysIndexMap.find(pfPrev->blockIndex);
1163        if (it != prevWaysIndexMap.end())
1164        {
1165            const LastStackPosMap* cached = joinFirstPointsCache.use(it->second.first);
1166            if (cached!=nullptr)
1167            {
1168                ARDOut << "use pfcached: " << it->second.first << ", " <<
1169                        it->second.second << "\n";
1170                stackVarMap = *cached;
1171                pfStartIndex = it->second.second+1;
1172               
1173                // apply missing calls at end of the cached
1174                const CodeBlock& cblock = codeBlocks[it->second.first];
1175               
1176                const FlowStackEntry3& entry = *(prevFlowStack.begin()+pfStartIndex-1);
1177                if (entry.nextIndex > cblock.nexts.size())
1178                    applyCallToStackVarMap(cblock, routineMap, stackVarMap,
1179                                    pfStartIndex-1, -1);
1180            }
1181        }
1182    }
1183   
1184    for (auto pfit = prevFlowStack.begin()+pfStartIndex; pfit != pfEnd; ++pfit)
1185    {
1186        const FlowStackEntry3& entry = *pfit;
1187        const CodeBlock& cblock = codeBlocks[entry.blockIndex];
1188        for (const auto& sentry: cblock.ssaInfoMap)
1189        {
1190            // MSVC error fix
1191            auto& v = stackVarMap[sentry.first];
1192            v = { size_t(pfit - prevFlowStack.begin()), false };
1193        }
1194       
1195        if (entry.nextIndex > cblock.nexts.size())
1196            applyCallToStackVarMap(cblock, routineMap, stackVarMap,
1197                        pfit - prevFlowStack.begin(), entry.nextIndex);
1198       
1199        // put to first point cache
1200        if (waysToCache[pfit->blockIndex] &&
1201            !joinFirstPointsCache.hasKey(pfit->blockIndex))
1202        {
1203            ARDOut << "put pfcache " << pfit->blockIndex << "\n";
1204            joinFirstPointsCache.put(pfit->blockIndex, stackVarMap);
1205        }
1206    }
1207   
1208    SVRegMap cacheSecPoints;
1209    const bool toCache = (!joinSecondPointsCache.hasKey(nextBlock)) &&
1210                cblocksToCache.count(nextBlock)>=2;
1211   
1212    // traverse by graph from next block
1213    std::deque<FlowStackEntry3> flowStack;
1214    flowStack.push_back({ nextBlock, 0 });
1215    std::vector<bool> visited(codeBlocks.size(), false);
1216   
1217    // already read in current path
1218    // key - vreg, value - source block where vreg of conflict found
1219    SVRegMap alreadyReadMap;
1220   
1221    while (!flowStack.empty())
1222    {
1223        FlowStackEntry3& entry = flowStack.back();
1224        const CodeBlock& cblock = codeBlocks[entry.blockIndex];
1225       
1226        if (entry.nextIndex == 0)
1227        {
1228            // process current block
1229            if (!visited[entry.blockIndex])
1230            {
1231                visited[entry.blockIndex] = true;
1232                ARDOut << "  lvjoin: " << entry.blockIndex << "\n";
1233               
1234                const SVRegMap* joinSecondPoints =
1235                        joinSecondPointsCache.use(entry.blockIndex);
1236               
1237                if (joinSecondPoints == nullptr)
1238                    for (const auto& sentry: cblock.ssaInfoMap)
1239                    {
1240                        const SSAInfo& sinfo = sentry.second;
1241                        auto res = alreadyReadMap.insert(
1242                                    { sentry.first, entry.blockIndex });
1243                       
1244                        if (toCache)
1245                            cacheSecPoints[sentry.first] = sinfo.ssaIdBefore;
1246                       
1247                        if (res.second && sinfo.readBeforeWrite)
1248                        {
1249                            auto it = stackVarMap.find(sentry.first);
1250                            LastVRegStackPos stackPos = (it != stackVarMap.end() ?
1251                                        it->second : LastVRegStackPos{ 0, false });
1252                           
1253                            joinVRegRecur(prevFlowStack, codeBlocks, routineMap,
1254                                vidxCallMap, vidxRoutineMap,
1255                                stackPos, sentry.first, sentry.second.ssaIdBefore,
1256                                vregIndexMaps, livenesses, regTypesNum, regRanges, true);
1257                        }
1258                    }
1259                else
1260                {
1261                    ARDOut << "use join secPointCache: " << entry.blockIndex << "\n";
1262                    // add to current cache sec points
1263                    for (const auto& rsentry: *joinSecondPoints)
1264                    {
1265                        const bool alreadyRead =
1266                            alreadyReadMap.find(rsentry.first) != alreadyReadMap.end();
1267                       
1268                        if (!alreadyRead)
1269                        {
1270                            if (toCache)
1271                                cacheSecPoints[rsentry.first] = rsentry.second;
1272                           
1273                            auto it = stackVarMap.find(rsentry.first);
1274                            LastVRegStackPos stackPos = (it != stackVarMap.end() ?
1275                                        it->second : LastVRegStackPos{ 0, false });
1276                           
1277                            joinVRegRecur(prevFlowStack, codeBlocks, routineMap,
1278                                vidxCallMap, vidxRoutineMap,
1279                                stackPos, rsentry.first, rsentry.second, vregIndexMaps,
1280                                livenesses, regTypesNum, regRanges, true);
1281                        }
1282                    }
1283                    flowStack.pop_back();
1284                    continue;
1285                }
1286            }
1287            else
1288            {
1289                cblocksToCache.increase(entry.blockIndex);
1290                ARDOut << "jcblockToCache: " << entry.blockIndex << "=" <<
1291                            cblocksToCache.count(entry.blockIndex) << "\n";
1292                // back, already visited
1293                ARDOut << "join already: " << entry.blockIndex << "\n";
1294                flowStack.pop_back();
1295                continue;
1296            }
1297        }
1298       
1299        if (entry.nextIndex < cblock.nexts.size())
1300        {
1301            flowStack.push_back({ cblock.nexts[entry.nextIndex].block, 0 });
1302            entry.nextIndex++;
1303        }
1304        else if (((entry.nextIndex==0 && cblock.nexts.empty()) ||
1305                // if have any call then go to next block
1306                (cblock.haveCalls && entry.nextIndex==cblock.nexts.size())) &&
1307                 !cblock.haveReturn && !cblock.haveEnd)
1308        {
1309            // add toResolveMap ssaIds inside called routines
1310            for (const auto& next: cblock.nexts)
1311                if (next.isCall)
1312                {
1313                    const RoutineDataLv& rdata = routineMap.find(next.block)->second;
1314                    for (const auto& v: rdata.rbwSSAIdMap)
1315                        alreadyReadMap.insert({v.first, entry.blockIndex });
1316                    for (const auto& v: rdata.lastAccessMap)
1317                        alreadyReadMap.insert({v.first, entry.blockIndex });
1318                }
1319           
1320            flowStack.push_back({ entry.blockIndex+1, 0 });
1321            entry.nextIndex++;
1322        }
1323        else // back
1324        {
1325            // remove old to resolve in leaved way to allow collecting next ssaId
1326            // before write (can be different due to earlier visit)
1327            for (const auto& next: cblock.nexts)
1328                if (next.isCall)
1329                {
1330                    const RoutineDataLv& rdata = routineMap.find(next.block)->second;
1331                    for (const auto& v: rdata.rbwSSAIdMap)
1332                    {
1333                        auto it = alreadyReadMap.find(v.first);
1334                        if (it != alreadyReadMap.end() && it->second == entry.blockIndex)
1335                            alreadyReadMap.erase(it);
1336                    }
1337                    for (const auto& v: rdata.lastAccessMap)
1338                    {
1339                        auto it = alreadyReadMap.find(v.first);
1340                        if (it != alreadyReadMap.end() && it->second == entry.blockIndex)
1341                            alreadyReadMap.erase(it);
1342                    }
1343                }
1344           
1345            for (const auto& sentry: cblock.ssaInfoMap)
1346            {
1347                auto it = alreadyReadMap.find(sentry.first);
1348                if (it != alreadyReadMap.end() && it->second == entry.blockIndex)
1349                    // remove old to resolve in leaved way to allow collecting next ssaId
1350                    // before write (can be different due to earlier visit)
1351                    alreadyReadMap.erase(it);
1352            }
1353            ARDOut << "  popjoin\n";
1354           
1355            if (cblocksToCache.count(entry.blockIndex)==2 &&
1356                !joinSecondPointsCache.hasKey(entry.blockIndex))
1357                // add to cache
1358                addJoinSecCacheEntry(routineMap, codeBlocks, joinSecondPointsCache,
1359                            entry.blockIndex);
1360           
1361            flowStack.pop_back();
1362        }
1363    }
1364   
1365    if (toCache)
1366        joinSecondPointsCache.put(nextBlock, cacheSecPoints);
1367}
1368
1369static void addUsageDeps(const cxbyte* ldeps, cxuint rvusNum,
1370            const AsmRegVarUsage* rvus, LinearDepMap* ldepsOut,
1371            const VarIndexMap* vregIndexMaps, const SVRegMap& ssaIdIdxMap,
1372            size_t regTypesNum, const cxuint* regRanges)
1373{
1374    // add linear deps
1375    cxuint count = ldeps[0];
1376    cxuint pos = 1;
1377    cxbyte rvuAdded = 0;
1378    for (cxuint i = 0; i < count; i++)
1379    {
1380        cxuint ccount = ldeps[pos++];
1381        std::vector<size_t> vidxes;
1382        cxuint regType = UINT_MAX;
1383        cxbyte align = rvus[ldeps[pos]].align;
1384        for (cxuint j = 0; j < ccount; j++)
1385        {
1386            rvuAdded |= 1U<<ldeps[pos];
1387            const AsmRegVarUsage& rvu = rvus[ldeps[pos++]];
1388            if (rvu.regVar == nullptr)
1389                continue;
1390            for (uint16_t k = rvu.rstart; k < rvu.rend; k++)
1391            {
1392                AsmSingleVReg svreg = {rvu.regVar, k};
1393                auto sit = ssaIdIdxMap.find(svreg);
1394                if (regType==UINT_MAX)
1395                    regType = getRegType(regTypesNum, regRanges, svreg);
1396                const VarIndexMap& vregIndexMap = vregIndexMaps[regType];
1397                const std::vector<size_t>& ssaIdIndices =
1398                            vregIndexMap.find(svreg)->second;
1399                // push variable index
1400                vidxes.push_back(ssaIdIndices[sit->second]);
1401            }
1402        }
1403        ldepsOut[regType][vidxes[0]].align = align;
1404        for (size_t k = 1; k < vidxes.size(); k++)
1405        {
1406            ldepsOut[regType][vidxes[k-1]].nextVidxes.insertValue(vidxes[k]);
1407            ldepsOut[regType][vidxes[k]].prevVidxes.insertValue(vidxes[k-1]);
1408        }
1409    }
1410    // add single arg linear dependencies
1411    for (cxuint i = 0; i < rvusNum; i++)
1412        if ((rvuAdded & (1U<<i)) == 0 && rvus[i].rstart+1<rvus[i].rend)
1413        {
1414            const AsmRegVarUsage& rvu = rvus[i];
1415            if (rvu.regVar == nullptr)
1416                continue;
1417            std::vector<size_t> vidxes;
1418            cxuint regType = UINT_MAX;
1419            cxbyte align = rvus[i].align;
1420            for (uint16_t k = rvu.rstart; k < rvu.rend; k++)
1421            {
1422                AsmSingleVReg svreg = {rvu.regVar, k};
1423                auto sit = ssaIdIdxMap.find(svreg);
1424                assert(sit != ssaIdIdxMap.end());
1425                if (regType==UINT_MAX)
1426                    regType = getRegType(regTypesNum, regRanges, svreg);
1427                const VarIndexMap& vregIndexMap = vregIndexMaps[regType];
1428                const std::vector<size_t>& ssaIdIndices =
1429                            vregIndexMap.find(svreg)->second;
1430                // push variable index
1431                vidxes.push_back(ssaIdIndices[sit->second]);
1432            }
1433            ldepsOut[regType][vidxes[0]].align = align;
1434            for (size_t j = 1; j < vidxes.size(); j++)
1435            {
1436                ldepsOut[regType][vidxes[j-1]].nextVidxes.insertValue(vidxes[j]);
1437                ldepsOut[regType][vidxes[j]].prevVidxes.insertValue(vidxes[j-1]);
1438            }
1439        }
1440}
1441
1442static void joinRoutineDataLv(RoutineDataLv& dest, VIdxSetEntry& destVars,
1443            RoutineCurAccessMap& curSVRegMap, FlowStackEntry4& entry,
1444            const RoutineDataLv& src, const VIdxSetEntry& srcVars)
1445{
1446    dest.rbwSSAIdMap.insert(src.rbwSSAIdMap.begin(), src.rbwSSAIdMap.end());
1447    for (size_t i = 0; i < MAX_REGTYPES_NUM; i++)
1448        destVars.vs[i].insert(srcVars.vs[i].begin(), srcVars.vs[i].end());
1449   
1450    // join source lastAccessMap with curSVRegMap
1451    for (const auto& sentry: src.lastAccessMap)
1452    {
1453        auto res = curSVRegMap.insert({ sentry.first, { entry.blockIndex, true } });
1454        if (!res.second)
1455        {   // not added because is present in map
1456            if (res.first->second.blockIndex != entry.blockIndex)
1457                entry.prevCurSVRegMap.insert(*res.first);
1458            // otherwise, it is same code block but inside routines
1459            // and do not change prevCurSVRegMap for revert
1460            // update entry
1461            res.first->second = { entry.blockIndex, true };
1462        }
1463        else
1464            entry.prevCurSVRegMap.insert({ sentry.first, { SIZE_MAX, true } });
1465    }
1466}
1467
1468static void createRoutineDataLv(const std::vector<CodeBlock>& codeBlocks,
1469        const RoutineLvMap& routineMap,
1470        const std::unordered_map<size_t, VIdxSetEntry>& vidxRoutineMap,
1471        RoutineDataLv& rdata, VIdxSetEntry& routineVIdxes,
1472        size_t routineBlock, const VarIndexMap* vregIndexMaps,
1473        size_t regTypesNum, const cxuint* regRanges)
1474{
1475    std::deque<FlowStackEntry4> flowStack;
1476    std::unordered_set<size_t> visited;
1477   
1478    // already read in current path
1479    // key - vreg, value - source block where vreg of conflict found
1480    SVRegMap alreadyReadMap;
1481    std::unordered_set<AsmSingleVReg> vregsNotInAllRets;
1482    std::unordered_set<AsmSingleVReg> vregsInFirstReturn;
1483   
1484    bool notFirstReturn = false;
1485    flowStack.push_back({ routineBlock, 0 });
1486    RoutineCurAccessMap curSVRegMap; // key - svreg, value - block index
1487   
1488    while (!flowStack.empty())
1489    {
1490        FlowStackEntry4& entry = flowStack.back();
1491        const CodeBlock& cblock = codeBlocks[entry.blockIndex];
1492       
1493        if (entry.nextIndex == 0)
1494        {
1495            // process current block
1496            if (visited.insert(entry.blockIndex).second)
1497            {
1498                for (const auto& sentry: cblock.ssaInfoMap)
1499                {
1500                    if (sentry.second.readBeforeWrite)
1501                        if (alreadyReadMap.insert(
1502                                    { sentry.first, entry.blockIndex }).second)
1503                        {
1504                            auto res = rdata.rbwSSAIdMap.insert({ sentry.first,
1505                                        sentry.second.ssaIdBefore });
1506                            if (res.second && notFirstReturn)
1507                                // first readBeforeWrite and notFirstReturn
1508                                vregsNotInAllRets.insert(sentry.first);
1509                        }
1510                   
1511                    auto res = curSVRegMap.insert({ sentry.first,
1512                        LastAccessBlockPos{ entry.blockIndex, false } });
1513                    if (!res.second)
1514                    {   // not added because is present in map
1515                        entry.prevCurSVRegMap.insert(*res.first);
1516                        res.first->second = { entry.blockIndex, false };
1517                    }
1518                    else
1519                        entry.prevCurSVRegMap.insert(
1520                                        { sentry.first, { SIZE_MAX, false } });
1521                   
1522                    // all SSAs
1523                    const SSAInfo& sinfo = sentry.second;
1524                    const AsmSingleVReg& svreg = sentry.first;
1525                    cxuint regType = getRegType(regTypesNum, regRanges, svreg);
1526                    const VarIndexMap& vregIndexMap = vregIndexMaps[regType];
1527                    const std::vector<size_t>& vidxes =
1528                                vregIndexMap.find(svreg)->second;
1529                   
1530                    // add SSA indices to allSSAs
1531                    if (sinfo.readBeforeWrite)
1532                        routineVIdxes.vs[regType].insert(vidxes[sinfo.ssaIdBefore]);
1533                    if (sinfo.ssaIdChange != 0)
1534                    {
1535                        routineVIdxes.vs[regType].insert(vidxes[sinfo.ssaIdFirst]);
1536                        for (size_t i = 1; i < sinfo.ssaIdChange; i++)
1537                            routineVIdxes.vs[regType].insert(vidxes[sinfo.ssaId+i]);
1538                        routineVIdxes.vs[regType].insert(vidxes[sinfo.ssaIdLast]);
1539                    }
1540                }
1541            }
1542            else
1543            {
1544                flowStack.pop_back();
1545                continue;
1546            }
1547        }
1548       
1549        // join and skip calls
1550        {
1551            std::vector<size_t> calledRoutines;
1552            for (; entry.nextIndex < cblock.nexts.size() &&
1553                        cblock.nexts[entry.nextIndex].isCall; entry.nextIndex++)
1554            {
1555                size_t rblock = cblock.nexts[entry.nextIndex].block;
1556                if (rblock != routineBlock)
1557                    calledRoutines.push_back(rblock);
1558            }
1559           
1560            for (size_t srcRoutBlock: calledRoutines)
1561            {
1562                // update svregs 'not in all returns'
1563                const RoutineDataLv& srcRdata = routineMap.find(srcRoutBlock)->second;
1564                if (notFirstReturn)
1565                    for (const auto& vrentry: srcRdata.rbwSSAIdMap)
1566                        if (rdata.rbwSSAIdMap.find(vrentry.first)==rdata.rbwSSAIdMap.end())
1567                            vregsNotInAllRets.insert(vrentry.first);
1568               
1569                joinRoutineDataLv(rdata, routineVIdxes, curSVRegMap, entry,
1570                        srcRdata, vidxRoutineMap.find(srcRoutBlock)->second);
1571            }
1572        }
1573       
1574        if (entry.nextIndex < cblock.nexts.size())
1575        {
1576            flowStack.push_back({ cblock.nexts[entry.nextIndex].block, 0 });
1577            entry.nextIndex++;
1578        }
1579        else if (((entry.nextIndex==0 && cblock.nexts.empty()) ||
1580                // if have any call then go to next block
1581                (cblock.haveCalls && entry.nextIndex==cblock.nexts.size())) &&
1582                 !cblock.haveReturn && !cblock.haveEnd)
1583        {
1584            flowStack.push_back({ entry.blockIndex+1, 0 });
1585            entry.nextIndex++;
1586        }
1587        else
1588        {
1589            if (cblock.haveReturn)
1590            {
1591                // handle return
1592                // add curSVReg access positions to lastAccessMap
1593                for (const auto& entry: curSVRegMap)
1594                {
1595                    auto res = rdata.lastAccessMap.insert({ entry.first,
1596                                    { entry.second } });
1597                    if (!res.second)
1598                        res.first->second.insertValue(entry.second);
1599                    if (!notFirstReturn)
1600                        // fill up vregs for first return
1601                        vregsInFirstReturn.insert(entry.first);
1602                }
1603                if (notFirstReturn)
1604                    for (const AsmSingleVReg& vreg: vregsInFirstReturn)
1605                        if (curSVRegMap.find(vreg) == curSVRegMap.end())
1606                            // not found in this path then add to 'not in all paths'
1607                            vregsNotInAllRets.insert(vreg);
1608               
1609                notFirstReturn = true;
1610            }
1611            // revert curSVRegMap
1612            for (const auto& sentry: entry.prevCurSVRegMap)
1613                if (sentry.second.blockIndex != SIZE_MAX)
1614                    curSVRegMap.find(sentry.first)->second = sentry.second;
1615                else // no before that
1616                    curSVRegMap.erase(sentry.first);
1617           
1618            for (const auto& sentry: cblock.ssaInfoMap)
1619            {
1620                auto it = alreadyReadMap.find(sentry.first);
1621                if (it != alreadyReadMap.end() && it->second == entry.blockIndex)
1622                    // remove old to resolve in leaved way to allow collecting next ssaId
1623                    // before write (can be different due to earlier visit)
1624                    alreadyReadMap.erase(it);
1625            }
1626            ARDOut << "  popjoin\n";
1627            flowStack.pop_back();
1628        }
1629    }
1630   
1631    // handle unused svregs in this path (from routine start) and
1632    // used other paths and have this same ssaId as at routine start.
1633    // just add to lastAccessMap svreg for start to join through all routine
1634    for (const AsmSingleVReg& svreg: vregsNotInAllRets)
1635    {
1636        auto res = rdata.lastAccessMap.insert({ svreg, { { routineBlock, false } } });
1637        if (!res.second)
1638            res.first->second.insertValue({ routineBlock, false });
1639    }
1640}
1641
1642static inline void revertLastSVReg(LastVRegMap& lastVRegMap, const AsmSingleVReg& svreg)
1643{
1644    auto lvrit = lastVRegMap.find(svreg);
1645    if (lvrit != lastVRegMap.end())
1646    {
1647        std::vector<LastVRegStackPos>& lastPos = lvrit->second;
1648        lastPos.pop_back();
1649        if (lastPos.empty()) // just remove from lastVRegs
1650            lastVRegMap.erase(lvrit);
1651    }
1652}
1653
1654/* TODO: handling livenesses between routine call:
1655 *   for any routine call in call point:
1656 *     add extra liveness point which will be added to liveness of the vars used between
1657 *     call point and to liveness of the vars used inside routine
1658 */
1659
1660void AsmRegAllocator::createLivenesses(ISAUsageHandler& usageHandler)
1661{
1662    ARDOut << "----- createLivenesses ------\n";
1663    // construct var index maps
1664    cxuint regRanges[MAX_REGTYPES_NUM*2];
1665    std::fill(graphVregsCounts, graphVregsCounts+MAX_REGTYPES_NUM, size_t(0));
1666    size_t regTypesNum;
1667    assembler.isaAssembler->getRegisterRanges(regTypesNum, regRanges);
1668   
1669    for (const CodeBlock& cblock: codeBlocks)
1670        for (const auto& entry: cblock.ssaInfoMap)
1671        {
1672            const SSAInfo& sinfo = entry.second;
1673            cxuint regType = getRegType(regTypesNum, regRanges, entry.first);
1674            VarIndexMap& vregIndices = vregIndexMaps[regType];
1675            size_t& graphVregsCount = graphVregsCounts[regType];
1676            std::vector<size_t>& vidxes = vregIndices[entry.first];
1677            size_t ssaIdCount = 0;
1678            if (sinfo.readBeforeWrite)
1679                ssaIdCount = sinfo.ssaIdBefore+1;
1680            if (sinfo.ssaIdChange!=0)
1681            {
1682                ssaIdCount = std::max(ssaIdCount, sinfo.ssaIdLast+1);
1683                ssaIdCount = std::max(ssaIdCount, sinfo.ssaId+sinfo.ssaIdChange-1);
1684                ssaIdCount = std::max(ssaIdCount, sinfo.ssaIdFirst+1);
1685            }
1686            // if not readBeforeWrite and neither ssaIdChanges but it is write to
1687            // normal register
1688            if (entry.first.regVar==nullptr)
1689                ssaIdCount = 1;
1690           
1691            if (vidxes.size() < ssaIdCount)
1692                vidxes.resize(ssaIdCount, SIZE_MAX);
1693           
1694            // set liveness index to vidxes
1695            if (sinfo.readBeforeWrite)
1696            {
1697                if (vidxes[sinfo.ssaIdBefore] == SIZE_MAX)
1698                    vidxes[sinfo.ssaIdBefore] = graphVregsCount++;
1699            }
1700            if (sinfo.ssaIdChange!=0)
1701            {
1702                // fill up vidxes (with graph Ids)
1703                if (vidxes[sinfo.ssaIdFirst] == SIZE_MAX)
1704                    vidxes[sinfo.ssaIdFirst] = graphVregsCount++;
1705                for (size_t ssaId = sinfo.ssaId+1;
1706                        ssaId < sinfo.ssaId+sinfo.ssaIdChange-1; ssaId++)
1707                    vidxes[ssaId] = graphVregsCount++;
1708                if (vidxes[sinfo.ssaIdLast] == SIZE_MAX)
1709                    vidxes[sinfo.ssaIdLast] = graphVregsCount++;
1710            }
1711            // if not readBeforeWrite and neither ssaIdChanges but it is write to
1712            // normal register
1713            if (entry.first.regVar==nullptr && vidxes[0] == SIZE_MAX)
1714                vidxes[0] = graphVregsCount++;
1715        }
1716   
1717    // construct vreg liveness
1718    std::deque<CallStackEntry2> callStack;
1719    std::deque<FlowStackEntry3> flowStack;
1720    std::vector<bool> visited(codeBlocks.size(), false);
1721    // hold last vreg ssaId and position
1722    LastVRegMap lastVRegMap;
1723   
1724    // key - current res first key, value - previous first key and its flowStack pos
1725    PrevWaysIndexMap prevWaysIndexMap;
1726    // to track ways last block indices pair: block index, flowStackPos)
1727    std::pair<size_t, size_t> lastCommonCacheWayPoint{ SIZE_MAX, SIZE_MAX };
1728    std::vector<bool> waysToCache(codeBlocks.size(), false);
1729    ResSecondPointsToCache cblocksToCache(codeBlocks.size());
1730   
1731    size_t rbwCount = 0;
1732    size_t wrCount = 0;
1733   
1734    RoutineLvMap routineMap;
1735    std::vector<Liveness> livenesses[MAX_REGTYPES_NUM];
1736   
1737    for (size_t i = 0; i < regTypesNum; i++)
1738        livenesses[i].resize(graphVregsCounts[i]);
1739   
1740    // callLiveTime - call live time where routine will be called
1741    // reverse counted, begin from SIZE_MAX, used for joining svreg from routines
1742    // and svreg used in this time
1743    size_t curLiveTime = 0;
1744    flowStack.push_back({ 0, 0 });
1745   
1746    while (!flowStack.empty())
1747    {
1748        FlowStackEntry3& entry = flowStack.back();
1749        CodeBlock& cblock = codeBlocks[entry.blockIndex];
1750       
1751        if (entry.nextIndex == 0)
1752        {
1753            curLiveTime = cblock.start;
1754            // process current block
1755            if (!visited[entry.blockIndex])
1756            {
1757                visited[entry.blockIndex] = true;
1758                ARDOut << "joinpush: " << entry.blockIndex << "\n";
1759                if (flowStack.size() > 1)
1760                    putCrossBlockLivenesses(flowStack, codeBlocks, routineMap,
1761                            vidxCallMap, vidxRoutineMap, lastVRegMap,
1762                            livenesses, vregIndexMaps, regTypesNum, regRanges);
1763                // update last vreg position
1764                for (const auto& sentry: cblock.ssaInfoMap)
1765                {
1766                    // update
1767                    auto res = lastVRegMap.insert({ sentry.first,
1768                                { { flowStack.size()-1, false } } });
1769                    if (!res.second) // if not first seen, just update
1770                        // update last
1771                        res.first->second.push_back({ flowStack.size()-1, false });
1772                   
1773                    // count read before writes (for cache weight)
1774                    if (sentry.second.readBeforeWrite)
1775                        rbwCount++;
1776                    if (sentry.second.ssaIdChange!=0)
1777                        wrCount++;
1778                }
1779               
1780                // main routine to handle ssaInfos
1781                SVRegMap ssaIdIdxMap;
1782                AsmRegVarUsage instrRVUs[8];
1783                cxuint instrRVUsCount = 0;
1784               
1785                size_t oldOffset = cblock.usagePos.readOffset;
1786                std::vector<AsmSingleVReg> readSVRegs;
1787                std::vector<AsmSingleVReg> writtenSVRegs;
1788               
1789                usageHandler.setReadPos(cblock.usagePos);
1790                // register in liveness
1791                while (true)
1792                {
1793                    AsmRegVarUsage rvu = { 0U, nullptr, 0U, 0U };
1794                    bool hasNext = false;
1795                    if (usageHandler.hasNext() && oldOffset < cblock.end)
1796                    {
1797                        hasNext = true;
1798                        rvu = usageHandler.nextUsage();
1799                    }
1800                    const size_t liveTime = oldOffset;
1801                    if ((!hasNext || rvu.offset > oldOffset) && oldOffset < cblock.end)
1802                    {
1803                        ARDOut << "apply to liveness. offset: " << oldOffset << "\n";
1804                        // apply to liveness
1805                        for (AsmSingleVReg svreg: readSVRegs)
1806                        {
1807                            auto svrres = ssaIdIdxMap.insert({ svreg, 0 });
1808                            Liveness& lv = getLiveness(svreg, svrres.first->second,
1809                                    cblock.ssaInfoMap.find(svreg)->second,
1810                                    livenesses, vregIndexMaps, regTypesNum, regRanges);
1811                            if (svrres.second)
1812                                // begin region from this block
1813                                lv.newRegion(curLiveTime);
1814                            lv.expand(liveTime);
1815                        }
1816                        for (AsmSingleVReg svreg: writtenSVRegs)
1817                        {
1818                            size_t& ssaIdIdx = ssaIdIdxMap[svreg];
1819                            if (svreg.regVar != nullptr)
1820                                ssaIdIdx++;
1821                            SSAInfo& sinfo = cblock.ssaInfoMap.find(svreg)->second;
1822                            Liveness& lv = getLiveness(svreg, ssaIdIdx, sinfo,
1823                                    livenesses, vregIndexMaps, regTypesNum, regRanges);
1824                            // works only with ISA where smallest instruction have 2 bytes!
1825                            // after previous read, but not after instruction.
1826                            // if var is not used anywhere then this liveness region
1827                            // blocks assignment for other vars
1828                            lv.insert(liveTime+1, liveTime+2);
1829                        }
1830                        // get linear deps and equal to
1831                        cxbyte lDeps[16];
1832                        usageHandler.getUsageDependencies(instrRVUsCount, instrRVUs, lDeps);
1833                       
1834                        addUsageDeps(lDeps, instrRVUsCount, instrRVUs,
1835                                linearDepMaps, vregIndexMaps, ssaIdIdxMap,
1836                                regTypesNum, regRanges);
1837                       
1838                        readSVRegs.clear();
1839                        writtenSVRegs.clear();
1840                        if (!hasNext)
1841                            break;
1842                        oldOffset = rvu.offset;
1843                        instrRVUsCount = 0;
1844                    }
1845                    if (hasNext && oldOffset < cblock.end && !rvu.useRegMode)
1846                        instrRVUs[instrRVUsCount++] = rvu;
1847                    if (oldOffset >= cblock.end)
1848                        break;
1849                   
1850                    for (uint16_t rindex = rvu.rstart; rindex < rvu.rend; rindex++)
1851                    {
1852                        // per register/singlvreg
1853                        AsmSingleVReg svreg{ rvu.regVar, rindex };
1854                        if (rvu.rwFlags == ASMRVU_WRITE && rvu.regField!=ASMFIELD_NONE)
1855                            writtenSVRegs.push_back(svreg);
1856                        else // read or treat as reading // expand previous region
1857                            readSVRegs.push_back(svreg);
1858                    }
1859                }
1860            }
1861            else
1862            {
1863                cblocksToCache.increase(entry.blockIndex);
1864                ARDOut << "jcblockToCache: " << entry.blockIndex << "=" <<
1865                            cblocksToCache.count(entry.blockIndex) << "\n";
1866               
1867                // back, already visited
1868                flowStack.pop_back();
1869               
1870                size_t curWayBIndex = flowStack.back().blockIndex;
1871                if (lastCommonCacheWayPoint.first != SIZE_MAX)
1872                {
1873                    // mark point of way to cache (res first point)
1874                    waysToCache[lastCommonCacheWayPoint.first] = true;
1875                    ARDOut << "mark to pfcache " <<
1876                            lastCommonCacheWayPoint.first << ", " <<
1877                            curWayBIndex << "\n";
1878                    prevWaysIndexMap[curWayBIndex] = lastCommonCacheWayPoint;
1879                }
1880                lastCommonCacheWayPoint = { curWayBIndex, flowStack.size()-1 };
1881                ARDOut << "lastCcwP: " << curWayBIndex << "\n";
1882                continue;
1883            }
1884        }
1885       
1886        if (!callStack.empty() &&
1887            entry.blockIndex == callStack.back().callBlock &&
1888            entry.nextIndex-1 == callStack.back().callNextIndex)
1889        {
1890            ARDOut << " ret: " << entry.blockIndex << "\n";
1891            const size_t routineBlock = callStack.back().routineBlock;
1892            auto res = routineMap.insert({ routineBlock, { } });
1893           
1894            if (res.second)
1895            {
1896                auto varRes = vidxRoutineMap.insert({ routineBlock, VIdxSetEntry{} });
1897                createRoutineDataLv(codeBlocks, routineMap, vidxRoutineMap,
1898                        res.first->second, varRes.first->second,
1899                        routineBlock, vregIndexMaps, regTypesNum, regRanges);
1900            }
1901            else
1902            {
1903                // already added join livenesses from all readBeforeWrites
1904                for (const auto& entry: res.first->second.rbwSSAIdMap)
1905                {
1906                    // find last
1907                    auto lvrit = lastVRegMap.find(entry.first);
1908                    LastVRegStackPos flowStackStart = (lvrit != lastVRegMap.end()) ?
1909                            lvrit->second.back() : LastVRegStackPos{ 0, false };
1910                   
1911                    joinVRegRecur(flowStack, codeBlocks, routineMap,
1912                                  vidxCallMap, vidxRoutineMap,
1913                            flowStackStart, entry.first, entry.second, vregIndexMaps,
1914                            livenesses, regTypesNum, regRanges, false);
1915                }
1916            }
1917            callStack.pop_back(); // just return from call
1918        }
1919       
1920        if (entry.nextIndex < cblock.nexts.size())
1921        {
1922            //bool isCall = false;
1923            size_t nextBlock = cblock.nexts[entry.nextIndex].block;
1924            if (cblock.nexts[entry.nextIndex].isCall)
1925            {
1926                callStack.push_back({ entry.blockIndex, entry.nextIndex, nextBlock });
1927                //isCall = true;
1928            }
1929           
1930            flowStack.push_back({ cblock.nexts[entry.nextIndex].block, 0 });
1931            entry.nextIndex++;
1932        }
1933        else if (((entry.nextIndex==0 && cblock.nexts.empty()) ||
1934                // if have any call then go to next block
1935                (cblock.haveCalls && entry.nextIndex==cblock.nexts.size())) &&
1936                 !cblock.haveReturn && !cblock.haveEnd)
1937        {
1938            if (entry.nextIndex!=0) // if back from calls (just return from calls)
1939            {
1940                std::unordered_set<AsmSingleVReg> regSVRegs;
1941                // just add last access of svreg from call routines to lastVRegMap
1942                // and join svregs from routine with svreg used at this time
1943                for (const NextBlock& next: cblock.nexts)
1944                    if (next.isCall)
1945                    {
1946                        const RoutineDataLv& rdata = routineMap.find(next.block)->second;
1947                        for (const auto& entry: rdata.lastAccessMap)
1948                            if (regSVRegs.insert(entry.first).second)
1949                            {
1950                                auto res = lastVRegMap.insert({ entry.first,
1951                                        { { flowStack.size()-1, true } } });
1952                                if (!res.second) // if not first seen, just update
1953                                    // update last
1954                                    res.first->second.push_back(
1955                                                { flowStack.size()-1, true });
1956                            }
1957                    }
1958            }
1959           
1960            flowStack.push_back({ entry.blockIndex+1, 0 });
1961            entry.nextIndex++;
1962        }
1963        else // back
1964        {
1965            // revert lastSSAIdMap
1966            flowStack.pop_back();
1967           
1968            // revert lastVRegs in call
1969            std::unordered_set<AsmSingleVReg> revertedSVRegs;
1970            for (const NextBlock& next: cblock.nexts)
1971                if (next.isCall)
1972                {
1973                    const RoutineDataLv& rdata = routineMap.find(next.block)->second;
1974                    for (const auto& entry: rdata.lastAccessMap)
1975                        if (revertedSVRegs.insert(entry.first).second)
1976                            revertLastSVReg(lastVRegMap, entry.first);
1977                }
1978           
1979            for (const auto& sentry: cblock.ssaInfoMap)
1980                revertLastSVReg(lastVRegMap, sentry.first);
1981           
1982            if (!flowStack.empty() && lastCommonCacheWayPoint.first != SIZE_MAX &&
1983                    lastCommonCacheWayPoint.second >= flowStack.size())
1984            {
1985                lastCommonCacheWayPoint =
1986                        { flowStack.back().blockIndex, flowStack.size()-1 };
1987                ARDOut << "POPlastCcwP: " << lastCommonCacheWayPoint.first << "\n";
1988            }
1989        }
1990    }
1991   
1992    // after, that resolve joins (join with already visited code)
1993    // SVRegMap in this cache: key - vreg, value - last flowStack entry position
1994    SimpleCache<size_t, LastStackPosMap> joinFirstPointsCache(wrCount<<1);
1995    // SVRegMap in this cache: key - vreg, value - first readBefore in second part
1996    SimpleCache<size_t, SVRegMap> joinSecondPointsCache(rbwCount<<1);
1997   
1998    flowStack.clear();
1999    std::fill(visited.begin(), visited.end(), false);
2000   
2001    flowStack.push_back({ 0, 0 });
2002   
2003    while (!flowStack.empty())
2004    {
2005        FlowStackEntry3& entry = flowStack.back();
2006        CodeBlock& cblock = codeBlocks[entry.blockIndex];
2007       
2008        if (entry.nextIndex == 0)
2009        {
2010            // process current block
2011            if (!visited[entry.blockIndex])
2012                visited[entry.blockIndex] = true;
2013            else
2014            {
2015                joinRegVarLivenesses(flowStack, codeBlocks, routineMap,
2016                        vidxCallMap, vidxRoutineMap,
2017                        prevWaysIndexMap, waysToCache, cblocksToCache,
2018                        joinFirstPointsCache, joinSecondPointsCache,
2019                        vregIndexMaps, livenesses, regTypesNum, regRanges);
2020                // back, already visited
2021                flowStack.pop_back();
2022                continue;
2023            }
2024        }
2025       
2026        if (entry.nextIndex < cblock.nexts.size())
2027        {
2028            flowStack.push_back({ cblock.nexts[entry.nextIndex].block, 0 });
2029            entry.nextIndex++;
2030        }
2031        else if (((entry.nextIndex==0 && cblock.nexts.empty()) ||
2032                // if have any call then go to next block
2033                (cblock.haveCalls && entry.nextIndex==cblock.nexts.size())) &&
2034                 !cblock.haveReturn && !cblock.haveEnd)
2035        {
2036            flowStack.push_back({ entry.blockIndex+1, 0 });
2037            entry.nextIndex++;
2038        }
2039        else // back
2040        {
2041            if (cblocksToCache.count(entry.blockIndex)==2 &&
2042                !joinSecondPointsCache.hasKey(entry.blockIndex))
2043                // add to cache
2044                addJoinSecCacheEntry(routineMap, codeBlocks, joinSecondPointsCache,
2045                            entry.blockIndex);
2046            flowStack.pop_back();
2047        }
2048    }
2049   
2050    // move livenesses to AsmRegAllocator outLivenesses
2051    for (size_t regType = 0; regType < regTypesNum; regType++)
2052    {
2053        std::vector<Liveness>& livenesses2 = livenesses[regType];
2054        Array<OutLiveness>& outLivenesses2 = outLivenesses[regType];
2055        outLivenesses2.resize(livenesses2.size());
2056        for (size_t li = 0; li < livenesses2.size(); li++)
2057        {
2058            outLivenesses2[li].resize(livenesses2[li].l.size());
2059            std::copy(livenesses2[li].l.begin(), livenesses2[li].l.end(),
2060                      outLivenesses2[li].begin());
2061            livenesses2[li].clear();
2062        }
2063        livenesses2.clear();
2064    }
2065}
2066
2067void AsmRegAllocator::createInterferenceGraph()
2068{
2069    /// construct liveBlockMaps
2070    std::set<LiveBlock> liveBlockMaps[MAX_REGTYPES_NUM];
2071    for (size_t regType = 0; regType < regTypesNum; regType++)
2072    {
2073        std::set<LiveBlock>& liveBlockMap = liveBlockMaps[regType];
2074        Array<OutLiveness>& liveness = outLivenesses[regType];
2075        for (size_t li = 0; li < liveness.size(); li++)
2076        {
2077            OutLiveness& lv = liveness[li];
2078            for (const std::pair<size_t, size_t>& blk: lv)
2079                if (blk.first != blk.second)
2080                    liveBlockMap.insert({ blk.first, blk.second, li });
2081            lv.clear();
2082        }
2083        liveness.clear();
2084    }
2085   
2086    // create interference graphs
2087    for (size_t regType = 0; regType < regTypesNum; regType++)
2088    {
2089        InterGraph& interGraph = interGraphs[regType];
2090        interGraph.resize(graphVregsCounts[regType]);
2091        std::set<LiveBlock>& liveBlockMap = liveBlockMaps[regType];
2092       
2093        auto lit = liveBlockMap.begin();
2094        size_t rangeStart = 0;
2095        if (lit != liveBlockMap.end())
2096            rangeStart = lit->start;
2097        while (lit != liveBlockMap.end())
2098        {
2099            const size_t blkStart = lit->start;
2100            const size_t blkEnd = lit->end;
2101            size_t rangeEnd = blkEnd;
2102            auto liStart = liveBlockMap.lower_bound({ rangeStart, 0, 0 });
2103            auto liEnd = liveBlockMap.lower_bound({ rangeEnd, 0, 0 });
2104            // collect from this range, variable indices
2105            std::set<size_t> varIndices;
2106            for (auto lit2 = liStart; lit2 != liEnd; ++lit2)
2107                varIndices.insert(lit2->vidx);
2108            // push to intergraph as full subgGraph
2109            for (auto vit = varIndices.begin(); vit != varIndices.end(); ++vit)
2110                for (auto vit2 = varIndices.begin(); vit2 != varIndices.end(); ++vit2)
2111                    if (vit != vit2)
2112                        interGraph[*vit].insert(*vit2);
2113            // go to next live blocks
2114            rangeStart = rangeEnd;
2115            for (; lit != liveBlockMap.end(); ++lit)
2116                if (lit->start != blkStart && lit->end != blkEnd)
2117                    break;
2118            if (lit == liveBlockMap.end())
2119                break; //
2120            rangeStart = std::max(rangeStart, lit->start);
2121        }
2122    }
2123}
2124
2125/* algorithm to allocate regranges:
2126 * from smallest regranges to greatest regranges:
2127 *   choosing free register: from smallest free regranges
2128 *      to greatest regranges:
2129 *         in this same regrange:
2130 *               try to find free regs in regranges
2131 *               try to link free ends of two distinct regranges
2132 */
2133
2134void AsmRegAllocator::colorInterferenceGraph()
2135{
2136    const GPUArchitecture arch = getGPUArchitectureFromDeviceType(
2137                    assembler.deviceType);
2138   
2139    for (size_t regType = 0; regType < regTypesNum; regType++)
2140    {
2141        const size_t maxColorsNum = getGPUMaxRegistersNum(arch, regType);
2142        InterGraph& interGraph = interGraphs[regType];
2143        const VarIndexMap& vregIndexMap = vregIndexMaps[regType];
2144        Array<cxuint>& gcMap = graphColorMaps[regType];
2145       
2146        const size_t nodesNum = interGraph.size();
2147        gcMap.resize(nodesNum);
2148        std::fill(gcMap.begin(), gcMap.end(), cxuint(UINT_MAX));
2149        Array<size_t> sdoCounts(nodesNum);
2150        std::fill(sdoCounts.begin(), sdoCounts.end(), 0);
2151       
2152        SDOLDOCompare compare(interGraph, sdoCounts);
2153        std::set<size_t, SDOLDOCompare> nodeSet(compare);
2154        for (size_t i = 0; i < nodesNum; i++)
2155            nodeSet.insert(i);
2156       
2157        cxuint colorsNum = 0;
2158        // firstly, allocate real registers
2159        for (const auto& entry: vregIndexMap)
2160            if (entry.first.regVar == nullptr)
2161                gcMap[entry.second[0]] = colorsNum++;
2162       
2163        for (size_t colored = 0; colored < nodesNum; colored++)
2164        {
2165            size_t node = *nodeSet.begin();
2166            if (gcMap[node] != UINT_MAX)
2167                continue; // already colored
2168            size_t color = 0;
2169           
2170            for (color = 0; color <= colorsNum; color++)
2171            {
2172                // find first usable color
2173                bool thisSame = false;
2174                for (size_t nb: interGraph[node])
2175                    if (gcMap[nb] == color)
2176                    {
2177                        thisSame = true;
2178                        break;
2179                    }
2180                if (!thisSame)
2181                    break;
2182            }
2183            if (color==colorsNum) // add new color if needed
2184            {
2185                if (colorsNum >= maxColorsNum)
2186                    throw AsmException("Too many register is needed");
2187                colorsNum++;
2188            }
2189           
2190            gcMap[node] = color;
2191            // update SDO for node
2192            bool colorExists = false;
2193            for (size_t nb: interGraph[node])
2194                if (gcMap[nb] == color)
2195                {
2196                    colorExists = true;
2197                    break;
2198                }
2199            if (!colorExists)
2200                sdoCounts[node]++;
2201            // update SDO for neighbors
2202            for (size_t nb: interGraph[node])
2203            {
2204                colorExists = false;
2205                for (size_t nb2: interGraph[nb])
2206                    if (gcMap[nb2] == color)
2207                    {
2208                        colorExists = true;
2209                        break;
2210                    }
2211                if (!colorExists)
2212                {
2213                    if (gcMap[nb] == UINT_MAX)
2214                        nodeSet.erase(nb);  // before update we erase from nodeSet
2215                    sdoCounts[nb]++;
2216                    if (gcMap[nb] == UINT_MAX)
2217                        nodeSet.insert(nb); // after update, insert again
2218                }
2219            }
2220           
2221            gcMap[node] = color;
2222        }
2223    }
2224}
2225
2226void AsmRegAllocator::allocateRegisters(cxuint sectionId)
2227{
2228    // before any operation, clear all
2229    codeBlocks.clear();
2230    for (size_t i = 0; i < MAX_REGTYPES_NUM; i++)
2231    {
2232        graphVregsCounts[i] = 0;
2233        vregIndexMaps[i].clear();
2234        interGraphs[i].clear();
2235        linearDepMaps[i].clear();
2236        graphColorMaps[i].clear();
2237    }
2238    ssaReplacesMap.clear();
2239    cxuint maxRegs[MAX_REGTYPES_NUM];
2240    assembler.isaAssembler->getMaxRegistersNum(regTypesNum, maxRegs);
2241   
2242    // set up
2243    const AsmSection& section = assembler.sections[sectionId];
2244    createCodeStructure(section.codeFlow, section.content.size(), section.content.data());
2245    createSSAData(*section.usageHandler);
2246    applySSAReplaces();
2247    createLivenesses(*section.usageHandler);
2248    createInterferenceGraph();
2249    colorInterferenceGraph();
2250}
Note: See TracBrowser for help on using the repository browser.