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

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

CLRadeonExtender: AsmRegAlloc?: Change LastVRegMap def: map of vectors of LastAccessBlockPos? instead sizes.

File size: 82.1 KB
Line 
1/*
2 *  CLRadeonExtender - Unofficial OpenCL Radeon Extensions Library
3 *  Copyright (C) 2014-2018 Mateusz Szpakowski
4 *
5 *  This library is free software; you can redistribute it and/or
6 *  modify it under the terms of the GNU Lesser General Public
7 *  License as published by the Free Software Foundation; either
8 *  version 2.1 of the License, or (at your option) any later version.
9 *
10 *  This library is distributed in the hope that it will be useful,
11 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
12 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
13 *  Lesser General Public License for more details.
14 *
15 *  You should have received a copy of the GNU Lesser General Public
16 *  License along with this library; if not, write to the Free Software
17 *  Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
18 */
19
20#include <CLRX/Config.h>
21#include <assert.h>
22#include <iostream>
23#include <stack>
24#include <deque>
25#include <vector>
26#include <utility>
27#include <unordered_set>
28#include <map>
29#include <set>
30#include <unordered_map>
31#include <algorithm>
32#include <CLRX/utils/Utilities.h>
33#include <CLRX/utils/Containers.h>
34#include <CLRX/amdasm/Assembler.h>
35#include "AsmInternals.h"
36#include "AsmRegAlloc.h"
37
38using namespace CLRX;
39
40#if ASMREGALLOC_DEBUGDUMP
41std::ostream& operator<<(std::ostream& os, const CLRX::BlockIndex& v)
42{
43    if (v.pass==0)
44        return os << v.index;
45    else
46        return os << v.index << "#" << v.pass;
47}
48#endif
49
50ISAUsageHandler::ISAUsageHandler(const std::vector<cxbyte>& _content) :
51            content(_content), lastOffset(0), readOffset(0), instrStructPos(0),
52            regUsagesPos(0), regUsages2Pos(0), regVarUsagesPos(0),
53            pushedArgs(0), argPos(0), argFlags(0), isNext(false), useRegMode(false)
54{ }
55
56ISAUsageHandler::~ISAUsageHandler()
57{ }
58
59void ISAUsageHandler::rewind()
60{
61    readOffset = instrStructPos = 0;
62    regUsagesPos = regUsages2Pos = regVarUsagesPos = 0;
63    useRegMode = false;
64    pushedArgs = 0;
65    skipBytesInInstrStruct();
66}
67
68void ISAUsageHandler::skipBytesInInstrStruct()
69{
70    // do not add instruction size if usereg (usereg immediately before instr regusages)
71    if ((instrStructPos != 0 || argPos != 0) && !useRegMode)
72        readOffset += defaultInstrSize;
73    argPos = 0;
74    for (;instrStructPos < instrStruct.size() &&
75        instrStruct[instrStructPos] > 0x80; instrStructPos++)
76        readOffset += (instrStruct[instrStructPos] & 0x7f);
77    isNext = (instrStructPos < instrStruct.size());
78}
79
80void ISAUsageHandler::putSpace(size_t offset)
81{
82    if (lastOffset != offset)
83    {
84        flush(); // flush before new instruction
85        // useReg immediately before instruction regusages
86        size_t defaultInstrSize = (!useRegMode ? this->defaultInstrSize : 0);
87        if (lastOffset > offset)
88            throw AsmException("Offset before previous instruction");
89        if (!instrStruct.empty() && offset - lastOffset < defaultInstrSize)
90            throw AsmException("Offset between previous instruction");
91        size_t toSkip = !instrStruct.empty() ? 
92                offset - lastOffset - defaultInstrSize : offset;
93        while (toSkip > 0)
94        {
95            size_t skipped = std::min(toSkip, size_t(0x7f));
96            instrStruct.push_back(skipped | 0x80);
97            toSkip -= skipped;
98        }
99        lastOffset = offset;
100        argFlags = 0;
101        pushedArgs = 0;
102    } 
103}
104
105void ISAUsageHandler::pushUsage(const AsmRegVarUsage& rvu)
106{
107    if (lastOffset == rvu.offset && useRegMode)
108        flush(); // only flush if useRegMode and no change in offset
109    else // otherwise
110        putSpace(rvu.offset);
111    useRegMode = false;
112    if (rvu.regVar != nullptr)
113    {
114        argFlags |= (1U<<pushedArgs);
115        regVarUsages.push_back({ rvu.regVar, rvu.rstart, rvu.rend, rvu.regField,
116            rvu.rwFlags, rvu.align });
117    }
118    else // reg usages
119        regUsages.push_back({ rvu.regField,cxbyte(rvu.rwFlags |
120                    getRwFlags(rvu.regField, rvu.rstart, rvu.rend)) });
121    pushedArgs++;
122}
123
124void ISAUsageHandler::pushUseRegUsage(const AsmRegVarUsage& rvu)
125{
126    if (lastOffset == rvu.offset && !useRegMode)
127        flush(); // only flush if useRegMode and no change in offset
128    else // otherwise
129        putSpace(rvu.offset);
130    useRegMode = true;
131    if (pushedArgs == 0 || pushedArgs == 256)
132    {
133        argFlags = 0;
134        pushedArgs = 0;
135        instrStruct.push_back(0x80); // sign of regvarusage from usereg
136        instrStruct.push_back(0);
137    }
138    if (rvu.regVar != nullptr)
139    {
140        argFlags |= (1U<<(pushedArgs & 7));
141        regVarUsages.push_back({ rvu.regVar, rvu.rstart, rvu.rend, rvu.regField,
142            rvu.rwFlags, rvu.align });
143    }
144    else // reg usages
145        regUsages2.push_back({ rvu.rstart, rvu.rend, rvu.rwFlags });
146    pushedArgs++;
147    if ((pushedArgs & 7) == 0) // just flush per 8 bit
148    {
149        instrStruct.push_back(argFlags);
150        instrStruct[instrStruct.size() - ((pushedArgs+7) >> 3) - 1] = pushedArgs;
151        argFlags = 0;
152    }
153}
154
155void ISAUsageHandler::flush()
156{
157    if (pushedArgs != 0)
158    {
159        if (!useRegMode)
160        {
161            // normal regvarusages
162            instrStruct.push_back(argFlags);
163            if ((argFlags & (1U<<(pushedArgs-1))) != 0)
164                regVarUsages.back().rwFlags |= 0x80;
165            else // reg usages
166                regUsages.back().rwFlags |= 0x80;
167        }
168        else
169        {
170            // use reg regvarusages
171            if ((pushedArgs & 7) != 0) //if only not pushed args remains
172                instrStruct.push_back(argFlags);
173            instrStruct[instrStruct.size() - ((pushedArgs+7) >> 3) - 1] = pushedArgs;
174        }
175    }
176}
177
178AsmRegVarUsage ISAUsageHandler::nextUsage()
179{
180    if (!isNext)
181        throw AsmException("No reg usage in this code");
182    AsmRegVarUsage rvu;
183    // get regvarusage
184    bool lastRegUsage = false;
185    rvu.offset = readOffset;
186    if (!useRegMode && instrStruct[instrStructPos] == 0x80)
187    {
188        // useRegMode (begin fetching useregs)
189        useRegMode = true;
190        argPos = 0;
191        instrStructPos++;
192        // pushedArgs - numer of useregs, 0 - 256 useregs
193        pushedArgs = instrStruct[instrStructPos++];
194        argFlags = instrStruct[instrStructPos];
195    }
196    rvu.useRegMode = useRegMode; // no ArgPos
197   
198    if ((instrStruct[instrStructPos] & (1U << (argPos&7))) != 0)
199    {
200        // regvar usage
201        const AsmRegVarUsageInt& inRVU = regVarUsages[regVarUsagesPos++];
202        rvu.regVar = inRVU.regVar;
203        rvu.rstart = inRVU.rstart;
204        rvu.rend = inRVU.rend;
205        rvu.regField = inRVU.regField;
206        rvu.rwFlags = inRVU.rwFlags & ASMRVU_ACCESS_MASK;
207        rvu.align = inRVU.align;
208        if (!useRegMode)
209            lastRegUsage = ((inRVU.rwFlags&0x80) != 0);
210    }
211    else if (!useRegMode)
212    {
213        // simple reg usage
214        const AsmRegUsageInt& inRU = regUsages[regUsagesPos++];
215        rvu.regVar = nullptr;
216        const std::pair<uint16_t, uint16_t> regPair =
217                    getRegPair(inRU.regField, inRU.rwFlags);
218        rvu.rstart = regPair.first;
219        rvu.rend = regPair.second;
220        rvu.rwFlags = (inRU.rwFlags & ASMRVU_ACCESS_MASK);
221        rvu.regField = inRU.regField;
222        rvu.align = 0;
223        lastRegUsage = ((inRU.rwFlags&0x80) != 0);
224    }
225    else
226    {
227        // use reg (simple reg usage, second structure)
228        const AsmRegUsage2Int& inRU = regUsages2[regUsages2Pos++];
229        rvu.regVar = nullptr;
230        rvu.rstart = inRU.rstart;
231        rvu.rend = inRU.rend;
232        rvu.rwFlags = inRU.rwFlags;
233        rvu.regField = ASMFIELD_NONE;
234        rvu.align = 0;
235    }
236    argPos++;
237    if (useRegMode)
238    {
239        // if inside useregs
240        if (argPos == (pushedArgs&0xff))
241        {
242            instrStructPos++; // end
243            skipBytesInInstrStruct();
244            useRegMode = false;
245        }
246        else if ((argPos & 7) == 0) // fetch new flag
247        {
248            instrStructPos++;
249            argFlags = instrStruct[instrStructPos];
250        }
251    }
252    // after instr
253    if (lastRegUsage)
254    {
255        instrStructPos++;
256        skipBytesInInstrStruct();
257    }
258    return rvu;
259}
260
261AsmRegAllocator::AsmRegAllocator(Assembler& _assembler) : assembler(_assembler)
262{ }
263
264AsmRegAllocator::AsmRegAllocator(Assembler& _assembler,
265        const std::vector<CodeBlock>& _codeBlocks, const SSAReplacesMap& _ssaReplacesMap)
266        : assembler(_assembler), codeBlocks(_codeBlocks), ssaReplacesMap(_ssaReplacesMap)
267{ }
268
269static inline bool codeBlockStartLess(const AsmRegAllocator::CodeBlock& c1,
270                  const AsmRegAllocator::CodeBlock& c2)
271{ return c1.start < c2.start; }
272
273static inline bool codeBlockEndLess(const AsmRegAllocator::CodeBlock& c1,
274                  const AsmRegAllocator::CodeBlock& c2)
275{ return c1.end < c2.end; }
276
277void AsmRegAllocator::createCodeStructure(const std::vector<AsmCodeFlowEntry>& codeFlow,
278             size_t codeSize, const cxbyte* code)
279{
280    ISAAssembler* isaAsm = assembler.isaAssembler;
281    if (codeSize == 0)
282        return;
283    std::vector<size_t> splits;
284    std::vector<size_t> codeStarts;
285    std::vector<size_t> codeEnds;
286    codeStarts.push_back(0);
287    codeEnds.push_back(codeSize);
288    for (const AsmCodeFlowEntry& entry: codeFlow)
289    {
290        size_t instrAfter = 0;
291        if (entry.type == AsmCodeFlowType::JUMP || entry.type == AsmCodeFlowType::CJUMP ||
292            entry.type == AsmCodeFlowType::CALL || entry.type == AsmCodeFlowType::RETURN)
293            instrAfter = entry.offset + isaAsm->getInstructionSize(
294                        codeSize - entry.offset, code + entry.offset);
295       
296        switch(entry.type)
297        {
298            case AsmCodeFlowType::START:
299                codeStarts.push_back(entry.offset);
300                break;
301            case AsmCodeFlowType::END:
302                codeEnds.push_back(entry.offset);
303                break;
304            case AsmCodeFlowType::JUMP:
305                splits.push_back(entry.target);
306                codeEnds.push_back(instrAfter);
307                break;
308            case AsmCodeFlowType::CJUMP:
309                splits.push_back(entry.target);
310                splits.push_back(instrAfter);
311                break;
312            case AsmCodeFlowType::CALL:
313                splits.push_back(entry.target);
314                splits.push_back(instrAfter);
315                break;
316            case AsmCodeFlowType::RETURN:
317                codeEnds.push_back(instrAfter);
318                break;
319            default:
320                break;
321        }
322    }
323    std::sort(splits.begin(), splits.end());
324    splits.resize(std::unique(splits.begin(), splits.end()) - splits.begin());
325    std::sort(codeEnds.begin(), codeEnds.end());
326    codeEnds.resize(std::unique(codeEnds.begin(), codeEnds.end()) - codeEnds.begin());
327    // remove codeStarts between codeStart and codeEnd
328    size_t i = 0;
329    size_t ii = 0;
330    size_t ei = 0; // codeEnd i
331    while (i < codeStarts.size())
332    {
333        size_t end = (ei < codeEnds.size() ? codeEnds[ei] : SIZE_MAX);
334        if (ei < codeEnds.size())
335            ei++;
336        codeStarts[ii++] = codeStarts[i];
337        // skip codeStart to end
338        for (i++ ;i < codeStarts.size() && codeStarts[i] < end; i++);
339    }
340    codeStarts.resize(ii);
341    // add next codeStarts
342    auto splitIt = splits.begin();
343    for (size_t codeEnd: codeEnds)
344    {
345        auto it = std::lower_bound(splitIt, splits.end(), codeEnd);
346        if (it != splits.end())
347        {
348            codeStarts.push_back(*it);
349            splitIt = it;
350        }
351        else // if end
352            break;
353    }
354   
355    std::sort(codeStarts.begin(), codeStarts.end());
356    codeStarts.resize(std::unique(codeStarts.begin(), codeStarts.end()) -
357                codeStarts.begin());
358    // divide to blocks
359    splitIt = splits.begin();
360    for (size_t codeStart: codeStarts)
361    {
362        size_t codeEnd = *std::upper_bound(codeEnds.begin(), codeEnds.end(), codeStart);
363        splitIt = std::lower_bound(splitIt, splits.end(), codeStart);
364       
365        if (splitIt != splits.end() && *splitIt==codeStart)
366            ++splitIt; // skip split in codeStart
367       
368        for (size_t start = codeStart; start < codeEnd; )
369        {
370            size_t end = codeEnd;
371            if (splitIt != splits.end())
372            {
373                end = std::min(end, *splitIt);
374                ++splitIt;
375            }
376            codeBlocks.push_back({ start, end, { }, false, false, false });
377            start = end;
378        }
379    }
380    // force empty block at end if some jumps goes to its
381    if (!codeEnds.empty() && !codeStarts.empty() && !splits.empty() &&
382        codeStarts.back()==codeEnds.back() && codeStarts.back() == splits.back())
383        codeBlocks.push_back({ codeStarts.back(), codeStarts.back(), { },
384                             false, false, false });
385   
386    // construct flow-graph
387    for (const AsmCodeFlowEntry& entry: codeFlow)
388        if (entry.type == AsmCodeFlowType::CALL || entry.type == AsmCodeFlowType::JUMP ||
389            entry.type == AsmCodeFlowType::CJUMP || entry.type == AsmCodeFlowType::RETURN)
390        {
391            std::vector<CodeBlock>::iterator it;
392            size_t instrAfter = entry.offset + isaAsm->getInstructionSize(
393                        codeSize - entry.offset, code + entry.offset);
394           
395            if (entry.type != AsmCodeFlowType::RETURN)
396                it = binaryFind(codeBlocks.begin(), codeBlocks.end(),
397                        CodeBlock{ entry.target }, codeBlockStartLess);
398            else // return
399            {
400                it = binaryFind(codeBlocks.begin(), codeBlocks.end(),
401                        CodeBlock{ 0, instrAfter }, codeBlockEndLess);
402                // if block have return
403                if (it != codeBlocks.end())
404                    it->haveEnd = it->haveReturn = true;
405                continue;
406            }
407           
408            if (it == codeBlocks.end())
409                continue; // error!
410            auto it2 = std::lower_bound(codeBlocks.begin(), codeBlocks.end(),
411                    CodeBlock{ instrAfter }, codeBlockStartLess);
412            auto curIt = it2;
413            --curIt;
414           
415            curIt->nexts.push_back({ size_t(it - codeBlocks.begin()),
416                        entry.type == AsmCodeFlowType::CALL });
417            curIt->haveCalls |= entry.type == AsmCodeFlowType::CALL;
418            if (entry.type == AsmCodeFlowType::CJUMP ||
419                 entry.type == AsmCodeFlowType::CALL)
420            {
421                curIt->haveEnd = false; // revert haveEnd if block have cond jump or call
422                if (it2 != codeBlocks.end() && entry.type == AsmCodeFlowType::CJUMP)
423                    // add next next block (only for cond jump)
424                    curIt->nexts.push_back({ size_t(it2 - codeBlocks.begin()), false });
425            }
426            else if (entry.type == AsmCodeFlowType::JUMP)
427                curIt->haveEnd = true; // set end
428        }
429    // force haveEnd for block with cf_end
430    for (const AsmCodeFlowEntry& entry: codeFlow)
431        if (entry.type == AsmCodeFlowType::END)
432        {
433            auto it = binaryFind(codeBlocks.begin(), codeBlocks.end(),
434                    CodeBlock{ 0, entry.offset }, codeBlockEndLess);
435            if (it != codeBlocks.end())
436                it->haveEnd = true;
437        }
438   
439    if (!codeBlocks.empty()) // always set haveEnd to last block
440        codeBlocks.back().haveEnd = true;
441   
442    // reduce nexts
443    for (CodeBlock& block: codeBlocks)
444    {
445        // first non-call nexts, for correct resolving SSA conflicts
446        std::sort(block.nexts.begin(), block.nexts.end(),
447                  [](const NextBlock& n1, const NextBlock& n2)
448                  { return int(n1.isCall)<int(n2.isCall) ||
449                      (n1.isCall == n2.isCall && n1.block < n2.block); });
450        auto it = std::unique(block.nexts.begin(), block.nexts.end(),
451                  [](const NextBlock& n1, const NextBlock& n2)
452                  { return n1.block == n2.block && n1.isCall == n2.isCall; });
453        block.nexts.resize(it - block.nexts.begin());
454    }
455}
456
457
458void AsmRegAllocator::applySSAReplaces()
459{
460    if (ssaReplacesMap.empty())
461        return; // do nothing
462   
463    /* prepare SSA id replaces */
464    struct MinSSAGraphNode
465    {
466        size_t minSSAId;
467        bool visited;
468        std::unordered_set<size_t> nexts;
469        MinSSAGraphNode() : minSSAId(SIZE_MAX), visited(false)
470        { }
471    };
472   
473    typedef std::map<size_t, MinSSAGraphNode, std::greater<size_t> > SSAGraphNodesMap;
474   
475    struct MinSSAGraphStackEntry
476    {
477        SSAGraphNodesMap::iterator nodeIt;
478        std::unordered_set<size_t>::const_iterator nextIt;
479        size_t minSSAId;
480       
481        MinSSAGraphStackEntry(
482                SSAGraphNodesMap::iterator _nodeIt,
483                std::unordered_set<size_t>::const_iterator _nextIt,
484                size_t _minSSAId = SIZE_MAX)
485                : nodeIt(_nodeIt), nextIt(_nextIt), minSSAId(_minSSAId)
486        { }
487    };
488   
489    for (auto& entry: ssaReplacesMap)
490    {
491        ARDOut << "SSAReplace: " << entry.first.regVar << "." << entry.first.index << "\n";
492        VectorSet<SSAReplace>& replaces = entry.second;
493        std::sort(replaces.begin(), replaces.end(), std::greater<SSAReplace>());
494        replaces.resize(std::unique(replaces.begin(), replaces.end()) - replaces.begin());
495        VectorSet<SSAReplace> newReplaces;
496       
497        SSAGraphNodesMap ssaGraphNodes;
498       
499        auto it = replaces.begin();
500        while (it != replaces.end())
501        {
502            auto itEnd = std::upper_bound(it, replaces.end(),
503                    std::make_pair(it->first, size_t(0)), std::greater<SSAReplace>());
504            {
505                auto itLast = itEnd;
506                --itLast;
507                MinSSAGraphNode& node = ssaGraphNodes[it->first];
508                node.minSSAId = std::min(node.minSSAId, itLast->second);
509                for (auto it2 = it; it2 != itEnd; ++it2)
510                {
511                    node.nexts.insert(it2->second);
512                    ssaGraphNodes.insert({ it2->second, MinSSAGraphNode() });
513                }
514            }
515            it = itEnd;
516        }
517        /*for (const auto& v: ssaGraphNodes)
518            ARDOut << "  SSANode: " << v.first << ":" << &v.second << " minSSAID: " <<
519                            v.second.minSSAId << std::endl;*/
520        // propagate min value
521        std::stack<MinSSAGraphStackEntry> minSSAStack;
522       
523        // initialize parents and new nexts
524        for (auto ssaGraphNodeIt = ssaGraphNodes.begin();
525                 ssaGraphNodeIt!=ssaGraphNodes.end(); )
526        {
527            ARDOut << "  Start in " << ssaGraphNodeIt->first << "." << "\n";
528            minSSAStack.push({ ssaGraphNodeIt, ssaGraphNodeIt->second.nexts.begin() });
529            // traverse with minimalize SSA id
530            while (!minSSAStack.empty())
531            {
532                MinSSAGraphStackEntry& entry = minSSAStack.top();
533                MinSSAGraphNode& node = entry.nodeIt->second;
534                bool toPop = false;
535                if (entry.nextIt == node.nexts.begin())
536                {
537                    toPop = node.visited;
538                    node.visited = true;
539                }
540                if (!toPop && entry.nextIt != node.nexts.end())
541                {
542                    auto nodeIt = ssaGraphNodes.find(*entry.nextIt);
543                    if (nodeIt != ssaGraphNodes.end())
544                        minSSAStack.push({ nodeIt, nodeIt->second.nexts.begin(),
545                                    size_t(0) });
546                    ++entry.nextIt;
547                }
548                else
549                {
550                    minSSAStack.pop();
551                    if (!minSSAStack.empty())
552                        node.nexts.insert(minSSAStack.top().nodeIt->first);
553                }
554            }
555           
556            // skip visited nodes
557            for(; ssaGraphNodeIt != ssaGraphNodes.end(); ++ssaGraphNodeIt)
558                if (!ssaGraphNodeIt->second.visited)
559                    break;
560        }
561       
562        /*for (const auto& v: ssaGraphNodes)
563        {
564            ARDOut << "  Nexts: " << v.first << ":" << &v.second << " nexts:";
565            for (size_t p: v.second.nexts)
566                ARDOut << " " << p;
567            ARDOut << "\n";
568        }*/
569       
570        for (auto& entry: ssaGraphNodes)
571            entry.second.visited = false;
572       
573        std::vector<MinSSAGraphNode*> toClear; // nodes to clear
574       
575        for (auto ssaGraphNodeIt = ssaGraphNodes.begin();
576                 ssaGraphNodeIt!=ssaGraphNodes.end(); )
577        {
578            ARDOut << "  Start in " << ssaGraphNodeIt->first << "." << "\n";
579            minSSAStack.push({ ssaGraphNodeIt, ssaGraphNodeIt->second.nexts.begin() });
580            // traverse with minimalize SSA id
581            while (!minSSAStack.empty())
582            {
583                MinSSAGraphStackEntry& entry = minSSAStack.top();
584                MinSSAGraphNode& node = entry.nodeIt->second;
585                bool toPop = false;
586                if (entry.nextIt == node.nexts.begin())
587                {
588                    toPop = node.visited;
589                    if (!node.visited)
590                        // this flag visited for this node will be clear after this pass
591                        toClear.push_back(&node);
592                    node.visited = true;
593                }
594               
595                // try to children only all parents are visited and if parent has children
596                if (!toPop && entry.nextIt != node.nexts.end())
597                {
598                    auto nodeIt = ssaGraphNodes.find(*entry.nextIt);
599                    if (nodeIt != ssaGraphNodes.end())
600                    {
601                        ARDOut << "  Node: " <<
602                                entry.nodeIt->first << ":" << &node << " minSSAId: " <<
603                                node.minSSAId << " to " <<
604                                nodeIt->first << ":" << &(nodeIt->second) <<
605                                " minSSAId: " << nodeIt->second.minSSAId << "\n";
606                        nodeIt->second.minSSAId =
607                                std::min(nodeIt->second.minSSAId, node.minSSAId);
608                        minSSAStack.push({ nodeIt, nodeIt->second.nexts.begin(),
609                                nodeIt->second.minSSAId });
610                    }
611                    ++entry.nextIt;
612                }
613                else
614                {
615                    node.minSSAId = std::min(node.minSSAId, entry.minSSAId);
616                    ARDOut << "    Node: " <<
617                                entry.nodeIt->first << ":" << &node << " minSSAId: " <<
618                                node.minSSAId << "\n";
619                    minSSAStack.pop();
620                    if (!minSSAStack.empty())
621                    {
622                        MinSSAGraphStackEntry& pentry = minSSAStack.top();
623                        pentry.minSSAId = std::min(pentry.minSSAId, node.minSSAId);
624                    }
625                }
626            }
627           
628            const size_t minSSAId = ssaGraphNodeIt->second.minSSAId;
629           
630            // skip visited nodes
631            for(; ssaGraphNodeIt != ssaGraphNodes.end(); ++ssaGraphNodeIt)
632                if (!ssaGraphNodeIt->second.visited)
633                    break;
634            // zeroing visited
635            for (MinSSAGraphNode* node: toClear)
636            {
637                node->minSSAId = minSSAId; // fill up by minSSAId
638                node->visited = false;
639            }
640            toClear.clear();
641        }
642       
643        for (const auto& entry: ssaGraphNodes)
644            newReplaces.push_back({ entry.first, entry.second.minSSAId });
645       
646        std::sort(newReplaces.begin(), newReplaces.end());
647        entry.second = newReplaces;
648    }
649   
650    /* apply SSA id replaces */
651    for (CodeBlock& cblock: codeBlocks)
652        for (auto& ssaEntry: cblock.ssaInfoMap)
653        {
654            auto it = ssaReplacesMap.find(ssaEntry.first);
655            if (it == ssaReplacesMap.end())
656                continue;
657            SSAInfo& sinfo = ssaEntry.second;
658            VectorSet<SSAReplace>& replaces = it->second;
659            if (sinfo.readBeforeWrite)
660            {
661                auto rit = binaryMapFind(replaces.begin(), replaces.end(),
662                                 ssaEntry.second.ssaIdBefore);
663                if (rit != replaces.end())
664                    sinfo.ssaIdBefore = rit->second; // replace
665            }
666            if (sinfo.ssaIdFirst != SIZE_MAX)
667            {
668                auto rit = binaryMapFind(replaces.begin(), replaces.end(),
669                                 ssaEntry.second.ssaIdFirst);
670                if (rit != replaces.end())
671                    sinfo.ssaIdFirst = rit->second; // replace
672            }
673            if (sinfo.ssaIdLast != SIZE_MAX)
674            {
675                auto rit = binaryMapFind(replaces.begin(), replaces.end(),
676                                 ssaEntry.second.ssaIdLast);
677                if (rit != replaces.end())
678                    sinfo.ssaIdLast = rit->second; // replace
679            }
680        }
681   
682    // clear ssa replaces
683    ssaReplacesMap.clear();
684}
685
686static cxuint getRegType(size_t regTypesNum, const cxuint* regRanges,
687            const AsmSingleVReg& svreg)
688{
689    cxuint regType; // regtype
690    if (svreg.regVar!=nullptr)
691        regType = svreg.regVar->type;
692    else
693        for (regType = 0; regType < regTypesNum; regType++)
694            if (svreg.index >= regRanges[regType<<1] &&
695                svreg.index < regRanges[(regType<<1)+1])
696                break;
697    return regType;
698}
699
700static Liveness& getLiveness(const AsmSingleVReg& svreg, size_t ssaIdIdx,
701        const AsmRegAllocator::SSAInfo& ssaInfo, std::vector<Liveness>* livenesses,
702        const VarIndexMap* vregIndexMaps, size_t regTypesNum, const cxuint* regRanges)
703{
704    size_t ssaId;
705    if (svreg.regVar==nullptr)
706        ssaId = 0;
707    else if (ssaIdIdx==0)
708        ssaId = ssaInfo.ssaIdBefore;
709    else if (ssaIdIdx==1)
710        ssaId = ssaInfo.ssaIdFirst;
711    else if (ssaIdIdx<ssaInfo.ssaIdChange)
712        ssaId = ssaInfo.ssaId + ssaIdIdx-1;
713    else // last
714        ssaId = ssaInfo.ssaIdLast;
715   
716    cxuint regType = getRegType(regTypesNum, regRanges, svreg); // regtype
717    const VarIndexMap& vregIndexMap = vregIndexMaps[regType];
718    const std::vector<size_t>& ssaIdIndices = vregIndexMap.find(svreg)->second;
719    ARDOut << "lvn[" << regType << "][" << ssaIdIndices[ssaId] << "]. ssaIdIdx: " <<
720            ssaIdIdx << ". ssaId: " << ssaId << ". svreg: " << svreg.regVar << ":" <<
721            svreg.index << "\n";
722    return livenesses[regType][ssaIdIndices[ssaId]];
723}
724
725static Liveness& getLiveness2(const AsmSingleVReg& svreg,
726        size_t ssaId, std::vector<Liveness>* livenesses,
727        const VarIndexMap* vregIndexMaps, size_t regTypesNum, const cxuint* regRanges)
728{
729    cxuint regType = getRegType(regTypesNum, regRanges, svreg); // regtype
730    const VarIndexMap& vregIndexMap = vregIndexMaps[regType];
731    const std::vector<size_t>& ssaIdIndices = vregIndexMap.find(svreg)->second;
732    ARDOut << "lvn[" << regType << "][" << ssaIdIndices[ssaId] << "]. ssaId: " <<
733            ssaId << ". svreg: " << svreg.regVar << ":" << svreg.index << "\n";
734    return livenesses[regType][ssaIdIndices[ssaId]];
735}
736
737/* TODO: add handling calls
738 * handle many start points in this code (for example many kernel's in same code)
739 * replace sets by vector, and sort and remove same values on demand
740 */
741
742/* join livenesses between consecutive code blocks */
743static void putCrossBlockLivenesses(const std::deque<FlowStackEntry3>& flowStack,
744        const std::vector<CodeBlock>& codeBlocks, const LastVRegMap& lastVRegMap,
745        std::vector<Liveness>* livenesses, const VarIndexMap* vregIndexMaps,
746        size_t regTypesNum, const cxuint* regRanges)
747{
748    ARDOut << "putCrossBlockLv block: " << flowStack.back().blockIndex << "\n";
749    const CodeBlock& cblock = codeBlocks[flowStack.back().blockIndex];
750    for (const auto& entry: cblock.ssaInfoMap)
751        if (entry.second.readBeforeWrite)
752        {
753            // find last
754            auto lvrit = lastVRegMap.find(entry.first);
755            FlowStackCIter flit = flowStack.begin();
756            if (lvrit != lastVRegMap.end())
757                flit += lvrit->second.back().blockIndex;
758           
759            cxuint regType = getRegType(regTypesNum, regRanges, entry.first);
760            const VarIndexMap& vregIndexMap = vregIndexMaps[regType];
761            const std::vector<size_t>& ssaIdIndices =
762                        vregIndexMap.find(entry.first)->second;
763            Liveness& lv = livenesses[regType][ssaIdIndices[entry.second.ssaIdBefore]];
764            FlowStackCIter flitEnd = flowStack.end();
765            --flitEnd; // before last element
766           
767            ARDOut << "  putCross for " << entry.first.regVar << ":" <<
768                    entry.first.index << "\n";
769            // insert live time to last seen position
770            const CodeBlock& lastBlk = codeBlocks[flit->blockIndex];
771           
772            auto sinfoIt = lastBlk.ssaInfoMap.find(entry.first);
773            size_t lastPos = lastBlk.start;
774            if (sinfoIt != lastBlk.ssaInfoMap.end())
775            {
776                // if begin at some point at last block
777                lastPos = sinfoIt->second.lastPos;
778                lv.insert(lastPos + 1, lastBlk.end);
779                ++flit; // skip last block in stack
780            }
781           
782            for (; flit != flitEnd; ++flit)
783            {
784                const CodeBlock& cblock = codeBlocks[flit->blockIndex];
785                lv.insert(cblock.start, cblock.end);
786            }
787        }
788}
789
790static void fillUpInsideRoutine(std::vector<bool>& visited,
791            const std::vector<CodeBlock>& codeBlocks, size_t startBlock,
792            const AsmSingleVReg& svreg, Liveness& lv)
793{
794    std::deque<FlowStackEntry3> flowStack;
795    flowStack.push_back({ startBlock, 0 });
796   
797    if (lv.contain(codeBlocks[startBlock].end-1))
798        // already filled, then do nothing
799        return;
800   
801    while (!flowStack.empty())
802    {
803        FlowStackEntry3& entry = flowStack.back();
804        const CodeBlock& cblock = codeBlocks[entry.blockIndex];
805       
806        if (entry.nextIndex == 0)
807        {
808            if (!visited[entry.blockIndex])
809            {
810                visited[entry.blockIndex] = true;
811                size_t cbStart = cblock.start;
812                if (flowStack.size() == 1)
813                {
814                    // if first block, then get last occurrence in this path
815                    auto sinfoIt = cblock.ssaInfoMap.find(svreg);
816                    if (sinfoIt != cblock.ssaInfoMap.end())
817                        cbStart = sinfoIt->second.lastPos+1;
818                }
819                // just insert
820                lv.insert(cbStart, cblock.end);
821            }
822            else
823            {
824                flowStack.pop_back();
825                continue;
826            }
827        }
828       
829        if (entry.nextIndex < cblock.nexts.size())
830        {
831            flowStack.push_back({ cblock.nexts[entry.nextIndex].block, 0 });
832            entry.nextIndex++;
833        }
834        else if (((entry.nextIndex==0 && cblock.nexts.empty()) ||
835                // if have any call then go to next block
836                (cblock.haveCalls && entry.nextIndex==cblock.nexts.size())) &&
837                 !cblock.haveReturn && !cblock.haveEnd)
838        {
839            flowStack.push_back({ entry.blockIndex+1, 0 });
840            entry.nextIndex++;
841        }
842        else // back
843            flowStack.pop_back();
844    }
845}
846           
847
848static void joinVRegRecur(const std::deque<FlowStackEntry3>& flowStack,
849            const std::vector<CodeBlock>& codeBlocks, const RoutineLvMap& routineMap,
850            size_t flowStackStart, const AsmSingleVReg& svreg,
851            const LastAccessBlockPos& lastAccessPos,
852            const VarIndexMap* vregIndexMaps, std::vector<Liveness>* livenesses,
853            size_t regTypesNum, const cxuint* regRanges)
854{
855    struct JoinEntry
856    {
857        size_t blockIndex; // block index where is call
858        size_t nextIndex; // next index of routine call
859        size_t lastAccessIndex; // last access pos index
860        bool inSubroutines;
861    };
862    Liveness* lv = nullptr;
863    std::vector<bool> visited(codeBlocks.size(), false);
864   
865    std::stack<JoinEntry> rjStack; // routine join stack
866    if (lastAccessPos.inSubroutines)
867        rjStack.push({ lastAccessPos.blockIndex, 0, 0, true });
868   
869    while (!rjStack.empty())
870    {
871        JoinEntry& entry = rjStack.top();
872        const CodeBlock& cblock = codeBlocks[entry.blockIndex];
873       
874        if (entry.inSubroutines && entry.nextIndex < cblock.nexts.size())
875        {
876            bool doNextIndex = false; // true if to next call
877            if (cblock.nexts[entry.nextIndex].isCall)
878            {
879                const RoutineDataLv& rdata =
880                        routineMap.find(cblock.nexts[entry.nextIndex].block)->second;
881                auto lastAccessIt = rdata.lastAccessMap.find(svreg);
882                if (lastAccessIt != rdata.lastAccessMap.end())
883                {
884                    if (entry.lastAccessIndex < lastAccessIt->second.size())
885                    {
886                        const auto& lastAccess =
887                                lastAccessIt->second[entry.lastAccessIndex];
888                        rjStack.push({ lastAccess.blockIndex, 0,
889                                    0, lastAccess.inSubroutines });
890                        entry.lastAccessIndex++;
891                    }
892                    else
893                        doNextIndex = true;
894                }
895                else
896                    doNextIndex = true;
897            }
898            else
899                doNextIndex = true;
900           
901            if (doNextIndex)
902            {
903                // to next call
904                entry.nextIndex++;
905                entry.lastAccessIndex = 0;
906            }
907        }
908        else
909        {
910            size_t blockStart = entry.blockIndex;
911            if (lv == nullptr)
912            {
913                const SSAInfo& ssaInfo = codeBlocks[blockStart]
914                            .ssaInfoMap.find(svreg)->second;
915                lv = &getLiveness2(svreg, (ssaInfo.ssaIdChange==0) ?
916                        ssaInfo.ssaIdBefore : ssaInfo.ssaIdLast,
917                        livenesses, vregIndexMaps, regTypesNum, regRanges);
918            }
919            if (!entry.inSubroutines)
920                fillUpInsideRoutine(visited, codeBlocks, blockStart, svreg, *lv);
921            else
922            {
923                // fill up next block in path (do not fill start block)
924                const CodeBlock& cbstart = codeBlocks[blockStart];
925                for (size_t k = 0; k < cbstart.nexts.size(); k++)
926                    if (!cbstart.nexts[k].isCall)
927                        fillUpInsideRoutine(visited, codeBlocks,
928                                cbstart.nexts[k].block, svreg, *lv);
929            }
930            rjStack.pop();
931        }
932    }
933   
934    auto flit = flowStack.begin() + flowStackStart;
935    if (lv == nullptr)
936    {
937        size_t blockStart = flit->blockIndex;
938        auto ssaInfoIt = codeBlocks[blockStart].ssaInfoMap.find(svreg);
939        size_t ssaId = 0;
940        if (ssaInfoIt != codeBlocks[blockStart].ssaInfoMap.end())
941            ssaId = (ssaInfoIt->second.ssaIdChange==0) ? ssaInfoIt->second.ssaIdLast :
942                    ssaInfoIt->second.ssaIdBefore;
943        lv = &getLiveness2(svreg, ssaId, livenesses, vregIndexMaps,
944                        regTypesNum, regRanges);
945    }
946   
947    // fill up to this
948    for (; flit != flowStack.end(); ++flit)
949    {
950        const CodeBlock& cblock = codeBlocks[flit->blockIndex];
951        lv->insert(cblock.start, cblock.end);
952    }
953}
954           
955
956static void joinSVregWithVisited(const SVRegMap* stackVarMap, const AsmSingleVReg& vreg,
957            size_t ssaIdNextBefore, const std::deque<FlowStackEntry3>& prevFlowStack,
958            const std::vector<CodeBlock>& codeBlocks, const VarIndexMap* vregIndexMaps,
959            std::vector<Liveness>* livenesses, size_t regTypesNum, const cxuint* regRanges)
960{
961    auto pfEnd = prevFlowStack.end();
962    --pfEnd;
963   
964    Liveness& lv = getLiveness2(vreg, ssaIdNextBefore,
965            livenesses, vregIndexMaps, regTypesNum, regRanges);
966   
967    const CodeBlock& cbLast = codeBlocks[(pfEnd-1)->blockIndex];
968    if (lv.contain(cbLast.end-1))
969        // if already filled up
970        return;
971   
972    // join liveness for this variable ssaId>.
973    // only if in previous block previous SSAID is
974    // read before all writes
975    auto it = stackVarMap->find(vreg);
976   
977    const size_t pfStart = (it != stackVarMap->end() ? it->second : 0);
978    //if (it == stackVarMap.end())
979        //continue;
980    // fill up previous part
981    auto flit = prevFlowStack.begin() + pfStart;
982    {
983        // fill up liveness for first code block
984        const CodeBlock& cblock = codeBlocks[flit->blockIndex];
985        auto ssaInfoIt = cblock.ssaInfoMap.find(vreg);
986        size_t prevLastPos = (ssaInfoIt != cblock.ssaInfoMap.end()) ?
987                ssaInfoIt->second.lastPos+1 : cblock.start;
988        lv.insert(prevLastPos, cblock.end);
989    }
990   
991    for (++flit; flit != pfEnd; ++flit)
992    {
993        const CodeBlock& cblock = codeBlocks[flit->blockIndex];
994        lv.insert(cblock.start, cblock.end);
995    }
996}
997
998// add new join second cache entry with readBeforeWrite for all encountered regvars
999static void addJoinSecCacheEntry(//const RoutineMap& routineMap,
1000                const std::vector<CodeBlock>& codeBlocks,
1001                SimpleCache<size_t, SVRegMap>& joinSecondPointsCache,
1002                size_t nextBlock)
1003{
1004    ARDOut << "addJoinSecCacheEntry: " << nextBlock << "\n";
1005    //std::stack<CallStackEntry> callStack = prevCallStack;
1006    // traverse by graph from next block
1007    std::deque<FlowStackEntry3> flowStack;
1008    flowStack.push_back({ nextBlock, 0 });
1009    CBlockBitPool visited(codeBlocks.size(), false);
1010   
1011    SVRegBlockMap alreadyReadMap;
1012    SVRegMap cacheSecPoints;
1013   
1014    while (!flowStack.empty())
1015    {
1016        FlowStackEntry3& entry = flowStack.back();
1017        const CodeBlock& cblock = codeBlocks[entry.blockIndex];
1018       
1019        if (entry.nextIndex == 0)
1020        {
1021            // process current block
1022            if (!visited[entry.blockIndex])
1023            {
1024                visited[entry.blockIndex] = true;
1025                ARDOut << "  resolv (cache): " << entry.blockIndex << "\n";
1026               
1027                const SVRegMap* resSecondPoints =
1028                            joinSecondPointsCache.use(entry.blockIndex);
1029                if (resSecondPoints == nullptr)
1030                {
1031                    // if joinSecondPointCache not found
1032                    for (auto& sentry: cblock.ssaInfoMap)
1033                    {
1034                        const SSAInfo& sinfo = sentry.second;
1035                        auto res = alreadyReadMap.insert(
1036                                    { sentry.first, entry.blockIndex });
1037                       
1038                        if (res.second && sinfo.readBeforeWrite)
1039                            cacheSecPoints[sentry.first] = sinfo.ssaIdBefore;
1040                    }
1041                }
1042                else // to use cache
1043                {
1044                    // add to current cache sec points
1045                    for (const auto& rsentry: *resSecondPoints)
1046                    {
1047                        const bool alreadyRead =
1048                            alreadyReadMap.find(rsentry.first) != alreadyReadMap.end();
1049                        if (!alreadyRead)
1050                            cacheSecPoints[rsentry.first] = rsentry.second;
1051                    }
1052                    flowStack.pop_back();
1053                    continue;
1054                }
1055            }
1056            else
1057            {
1058                // back, already visited
1059                ARDOut << "join already (cache): " << entry.blockIndex << "\n";
1060                flowStack.pop_back();
1061                continue;
1062            }
1063        }
1064       
1065        if (entry.nextIndex < cblock.nexts.size())
1066        {
1067            flowStack.push_back({ cblock.nexts[entry.nextIndex].block, 0 });
1068            entry.nextIndex++;
1069        }
1070        else if (((entry.nextIndex==0 && cblock.nexts.empty()) ||
1071                // if have any call then go to next block
1072                (cblock.haveCalls && entry.nextIndex==cblock.nexts.size())) &&
1073                 !cblock.haveReturn && !cblock.haveEnd)
1074        {
1075            // add toResolveMap ssaIds inside called routines
1076            /*for (const auto& next: cblock.nexts)
1077                if (next.isCall)
1078                {
1079                    const RoutineData& rdata = routineMap.find(next.block)->second;
1080                    for (const auto& v: rdata.rbwSSAIdMap)
1081                        alreadyReadMap.insert({v.first, entry.blockIndex });
1082                    for (const auto& v: rdata.lastSSAIdMap)
1083                        alreadyReadMap.insert({v.first, entry.blockIndex });
1084                }*/
1085           
1086            flowStack.push_back({ entry.blockIndex+1, 0 });
1087            entry.nextIndex++;
1088        }
1089        else // back
1090        {
1091            // remove old to resolve in leaved way to allow collecting next ssaId
1092            // before write (can be different due to earlier visit)
1093            /*for (const auto& next: cblock.nexts)
1094                if (next.isCall)
1095                {
1096                    const RoutineData& rdata = routineMap.find(next.block)->second;
1097                    for (const auto& v: rdata.rbwSSAIdMap)
1098                    {
1099                        auto it = alreadyReadMap.find(v.first);
1100                        if (it != alreadyReadMap.end() && it->second == entry.blockIndex)
1101                            alreadyReadMap.erase(it);
1102                    }
1103                    for (const auto& v: rdata.lastSSAIdMap)
1104                    {
1105                        auto it = alreadyReadMap.find(v.first);
1106                        if (it != alreadyReadMap.end() && it->second == entry.blockIndex)
1107                            alreadyReadMap.erase(it);
1108                    }
1109                }*/
1110           
1111            for (const auto& sentry: cblock.ssaInfoMap)
1112            {
1113                auto it = alreadyReadMap.find(sentry.first);
1114                if (it != alreadyReadMap.end() && it->second == entry.blockIndex)
1115                    // remove old to resolve in leaved way to allow collecting next ssaId
1116                    // before write (can be different due to earlier visit)
1117                    alreadyReadMap.erase(it);
1118            }
1119            ARDOut << "  popjoin (cache)\n";
1120            flowStack.pop_back();
1121        }
1122    }
1123   
1124    joinSecondPointsCache.put(nextBlock, cacheSecPoints);
1125}
1126
1127static void joinRegVarLivenesses(const std::deque<FlowStackEntry3>& prevFlowStack,
1128        const std::vector<CodeBlock>& codeBlocks,
1129        const PrevWaysIndexMap& prevWaysIndexMap,
1130        const std::vector<bool>& waysToCache, ResSecondPointsToCache& cblocksToCache,
1131        SimpleCache<size_t, SVRegMap>& joinFirstPointsCache,
1132        SimpleCache<size_t, SVRegMap>& joinSecondPointsCache,
1133        const VarIndexMap* vregIndexMaps,
1134        std::vector<Liveness>* livenesses, size_t regTypesNum, const cxuint* regRanges)
1135{
1136    size_t nextBlock = prevFlowStack.back().blockIndex;
1137    auto pfEnd = prevFlowStack.end();
1138    --pfEnd;
1139    ARDOut << "startJoinLv: " << (pfEnd-1)->blockIndex << "," << nextBlock << "\n";
1140    // key - varreg, value - last position in previous flowStack
1141    SVRegMap stackVarMap;
1142   
1143    size_t pfStartIndex = 0;
1144    {
1145        auto pfPrev = pfEnd;
1146        --pfPrev;
1147        auto it = prevWaysIndexMap.find(pfPrev->blockIndex);
1148        if (it != prevWaysIndexMap.end())
1149        {
1150            const SVRegMap* cached = joinFirstPointsCache.use(it->second.first);
1151            if (cached!=nullptr)
1152            {
1153                ARDOut << "use pfcached: " << it->second.first << ", " <<
1154                        it->second.second << "\n";
1155                stackVarMap = *cached;
1156                pfStartIndex = it->second.second+1;
1157               
1158                // apply missing calls at end of the cached
1159                //const CodeBlock& cblock = codeBlocks[it->second.first];
1160               
1161                //const FlowStackEntry3& entry = *(prevFlowStack.begin()+pfStartIndex-1);
1162                //if (entry.nextIndex > cblock.nexts.size())
1163                   // applyCallToStackVarMap(cblock, routineMap, stackVarMap, -1, -1);
1164            }
1165        }
1166    }
1167   
1168    for (auto pfit = prevFlowStack.begin()+pfStartIndex; pfit != pfEnd; ++pfit)
1169    {
1170        const FlowStackEntry3& entry = *pfit;
1171        const CodeBlock& cblock = codeBlocks[entry.blockIndex];
1172        for (const auto& sentry: cblock.ssaInfoMap)
1173            stackVarMap[sentry.first] = pfit - prevFlowStack.begin();
1174       
1175        // put to first point cache
1176        if (waysToCache[pfit->blockIndex] &&
1177            !joinFirstPointsCache.hasKey(pfit->blockIndex))
1178        {
1179            ARDOut << "put pfcache " << pfit->blockIndex << "\n";
1180            joinFirstPointsCache.put(pfit->blockIndex, stackVarMap);
1181        }
1182    }
1183   
1184    SVRegMap cacheSecPoints;
1185    const bool toCache = (!joinSecondPointsCache.hasKey(nextBlock)) &&
1186                cblocksToCache.count(nextBlock)>=2;
1187   
1188    // traverse by graph from next block
1189    std::deque<FlowStackEntry3> flowStack;
1190    flowStack.push_back({ nextBlock, 0 });
1191    std::vector<bool> visited(codeBlocks.size(), false);
1192   
1193    // already read in current path
1194    // key - vreg, value - source block where vreg of conflict found
1195    SVRegMap alreadyReadMap;
1196   
1197    while (!flowStack.empty())
1198    {
1199        FlowStackEntry3& entry = flowStack.back();
1200        const CodeBlock& cblock = codeBlocks[entry.blockIndex];
1201       
1202        if (entry.nextIndex == 0)
1203        {
1204            // process current block
1205            if (!visited[entry.blockIndex])
1206            {
1207                visited[entry.blockIndex] = true;
1208                ARDOut << "  lvjoin: " << entry.blockIndex << "\n";
1209               
1210                const SVRegMap* joinSecondPoints =
1211                        joinSecondPointsCache.use(entry.blockIndex);
1212               
1213                if (joinSecondPoints == nullptr)
1214                    for (const auto& sentry: cblock.ssaInfoMap)
1215                    {
1216                        const SSAInfo& sinfo = sentry.second;
1217                        auto res = alreadyReadMap.insert(
1218                                    { sentry.first, entry.blockIndex });
1219                       
1220                        if (toCache)
1221                            cacheSecPoints[sentry.first] = sinfo.ssaIdBefore;
1222                       
1223                        if (res.second && sinfo.readBeforeWrite)
1224                            joinSVregWithVisited(&stackVarMap, sentry.first,
1225                                sentry.second.ssaIdBefore, prevFlowStack, codeBlocks,
1226                                vregIndexMaps, livenesses, regTypesNum, regRanges);
1227                    }
1228                else
1229                {
1230                    ARDOut << "use join secPointCache: " << entry.blockIndex << "\n";
1231                    // add to current cache sec points
1232                    for (const auto& rsentry: *joinSecondPoints)
1233                    {
1234                        const bool alreadyRead =
1235                            alreadyReadMap.find(rsentry.first) != alreadyReadMap.end();
1236                       
1237                        if (!alreadyRead)
1238                        {
1239                            if (toCache)
1240                                cacheSecPoints[rsentry.first] = rsentry.second;
1241                           
1242                            joinSVregWithVisited(&stackVarMap, rsentry.first,
1243                                    rsentry.second, prevFlowStack, codeBlocks,
1244                                    vregIndexMaps, livenesses, regTypesNum, regRanges);
1245                        }
1246                    }
1247                    flowStack.pop_back();
1248                    continue;
1249                }
1250            }
1251            else
1252            {
1253                cblocksToCache.increase(entry.blockIndex);
1254                ARDOut << "jcblockToCache: " << entry.blockIndex << "=" <<
1255                            cblocksToCache.count(entry.blockIndex) << "\n";
1256                // back, already visited
1257                ARDOut << "join already: " << entry.blockIndex << "\n";
1258                flowStack.pop_back();
1259                continue;
1260            }
1261        }
1262       
1263        if (entry.nextIndex < cblock.nexts.size())
1264        {
1265            flowStack.push_back({ cblock.nexts[entry.nextIndex].block, 0 });
1266            entry.nextIndex++;
1267        }
1268        else if (((entry.nextIndex==0 && cblock.nexts.empty()) ||
1269                // if have any call then go to next block
1270                (cblock.haveCalls && entry.nextIndex==cblock.nexts.size())) &&
1271                 !cblock.haveReturn && !cblock.haveEnd)
1272        {
1273            // add toResolveMap ssaIds inside called routines
1274            /*for (const auto& next: cblock.nexts)
1275                if (next.isCall)
1276                {
1277                    const RoutineData& rdata = routineMap.find(next.block)->second;
1278                    for (const auto& v: rdata.rbwSSAIdMap)
1279                        alreadyReadMap.insert({v.first, entry.blockIndex });
1280                    for (const auto& v: rdata.lastSSAIdMap)
1281                        alreadyReadMap.insert({v.first, entry.blockIndex });
1282                }*/
1283           
1284            flowStack.push_back({ entry.blockIndex+1, 0 });
1285            entry.nextIndex++;
1286        }
1287        else // back
1288        {
1289            // remove old to resolve in leaved way to allow collecting next ssaId
1290            // before write (can be different due to earlier visit)
1291            /*for (const auto& next: cblock.nexts)
1292                if (next.isCall)
1293                {
1294                    const RoutineData& rdata = routineMap.find(next.block)->second;
1295                    for (const auto& v: rdata.rbwSSAIdMap)
1296                    {
1297                        auto it = alreadyReadMap.find(v.first);
1298                        if (it != alreadyReadMap.end() && it->second == entry.blockIndex)
1299                            alreadyReadMap.erase(it);
1300                    }
1301                    for (const auto& v: rdata.lastSSAIdMap)
1302                    {
1303                        auto it = alreadyReadMap.find(v.first);
1304                        if (it != alreadyReadMap.end() && it->second == entry.blockIndex)
1305                            alreadyReadMap.erase(it);
1306                    }
1307                }*/
1308           
1309            for (const auto& sentry: cblock.ssaInfoMap)
1310            {
1311                auto it = alreadyReadMap.find(sentry.first);
1312                if (it != alreadyReadMap.end() && it->second == entry.blockIndex)
1313                    // remove old to resolve in leaved way to allow collecting next ssaId
1314                    // before write (can be different due to earlier visit)
1315                    alreadyReadMap.erase(it);
1316            }
1317            ARDOut << "  popjoin\n";
1318           
1319            if (cblocksToCache.count(entry.blockIndex)==2 &&
1320                !joinSecondPointsCache.hasKey(entry.blockIndex))
1321                // add to cache
1322                addJoinSecCacheEntry(codeBlocks, joinSecondPointsCache,
1323                            entry.blockIndex);
1324           
1325            flowStack.pop_back();
1326        }
1327    }
1328   
1329    if (toCache)
1330        joinSecondPointsCache.put(nextBlock, cacheSecPoints);
1331}
1332
1333static void addUsageDeps(const cxbyte* ldeps, cxuint rvusNum,
1334            const AsmRegVarUsage* rvus, LinearDepMap* ldepsOut,
1335            const VarIndexMap* vregIndexMaps, const SVRegMap& ssaIdIdxMap,
1336            size_t regTypesNum, const cxuint* regRanges)
1337{
1338    // add linear deps
1339    cxuint count = ldeps[0];
1340    cxuint pos = 1;
1341    cxbyte rvuAdded = 0;
1342    for (cxuint i = 0; i < count; i++)
1343    {
1344        cxuint ccount = ldeps[pos++];
1345        std::vector<size_t> vidxes;
1346        cxuint regType = UINT_MAX;
1347        cxbyte align = rvus[ldeps[pos]].align;
1348        for (cxuint j = 0; j < ccount; j++)
1349        {
1350            rvuAdded |= 1U<<ldeps[pos];
1351            const AsmRegVarUsage& rvu = rvus[ldeps[pos++]];
1352            for (uint16_t k = rvu.rstart; k < rvu.rend; k++)
1353            {
1354                AsmSingleVReg svreg = {rvu.regVar, k};
1355                auto sit = ssaIdIdxMap.find(svreg);
1356                if (regType==UINT_MAX)
1357                    regType = getRegType(regTypesNum, regRanges, svreg);
1358                const VarIndexMap& vregIndexMap = vregIndexMaps[regType];
1359                const std::vector<size_t>& ssaIdIndices =
1360                            vregIndexMap.find(svreg)->second;
1361                // push variable index
1362                vidxes.push_back(ssaIdIndices[sit->second]);
1363            }
1364        }
1365        ldepsOut[regType][vidxes[0]].align = align;
1366        for (size_t k = 1; k < vidxes.size(); k++)
1367        {
1368            ldepsOut[regType][vidxes[k-1]].nextVidxes.insertValue(vidxes[k]);
1369            ldepsOut[regType][vidxes[k]].prevVidxes.insertValue(vidxes[k-1]);
1370        }
1371    }
1372    // add single arg linear dependencies
1373    for (cxuint i = 0; i < rvusNum; i++)
1374        if ((rvuAdded & (1U<<i)) == 0 && rvus[i].rstart+1<rvus[i].rend)
1375        {
1376            const AsmRegVarUsage& rvu = rvus[i];
1377            std::vector<size_t> vidxes;
1378            cxuint regType = UINT_MAX;
1379            cxbyte align = rvus[i].align;
1380            for (uint16_t k = rvu.rstart; k < rvu.rend; k++)
1381            {
1382                AsmSingleVReg svreg = {rvu.regVar, k};
1383                auto sit = ssaIdIdxMap.find(svreg);
1384                assert(sit != ssaIdIdxMap.end());
1385                if (regType==UINT_MAX)
1386                    regType = getRegType(regTypesNum, regRanges, svreg);
1387                const VarIndexMap& vregIndexMap = vregIndexMaps[regType];
1388                const std::vector<size_t>& ssaIdIndices =
1389                            vregIndexMap.find(svreg)->second;
1390                // push variable index
1391                vidxes.push_back(ssaIdIndices[sit->second]);
1392            }
1393            ldepsOut[regType][vidxes[0]].align = align;
1394            for (size_t j = 1; j < vidxes.size(); j++)
1395            {
1396                ldepsOut[regType][vidxes[j-1]].nextVidxes.insertValue(vidxes[j]);
1397                ldepsOut[regType][vidxes[j]].prevVidxes.insertValue(vidxes[j-1]);
1398            }
1399        }
1400}
1401
1402
1403static void createRoutineDataLv(const std::vector<CodeBlock>& codeBlocks,
1404        const RoutineLvMap& routineMap, RoutineDataLv& rdata,
1405        size_t routineBlock, const VarIndexMap* vregIndexMaps,
1406        size_t regTypesNum, const cxuint* regRanges)
1407{
1408    std::deque<FlowStackEntry4> flowStack;
1409    std::vector<bool> visited(codeBlocks.size(), false);
1410   
1411    // already read in current path
1412    // key - vreg, value - source block where vreg of conflict found
1413    SVRegMap alreadyReadMap;
1414   
1415    flowStack.push_back({ routineBlock, 0 });
1416    SVRegMap curSVRegMap; // key - svreg, value - block index
1417   
1418    while (!flowStack.empty())
1419    {
1420        FlowStackEntry4& entry = flowStack.back();
1421        const CodeBlock& cblock = codeBlocks[entry.blockIndex];
1422       
1423        if (entry.nextIndex == 0)
1424        {
1425            // process current block
1426            if (!visited[entry.blockIndex])
1427            {
1428                visited[entry.blockIndex] = true;
1429               
1430                for (const auto& sentry: cblock.ssaInfoMap)
1431                {
1432                    if (sentry.second.readBeforeWrite)
1433                        if (alreadyReadMap.insert(
1434                                    { sentry.first, entry.blockIndex }).second)
1435                            rdata.rbwSSAIdMap.insert({ sentry.first,
1436                                        sentry.second.ssaIdBefore });
1437                   
1438                    auto res = curSVRegMap.insert({ sentry.first, entry.blockIndex });
1439                    if (!res.second)
1440                    {   // not added because is present in map
1441                        entry.prevCurSVRegMap.insert(*res.first);
1442                        res.first->second = entry.blockIndex;
1443                    }
1444                    else
1445                        entry.prevCurSVRegMap.insert({ sentry.first, SIZE_MAX });
1446                   
1447                    // all SSAs
1448                    const SSAInfo& sinfo = sentry.second;
1449                    const AsmSingleVReg& svreg = sentry.first;
1450                    cxuint regType = getRegType(regTypesNum, regRanges, svreg);
1451                    const VarIndexMap& vregIndexMap = vregIndexMaps[regType];
1452                    const std::vector<size_t>& ssaIdIndices =
1453                                vregIndexMap.find(svreg)->second;
1454                   
1455                    // add SSA indices to allSSAs
1456                    if (sinfo.readBeforeWrite)
1457                        rdata.allSSAs[regType].insert(ssaIdIndices[sinfo.ssaIdBefore]);
1458                    if (sinfo.ssaIdChange != 0)
1459                    {
1460                        rdata.allSSAs[regType].insert(ssaIdIndices[sinfo.ssaIdFirst]);
1461                        for (size_t i = 1; i < sinfo.ssaIdChange; i++)
1462                            rdata.allSSAs[regType].insert(ssaIdIndices[sinfo.ssaId+i]);
1463                        rdata.allSSAs[regType].insert(ssaIdIndices[sinfo.ssaIdLast]);
1464                    }
1465                }
1466            }
1467            else
1468            {
1469                flowStack.pop_back();
1470                continue;
1471            }
1472        }
1473       
1474        if (entry.nextIndex < cblock.nexts.size())
1475        {
1476            flowStack.push_back({ cblock.nexts[entry.nextIndex].block, 0 });
1477            entry.nextIndex++;
1478        }
1479        else if (((entry.nextIndex==0 && cblock.nexts.empty()) ||
1480                // if have any call then go to next block
1481                (cblock.haveCalls && entry.nextIndex==cblock.nexts.size())) &&
1482                 !cblock.haveReturn && !cblock.haveEnd)
1483        {
1484            flowStack.push_back({ entry.blockIndex+1, 0 });
1485            entry.nextIndex++;
1486        }
1487        else
1488        {
1489            if (cblock.haveReturn)
1490            {
1491                // handle return
1492                for (const auto& entry: curSVRegMap)
1493                {
1494                    auto res = rdata.lastAccessMap.insert({ entry.first,
1495                                    { LastAccessBlockPos{  entry.second, false } } });
1496                    if (!res.second)
1497                        res.first->second.insertValue(
1498                                    LastAccessBlockPos{ entry.second, false });
1499                }
1500            }
1501            // revert curSVRegMap
1502            for (const auto& sentry: entry.prevCurSVRegMap)
1503                if (sentry.second != SIZE_MAX)
1504                    curSVRegMap.find(sentry.first)->second = sentry.second;
1505                else // no before that
1506                    curSVRegMap.erase(sentry.first);
1507           
1508            for (const auto& sentry: cblock.ssaInfoMap)
1509            {
1510                auto it = alreadyReadMap.find(sentry.first);
1511                if (it != alreadyReadMap.end() && it->second == entry.blockIndex)
1512                    // remove old to resolve in leaved way to allow collecting next ssaId
1513                    // before write (can be different due to earlier visit)
1514                    alreadyReadMap.erase(it);
1515            }
1516            ARDOut << "  popjoin\n";
1517            flowStack.pop_back();
1518        }
1519    }
1520}
1521
1522/* TODO: handling livenesses between routine call:
1523 *   for any routine call in call point:
1524 *     add extra liveness point which will be added to liveness of the vars used between
1525 *     call point and to liveness of the vars used inside routine
1526 */
1527
1528void AsmRegAllocator::createLivenesses(ISAUsageHandler& usageHandler)
1529{
1530    ARDOut << "----- createLivenesses ------\n";
1531    // construct var index maps
1532    cxuint regRanges[MAX_REGTYPES_NUM*2];
1533    std::fill(graphVregsCounts, graphVregsCounts+MAX_REGTYPES_NUM, size_t(0));
1534    size_t regTypesNum;
1535    assembler.isaAssembler->getRegisterRanges(regTypesNum, regRanges);
1536   
1537    for (const CodeBlock& cblock: codeBlocks)
1538        for (const auto& entry: cblock.ssaInfoMap)
1539        {
1540            const SSAInfo& sinfo = entry.second;
1541            cxuint regType = getRegType(regTypesNum, regRanges, entry.first);
1542            VarIndexMap& vregIndices = vregIndexMaps[regType];
1543            size_t& graphVregsCount = graphVregsCounts[regType];
1544            std::vector<size_t>& ssaIdIndices = vregIndices[entry.first];
1545            size_t ssaIdCount = 0;
1546            if (sinfo.readBeforeWrite)
1547                ssaIdCount = sinfo.ssaIdBefore+1;
1548            if (sinfo.ssaIdChange!=0)
1549            {
1550                ssaIdCount = std::max(ssaIdCount, sinfo.ssaIdLast+1);
1551                ssaIdCount = std::max(ssaIdCount, sinfo.ssaId+sinfo.ssaIdChange-1);
1552                ssaIdCount = std::max(ssaIdCount, sinfo.ssaIdFirst+1);
1553            }
1554            // if not readBeforeWrite and neither ssaIdChanges but it is write to
1555            // normal register
1556            if (entry.first.regVar==nullptr)
1557                ssaIdCount = 1;
1558           
1559            if (ssaIdIndices.size() < ssaIdCount)
1560                ssaIdIndices.resize(ssaIdCount, SIZE_MAX);
1561           
1562            // set liveness index to ssaIdIndices
1563            if (sinfo.readBeforeWrite)
1564            {
1565                if (ssaIdIndices[sinfo.ssaIdBefore] == SIZE_MAX)
1566                    ssaIdIndices[sinfo.ssaIdBefore] = graphVregsCount++;
1567            }
1568            if (sinfo.ssaIdChange!=0)
1569            {
1570                // fill up ssaIdIndices (with graph Ids)
1571                if (ssaIdIndices[sinfo.ssaIdFirst] == SIZE_MAX)
1572                    ssaIdIndices[sinfo.ssaIdFirst] = graphVregsCount++;
1573                for (size_t ssaId = sinfo.ssaId+1;
1574                        ssaId < sinfo.ssaId+sinfo.ssaIdChange-1; ssaId++)
1575                    ssaIdIndices[ssaId] = graphVregsCount++;
1576                if (ssaIdIndices[sinfo.ssaIdLast] == SIZE_MAX)
1577                    ssaIdIndices[sinfo.ssaIdLast] = graphVregsCount++;
1578            }
1579            // if not readBeforeWrite and neither ssaIdChanges but it is write to
1580            // normal register
1581            if (entry.first.regVar==nullptr && ssaIdIndices[0] == SIZE_MAX)
1582                ssaIdIndices[0] = graphVregsCount++;
1583        }
1584   
1585    // construct vreg liveness
1586    std::deque<CallStackEntry2> callStack;
1587    std::deque<FlowStackEntry3> flowStack;
1588    std::vector<bool> visited(codeBlocks.size(), false);
1589    // hold last vreg ssaId and position
1590    LastVRegMap lastVRegMap;
1591   
1592    // key - current res first key, value - previous first key and its flowStack pos
1593    PrevWaysIndexMap prevWaysIndexMap;
1594    // to track ways last block indices pair: block index, flowStackPos)
1595    std::pair<size_t, size_t> lastCommonCacheWayPoint{ SIZE_MAX, SIZE_MAX };
1596    std::vector<bool> waysToCache(codeBlocks.size(), false);
1597    ResSecondPointsToCache cblocksToCache(codeBlocks.size());
1598   
1599    size_t rbwCount = 0;
1600    size_t wrCount = 0;
1601   
1602    RoutineLvMap routineMap;
1603    std::vector<Liveness> livenesses[MAX_REGTYPES_NUM];
1604   
1605    for (size_t i = 0; i < regTypesNum; i++)
1606        livenesses[i].resize(graphVregsCounts[i]);
1607   
1608    size_t curLiveTime = 0;
1609    flowStack.push_back({ 0, 0 });
1610   
1611    while (!flowStack.empty())
1612    {
1613        FlowStackEntry3& entry = flowStack.back();
1614        CodeBlock& cblock = codeBlocks[entry.blockIndex];
1615       
1616        if (entry.nextIndex == 0)
1617        {
1618            curLiveTime = cblock.start;
1619            // process current block
1620            if (!visited[entry.blockIndex])
1621            {
1622                visited[entry.blockIndex] = true;
1623                ARDOut << "joinpush: " << entry.blockIndex << "\n";
1624                if (flowStack.size() > 1)
1625                    putCrossBlockLivenesses(flowStack, codeBlocks, lastVRegMap,
1626                            livenesses, vregIndexMaps, regTypesNum, regRanges);
1627                // update last vreg position
1628                for (const auto& sentry: cblock.ssaInfoMap)
1629                {
1630                    // update
1631                    auto res = lastVRegMap.insert({ sentry.first,
1632                                { { flowStack.size()-1, false } } });
1633                    if (!res.second) // if not first seen, just update
1634                        // update last
1635                        res.first->second.push_back({ flowStack.size()-1, false });
1636                   
1637                    // count read before writes (for cache weight)
1638                    if (sentry.second.readBeforeWrite)
1639                        rbwCount++;
1640                    if (sentry.second.ssaIdChange!=0)
1641                        wrCount++;
1642                }
1643               
1644                // main routine to handle ssaInfos
1645                SVRegMap ssaIdIdxMap;
1646                AsmRegVarUsage instrRVUs[8];
1647                cxuint instrRVUsCount = 0;
1648               
1649                size_t oldOffset = cblock.usagePos.readOffset;
1650                std::vector<AsmSingleVReg> readSVRegs;
1651                std::vector<AsmSingleVReg> writtenSVRegs;
1652               
1653                usageHandler.setReadPos(cblock.usagePos);
1654                // register in liveness
1655                while (true)
1656                {
1657                    AsmRegVarUsage rvu = { 0U, nullptr, 0U, 0U };
1658                    bool hasNext = false;
1659                    if (usageHandler.hasNext() && oldOffset < cblock.end)
1660                    {
1661                        hasNext = true;
1662                        rvu = usageHandler.nextUsage();
1663                    }
1664                    const size_t liveTime = oldOffset;
1665                    if ((!hasNext || rvu.offset > oldOffset) && oldOffset < cblock.end)
1666                    {
1667                        ARDOut << "apply to liveness. offset: " << oldOffset << "\n";
1668                        // apply to liveness
1669                        for (AsmSingleVReg svreg: readSVRegs)
1670                        {
1671                            auto svrres = ssaIdIdxMap.insert({ svreg, 0 });
1672                            Liveness& lv = getLiveness(svreg, svrres.first->second,
1673                                    cblock.ssaInfoMap.find(svreg)->second,
1674                                    livenesses, vregIndexMaps, regTypesNum, regRanges);
1675                            if (svrres.second)
1676                                // begin region from this block
1677                                lv.newRegion(curLiveTime);
1678                            lv.expand(liveTime);
1679                        }
1680                        for (AsmSingleVReg svreg: writtenSVRegs)
1681                        {
1682                            size_t& ssaIdIdx = ssaIdIdxMap[svreg];
1683                            ssaIdIdx++;
1684                            SSAInfo& sinfo = cblock.ssaInfoMap.find(svreg)->second;
1685                            Liveness& lv = getLiveness(svreg, ssaIdIdx, sinfo,
1686                                    livenesses, vregIndexMaps, regTypesNum, regRanges);
1687                            // works only with ISA where smallest instruction have 2 bytes!
1688                            // after previous read, but not after instruction.
1689                            // if var is not used anywhere then this liveness region
1690                            // blocks assignment for other vars
1691                            lv.insert(liveTime+1, liveTime+2);
1692                        }
1693                        // get linear deps and equal to
1694                        cxbyte lDeps[16];
1695                        usageHandler.getUsageDependencies(instrRVUsCount, instrRVUs, lDeps);
1696                       
1697                        addUsageDeps(lDeps, instrRVUsCount, instrRVUs,
1698                                linearDepMaps, vregIndexMaps, ssaIdIdxMap,
1699                                regTypesNum, regRanges);
1700                       
1701                        readSVRegs.clear();
1702                        writtenSVRegs.clear();
1703                        if (!hasNext)
1704                            break;
1705                        oldOffset = rvu.offset;
1706                        instrRVUsCount = 0;
1707                    }
1708                    if (hasNext && oldOffset < cblock.end && !rvu.useRegMode)
1709                        instrRVUs[instrRVUsCount++] = rvu;
1710                    if (oldOffset >= cblock.end)
1711                        break;
1712                   
1713                    for (uint16_t rindex = rvu.rstart; rindex < rvu.rend; rindex++)
1714                    {
1715                        // per register/singlvreg
1716                        AsmSingleVReg svreg{ rvu.regVar, rindex };
1717                        if (rvu.rwFlags == ASMRVU_WRITE && rvu.regField!=ASMFIELD_NONE)
1718                            writtenSVRegs.push_back(svreg);
1719                        else // read or treat as reading // expand previous region
1720                            readSVRegs.push_back(svreg);
1721                    }
1722                }
1723            }
1724            else
1725            {
1726                cblocksToCache.increase(entry.blockIndex);
1727                ARDOut << "jcblockToCache: " << entry.blockIndex << "=" <<
1728                            cblocksToCache.count(entry.blockIndex) << "\n";
1729               
1730                // back, already visited
1731                flowStack.pop_back();
1732               
1733                size_t curWayBIndex = flowStack.back().blockIndex;
1734                if (lastCommonCacheWayPoint.first != SIZE_MAX)
1735                {
1736                    // mark point of way to cache (res first point)
1737                    waysToCache[lastCommonCacheWayPoint.first] = true;
1738                    ARDOut << "mark to pfcache " <<
1739                            lastCommonCacheWayPoint.first << ", " <<
1740                            curWayBIndex << "\n";
1741                    prevWaysIndexMap[curWayBIndex] = lastCommonCacheWayPoint;
1742                }
1743                lastCommonCacheWayPoint = { curWayBIndex, flowStack.size()-1 };
1744                ARDOut << "lastCcwP: " << curWayBIndex << "\n";
1745                continue;
1746            }
1747        }
1748       
1749        if (!callStack.empty() &&
1750            entry.blockIndex == callStack.back().callBlock &&
1751            entry.nextIndex-1 == callStack.back().callNextIndex)
1752        {
1753            ARDOut << " ret: " << entry.blockIndex << "\n";
1754            auto res = routineMap.insert({ entry.blockIndex, { } });
1755            if (res.second)
1756                createRoutineDataLv(codeBlocks, routineMap, res.first->second,
1757                        entry.blockIndex, vregIndexMaps, regTypesNum, regRanges);
1758            else
1759            {
1760                // already added join livenesses from all readBeforeWrites
1761                for (const auto& entry: res.first->second.rbwSSAIdMap)
1762                {
1763                    // find last
1764                    auto lvrit = lastVRegMap.find(entry.first);
1765                    FlowStackCIter flit = flowStack.begin();
1766                    if (lvrit != lastVRegMap.end())
1767                        flit += lvrit->second.back().blockIndex;
1768                   
1769                    const CodeBlock& lastBlk = codeBlocks[flit->blockIndex];
1770                    auto sinfoIt = lastBlk.ssaInfoMap.find(entry.first);
1771                    Liveness& lv = getLiveness2(entry.first, entry.second, livenesses, 
1772                                vregIndexMaps, regTypesNum, regRanges);
1773                   
1774                    if (lv.contain(codeBlocks[(flowStack.end()-1)->blockIndex].end-1))
1775                        // already joined (check last byte from last block)
1776                        continue;
1777                   
1778                    size_t lastPos = lastBlk.start;
1779                    if (sinfoIt != lastBlk.ssaInfoMap.end())
1780                    {
1781                        // if begin at some point at last block
1782                        lastPos = sinfoIt->second.lastPos;
1783                        lv.insert(lastPos + 1, lastBlk.end);
1784                        ++flit; // skip last block in stack
1785                    }
1786                   
1787                    for (; flit != flowStack.end(); ++flit)
1788                    {
1789                        const CodeBlock& cblock = codeBlocks[flit->blockIndex];
1790                        lv.insert(cblock.start, cblock.end);
1791                    }
1792                }
1793            }
1794            callStack.pop_back(); // just return from call
1795        }
1796       
1797        if (entry.nextIndex < cblock.nexts.size())
1798        {
1799            //bool isCall = false;
1800            size_t nextBlock = cblock.nexts[entry.nextIndex].block;
1801            if (cblock.nexts[entry.nextIndex].isCall)
1802            {
1803                callStack.push_back({ entry.blockIndex, entry.nextIndex, nextBlock });
1804                //isCall = true;
1805            }
1806           
1807            flowStack.push_back({ cblock.nexts[entry.nextIndex].block, 0 });
1808            entry.nextIndex++;
1809        }
1810        else if (entry.nextIndex==0 && cblock.nexts.empty() && !cblock.haveEnd)
1811        {
1812            flowStack.push_back({ entry.blockIndex+1, 0 });
1813            entry.nextIndex++;
1814        }
1815        else // back
1816        {
1817            // revert lastSSAIdMap
1818            flowStack.pop_back();
1819            if (!flowStack.empty())
1820                for (const auto& sentry: cblock.ssaInfoMap)
1821                {
1822                    auto lvrit = lastVRegMap.find(sentry.first);
1823                    if (lvrit != lastVRegMap.end())
1824                    {
1825                        std::vector<LastAccessBlockPos>& lastPos = lvrit->second;
1826                        lastPos.pop_back();
1827                        if (lastPos.empty()) // just remove from lastVRegs
1828                            lastVRegMap.erase(lvrit);
1829                    }
1830                }
1831           
1832            if (!flowStack.empty() && lastCommonCacheWayPoint.first != SIZE_MAX &&
1833                    lastCommonCacheWayPoint.second >= flowStack.size())
1834            {
1835                lastCommonCacheWayPoint =
1836                        { flowStack.back().blockIndex, flowStack.size()-1 };
1837                ARDOut << "POPlastCcwP: " << lastCommonCacheWayPoint.first << "\n";
1838            }
1839        }
1840    }
1841   
1842    // after, that resolve joins (join with already visited code)
1843    // SVRegMap in this cache: key - vreg, value - last flowStack entry position
1844    SimpleCache<size_t, SVRegMap> joinFirstPointsCache(wrCount<<1);
1845    // SVRegMap in this cache: key - vreg, value - first readBefore in second part
1846    SimpleCache<size_t, SVRegMap> joinSecondPointsCache(rbwCount<<1);
1847   
1848    flowStack.clear();
1849    std::fill(visited.begin(), visited.end(), false);
1850   
1851    flowStack.push_back({ 0, 0 });
1852   
1853    while (!flowStack.empty())
1854    {
1855        FlowStackEntry3& entry = flowStack.back();
1856        CodeBlock& cblock = codeBlocks[entry.blockIndex];
1857       
1858        if (entry.nextIndex == 0)
1859        {
1860            // process current block
1861            if (!visited[entry.blockIndex])
1862                visited[entry.blockIndex] = true;
1863            else
1864            {
1865                joinRegVarLivenesses(flowStack, codeBlocks,
1866                        prevWaysIndexMap, waysToCache, cblocksToCache,
1867                        joinFirstPointsCache, joinSecondPointsCache,
1868                        vregIndexMaps, livenesses, regTypesNum, regRanges);
1869                // back, already visited
1870                flowStack.pop_back();
1871                continue;
1872            }
1873        }
1874       
1875        if (entry.nextIndex < cblock.nexts.size())
1876        {
1877            flowStack.push_back({ cblock.nexts[entry.nextIndex].block, 0 });
1878            entry.nextIndex++;
1879        }
1880        else if (((entry.nextIndex==0 && cblock.nexts.empty()) ||
1881                // if have any call then go to next block
1882                (cblock.haveCalls && entry.nextIndex==cblock.nexts.size())) &&
1883                 !cblock.haveReturn && !cblock.haveEnd)
1884        {
1885            flowStack.push_back({ entry.blockIndex+1, 0 });
1886            entry.nextIndex++;
1887        }
1888        else // back
1889        {
1890            if (cblocksToCache.count(entry.blockIndex)==2 &&
1891                !joinSecondPointsCache.hasKey(entry.blockIndex))
1892                // add to cache
1893                addJoinSecCacheEntry(codeBlocks, joinSecondPointsCache,
1894                            entry.blockIndex);
1895            flowStack.pop_back();
1896        }
1897    }
1898   
1899    // move livenesses to AsmRegAllocator outLivenesses
1900    for (size_t regType = 0; regType < regTypesNum; regType++)
1901    {
1902        std::vector<Liveness>& livenesses2 = livenesses[regType];
1903        Array<OutLiveness>& outLivenesses2 = outLivenesses[regType];
1904        outLivenesses2.resize(livenesses2.size());
1905        for (size_t li = 0; li < livenesses2.size(); li++)
1906        {
1907            outLivenesses2[li].resize(livenesses2[li].l.size());
1908            std::copy(livenesses2[li].l.begin(), livenesses2[li].l.end(),
1909                      outLivenesses2[li].begin());
1910            livenesses2[li].clear();
1911        }
1912        livenesses2.clear();
1913    }
1914}
1915
1916void AsmRegAllocator::createInterferenceGraph()
1917{
1918    /// construct liveBlockMaps
1919    std::set<LiveBlock> liveBlockMaps[MAX_REGTYPES_NUM];
1920    for (size_t regType = 0; regType < regTypesNum; regType++)
1921    {
1922        std::set<LiveBlock>& liveBlockMap = liveBlockMaps[regType];
1923        Array<OutLiveness>& liveness = outLivenesses[regType];
1924        for (size_t li = 0; li < liveness.size(); li++)
1925        {
1926            OutLiveness& lv = liveness[li];
1927            for (const std::pair<size_t, size_t>& blk: lv)
1928                if (blk.first != blk.second)
1929                    liveBlockMap.insert({ blk.first, blk.second, li });
1930            lv.clear();
1931        }
1932        liveness.clear();
1933    }
1934   
1935    // create interference graphs
1936    for (size_t regType = 0; regType < regTypesNum; regType++)
1937    {
1938        InterGraph& interGraph = interGraphs[regType];
1939        interGraph.resize(graphVregsCounts[regType]);
1940        std::set<LiveBlock>& liveBlockMap = liveBlockMaps[regType];
1941       
1942        auto lit = liveBlockMap.begin();
1943        size_t rangeStart = 0;
1944        if (lit != liveBlockMap.end())
1945            rangeStart = lit->start;
1946        while (lit != liveBlockMap.end())
1947        {
1948            const size_t blkStart = lit->start;
1949            const size_t blkEnd = lit->end;
1950            size_t rangeEnd = blkEnd;
1951            auto liStart = liveBlockMap.lower_bound({ rangeStart, 0, 0 });
1952            auto liEnd = liveBlockMap.lower_bound({ rangeEnd, 0, 0 });
1953            // collect from this range, variable indices
1954            std::set<size_t> varIndices;
1955            for (auto lit2 = liStart; lit2 != liEnd; ++lit2)
1956                varIndices.insert(lit2->vidx);
1957            // push to intergraph as full subgGraph
1958            for (auto vit = varIndices.begin(); vit != varIndices.end(); ++vit)
1959                for (auto vit2 = varIndices.begin(); vit2 != varIndices.end(); ++vit2)
1960                    if (vit != vit2)
1961                        interGraph[*vit].insert(*vit2);
1962            // go to next live blocks
1963            rangeStart = rangeEnd;
1964            for (; lit != liveBlockMap.end(); ++lit)
1965                if (lit->start != blkStart && lit->end != blkEnd)
1966                    break;
1967            if (lit == liveBlockMap.end())
1968                break; //
1969            rangeStart = std::max(rangeStart, lit->start);
1970        }
1971    }
1972}
1973
1974/* algorithm to allocate regranges:
1975 * from smallest regranges to greatest regranges:
1976 *   choosing free register: from smallest free regranges
1977 *      to greatest regranges:
1978 *         in this same regrange:
1979 *               try to find free regs in regranges
1980 *               try to link free ends of two distinct regranges
1981 */
1982
1983void AsmRegAllocator::colorInterferenceGraph()
1984{
1985    const GPUArchitecture arch = getGPUArchitectureFromDeviceType(
1986                    assembler.deviceType);
1987   
1988    for (size_t regType = 0; regType < regTypesNum; regType++)
1989    {
1990        const size_t maxColorsNum = getGPUMaxRegistersNum(arch, regType);
1991        InterGraph& interGraph = interGraphs[regType];
1992        const VarIndexMap& vregIndexMap = vregIndexMaps[regType];
1993        Array<cxuint>& gcMap = graphColorMaps[regType];
1994       
1995        const size_t nodesNum = interGraph.size();
1996        gcMap.resize(nodesNum);
1997        std::fill(gcMap.begin(), gcMap.end(), cxuint(UINT_MAX));
1998        Array<size_t> sdoCounts(nodesNum);
1999        std::fill(sdoCounts.begin(), sdoCounts.end(), 0);
2000       
2001        SDOLDOCompare compare(interGraph, sdoCounts);
2002        std::set<size_t, SDOLDOCompare> nodeSet(compare);
2003        for (size_t i = 0; i < nodesNum; i++)
2004            nodeSet.insert(i);
2005       
2006        cxuint colorsNum = 0;
2007        // firstly, allocate real registers
2008        for (const auto& entry: vregIndexMap)
2009            if (entry.first.regVar == nullptr)
2010                gcMap[entry.second[0]] = colorsNum++;
2011       
2012        for (size_t colored = 0; colored < nodesNum; colored++)
2013        {
2014            size_t node = *nodeSet.begin();
2015            if (gcMap[node] != UINT_MAX)
2016                continue; // already colored
2017            size_t color = 0;
2018           
2019            for (color = 0; color <= colorsNum; color++)
2020            {
2021                // find first usable color
2022                bool thisSame = false;
2023                for (size_t nb: interGraph[node])
2024                    if (gcMap[nb] == color)
2025                    {
2026                        thisSame = true;
2027                        break;
2028                    }
2029                if (!thisSame)
2030                    break;
2031            }
2032            if (color==colorsNum) // add new color if needed
2033            {
2034                if (colorsNum >= maxColorsNum)
2035                    throw AsmException("Too many register is needed");
2036                colorsNum++;
2037            }
2038           
2039            gcMap[node] = color;
2040            // update SDO for node
2041            bool colorExists = false;
2042            for (size_t nb: interGraph[node])
2043                if (gcMap[nb] == color)
2044                {
2045                    colorExists = true;
2046                    break;
2047                }
2048            if (!colorExists)
2049                sdoCounts[node]++;
2050            // update SDO for neighbors
2051            for (size_t nb: interGraph[node])
2052            {
2053                colorExists = false;
2054                for (size_t nb2: interGraph[nb])
2055                    if (gcMap[nb2] == color)
2056                    {
2057                        colorExists = true;
2058                        break;
2059                    }
2060                if (!colorExists)
2061                {
2062                    if (gcMap[nb] == UINT_MAX)
2063                        nodeSet.erase(nb);  // before update we erase from nodeSet
2064                    sdoCounts[nb]++;
2065                    if (gcMap[nb] == UINT_MAX)
2066                        nodeSet.insert(nb); // after update, insert again
2067                }
2068            }
2069           
2070            gcMap[node] = color;
2071        }
2072    }
2073}
2074
2075void AsmRegAllocator::allocateRegisters(cxuint sectionId)
2076{
2077    // before any operation, clear all
2078    codeBlocks.clear();
2079    for (size_t i = 0; i < MAX_REGTYPES_NUM; i++)
2080    {
2081        graphVregsCounts[i] = 0;
2082        vregIndexMaps[i].clear();
2083        interGraphs[i].clear();
2084        linearDepMaps[i].clear();
2085        graphColorMaps[i].clear();
2086    }
2087    ssaReplacesMap.clear();
2088    cxuint maxRegs[MAX_REGTYPES_NUM];
2089    assembler.isaAssembler->getMaxRegistersNum(regTypesNum, maxRegs);
2090   
2091    // set up
2092    const AsmSection& section = assembler.sections[sectionId];
2093    createCodeStructure(section.codeFlow, section.content.size(), section.content.data());
2094    createSSAData(*section.usageHandler);
2095    applySSAReplaces();
2096    createLivenesses(*section.usageHandler);
2097    createInterferenceGraph();
2098    colorInterferenceGraph();
2099}
Note: See TracBrowser for help on using the repository browser.