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

Last change on this file since 3601 was 3601, checked in by matszpk, 6 weeks ago

CLRadeonExtender: AsmRegAlloc?: Next createSSAData testcase.

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