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

Last change on this file was 4575, checked in by matszpk, 10 months ago

CLRadeonExtender: AsmRegAlloc?: Add findPositionByOffset to ISAUsageHandler (untested).

File size: 27.9 KB
Line 
1/*
2 *  CLRadeonExtender - Unofficial OpenCL Radeon Extensions Library
3 *  Copyright (C) 2014-2018 Mateusz Szpakowski
4 *
5 *  This library is free software; you can redistribute it and/or
6 *  modify it under the terms of the GNU Lesser General Public
7 *  License as published by the Free Software Foundation; either
8 *  version 2.1 of the License, or (at your option) any later version.
9 *
10 *  This library is distributed in the hope that it will be useful,
11 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
12 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
13 *  Lesser General Public License for more details.
14 *
15 *  You should have received a copy of the GNU Lesser General Public
16 *  License along with this library; if not, write to the Free Software
17 *  Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
18 */
19
20#include <CLRX/Config.h>
21#include <assert.h>
22#include <iostream>
23#include <cstddef>
24#include <stack>
25#include <deque>
26#include <vector>
27#include <utility>
28#include <unordered_set>
29#include <map>
30#include <set>
31#include <unordered_map>
32#include <algorithm>
33#include <CLRX/utils/Utilities.h>
34#include <CLRX/utils/Containers.h>
35#include <CLRX/amdasm/Assembler.h>
36#include "AsmInternals.h"
37#include "AsmRegAlloc.h"
38
39using namespace CLRX;
40
41#if ASMREGALLOC_DEBUGDUMP
42std::ostream& operator<<(std::ostream& os, const CLRX::BlockIndex& v)
43{
44    if (v.pass==0)
45        return os << v.index;
46    else
47        return os << v.index << "#" << v.pass;
48}
49#endif
50
51ISAUsageHandler::ISAUsageHandler()
52{ }
53
54ISAUsageHandler::~ISAUsageHandler()
55{ }
56
57void ISAUsageHandler::pushUsage(const AsmRegVarUsage& rvu)
58{
59    if (!chunks.empty())
60    {
61        const Chunk& last = chunks.back();
62       
63        if ((last.offsetFirst & ~size_t(0xffff)) != (rvu.offset & ~size_t(0xffff)))
64            // add new chunk
65            chunks.push_back(Chunk{ rvu.offset });
66    }
67    else
68        chunks.push_back(Chunk{ rvu.offset });
69   
70    const cxbyte align = rvu.align!=0 ? 32-CLZ32(rvu.align) : 0;
71    chunks.back().items.push_back(RegVarUsageInt{ rvu.regVar, rvu.rstart, rvu.rend, 
72                rvu.regField, rvu.rwFlags, align, rvu.useRegMode,
73                uint16_t(rvu.offset & 0xffffU) });
74}
75
76AsmRegVarUsage ISAUsageHandler::nextUsage(ReadPos& readPos)
77{
78    const Chunk& chunk = chunks[readPos.chunkPos];
79    const RegVarUsageInt& item = chunk.items[readPos.itemPos];
80    readPos.itemPos++;
81    // fix itemPos to zero
82    if (readPos.itemPos >= chunk.items.size())
83    {
84        readPos.itemPos = 0;
85        readPos.chunkPos++;
86    }
87    const cxbyte outAlign = item.align!=0 ? 1U<<(item.align-1) : 0;
88    return AsmRegVarUsage{ (chunk.offsetFirst & ~size_t(0xffffU)) | item.offsetLo,
89            item.regVar, item.rstart, item.rend, item.regField, item.rwFlags,
90            cxbyte(outAlign), item.useRegMode!=0 };
91}
92
93ISAUsageHandler::ReadPos ISAUsageHandler::findPositionByOffset(size_t offset) const
94{
95    if (chunks.empty())
96        return ReadPos{ 0, 0 };
97    size_t chunkPos = std::lower_bound(chunks.begin(), chunks.end(), Chunk{ offset },
98            [](const Chunk& a, const Chunk& b)
99            { return a.offsetFirst < b.offsetFirst; }) - chunks.begin();
100    // fix - move back if found offset is greater or if end
101    if (chunkPos == chunks.size() ||
102        (chunkPos != 0 && chunks[chunkPos].offsetFirst != offset))
103        chunkPos--;
104   
105    size_t itemPos = 0;
106    if (chunks[chunkPos].offsetFirst != offset)
107    {
108        const std::vector<RegVarUsageInt>& items = chunks[chunkPos].items;
109        RegVarUsageInt rvu;
110        rvu.offsetLo = uint16_t(offset & 0xffff);
111        size_t itemPos = std::lower_bound(items.begin(), items.end(), rvu,
112                [](const RegVarUsageInt& a, const RegVarUsageInt& b)
113                { return a.offsetLo < b.offsetLo; }) - items.begin();
114        // fix itemPos to zero
115        if (itemPos >= items.size())
116        {
117            chunkPos++;
118            itemPos = 0;
119        }
120    }
121    return ReadPos{ chunkPos, itemPos };
122}
123
124
125ISALinearDepHandler::ISALinearDepHandler()
126{ }
127
128size_t ISALinearDepHandler::findPositionByOffset(size_t offset) const
129{
130    return std::lower_bound(regVarLinDeps.begin(), regVarLinDeps.end(),
131            AsmRegVarLinearDep{offset},
132            [](const AsmRegVarLinearDep& a, const AsmRegVarLinearDep& b)
133            { return a.offset < b.offset; }) - regVarLinDeps.begin();
134}
135
136ISALinearDepHandler* ISALinearDepHandler::copy() const
137{
138    return new ISALinearDepHandler(*this);
139}
140
141/*
142 * Asm register allocator stuff
143 */
144
145AsmRegAllocator::AsmRegAllocator(Assembler& _assembler) : assembler(_assembler)
146{ }
147
148AsmRegAllocator::AsmRegAllocator(Assembler& _assembler,
149        const std::vector<CodeBlock>& _codeBlocks, const SSAReplacesMap& _ssaReplacesMap)
150        : assembler(_assembler), codeBlocks(_codeBlocks), ssaReplacesMap(_ssaReplacesMap)
151{ }
152
153static inline bool codeBlockStartLess(const AsmRegAllocator::CodeBlock& c1,
154                  const AsmRegAllocator::CodeBlock& c2)
155{ return c1.start < c2.start; }
156
157static inline bool codeBlockEndLess(const AsmRegAllocator::CodeBlock& c1,
158                  const AsmRegAllocator::CodeBlock& c2)
159{ return c1.end < c2.end; }
160
161void AsmRegAllocator::createCodeStructure(const std::vector<AsmCodeFlowEntry>& codeFlow,
162             size_t codeSize, const cxbyte* code)
163{
164    ISAAssembler* isaAsm = assembler.isaAssembler;
165    if (codeSize == 0)
166        return;
167    std::vector<size_t> splits;
168    std::vector<size_t> codeStarts;
169    std::vector<size_t> codeEnds;
170    codeStarts.push_back(0);
171    codeEnds.push_back(codeSize);
172    for (const AsmCodeFlowEntry& entry: codeFlow)
173    {
174        size_t instrAfter = 0;
175        if (entry.type == AsmCodeFlowType::JUMP || entry.type == AsmCodeFlowType::CJUMP ||
176            entry.type == AsmCodeFlowType::CALL || entry.type == AsmCodeFlowType::RETURN)
177            instrAfter = entry.offset + isaAsm->getInstructionSize(
178                        codeSize - entry.offset, code + entry.offset);
179       
180        switch(entry.type)
181        {
182            case AsmCodeFlowType::START:
183                codeStarts.push_back(entry.offset);
184                break;
185            case AsmCodeFlowType::END:
186                codeEnds.push_back(entry.offset);
187                break;
188            case AsmCodeFlowType::JUMP:
189                splits.push_back(entry.target);
190                codeEnds.push_back(instrAfter);
191                break;
192            case AsmCodeFlowType::CJUMP:
193                splits.push_back(entry.target);
194                splits.push_back(instrAfter);
195                break;
196            case AsmCodeFlowType::CALL:
197                splits.push_back(entry.target);
198                splits.push_back(instrAfter);
199                break;
200            case AsmCodeFlowType::RETURN:
201                codeEnds.push_back(instrAfter);
202                break;
203            default:
204                break;
205        }
206    }
207    std::sort(splits.begin(), splits.end());
208    splits.resize(std::unique(splits.begin(), splits.end()) - splits.begin());
209    std::sort(codeEnds.begin(), codeEnds.end());
210    codeEnds.resize(std::unique(codeEnds.begin(), codeEnds.end()) - codeEnds.begin());
211    // remove codeStarts between codeStart and codeEnd
212    size_t i = 0;
213    size_t ii = 0;
214    size_t ei = 0; // codeEnd i
215    while (i < codeStarts.size())
216    {
217        size_t end = (ei < codeEnds.size() ? codeEnds[ei] : SIZE_MAX);
218        if (ei < codeEnds.size())
219            ei++;
220        codeStarts[ii++] = codeStarts[i];
221        // skip codeStart to end
222        for (i++ ;i < codeStarts.size() && codeStarts[i] < end; i++);
223    }
224    codeStarts.resize(ii);
225    // add next codeStarts
226    auto splitIt = splits.begin();
227    for (size_t codeEnd: codeEnds)
228    {
229        auto it = std::lower_bound(splitIt, splits.end(), codeEnd);
230        if (it != splits.end())
231        {
232            codeStarts.push_back(*it);
233            splitIt = it;
234        }
235        else // if end
236            break;
237    }
238   
239    std::sort(codeStarts.begin(), codeStarts.end());
240    codeStarts.resize(std::unique(codeStarts.begin(), codeStarts.end()) -
241                codeStarts.begin());
242    // divide to blocks
243    splitIt = splits.begin();
244    for (size_t codeStart: codeStarts)
245    {
246        size_t codeEnd = *std::upper_bound(codeEnds.begin(), codeEnds.end(), codeStart);
247        splitIt = std::lower_bound(splitIt, splits.end(), codeStart);
248       
249        if (splitIt != splits.end() && *splitIt==codeStart)
250            ++splitIt; // skip split in codeStart
251       
252        for (size_t start = codeStart; start < codeEnd; )
253        {
254            size_t end = codeEnd;
255            if (splitIt != splits.end())
256            {
257                end = std::min(end, *splitIt);
258                ++splitIt;
259            }
260            codeBlocks.push_back({ start, end, { }, false, false, false });
261            start = end;
262        }
263    }
264    // force empty block at end if some jumps goes to its
265    if (!codeEnds.empty() && !codeStarts.empty() && !splits.empty() &&
266        codeStarts.back()==codeEnds.back() && codeStarts.back() == splits.back())
267        codeBlocks.push_back({ codeStarts.back(), codeStarts.back(), { },
268                             false, false, false });
269   
270    // construct flow-graph
271    for (const AsmCodeFlowEntry& entry: codeFlow)
272        if (entry.type == AsmCodeFlowType::CALL || entry.type == AsmCodeFlowType::JUMP ||
273            entry.type == AsmCodeFlowType::CJUMP || entry.type == AsmCodeFlowType::RETURN)
274        {
275            std::vector<CodeBlock>::iterator it;
276            size_t instrAfter = entry.offset + isaAsm->getInstructionSize(
277                        codeSize - entry.offset, code + entry.offset);
278           
279            if (entry.type != AsmCodeFlowType::RETURN)
280                it = binaryFind(codeBlocks.begin(), codeBlocks.end(),
281                        CodeBlock{ entry.target }, codeBlockStartLess);
282            else // return
283            {
284                it = binaryFind(codeBlocks.begin(), codeBlocks.end(),
285                        CodeBlock{ 0, instrAfter }, codeBlockEndLess);
286                // if block have return
287                if (it != codeBlocks.end())
288                    it->haveEnd = it->haveReturn = true;
289                continue;
290            }
291           
292            if (it == codeBlocks.end())
293                continue; // error!
294            auto it2 = std::lower_bound(codeBlocks.begin(), codeBlocks.end(),
295                    CodeBlock{ instrAfter }, codeBlockStartLess);
296            auto curIt = it2;
297            --curIt;
298           
299            curIt->nexts.push_back({ size_t(it - codeBlocks.begin()),
300                        entry.type == AsmCodeFlowType::CALL });
301            curIt->haveCalls |= entry.type == AsmCodeFlowType::CALL;
302            if (entry.type == AsmCodeFlowType::CJUMP ||
303                 entry.type == AsmCodeFlowType::CALL)
304            {
305                curIt->haveEnd = false; // revert haveEnd if block have cond jump or call
306                if (it2 != codeBlocks.end() && entry.type == AsmCodeFlowType::CJUMP)
307                    // add next next block (only for cond jump)
308                    curIt->nexts.push_back({ size_t(it2 - codeBlocks.begin()), false });
309            }
310            else if (entry.type == AsmCodeFlowType::JUMP)
311                curIt->haveEnd = true; // set end
312        }
313    // force haveEnd for block with cf_end
314    for (const AsmCodeFlowEntry& entry: codeFlow)
315        if (entry.type == AsmCodeFlowType::END)
316        {
317            auto it = binaryFind(codeBlocks.begin(), codeBlocks.end(),
318                    CodeBlock{ 0, entry.offset }, codeBlockEndLess);
319            if (it != codeBlocks.end())
320                it->haveEnd = true;
321        }
322   
323    if (!codeBlocks.empty()) // always set haveEnd to last block
324        codeBlocks.back().haveEnd = true;
325   
326    // reduce nexts
327    for (CodeBlock& block: codeBlocks)
328    {
329        // first non-call nexts, for correct resolving SSA conflicts
330        std::sort(block.nexts.begin(), block.nexts.end(),
331                  [](const NextBlock& n1, const NextBlock& n2)
332                  { return int(n1.isCall)<int(n2.isCall) ||
333                      (n1.isCall == n2.isCall && n1.block < n2.block); });
334        auto it = std::unique(block.nexts.begin(), block.nexts.end(),
335                  [](const NextBlock& n1, const NextBlock& n2)
336                  { return n1.block == n2.block && n1.isCall == n2.isCall; });
337        block.nexts.resize(it - block.nexts.begin());
338    }
339}
340
341
342void AsmRegAllocator::applySSAReplaces()
343{
344    if (ssaReplacesMap.empty())
345        return; // do nothing
346   
347    /* prepare SSA id replaces */
348    struct MinSSAGraphNode
349    {
350        size_t minSSAId;
351        bool visited;
352        std::unordered_set<size_t> nexts;
353        MinSSAGraphNode() : minSSAId(SIZE_MAX), visited(false)
354        { }
355    };
356   
357    typedef std::map<size_t, MinSSAGraphNode, std::greater<size_t> > SSAGraphNodesMap;
358   
359    struct MinSSAGraphStackEntry
360    {
361        SSAGraphNodesMap::iterator nodeIt;
362        std::unordered_set<size_t>::const_iterator nextIt;
363        size_t minSSAId;
364       
365        MinSSAGraphStackEntry(
366                SSAGraphNodesMap::iterator _nodeIt,
367                std::unordered_set<size_t>::const_iterator _nextIt,
368                size_t _minSSAId = SIZE_MAX)
369                : nodeIt(_nodeIt), nextIt(_nextIt), minSSAId(_minSSAId)
370        { }
371    };
372   
373    for (auto& entry: ssaReplacesMap)
374    {
375        ARDOut << "SSAReplace: " << entry.first.regVar << "." << entry.first.index << "\n";
376        VectorSet<SSAReplace>& replaces = entry.second;
377        std::sort(replaces.begin(), replaces.end(), std::greater<SSAReplace>());
378        replaces.resize(std::unique(replaces.begin(), replaces.end()) - replaces.begin());
379        VectorSet<SSAReplace> newReplaces;
380       
381        SSAGraphNodesMap ssaGraphNodes;
382       
383        auto it = replaces.begin();
384        while (it != replaces.end())
385        {
386            auto itEnd = std::upper_bound(it, replaces.end(),
387                    std::make_pair(it->first, size_t(0)), std::greater<SSAReplace>());
388            {
389                auto itLast = itEnd;
390                --itLast;
391                MinSSAGraphNode& node = ssaGraphNodes[it->first];
392                node.minSSAId = std::min(node.minSSAId, itLast->second);
393                for (auto it2 = it; it2 != itEnd; ++it2)
394                {
395                    node.nexts.insert(it2->second);
396                    ssaGraphNodes.insert({ it2->second, MinSSAGraphNode() });
397                }
398            }
399            it = itEnd;
400        }
401        /*for (const auto& v: ssaGraphNodes)
402            ARDOut << "  SSANode: " << v.first << ":" << &v.second << " minSSAID: " <<
403                            v.second.minSSAId << std::endl;*/
404        // propagate min value
405        std::stack<MinSSAGraphStackEntry> minSSAStack;
406       
407        // initialize parents and new nexts
408        for (auto ssaGraphNodeIt = ssaGraphNodes.begin();
409                 ssaGraphNodeIt!=ssaGraphNodes.end(); )
410        {
411            ARDOut << "  Start in " << ssaGraphNodeIt->first << "." << "\n";
412            minSSAStack.push({ ssaGraphNodeIt, ssaGraphNodeIt->second.nexts.begin() });
413            // traverse with minimalize SSA id
414            while (!minSSAStack.empty())
415            {
416                MinSSAGraphStackEntry& entry = minSSAStack.top();
417                MinSSAGraphNode& node = entry.nodeIt->second;
418                bool toPop = false;
419                if (entry.nextIt == node.nexts.begin())
420                {
421                    toPop = node.visited;
422                    node.visited = true;
423                }
424                if (!toPop && entry.nextIt != node.nexts.end())
425                {
426                    auto nodeIt = ssaGraphNodes.find(*entry.nextIt);
427                    if (nodeIt != ssaGraphNodes.end())
428                        minSSAStack.push({ nodeIt, nodeIt->second.nexts.begin(),
429                                    size_t(0) });
430                    ++entry.nextIt;
431                }
432                else
433                {
434                    minSSAStack.pop();
435                    if (!minSSAStack.empty())
436                        node.nexts.insert(minSSAStack.top().nodeIt->first);
437                }
438            }
439           
440            // skip visited nodes
441            for(; ssaGraphNodeIt != ssaGraphNodes.end(); ++ssaGraphNodeIt)
442                if (!ssaGraphNodeIt->second.visited)
443                    break;
444        }
445       
446        /*for (const auto& v: ssaGraphNodes)
447        {
448            ARDOut << "  Nexts: " << v.first << ":" << &v.second << " nexts:";
449            for (size_t p: v.second.nexts)
450                ARDOut << " " << p;
451            ARDOut << "\n";
452        }*/
453       
454        for (auto& entry: ssaGraphNodes)
455            entry.second.visited = false;
456       
457        std::vector<MinSSAGraphNode*> toClear; // nodes to clear
458       
459        for (auto ssaGraphNodeIt = ssaGraphNodes.begin();
460                 ssaGraphNodeIt!=ssaGraphNodes.end(); )
461        {
462            ARDOut << "  Start in " << ssaGraphNodeIt->first << "." << "\n";
463            minSSAStack.push({ ssaGraphNodeIt, ssaGraphNodeIt->second.nexts.begin() });
464            // traverse with minimalize SSA id
465            while (!minSSAStack.empty())
466            {
467                MinSSAGraphStackEntry& entry = minSSAStack.top();
468                MinSSAGraphNode& node = entry.nodeIt->second;
469                bool toPop = false;
470                if (entry.nextIt == node.nexts.begin())
471                {
472                    toPop = node.visited;
473                    if (!node.visited)
474                        // this flag visited for this node will be clear after this pass
475                        toClear.push_back(&node);
476                    node.visited = true;
477                }
478               
479                // try to children only all parents are visited and if parent has children
480                if (!toPop && entry.nextIt != node.nexts.end())
481                {
482                    auto nodeIt = ssaGraphNodes.find(*entry.nextIt);
483                    if (nodeIt != ssaGraphNodes.end())
484                    {
485                        ARDOut << "  Node: " <<
486                                entry.nodeIt->first << ":" << &node << " minSSAId: " <<
487                                node.minSSAId << " to " <<
488                                nodeIt->first << ":" << &(nodeIt->second) <<
489                                " minSSAId: " << nodeIt->second.minSSAId << "\n";
490                        nodeIt->second.minSSAId =
491                                std::min(nodeIt->second.minSSAId, node.minSSAId);
492                        minSSAStack.push({ nodeIt, nodeIt->second.nexts.begin(),
493                                nodeIt->second.minSSAId });
494                    }
495                    ++entry.nextIt;
496                }
497                else
498                {
499                    node.minSSAId = std::min(node.minSSAId, entry.minSSAId);
500                    ARDOut << "    Node: " <<
501                                entry.nodeIt->first << ":" << &node << " minSSAId: " <<
502                                node.minSSAId << "\n";
503                    minSSAStack.pop();
504                    if (!minSSAStack.empty())
505                    {
506                        MinSSAGraphStackEntry& pentry = minSSAStack.top();
507                        pentry.minSSAId = std::min(pentry.minSSAId, node.minSSAId);
508                    }
509                }
510            }
511           
512            const size_t minSSAId = ssaGraphNodeIt->second.minSSAId;
513           
514            // skip visited nodes
515            for(; ssaGraphNodeIt != ssaGraphNodes.end(); ++ssaGraphNodeIt)
516                if (!ssaGraphNodeIt->second.visited)
517                    break;
518            // zeroing visited
519            for (MinSSAGraphNode* node: toClear)
520            {
521                node->minSSAId = minSSAId; // fill up by minSSAId
522                node->visited = false;
523            }
524            toClear.clear();
525        }
526       
527        for (const auto& entry: ssaGraphNodes)
528            newReplaces.push_back({ entry.first, entry.second.minSSAId });
529       
530        std::sort(newReplaces.begin(), newReplaces.end());
531        entry.second = newReplaces;
532    }
533   
534    /* apply SSA id replaces */
535    for (CodeBlock& cblock: codeBlocks)
536        for (auto& ssaEntry: cblock.ssaInfoMap)
537        {
538            auto it = ssaReplacesMap.find(ssaEntry.first);
539            if (it == ssaReplacesMap.end())
540                continue;
541            SSAInfo& sinfo = ssaEntry.second;
542            VectorSet<SSAReplace>& replaces = it->second;
543            if (sinfo.readBeforeWrite)
544            {
545                auto rit = binaryMapFind(replaces.begin(), replaces.end(),
546                                 ssaEntry.second.ssaIdBefore);
547                if (rit != replaces.end())
548                    sinfo.ssaIdBefore = rit->second; // replace
549            }
550            if (sinfo.ssaIdFirst != SIZE_MAX)
551            {
552                auto rit = binaryMapFind(replaces.begin(), replaces.end(),
553                                 ssaEntry.second.ssaIdFirst);
554                if (rit != replaces.end())
555                    sinfo.ssaIdFirst = rit->second; // replace
556            }
557            if (sinfo.ssaIdLast != SIZE_MAX)
558            {
559                auto rit = binaryMapFind(replaces.begin(), replaces.end(),
560                                 ssaEntry.second.ssaIdLast);
561                if (rit != replaces.end())
562                    sinfo.ssaIdLast = rit->second; // replace
563            }
564        }
565   
566    // clear ssa replaces
567    ssaReplacesMap.clear();
568}
569
570void AsmRegAllocator::createInterferenceGraph()
571{
572    /// construct liveBlockMaps
573    std::set<LiveBlock> liveBlockMaps[MAX_REGTYPES_NUM];
574    for (size_t regType = 0; regType < regTypesNum; regType++)
575    {
576        std::set<LiveBlock>& liveBlockMap = liveBlockMaps[regType];
577        Array<OutLiveness>& liveness = outLivenesses[regType];
578        for (size_t li = 0; li < liveness.size(); li++)
579        {
580            OutLiveness& lv = liveness[li];
581            for (const std::pair<size_t, size_t>& blk: lv)
582                if (blk.first != blk.second)
583                    liveBlockMap.insert({ blk.first, blk.second, li });
584            lv.clear();
585        }
586        liveness.clear();
587    }
588   
589    // create interference graphs
590    for (size_t regType = 0; regType < regTypesNum; regType++)
591    {
592        InterGraph& interGraph = interGraphs[regType];
593        interGraph.resize(graphVregsCounts[regType]);
594        std::set<LiveBlock>& liveBlockMap = liveBlockMaps[regType];
595       
596        auto lit = liveBlockMap.begin();
597        size_t rangeStart = 0;
598        if (lit != liveBlockMap.end())
599            rangeStart = lit->start;
600        while (lit != liveBlockMap.end())
601        {
602            const size_t blkStart = lit->start;
603            const size_t blkEnd = lit->end;
604            size_t rangeEnd = blkEnd;
605            auto liStart = liveBlockMap.lower_bound({ rangeStart, 0, 0 });
606            auto liEnd = liveBlockMap.lower_bound({ rangeEnd, 0, 0 });
607            // collect from this range, variable indices
608            std::set<size_t> varIndices;
609            for (auto lit2 = liStart; lit2 != liEnd; ++lit2)
610                varIndices.insert(lit2->vidx);
611            // push to intergraph as full subgGraph
612            for (auto vit = varIndices.begin(); vit != varIndices.end(); ++vit)
613                for (auto vit2 = varIndices.begin(); vit2 != varIndices.end(); ++vit2)
614                    if (vit != vit2)
615                        interGraph[*vit].insert(*vit2);
616            // go to next live blocks
617            rangeStart = rangeEnd;
618            for (; lit != liveBlockMap.end(); ++lit)
619                if (lit->start != blkStart && lit->end != blkEnd)
620                    break;
621            if (lit == liveBlockMap.end())
622                break; //
623            rangeStart = std::max(rangeStart, lit->start);
624        }
625    }
626}
627
628/* algorithm to allocate regranges:
629 * from smallest regranges to greatest regranges:
630 *   choosing free register: from smallest free regranges
631 *      to greatest regranges:
632 *         in this same regrange:
633 *               try to find free regs in regranges
634 *               try to link free ends of two distinct regranges
635 */
636
637void AsmRegAllocator::colorInterferenceGraph()
638{
639    const GPUArchitecture arch = getGPUArchitectureFromDeviceType(
640                    assembler.deviceType);
641   
642    for (size_t regType = 0; regType < regTypesNum; regType++)
643    {
644        const size_t maxColorsNum = getGPUMaxRegistersNum(arch, regType);
645        InterGraph& interGraph = interGraphs[regType];
646        const VarIndexMap& vregIndexMap = vregIndexMaps[regType];
647        Array<cxuint>& gcMap = graphColorMaps[regType];
648       
649        const size_t nodesNum = interGraph.size();
650        gcMap.resize(nodesNum);
651        std::fill(gcMap.begin(), gcMap.end(), cxuint(UINT_MAX));
652        Array<size_t> sdoCounts(nodesNum);
653        std::fill(sdoCounts.begin(), sdoCounts.end(), 0);
654       
655        SDOLDOCompare compare(interGraph, sdoCounts);
656        std::set<size_t, SDOLDOCompare> nodeSet(compare);
657        for (size_t i = 0; i < nodesNum; i++)
658            nodeSet.insert(i);
659       
660        cxuint colorsNum = 0;
661        // firstly, allocate real registers
662        for (const auto& entry: vregIndexMap)
663            if (entry.first.regVar == nullptr)
664                gcMap[entry.second[0]] = colorsNum++;
665       
666        for (size_t colored = 0; colored < nodesNum; colored++)
667        {
668            size_t node = *nodeSet.begin();
669            if (gcMap[node] != UINT_MAX)
670                continue; // already colored
671            size_t color = 0;
672           
673            for (color = 0; color <= colorsNum; color++)
674            {
675                // find first usable color
676                bool thisSame = false;
677                for (size_t nb: interGraph[node])
678                    if (gcMap[nb] == color)
679                    {
680                        thisSame = true;
681                        break;
682                    }
683                if (!thisSame)
684                    break;
685            }
686            if (color==colorsNum) // add new color if needed
687            {
688                if (colorsNum >= maxColorsNum)
689                    throw AsmException("Too many register is needed");
690                colorsNum++;
691            }
692           
693            gcMap[node] = color;
694            // update SDO for node
695            bool colorExists = false;
696            for (size_t nb: interGraph[node])
697                if (gcMap[nb] == color)
698                {
699                    colorExists = true;
700                    break;
701                }
702            if (!colorExists)
703                sdoCounts[node]++;
704            // update SDO for neighbors
705            for (size_t nb: interGraph[node])
706            {
707                colorExists = false;
708                for (size_t nb2: interGraph[nb])
709                    if (gcMap[nb2] == color)
710                    {
711                        colorExists = true;
712                        break;
713                    }
714                if (!colorExists)
715                {
716                    if (gcMap[nb] == UINT_MAX)
717                        nodeSet.erase(nb);  // before update we erase from nodeSet
718                    sdoCounts[nb]++;
719                    if (gcMap[nb] == UINT_MAX)
720                        nodeSet.insert(nb); // after update, insert again
721                }
722            }
723           
724            gcMap[node] = color;
725        }
726    }
727}
728
729void AsmRegAllocator::allocateRegisters(AsmSectionId sectionId)
730{
731    // before any operation, clear all
732    codeBlocks.clear();
733    for (size_t i = 0; i < MAX_REGTYPES_NUM; i++)
734    {
735        graphVregsCounts[i] = 0;
736        vregIndexMaps[i].clear();
737        interGraphs[i].clear();
738        linearDepMaps[i].clear();
739        graphColorMaps[i].clear();
740    }
741    ssaReplacesMap.clear();
742    cxuint maxRegs[MAX_REGTYPES_NUM];
743    assembler.isaAssembler->getMaxRegistersNum(regTypesNum, maxRegs);
744   
745    // set up
746    const AsmSection& section = assembler.sections[sectionId];
747    createCodeStructure(section.codeFlow, section.content.size(), section.content.data());
748    createSSAData(*section.usageHandler, *section.linearDepHandler);
749    applySSAReplaces();
750    createLivenesses(*section.usageHandler, *section.linearDepHandler);
751    createInterferenceGraph();
752    colorInterferenceGraph();
753}
Note: See TracBrowser for help on using the repository browser.