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

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

CLRadeonExtender: AsmRegAlloc?: Fix stupid bug in createSSAData: do not ssaId when no reduced SSAid but no reduction for this regvar but no ssaId changes (no writes). Fixed testcases (livenesses). Fixed insert in Liveness class: use max k2 (end of region) instead simple replacing.
Correct condition for adding 1 to region start while putting liveness through previous blocks. Add new testcase with empty blocks (no reg or regvar usage) (livenesses).

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