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

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

CLRadeonExtender: AsmRegAlloc?: Fixed creating routine data (for livenesses) for two recursion passes.

File size: 66.8 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        size_t 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, 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;
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({ svreg, { { routineBlock, false } } });
1122        if (!res.second)
1123        {
1124            VectorSet<LastAccessBlockPos>& sset = res.first->second;
1125            sset.insertValue({ routineBlock, false });
1126        }
1127    }
1128}
1129
1130static inline void revertLastSVReg(LastVRegMap& lastVRegMap, const AsmSingleVReg& svreg)
1131{
1132    auto lvrit = lastVRegMap.find(svreg);
1133    if (lvrit != lastVRegMap.end())
1134    {
1135        std::vector<LastVRegStackPos>& lastPos = lvrit->second;
1136        lastPos.pop_back();
1137        if (lastPos.empty()) // just remove from lastVRegs
1138            lastVRegMap.erase(lvrit);
1139    }
1140}
1141
1142void AsmRegAllocator::createLivenesses(ISAUsageHandler& usageHandler)
1143{
1144    ARDOut << "----- createLivenesses ------\n";
1145    // construct var index maps
1146    cxuint regRanges[MAX_REGTYPES_NUM*2];
1147    std::fill(graphVregsCounts, graphVregsCounts+MAX_REGTYPES_NUM, size_t(0));
1148    size_t regTypesNum;
1149    assembler.isaAssembler->getRegisterRanges(regTypesNum, regRanges);
1150   
1151    for (const CodeBlock& cblock: codeBlocks)
1152        for (const auto& entry: cblock.ssaInfoMap)
1153        {
1154            const SSAInfo& sinfo = entry.second;
1155            cxuint regType = getRegType(regTypesNum, regRanges, entry.first);
1156            VarIndexMap& vregIndices = vregIndexMaps[regType];
1157            size_t& graphVregsCount = graphVregsCounts[regType];
1158            std::vector<size_t>& vidxes = vregIndices[entry.first];
1159            size_t ssaIdCount = 0;
1160            if (sinfo.readBeforeWrite)
1161                ssaIdCount = sinfo.ssaIdBefore+1;
1162            if (sinfo.ssaIdChange!=0)
1163            {
1164                ssaIdCount = std::max(ssaIdCount, sinfo.ssaIdLast+1);
1165                ssaIdCount = std::max(ssaIdCount, sinfo.ssaId+sinfo.ssaIdChange-1);
1166                ssaIdCount = std::max(ssaIdCount, sinfo.ssaIdFirst+1);
1167            }
1168            // if not readBeforeWrite and neither ssaIdChanges but it is write to
1169            // normal register
1170            if (entry.first.regVar==nullptr)
1171                ssaIdCount = 1;
1172           
1173            if (vidxes.size() < ssaIdCount)
1174                vidxes.resize(ssaIdCount, SIZE_MAX);
1175           
1176            // set liveness index to vidxes
1177            if (sinfo.readBeforeWrite)
1178            {
1179                if (vidxes[sinfo.ssaIdBefore] == SIZE_MAX)
1180                    vidxes[sinfo.ssaIdBefore] = graphVregsCount++;
1181            }
1182            if (sinfo.ssaIdChange!=0)
1183            {
1184                // fill up vidxes (with graph Ids)
1185                if (vidxes[sinfo.ssaIdFirst] == SIZE_MAX)
1186                    vidxes[sinfo.ssaIdFirst] = graphVregsCount++;
1187                for (size_t ssaId = sinfo.ssaId+1;
1188                        ssaId < sinfo.ssaId+sinfo.ssaIdChange-1; ssaId++)
1189                    vidxes[ssaId] = graphVregsCount++;
1190                if (vidxes[sinfo.ssaIdLast] == SIZE_MAX)
1191                    vidxes[sinfo.ssaIdLast] = graphVregsCount++;
1192            }
1193            // if not readBeforeWrite and neither ssaIdChanges but it is write to
1194            // normal register
1195            if (entry.first.regVar==nullptr && vidxes[0] == SIZE_MAX)
1196                vidxes[0] = graphVregsCount++;
1197        }
1198   
1199    // construct vreg liveness
1200    std::deque<CallStackEntry> callStack;
1201    std::deque<FlowStackEntry3> flowStack;
1202    CBlockBitPool visited(codeBlocks.size(), false);
1203    // hold last vreg ssaId and position
1204    LastVRegMap lastVRegMap;
1205   
1206    // key - current res first key, value - previous first key and its flowStack pos
1207    PrevWaysIndexMap prevWaysIndexMap;
1208    // to track ways last block indices pair: block index, flowStackPos)
1209    std::pair<size_t, size_t> lastCommonCacheWayPoint{ SIZE_MAX, SIZE_MAX };
1210    std::vector<bool> waysToCache(codeBlocks.size(), false);
1211    ResSecondPointsToCache cblocksToCache(codeBlocks.size());
1212    std::unordered_set<BlockIndex> callBlocks;
1213    std::unordered_set<size_t> recurseBlocks;
1214   
1215    size_t rbwCount = 0;
1216    size_t wrCount = 0;
1217   
1218    RoutineLvMap routineMap;
1219    std::vector<Liveness> livenesses[MAX_REGTYPES_NUM];
1220   
1221    for (size_t i = 0; i < regTypesNum; i++)
1222        livenesses[i].resize(graphVregsCounts[i]);
1223   
1224    // callLiveTime - call live time where routine will be called
1225    // reverse counted, begin from SIZE_MAX, used for joining svreg from routines
1226    // and svreg used in this time
1227    size_t curLiveTime = 0;
1228    flowStack.push_back({ 0, 0 });
1229   
1230    while (!flowStack.empty())
1231    {
1232        FlowStackEntry3& entry = flowStack.back();
1233        CodeBlock& cblock = codeBlocks[entry.blockIndex.index];
1234       
1235        if (entry.nextIndex == 0)
1236        {
1237            curLiveTime = cblock.start;
1238            // process current block
1239            if (!visited[entry.blockIndex])
1240            {
1241                visited[entry.blockIndex] = true;
1242                ARDOut << "joinpush: " << entry.blockIndex << "\n";
1243                if (flowStack.size() > 1)
1244                    putCrossBlockLivenesses(flowStack, codeBlocks, routineMap,
1245                            vidxCallMap, vidxRoutineMap, lastVRegMap,
1246                            livenesses, vregIndexMaps, regTypesNum, regRanges);
1247                // update last vreg position
1248                for (const auto& sentry: cblock.ssaInfoMap)
1249                {
1250                    // update
1251                    auto res = lastVRegMap.insert({ sentry.first,
1252                                { { flowStack.size()-1, false } } });
1253                    if (!res.second) // if not first seen, just update
1254                        // update last
1255                        res.first->second.push_back({ flowStack.size()-1, false });
1256                   
1257                    // count read before writes (for cache weight)
1258                    if (sentry.second.readBeforeWrite)
1259                        rbwCount++;
1260                    if (sentry.second.ssaIdChange!=0)
1261                        wrCount++;
1262                }
1263               
1264                // main routine to handle ssaInfos
1265                SVRegMap ssaIdIdxMap;
1266                AsmRegVarUsage instrRVUs[8];
1267                cxuint instrRVUsCount = 0;
1268               
1269                size_t oldOffset = cblock.usagePos.readOffset;
1270                std::vector<AsmSingleVReg> readSVRegs;
1271                std::vector<AsmSingleVReg> writtenSVRegs;
1272               
1273                usageHandler.setReadPos(cblock.usagePos);
1274                // register in liveness
1275                while (true)
1276                {
1277                    AsmRegVarUsage rvu = { 0U, nullptr, 0U, 0U };
1278                    bool hasNext = false;
1279                    if (usageHandler.hasNext() && oldOffset < cblock.end)
1280                    {
1281                        hasNext = true;
1282                        rvu = usageHandler.nextUsage();
1283                    }
1284                    const size_t liveTime = oldOffset;
1285                    if ((!hasNext || rvu.offset > oldOffset) && oldOffset < cblock.end)
1286                    {
1287                        ARDOut << "apply to liveness. offset: " << oldOffset << "\n";
1288                        // apply to liveness
1289                        for (AsmSingleVReg svreg: readSVRegs)
1290                        {
1291                            auto svrres = ssaIdIdxMap.insert({ svreg, 0 });
1292                            Liveness& lv = getLiveness(svreg, svrres.first->second,
1293                                    cblock.ssaInfoMap.find(svreg)->second,
1294                                    livenesses, vregIndexMaps, regTypesNum, regRanges);
1295                            if (svrres.second)
1296                                // begin region from this block
1297                                lv.newRegion(curLiveTime);
1298                            lv.expand(liveTime);
1299                        }
1300                        for (AsmSingleVReg svreg: writtenSVRegs)
1301                        {
1302                            size_t& ssaIdIdx = ssaIdIdxMap[svreg];
1303                            if (svreg.regVar != nullptr)
1304                                ssaIdIdx++;
1305                            SSAInfo& sinfo = cblock.ssaInfoMap.find(svreg)->second;
1306                            Liveness& lv = getLiveness(svreg, ssaIdIdx, sinfo,
1307                                    livenesses, vregIndexMaps, regTypesNum, regRanges);
1308                            // works only with ISA where smallest instruction have 2 bytes!
1309                            // after previous read, but not after instruction.
1310                            // if var is not used anywhere then this liveness region
1311                            // blocks assignment for other vars
1312                            lv.insert(liveTime+1, liveTime+2);
1313                        }
1314                        // get linear deps and equal to
1315                        cxbyte lDeps[16];
1316                        usageHandler.getUsageDependencies(instrRVUsCount, instrRVUs, lDeps);
1317                       
1318                        addUsageDeps(lDeps, instrRVUsCount, instrRVUs,
1319                                linearDepMaps, vregIndexMaps, ssaIdIdxMap,
1320                                regTypesNum, regRanges);
1321                       
1322                        readSVRegs.clear();
1323                        writtenSVRegs.clear();
1324                        if (!hasNext)
1325                            break;
1326                        oldOffset = rvu.offset;
1327                        instrRVUsCount = 0;
1328                    }
1329                    if (hasNext && oldOffset < cblock.end && !rvu.useRegMode)
1330                        instrRVUs[instrRVUsCount++] = rvu;
1331                    if (oldOffset >= cblock.end)
1332                        break;
1333                   
1334                    for (uint16_t rindex = rvu.rstart; rindex < rvu.rend; rindex++)
1335                    {
1336                        // per register/singlvreg
1337                        AsmSingleVReg svreg{ rvu.regVar, rindex };
1338                        if (rvu.rwFlags == ASMRVU_WRITE && rvu.regField!=ASMFIELD_NONE)
1339                            writtenSVRegs.push_back(svreg);
1340                        else // read or treat as reading // expand previous region
1341                            readSVRegs.push_back(svreg);
1342                    }
1343                }
1344            }
1345            else
1346            {
1347                cblocksToCache.increase(entry.blockIndex);
1348                ARDOut << "jcblockToCache: " << entry.blockIndex << "=" <<
1349                            cblocksToCache.count(entry.blockIndex) << "\n";
1350               
1351                // back, already visited
1352                flowStack.pop_back();
1353               
1354                size_t curWayBIndex = flowStack.back().blockIndex.index;
1355                if (lastCommonCacheWayPoint.first != SIZE_MAX)
1356                {
1357                    // mark point of way to cache (res first point)
1358                    waysToCache[lastCommonCacheWayPoint.first] = true;
1359                    ARDOut << "mark to pfcache " <<
1360                            lastCommonCacheWayPoint.first << ", " <<
1361                            curWayBIndex << "\n";
1362                    prevWaysIndexMap[curWayBIndex] = lastCommonCacheWayPoint;
1363                }
1364                lastCommonCacheWayPoint = { curWayBIndex, flowStack.size()-1 };
1365                ARDOut << "lastCcwP: " << curWayBIndex << "\n";
1366                continue;
1367            }
1368        }
1369       
1370        if (!callStack.empty() &&
1371            entry.blockIndex == callStack.back().callBlock &&
1372            entry.nextIndex-1 == callStack.back().callNextIndex)
1373        {
1374            ARDOut << " ret: " << entry.blockIndex << "\n";
1375            const BlockIndex routineBlock = callStack.back().routineBlock;
1376            auto res = routineMap.insert({ routineBlock.index, { } });
1377           
1378            // while second pass in recursion: the routine's insertion was happened
1379            // later in first pass (after return from second pass)
1380            // we check whether second pass happened for this routine
1381            // order: create in second pass recursion
1382            //           (fromSecondPass && rblock.pass==0 avoids
1383            //            doubles creating in second pass)
1384            //        create in first pass recursion
1385            if (res.second || (res.first->second.fromSecondPass && routineBlock.pass==0))
1386            {
1387                res.first->second.fromSecondPass = routineBlock.pass==1;
1388                auto varRes = vidxRoutineMap.insert({ routineBlock.index, VIdxSetEntry{} });
1389                createRoutineDataLv(codeBlocks, routineMap, recurseBlocks, vidxRoutineMap,
1390                        res.first->second, varRes.first->second,
1391                        routineBlock.index, vregIndexMaps, regTypesNum, regRanges);
1392            }
1393            else
1394            {
1395                // already added join livenesses from all readBeforeWrites
1396                for (const auto& entry: res.first->second.rbwSSAIdMap)
1397                {
1398                    // find last
1399                    auto lvrit = lastVRegMap.find(entry.first);
1400                    LastVRegStackPos flowStackStart = (lvrit != lastVRegMap.end()) ?
1401                            lvrit->second.back() : LastVRegStackPos{ 0, false };
1402                   
1403                    joinVRegRecur(flowStack, codeBlocks, routineMap,
1404                                  vidxCallMap, vidxRoutineMap,
1405                            flowStackStart, entry.first, entry.second, vregIndexMaps,
1406                            livenesses, regTypesNum, regRanges, false);
1407                }
1408            }
1409            callBlocks.erase(routineBlock);
1410            callStack.pop_back(); // just return from call
1411        }
1412       
1413        if (entry.nextIndex < cblock.nexts.size())
1414        {
1415            BlockIndex nextBlock = cblock.nexts[entry.nextIndex].block;
1416            nextBlock.pass = entry.blockIndex.pass;
1417            if (cblock.nexts[entry.nextIndex].isCall)
1418            {
1419                if (!callBlocks.insert(nextBlock).second)
1420                {
1421                    // just skip recursion (is good?)
1422                    if (recurseBlocks.insert(nextBlock.index).second)
1423                    {
1424                        ARDOut << "   -- recursion: " << nextBlock << "\n";
1425                        nextBlock.pass = 1;
1426                    }
1427                    else if (entry.blockIndex.pass==1)
1428                    {
1429                        /// mark that is routine call to skip
1430                        entry.nextIndex++;
1431                        continue;
1432                    }
1433                }
1434                else if (entry.blockIndex.pass==1 &&
1435                    recurseBlocks.find(nextBlock.index) != recurseBlocks.end())
1436                {
1437                    /// mark that is routine call to skip
1438                    entry.nextIndex++;
1439                    continue;
1440                }
1441               
1442                callStack.push_back({ entry.blockIndex,
1443                            entry.nextIndex, nextBlock });
1444            }
1445           
1446            flowStack.push_back({ nextBlock, 0 });
1447            entry.nextIndex++;
1448        }
1449        else if (((entry.nextIndex==0 && cblock.nexts.empty()) ||
1450                // if have any call then go to next block
1451                (cblock.haveCalls && entry.nextIndex==cblock.nexts.size())) &&
1452                 !cblock.haveReturn && !cblock.haveEnd)
1453        {
1454            if (entry.nextIndex!=0) // if back from calls (just return from calls)
1455            {
1456                std::unordered_set<AsmSingleVReg> regSVRegs;
1457                // just add last access of svreg from call routines to lastVRegMap
1458                // and join svregs from routine with svreg used at this time
1459                for (const NextBlock& next: cblock.nexts)
1460                    if (next.isCall)
1461                    {
1462                        auto rit = routineMap.find(next.block);
1463                        if (rit == routineMap.end())
1464                            continue;
1465                        const RoutineDataLv& rdata = rit->second;
1466                        for (const auto& entry: rdata.lastAccessMap)
1467                            if (regSVRegs.insert(entry.first).second)
1468                            {
1469                                auto res = lastVRegMap.insert({ entry.first,
1470                                        { { flowStack.size()-1, true } } });
1471                                if (!res.second) // if not first seen, just update
1472                                    // update last
1473                                    res.first->second.push_back(
1474                                                { flowStack.size()-1, true });
1475                            }
1476                    }
1477            }
1478           
1479            flowStack.push_back({ entry.blockIndex+1, 0 });
1480            entry.nextIndex++;
1481        }
1482        else // back
1483        {
1484            // revert lastSSAIdMap
1485            flowStack.pop_back();
1486           
1487            // revert lastVRegs in call
1488            std::unordered_set<AsmSingleVReg> revertedSVRegs;
1489            for (const NextBlock& next: cblock.nexts)
1490                if (next.isCall)
1491                {
1492                    auto rit = routineMap.find(next.block);
1493                    if (rit == routineMap.end())
1494                        continue;
1495                    const RoutineDataLv& rdata = rit->second;
1496                    for (const auto& entry: rdata.lastAccessMap)
1497                        if (revertedSVRegs.insert(entry.first).second)
1498                            revertLastSVReg(lastVRegMap, entry.first);
1499                }
1500           
1501            for (const auto& sentry: cblock.ssaInfoMap)
1502                revertLastSVReg(lastVRegMap, sentry.first);
1503           
1504            if (!flowStack.empty() && lastCommonCacheWayPoint.first != SIZE_MAX &&
1505                    lastCommonCacheWayPoint.second >= flowStack.size() &&
1506                    flowStack.back().blockIndex.pass == 0)
1507            {
1508                lastCommonCacheWayPoint =
1509                        { flowStack.back().blockIndex.index, flowStack.size()-1 };
1510                ARDOut << "POPlastCcwP: " << lastCommonCacheWayPoint.first << "\n";
1511            }
1512        }
1513    }
1514   
1515    // after, that resolve joins (join with already visited code)
1516    // SVRegMap in this cache: key - vreg, value - last flowStack entry position
1517    SimpleCache<size_t, LastStackPosMap> joinFirstPointsCache(wrCount<<1);
1518    // SVRegMap in this cache: key - vreg, value - first readBefore in second part
1519    SimpleCache<size_t, SVRegMap> joinSecondPointsCache(rbwCount<<1);
1520   
1521    flowStack.clear();
1522    std::fill(visited.begin(), visited.end(), false);
1523   
1524    flowStack.push_back({ 0, 0 });
1525   
1526    while (!flowStack.empty())
1527    {
1528        FlowStackEntry3& entry = flowStack.back();
1529        CodeBlock& cblock = codeBlocks[entry.blockIndex.index];
1530       
1531        if (entry.nextIndex == 0)
1532        {
1533            // process current block
1534            if (!visited[entry.blockIndex])
1535                visited[entry.blockIndex] = true;
1536            else
1537            {
1538                joinRegVarLivenesses(flowStack, codeBlocks, routineMap,
1539                        vidxCallMap, vidxRoutineMap,
1540                        prevWaysIndexMap, waysToCache, cblocksToCache,
1541                        joinFirstPointsCache, joinSecondPointsCache,
1542                        vregIndexMaps, livenesses, regTypesNum, regRanges);
1543                // back, already visited
1544                flowStack.pop_back();
1545                continue;
1546            }
1547        }
1548       
1549        if (entry.nextIndex < cblock.nexts.size())
1550        {
1551            flowStack.push_back({ cblock.nexts[entry.nextIndex].block, 0 });
1552            entry.nextIndex++;
1553        }
1554        else if (((entry.nextIndex==0 && cblock.nexts.empty()) ||
1555                // if have any call then go to next block
1556                (cblock.haveCalls && entry.nextIndex==cblock.nexts.size())) &&
1557                 !cblock.haveReturn && !cblock.haveEnd)
1558        {
1559            flowStack.push_back({ entry.blockIndex+1, 0 });
1560            entry.nextIndex++;
1561        }
1562        else // back
1563        {
1564            if (cblocksToCache.count(entry.blockIndex)==2 &&
1565                !joinSecondPointsCache.hasKey(entry.blockIndex.index))
1566                // add to cache
1567                addJoinSecCacheEntry(routineMap, codeBlocks, joinSecondPointsCache,
1568                            entry.blockIndex.index);
1569            flowStack.pop_back();
1570        }
1571    }
1572   
1573    // move livenesses to AsmRegAllocator outLivenesses
1574    for (size_t regType = 0; regType < regTypesNum; regType++)
1575    {
1576        std::vector<Liveness>& livenesses2 = livenesses[regType];
1577        Array<OutLiveness>& outLivenesses2 = outLivenesses[regType];
1578        outLivenesses2.resize(livenesses2.size());
1579        for (size_t li = 0; li < livenesses2.size(); li++)
1580        {
1581            outLivenesses2[li].resize(livenesses2[li].l.size());
1582            std::copy(livenesses2[li].l.begin(), livenesses2[li].l.end(),
1583                      outLivenesses2[li].begin());
1584            livenesses2[li].clear();
1585        }
1586        livenesses2.clear();
1587    }
1588}
Note: See TracBrowser for help on using the repository browser.