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

Last change on this file since 3607 was 3607, checked in by matszpk, 3 years ago

CLRadeonExtender: AsmRegAlloc?: resolveSSAConflict: Mark regvar handled only if conflict found and inserted to ssaReplaces.

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