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

Last change on this file since 4158 was 4158, checked in by matszpk, 12 months ago

CLRadeonExtender: AsmRegAlloc?: Fixed last testcase (missing sa[1] (7) in vidxCallmap).
Add vidx to callMap before entry call and if join inside subroutines (not before call point).

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