source: CLRX/CLRadeonExtender/trunk/amdasm/AsmRegAllocSSAData.cpp @ 3994

Last change on this file since 3994 was 3994, checked in by matszpk, 13 months ago

CLRadeonExtender: remove obsolete includes.

File size: 74.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 <iostream>
22#include <stack>
23#include <deque>
24#include <vector>
25#include <utility>
26#include <unordered_set>
27#include <unordered_map>
28#include <algorithm>
29#include <CLRX/utils/Utilities.h>
30#include <CLRX/utils/Containers.h>
31#include <CLRX/amdasm/Assembler.h>
32#include "AsmInternals.h"
33#include "AsmRegAlloc.h"
34
35using namespace CLRX;
36
37
38class CLRX_INTERNAL ResSecondPointsToCache: public CBlockBitPool
39{
40public:
41    explicit ResSecondPointsToCache(size_t n) : CBlockBitPool(n<<1, false)
42    { }
43   
44    void increase(BlockIndex ip)
45    {
46        const size_t i = ip.index + (ip.pass ? (size()>>2) : 0);
47        if ((*this)[i<<1])
48            (*this)[(i<<1)+1] = true;
49        else
50            (*this)[i<<1] = true;
51    }
52   
53    cxuint count(BlockIndex ip) const
54    {
55        const size_t i = ip.index + (ip.pass ? (size()>>2) : 0);
56        return cxuint((*this)[i<<1]) + (*this)[(i<<1)+1];
57    }
58};
59
60typedef AsmRegAllocator::SSAReplace SSAReplace; // first - orig ssaid, second - dest ssaid
61typedef AsmRegAllocator::SSAReplacesMap SSAReplacesMap;
62
63static inline void insertReplace(SSAReplacesMap& rmap, const AsmSingleVReg& vreg,
64              size_t origId, size_t destId)
65{
66    ARDOut << "  insertreplace: " << vreg.regVar << ":" << vreg.index  << ": " <<
67                origId << ", " << destId << "\n";
68    auto res = rmap.insert({ vreg, {} });
69    res.first->second.insertValue({ origId, destId });
70}
71
72/* caching concepts:
73 * resfirstPointsCache - cache of the ways that goes to conflict which should be resolved
74 *               from first code block of the code. The entries holds a stackVarMap state
75 *               to first point the conflict (first visited already code block)
76 * resSecondPointsCache - cache of the tree traversing, starting at the first conflict
77 *               point (first visited code block). Entries holds a
78 *               regvars SSAId read before write (that should resolved)
79 */
80
81static void handleSSAEntryWhileResolving(SSAReplacesMap* replacesMap,
82            const LastSSAIdMap* stackVarMap,
83            std::unordered_map<AsmSingleVReg, BlockIndex>& alreadyReadMap,
84            FlowStackEntry2& entry, const SSAEntry& sentry,
85            RBWSSAIdMap* cacheSecPoints)
86{
87    const SSAInfo& sinfo = sentry.second;
88    auto res = alreadyReadMap.insert({ sentry.first, entry.blockIndex });
89   
90    if (res.second && sinfo.readBeforeWrite)
91    {
92        if (cacheSecPoints != nullptr)
93        {
94            auto res = cacheSecPoints->insert({ sentry.first, { sinfo.ssaIdBefore } });
95            if (!res.second)
96                res.first->second.insertValue(sinfo.ssaIdBefore);
97        }
98       
99        if (stackVarMap != nullptr)
100        {
101            // resolve conflict for this variable ssaId>.
102            // only if in previous block previous SSAID is
103            // read before all writes
104            auto it = stackVarMap->find(sentry.first);
105           
106            if (it != stackVarMap->end())
107            {
108                // found, resolve by set ssaIdLast
109                for (size_t ssaId: it->second)
110                {
111                    if (ssaId > sinfo.ssaIdBefore)
112                        insertReplace(*replacesMap, sentry.first, ssaId,
113                                    sinfo.ssaIdBefore);
114                    else if (ssaId < sinfo.ssaIdBefore)
115                        insertReplace(*replacesMap, sentry.first,
116                                        sinfo.ssaIdBefore, ssaId);
117                }
118            }
119        }
120    }
121}
122
123typedef std::unordered_map<BlockIndex, std::pair<BlockIndex, size_t> > PrevWaysIndexMap;
124
125// use res second point cache entry to resolve conflict with SSAIds.
126// it emits SSA replaces from these conflicts
127static void useResSecPointCache(SSAReplacesMap* replacesMap,
128        const LastSSAIdMap* stackVarMap,
129        const std::unordered_map<AsmSingleVReg, BlockIndex>& alreadyReadMap,
130        const RBWSSAIdMap* resSecondPoints, BlockIndex nextBlock,
131        RBWSSAIdMap* destCacheSecPoints)
132{
133    ARDOut << "use resSecPointCache for " << nextBlock <<
134            ", alreadyRMapSize: " << alreadyReadMap.size() << "\n";
135    for (const auto& sentry: *resSecondPoints)
136    {
137        const bool alreadyRead = alreadyReadMap.find(sentry.first) != alreadyReadMap.end();
138        if (destCacheSecPoints != nullptr && !alreadyRead)
139        {
140            auto res = destCacheSecPoints->insert(sentry);
141            if (!res.second)
142                for (size_t srcSSAId: sentry.second)
143                    res.first->second.insertValue(srcSSAId);
144        }
145       
146        if (stackVarMap != nullptr)
147        {
148            auto it = stackVarMap->find(sentry.first);
149           
150            if (it != stackVarMap->end() && !alreadyRead)
151            {
152                // found, resolve by set ssaIdLast
153                for (size_t ssaId: it->second)
154                {
155                    for (size_t secSSAId: sentry.second)
156                    {
157                        if (ssaId > secSSAId)
158                            insertReplace(*replacesMap, sentry.first, ssaId, secSSAId);
159                        else if (ssaId < secSSAId)
160                            insertReplace(*replacesMap, sentry.first, secSSAId, ssaId);
161                    }
162                }
163            }
164        }
165    }
166}
167
168// add new res second cache entry with readBeforeWrite for all encountered regvars
169static void addResSecCacheEntry(const RoutineMap& routineMap,
170                const std::vector<CodeBlock>& codeBlocks,
171                SimpleCache<BlockIndex, RBWSSAIdMap>& resSecondPointsCache,
172                BlockIndex nextBlock)
173{
174    ARDOut << "addResSecCacheEntry: " << nextBlock << "\n";
175    //std::stack<CallStackEntry> callStack = prevCallStack;
176    // traverse by graph from next block
177    std::deque<FlowStackEntry2> flowStack;
178    flowStack.push_back({ nextBlock, 0 });
179    CBlockBitPool visited(codeBlocks.size(), false);
180   
181    std::unordered_map<AsmSingleVReg, BlockIndex> alreadyReadMap;
182   
183    RBWSSAIdMap cacheSecPoints;
184   
185    while (!flowStack.empty())
186    {
187        FlowStackEntry2& entry = flowStack.back();
188        const CodeBlock& cblock = codeBlocks[entry.blockIndex.index];
189       
190        if (entry.nextIndex == 0)
191        {
192            // process current block
193            if (!visited[entry.blockIndex])
194            {
195                visited[entry.blockIndex] = true;
196                ARDOut << "  resolv (cache): " << entry.blockIndex << "\n";
197               
198                const RBWSSAIdMap* resSecondPoints =
199                            resSecondPointsCache.use(entry.blockIndex);
200                if (resSecondPoints == nullptr)
201                    for (auto& sentry: cblock.ssaInfoMap)
202                        handleSSAEntryWhileResolving(nullptr, nullptr,
203                                alreadyReadMap, entry, sentry,
204                                &cacheSecPoints);
205                else // to use cache
206                {
207                    useResSecPointCache(nullptr, nullptr, alreadyReadMap,
208                            resSecondPoints, entry.blockIndex, &cacheSecPoints);
209                    flowStack.pop_back();
210                    continue;
211                }
212            }
213            else
214            {
215                // back, already visited
216                ARDOut << "resolv already (cache): " << entry.blockIndex << "\n";
217                flowStack.pop_back();
218                continue;
219            }
220        }
221       
222        if (entry.nextIndex < cblock.nexts.size())
223        {
224            flowStack.push_back({ { cblock.nexts[entry.nextIndex].block,
225                    entry.blockIndex.pass }, 0 });
226            entry.nextIndex++;
227        }
228        else if (((entry.nextIndex==0 && cblock.nexts.empty()) ||
229                // if have any call then go to next block
230                (cblock.haveCalls && entry.nextIndex==cblock.nexts.size())) &&
231                 !cblock.haveReturn && !cblock.haveEnd)
232        {
233            // add toResolveMap ssaIds inside called routines
234            for (const auto& next: cblock.nexts)
235                if (next.isCall)
236                {
237                    const RoutineData& rdata = routineMap.find(next.block)->second;
238                    for (const auto& v: rdata.rbwSSAIdMap)
239                        alreadyReadMap.insert({v.first, entry.blockIndex });
240                    for (const auto& v: rdata.lastSSAIdMap)
241                        alreadyReadMap.insert({v.first, entry.blockIndex });
242                }
243           
244            flowStack.push_back({ entry.blockIndex+1, 0 });
245            entry.nextIndex++;
246        }
247        else // back
248        {
249            // remove old to resolve in leaved way to allow collecting next ssaId
250            // before write (can be different due to earlier visit)
251            for (const auto& next: cblock.nexts)
252                if (next.isCall)
253                {
254                    const RoutineData& rdata = routineMap.find(next.block)->second;
255                    for (const auto& v: rdata.rbwSSAIdMap)
256                    {
257                        auto it = alreadyReadMap.find(v.first);
258                        if (it != alreadyReadMap.end() && it->second == entry.blockIndex)
259                            alreadyReadMap.erase(it);
260                    }
261                    for (const auto& v: rdata.lastSSAIdMap)
262                    {
263                        auto it = alreadyReadMap.find(v.first);
264                        if (it != alreadyReadMap.end() && it->second == entry.blockIndex)
265                            alreadyReadMap.erase(it);
266                    }
267                }
268           
269            for (const auto& sentry: cblock.ssaInfoMap)
270            {
271                auto it = alreadyReadMap.find(sentry.first);
272                if (it != alreadyReadMap.end() && it->second == entry.blockIndex)
273                    // remove old to resolve in leaved way to allow collecting next ssaId
274                    // before write (can be different due to earlier visit)
275                    alreadyReadMap.erase(it);
276            }
277            ARDOut << "  popresolv (cache)\n";
278            flowStack.pop_back();
279        }
280    }
281   
282    resSecondPointsCache.put(nextBlock, cacheSecPoints);
283}
284
285// apply calls (changes from these calls) from code blocks to stack var map
286static void applyCallToStackVarMap(const CodeBlock& cblock, const RoutineMap& routineMap,
287        LastSSAIdMap& stackVarMap, BlockIndex blockIndex, size_t nextIndex)
288{
289    for (const NextBlock& next: cblock.nexts)
290        if (next.isCall)
291        {
292            const LastSSAIdMap& regVarMap =
293                    routineMap.find(next.block)->second.lastSSAIdMap;
294            for (const auto& sentry: regVarMap)
295                stackVarMap[sentry.first].clear(); // clearing
296        }
297   
298    for (const NextBlock& next: cblock.nexts)
299        if (next.isCall)
300        {
301            ARDOut << "  applycall: " << blockIndex << ": " <<
302                    nextIndex << ": " << next.block << "\n";
303            const LastSSAIdMap& regVarMap =
304                    routineMap.find(next.block)->second.lastSSAIdMap;
305            for (const auto& sentry: regVarMap)
306                for (size_t s: sentry.second)
307                    stackVarMap.insertSSAId(sentry.first, s);
308        }
309}
310
311
312// main routine to resilve SSA conflicts in code
313// it emits SSA replaces from these conflicts
314static void resolveSSAConflicts(const std::deque<FlowStackEntry2>& prevFlowStack,
315        const RoutineMap& routineMap, const std::vector<CodeBlock>& codeBlocks,
316        const PrevWaysIndexMap& prevWaysIndexMap,
317        const CBlockBitPool& waysToCache, ResSecondPointsToCache& cblocksToCache,
318        SimpleCache<BlockIndex, LastSSAIdMap>& resFirstPointsCache,
319        SimpleCache<BlockIndex, RBWSSAIdMap>& resSecondPointsCache,
320        SSAReplacesMap& replacesMap)
321{
322    BlockIndex nextBlock = prevFlowStack.back().blockIndex;
323    auto pfEnd = prevFlowStack.end();
324    --pfEnd;
325    ARDOut << "startResolv: " << (pfEnd-1)->blockIndex << "," << nextBlock << "\n";
326    LastSSAIdMap stackVarMap;
327   
328    size_t pfStartIndex = 0;
329    {
330        auto pfPrev = pfEnd;
331        --pfPrev;
332        auto it = prevWaysIndexMap.find(pfPrev->blockIndex);
333        if (it != prevWaysIndexMap.end())
334        {
335            const LastSSAIdMap* cached = resFirstPointsCache.use(it->second.first);
336            if (cached!=nullptr)
337            {
338                ARDOut << "use pfcached: " << it->second.first << ", " <<
339                        it->second.second << "\n";
340                stackVarMap = *cached;
341                pfStartIndex = it->second.second+1;
342               
343                // apply missing calls at end of the cached
344                const CodeBlock& cblock = codeBlocks[it->second.first.index];
345               
346                const FlowStackEntry2& entry = *(prevFlowStack.begin()+pfStartIndex-1);
347                if (entry.nextIndex > cblock.nexts.size())
348                    applyCallToStackVarMap(cblock, routineMap, stackVarMap, -1, -1);
349            }
350        }
351    }
352   
353    for (auto pfit = prevFlowStack.begin()+pfStartIndex; pfit != pfEnd; ++pfit)
354    {
355        const FlowStackEntry2& entry = *pfit;
356        ARDOut << "  apply: " << entry.blockIndex << "\n";
357        const CodeBlock& cblock = codeBlocks[entry.blockIndex.index];
358        for (const auto& sentry: cblock.ssaInfoMap)
359        {
360            const SSAInfo& sinfo = sentry.second;
361            if (sinfo.ssaIdChange != 0)
362                stackVarMap[sentry.first] = { sinfo.ssaId + sinfo.ssaIdChange - 1 };
363        }
364        if (entry.nextIndex > cblock.nexts.size())
365            applyCallToStackVarMap(cblock, routineMap, stackVarMap,
366                        entry.blockIndex, entry.nextIndex);
367       
368        // put to first point cache
369        if (waysToCache[pfit->blockIndex] &&
370            !resFirstPointsCache.hasKey(pfit->blockIndex))
371        {
372            ARDOut << "put pfcache " << pfit->blockIndex << "\n";
373            resFirstPointsCache.put(pfit->blockIndex, stackVarMap);
374        }
375    }
376   
377    RBWSSAIdMap cacheSecPoints;
378    const bool toCache = (!resSecondPointsCache.hasKey(nextBlock)) &&
379                cblocksToCache.count(nextBlock)>=2;
380   
381    //std::stack<CallStackEntry> callStack = prevCallStack;
382    // traverse by graph from next block
383    std::deque<FlowStackEntry2> flowStack;
384    flowStack.push_back({ nextBlock, 0 });
385    CBlockBitPool visited(codeBlocks.size(), false);
386   
387    // already read in current path
388    // key - vreg, value - source block where vreg of conflict found
389    std::unordered_map<AsmSingleVReg, BlockIndex> alreadyReadMap;
390   
391    while (!flowStack.empty())
392    {
393        FlowStackEntry2& entry = flowStack.back();
394        const CodeBlock& cblock = codeBlocks[entry.blockIndex.index];
395       
396        if (entry.nextIndex == 0)
397        {
398            // process current block
399            if (!visited[entry.blockIndex])
400            {
401                visited[entry.blockIndex] = true;
402                ARDOut << "  resolv: " << entry.blockIndex << "\n";
403               
404                const RBWSSAIdMap* resSecondPoints =
405                        resSecondPointsCache.use(entry.blockIndex);
406                if (resSecondPoints == nullptr)
407                    for (auto& sentry: cblock.ssaInfoMap)
408                        handleSSAEntryWhileResolving(&replacesMap, &stackVarMap,
409                                alreadyReadMap, entry, sentry,
410                                toCache ? &cacheSecPoints : nullptr);
411                else // to use cache
412                {
413                    useResSecPointCache(&replacesMap, &stackVarMap, alreadyReadMap,
414                            resSecondPoints, entry.blockIndex,
415                            toCache ? &cacheSecPoints : nullptr);
416                    flowStack.pop_back();
417                    continue;
418                }
419            }
420            else
421            {
422                cblocksToCache.increase(entry.blockIndex);
423                ARDOut << "cblockToCache: " << entry.blockIndex << "=" <<
424                            cblocksToCache.count(entry.blockIndex) << "\n";
425                // back, already visited
426                ARDOut << "resolv already: " << entry.blockIndex << "\n";
427                flowStack.pop_back();
428                continue;
429            }
430        }
431       
432        if (entry.nextIndex < cblock.nexts.size())
433        {
434            flowStack.push_back({ { cblock.nexts[entry.nextIndex].block,
435                        entry.blockIndex.pass }, 0 });
436            entry.nextIndex++;
437        }
438        else if (((entry.nextIndex==0 && cblock.nexts.empty()) ||
439                // if have any call then go to next block
440                (cblock.haveCalls && entry.nextIndex==cblock.nexts.size())) &&
441                 !cblock.haveReturn && !cblock.haveEnd)
442        {
443            // add toResolveMap ssaIds inside called routines
444            for (const auto& next: cblock.nexts)
445                if (next.isCall)
446                {
447                    const RoutineData& rdata = routineMap.find(next.block)->second;
448                    for (const auto& v: rdata.rbwSSAIdMap)
449                        alreadyReadMap.insert({v.first, entry.blockIndex });
450                    for (const auto& v: rdata.lastSSAIdMap)
451                        alreadyReadMap.insert({v.first, entry.blockIndex });
452                }
453           
454            flowStack.push_back({ entry.blockIndex+1, 0 });
455            entry.nextIndex++;
456        }
457        else // back
458        {
459            // remove old to resolve in leaved way to allow collecting next ssaId
460            // before write (can be different due to earlier visit)
461            for (const auto& next: cblock.nexts)
462                if (next.isCall)
463                {
464                    const RoutineData& rdata = routineMap.find(next.block)->second;
465                    for (const auto& v: rdata.rbwSSAIdMap)
466                    {
467                        auto it = alreadyReadMap.find(v.first);
468                        if (it != alreadyReadMap.end() && it->second == entry.blockIndex)
469                            alreadyReadMap.erase(it);
470                    }
471                    for (const auto& v: rdata.lastSSAIdMap)
472                    {
473                        auto it = alreadyReadMap.find(v.first);
474                        if (it != alreadyReadMap.end() && it->second == entry.blockIndex)
475                            alreadyReadMap.erase(it);
476                    }
477                }
478           
479            for (const auto& sentry: cblock.ssaInfoMap)
480            {
481                auto it = alreadyReadMap.find(sentry.first);
482                if (it != alreadyReadMap.end() && it->second == entry.blockIndex)
483                    // remove old to resolve in leaved way to allow collecting next ssaId
484                    // before write (can be different due to earlier visit)
485                    alreadyReadMap.erase(it);
486            }
487            ARDOut << "  popresolv\n";
488           
489            if (cblocksToCache.count(entry.blockIndex)==2 &&
490                !resSecondPointsCache.hasKey(entry.blockIndex))
491                // add to cache
492                addResSecCacheEntry(routineMap, codeBlocks, resSecondPointsCache,
493                            entry.blockIndex);
494           
495            flowStack.pop_back();
496        }
497    }
498   
499    if (toCache)
500        resSecondPointsCache.put(nextBlock, cacheSecPoints);
501}
502
503// join ret SSAId Map - src - last SSAIdMap from called routine
504static void joinRetSSAIdMap(RetSSAIdMap& dest, const LastSSAIdMap& src,
505                BlockIndex routineBlock)
506{
507    for (const auto& entry: src)
508    {
509        ARDOut << "  joinRetSSAIdMap: " << entry.first.regVar << ":" <<
510                cxuint(entry.first.index) << ":";
511        for (size_t v: entry.second)
512            ARDOut << " " << v;
513        ARDOut << "\n";
514        // insert if not inserted
515        auto res = dest.insert({entry.first, { { routineBlock }, entry.second } });
516        if (res.second)
517            continue; // added new
518        VectorSet<size_t>& destEntry = res.first->second.ssaIds;
519        res.first->second.routines.push_back(routineBlock);
520        // add new ways
521        for (size_t ssaId: entry.second)
522            destEntry.insertValue(ssaId);
523        ARDOut << "    :";
524        for (size_t v: destEntry)
525            ARDOut << " " << v;
526        ARDOut << "\n";
527    }
528}
529
530// simple join last ssaid map
531static void joinLastSSAIdMap(LastSSAIdMap& dest, const LastSSAIdMap& src)
532{
533    for (const auto& entry: src)
534    {
535        ARDOut << "  joinLastSSAIdMap: " << entry.first.regVar << ":" <<
536                cxuint(entry.first.index) << ":";
537        for (size_t v: entry.second)
538            ARDOut << " " << v;
539        ARDOut << "\n";
540        auto res = dest.insert(entry); // find
541        if (res.second)
542            continue; // added new
543        VectorSet<size_t>& destEntry = res.first->second;
544        // add new ways
545        for (size_t ssaId: entry.second)
546            destEntry.insertValue(ssaId);
547        ARDOut << "    :";
548        for (size_t v: destEntry)
549            ARDOut << " " << v;
550        ARDOut << "\n";
551    }
552}
553
554// join last SSAIdMap of the routine including later routine call
555// dest - dest last SSAId map, src - source lastSSAIdMap
556// laterRdatas - data of subroutine/routine exeuted after src lastSSAIdMap state
557static void joinLastSSAIdMapInt(LastSSAIdMap& dest, const LastSSAIdMap& src,
558                    const LastSSAIdMap& laterRdataCurSSAIdMap,
559                    const LastSSAIdMap& laterRdataLastSSAIdMap, bool loop)
560{
561    for (const auto& entry: src)
562    {
563        auto lsit = laterRdataLastSSAIdMap.find(entry.first);
564        if (lsit != laterRdataLastSSAIdMap.end())
565        {
566            auto csit = laterRdataCurSSAIdMap.find(entry.first);
567            if (csit != laterRdataCurSSAIdMap.end() && !csit->second.empty())
568            {
569                // if found in last ssa ID map,
570                // but has first value (some way do not change SSAId)
571                // then pass to add new ssaIds before this point
572                if (!lsit->second.hasValue(csit->second[0]))
573                    continue; // otherwise, skip
574            }
575        }
576        ARDOut << "  joinLastSSAIdMapInt: " << entry.first.regVar << ":" <<
577                cxuint(entry.first.index) << ":";
578        for (size_t v: entry.second)
579            ARDOut << " " << v;
580        ARDOut << "\n";
581        auto res = dest.insert(entry); // find
582        if (res.second)
583            continue; // added new
584        VectorSet<size_t>& destEntry = res.first->second;
585        // add new ways
586        for (size_t ssaId: entry.second)
587            destEntry.insertValue(ssaId);
588        ARDOut << "    :";
589        for (size_t v: destEntry)
590            ARDOut << " " << v;
591        ARDOut << "\n";
592    }
593    if (!loop) // do not if loop
594        joinLastSSAIdMap(dest, laterRdataLastSSAIdMap);
595}
596
597static void joinLastSSAIdMap(LastSSAIdMap& dest, const LastSSAIdMap& src,
598                    const RoutineData& laterRdata, bool loop = false)
599{
600    joinLastSSAIdMapInt(dest, src, laterRdata.curSSAIdMap, laterRdata.lastSSAIdMap, loop);
601}
602
603
604// join routine data from child call with data from parent routine
605// (just join child call from parent)
606static void joinRoutineData(RoutineData& dest, const RoutineData& src,
607            const std::unordered_map<AsmSingleVReg, size_t>& curSSAIdMap,
608            bool notFirstReturn)
609{
610    // insert readBeforeWrite only if doesnt exists in destination
611    dest.rbwSSAIdMap.insert(src.rbwSSAIdMap.begin(), src.rbwSSAIdMap.end());
612    dest.origRbwSSAIdMap.insert(src.origRbwSSAIdMap.begin(), src.origRbwSSAIdMap.end());
613   
614    //joinLastSSAIdMap(dest.curSSAIdMap, src.lastSSAIdMap);
615   
616    for (const auto& entry: src.lastSSAIdMap)
617    {
618        ARDOut << "  joinRoutineData: " << entry.first.regVar << ":" <<
619                cxuint(entry.first.index) << ":";
620        for (size_t v: entry.second)
621            ARDOut << " " << v;
622        ARDOut << "\n";
623        auto res = dest.curSSAIdMap.insert(entry); // find
624        VectorSet<size_t>& destEntry = res.first->second;
625       
626        if (!res.second)
627        {
628            // add new ways
629            for (size_t ssaId: entry.second)
630                destEntry.insertValue(ssaId);
631        }
632        else if (notFirstReturn)
633        {
634            auto csit = curSSAIdMap.find(entry.first);
635            // insert to lastSSAIdMap if no ssaIds for regvar in lastSSAIdMap
636            dest.lastSSAIdMap.insert({ entry.first,
637                        { (csit!=curSSAIdMap.end() ? csit->second : 1)-1 } });
638        }
639       
640        ARDOut << "    :";
641        for (size_t v: destEntry)
642            ARDOut << " " << v;
643        ARDOut << "\n";
644    }
645}
646
647// reduce retSSAIds for calls (for all read before write SSAIds for current code block)
648static void reduceSSAIdsForCalls(FlowStackEntry& entry,
649            const std::vector<CodeBlock>& codeBlocks,
650            RetSSAIdMap& retSSAIdMap, RoutineMap& routineMap,
651            SSAReplacesMap& ssaReplacesMap)
652{
653    if (retSSAIdMap.empty())
654        return;
655    LastSSAIdMap rbwSSAIdMap;
656    std::unordered_set<AsmSingleVReg> reduced;
657    std::unordered_set<AsmSingleVReg> changed;
658    const CodeBlock& cblock = codeBlocks[entry.blockIndex.index];
659    // collect rbw SSAIds
660    for (const NextBlock next: cblock.nexts)
661        if (next.isCall)
662        {
663            auto it = routineMap.find(next.block); // must find
664            for (const auto& rentry: it->second.rbwSSAIdMap)
665                rbwSSAIdMap.insertSSAId(rentry.first,rentry.second);
666           
667        }
668    for (const NextBlock next: cblock.nexts)
669        if (next.isCall)
670        {
671            auto it = routineMap.find(next.block); // must find
672            // add changed
673            for (const auto& lentry: it->second.lastSSAIdMap)
674                if (rbwSSAIdMap.find(lentry.first) == rbwSSAIdMap.end())
675                    changed.insert(lentry.first);
676        }
677   
678    // reduce SSAIds
679    for (const auto& rentry: retSSAIdMap)
680    {
681        auto ssaIdsIt = rbwSSAIdMap.find(rentry.first);
682        if (ssaIdsIt != rbwSSAIdMap.end())
683        {
684            const VectorSet<size_t>& ssaIds = ssaIdsIt->second;
685            const VectorSet<size_t>& rssaIds = rentry.second.ssaIds;
686            Array<size_t> outSSAIds(ssaIds.size() + rssaIds.size());
687            std::copy(rssaIds.begin(), rssaIds.end(), outSSAIds.begin());
688            std::copy(ssaIds.begin(), ssaIds.end(), outSSAIds.begin()+rssaIds.size());
689           
690            std::sort(outSSAIds.begin(), outSSAIds.end());
691            outSSAIds.resize(std::unique(outSSAIds.begin(), outSSAIds.end()) -
692                        outSSAIds.begin());
693            size_t minSSAId = outSSAIds.front();
694            if (outSSAIds.size() >= 2)
695            {
696                for (auto sit = outSSAIds.begin()+1; sit != outSSAIds.end(); ++sit)
697                    insertReplace(ssaReplacesMap, rentry.first, *sit, minSSAId);
698               
699                ARDOut << "calls retssa ssaid: " << rentry.first.regVar << ":" <<
700                        rentry.first.index << "\n";
701            }
702           
703            for (BlockIndex rblock: rentry.second.routines)
704                routineMap.find(rblock)->second.lastSSAIdMap[rentry.first] =
705                            VectorSet<size_t>({ minSSAId });
706            reduced.insert(rentry.first);
707        }
708    }
709    for (const AsmSingleVReg& vreg: reduced)
710        retSSAIdMap.erase(vreg);
711    reduced.clear();
712       
713    for (const AsmSingleVReg& vreg: changed)
714    {
715        auto rit = retSSAIdMap.find(vreg);
716        if (rit != retSSAIdMap.end())
717        {
718            // if modified
719            // put before removing to revert for other ways after calls
720            auto res = entry.prevRetSSAIdSets.insert(*rit);
721            if (res.second)
722                res.first->second = rit->second;
723            // just remove, if some change without read before
724            retSSAIdMap.erase(rit);
725        }
726    }
727}
728
729static void reduceSSAIds2(std::unordered_map<AsmSingleVReg, size_t>& curSSAIdMap,
730            RetSSAIdMap& retSSAIdMap, FlowStackEntry& entry, const SSAEntry& ssaEntry)
731{
732    const SSAInfo& sinfo = ssaEntry.second;
733    size_t& ssaId = curSSAIdMap[ssaEntry.first];
734    auto ssaIdsIt = retSSAIdMap.find(ssaEntry.first);
735    if (ssaIdsIt != retSSAIdMap.end() && sinfo.readBeforeWrite)
736    {
737        auto& ssaIds = ssaIdsIt->second.ssaIds;
738        ssaId = ssaIds.front()+1; // plus one
739        retSSAIdMap.erase(ssaIdsIt);
740    }
741    else if (ssaIdsIt != retSSAIdMap.end() && sinfo.ssaIdChange!=0)
742    {
743        // put before removing to revert for other ways after calls
744        auto res = entry.prevRetSSAIdSets.insert(*ssaIdsIt);
745        if (res.second)
746            res.first->second = ssaIdsIt->second;
747        // just remove, if some change without read before
748        retSSAIdMap.erase(ssaIdsIt);
749    }
750}
751
752// reduce retSSAIds (last SSAIds for regvar) while passing by code block
753// and emits SSA replaces for these ssaids
754static bool reduceSSAIds(std::unordered_map<AsmSingleVReg, size_t>& curSSAIdMap,
755            RetSSAIdMap& retSSAIdMap, RoutineMap& routineMap,
756            SSAReplacesMap& ssaReplacesMap, FlowStackEntry& entry, SSAEntry& ssaEntry)
757{
758    SSAInfo& sinfo = ssaEntry.second;
759    size_t& ssaId = curSSAIdMap[ssaEntry.first];
760    auto ssaIdsIt = retSSAIdMap.find(ssaEntry.first);
761    if (ssaIdsIt != retSSAIdMap.end() && sinfo.readBeforeWrite)
762    {
763        auto& ssaIds = ssaIdsIt->second.ssaIds;
764       
765        if (sinfo.ssaId != SIZE_MAX)
766        {
767            VectorSet<size_t> outSSAIds = ssaIds;
768            outSSAIds.insertValue(ssaId-1); // ???
769            // already set
770            if (outSSAIds.size() >= 1)
771            {
772                // reduce to minimal ssaId from all calls
773                std::sort(outSSAIds.begin(), outSSAIds.end());
774                outSSAIds.resize(std::unique(outSSAIds.begin(), outSSAIds.end()) -
775                            outSSAIds.begin());
776                // insert SSA replaces
777                if (outSSAIds.size() >= 2)
778                {
779                    size_t minSSAId = outSSAIds.front();
780                    for (auto sit = outSSAIds.begin()+1; sit != outSSAIds.end(); ++sit)
781                        insertReplace(ssaReplacesMap, ssaEntry.first, *sit, minSSAId);
782                }
783            }
784        }
785        else if (ssaIds.size() >= 2)
786        {
787            // reduce to minimal ssaId from all calls
788            std::sort(ssaIds.begin(), ssaIds.end());
789            ssaIds.resize(std::unique(ssaIds.begin(), ssaIds.end()) - ssaIds.begin());
790            // insert SSA replaces
791            size_t minSSAId = ssaIds.front();
792            for (auto sit = ssaIds.begin()+1; sit != ssaIds.end(); ++sit)
793                insertReplace(ssaReplacesMap, ssaEntry.first, *sit, minSSAId);
794            ssaId = minSSAId+1; // plus one
795        }
796        else if (ssaIds.size() == 1)
797            ssaId = ssaIds.front()+1; // plus one
798       
799        ARDOut << "retssa ssaid: " << ssaEntry.first.regVar << ":" <<
800                ssaEntry.first.index << ": " << ssaId << "\n";
801        // replace smallest ssaId in routineMap lastSSAId entry
802        // reduce SSAIds replaces
803        for (BlockIndex rblock: ssaIdsIt->second.routines)
804        {
805            RoutineData& rdata = routineMap.find(rblock)->second;
806            size_t rbwRetSSAId = SIZE_MAX;
807            auto rbwIt = rdata.rbwSSAIdMap.find(ssaEntry.first);
808            auto rlsit = rdata.lastSSAIdMap.find(ssaEntry.first);
809            if (rbwIt != rdata.rbwSSAIdMap.end() && rlsit->second.hasValue(rbwIt->second))
810                rbwRetSSAId = rbwIt->second;
811            rlsit->second = VectorSet<size_t>({ ssaId-1 });
812            if (rbwRetSSAId != SIZE_MAX)
813            {
814                ARDOut << "  keep retSSAId rbw: " << rbwRetSSAId << "\n";
815                // add retSSAId without changes (in way without regvar changes)
816                rlsit->second.insertValue(rbwRetSSAId);
817            }
818        }
819        // finally remove from container (because obsolete)
820        retSSAIdMap.erase(ssaIdsIt);
821        return true;
822    }
823    else if (ssaIdsIt != retSSAIdMap.end() && sinfo.ssaIdChange!=0)
824    {
825        // put before removing to revert for other ways after calls
826        auto res = entry.prevRetSSAIdSets.insert(*ssaIdsIt);
827        if (res.second)
828            res.first->second = ssaIdsIt->second;
829        // just remove, if some change without read before
830        retSSAIdMap.erase(ssaIdsIt);
831    }
832    return false;
833}
834
835// update single current SSAId for routine and optionally lastSSAIdMap if returns
836// has been encountered but not regvar
837static void updateRoutineData(RoutineData& rdata, const SSAEntry& ssaEntry,
838                size_t prevSSAId)
839{
840    const SSAInfo& sinfo = ssaEntry.second;
841    bool beforeFirstAccess = true;
842    // put first SSAId before write
843    if (sinfo.readBeforeWrite)
844    {
845        //ARDOut << "PutCRBW: " << sinfo.ssaIdBefore << "\n";
846        if (!rdata.rbwSSAIdMap.insert({ ssaEntry.first, prevSSAId }).second)
847            // if already added
848            beforeFirstAccess = false;
849       
850        rdata.origRbwSSAIdMap.insert({ ssaEntry.first,
851                        ssaEntry.second.ssaIdBefore }).second;
852    }
853   
854    if (sinfo.ssaIdChange != 0)
855    {
856        //ARDOut << "PutC: " << sinfo.ssaIdLast << "\n";
857        auto res = rdata.curSSAIdMap.insert({ ssaEntry.first, { sinfo.ssaIdLast } });
858        // put last SSAId
859        if (!res.second)
860        {
861            beforeFirstAccess = false;
862            // if not inserted
863            VectorSet<size_t>& ssaIds = res.first->second;
864            ssaIds.clear(); // clear all ssaIds in currentSSAID entry
865            ssaIds.insertValue(sinfo.ssaIdLast);
866        }
867        // add readbefore if in previous returns if not added yet
868        if (rdata.notFirstReturn && beforeFirstAccess)
869        {
870            rdata.lastSSAIdMap.insert({ ssaEntry.first, { prevSSAId } });
871            for (auto& loopEnd: rdata.loopEnds)
872                loopEnd.second.ssaIdMap.insert({ ssaEntry.first, { prevSSAId } });
873        }
874    }
875    else
876    {
877        // insert read ssaid if no change
878        auto res = rdata.curSSAIdMap.insert({ ssaEntry.first, { prevSSAId } });
879        if (!res.second)
880        {
881            VectorSet<size_t>& ssaIds = res.first->second;
882            ssaIds.insertValue(prevSSAId);
883        }
884    }
885}
886
887static void initializePrevRetSSAIds(
888            const std::unordered_map<AsmSingleVReg, size_t>& curSSAIdMap,
889            const RetSSAIdMap& retSSAIdMap, const RoutineData& rdata,
890            FlowStackEntry& entry)
891{
892    for (const auto& v: rdata.lastSSAIdMap)
893    {
894        auto res = entry.prevRetSSAIdSets.insert({v.first, {}});
895        if (!res.second)
896            continue; // already added, do not change
897        auto rfit = retSSAIdMap.find(v.first);
898        if (rfit != retSSAIdMap.end())
899            res.first->second = rfit->second;
900       
901        auto csit = curSSAIdMap.find(v.first);
902        res.first->second.prevSSAId = (csit!=curSSAIdMap.end() ? csit->second : 1);
903    }
904}
905
906// revert retSSAIdMap while leaving from code block
907static void revertRetSSAIdMap(std::unordered_map<AsmSingleVReg, size_t>& curSSAIdMap,
908            RetSSAIdMap& retSSAIdMap, FlowStackEntry& entry, RoutineData* rdata)
909{
910    // revert retSSAIdMap
911    for (auto v: entry.prevRetSSAIdSets)
912    {
913        auto rfit = retSSAIdMap.find(v.first);
914        if (rdata!=nullptr && rfit != retSSAIdMap.end())
915        {
916            VectorSet<size_t>& ssaIds = rdata->curSSAIdMap[v.first];
917            for (size_t ssaId: rfit->second.ssaIds)
918                ssaIds.eraseValue(ssaId);
919        }
920       
921        if (!v.second.ssaIds.empty())
922        {
923            // just add if previously present
924            if (rfit != retSSAIdMap.end())
925                rfit->second = v.second;
926            else
927                retSSAIdMap.insert(v);
928        }
929        else // erase if empty
930            retSSAIdMap.erase(v.first);
931       
932        size_t oldSSAId = curSSAIdMap[v.first]-1;
933        curSSAIdMap[v.first] = v.second.prevSSAId;
934        if (rdata!=nullptr)
935        {
936            VectorSet<size_t>& ssaIds = rdata->curSSAIdMap[v.first];
937            ssaIds.eraseValue(oldSSAId); // ??? need extra constraints
938            for (size_t ssaId: v.second.ssaIds)
939                ssaIds.insertValue(ssaId);
940            if (v.second.ssaIds.empty())
941            {
942                auto cit = curSSAIdMap.find(v.first);
943                ssaIds.insertValue((cit!=curSSAIdMap.end() ? cit->second : 1)-1);
944            }
945           
946            ARDOut << " revertSSAIdPopEntry" << entry.blockIndex << ": " <<
947                    v.first.regVar << ":" << v.first.index << ":";
948            for (size_t v: ssaIds)
949                ARDOut << " " << v;
950            ARDOut << "\n";
951        }
952    }
953}
954
955// update current SSAId in curSSAIdMap for routine while leaving from code block
956static void updateRoutineCurSSAIdMap(RoutineData* rdata, const SSAEntry& ssaEntry,
957            const FlowStackEntry& entry, size_t curSSAId, size_t nextSSAId)
958{
959    VectorSet<size_t>& ssaIds = rdata->curSSAIdMap[ssaEntry.first];
960    ARDOut << " updateRoutineCurSSAIdMap " << entry.blockIndex << ": " <<
961                ssaEntry.first.regVar << ":" << ssaEntry.first.index << ":";
962    for (size_t v: ssaIds)
963        ARDOut << " " << v;
964    ARDOut << "\n";
965   
966    // if cblock with some children
967    if (nextSSAId != curSSAId)
968        ssaIds.eraseValue(nextSSAId-1);
969   
970    // push previous SSAId to lastSSAIdMap (later will be replaced)
971    ssaIds.insertValue(curSSAId-1);
972   
973    ARDOut << " updateRoutineCurSSAIdMap after " << entry.blockIndex << ": " <<
974                ssaEntry.first.regVar << ":" << ssaEntry.first.index << ":";
975    for (size_t v: ssaIds)
976        ARDOut << " " << v;
977    ARDOut << "\n";
978}
979
980static bool tryAddLoopEnd(const FlowStackEntry& entry, BlockIndex routineBlock,
981                RoutineData& rdata, bool isLoop, bool noMainLoop)
982{
983    if (isLoop && (!noMainLoop || routineBlock != entry.blockIndex))
984    {
985        // handle loops
986        ARDOut << "  join loop ssaids: " << entry.blockIndex << "\n";
987        // add to routine data loopEnds
988        auto loopsit2 = rdata.loopEnds.find(entry.blockIndex);
989        if (loopsit2 != rdata.loopEnds.end())
990        {
991            if (!loopsit2->second.passed)
992                // still in loop join ssaid map
993                joinLastSSAIdMap(loopsit2->second.ssaIdMap, rdata.curSSAIdMap);
994        }
995        else
996            rdata.loopEnds.insert({ entry.blockIndex, { rdata.curSSAIdMap, false } });
997        return true;
998    }
999    return false;
1000}
1001
1002
1003static void createRoutineData(const std::vector<CodeBlock>& codeBlocks,
1004        std::unordered_map<AsmSingleVReg, size_t>& curSSAIdMap,
1005        const std::unordered_set<BlockIndex>& loopBlocks,
1006        const std::unordered_set<BlockIndex>& callBlocks,
1007        const ResSecondPointsToCache& subroutToCache,
1008        SimpleCache<BlockIndex, RoutineData>& subroutinesCache,
1009        const RoutineMap& routineMap, RoutineData& rdata,
1010        BlockIndex routineBlock, bool noMainLoop = false,
1011        const CBlockBitPool& prevFlowStackBlocks = {})
1012{
1013    ARDOut << "--------- createRoutineData ----------------\n";
1014    CBlockBitPool visited(codeBlocks.size(), false);
1015    CBlockBitPool haveReturnBlocks(codeBlocks.size(), false);
1016   
1017    VectorSet<BlockIndex> activeLoops;
1018    SubrLoopsMap subrLoopsMap;
1019    SubrLoopsMap loopSubrsMap;
1020    RoutineMap subrDataForLoopMap;
1021    std::deque<FlowStackEntry> flowStack;
1022    CBlockBitPool flowStackBlocks(codeBlocks.size(), false);
1023    if (!prevFlowStackBlocks.empty())
1024        flowStackBlocks = prevFlowStackBlocks;
1025    // last SSA ids map from returns
1026    RetSSAIdMap retSSAIdMap;
1027    flowStack.push_back({ routineBlock, 0 });
1028    flowStackBlocks[routineBlock] = true;
1029   
1030   
1031    while (!flowStack.empty())
1032    {
1033        FlowStackEntry& entry = flowStack.back();
1034        const CodeBlock& cblock = codeBlocks[entry.blockIndex.index];
1035       
1036        auto addSubroutine = [&](
1037            std::unordered_map<BlockIndex, LoopSSAIdMap>::const_iterator loopsit2,
1038            bool applyToMainRoutine)
1039        {
1040            if (subroutinesCache.hasKey(entry.blockIndex))
1041            {
1042                // if already put, just applyToMainRoutine if needed
1043                if (applyToMainRoutine &&
1044                    loopBlocks.find(entry.blockIndex) != loopBlocks.end() &&
1045                    loopsit2 != rdata.loopEnds.end())
1046                {
1047                    RoutineData* subRdata = subroutinesCache.use(entry.blockIndex);
1048                    joinLastSSAIdMap(rdata.lastSSAIdMap, loopsit2->second.ssaIdMap,
1049                                        *subRdata, true);
1050                }
1051                return;
1052            }
1053           
1054            RoutineData subrData;
1055            const bool oldFB = flowStackBlocks[entry.blockIndex];
1056            flowStackBlocks[entry.blockIndex] = !oldFB;
1057            createRoutineData(codeBlocks, curSSAIdMap, loopBlocks, callBlocks,
1058                    subroutToCache, subroutinesCache, routineMap, subrData,
1059                    entry.blockIndex, true, flowStackBlocks);
1060            RoutineData subrDataCopy;
1061            flowStackBlocks[entry.blockIndex] = oldFB;
1062           
1063            if (loopBlocks.find(entry.blockIndex) != loopBlocks.end())
1064            {   // leave from loop point
1065                ARDOut << "   loopfound " << entry.blockIndex << "\n";
1066                if (loopsit2 != rdata.loopEnds.end())
1067                {
1068                    subrDataCopy = subrData;
1069                    subrDataForLoopMap.insert({ entry.blockIndex, subrDataCopy });
1070                    ARDOut << "   loopssaId2Map: " <<
1071                            entry.blockIndex << "\n";
1072                    joinLastSSAIdMap(subrData.lastSSAIdMap,
1073                            loopsit2->second.ssaIdMap, subrData, true);
1074                    ARDOut << "   loopssaIdMap2End: \n";
1075                    if (applyToMainRoutine)
1076                        joinLastSSAIdMap(rdata.lastSSAIdMap, loopsit2->second.ssaIdMap,
1077                                        subrDataCopy, true);
1078                }
1079            }
1080           
1081            // apply loop to subroutines
1082            auto it = loopSubrsMap.find(entry.blockIndex);
1083            if (it != loopSubrsMap.end())
1084            {
1085                ARDOut << "    found loopsubrsmap: " << entry.blockIndex << ":";
1086                for (BlockIndex subr: it->second)
1087                {
1088                    ARDOut << " " << subr;
1089                    RoutineData* subrData2 = subroutinesCache.use(subr);
1090                    if (subrData2 == nullptr)
1091                        continue;
1092                    RoutineData subrData2Copy = *subrData2;
1093                    ARDOut << "*";
1094                    joinLastSSAIdMap(subrData2Copy.lastSSAIdMap,
1095                            loopsit2->second.ssaIdMap, subrDataCopy, false);
1096                    // reinsert subroutine into subroutine cache
1097                    subrData2Copy.calculateWeight();
1098                    subroutinesCache.put(subr, subrData2Copy);
1099                }
1100                ARDOut << "\n";
1101            }
1102            // apply loops to this subroutine
1103            auto it2 = subrLoopsMap.find(entry.blockIndex);
1104            if (it2 != subrLoopsMap.end())
1105            {
1106                ARDOut << "    found subrloopsmap: " << entry.blockIndex << ":";
1107                for (auto lit2 = it2->second.rbegin(); lit2 != it2->second.rend(); ++lit2)
1108                {
1109                    BlockIndex loop = *lit2;
1110                    auto loopsit3 = rdata.loopEnds.find(loop);
1111                    if (loopsit3 == rdata.loopEnds.end() ||
1112                        activeLoops.hasValue(loop))
1113                        continue;
1114                    ARDOut << " " << loop;
1115                    auto  itx = subrDataForLoopMap.find(loop);
1116                    if (itx != subrDataForLoopMap.end())
1117                        joinLastSSAIdMap(subrData.lastSSAIdMap,
1118                                loopsit3->second.ssaIdMap, itx->second, false);
1119                }
1120                ARDOut << "\n";
1121            }
1122           
1123            subrData.calculateWeight();
1124            subroutinesCache.put(entry.blockIndex, subrData);
1125        };
1126       
1127        if (entry.nextIndex == 0)
1128        {
1129            bool isLoop = loopBlocks.find(entry.blockIndex) != loopBlocks.end();
1130           
1131            if (!prevFlowStackBlocks.empty() && prevFlowStackBlocks[entry.blockIndex])
1132            {
1133                tryAddLoopEnd(entry, routineBlock, rdata, isLoop, noMainLoop);
1134               
1135                flowStackBlocks[entry.blockIndex] = !flowStackBlocks[entry.blockIndex];
1136                flowStack.pop_back();
1137                continue;
1138            }
1139           
1140            // process current block
1141            const RoutineData* cachedRdata = nullptr;
1142           
1143            if (routineBlock != entry.blockIndex)
1144            {
1145                cachedRdata = subroutinesCache.use(entry.blockIndex);
1146                if (cachedRdata == nullptr)
1147                {
1148                    // try in routine map
1149                    auto rit = routineMap.find(entry.blockIndex);
1150                    if (rit != routineMap.end())
1151                        cachedRdata = &rit->second;
1152                }
1153                if (!isLoop && visited[entry.blockIndex] && cachedRdata == nullptr &&
1154                    subroutToCache.count(entry.blockIndex)!=0)
1155                {
1156                    auto loopsit2 = rdata.loopEnds.find(entry.blockIndex);
1157                    ARDOut << "-- subrcache2 for " << entry.blockIndex << "\n";
1158                    addSubroutine(loopsit2, false);
1159                    cachedRdata = subroutinesCache.use(entry.blockIndex);
1160                }
1161            }
1162           
1163            if (cachedRdata != nullptr)
1164            {
1165                ARDOut << "use cached subr " << entry.blockIndex << "\n";
1166                ARDOut << "procret2: " << entry.blockIndex << "\n";
1167                if (visited[entry.blockIndex] && !haveReturnBlocks[entry.blockIndex])
1168                {
1169                    // no joining. no returns
1170                    ARDOut << "procretend2 nojoin\n";
1171                    flowStackBlocks[entry.blockIndex] = !flowStackBlocks[entry.blockIndex];
1172                    flowStack.pop_back();
1173                    continue;
1174                }
1175                joinLastSSAIdMap(rdata.lastSSAIdMap, rdata.curSSAIdMap, *cachedRdata);
1176                // get not given rdata curSSAIdMap ssaIds but present in cachedRdata
1177                // curSSAIdMap
1178                for (const auto& entry: cachedRdata->curSSAIdMap)
1179                    if (rdata.curSSAIdMap.find(entry.first) == rdata.curSSAIdMap.end())
1180                    {
1181                        auto cit = curSSAIdMap.find(entry.first);
1182                        size_t prevSSAId = (cit!=curSSAIdMap.end() ? cit->second : 1)-1;
1183                        rdata.curSSAIdMap.insert({ entry.first, { prevSSAId } });
1184                       
1185                        if (rdata.notFirstReturn)
1186                        {
1187                            rdata.lastSSAIdMap.insertSSAId(entry.first, prevSSAId);
1188                            for (auto& loopEnd: rdata.loopEnds)
1189                                loopEnd.second.ssaIdMap.
1190                                        insertSSAId(entry.first, prevSSAId);
1191                        }
1192                    }
1193               
1194                // join loopEnds
1195                for (const auto& loopEnd: cachedRdata->loopEnds)
1196                {
1197                    auto res = rdata.loopEnds.insert({ loopEnd.first, LoopSSAIdMap{} });
1198                    // true - do not add cached rdata loopend, because it was added
1199                    joinLastSSAIdMapInt(res.first->second.ssaIdMap, rdata.curSSAIdMap,
1200                                cachedRdata->curSSAIdMap, loopEnd.second.ssaIdMap, true);
1201                }
1202                ARDOut << "procretend2\n";
1203                flowStackBlocks[entry.blockIndex] = !flowStackBlocks[entry.blockIndex];
1204                flowStack.pop_back();
1205                // propagate haveReturn to previous block
1206                flowStack.back().haveReturn = true;
1207                haveReturnBlocks[flowStack.back().blockIndex] = true;
1208                continue;
1209            }
1210            else if (!visited[entry.blockIndex])
1211            {
1212                // set up loops for which subroutine is present
1213                if (subroutToCache.count(entry.blockIndex)!=0 && !activeLoops.empty())
1214                {
1215                    subrLoopsMap.insert({ entry.blockIndex, activeLoops });
1216                    for (BlockIndex loop: activeLoops)
1217                    {
1218                        auto res = loopSubrsMap.insert({ loop, { entry.blockIndex } });
1219                        if (!res.second)
1220                            res.first->second.insertValue(entry.blockIndex);
1221                    }
1222                }
1223               
1224                if (loopBlocks.find(entry.blockIndex) != loopBlocks.end())
1225                    activeLoops.insertValue(entry.blockIndex);
1226                ARDOut << "proc: " << entry.blockIndex << "\n";
1227                visited[entry.blockIndex] = true;
1228               
1229                for (const auto& ssaEntry: cblock.ssaInfoMap)
1230                    if (ssaEntry.first.regVar != nullptr)
1231                    {
1232                        reduceSSAIds2(curSSAIdMap, retSSAIdMap, entry, ssaEntry);
1233                        // put data to routine data
1234                        updateRoutineData(rdata, ssaEntry, curSSAIdMap[ssaEntry.first]-1);
1235                       
1236                        if (ssaEntry.second.ssaIdChange!=0)
1237                            curSSAIdMap[ssaEntry.first] = ssaEntry.second.ssaIdLast+1;
1238                    }
1239            }
1240            else
1241            {
1242                tryAddLoopEnd(entry, routineBlock, rdata, isLoop, noMainLoop);
1243                flowStackBlocks[entry.blockIndex] = !flowStackBlocks[entry.blockIndex];
1244                flowStack.pop_back();
1245                continue;
1246            }
1247        }
1248       
1249        // join and skip calls
1250        {
1251            std::vector<BlockIndex> calledRoutines;
1252            for (; entry.nextIndex < cblock.nexts.size() &&
1253                        cblock.nexts[entry.nextIndex].isCall; entry.nextIndex++)
1254            {
1255                BlockIndex rblock = cblock.nexts[entry.nextIndex].block;
1256                if (callBlocks.find(rblock) != callBlocks.end())
1257                    rblock.pass = 1;
1258                if (rblock != routineBlock)
1259                    calledRoutines.push_back(rblock);
1260            }
1261           
1262            if (!calledRoutines.empty())
1263            {
1264                // toNotClear - regvar to no keep (because is used in called routines)
1265                std::unordered_set<AsmSingleVReg> toNotClear;
1266                // if regvar any called routine (used)
1267                std::unordered_set<AsmSingleVReg> allInCalls;
1268                for (BlockIndex rblock: calledRoutines)
1269                {
1270                    const RoutineData& srcRdata = routineMap.find(rblock)->second;
1271                    // for next recursion pass call - choose origRvwSSAIdMap
1272                    // otherwise - standard rbwSsaIdMap
1273                    const std::unordered_map<AsmSingleVReg, size_t>& srcRbwSSAIdMap =
1274                        (entry.blockIndex.pass == 0 && rblock.pass!=0) ?
1275                        srcRdata.origRbwSSAIdMap : srcRdata.rbwSSAIdMap;
1276                    if (entry.blockIndex.pass == 0 && rblock.pass!=0)
1277                        ARDOut << "choose origRbwSSAIdMap: " << rblock << "\n";
1278                       
1279                    for (const auto& rbw: srcRbwSSAIdMap)
1280                    {
1281                        allInCalls.insert(rbw.first);
1282                        auto lsit = srcRdata.lastSSAIdMap.find(rbw.first);
1283                        if (lsit != srcRdata.lastSSAIdMap.end() &&
1284                             lsit->second.hasValue(rbw.second))
1285                            // if returned not modified, then do not clear this regvar
1286                            toNotClear.insert(rbw.first);
1287                    }
1288                    for (const auto& rbw: srcRdata.lastSSAIdMap)
1289                        allInCalls.insert(rbw.first);
1290                }
1291                for (auto& entry: rdata.curSSAIdMap)
1292                    // if any called routine and if to clear
1293                    if (allInCalls.find(entry.first) != allInCalls.end() &&
1294                        toNotClear.find(entry.first) == toNotClear.end())
1295                        // not found
1296                        entry.second.clear();
1297           
1298                for (BlockIndex rblock: calledRoutines)
1299                    joinRoutineData(rdata, routineMap.find(rblock)->second,
1300                                    curSSAIdMap, rdata.notFirstReturn);
1301            }
1302        }
1303       
1304        if (entry.nextIndex < cblock.nexts.size())
1305        {
1306            const BlockIndex nextBlock = { cblock.nexts[entry.nextIndex].block,
1307                        entry.blockIndex.pass };
1308            flowStack.push_back({ nextBlock, 0 });
1309            // negate - if true (already in flowstack, then popping keep this state)
1310            flowStackBlocks[nextBlock] = !flowStackBlocks[nextBlock];
1311            entry.nextIndex++;
1312        }
1313        else if (((entry.nextIndex==0 && cblock.nexts.empty()) ||
1314                // if have any call then go to next block
1315                (cblock.haveCalls && entry.nextIndex==cblock.nexts.size())) &&
1316                 !cblock.haveReturn && !cblock.haveEnd)
1317        {
1318            if (entry.nextIndex!=0) // if back from calls (just return from calls)
1319            {
1320                for (const NextBlock& next: cblock.nexts)
1321                    if (next.isCall)
1322                    {
1323                        //ARDOut << "joincall:"<< next.block << "\n";
1324                        BlockIndex rblock(next.block, entry.blockIndex.pass);
1325                        if (callBlocks.find(next.block) != callBlocks.end())
1326                            rblock.pass = 1;
1327                        auto it = routineMap.find(rblock); // must find
1328                        initializePrevRetSSAIds(curSSAIdMap, retSSAIdMap,
1329                                    it->second, entry);
1330                       
1331                        joinRetSSAIdMap(retSSAIdMap, it->second.lastSSAIdMap, rblock);
1332                    }
1333            }
1334            const BlockIndex nextBlock = entry.blockIndex+1;
1335            flowStack.push_back({ nextBlock, 0 });
1336            // negate - if true (already in flowstack, then popping keep this state)
1337            flowStackBlocks[nextBlock] = !flowStackBlocks[nextBlock];
1338            entry.nextIndex++;
1339        }
1340        else
1341        {
1342            ARDOut << "popstart: " << entry.blockIndex << "\n";
1343            if (cblock.haveReturn)
1344            {
1345                ARDOut << "procret: " << entry.blockIndex << "\n";
1346                joinLastSSAIdMap(rdata.lastSSAIdMap, rdata.curSSAIdMap);
1347                ARDOut << "procretend\n";
1348                rdata.notFirstReturn = true;
1349                entry.haveReturn = true;
1350                haveReturnBlocks[entry.blockIndex] = true;
1351            }
1352           
1353            const bool curHaveReturn = entry.haveReturn;
1354           
1355            // revert retSSAIdMap
1356            revertRetSSAIdMap(curSSAIdMap, retSSAIdMap, entry, &rdata);
1357            //
1358           
1359            for (const auto& ssaEntry: cblock.ssaInfoMap)
1360            {
1361                if (ssaEntry.first.regVar == nullptr)
1362                    continue;
1363                size_t curSSAId = ssaEntry.second.ssaIdBefore+1;
1364                size_t nextSSAId = (ssaEntry.second.ssaIdLast != SIZE_MAX) ?
1365                    ssaEntry.second.ssaIdLast+1 : curSSAId;
1366                curSSAIdMap[ssaEntry.first] = curSSAId;
1367               
1368                ARDOut << "popcurnext: " << ssaEntry.first.regVar <<
1369                            ":" << ssaEntry.first.index << ": " <<
1370                            nextSSAId << ", " << curSSAId << "\n";
1371               
1372                updateRoutineCurSSAIdMap(&rdata, ssaEntry, entry, curSSAId, nextSSAId);
1373            }
1374           
1375            activeLoops.eraseValue(entry.blockIndex);
1376           
1377            auto loopsit2 = rdata.loopEnds.find(entry.blockIndex);
1378            if (loopBlocks.find(entry.blockIndex) != loopBlocks.end())
1379            {
1380                if (loopsit2 != rdata.loopEnds.end())
1381                {
1382                    ARDOut << "   mark loopblocks passed: " <<
1383                                entry.blockIndex << "\n";
1384                    // mark that loop has passed fully
1385                    loopsit2->second.passed = true;
1386                }
1387                else
1388                    ARDOut << "   loopblocks nopassed: " <<
1389                                entry.blockIndex << "\n";
1390            }
1391           
1392            if ((!noMainLoop || flowStack.size() > 1) &&
1393                subroutToCache.count(entry.blockIndex)!=0)
1394            { //put to cache
1395                ARDOut << "-- subrcache for " << entry.blockIndex << "\n";
1396                addSubroutine(loopsit2, true);
1397            }
1398           
1399            flowStackBlocks[entry.blockIndex] = false;
1400            ARDOut << "pop: " << entry.blockIndex << "\n";
1401           
1402            flowStack.pop_back();
1403            // set up haveReturn
1404            if (!flowStack.empty())
1405            {
1406                flowStack.back().haveReturn |= curHaveReturn;
1407                haveReturnBlocks[flowStack.back().blockIndex] =
1408                        flowStack.back().haveReturn;
1409            }
1410        }
1411    }
1412    ARDOut << "--------- createRoutineData end ------------\n";
1413}
1414
1415void AsmRegAllocator::createSSAData(ISAUsageHandler& usageHandler)
1416{
1417    if (codeBlocks.empty())
1418        return;
1419    usageHandler.rewind();
1420    auto cbit = codeBlocks.begin();
1421    AsmRegVarUsage rvu;
1422    if (!usageHandler.hasNext())
1423        return; // do nothing if no regusages
1424    rvu = usageHandler.nextUsage();
1425   
1426    cxuint regRanges[MAX_REGTYPES_NUM*2];
1427    cxuint realRegsCount[MAX_REGTYPES_NUM];
1428    std::fill(realRegsCount, realRegsCount+MAX_REGTYPES_NUM, 0);
1429    size_t regTypesNum;
1430    assembler.isaAssembler->getRegisterRanges(regTypesNum, regRanges);
1431   
1432    while (true)
1433    {
1434        while (cbit != codeBlocks.end() && cbit->end <= rvu.offset)
1435        {
1436            cbit->usagePos = usageHandler.getReadPos();
1437            ++cbit;
1438        }
1439        if (cbit == codeBlocks.end())
1440            break;
1441        // skip rvu's before codeblock
1442        while (rvu.offset < cbit->start && usageHandler.hasNext())
1443            rvu = usageHandler.nextUsage();
1444        if (rvu.offset < cbit->start)
1445            break;
1446       
1447        cbit->usagePos = usageHandler.getReadPos();
1448        while (rvu.offset < cbit->end)
1449        {
1450            // process rvu
1451            // only if regVar
1452            for (uint16_t rindex = rvu.rstart; rindex < rvu.rend; rindex++)
1453            {
1454                auto res = cbit->ssaInfoMap.insert(
1455                        { AsmSingleVReg{ rvu.regVar, rindex }, SSAInfo() });
1456               
1457                SSAInfo& sinfo = res.first->second;
1458                if (res.second)
1459                    sinfo.firstPos = rvu.offset;
1460                if ((rvu.rwFlags & ASMRVU_READ) != 0 && (sinfo.ssaIdChange == 0 ||
1461                    // if first write RVU instead read RVU
1462                    (sinfo.ssaIdChange == 1 && sinfo.firstPos==rvu.offset)))
1463                    sinfo.readBeforeWrite = true;
1464                /* change SSA id only for write-only regvars -
1465                 *   read-write place can not have two different variables */
1466                if (rvu.rwFlags == ASMRVU_WRITE && rvu.regField!=ASMFIELD_NONE)
1467                    sinfo.ssaIdChange++;
1468                if (rvu.regVar==nullptr)
1469                    sinfo.ssaIdBefore = sinfo.ssaIdFirst =
1470                            sinfo.ssaId = sinfo.ssaIdLast = 0;
1471            }
1472            // get next rvusage
1473            if (!usageHandler.hasNext())
1474                break;
1475            rvu = usageHandler.nextUsage();
1476        }
1477        ++cbit;
1478    }
1479   
1480    size_t rbwCount = 0;
1481    size_t wrCount = 0;
1482   
1483    SimpleCache<BlockIndex, RoutineData> subroutinesCache(codeBlocks.size()<<3);
1484   
1485    std::deque<CallStackEntry> callStack;
1486    std::deque<FlowStackEntry> flowStack;
1487    // total SSA count
1488    std::unordered_map<AsmSingleVReg, size_t> totalSSACountMap;
1489    // last SSA ids map from returns
1490    RetSSAIdMap retSSAIdMap;
1491    // last SSA ids in current way in code flow
1492    std::unordered_map<AsmSingleVReg, size_t> curSSAIdMap;
1493    // routine map - routine datas map, value - last SSA ids map
1494    RoutineMap routineMap;
1495    // key - current res first key, value - previous first key and its flowStack pos
1496    PrevWaysIndexMap prevWaysIndexMap;
1497    // to track ways last block indices pair: block index, flowStackPos)
1498    std::pair<BlockIndex, size_t> lastCommonCacheWayPoint{ SIZE_MAX, SIZE_MAX };
1499    CBlockBitPool isRoutineGen(codeBlocks.size(), false);
1500   
1501    CBlockBitPool waysToCache(codeBlocks.size(), false);
1502    CBlockBitPool flowStackBlocks(codeBlocks.size(), false);
1503    // subroutToCache - true if given block begin subroutine to cache
1504    ResSecondPointsToCache cblocksToCache(codeBlocks.size());
1505    CBlockBitPool visited(codeBlocks.size(), false);
1506    flowStack.push_back({ 0, 0 });
1507    flowStackBlocks[0] = true;
1508    std::unordered_set<BlockIndex> callBlocks;
1509    std::unordered_set<BlockIndex> loopBlocks;
1510    std::unordered_set<size_t> recurseBlocks;
1511   
1512    /** INFO if you want to get code changedRegVars between recursions you get 3984
1513     * this stuff has been deleted */
1514   
1515    std::unordered_map<size_t, std::unordered_map<AsmSingleVReg, size_t> >
1516            curSSAIdMapStateMap;
1517   
1518    /*
1519     * main loop to fill up ssaInfos
1520     */
1521    while (!flowStack.empty())
1522    {
1523        FlowStackEntry& entry = flowStack.back();
1524        CodeBlock& cblock = codeBlocks[entry.blockIndex.index];
1525       
1526        if (entry.nextIndex == 0)
1527        {
1528            // process current block
1529            if (!visited[entry.blockIndex])
1530            {
1531                ARDOut << "proc: " << entry.blockIndex << "\n";
1532                visited[entry.blockIndex] = true;
1533               
1534                for (auto& ssaEntry: cblock.ssaInfoMap)
1535                {
1536                    SSAInfo& sinfo = ssaEntry.second;
1537                    if (ssaEntry.first.regVar==nullptr)
1538                    {
1539                        // TODO - pass registers through SSA marking and resolving
1540                        sinfo.ssaIdChange = 0; // zeroing SSA changes
1541                        continue; // no change for registers
1542                    }
1543                   
1544                    if (sinfo.ssaId != SIZE_MAX)
1545                    {
1546                        // already initialized
1547                        reduceSSAIds(curSSAIdMap, retSSAIdMap,
1548                                routineMap, ssaReplacesMap, entry, ssaEntry);
1549                        if (sinfo.ssaIdChange!=0)
1550                            curSSAIdMap[ssaEntry.first] = sinfo.ssaIdLast+1;
1551                       
1552                        // count read before writes (for cache weight)
1553                        if (sinfo.readBeforeWrite)
1554                            rbwCount++;
1555                        if (sinfo.ssaIdChange!=0)
1556                            wrCount++;
1557                        continue;
1558                    }
1559                   
1560                    bool reducedSSAId = reduceSSAIds(curSSAIdMap, retSSAIdMap,
1561                                routineMap, ssaReplacesMap, entry, ssaEntry);
1562                   
1563                    size_t& ssaId = curSSAIdMap[ssaEntry.first];
1564                   
1565                    size_t& totalSSACount = totalSSACountMap[ssaEntry.first];
1566                    if (totalSSACount == 0)
1567                    {
1568                        // first read before write at all, need change totalcount, ssaId
1569                        ssaId++;
1570                        totalSSACount++;
1571                    }
1572                   
1573                    sinfo.ssaId = totalSSACount;
1574                    sinfo.ssaIdFirst = sinfo.ssaIdChange!=0 ? totalSSACount : SIZE_MAX;
1575                    sinfo.ssaIdBefore = ssaId-1;
1576                   
1577                    totalSSACount += sinfo.ssaIdChange;
1578                    sinfo.ssaIdLast = sinfo.ssaIdChange!=0 ? totalSSACount-1 : SIZE_MAX;
1579                    //totalSSACount = std::max(totalSSACount, ssaId);
1580                    if (!reducedSSAId || sinfo.ssaIdChange!=0)
1581                        ssaId = totalSSACount;
1582                   
1583                    // count read before writes (for cache weight)
1584                    if (sinfo.readBeforeWrite)
1585                        rbwCount++;
1586                    if (sinfo.ssaIdChange!=0)
1587                        wrCount++;
1588                }
1589            }
1590            else
1591            {
1592                cblocksToCache.increase(entry.blockIndex);
1593                ARDOut << "cblockToCache: " << entry.blockIndex << "=" <<
1594                            cblocksToCache.count(entry.blockIndex) << "\n";
1595                // back, already visited
1596                flowStackBlocks[entry.blockIndex] = !flowStackBlocks[entry.blockIndex];
1597                flowStack.pop_back();
1598               
1599                BlockIndex curWayBIndex = flowStack.back().blockIndex;
1600                if (lastCommonCacheWayPoint.first != SIZE_MAX)
1601                {
1602                    // mark point of way to cache (res first point)
1603                    waysToCache[lastCommonCacheWayPoint.first] = true;
1604                    ARDOut << "mark to pfcache " <<
1605                            lastCommonCacheWayPoint.first << ", " <<
1606                            curWayBIndex << "\n";
1607                    prevWaysIndexMap[curWayBIndex] = lastCommonCacheWayPoint;
1608                }
1609                lastCommonCacheWayPoint = { curWayBIndex, flowStack.size()-1 };
1610                ARDOut << "lastCcwP: " << curWayBIndex << "\n";
1611                continue;
1612            }
1613        }
1614       
1615        if (!callStack.empty() &&
1616            entry.blockIndex == callStack.back().callBlock &&
1617            entry.nextIndex-1 == callStack.back().callNextIndex)
1618        {
1619            ARDOut << " ret: " << entry.blockIndex << "\n";
1620            const BlockIndex routineBlock = callStack.back().routineBlock;
1621            RoutineData& prevRdata = routineMap.find(routineBlock)->second;
1622            if (!isRoutineGen[routineBlock])
1623            {
1624                createRoutineData(codeBlocks, curSSAIdMap, loopBlocks, callBlocks,
1625                            cblocksToCache, subroutinesCache, routineMap, prevRdata,
1626                            routineBlock);
1627                //prevRdata.compare(myRoutineData);
1628                isRoutineGen[routineBlock] = true;
1629               
1630                auto csimsmit = curSSAIdMapStateMap.find(routineBlock.index);
1631                if (csimsmit != curSSAIdMapStateMap.end() && entry.blockIndex.pass==0)
1632                {
1633                    ARDOut << " get curSSAIdMap from back recur 2\n";
1634                    curSSAIdMap = csimsmit->second;
1635                    curSSAIdMapStateMap.erase(csimsmit);
1636                }
1637            }
1638           
1639            callStack.pop_back(); // just return from call
1640            callBlocks.erase(routineBlock);
1641        }
1642       
1643        if (entry.nextIndex < cblock.nexts.size())
1644        {
1645            bool isCall = false;
1646            BlockIndex nextBlock = cblock.nexts[entry.nextIndex].block;
1647            nextBlock.pass = entry.blockIndex.pass;
1648            if (cblock.nexts[entry.nextIndex].isCall)
1649            {
1650                if (!callBlocks.insert(nextBlock).second)
1651                {
1652                    // if already called (then it is recursion)
1653                    if (recurseBlocks.insert(nextBlock.index).second)
1654                    {
1655                        ARDOut << "   -- recursion: " << nextBlock << "\n";
1656                        nextBlock.pass = 1;
1657                       
1658                        curSSAIdMapStateMap.insert({ nextBlock.index,  curSSAIdMap });
1659                    }
1660                    else if (entry.blockIndex.pass==1)
1661                    {
1662                        entry.nextIndex++;
1663                        ARDOut << " NO call (rec): " << entry.blockIndex << "\n";
1664                        continue;
1665                    }
1666                }
1667                else if (entry.blockIndex.pass==1 &&
1668                    recurseBlocks.find(nextBlock.index) != recurseBlocks.end())
1669                {
1670                    entry.nextIndex++;
1671                    ARDOut << " NO call (rec)2: " << entry.blockIndex << "\n";
1672                    continue;
1673                }
1674               
1675                ARDOut << " call: " << entry.blockIndex << "\n";
1676               
1677                callStack.push_back({ entry.blockIndex, entry.nextIndex, nextBlock });
1678                routineMap.insert({ nextBlock, { } });
1679                isCall = true;
1680            }
1681           
1682            flowStack.push_back({ nextBlock, 0, isCall });
1683            if (flowStackBlocks[nextBlock])
1684            {
1685                if (!cblock.nexts[entry.nextIndex].isCall)
1686                    loopBlocks.insert(nextBlock);
1687                flowStackBlocks[nextBlock] = false; // keep to inserted in popping
1688            }
1689            else
1690                flowStackBlocks[nextBlock] = true;
1691            entry.nextIndex++;
1692        }
1693        else if (((entry.nextIndex==0 && cblock.nexts.empty()) ||
1694                // if have any call then go to next block
1695                (cblock.haveCalls && entry.nextIndex==cblock.nexts.size())) &&
1696                 !cblock.haveReturn && !cblock.haveEnd)
1697        {
1698            if (entry.nextIndex!=0) // if back from calls (just return from calls)
1699            {
1700                reduceSSAIdsForCalls(entry, codeBlocks, retSSAIdMap, routineMap,
1701                                     ssaReplacesMap);
1702                //
1703                for (const NextBlock& next: cblock.nexts)
1704                    if (next.isCall)
1705                    {
1706                        //ARDOut << "joincall:"<< next.block << "\n";
1707                        size_t pass = 0;
1708                        if (callBlocks.find(next.block) != callBlocks.end())
1709                        {
1710                            ARDOut << " is secpass: " << entry.blockIndex << " : " <<
1711                                    next.block << "\n";
1712                            pass = 1; // it ways second pass
1713                        }
1714                       
1715                        auto it = routineMap.find({ next.block, pass }); // must find
1716                        initializePrevRetSSAIds(curSSAIdMap, retSSAIdMap,
1717                                    it->second, entry);
1718                       
1719                        BlockIndex rblock(next.block, entry.blockIndex.pass);
1720                        if (callBlocks.find(next.block) != callBlocks.end())
1721                            rblock.pass = 1;
1722                       
1723                        joinRetSSAIdMap(retSSAIdMap, it->second.lastSSAIdMap, rblock);
1724                    }
1725            }
1726           
1727            flowStack.push_back({ entry.blockIndex+1, 0, false });
1728            if (flowStackBlocks[entry.blockIndex+1])
1729            {
1730                loopBlocks.insert(entry.blockIndex+1);
1731                 // keep to inserted in popping
1732                flowStackBlocks[entry.blockIndex+1] = false;
1733            }
1734            else
1735                flowStackBlocks[entry.blockIndex+1] = true;
1736            entry.nextIndex++;
1737        }
1738        else // back
1739        {
1740            // revert retSSAIdMap
1741            revertRetSSAIdMap(curSSAIdMap, retSSAIdMap, entry, nullptr);
1742            //
1743           
1744            for (const auto& ssaEntry: cblock.ssaInfoMap)
1745            {
1746                if (ssaEntry.first.regVar == nullptr)
1747                    continue;
1748               
1749                size_t& curSSAId = curSSAIdMap[ssaEntry.first];
1750                const size_t nextSSAId = curSSAId;
1751                curSSAId = ssaEntry.second.ssaIdBefore+1;
1752               
1753                ARDOut << "popcurnext: " << ssaEntry.first.regVar <<
1754                            ":" << ssaEntry.first.index << ": " <<
1755                            nextSSAId << ", " << curSSAId << "\n";
1756            }
1757           
1758            ARDOut << "pop: " << entry.blockIndex << "\n";
1759            flowStackBlocks[entry.blockIndex] = false;
1760           
1761            if (!flowStack.empty() && flowStack.back().isCall)
1762            {
1763                auto csimsmit = curSSAIdMapStateMap.find(entry.blockIndex.index);
1764                if (csimsmit != curSSAIdMapStateMap.end())
1765                {
1766                    ARDOut << " get curSSAIdMap from back recur\n";
1767                    curSSAIdMap = csimsmit->second;
1768                }
1769            }
1770           
1771            flowStack.pop_back();
1772           
1773            if (!flowStack.empty() && lastCommonCacheWayPoint.first != SIZE_MAX &&
1774                    lastCommonCacheWayPoint.second >= flowStack.size())
1775            {
1776                lastCommonCacheWayPoint =
1777                        { flowStack.back().blockIndex, flowStack.size()-1 };
1778                ARDOut << "POPlastCcwP: " << lastCommonCacheWayPoint.first << "\n";
1779            }
1780        }
1781    }
1782   
1783    /**********
1784     * after that, we find points to resolve conflicts
1785     **********/
1786    flowStack.clear();
1787    std::deque<FlowStackEntry2> flowStack2;
1788   
1789    std::fill(visited.begin(), visited.end(), false);
1790    flowStack2.push_back({ 0, 0 });
1791   
1792    SimpleCache<BlockIndex, LastSSAIdMap> resFirstPointsCache(wrCount<<1);
1793    SimpleCache<BlockIndex, RBWSSAIdMap> resSecondPointsCache(rbwCount<<1);
1794   
1795    while (!flowStack2.empty())
1796    {
1797        FlowStackEntry2& entry = flowStack2.back();
1798        CodeBlock& cblock = codeBlocks[entry.blockIndex.index];
1799       
1800        if (entry.nextIndex == 0)
1801        {
1802            // process current block
1803            if (!visited[entry.blockIndex])
1804                visited[entry.blockIndex] = true;
1805            else
1806            {
1807                resolveSSAConflicts(flowStack2, routineMap, codeBlocks,
1808                            prevWaysIndexMap, waysToCache, cblocksToCache,
1809                            resFirstPointsCache, resSecondPointsCache, ssaReplacesMap);
1810               
1811                // back, already visited
1812                flowStack2.pop_back();
1813                continue;
1814            }
1815        }
1816       
1817        if (entry.nextIndex < cblock.nexts.size())
1818        {
1819            flowStack2.push_back({
1820                { cblock.nexts[entry.nextIndex].block, entry.blockIndex.pass }, 0 });
1821            entry.nextIndex++;
1822        }
1823        else if (((entry.nextIndex==0 && cblock.nexts.empty()) ||
1824                // if have any call then go to next block
1825                (cblock.haveCalls && entry.nextIndex==cblock.nexts.size())) &&
1826                 !cblock.haveReturn && !cblock.haveEnd)
1827        {
1828            flowStack2.push_back({ entry.blockIndex+1, 0 });
1829            entry.nextIndex++;
1830        }
1831        else // back
1832        {
1833            if (cblocksToCache.count(entry.blockIndex)==2 &&
1834                !resSecondPointsCache.hasKey(entry.blockIndex))
1835                // add to cache
1836                addResSecCacheEntry(routineMap, codeBlocks, resSecondPointsCache,
1837                            entry.blockIndex);
1838            flowStack2.pop_back();
1839        }
1840    }
1841}
Note: See TracBrowser for help on using the repository browser.