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

Last change on this file since 3585 was 3585, checked in by matszpk, 11 months ago

CLRadeonExtender: AsmRegAlloc?: Set routine processed before leaving from it.

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