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

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

CLRadeonExtender: AsmRegAlloc?: Unfinished integration LinearDepHandler? with AsmRegAllocator?.

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