source: CLRX/CLRadeonExtender/trunk/amdasm/AsmRegAllocLive.cpp @ 4167

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

CLRadeonExtender: AsmRegAlloc?: Comment code. remove obsolete a commented code.

File size: 66.6 KB
Line 
1/*
2 *  CLRadeonExtender - Unofficial OpenCL Radeon Extensions Library
3 *  Copyright (C) 2014-2018 Mateusz Szpakowski
4 *
5 *  This library is free software; you can redistribute it and/or
6 *  modify it under the terms of the GNU Lesser General Public
7 *  License as published by the Free Software Foundation; either
8 *  version 2.1 of the License, or (at your option) any later version.
9 *
10 *  This library is distributed in the hope that it will be useful,
11 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
12 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
13 *  Lesser General Public License for more details.
14 *
15 *  You should have received a copy of the GNU Lesser General Public
16 *  License along with this library; if not, write to the Free Software
17 *  Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
18 */
19
20#include <CLRX/Config.h>
21#include <assert.h>
22#include <iostream>
23#include <stack>
24#include <deque>
25#include <vector>
26#include <utility>
27#include <unordered_set>
28#include <map>
29#include <set>
30#include <unordered_map>
31#include <algorithm>
32#include <CLRX/utils/Utilities.h>
33#include <CLRX/utils/Containers.h>
34#include <CLRX/amdasm/Assembler.h>
35#include "AsmInternals.h"
36#include "AsmRegAlloc.h"
37
38using namespace CLRX;
39
40/*********
41 * createLivenesses stuff
42 *********/
43
44static cxuint getRegType(size_t regTypesNum, const cxuint* regRanges,
45            const AsmSingleVReg& svreg)
46{
47    cxuint regType; // regtype
48    if (svreg.regVar!=nullptr)
49        regType = svreg.regVar->type;
50    else
51        for (regType = 0; regType < regTypesNum; regType++)
52            if (svreg.index >= regRanges[regType<<1] &&
53                svreg.index < regRanges[(regType<<1)+1])
54                break;
55    return regType;
56}
57
58static void getVIdx(const AsmSingleVReg& svreg, size_t ssaIdIdx,
59        const AsmRegAllocator::SSAInfo& ssaInfo,
60        const VarIndexMap* vregIndexMaps, size_t regTypesNum, const cxuint* regRanges,
61        cxuint& regType, size_t& vidx)
62{
63    size_t ssaId;
64    if (svreg.regVar==nullptr)
65        ssaId = 0;
66    else if (ssaIdIdx==0)
67        ssaId = ssaInfo.ssaIdBefore;
68    else if (ssaIdIdx==1)
69        ssaId = ssaInfo.ssaIdFirst;
70    else if (ssaIdIdx<ssaInfo.ssaIdChange)
71        ssaId = ssaInfo.ssaId + ssaIdIdx-1;
72    else // last
73        ssaId = ssaInfo.ssaIdLast;
74   
75    regType = getRegType(regTypesNum, regRanges, svreg); // regtype
76    const VarIndexMap& vregIndexMap = vregIndexMaps[regType];
77    const std::vector<size_t>& vidxes = vregIndexMap.find(svreg)->second;
78    /*ARDOut << "lvn[" << regType << "][" << vidxes[ssaId] << "]. ssaIdIdx: " <<
79            ssaIdIdx << ". ssaId: " << ssaId << ". svreg: " << svreg.regVar << ":" <<
80            svreg.index << "\n";*/
81    //return livenesses[regType][ssaIdIndices[ssaId]];
82    vidx = vidxes[ssaId];
83}
84
85static inline Liveness& getLiveness(const AsmSingleVReg& svreg, size_t ssaIdIdx,
86        const AsmRegAllocator::SSAInfo& ssaInfo, std::vector<Liveness>* livenesses,
87        const VarIndexMap* vregIndexMaps, size_t regTypesNum, const cxuint* regRanges)
88{
89    cxuint regType;
90    size_t vidx;
91    getVIdx(svreg, ssaIdIdx, ssaInfo, vregIndexMaps, regTypesNum, regRanges,
92            regType, vidx);
93    return livenesses[regType][vidx];
94}
95
96static void getVIdx2(const AsmSingleVReg& svreg, size_t ssaId,
97        const VarIndexMap* vregIndexMaps, size_t regTypesNum, const cxuint* regRanges,
98        cxuint& regType, size_t& vidx)
99{
100    regType = getRegType(regTypesNum, regRanges, svreg); // regtype
101    const VarIndexMap& vregIndexMap = vregIndexMaps[regType];
102    const std::vector<size_t>& vidxes = vregIndexMap.find(svreg)->second;
103    /*ARDOut << "lvn[" << regType << "][" << vidxes[ssaId] << "]. ssaId: " <<
104            ssaId << ". svreg: " << svreg.regVar << ":" << svreg.index << "\n";*/
105    vidx = vidxes[ssaId];
106}
107
108
109static void addVIdxToCallEntry(size_t blockIndex, cxuint regType, size_t vidx,
110            const std::vector<CodeBlock>& codeBlocks,
111            std::unordered_map<size_t, VIdxSetEntry>& vidxCallMap,
112            const std::unordered_map<size_t, VIdxSetEntry>& vidxRoutineMap)
113{
114    const CodeBlock& cblock = codeBlocks[blockIndex];
115    if (cblock.haveCalls)
116    {
117        VIdxSetEntry& varCallEntry = vidxCallMap[blockIndex];
118        for (const NextBlock& next: cblock.nexts)
119            if (next.isCall)
120            {
121                auto vidxRIt = vidxRoutineMap.find(next.block);
122                if (vidxRIt == vidxRoutineMap.end())
123                    continue;
124                const auto& allLvs = vidxRIt->second;
125                if (allLvs.vs[regType].find(vidx) == allLvs.vs[regType].end())
126                    // add callLiveTime only if vreg not present in routine
127                    varCallEntry.vs[regType].insert(vidx);
128            }
129    }
130}
131
132static void fillUpInsideRoutine(const std::vector<CodeBlock>& codeBlocks,
133            std::unordered_map<size_t, VIdxSetEntry>& vidxCallMap,
134            const std::unordered_map<size_t, VIdxSetEntry>& vidxRoutineMap,
135            size_t startBlock, size_t routineBlock, const AsmSingleVReg& svreg,
136            Liveness& lv, cxuint lvRType /* lv register type */, size_t vidx,
137            size_t ssaId, const RoutineDataLv& rdata,
138            std::unordered_set<size_t>& havePathBlocks)
139{
140    const std::unordered_set<size_t>& haveReturnBlocks = rdata.haveReturnBlocks;
141    std::deque<FlowStackEntry3> flowStack;
142    std::unordered_set<size_t> visited;
143   
144    flowStack.push_back({ startBlock, 0 });
145   
146    size_t startSSAId = ssaId;
147    bool fromStartPos = false;
148    // determine first SSAId and whether filling should begin from start of the routine
149    if (routineBlock == startBlock)
150    {
151        const CodeBlock& cblock = codeBlocks[startBlock];
152        auto sinfoIt = cblock.ssaInfoMap.find(svreg);
153        auto rbwIt = rdata.rbwSSAIdMap.find(svreg);
154        if (sinfoIt != cblock.ssaInfoMap.end())
155        {
156            const SSAInfo& sinfo = sinfoIt->second;
157            if (sinfo.readBeforeWrite && sinfo.ssaIdBefore==ssaId)
158                // if ssaId is first read, then we assume start at routine start pos
159                fromStartPos = true;
160            else if (sinfo.ssaIdChange == 0 || sinfo.ssaIdLast != ssaId)
161                // do nothing (last SSAId doesnt match or no change
162                return;
163        }
164        else if (rbwIt != rdata.rbwSSAIdMap.end())
165        {
166            fromStartPos = true;
167            startSSAId = rbwIt->second;
168        }
169        else
170            return; // do nothing
171    }
172    if (startSSAId != ssaId)
173        return; // also, do nothing
174   
175    while (!flowStack.empty())
176    {
177        FlowStackEntry3& entry = flowStack.back();
178        const CodeBlock& cblock = codeBlocks[entry.blockIndex.index];
179       
180        bool endOfPath = false;
181        if (entry.nextIndex == 0)
182        {
183            if (visited.insert(entry.blockIndex.index).second &&
184                haveReturnBlocks.find(entry.blockIndex.index) != haveReturnBlocks.end())
185            {
186                auto sinfoIt = cblock.ssaInfoMap.find(svreg);
187                if (flowStack.size() > 1 && sinfoIt != cblock.ssaInfoMap.end())
188                {
189                    if (!sinfoIt->second.readBeforeWrite)
190                    {
191                        // no read before write skip this path
192                        flowStack.pop_back();
193                        continue;
194                    }
195                    else
196                        // we end path at first read
197                        endOfPath = true;
198                }
199            }
200            else
201            {
202                const bool prevPath = havePathBlocks.find(entry.blockIndex.index) !=
203                        havePathBlocks.end();
204                flowStack.pop_back();
205                // propagate haveReturn to previous block
206                if (prevPath)
207                {
208                    flowStack.back().havePath = true;
209                    havePathBlocks.insert(flowStack.back().blockIndex.index);
210                }
211                continue;
212            }
213        }
214       
215        // skip calls
216        if (!endOfPath)
217            for (; entry.nextIndex < cblock.nexts.size() &&
218                    cblock.nexts[entry.nextIndex].isCall; entry.nextIndex++);
219       
220        if (!endOfPath && entry.nextIndex < cblock.nexts.size())
221        {
222            flowStack.push_back({ cblock.nexts[entry.nextIndex].block, 0 });
223            entry.nextIndex++;
224        }
225        else if (!endOfPath &&
226            ((entry.nextIndex==0 && cblock.nexts.empty()) ||
227                // if have any call then go to next block
228                (cblock.haveCalls && entry.nextIndex==cblock.nexts.size())) &&
229                 !cblock.haveReturn && !cblock.haveEnd)
230        {
231            flowStack.push_back({ entry.blockIndex+1, 0 });
232            entry.nextIndex++;
233        }
234        else
235        {
236            if (endOfPath || cblock.haveReturn)
237            {
238                havePathBlocks.insert(entry.blockIndex.index);
239                // we have path only if have return and if have path
240                entry.havePath = true;
241            }
242           
243            const bool curHavePath = entry.havePath;
244            if (curHavePath)
245            {
246                // fill up block when in path
247                auto sinfoIt = cblock.ssaInfoMap.find(svreg);
248                size_t cbStart = cblock.start;
249                size_t cbEnd = cblock.end;
250                if (flowStack.size() == 1 && !fromStartPos)
251                {
252                    // if first block, then get last occurrence in this path
253                    if (sinfoIt != cblock.ssaInfoMap.end())
254                        cbStart = sinfoIt->second.lastPos+1;
255                }
256                if (endOfPath && sinfoIt != cblock.ssaInfoMap.end())
257                    cbEnd = sinfoIt->second.firstPos+1;
258                // fill up block
259                lv.insert(cbStart, cbEnd);
260                if (cblock.end == cbEnd)
261                    addVIdxToCallEntry(entry.blockIndex.index, lvRType, vidx,
262                            codeBlocks, vidxCallMap, vidxRoutineMap);
263            }
264           
265            // back
266            flowStack.pop_back();
267            // propagate havePath
268            if (!flowStack.empty())
269            {
270                if (curHavePath)
271                    havePathBlocks.insert(flowStack.back().blockIndex.index);
272                flowStack.back().havePath |= curHavePath;
273            }
274        }
275    }
276}
277
278static void joinVRegRecur(const std::deque<FlowStackEntry3>& flowStack,
279            const std::vector<CodeBlock>& codeBlocks, const RoutineLvMap& routineMap,
280            std::unordered_map<size_t, VIdxSetEntry>& vidxCallMap,
281            const std::unordered_map<size_t, VIdxSetEntry>& vidxRoutineMap,
282            LastVRegStackPos flowStkStart, const AsmSingleVReg& svreg, size_t ssaId,
283            const VarIndexMap* vregIndexMaps, std::vector<Liveness>* livenesses,
284            size_t regTypesNum, const cxuint* regRanges, bool skipLastBlock = false)
285{
286    struct JoinEntry
287    {
288        size_t blockIndex; // block index where is call
289        size_t nextIndex; // next index of routine call
290        size_t lastAccessIndex; // last access pos index
291        bool inSubroutines;
292        size_t routineBlock;
293        const RoutineDataLv* rdata;
294    };
295   
296    std::unordered_set<size_t> havePathBlocks;
297   
298    FlowStackCIter flitEnd = flowStack.end();
299    if (skipLastBlock)
300        --flitEnd; // before last element
301    cxuint lvRegType;
302    size_t vidx;
303    getVIdx2(svreg, ssaId, vregIndexMaps, regTypesNum, regRanges, lvRegType, vidx);
304    Liveness& lv = livenesses[lvRegType][vidx];
305   
306    std::stack<JoinEntry> rjStack; // routine join stack
307    if (flowStkStart.inSubroutines)
308        rjStack.push({ flowStack[flowStkStart.stackPos].blockIndex.index,
309                            0, 0, true, SIZE_MAX, nullptr });
310   
311    while (!rjStack.empty())
312    {
313        JoinEntry& entry = rjStack.top();
314        const CodeBlock& cblock = codeBlocks[entry.blockIndex];
315       
316        if (entry.inSubroutines && entry.nextIndex < cblock.nexts.size())
317        {
318            bool doNextIndex = false; // true if to next call
319            if (cblock.nexts[entry.nextIndex].isCall)
320            {
321                const size_t routineBlock = cblock.nexts[entry.nextIndex].block;
322                const RoutineDataLv& rdata =
323                        routineMap.find(routineBlock)->second;
324                auto lastAccessIt = rdata.lastAccessMap.find(svreg);
325                if (lastAccessIt != rdata.lastAccessMap.end())
326                {
327                    if (entry.lastAccessIndex < lastAccessIt->second.size())
328                    {
329                        // we have new path in subroutine to fill
330                        const auto& lastAccess =
331                                lastAccessIt->second[entry.lastAccessIndex];
332                        rjStack.push({ lastAccess.blockIndex, 0, 0,
333                                lastAccess.inSubroutines, routineBlock, &rdata });
334                        entry.lastAccessIndex++;
335                        if (entry.lastAccessIndex == lastAccessIt->second.size())
336                            doNextIndex = true;
337                    }
338                    else
339                        doNextIndex = true;
340                }
341                else
342                    doNextIndex = true;
343            }
344            else
345                doNextIndex = true;
346           
347            if (doNextIndex)
348            {
349                // to next call
350                entry.nextIndex++;
351                entry.lastAccessIndex = 0;
352            }
353        }
354        else
355        {
356            // fill up next block in path (do not fill start block)
357            /* if inSubroutines, then first block
358             * (that with subroutines calls) will be skipped */
359            if (rjStack.size() > 1)
360                fillUpInsideRoutine(codeBlocks, vidxCallMap, vidxRoutineMap,
361                        entry.blockIndex + (entry.inSubroutines),
362                        entry.routineBlock, svreg, lv, lvRegType, vidx, ssaId,
363                        *entry.rdata, havePathBlocks);
364            rjStack.pop();
365        }
366    }
367   
368    auto flit = flowStack.begin() + flowStkStart.stackPos;
369    // applyVIdx to call entry (if needed, and if some join inside subroutines)
370    // resolve this vidx before these call point and if nexts>1
371    if (flowStkStart.inSubroutines &&
372        lv.contain(codeBlocks[flit->blockIndex.index].end-1) &&
373        codeBlocks[flit->blockIndex.index].nexts.size() > 1)
374        // just apply, only if join before call
375        addVIdxToCallEntry(flit->blockIndex.index, lvRegType, vidx,
376                    codeBlocks, vidxCallMap, vidxRoutineMap);
377   
378    if (flowStkStart.inSubroutines)
379        ++flit; // skip this codeblock before call
380   
381    const CodeBlock& lastBlk = codeBlocks[flit->blockIndex.index];
382    if (flit != flitEnd)
383    {
384        auto sinfoIt = lastBlk.ssaInfoMap.find(svreg);
385        size_t lastPos = lastBlk.start;
386        if (sinfoIt != lastBlk.ssaInfoMap.end())
387        {
388            if (flit->nextIndex > lastBlk.nexts.size())
389                // only if pass this routine
390                addVIdxToCallEntry(flit->blockIndex.index, lvRegType, vidx,
391                        codeBlocks, vidxCallMap, vidxRoutineMap);
392            // if begin at some point at last block
393            lastPos = sinfoIt->second.lastPos;
394            lv.insert(lastPos + 1, lastBlk.end);
395            ++flit; // skip last block in stack
396        }
397    }
398    // fill up to this
399    for (; flit != flitEnd; ++flit)
400    {
401        const CodeBlock& cblock = codeBlocks[flit->blockIndex.index];
402        if (flit->nextIndex > cblock.nexts.size())
403            // only if pass this routine
404            addVIdxToCallEntry(flit->blockIndex.index, lvRegType, vidx, codeBlocks,
405                        vidxCallMap, vidxRoutineMap);
406        lv.insert(cblock.start, cblock.end);
407    }
408}
409
410/* handle many start points in this code (for example many kernel's in same code)
411 * replace sets by vector, and sort and remove same values on demand
412 */
413
414/* join livenesses between consecutive code blocks */
415static void putCrossBlockLivenesses(const std::deque<FlowStackEntry3>& flowStack,
416        const std::vector<CodeBlock>& codeBlocks, const RoutineLvMap& routineMap,
417        std::unordered_map<size_t, VIdxSetEntry>& vidxCallMap,
418        const std::unordered_map<size_t, VIdxSetEntry>& vidxRoutineMap,
419        const LastVRegMap& lastVRegMap, std::vector<Liveness>* livenesses,
420        const VarIndexMap* vregIndexMaps, size_t regTypesNum, const cxuint* regRanges)
421{
422    ARDOut << "putCrossBlockLv block: " << flowStack.back().blockIndex << "\n";
423    const CodeBlock& cblock = codeBlocks[flowStack.back().blockIndex.index];
424    for (const auto& entry: cblock.ssaInfoMap)
425        if (entry.second.readBeforeWrite)
426        {
427            // find last
428            auto lvrit = lastVRegMap.find(entry.first);
429            LastVRegStackPos flowStackStart = (lvrit != lastVRegMap.end()) ?
430                lvrit->second.back() : LastVRegStackPos{ 0, false };
431           
432            joinVRegRecur(flowStack, codeBlocks, routineMap, vidxCallMap, vidxRoutineMap,
433                    flowStackStart, entry.first, entry.second.ssaIdBefore,
434                    vregIndexMaps, livenesses, regTypesNum, regRanges, true);
435        }
436}
437
438// add new join second cache entry with readBeforeWrite for all encountered regvars
439static void addJoinSecCacheEntry(const RoutineLvMap& routineMap,
440                const std::vector<CodeBlock>& codeBlocks,
441                SimpleCache<size_t, SVRegMap>& joinSecondPointsCache,
442                size_t nextBlock)
443{
444    ARDOut << "addJoinSecCacheEntry: " << nextBlock << "\n";
445    //std::stack<CallStackEntry> callStack = prevCallStack;
446    // traverse by graph from next block
447    std::deque<FlowStackEntry3> flowStack;
448    flowStack.push_back({ nextBlock, 0 });
449    std::unordered_set<size_t> visited;
450   
451    // already read in current path
452    // key - vreg, value - source block where vreg of conflict found
453    SVRegBlockMap alreadyReadMap;
454    SVRegMap cacheSecPoints;
455   
456    while (!flowStack.empty())
457    {
458        FlowStackEntry3& entry = flowStack.back();
459        const CodeBlock& cblock = codeBlocks[entry.blockIndex.index];
460       
461        if (entry.nextIndex == 0)
462        {
463            // process current block
464            if (visited.insert(entry.blockIndex.index).second)
465            {
466                ARDOut << "  resolv (cache): " << entry.blockIndex << "\n";
467               
468                const SVRegMap* resSecondPoints =
469                            joinSecondPointsCache.use(entry.blockIndex.index);
470                if (resSecondPoints == nullptr)
471                {
472                    // if joinSecondPointCache not found
473                    for (auto& sentry: cblock.ssaInfoMap)
474                    {
475                        const SSAInfo& sinfo = sentry.second;
476                        auto res = alreadyReadMap.insert(
477                                    { sentry.first, entry.blockIndex });
478                       
479                        if (res.second && sinfo.readBeforeWrite)
480                            cacheSecPoints[sentry.first] = sinfo.ssaIdBefore;
481                    }
482                }
483                else // to use cache
484                {
485                    // add to current cache sec points
486                    for (const auto& rsentry: *resSecondPoints)
487                    {
488                        const bool alreadyRead =
489                            alreadyReadMap.find(rsentry.first) != alreadyReadMap.end();
490                        if (!alreadyRead)
491                            cacheSecPoints[rsentry.first] = rsentry.second;
492                    }
493                    flowStack.pop_back();
494                    continue;
495                }
496            }
497            else
498            {
499                // back, already visited
500                ARDOut << "join already (cache): " << entry.blockIndex << "\n";
501                flowStack.pop_back();
502                continue;
503            }
504        }
505       
506        if (entry.nextIndex < cblock.nexts.size())
507        {
508            flowStack.push_back({ cblock.nexts[entry.nextIndex].block, 0 });
509            entry.nextIndex++;
510        }
511        else if (((entry.nextIndex==0 && cblock.nexts.empty()) ||
512                // if have any call then go to next block
513                (cblock.haveCalls && entry.nextIndex==cblock.nexts.size())) &&
514                 !cblock.haveReturn && !cblock.haveEnd)
515        {
516            // add alreadyReadMap ssaIds inside called routines
517            for (const auto& next: cblock.nexts)
518                if (next.isCall)
519                {
520                    const RoutineDataLv& rdata = routineMap.find(next.block)->second;
521                    for (const auto& v: rdata.rbwSSAIdMap)
522                        alreadyReadMap.insert({v.first, entry.blockIndex });
523                    for (const auto& v: rdata.lastAccessMap)
524                        alreadyReadMap.insert({v.first, entry.blockIndex });
525                }
526           
527            flowStack.push_back({ entry.blockIndex+1, 0 });
528            entry.nextIndex++;
529        }
530        else // back
531        {
532            // remove old to resolve in leaved way to allow collecting next ssaId
533            // before write (can be different due to earlier visit)
534            for (const auto& next: cblock.nexts)
535                if (next.isCall)
536                {
537                    const RoutineDataLv& rdata = routineMap.find(next.block)->second;
538                    for (const auto& v: rdata.rbwSSAIdMap)
539                    {
540                        auto it = alreadyReadMap.find(v.first);
541                        if (it != alreadyReadMap.end() && it->second == entry.blockIndex)
542                            alreadyReadMap.erase(it);
543                    }
544                    for (const auto& v: rdata.lastAccessMap)
545                    {
546                        auto it = alreadyReadMap.find(v.first);
547                        if (it != alreadyReadMap.end() && it->second == entry.blockIndex)
548                            alreadyReadMap.erase(it);
549                    }
550                }
551           
552            for (const auto& sentry: cblock.ssaInfoMap)
553            {
554                auto it = alreadyReadMap.find(sentry.first);
555                if (it != alreadyReadMap.end() && it->second == entry.blockIndex)
556                    // remove old to resolve in leaved way to allow collecting next ssaId
557                    // before write (can be different due to earlier visit)
558                    alreadyReadMap.erase(it);
559            }
560            ARDOut << "  popjoin (cache)\n";
561            flowStack.pop_back();
562        }
563    }
564   
565    joinSecondPointsCache.put(nextBlock, cacheSecPoints);
566}
567
568// apply calls (changes from these calls) from code blocks to stack var map
569static void applyCallToStackVarMap(const CodeBlock& cblock, const RoutineLvMap& routineMap,
570        LastStackPosMap& stackVarMap, size_t pfPos, size_t nextIndex)
571{
572    for (const NextBlock& next: cblock.nexts)
573        if (next.isCall)
574        {
575            ARDOut << "  japplycall: " << pfPos << ": " <<
576                    nextIndex << ": " << next.block << "\n";
577            const LastAccessMap& regVarMap =
578                    routineMap.find(next.block)->second.lastAccessMap;
579            for (const auto& sentry: regVarMap)
580            {
581                // MSVC error fix
582                auto& v = stackVarMap[sentry.first];
583                v = LastVRegStackPos{ pfPos, true };
584            }
585        }
586}
587
588static void joinRegVarLivenesses(const std::deque<FlowStackEntry3>& prevFlowStack,
589        const std::vector<CodeBlock>& codeBlocks, const RoutineLvMap& routineMap,
590        std::unordered_map<size_t, VIdxSetEntry>& vidxCallMap,
591        const std::unordered_map<size_t, VIdxSetEntry>& vidxRoutineMap,
592        const PrevWaysIndexMap& prevWaysIndexMap,
593        const std::vector<bool>& waysToCache, ResSecondPointsToCache& cblocksToCache,
594        SimpleCache<size_t, LastStackPosMap>& joinFirstPointsCache,
595        SimpleCache<size_t, SVRegMap>& joinSecondPointsCache,
596        const VarIndexMap* vregIndexMaps,
597        std::vector<Liveness>* livenesses, size_t regTypesNum, const cxuint* regRanges)
598{
599    size_t nextBlock = prevFlowStack.back().blockIndex.index;
600    auto pfEnd = prevFlowStack.end();
601    --pfEnd;
602    ARDOut << "startJoinLv: " << (pfEnd-1)->blockIndex << "," << nextBlock << "\n";
603    // key - varreg, value - last position in previous flowStack
604    LastStackPosMap stackVarMap;
605   
606    size_t pfStartIndex = 0;
607    {
608        auto pfPrev = pfEnd;
609        --pfPrev;
610        auto it = prevWaysIndexMap.find(pfPrev->blockIndex.index);
611        if (it != prevWaysIndexMap.end())
612        {
613            const LastStackPosMap* cached = joinFirstPointsCache.use(it->second.first);
614            if (cached!=nullptr)
615            {
616                ARDOut << "use pfcached: " << it->second.first << ", " <<
617                        it->second.second << "\n";
618                stackVarMap = *cached;
619                pfStartIndex = it->second.second+1;
620               
621                // apply missing calls at end of the cached
622                const CodeBlock& cblock = codeBlocks[it->second.first];
623               
624                const FlowStackEntry3& entry = *(prevFlowStack.begin()+pfStartIndex-1);
625                if (entry.nextIndex > cblock.nexts.size())
626                    applyCallToStackVarMap(cblock, routineMap, stackVarMap,
627                                    pfStartIndex-1, -1);
628            }
629        }
630    }
631   
632    // collect previous svreg from current path
633    for (auto pfit = prevFlowStack.begin()+pfStartIndex; pfit != pfEnd; ++pfit)
634    {
635        const FlowStackEntry3& entry = *pfit;
636        const CodeBlock& cblock = codeBlocks[entry.blockIndex.index];
637        for (const auto& sentry: cblock.ssaInfoMap)
638        {
639            // MSVC error fix
640            auto& v = stackVarMap[sentry.first];
641            v = { size_t(pfit - prevFlowStack.begin()), false };
642        }
643       
644        if (entry.nextIndex > cblock.nexts.size())
645            applyCallToStackVarMap(cblock, routineMap, stackVarMap,
646                        pfit - prevFlowStack.begin(), entry.nextIndex);
647       
648        // put to first point cache
649        if (waysToCache[pfit->blockIndex.index] &&
650            !joinFirstPointsCache.hasKey(pfit->blockIndex.index))
651        {
652            ARDOut << "put pfcache " << pfit->blockIndex << "\n";
653            joinFirstPointsCache.put(pfit->blockIndex.index, stackVarMap);
654        }
655    }
656   
657    SVRegMap cacheSecPoints;
658    const bool toCache = (!joinSecondPointsCache.hasKey(nextBlock)) &&
659                cblocksToCache.count(nextBlock)>=2;
660   
661    // traverse by graph from next block
662    std::deque<FlowStackEntry3> flowStack;
663    flowStack.push_back({ nextBlock, 0 });
664    std::vector<bool> visited(codeBlocks.size(), false);
665   
666    // already read in current path
667    // key - vreg, value - source block where vreg of conflict found
668    SVRegMap alreadyReadMap;
669   
670    while (!flowStack.empty())
671    {
672        FlowStackEntry3& entry = flowStack.back();
673        const CodeBlock& cblock = codeBlocks[entry.blockIndex.index];
674       
675        if (entry.nextIndex == 0)
676        {
677            // process current block
678            if (!visited[entry.blockIndex.index])
679            {
680                visited[entry.blockIndex.index] = true;
681                ARDOut << "  lvjoin: " << entry.blockIndex << "\n";
682               
683                const SVRegMap* joinSecondPoints =
684                        joinSecondPointsCache.use(entry.blockIndex.index);
685               
686                if (joinSecondPoints == nullptr)
687                    for (const auto& sentry: cblock.ssaInfoMap)
688                    {
689                        const SSAInfo& sinfo = sentry.second;
690                        auto res = alreadyReadMap.insert(
691                                    { sentry.first, entry.blockIndex.index });
692                       
693                        if (toCache)
694                            cacheSecPoints[sentry.first] = sinfo.ssaIdBefore;
695                       
696                        if (res.second && sinfo.readBeforeWrite)
697                        {
698                            auto it = stackVarMap.find(sentry.first);
699                            LastVRegStackPos stackPos = (it != stackVarMap.end() ?
700                                        it->second : LastVRegStackPos{ 0, false });
701                           
702                            joinVRegRecur(prevFlowStack, codeBlocks, routineMap,
703                                vidxCallMap, vidxRoutineMap,
704                                stackPos, sentry.first, sentry.second.ssaIdBefore,
705                                vregIndexMaps, livenesses, regTypesNum, regRanges, true);
706                        }
707                    }
708                else
709                {
710                    ARDOut << "use join secPointCache: " << entry.blockIndex << "\n";
711                    // add to current cache sec points
712                    for (const auto& rsentry: *joinSecondPoints)
713                    {
714                        const bool alreadyRead =
715                            alreadyReadMap.find(rsentry.first) != alreadyReadMap.end();
716                       
717                        if (!alreadyRead)
718                        {
719                            if (toCache)
720                                cacheSecPoints[rsentry.first] = rsentry.second;
721                           
722                            auto it = stackVarMap.find(rsentry.first);
723                            LastVRegStackPos stackPos = (it != stackVarMap.end() ?
724                                        it->second : LastVRegStackPos{ 0, false });
725                           
726                            joinVRegRecur(prevFlowStack, codeBlocks, routineMap,
727                                vidxCallMap, vidxRoutineMap,
728                                stackPos, rsentry.first, rsentry.second, vregIndexMaps,
729                                livenesses, regTypesNum, regRanges, true);
730                        }
731                    }
732                    flowStack.pop_back();
733                    continue;
734                }
735            }
736            else
737            {
738                cblocksToCache.increase(entry.blockIndex);
739                ARDOut << "jcblockToCache: " << entry.blockIndex << "=" <<
740                            cblocksToCache.count(entry.blockIndex) << "\n";
741                // back, already visited
742                ARDOut << "join already: " << entry.blockIndex << "\n";
743                flowStack.pop_back();
744                continue;
745            }
746        }
747       
748        if (entry.nextIndex < cblock.nexts.size())
749        {
750            flowStack.push_back({ cblock.nexts[entry.nextIndex].block, 0 });
751            entry.nextIndex++;
752        }
753        else if (((entry.nextIndex==0 && cblock.nexts.empty()) ||
754                // if have any call then go to next block
755                (cblock.haveCalls && entry.nextIndex==cblock.nexts.size())) &&
756                 !cblock.haveReturn && !cblock.haveEnd)
757        {
758            // add alreadReadMap ssaIds inside called routines
759            for (const auto& next: cblock.nexts)
760                if (next.isCall)
761                {
762                    const RoutineDataLv& rdata = routineMap.find(next.block)->second;
763                    for (const auto& v: rdata.rbwSSAIdMap)
764                        alreadyReadMap.insert({v.first, entry.blockIndex.index });
765                    for (const auto& v: rdata.lastAccessMap)
766                        alreadyReadMap.insert({v.first, entry.blockIndex.index });
767                }
768           
769            flowStack.push_back({ entry.blockIndex+1, 0 });
770            entry.nextIndex++;
771        }
772        else // back
773        {
774            // remove old to resolve in leaved way to allow collecting next ssaId
775            // before write (can be different due to earlier visit)
776            for (const auto& next: cblock.nexts)
777                if (next.isCall)
778                {
779                    const RoutineDataLv& rdata = routineMap.find(next.block)->second;
780                    for (const auto& v: rdata.rbwSSAIdMap)
781                    {
782                        auto it = alreadyReadMap.find(v.first);
783                        if (it != alreadyReadMap.end() &&
784                            it->second == entry.blockIndex.index)
785                            alreadyReadMap.erase(it);
786                    }
787                    for (const auto& v: rdata.lastAccessMap)
788                    {
789                        auto it = alreadyReadMap.find(v.first);
790                        if (it != alreadyReadMap.end() &&
791                            it->second == entry.blockIndex.index)
792                            alreadyReadMap.erase(it);
793                    }
794                }
795           
796            for (const auto& sentry: cblock.ssaInfoMap)
797            {
798                auto it = alreadyReadMap.find(sentry.first);
799                if (it != alreadyReadMap.end() && it->second == entry.blockIndex.index)
800                    // remove old to resolve in leaved way to allow collecting next ssaId
801                    // before write (can be different due to earlier visit)
802                    alreadyReadMap.erase(it);
803            }
804            ARDOut << "  popjoin\n";
805           
806            if (cblocksToCache.count(entry.blockIndex)==2 &&
807                !joinSecondPointsCache.hasKey(entry.blockIndex.index))
808                // add to cache
809                addJoinSecCacheEntry(routineMap, codeBlocks, joinSecondPointsCache,
810                            entry.blockIndex.index);
811           
812            flowStack.pop_back();
813        }
814    }
815   
816    if (toCache)
817        joinSecondPointsCache.put(nextBlock, cacheSecPoints);
818}
819
820static void addUsageDeps(const cxbyte* ldeps, cxuint rvusNum,
821            const AsmRegVarUsage* rvus, LinearDepMap* ldepsOut,
822            const VarIndexMap* vregIndexMaps, const SVRegMap& ssaIdIdxMap,
823            size_t regTypesNum, const cxuint* regRanges)
824{
825    // add linear deps
826    cxuint count = ldeps[0];
827    cxuint pos = 1;
828    cxbyte rvuAdded = 0;
829    for (cxuint i = 0; i < count; i++)
830    {
831        cxuint ccount = ldeps[pos++];
832        std::vector<size_t> vidxes;
833        cxuint regType = UINT_MAX;
834        cxbyte align = rvus[ldeps[pos]].align;
835        for (cxuint j = 0; j < ccount; j++)
836        {
837            rvuAdded |= 1U<<ldeps[pos];
838            const AsmRegVarUsage& rvu = rvus[ldeps[pos++]];
839            if (rvu.regVar == nullptr)
840                continue;
841            for (uint16_t k = rvu.rstart; k < rvu.rend; k++)
842            {
843                AsmSingleVReg svreg = {rvu.regVar, k};
844                auto sit = ssaIdIdxMap.find(svreg);
845                if (regType==UINT_MAX)
846                    regType = getRegType(regTypesNum, regRanges, svreg);
847                const VarIndexMap& vregIndexMap = vregIndexMaps[regType];
848                const std::vector<size_t>& ssaIdIndices =
849                            vregIndexMap.find(svreg)->second;
850                // push variable index
851                vidxes.push_back(ssaIdIndices[sit->second]);
852            }
853        }
854        ldepsOut[regType][vidxes[0]].align = align;
855        for (size_t k = 1; k < vidxes.size(); k++)
856        {
857            ldepsOut[regType][vidxes[k-1]].nextVidxes.insertValue(vidxes[k]);
858            ldepsOut[regType][vidxes[k]].prevVidxes.insertValue(vidxes[k-1]);
859        }
860    }
861    // add single arg linear dependencies
862    for (cxuint i = 0; i < rvusNum; i++)
863        if ((rvuAdded & (1U<<i)) == 0 && rvus[i].rstart+1<rvus[i].rend)
864        {
865            const AsmRegVarUsage& rvu = rvus[i];
866            if (rvu.regVar == nullptr)
867                continue;
868            std::vector<size_t> vidxes;
869            cxuint regType = UINT_MAX;
870            cxbyte align = rvus[i].align;
871            for (uint16_t k = rvu.rstart; k < rvu.rend; k++)
872            {
873                AsmSingleVReg svreg = {rvu.regVar, k};
874                auto sit = ssaIdIdxMap.find(svreg);
875                assert(sit != ssaIdIdxMap.end());
876                if (regType==UINT_MAX)
877                    regType = getRegType(regTypesNum, regRanges, svreg);
878                const VarIndexMap& vregIndexMap = vregIndexMaps[regType];
879                const std::vector<size_t>& ssaIdIndices =
880                            vregIndexMap.find(svreg)->second;
881                // push variable index
882                vidxes.push_back(ssaIdIndices[sit->second]);
883            }
884            ldepsOut[regType][vidxes[0]].align = align;
885            for (size_t j = 1; j < vidxes.size(); j++)
886            {
887                ldepsOut[regType][vidxes[j-1]].nextVidxes.insertValue(vidxes[j]);
888                ldepsOut[regType][vidxes[j]].prevVidxes.insertValue(vidxes[j-1]);
889            }
890        }
891}
892
893static void joinRoutineDataLv(RoutineDataLv& dest, VIdxSetEntry& destVars,
894            RoutineCurAccessMap& curSVRegMap, FlowStackEntry4& entry,
895            const RoutineDataLv& src, const VIdxSetEntry& srcVars)
896{
897    dest.rbwSSAIdMap.insert(src.rbwSSAIdMap.begin(), src.rbwSSAIdMap.end());
898    for (size_t i = 0; i < MAX_REGTYPES_NUM; i++)
899        destVars.vs[i].insert(srcVars.vs[i].begin(), srcVars.vs[i].end());
900   
901    // join source lastAccessMap with curSVRegMap
902    for (const auto& sentry: src.lastAccessMap)
903    {
904        auto res = curSVRegMap.insert({ sentry.first, { entry.blockIndex, true } });
905        if (!res.second)
906        {   // not added because is present in map
907            if (res.first->second.blockIndex != entry.blockIndex)
908                entry.prevCurSVRegMap.insert(*res.first);
909            // otherwise, it is same code block but inside routines
910            // and do not change prevCurSVRegMap for revert
911            // update entry
912            res.first->second = { entry.blockIndex, true };
913        }
914        else
915            entry.prevCurSVRegMap.insert({ sentry.first, { SIZE_MAX, true } });
916    }
917}
918
919static void createRoutineDataLv(const std::vector<CodeBlock>& codeBlocks,
920        const RoutineLvMap& routineMap, const std::unordered_set<size_t>& recurseBlocks,
921        const std::unordered_map<size_t, VIdxSetEntry>& vidxRoutineMap,
922        RoutineDataLv& rdata, VIdxSetEntry& routineVIdxes,
923        BlockIndex routineBlock, const VarIndexMap* vregIndexMaps,
924        size_t regTypesNum, const cxuint* regRanges)
925{
926    ARDOut << "--------- createRoutineDataLv(" << routineBlock << ")\n";
927    std::deque<FlowStackEntry4> flowStack;
928    std::unordered_set<size_t> visited;
929   
930    // already read in current path
931    // key - vreg, value - source block where vreg of conflict found
932    SVRegMap alreadyReadMap;
933    std::unordered_set<AsmSingleVReg> vregsNotInAllRets;
934    std::unordered_set<AsmSingleVReg> vregsInFirstReturn;
935    std::unordered_set<size_t>& haveReturnBlocks = rdata.haveReturnBlocks;
936   
937    bool notFirstReturn = false;
938    flowStack.push_back({ routineBlock.index, 0 });
939    RoutineCurAccessMap curSVRegMap; // key - svreg, value - block index
940   
941    while (!flowStack.empty())
942    {
943        FlowStackEntry4& entry = flowStack.back();
944        const CodeBlock& cblock = codeBlocks[entry.blockIndex];
945       
946        if (entry.nextIndex == 0)
947        {
948            // process current block
949            if (visited.insert(entry.blockIndex).second)
950            {
951                ARDOut << "  cpjproc: " << entry.blockIndex << "\n";
952               
953                for (const auto& sentry: cblock.ssaInfoMap)
954                {
955                    if (sentry.second.readBeforeWrite)
956                        if (alreadyReadMap.insert(
957                                    { sentry.first, entry.blockIndex }).second)
958                        {
959                            auto res = rdata.rbwSSAIdMap.insert({ sentry.first,
960                                        sentry.second.ssaIdBefore });
961                            if (res.second && notFirstReturn)
962                                // first readBeforeWrite and notFirstReturn
963                                vregsNotInAllRets.insert(sentry.first);
964                        }
965                   
966                    auto res = curSVRegMap.insert({ sentry.first,
967                        LastAccessBlockPos{ entry.blockIndex, false } });
968                    if (!res.second)
969                    {   // not added because is present in map
970                        entry.prevCurSVRegMap.insert(*res.first);
971                        res.first->second = { entry.blockIndex, false };
972                    }
973                    else
974                        entry.prevCurSVRegMap.insert(
975                                        { sentry.first, { SIZE_MAX, false } });
976                   
977                    // all SSAs
978                    const SSAInfo& sinfo = sentry.second;
979                    const AsmSingleVReg& svreg = sentry.first;
980                    cxuint regType = getRegType(regTypesNum, regRanges, svreg);
981                    const VarIndexMap& vregIndexMap = vregIndexMaps[regType];
982                    const std::vector<size_t>& vidxes =
983                                vregIndexMap.find(svreg)->second;
984                   
985                    // add SSA indices to allSSAs
986                    if (sinfo.readBeforeWrite)
987                        routineVIdxes.vs[regType].insert(vidxes[sinfo.ssaIdBefore]);
988                    if (sinfo.ssaIdChange != 0)
989                    {
990                        routineVIdxes.vs[regType].insert(vidxes[sinfo.ssaIdFirst]);
991                        for (size_t i = 1; i < sinfo.ssaIdChange-1; i++)
992                            routineVIdxes.vs[regType].insert(vidxes[sinfo.ssaId+i]);
993                        routineVIdxes.vs[regType].insert(vidxes[sinfo.ssaIdLast]);
994                    }
995                }
996            }
997            else
998            {
999                const bool prevReturn = haveReturnBlocks.find(entry.blockIndex) !=
1000                        haveReturnBlocks.end();
1001                flowStack.pop_back();
1002                // propagate haveReturn to previous block
1003                if (prevReturn)
1004                {
1005                    flowStack.back().haveReturn = true;
1006                    haveReturnBlocks.insert(flowStack.back().blockIndex);
1007                }
1008                continue;
1009            }
1010        }
1011       
1012        // join and skip calls
1013        {
1014            std::vector<size_t> calledRoutines;
1015            for (; entry.nextIndex < cblock.nexts.size() &&
1016                        cblock.nexts[entry.nextIndex].isCall; entry.nextIndex++)
1017            {
1018                BlockIndex rblock(cblock.nexts[entry.nextIndex].block, routineBlock.pass);
1019                if (rblock != routineBlock &&
1020                    recurseBlocks.find(rblock.index) == recurseBlocks.end())
1021                    calledRoutines.push_back(rblock.index);
1022            }
1023           
1024            for (size_t srcRoutBlock: calledRoutines)
1025            {
1026                auto srcRIt = routineMap.find(srcRoutBlock);
1027                if (srcRIt == routineMap.end())
1028                    continue; // skip not initialized recursion
1029                // update svregs 'not in all returns'
1030                const RoutineDataLv& srcRdata = srcRIt->second;
1031                if (notFirstReturn)
1032                    for (const auto& vrentry: srcRdata.rbwSSAIdMap)
1033                        if (rdata.rbwSSAIdMap.find(vrentry.first)==rdata.rbwSSAIdMap.end())
1034                            vregsNotInAllRets.insert(vrentry.first);
1035               
1036                joinRoutineDataLv(rdata, routineVIdxes, curSVRegMap, entry,
1037                        srcRdata, vidxRoutineMap.find(srcRoutBlock)->second);
1038            }
1039        }
1040       
1041        if (entry.nextIndex < cblock.nexts.size())
1042        {
1043            flowStack.push_back({ cblock.nexts[entry.nextIndex].block, 0 });
1044            entry.nextIndex++;
1045        }
1046        else if (((entry.nextIndex==0 && cblock.nexts.empty()) ||
1047                // if have any call then go to next block
1048                (cblock.haveCalls && entry.nextIndex==cblock.nexts.size())) &&
1049                 !cblock.haveReturn && !cblock.haveEnd)
1050        {
1051            flowStack.push_back({ entry.blockIndex+1, 0 });
1052            entry.nextIndex++;
1053        }
1054        else
1055        {
1056            if (cblock.haveReturn)
1057            {
1058                // handle return
1059                // add curSVReg access positions to lastAccessMap
1060                for (const auto& entry: curSVRegMap)
1061                {
1062                    auto res = rdata.lastAccessMap.insert({ entry.first,
1063                                    { entry.second } });
1064                    if (!res.second)
1065                        res.first->second.insertValue(entry.second);
1066                }
1067               
1068                entry.haveReturn = true;
1069                haveReturnBlocks.insert(entry.blockIndex);
1070            }
1071           
1072            // handle vidxes not in all paths (both end and returns)
1073            if (cblock.haveReturn || cblock.haveEnd)
1074            {
1075                for (const auto& entry: curSVRegMap)
1076                    if (!notFirstReturn)
1077                        // fill up vregs for first return
1078                        vregsInFirstReturn.insert(entry.first);
1079                if (notFirstReturn && cblock.haveReturn)
1080                    for (const AsmSingleVReg& vreg: vregsInFirstReturn)
1081                        if (curSVRegMap.find(vreg) == curSVRegMap.end())
1082                            // not found in this path then add to 'not in all paths'
1083                            vregsNotInAllRets.insert(vreg);
1084                notFirstReturn = true;
1085            }
1086           
1087            const bool curHaveReturn = entry.haveReturn;
1088           
1089            // revert curSVRegMap
1090            for (const auto& sentry: entry.prevCurSVRegMap)
1091                if (sentry.second.blockIndex != SIZE_MAX)
1092                    curSVRegMap.find(sentry.first)->second = sentry.second;
1093                else // no before that
1094                    curSVRegMap.erase(sentry.first);
1095           
1096            for (const auto& sentry: cblock.ssaInfoMap)
1097            {
1098                auto it = alreadyReadMap.find(sentry.first);
1099                if (it != alreadyReadMap.end() && it->second == entry.blockIndex)
1100                    // remove old to resolve in leaved way to allow collecting next ssaId
1101                    // before write (can be different due to earlier visit)
1102                    alreadyReadMap.erase(it);
1103            }
1104            ARDOut << "  popjoin\n";
1105            flowStack.pop_back();
1106            // set up haveReturn
1107            if (!flowStack.empty())
1108            {
1109                flowStack.back().haveReturn |= curHaveReturn;
1110                if (flowStack.back().haveReturn)
1111                    haveReturnBlocks.insert(flowStack.back().blockIndex);
1112            }
1113        }
1114    }
1115   
1116    // handle unused svregs in this path (from routine start) and
1117    // used other paths and have this same ssaId as at routine start.
1118    // just add to lastAccessMap svreg for start to join through all routine
1119    for (const AsmSingleVReg& svreg: vregsNotInAllRets)
1120    {
1121        auto res = rdata.lastAccessMap.insert(
1122                    { svreg, { { routineBlock.index, false } } });
1123        if (!res.second)
1124        {
1125            VectorSet<LastAccessBlockPos>& sset = res.first->second;
1126            sset.insertValue({ routineBlock.index, false });
1127        }
1128    }
1129}
1130
1131static inline void revertLastSVReg(LastVRegMap& lastVRegMap, const AsmSingleVReg& svreg)
1132{
1133    auto lvrit = lastVRegMap.find(svreg);
1134    if (lvrit != lastVRegMap.end())
1135    {
1136        std::vector<LastVRegStackPos>& lastPos = lvrit->second;
1137        lastPos.pop_back();
1138        if (lastPos.empty()) // just remove from lastVRegs
1139            lastVRegMap.erase(lvrit);
1140    }
1141}
1142
1143void AsmRegAllocator::createLivenesses(ISAUsageHandler& usageHandler)
1144{
1145    ARDOut << "----- createLivenesses ------\n";
1146    // construct var index maps
1147    cxuint regRanges[MAX_REGTYPES_NUM*2];
1148    std::fill(graphVregsCounts, graphVregsCounts+MAX_REGTYPES_NUM, size_t(0));
1149    size_t regTypesNum;
1150    assembler.isaAssembler->getRegisterRanges(regTypesNum, regRanges);
1151   
1152    for (const CodeBlock& cblock: codeBlocks)
1153        for (const auto& entry: cblock.ssaInfoMap)
1154        {
1155            const SSAInfo& sinfo = entry.second;
1156            cxuint regType = getRegType(regTypesNum, regRanges, entry.first);
1157            VarIndexMap& vregIndices = vregIndexMaps[regType];
1158            size_t& graphVregsCount = graphVregsCounts[regType];
1159            std::vector<size_t>& vidxes = vregIndices[entry.first];
1160            size_t ssaIdCount = 0;
1161            if (sinfo.readBeforeWrite)
1162                ssaIdCount = sinfo.ssaIdBefore+1;
1163            if (sinfo.ssaIdChange!=0)
1164            {
1165                ssaIdCount = std::max(ssaIdCount, sinfo.ssaIdLast+1);
1166                ssaIdCount = std::max(ssaIdCount, sinfo.ssaId+sinfo.ssaIdChange-1);
1167                ssaIdCount = std::max(ssaIdCount, sinfo.ssaIdFirst+1);
1168            }
1169            // if not readBeforeWrite and neither ssaIdChanges but it is write to
1170            // normal register
1171            if (entry.first.regVar==nullptr)
1172                ssaIdCount = 1;
1173           
1174            if (vidxes.size() < ssaIdCount)
1175                vidxes.resize(ssaIdCount, SIZE_MAX);
1176           
1177            // set liveness index to vidxes
1178            if (sinfo.readBeforeWrite)
1179            {
1180                if (vidxes[sinfo.ssaIdBefore] == SIZE_MAX)
1181                    vidxes[sinfo.ssaIdBefore] = graphVregsCount++;
1182            }
1183            if (sinfo.ssaIdChange!=0)
1184            {
1185                // fill up vidxes (with graph Ids)
1186                if (vidxes[sinfo.ssaIdFirst] == SIZE_MAX)
1187                    vidxes[sinfo.ssaIdFirst] = graphVregsCount++;
1188                for (size_t ssaId = sinfo.ssaId+1;
1189                        ssaId < sinfo.ssaId+sinfo.ssaIdChange-1; ssaId++)
1190                    vidxes[ssaId] = graphVregsCount++;
1191                if (vidxes[sinfo.ssaIdLast] == SIZE_MAX)
1192                    vidxes[sinfo.ssaIdLast] = graphVregsCount++;
1193            }
1194            // if not readBeforeWrite and neither ssaIdChanges but it is write to
1195            // normal register
1196            if (entry.first.regVar==nullptr && vidxes[0] == SIZE_MAX)
1197                vidxes[0] = graphVregsCount++;
1198        }
1199   
1200    // construct vreg liveness
1201    std::deque<CallStackEntry> callStack;
1202    std::deque<FlowStackEntry3> flowStack;
1203    CBlockBitPool visited(codeBlocks.size(), false);
1204    // hold last vreg ssaId and position
1205    LastVRegMap lastVRegMap;
1206   
1207    // key - current res first key, value - previous first key and its flowStack pos
1208    PrevWaysIndexMap prevWaysIndexMap;
1209    // to track ways last block indices pair: block index, flowStackPos)
1210    std::pair<size_t, size_t> lastCommonCacheWayPoint{ SIZE_MAX, SIZE_MAX };
1211    std::vector<bool> waysToCache(codeBlocks.size(), false);
1212    ResSecondPointsToCache cblocksToCache(codeBlocks.size());
1213    std::unordered_set<BlockIndex> callBlocks;
1214    std::unordered_set<size_t> recurseBlocks;
1215   
1216    size_t rbwCount = 0;
1217    size_t wrCount = 0;
1218   
1219    RoutineLvMap routineMap;
1220    std::vector<Liveness> livenesses[MAX_REGTYPES_NUM];
1221   
1222    for (size_t i = 0; i < regTypesNum; i++)
1223        livenesses[i].resize(graphVregsCounts[i]);
1224   
1225    // callLiveTime - call live time where routine will be called
1226    // reverse counted, begin from SIZE_MAX, used for joining svreg from routines
1227    // and svreg used in this time
1228    size_t curLiveTime = 0;
1229    flowStack.push_back({ 0, 0 });
1230   
1231    while (!flowStack.empty())
1232    {
1233        FlowStackEntry3& entry = flowStack.back();
1234        CodeBlock& cblock = codeBlocks[entry.blockIndex.index];
1235       
1236        if (entry.nextIndex == 0)
1237        {
1238            curLiveTime = cblock.start;
1239            // process current block
1240            if (!visited[entry.blockIndex])
1241            {
1242                visited[entry.blockIndex] = true;
1243                ARDOut << "joinpush: " << entry.blockIndex << "\n";
1244                if (flowStack.size() > 1)
1245                    putCrossBlockLivenesses(flowStack, codeBlocks, routineMap,
1246                            vidxCallMap, vidxRoutineMap, lastVRegMap,
1247                            livenesses, vregIndexMaps, regTypesNum, regRanges);
1248                // update last vreg position
1249                for (const auto& sentry: cblock.ssaInfoMap)
1250                {
1251                    // update
1252                    auto res = lastVRegMap.insert({ sentry.first,
1253                                { { flowStack.size()-1, false } } });
1254                    if (!res.second) // if not first seen, just update
1255                        // update last
1256                        res.first->second.push_back({ flowStack.size()-1, false });
1257                   
1258                    // count read before writes (for cache weight)
1259                    if (sentry.second.readBeforeWrite)
1260                        rbwCount++;
1261                    if (sentry.second.ssaIdChange!=0)
1262                        wrCount++;
1263                }
1264               
1265                // main routine to handle ssaInfos
1266                SVRegMap ssaIdIdxMap;
1267                AsmRegVarUsage instrRVUs[8];
1268                cxuint instrRVUsCount = 0;
1269               
1270                size_t oldOffset = cblock.usagePos.readOffset;
1271                std::vector<AsmSingleVReg> readSVRegs;
1272                std::vector<AsmSingleVReg> writtenSVRegs;
1273               
1274                usageHandler.setReadPos(cblock.usagePos);
1275                // register in liveness
1276                while (true)
1277                {
1278                    AsmRegVarUsage rvu = { 0U, nullptr, 0U, 0U };
1279                    bool hasNext = false;
1280                    if (usageHandler.hasNext() && oldOffset < cblock.end)
1281                    {
1282                        hasNext = true;
1283                        rvu = usageHandler.nextUsage();
1284                    }
1285                    const size_t liveTime = oldOffset;
1286                    if ((!hasNext || rvu.offset > oldOffset) && oldOffset < cblock.end)
1287                    {
1288                        ARDOut << "apply to liveness. offset: " << oldOffset << "\n";
1289                        // apply to liveness
1290                        for (AsmSingleVReg svreg: readSVRegs)
1291                        {
1292                            auto svrres = ssaIdIdxMap.insert({ svreg, 0 });
1293                            Liveness& lv = getLiveness(svreg, svrres.first->second,
1294                                    cblock.ssaInfoMap.find(svreg)->second,
1295                                    livenesses, vregIndexMaps, regTypesNum, regRanges);
1296                            if (svrres.second)
1297                                // begin region from this block
1298                                lv.newRegion(curLiveTime);
1299                            lv.expand(liveTime);
1300                        }
1301                        for (AsmSingleVReg svreg: writtenSVRegs)
1302                        {
1303                            size_t& ssaIdIdx = ssaIdIdxMap[svreg];
1304                            if (svreg.regVar != nullptr)
1305                                ssaIdIdx++;
1306                            SSAInfo& sinfo = cblock.ssaInfoMap.find(svreg)->second;
1307                            Liveness& lv = getLiveness(svreg, ssaIdIdx, sinfo,
1308                                    livenesses, vregIndexMaps, regTypesNum, regRanges);
1309                            // works only with ISA where smallest instruction have 2 bytes!
1310                            // after previous read, but not after instruction.
1311                            // if var is not used anywhere then this liveness region
1312                            // blocks assignment for other vars
1313                            lv.insert(liveTime+1, liveTime+2);
1314                        }
1315                        // get linear deps and equal to
1316                        cxbyte lDeps[16];
1317                        usageHandler.getUsageDependencies(instrRVUsCount, instrRVUs, lDeps);
1318                       
1319                        addUsageDeps(lDeps, instrRVUsCount, instrRVUs,
1320                                linearDepMaps, vregIndexMaps, ssaIdIdxMap,
1321                                regTypesNum, regRanges);
1322                       
1323                        readSVRegs.clear();
1324                        writtenSVRegs.clear();
1325                        if (!hasNext)
1326                            break;
1327                        oldOffset = rvu.offset;
1328                        instrRVUsCount = 0;
1329                    }
1330                    if (hasNext && oldOffset < cblock.end && !rvu.useRegMode)
1331                        instrRVUs[instrRVUsCount++] = rvu;
1332                    if (oldOffset >= cblock.end)
1333                        break;
1334                   
1335                    for (uint16_t rindex = rvu.rstart; rindex < rvu.rend; rindex++)
1336                    {
1337                        // per register/singlvreg
1338                        AsmSingleVReg svreg{ rvu.regVar, rindex };
1339                        if (rvu.rwFlags == ASMRVU_WRITE && rvu.regField!=ASMFIELD_NONE)
1340                            writtenSVRegs.push_back(svreg);
1341                        else // read or treat as reading // expand previous region
1342                            readSVRegs.push_back(svreg);
1343                    }
1344                }
1345            }
1346            else
1347            {
1348                cblocksToCache.increase(entry.blockIndex);
1349                ARDOut << "jcblockToCache: " << entry.blockIndex << "=" <<
1350                            cblocksToCache.count(entry.blockIndex) << "\n";
1351               
1352                // back, already visited
1353                flowStack.pop_back();
1354               
1355                size_t curWayBIndex = flowStack.back().blockIndex.index;
1356                if (lastCommonCacheWayPoint.first != SIZE_MAX)
1357                {
1358                    // mark point of way to cache (res first point)
1359                    waysToCache[lastCommonCacheWayPoint.first] = true;
1360                    ARDOut << "mark to pfcache " <<
1361                            lastCommonCacheWayPoint.first << ", " <<
1362                            curWayBIndex << "\n";
1363                    prevWaysIndexMap[curWayBIndex] = lastCommonCacheWayPoint;
1364                }
1365                lastCommonCacheWayPoint = { curWayBIndex, flowStack.size()-1 };
1366                ARDOut << "lastCcwP: " << curWayBIndex << "\n";
1367                continue;
1368            }
1369        }
1370       
1371        if (!callStack.empty() &&
1372            entry.blockIndex == callStack.back().callBlock &&
1373            entry.nextIndex-1 == callStack.back().callNextIndex)
1374        {
1375            ARDOut << " ret: " << entry.blockIndex << "\n";
1376            const BlockIndex routineBlock = callStack.back().routineBlock;
1377            auto res = routineMap.insert({ routineBlock.index, { } });
1378           
1379            // while second pass in recursion: the routine's insertion was happened
1380            // later in first pass (after return from second pass)
1381            // we check whether second pass happened for this routine
1382            if (res.second || res.first->second.inSecondPass)
1383            {
1384                res.first->second.inSecondPass = routineBlock.pass==1;
1385                auto varRes = vidxRoutineMap.insert({ routineBlock.index, VIdxSetEntry{} });
1386                createRoutineDataLv(codeBlocks, routineMap, recurseBlocks, vidxRoutineMap,
1387                        res.first->second, varRes.first->second,
1388                        routineBlock.index, vregIndexMaps, regTypesNum, regRanges);
1389            }
1390            else
1391            {
1392                // already added join livenesses from all readBeforeWrites
1393                for (const auto& entry: res.first->second.rbwSSAIdMap)
1394                {
1395                    // find last
1396                    auto lvrit = lastVRegMap.find(entry.first);
1397                    LastVRegStackPos flowStackStart = (lvrit != lastVRegMap.end()) ?
1398                            lvrit->second.back() : LastVRegStackPos{ 0, false };
1399                   
1400                    joinVRegRecur(flowStack, codeBlocks, routineMap,
1401                                  vidxCallMap, vidxRoutineMap,
1402                            flowStackStart, entry.first, entry.second, vregIndexMaps,
1403                            livenesses, regTypesNum, regRanges, false);
1404                }
1405            }
1406            callBlocks.erase(routineBlock);
1407            callStack.pop_back(); // just return from call
1408        }
1409       
1410        if (entry.nextIndex < cblock.nexts.size())
1411        {
1412            BlockIndex nextBlock = cblock.nexts[entry.nextIndex].block;
1413            nextBlock.pass = entry.blockIndex.pass;
1414            if (cblock.nexts[entry.nextIndex].isCall)
1415            {
1416                if (!callBlocks.insert(nextBlock).second)
1417                {
1418                    // just skip recursion (is good?)
1419                    if (recurseBlocks.insert(nextBlock.index).second)
1420                    {
1421                        ARDOut << "   -- recursion: " << nextBlock << "\n";
1422                        nextBlock.pass = 1;
1423                    }
1424                    else if (entry.blockIndex.pass==1)
1425                    {
1426                        /// mark that is routine call to skip
1427                        entry.nextIndex++;
1428                        continue;
1429                    }
1430                }
1431                else if (entry.blockIndex.pass==1 &&
1432                    recurseBlocks.find(nextBlock.index) != recurseBlocks.end())
1433                {
1434                    /// mark that is routine call to skip
1435                    entry.nextIndex++;
1436                    continue;
1437                }
1438               
1439                callStack.push_back({ entry.blockIndex,
1440                            entry.nextIndex, nextBlock });
1441            }
1442           
1443            flowStack.push_back({ nextBlock, 0 });
1444            entry.nextIndex++;
1445        }
1446        else if (((entry.nextIndex==0 && cblock.nexts.empty()) ||
1447                // if have any call then go to next block
1448                (cblock.haveCalls && entry.nextIndex==cblock.nexts.size())) &&
1449                 !cblock.haveReturn && !cblock.haveEnd)
1450        {
1451            if (entry.nextIndex!=0) // if back from calls (just return from calls)
1452            {
1453                std::unordered_set<AsmSingleVReg> regSVRegs;
1454                // just add last access of svreg from call routines to lastVRegMap
1455                // and join svregs from routine with svreg used at this time
1456                for (const NextBlock& next: cblock.nexts)
1457                    if (next.isCall)
1458                    {
1459                        auto rit = routineMap.find(next.block);
1460                        if (rit == routineMap.end())
1461                            continue;
1462                        const RoutineDataLv& rdata = rit->second;
1463                        for (const auto& entry: rdata.lastAccessMap)
1464                            if (regSVRegs.insert(entry.first).second)
1465                            {
1466                                auto res = lastVRegMap.insert({ entry.first,
1467                                        { { flowStack.size()-1, true } } });
1468                                if (!res.second) // if not first seen, just update
1469                                    // update last
1470                                    res.first->second.push_back(
1471                                                { flowStack.size()-1, true });
1472                            }
1473                    }
1474            }
1475           
1476            flowStack.push_back({ entry.blockIndex+1, 0 });
1477            entry.nextIndex++;
1478        }
1479        else // back
1480        {
1481            // revert lastSSAIdMap
1482            flowStack.pop_back();
1483           
1484            // revert lastVRegs in call
1485            std::unordered_set<AsmSingleVReg> revertedSVRegs;
1486            for (const NextBlock& next: cblock.nexts)
1487                if (next.isCall)
1488                {
1489                    auto rit = routineMap.find(next.block);
1490                    if (rit == routineMap.end())
1491                        continue;
1492                    const RoutineDataLv& rdata = rit->second;
1493                    for (const auto& entry: rdata.lastAccessMap)
1494                        if (revertedSVRegs.insert(entry.first).second)
1495                            revertLastSVReg(lastVRegMap, entry.first);
1496                }
1497           
1498            for (const auto& sentry: cblock.ssaInfoMap)
1499                revertLastSVReg(lastVRegMap, sentry.first);
1500           
1501            if (!flowStack.empty() && lastCommonCacheWayPoint.first != SIZE_MAX &&
1502                    lastCommonCacheWayPoint.second >= flowStack.size() &&
1503                    flowStack.back().blockIndex.pass == 0)
1504            {
1505                lastCommonCacheWayPoint =
1506                        { flowStack.back().blockIndex.index, flowStack.size()-1 };
1507                ARDOut << "POPlastCcwP: " << lastCommonCacheWayPoint.first << "\n";
1508            }
1509        }
1510    }
1511   
1512    // after, that resolve joins (join with already visited code)
1513    // SVRegMap in this cache: key - vreg, value - last flowStack entry position
1514    SimpleCache<size_t, LastStackPosMap> joinFirstPointsCache(wrCount<<1);
1515    // SVRegMap in this cache: key - vreg, value - first readBefore in second part
1516    SimpleCache<size_t, SVRegMap> joinSecondPointsCache(rbwCount<<1);
1517   
1518    flowStack.clear();
1519    std::fill(visited.begin(), visited.end(), false);
1520   
1521    flowStack.push_back({ 0, 0 });
1522   
1523    while (!flowStack.empty())
1524    {
1525        FlowStackEntry3& entry = flowStack.back();
1526        CodeBlock& cblock = codeBlocks[entry.blockIndex.index];
1527       
1528        if (entry.nextIndex == 0)
1529        {
1530            // process current block
1531            if (!visited[entry.blockIndex])
1532                visited[entry.blockIndex] = true;
1533            else
1534            {
1535                joinRegVarLivenesses(flowStack, codeBlocks, routineMap,
1536                        vidxCallMap, vidxRoutineMap,
1537                        prevWaysIndexMap, waysToCache, cblocksToCache,
1538                        joinFirstPointsCache, joinSecondPointsCache,
1539                        vregIndexMaps, livenesses, regTypesNum, regRanges);
1540                // back, already visited
1541                flowStack.pop_back();
1542                continue;
1543            }
1544        }
1545       
1546        if (entry.nextIndex < cblock.nexts.size())
1547        {
1548            flowStack.push_back({ cblock.nexts[entry.nextIndex].block, 0 });
1549            entry.nextIndex++;
1550        }
1551        else if (((entry.nextIndex==0 && cblock.nexts.empty()) ||
1552                // if have any call then go to next block
1553                (cblock.haveCalls && entry.nextIndex==cblock.nexts.size())) &&
1554                 !cblock.haveReturn && !cblock.haveEnd)
1555        {
1556            flowStack.push_back({ entry.blockIndex+1, 0 });
1557            entry.nextIndex++;
1558        }
1559        else // back
1560        {
1561            if (cblocksToCache.count(entry.blockIndex)==2 &&
1562                !joinSecondPointsCache.hasKey(entry.blockIndex.index))
1563                // add to cache
1564                addJoinSecCacheEntry(routineMap, codeBlocks, joinSecondPointsCache,
1565                            entry.blockIndex.index);
1566            flowStack.pop_back();
1567        }
1568    }
1569   
1570    // move livenesses to AsmRegAllocator outLivenesses
1571    for (size_t regType = 0; regType < regTypesNum; regType++)
1572    {
1573        std::vector<Liveness>& livenesses2 = livenesses[regType];
1574        Array<OutLiveness>& outLivenesses2 = outLivenesses[regType];
1575        outLivenesses2.resize(livenesses2.size());
1576        for (size_t li = 0; li < livenesses2.size(); li++)
1577        {
1578            outLivenesses2[li].resize(livenesses2[li].l.size());
1579            std::copy(livenesses2[li].l.begin(), livenesses2[li].l.end(),
1580                      outLivenesses2[li].begin());
1581            livenesses2[li].clear();
1582        }
1583        livenesses2.clear();
1584    }
1585}
Note: See TracBrowser for help on using the repository browser.