Changeset 3991 in CLRX


Ignore:
Timestamp:
Apr 13, 2018, 8:50:32 AM (6 days ago)
Author:
matszpk
Message:

CLRadeonExtender: Move SimpleCache? to Containers.h. Move createSSAData stuff into new source file (AsmRegAllocSSAData.cpp). Add new include: AsmRegAlloc?.h.

Location:
CLRadeonExtender/trunk
Files:
2 added
3 edited

Legend:

Unmodified
Added
Removed
  • CLRadeonExtender/trunk/CLRX/utils/Containers.h

    r3876 r3991  
    2929#include <algorithm>
    3030#include <vector>
     31#include <utility>
     32#include <unordered_map>
    3133#include <initializer_list>
    3234
     
    500502}
    501503
     504/** Simple cache **/
     505
     506/// Simple cache for object. object class should have a weight method
     507template<typename K, typename V>
     508class CLRX_INTERNAL SimpleCache
     509{
     510private:
     511    struct Entry
     512    {
     513        size_t sortedPos;
     514        size_t usage;
     515        V value;
     516    };
     517   
     518    size_t totalWeight;
     519    size_t maxWeight;
     520   
     521    typedef typename std::unordered_map<K, Entry>::iterator EntryMapIt;
     522    // sorted entries - sorted by usage
     523    std::vector<EntryMapIt> sortedEntries;
     524    std::unordered_map<K, Entry> entryMap;
     525   
     526    void updateInSortedEntries(EntryMapIt it)
     527    {
     528        const size_t curPos = it->second.sortedPos;
     529        if (curPos == 0)
     530            return; // first position
     531        if (sortedEntries[curPos-1]->second.usage < it->second.usage &&
     532            (curPos==1 || sortedEntries[curPos-2]->second.usage >= it->second.usage))
     533        {
     534            //std::cout << "fast path" << std::endl;
     535            std::swap(sortedEntries[curPos-1]->second.sortedPos, it->second.sortedPos);
     536            std::swap(sortedEntries[curPos-1], sortedEntries[curPos]);
     537            return;
     538        }
     539        //std::cout << "slow path" << std::endl;
     540        auto fit = std::upper_bound(sortedEntries.begin(),
     541            sortedEntries.begin()+it->second.sortedPos, it,
     542            [](EntryMapIt it1, EntryMapIt it2)
     543            { return it1->second.usage > it2->second.usage; });
     544        if (fit != sortedEntries.begin()+it->second.sortedPos)
     545        {
     546            const size_t curPos = it->second.sortedPos;
     547            std::swap((*fit)->second.sortedPos, it->second.sortedPos);
     548            std::swap(*fit, sortedEntries[curPos]);
     549        }
     550    }
     551   
     552    void insertToSortedEntries(EntryMapIt it)
     553    {
     554        it->second.sortedPos = sortedEntries.size();
     555        sortedEntries.push_back(it);
     556    }
     557   
     558    void removeFromSortedEntries(size_t pos)
     559    {
     560        // update later element positioning
     561        for (size_t i = pos+1; i < sortedEntries.size(); i++)
     562            (sortedEntries[i]->second.sortedPos)--;
     563        sortedEntries.erase(sortedEntries.begin() + pos);
     564    }
     565   
     566public:
     567    /// constructor
     568    explicit SimpleCache(size_t _maxWeight) : totalWeight(0), maxWeight(_maxWeight)
     569    { }
     570   
     571    /// use key - get value
     572    V* use(const K& key)
     573    {
     574        auto it = entryMap.find(key);
     575        if (it != entryMap.end())
     576        {
     577            it->second.usage++;
     578            updateInSortedEntries(it);
     579            return &(it->second.value);
     580        }
     581        return nullptr;
     582    }
     583   
     584    /// return true if key exists
     585    bool hasKey(const K& key)
     586    { return entryMap.find(key) != entryMap.end(); }
     587   
     588    /// put value
     589    void put(const K& key, const V& value)
     590    {
     591        auto res = entryMap.insert({ key, Entry{ 0, 0, value } });
     592        if (!res.second)
     593        {
     594            removeFromSortedEntries(res.first->second.sortedPos); // remove old value
     595            // update value
     596            totalWeight -= res.first->second.value.weight();
     597            res.first->second = Entry{ 0, 0, value };
     598        }
     599        const size_t elemWeight = value.weight();
     600       
     601        // correct max weight if element have greater weight
     602        if (elemWeight > maxWeight)
     603            maxWeight = elemWeight<<1;
     604       
     605        while (totalWeight+elemWeight > maxWeight)
     606        {
     607            // remove min usage element
     608            auto minUsageIt = sortedEntries.back();
     609            sortedEntries.pop_back();
     610            totalWeight -= minUsageIt->second.value.weight();
     611            entryMap.erase(minUsageIt);
     612        }
     613       
     614        insertToSortedEntries(res.first); // new entry in sorted entries
     615       
     616        totalWeight += elemWeight;
     617    }
     618};
     619
    502620#endif
  • CLRadeonExtender/trunk/amdasm/AsmRegAlloc.cpp

    r3985 r3991  
    3333#include <CLRX/amdasm/Assembler.h>
    3434#include "AsmInternals.h"
     35#include "AsmRegAlloc.h"
    3536
    3637using namespace CLRX;
    3738
    38 typedef AsmRegAllocator::CodeBlock CodeBlock;
    39 typedef AsmRegAllocator::NextBlock NextBlock;
    40 typedef AsmRegAllocator::SSAInfo SSAInfo;
    41 typedef std::pair<const AsmSingleVReg, SSAInfo> SSAEntry;
     39std::ostream& operator<<(std::ostream& os, const CLRX::BlockIndex& v)
     40{
     41    if (v.pass==0)
     42        return os << v.index;
     43    else
     44        return os << v.index << "#" << v.pass;
     45}
    4246
    4347ISAUsageHandler::ISAUsageHandler(const std::vector<cxbyte>& _content) :
     
    443447}
    444448
    445 /** Simple cache **/
    446 
    447 template<typename K, typename V>
    448 class CLRX_INTERNAL SimpleCache
    449 {
    450 private:
    451     struct Entry
    452     {
    453         size_t sortedPos;
    454         size_t usage;
    455         V value;
    456     };
    457    
    458     size_t totalWeight;
    459     size_t maxWeight;
    460    
    461     typedef typename std::unordered_map<K, Entry>::iterator EntryMapIt;
    462     // sorted entries - sorted by usage
    463     std::vector<EntryMapIt> sortedEntries;
    464     std::unordered_map<K, Entry> entryMap;
    465    
    466     void updateInSortedEntries(EntryMapIt it)
    467     {
    468         const size_t curPos = it->second.sortedPos;
    469         if (curPos == 0)
    470             return; // first position
    471         if (sortedEntries[curPos-1]->second.usage < it->second.usage &&
    472             (curPos==1 || sortedEntries[curPos-2]->second.usage >= it->second.usage))
    473         {
    474             //std::cout << "fast path" << std::endl;
    475             std::swap(sortedEntries[curPos-1]->second.sortedPos, it->second.sortedPos);
    476             std::swap(sortedEntries[curPos-1], sortedEntries[curPos]);
    477             return;
    478         }
    479         //std::cout << "slow path" << std::endl;
    480         auto fit = std::upper_bound(sortedEntries.begin(),
    481             sortedEntries.begin()+it->second.sortedPos, it,
    482             [](EntryMapIt it1, EntryMapIt it2)
    483             { return it1->second.usage > it2->second.usage; });
    484         if (fit != sortedEntries.begin()+it->second.sortedPos)
    485         {
    486             const size_t curPos = it->second.sortedPos;
    487             std::swap((*fit)->second.sortedPos, it->second.sortedPos);
    488             std::swap(*fit, sortedEntries[curPos]);
    489         }
    490     }
    491    
    492     void insertToSortedEntries(EntryMapIt it)
    493     {
    494         it->second.sortedPos = sortedEntries.size();
    495         sortedEntries.push_back(it);
    496     }
    497    
    498     void removeFromSortedEntries(size_t pos)
    499     {
    500         // update later element positioning
    501         for (size_t i = pos+1; i < sortedEntries.size(); i++)
    502             (sortedEntries[i]->second.sortedPos)--;
    503         sortedEntries.erase(sortedEntries.begin() + pos);
    504     }
    505    
    506 public:
    507     explicit SimpleCache(size_t _maxWeight) : totalWeight(0), maxWeight(_maxWeight)
    508     { }
    509    
    510     // use key - get value
    511     V* use(const K& key)
    512     {
    513         auto it = entryMap.find(key);
    514         if (it != entryMap.end())
    515         {
    516             it->second.usage++;
    517             updateInSortedEntries(it);
    518             return &(it->second.value);
    519         }
    520         return nullptr;
    521     }
    522    
    523     bool hasKey(const K& key)
    524     { return entryMap.find(key) != entryMap.end(); }
    525    
    526     // put value
    527     void put(const K& key, const V& value)
    528     {
    529         auto res = entryMap.insert({ key, Entry{ 0, 0, value } });
    530         if (!res.second)
    531         {
    532             removeFromSortedEntries(res.first->second.sortedPos); // remove old value
    533             // update value
    534             totalWeight -= res.first->second.value.weight();
    535             res.first->second = Entry{ 0, 0, value };
    536         }
    537         const size_t elemWeight = value.weight();
    538        
    539         // correct max weight if element have greater weight
    540         if (elemWeight > maxWeight)
    541             maxWeight = elemWeight<<1;
    542        
    543         while (totalWeight+elemWeight > maxWeight)
    544         {
    545             // remove min usage element
    546             auto minUsageIt = sortedEntries.back();
    547             sortedEntries.pop_back();
    548             totalWeight -= minUsageIt->second.value.weight();
    549             entryMap.erase(minUsageIt);
    550         }
    551        
    552         insertToSortedEntries(res.first); // new entry in sorted entries
    553        
    554         totalWeight += elemWeight;
    555     }
    556 };
    557 
    558 
    559 //  BlockIndex
    560 
    561 struct CLRX_INTERNAL BlockIndex
    562 {
    563     size_t index;
    564     size_t pass;
    565    
    566     BlockIndex(size_t _index = 0, size_t _pass = 0)
    567             : index(_index), pass(_pass)
    568     { }
    569    
    570     bool operator==(const BlockIndex& v) const
    571     { return index==v.index && pass==v.pass; }
    572     bool operator!=(const BlockIndex& v) const
    573     { return index!=v.index || pass!=v.pass; }
    574    
    575     BlockIndex operator+(size_t p) const
    576     { return BlockIndex(index+p, pass); }
    577 };
    578 
    579 std::ostream& operator<<(std::ostream& os, const BlockIndex& v)
    580 {
    581     if (v.pass==0)
    582         return os << v.index;
    583     else
    584         return os << v.index << "#" << v.pass;
    585 }
    586 
    587 namespace std
    588 {
    589 
    590 /// std::hash specialization for CLRX CString
    591 template<>
    592 struct hash<BlockIndex>
    593 {
    594     typedef BlockIndex argument_type;    ///< argument type
    595     typedef std::size_t result_type;    ///< result type
    596    
    597     /// a calling operator
    598     size_t operator()(const BlockIndex& r1) const
    599     {
    600         std::hash<size_t> h1;
    601         return h1(r1.index) ^ h1(r1.pass);
    602     }
    603 };
    604 
    605 }
    606 
    607 class CLRX_INTERNAL CBlockBitPool: public std::vector<bool>
    608 {
    609 public:
    610     CBlockBitPool(size_t n = 0, bool v = false) : std::vector<bool>(n<<1, v)
    611     { }
    612    
    613     reference operator[](BlockIndex i)
    614     { return std::vector<bool>::operator[](i.index + (i.pass ? (size()>>1) : 0)); }
    615     const_reference operator[](BlockIndex i) const
    616     { return std::vector<bool>::operator[](i.index + (i.pass ? (size()>>1) : 0)); }
    617 };
    618 
    619 /** Simple cache **/
    620 
    621 // map of last SSAId for routine, key - varid, value - last SSA ids
    622 class CLRX_INTERNAL LastSSAIdMap: public
    623             std::unordered_map<AsmSingleVReg, VectorSet<size_t> >
    624 {
    625 public:
    626     LastSSAIdMap()
    627     { }
    628    
    629     iterator insertSSAId(const AsmSingleVReg& vreg, size_t ssaId)
    630     {
    631         auto res = insert({ vreg, { ssaId } });
    632         if (!res.second)
    633             res.first->second.insertValue(ssaId);
    634         return res.first;
    635     }
    636    
    637     void eraseSSAId(const AsmSingleVReg& vreg, size_t ssaId)
    638     {
    639         auto it = find(vreg);
    640         if (it != end())
    641              it->second.eraseValue(ssaId);
    642     }
    643    
    644     size_t weight() const
    645     { return size(); }
    646 };
    647 
    648 typedef LastSSAIdMap RBWSSAIdMap;
    649 typedef std::unordered_map<BlockIndex, VectorSet<BlockIndex> > SubrLoopsMap;
    650 
    651 struct CLRX_INTERNAL RetSSAEntry
    652 {
    653     std::vector<BlockIndex> routines;
    654     VectorSet<size_t> ssaIds;
    655     size_t prevSSAId; // for curSSAId
    656 };
    657 
    658 typedef std::unordered_map<AsmSingleVReg, RetSSAEntry> RetSSAIdMap;
    659 
    660 struct CLRX_INTERNAL LoopSSAIdMap
    661 {
    662     LastSSAIdMap ssaIdMap;
    663     bool passed;
    664 };
    665 
    666 struct CLRX_INTERNAL RoutineData
    667 {
    668     // rbwSSAIdMap - read before write SSAId's map
    669     std::unordered_map<AsmSingleVReg, size_t> rbwSSAIdMap;
    670     std::unordered_map<AsmSingleVReg, size_t> origRbwSSAIdMap;
    671     LastSSAIdMap curSSAIdMap;
    672     LastSSAIdMap lastSSAIdMap;
    673     // key - loop block, value - last ssaId map for loop end
    674     std::unordered_map<BlockIndex, LoopSSAIdMap> loopEnds;
    675     bool notFirstReturn;
    676     size_t weight_;
    677    
    678     RoutineData() : notFirstReturn(false), weight_(0)
    679     { }
    680    
    681     void calculateWeight()
    682     {
    683         weight_ = rbwSSAIdMap.size() + lastSSAIdMap.weight();
    684         for (const auto& entry: loopEnds)
    685             weight_ += entry.second.ssaIdMap.weight();
    686     }
    687    
    688     size_t weight() const
    689     { return weight_; }
    690 };
    691 
    692 struct CLRX_INTERNAL FlowStackEntry
    693 {
    694     BlockIndex blockIndex;
    695     size_t nextIndex;
    696     bool isCall;
    697     bool haveReturn;
    698     RetSSAIdMap prevRetSSAIdSets;
    699 };
    700 
    701 struct CLRX_INTERNAL FlowStackEntry2
    702 {
    703     BlockIndex blockIndex;
    704     size_t nextIndex;
    705 };
    706 
    707 struct CLRX_INTERNAL FlowStackEntry3
    708 {
    709     size_t blockIndex;
    710     size_t nextIndex;
    711     bool isCall;
    712     RetSSAIdMap prevRetSSAIdSets;
    713 };
    714 
    715 
    716 struct CLRX_INTERNAL CallStackEntry
    717 {
    718     BlockIndex callBlock; // index
    719     size_t callNextIndex; // index of call next
    720     BlockIndex routineBlock;    // routine block
    721 };
    722 
    723 typedef std::unordered_map<BlockIndex, RoutineData> RoutineMap;
    724 
    725 class CLRX_INTERNAL ResSecondPointsToCache: public CBlockBitPool
    726 {
    727 public:
    728     explicit ResSecondPointsToCache(size_t n) : CBlockBitPool(n<<1, false)
    729     { }
    730    
    731     void increase(BlockIndex ip)
    732     {
    733         const size_t i = ip.index + (ip.pass ? (size()>>2) : 0);
    734         if ((*this)[i<<1])
    735             (*this)[(i<<1)+1] = true;
    736         else
    737             (*this)[i<<1] = true;
    738     }
    739    
    740     cxuint count(BlockIndex ip) const
    741     {
    742         const size_t i = ip.index + (ip.pass ? (size()>>2) : 0);
    743         return cxuint((*this)[i<<1]) + (*this)[(i<<1)+1];
    744     }
    745 };
    746 
    747 typedef AsmRegAllocator::SSAReplace SSAReplace; // first - orig ssaid, second - dest ssaid
    748 typedef AsmRegAllocator::SSAReplacesMap SSAReplacesMap;
    749 
    750 static inline void insertReplace(SSAReplacesMap& rmap, const AsmSingleVReg& vreg,
    751               size_t origId, size_t destId)
    752 {
    753     auto res = rmap.insert({ vreg, {} });
    754     res.first->second.insertValue({ origId, destId });
    755 }
    756 
    757 /* caching concepts:
    758  * resfirstPointsCache - cache of the ways that goes to conflict which should be resolved
    759  *               from first code block of the code. The entries holds a stackVarMap state
    760  *               to first point the conflict (first visited already code block)
    761  * resSecondPointsCache - cache of the tree traversing, starting at the first conflict
    762  *               point (first visited code block). Entries holds a
    763  *               regvars SSAId read before write (that should resolved)
    764  */
    765 
    766 static void handleSSAEntryWhileResolving(SSAReplacesMap* replacesMap,
    767             const LastSSAIdMap* stackVarMap,
    768             std::unordered_map<AsmSingleVReg, BlockIndex>& alreadyReadMap,
    769             FlowStackEntry2& entry, const SSAEntry& sentry,
    770             RBWSSAIdMap* cacheSecPoints)
    771 {
    772     const SSAInfo& sinfo = sentry.second;
    773     auto res = alreadyReadMap.insert({ sentry.first, entry.blockIndex });
    774    
    775     if (res.second && sinfo.readBeforeWrite)
    776     {
    777         if (cacheSecPoints != nullptr)
    778         {
    779             auto res = cacheSecPoints->insert({ sentry.first, { sinfo.ssaIdBefore } });
    780             if (!res.second)
    781                 res.first->second.insertValue(sinfo.ssaIdBefore);
    782         }
    783        
    784         if (stackVarMap != nullptr)
    785         {
    786            
    787             // resolve conflict for this variable ssaId>.
    788             // only if in previous block previous SSAID is
    789             // read before all writes
    790             auto it = stackVarMap->find(sentry.first);
    791            
    792             if (it != stackVarMap->end())
    793             {
    794                 // found, resolve by set ssaIdLast
    795                 for (size_t ssaId: it->second)
    796                 {
    797                     if (ssaId > sinfo.ssaIdBefore)
    798                     {
    799                         std::cout << "  insertreplace: " << sentry.first.regVar << ":" <<
    800                             sentry.first.index  << ": " <<
    801                             ssaId << ", " << sinfo.ssaIdBefore << std::endl;
    802                         insertReplace(*replacesMap, sentry.first, ssaId,
    803                                     sinfo.ssaIdBefore);
    804                     }
    805                     else if (ssaId < sinfo.ssaIdBefore)
    806                     {
    807                         std::cout << "  insertreplace2: " << sentry.first.regVar << ":" <<
    808                             sentry.first.index  << ": " <<
    809                             ssaId << ", " << sinfo.ssaIdBefore << std::endl;
    810                         insertReplace(*replacesMap, sentry.first,
    811                                         sinfo.ssaIdBefore, ssaId);
    812                     }
    813                     /*else
    814                         std::cout << "  noinsertreplace: " <<
    815                             ssaId << "," << sinfo.ssaIdBefore << std::endl;*/
    816                 }
    817             }
    818         }
    819     }
    820 }
    821 
    822 typedef std::unordered_map<BlockIndex, std::pair<BlockIndex, size_t> > PrevWaysIndexMap;
    823 
    824 // use res second point cache entry to resolve conflict with SSAIds.
    825 // it emits SSA replaces from these conflicts
    826 static void useResSecPointCache(SSAReplacesMap* replacesMap,
    827         const LastSSAIdMap* stackVarMap,
    828         const std::unordered_map<AsmSingleVReg, BlockIndex>& alreadyReadMap,
    829         const RBWSSAIdMap* resSecondPoints, BlockIndex nextBlock,
    830         RBWSSAIdMap* destCacheSecPoints)
    831 {
    832     std::cout << "use resSecPointCache for " << nextBlock <<
    833             ", alreadyRMapSize: " << alreadyReadMap.size() << std::endl;
    834     for (const auto& sentry: *resSecondPoints)
    835     {
    836         const bool alreadyRead = alreadyReadMap.find(sentry.first) != alreadyReadMap.end();
    837         if (destCacheSecPoints != nullptr && !alreadyRead)
    838         {
    839             auto res = destCacheSecPoints->insert(sentry);
    840             if (!res.second)
    841                 for (size_t srcSSAId: sentry.second)
    842                     res.first->second.insertValue(srcSSAId);
    843         }
    844        
    845         if (stackVarMap != nullptr)
    846         {
    847             auto it = stackVarMap->find(sentry.first);
    848            
    849             if (it != stackVarMap->end() && !alreadyRead)
    850             {
    851                 // found, resolve by set ssaIdLast
    852                 for (size_t ssaId: it->second)
    853                 {
    854                     for (size_t secSSAId: sentry.second)
    855                     {
    856                         if (ssaId > secSSAId)
    857                         {
    858                             std::cout << "  insertreplace: " <<
    859                                 sentry.first.regVar << ":" <<
    860                                 sentry.first.index  << ": " <<
    861                                 ssaId << ", " << secSSAId << std::endl;
    862                             insertReplace(*replacesMap, sentry.first, ssaId, secSSAId);
    863                         }
    864                         else if (ssaId < secSSAId)
    865                         {
    866                             std::cout << "  insertreplace2: " <<
    867                                 sentry.first.regVar << ":" <<
    868                                 sentry.first.index  << ": " <<
    869                                 ssaId << ", " << secSSAId << std::endl;
    870                             insertReplace(*replacesMap, sentry.first, secSSAId, ssaId);
    871                         }
    872                         /*else
    873                             std::cout << "  noinsertreplace: " <<
    874                                 ssaId << "," << sinfo.ssaIdBefore << std::endl;*/
    875                     }
    876                 }
    877             }
    878         }
    879     }
    880 }
    881 
    882 // add new res second cache entry with readBeforeWrite for all encountered regvars
    883 static void addResSecCacheEntry(const RoutineMap& routineMap,
    884                 const std::vector<CodeBlock>& codeBlocks,
    885                 SimpleCache<BlockIndex, RBWSSAIdMap>& resSecondPointsCache,
    886                 BlockIndex nextBlock)
    887 {
    888     std::cout << "addResSecCacheEntry: " << nextBlock << std::endl;
    889     //std::stack<CallStackEntry> callStack = prevCallStack;
    890     // traverse by graph from next block
    891     std::deque<FlowStackEntry2> flowStack;
    892     flowStack.push_back({ nextBlock, 0 });
    893     CBlockBitPool visited(codeBlocks.size(), false);
    894    
    895     std::unordered_map<AsmSingleVReg, BlockIndex> alreadyReadMap;
    896    
    897     RBWSSAIdMap cacheSecPoints;
    898    
    899     while (!flowStack.empty())
    900     {
    901         FlowStackEntry2& entry = flowStack.back();
    902         const CodeBlock& cblock = codeBlocks[entry.blockIndex.index];
    903        
    904         if (entry.nextIndex == 0)
    905         {
    906             // process current block
    907             if (!visited[entry.blockIndex])
    908             {
    909                 visited[entry.blockIndex] = true;
    910                 std::cout << "  resolv (cache): " << entry.blockIndex << std::endl;
    911                
    912                 const RBWSSAIdMap* resSecondPoints =
    913                             resSecondPointsCache.use(entry.blockIndex);
    914                 if (resSecondPoints == nullptr)
    915                     for (auto& sentry: cblock.ssaInfoMap)
    916                         handleSSAEntryWhileResolving(nullptr, nullptr,
    917                                 alreadyReadMap, entry, sentry,
    918                                 &cacheSecPoints);
    919                 else // to use cache
    920                 {
    921                     useResSecPointCache(nullptr, nullptr, alreadyReadMap,
    922                             resSecondPoints, entry.blockIndex, &cacheSecPoints);
    923                     flowStack.pop_back();
    924                     continue;
    925                 }
    926             }
    927             else
    928             {
    929                 // back, already visited
    930                 std::cout << "resolv already (cache): " << entry.blockIndex << std::endl;
    931                 flowStack.pop_back();
    932                 continue;
    933             }
    934         }
    935        
    936         if (entry.nextIndex < cblock.nexts.size())
    937         {
    938             flowStack.push_back({ { cblock.nexts[entry.nextIndex].block,
    939                     entry.blockIndex.pass }, 0 });
    940             entry.nextIndex++;
    941         }
    942         else if (((entry.nextIndex==0 && cblock.nexts.empty()) ||
    943                 // if have any call then go to next block
    944                 (cblock.haveCalls && entry.nextIndex==cblock.nexts.size())) &&
    945                  !cblock.haveReturn && !cblock.haveEnd)
    946         {
    947             // add toResolveMap ssaIds inside called routines
    948             for (const auto& next: cblock.nexts)
    949                 if (next.isCall)
    950                 {
    951                     const RoutineData& rdata = routineMap.find(next.block)->second;
    952                     for (const auto& v: rdata.rbwSSAIdMap)
    953                         alreadyReadMap.insert({v.first, entry.blockIndex });
    954                     for (const auto& v: rdata.lastSSAIdMap)
    955                         alreadyReadMap.insert({v.first, entry.blockIndex });
    956                 }
    957            
    958             flowStack.push_back({ entry.blockIndex+1, 0 });
    959             entry.nextIndex++;
    960         }
    961         else // back
    962         {
    963             // remove old to resolve in leaved way to allow collecting next ssaId
    964             // before write (can be different due to earlier visit)
    965             for (const auto& next: cblock.nexts)
    966                 if (next.isCall)
    967                 {
    968                     const RoutineData& rdata = routineMap.find(next.block)->second;
    969                     for (const auto& v: rdata.rbwSSAIdMap)
    970                     {
    971                         auto it = alreadyReadMap.find(v.first);
    972                         if (it != alreadyReadMap.end() && it->second == entry.blockIndex)
    973                             alreadyReadMap.erase(it);
    974                     }
    975                     for (const auto& v: rdata.lastSSAIdMap)
    976                     {
    977                         auto it = alreadyReadMap.find(v.first);
    978                         if (it != alreadyReadMap.end() && it->second == entry.blockIndex)
    979                             alreadyReadMap.erase(it);
    980                     }
    981                 }
    982            
    983             for (const auto& sentry: cblock.ssaInfoMap)
    984             {
    985                 auto it = alreadyReadMap.find(sentry.first);
    986                 if (it != alreadyReadMap.end() && it->second == entry.blockIndex)
    987                     // remove old to resolve in leaved way to allow collecting next ssaId
    988                     // before write (can be different due to earlier visit)
    989                     alreadyReadMap.erase(it);
    990             }
    991             std::cout << "  popresolv (cache)" << std::endl;
    992             flowStack.pop_back();
    993         }
    994     }
    995    
    996     resSecondPointsCache.put(nextBlock, cacheSecPoints);
    997 }
    998 
    999 // apply calls (changes from these calls) from code blocks to stack var map
    1000 static void applyCallToStackVarMap(const CodeBlock& cblock, const RoutineMap& routineMap,
    1001         LastSSAIdMap& stackVarMap, BlockIndex blockIndex, size_t nextIndex)
    1002 {
    1003     for (const NextBlock& next: cblock.nexts)
    1004         if (next.isCall)
    1005         {
    1006             const LastSSAIdMap& regVarMap =
    1007                     routineMap.find(next.block)->second.lastSSAIdMap;
    1008             for (const auto& sentry: regVarMap)
    1009                 stackVarMap[sentry.first].clear(); // clearing
    1010         }
    1011    
    1012     for (const NextBlock& next: cblock.nexts)
    1013         if (next.isCall)
    1014         {
    1015             std::cout << "  applycall: " << blockIndex << ": " <<
    1016                     nextIndex << ": " << next.block << std::endl;
    1017             const LastSSAIdMap& regVarMap =
    1018                     routineMap.find(next.block)->second.lastSSAIdMap;
    1019             for (const auto& sentry: regVarMap)
    1020                 for (size_t s: sentry.second)
    1021                     stackVarMap.insertSSAId(sentry.first, s);
    1022         }
    1023 }
    1024 
    1025 
    1026 // main routine to resilve SSA conflicts in code
    1027 // it emits SSA replaces from these conflicts
    1028 static void resolveSSAConflicts(const std::deque<FlowStackEntry2>& prevFlowStack,
    1029         const RoutineMap& routineMap, const std::vector<CodeBlock>& codeBlocks,
    1030         const PrevWaysIndexMap& prevWaysIndexMap,
    1031         const CBlockBitPool& waysToCache, ResSecondPointsToCache& cblocksToCache,
    1032         SimpleCache<BlockIndex, LastSSAIdMap>& resFirstPointsCache,
    1033         SimpleCache<BlockIndex, RBWSSAIdMap>& resSecondPointsCache,
    1034         SSAReplacesMap& replacesMap)
    1035 {
    1036     BlockIndex nextBlock = prevFlowStack.back().blockIndex;
    1037     auto pfEnd = prevFlowStack.end();
    1038     --pfEnd;
    1039     std::cout << "startResolv: " << (pfEnd-1)->blockIndex << "," << nextBlock << std::endl;
    1040     LastSSAIdMap stackVarMap;
    1041    
    1042     size_t pfStartIndex = 0;
    1043     {
    1044         auto pfPrev = pfEnd;
    1045         --pfPrev;
    1046         auto it = prevWaysIndexMap.find(pfPrev->blockIndex);
    1047         if (it != prevWaysIndexMap.end())
    1048         {
    1049             const LastSSAIdMap* cached = resFirstPointsCache.use(it->second.first);
    1050             if (cached!=nullptr)
    1051             {
    1052                 std::cout << "use pfcached: " << it->second.first << ", " <<
    1053                         it->second.second << std::endl;
    1054                 stackVarMap = *cached;
    1055                 pfStartIndex = it->second.second+1;
    1056                
    1057                 // apply missing calls at end of the cached
    1058                 const CodeBlock& cblock = codeBlocks[it->second.first.index];
    1059                
    1060                 const FlowStackEntry2& entry = *(prevFlowStack.begin()+pfStartIndex-1);
    1061                 if (entry.nextIndex > cblock.nexts.size())
    1062                     applyCallToStackVarMap(cblock, routineMap, stackVarMap, -1, -1);
    1063             }
    1064         }
    1065     }
    1066    
    1067     for (auto pfit = prevFlowStack.begin()+pfStartIndex; pfit != pfEnd; ++pfit)
    1068     {
    1069         const FlowStackEntry2& entry = *pfit;
    1070         std::cout << "  apply: " << entry.blockIndex << std::endl;
    1071         const CodeBlock& cblock = codeBlocks[entry.blockIndex.index];
    1072         for (const auto& sentry: cblock.ssaInfoMap)
    1073         {
    1074             const SSAInfo& sinfo = sentry.second;
    1075             if (sinfo.ssaIdChange != 0)
    1076                 stackVarMap[sentry.first] = { sinfo.ssaId + sinfo.ssaIdChange - 1 };
    1077         }
    1078         if (entry.nextIndex > cblock.nexts.size())
    1079             applyCallToStackVarMap(cblock, routineMap, stackVarMap,
    1080                         entry.blockIndex, entry.nextIndex);
    1081        
    1082         // put to first point cache
    1083         if (waysToCache[pfit->blockIndex] &&
    1084             !resFirstPointsCache.hasKey(pfit->blockIndex))
    1085         {
    1086             std::cout << "put pfcache " << pfit->blockIndex << std::endl;
    1087             resFirstPointsCache.put(pfit->blockIndex, stackVarMap);
    1088         }
    1089     }
    1090    
    1091     RBWSSAIdMap cacheSecPoints;
    1092     const bool toCache = (!resSecondPointsCache.hasKey(nextBlock)) &&
    1093                 cblocksToCache.count(nextBlock)>=2;
    1094    
    1095     //std::stack<CallStackEntry> callStack = prevCallStack;
    1096     // traverse by graph from next block
    1097     std::deque<FlowStackEntry2> flowStack;
    1098     flowStack.push_back({ nextBlock, 0 });
    1099     CBlockBitPool visited(codeBlocks.size(), false);
    1100    
    1101     // already read in current path
    1102     // key - vreg, value - source block where vreg of conflict found
    1103     std::unordered_map<AsmSingleVReg, BlockIndex> alreadyReadMap;
    1104    
    1105     while (!flowStack.empty())
    1106     {
    1107         FlowStackEntry2& entry = flowStack.back();
    1108         const CodeBlock& cblock = codeBlocks[entry.blockIndex.index];
    1109        
    1110         if (entry.nextIndex == 0)
    1111         {
    1112             // process current block
    1113             if (!visited[entry.blockIndex])
    1114             {
    1115                 visited[entry.blockIndex] = true;
    1116                 std::cout << "  resolv: " << entry.blockIndex << std::endl;
    1117                
    1118                 const RBWSSAIdMap* resSecondPoints =
    1119                         resSecondPointsCache.use(entry.blockIndex);
    1120                 if (resSecondPoints == nullptr)
    1121                     for (auto& sentry: cblock.ssaInfoMap)
    1122                         handleSSAEntryWhileResolving(&replacesMap, &stackVarMap,
    1123                                 alreadyReadMap, entry, sentry,
    1124                                 toCache ? &cacheSecPoints : nullptr);
    1125                 else // to use cache
    1126                 {
    1127                     useResSecPointCache(&replacesMap, &stackVarMap, alreadyReadMap,
    1128                             resSecondPoints, entry.blockIndex,
    1129                             toCache ? &cacheSecPoints : nullptr);
    1130                     flowStack.pop_back();
    1131                     continue;
    1132                 }
    1133             }
    1134             else
    1135             {
    1136                 cblocksToCache.increase(entry.blockIndex);
    1137                 std::cout << "cblockToCache: " << entry.blockIndex << "=" <<
    1138                             cblocksToCache.count(entry.blockIndex) << std::endl;
    1139                 // back, already visited
    1140                 std::cout << "resolv already: " << entry.blockIndex << std::endl;
    1141                 flowStack.pop_back();
    1142                 continue;
    1143             }
    1144         }
    1145        
    1146         if (entry.nextIndex < cblock.nexts.size())
    1147         {
    1148             flowStack.push_back({ { cblock.nexts[entry.nextIndex].block,
    1149                         entry.blockIndex.pass }, 0 });
    1150             entry.nextIndex++;
    1151         }
    1152         else if (((entry.nextIndex==0 && cblock.nexts.empty()) ||
    1153                 // if have any call then go to next block
    1154                 (cblock.haveCalls && entry.nextIndex==cblock.nexts.size())) &&
    1155                  !cblock.haveReturn && !cblock.haveEnd)
    1156         {
    1157             // add toResolveMap ssaIds inside called routines
    1158             for (const auto& next: cblock.nexts)
    1159                 if (next.isCall)
    1160                 {
    1161                     const RoutineData& rdata = routineMap.find(next.block)->second;
    1162                     for (const auto& v: rdata.rbwSSAIdMap)
    1163                         alreadyReadMap.insert({v.first, entry.blockIndex });
    1164                     for (const auto& v: rdata.lastSSAIdMap)
    1165                         alreadyReadMap.insert({v.first, entry.blockIndex });
    1166                 }
    1167            
    1168             flowStack.push_back({ entry.blockIndex+1, 0 });
    1169             entry.nextIndex++;
    1170         }
    1171         else // back
    1172         {
    1173             // remove old to resolve in leaved way to allow collecting next ssaId
    1174             // before write (can be different due to earlier visit)
    1175             for (const auto& next: cblock.nexts)
    1176                 if (next.isCall)
    1177                 {
    1178                     const RoutineData& rdata = routineMap.find(next.block)->second;
    1179                     for (const auto& v: rdata.rbwSSAIdMap)
    1180                     {
    1181                         auto it = alreadyReadMap.find(v.first);
    1182                         if (it != alreadyReadMap.end() && it->second == entry.blockIndex)
    1183                             alreadyReadMap.erase(it);
    1184                     }
    1185                     for (const auto& v: rdata.lastSSAIdMap)
    1186                     {
    1187                         auto it = alreadyReadMap.find(v.first);
    1188                         if (it != alreadyReadMap.end() && it->second == entry.blockIndex)
    1189                             alreadyReadMap.erase(it);
    1190                     }
    1191                 }
    1192            
    1193             for (const auto& sentry: cblock.ssaInfoMap)
    1194             {
    1195                 auto it = alreadyReadMap.find(sentry.first);
    1196                 if (it != alreadyReadMap.end() && it->second == entry.blockIndex)
    1197                     // remove old to resolve in leaved way to allow collecting next ssaId
    1198                     // before write (can be different due to earlier visit)
    1199                     alreadyReadMap.erase(it);
    1200             }
    1201             std::cout << "  popresolv" << std::endl;
    1202            
    1203             if (cblocksToCache.count(entry.blockIndex)==2 &&
    1204                 !resSecondPointsCache.hasKey(entry.blockIndex))
    1205                 // add to cache
    1206                 addResSecCacheEntry(routineMap, codeBlocks, resSecondPointsCache,
    1207                             entry.blockIndex);
    1208            
    1209             flowStack.pop_back();
    1210         }
    1211     }
    1212    
    1213     if (toCache)
    1214         resSecondPointsCache.put(nextBlock, cacheSecPoints);
    1215 }
    1216 
    1217 // join ret SSAId Map - src - last SSAIdMap from called routine
    1218 static void joinRetSSAIdMap(RetSSAIdMap& dest, const LastSSAIdMap& src,
    1219                 BlockIndex routineBlock)
    1220 {
    1221     for (const auto& entry: src)
    1222     {
    1223         std::cout << "  entry2: " << entry.first.regVar << ":" <<
    1224                 cxuint(entry.first.index) << ":";
    1225         for (size_t v: entry.second)
    1226             std::cout << " " << v;
    1227         std::cout << std::endl;
    1228         // insert if not inserted
    1229         auto res = dest.insert({entry.first, { { routineBlock }, entry.second } });
    1230         if (res.second)
    1231             continue; // added new
    1232         VectorSet<size_t>& destEntry = res.first->second.ssaIds;
    1233         res.first->second.routines.push_back(routineBlock);
    1234         // add new ways
    1235         for (size_t ssaId: entry.second)
    1236             destEntry.insertValue(ssaId);
    1237         std::cout << "    :";
    1238         for (size_t v: destEntry)
    1239             std::cout << " " << v;
    1240         std::cout << std::endl;
    1241     }
    1242 }
    1243 
    1244 // simple join last ssaid map
    1245 static void joinLastSSAIdMap(LastSSAIdMap& dest, const LastSSAIdMap& src)
    1246 {
    1247     for (const auto& entry: src)
    1248     {
    1249         std::cout << "  entry: " << entry.first.regVar << ":" <<
    1250                 cxuint(entry.first.index) << ":";
    1251         for (size_t v: entry.second)
    1252             std::cout << " " << v;
    1253         std::cout << std::endl;
    1254         auto res = dest.insert(entry); // find
    1255         if (res.second)
    1256             continue; // added new
    1257         VectorSet<size_t>& destEntry = res.first->second;
    1258         // add new ways
    1259         for (size_t ssaId: entry.second)
    1260             destEntry.insertValue(ssaId);
    1261         std::cout << "    :";
    1262         for (size_t v: destEntry)
    1263             std::cout << " " << v;
    1264         std::cout << std::endl;
    1265     }
    1266 }
    1267 
    1268 // join last SSAIdMap of the routine including later routine call
    1269 // dest - dest last SSAId map, src - source lastSSAIdMap
    1270 // laterRdatas - data of subroutine/routine exeuted after src lastSSAIdMap state
    1271 static void joinLastSSAIdMapInt(LastSSAIdMap& dest, const LastSSAIdMap& src,
    1272                     const LastSSAIdMap& laterRdataCurSSAIdMap,
    1273                     const LastSSAIdMap& laterRdataLastSSAIdMap, bool loop)
    1274 {
    1275     for (const auto& entry: src)
    1276     {
    1277         auto lsit = laterRdataLastSSAIdMap.find(entry.first);
    1278         if (lsit != laterRdataLastSSAIdMap.end())
    1279         {
    1280             auto csit = laterRdataCurSSAIdMap.find(entry.first);
    1281             if (csit != laterRdataCurSSAIdMap.end() && !csit->second.empty())
    1282             {
    1283                 // if found in last ssa ID map,
    1284                 // but has first value (some way do not change SSAId)
    1285                 // then pass to add new ssaIds before this point
    1286                 if (!lsit->second.hasValue(csit->second[0]))
    1287                     continue; // otherwise, skip
    1288             }
    1289         }
    1290         std::cout << "  entry: " << entry.first.regVar << ":" <<
    1291                 cxuint(entry.first.index) << ":";
    1292         for (size_t v: entry.second)
    1293             std::cout << " " << v;
    1294         std::cout << std::endl;
    1295         auto res = dest.insert(entry); // find
    1296         if (res.second)
    1297             continue; // added new
    1298         VectorSet<size_t>& destEntry = res.first->second;
    1299         // add new ways
    1300         for (size_t ssaId: entry.second)
    1301             destEntry.insertValue(ssaId);
    1302         std::cout << "    :";
    1303         for (size_t v: destEntry)
    1304             std::cout << " " << v;
    1305         std::cout << std::endl;
    1306     }
    1307     if (!loop) // do not if loop
    1308         joinLastSSAIdMap(dest, laterRdataLastSSAIdMap);
    1309 }
    1310 
    1311 static void joinLastSSAIdMap(LastSSAIdMap& dest, const LastSSAIdMap& src,
    1312                     const RoutineData& laterRdata, bool loop = false)
    1313 {
    1314     joinLastSSAIdMapInt(dest, src, laterRdata.curSSAIdMap, laterRdata.lastSSAIdMap, loop);
    1315 }
    1316 
    1317 
    1318 // join routine data from child call with data from parent routine
    1319 // (just join child call from parent)
    1320 static void joinRoutineData(RoutineData& dest, const RoutineData& src,
    1321             const std::unordered_map<AsmSingleVReg, size_t>& curSSAIdMap,
    1322             bool notFirstReturn)
    1323 {
    1324     // insert readBeforeWrite only if doesnt exists in destination
    1325     dest.rbwSSAIdMap.insert(src.rbwSSAIdMap.begin(), src.rbwSSAIdMap.end());
    1326     dest.origRbwSSAIdMap.insert(src.origRbwSSAIdMap.begin(), src.origRbwSSAIdMap.end());
    1327    
    1328     //joinLastSSAIdMap(dest.curSSAIdMap, src.lastSSAIdMap);
    1329    
    1330     for (const auto& entry: src.lastSSAIdMap)
    1331     {
    1332         std::cout << "  entry3: " << entry.first.regVar << ":" <<
    1333                 cxuint(entry.first.index) << ":";
    1334         for (size_t v: entry.second)
    1335             std::cout << " " << v;
    1336         std::cout << std::endl;
    1337         auto res = dest.curSSAIdMap.insert(entry); // find
    1338         VectorSet<size_t>& destEntry = res.first->second;
    1339        
    1340         if (!res.second)
    1341         {
    1342             // add new ways
    1343             for (size_t ssaId: entry.second)
    1344                 destEntry.insertValue(ssaId);
    1345         }
    1346         else if (notFirstReturn)
    1347         {
    1348             auto csit = curSSAIdMap.find(entry.first);
    1349             // insert to lastSSAIdMap if no ssaIds for regvar in lastSSAIdMap
    1350             dest.lastSSAIdMap.insert({ entry.first,
    1351                         { (csit!=curSSAIdMap.end() ? csit->second : 1)-1 } });
    1352         }
    1353        
    1354         std::cout << "    :";
    1355         for (size_t v: destEntry)
    1356             std::cout << " " << v;
    1357         std::cout << std::endl;
    1358     }
    1359 }
    1360 
    1361 // reduce retSSAIds for calls (for all read before write SSAIds for current code block)
    1362 static void reduceSSAIdsForCalls(FlowStackEntry& entry,
    1363             const std::vector<CodeBlock>& codeBlocks,
    1364             RetSSAIdMap& retSSAIdMap, RoutineMap& routineMap,
    1365             SSAReplacesMap& ssaReplacesMap)
    1366 {
    1367     if (retSSAIdMap.empty())
    1368         return;
    1369     LastSSAIdMap rbwSSAIdMap;
    1370     std::unordered_set<AsmSingleVReg> reduced;
    1371     std::unordered_set<AsmSingleVReg> changed;
    1372     const CodeBlock& cblock = codeBlocks[entry.blockIndex.index];
    1373     // collect rbw SSAIds
    1374     for (const NextBlock next: cblock.nexts)
    1375         if (next.isCall)
    1376         {
    1377             auto it = routineMap.find(next.block); // must find
    1378             for (const auto& rentry: it->second.rbwSSAIdMap)
    1379                 rbwSSAIdMap.insertSSAId(rentry.first,rentry.second);
    1380            
    1381         }
    1382     for (const NextBlock next: cblock.nexts)
    1383         if (next.isCall)
    1384         {
    1385             auto it = routineMap.find(next.block); // must find
    1386             // add changed
    1387             for (const auto& lentry: it->second.lastSSAIdMap)
    1388                 if (rbwSSAIdMap.find(lentry.first) == rbwSSAIdMap.end())
    1389                     changed.insert(lentry.first);
    1390         }
    1391    
    1392     // reduce SSAIds
    1393     for (const auto& rentry: retSSAIdMap)
    1394     {
    1395         auto ssaIdsIt = rbwSSAIdMap.find(rentry.first);
    1396         if (ssaIdsIt != rbwSSAIdMap.end())
    1397         {
    1398             const VectorSet<size_t>& ssaIds = ssaIdsIt->second;
    1399             const VectorSet<size_t>& rssaIds = rentry.second.ssaIds;
    1400             Array<size_t> outSSAIds(ssaIds.size() + rssaIds.size());
    1401             std::copy(rssaIds.begin(), rssaIds.end(), outSSAIds.begin());
    1402             std::copy(ssaIds.begin(), ssaIds.end(), outSSAIds.begin()+rssaIds.size());
    1403            
    1404             std::sort(outSSAIds.begin(), outSSAIds.end());
    1405             outSSAIds.resize(std::unique(outSSAIds.begin(), outSSAIds.end()) -
    1406                         outSSAIds.begin());
    1407             size_t minSSAId = outSSAIds.front();
    1408             if (outSSAIds.size() >= 2)
    1409             {
    1410                 for (auto sit = outSSAIds.begin()+1; sit != outSSAIds.end(); ++sit)
    1411                     insertReplace(ssaReplacesMap, rentry.first, *sit, minSSAId);
    1412                
    1413                 std::cout << "calls retssa ssaid: " << rentry.first.regVar << ":" <<
    1414                         rentry.first.index << std::endl;
    1415             }
    1416            
    1417             for (BlockIndex rblock: rentry.second.routines)
    1418                 routineMap.find(rblock)->second.lastSSAIdMap[rentry.first] =
    1419                             VectorSet<size_t>({ minSSAId });
    1420             reduced.insert(rentry.first);
    1421         }
    1422     }
    1423     for (const AsmSingleVReg& vreg: reduced)
    1424         retSSAIdMap.erase(vreg);
    1425     reduced.clear();
    1426        
    1427     for (const AsmSingleVReg& vreg: changed)
    1428     {
    1429         auto rit = retSSAIdMap.find(vreg);
    1430         if (rit != retSSAIdMap.end())
    1431         {
    1432             // if modified
    1433             // put before removing to revert for other ways after calls
    1434             auto res = entry.prevRetSSAIdSets.insert(*rit);
    1435             if (res.second)
    1436                 res.first->second = rit->second;
    1437             // just remove, if some change without read before
    1438             retSSAIdMap.erase(rit);
    1439         }
    1440     }
    1441 }
    1442 
    1443 static void reduceSSAIds2(std::unordered_map<AsmSingleVReg, size_t>& curSSAIdMap,
    1444             RetSSAIdMap& retSSAIdMap, FlowStackEntry& entry, const SSAEntry& ssaEntry)
    1445 {
    1446     const SSAInfo& sinfo = ssaEntry.second;
    1447     size_t& ssaId = curSSAIdMap[ssaEntry.first];
    1448     auto ssaIdsIt = retSSAIdMap.find(ssaEntry.first);
    1449     if (ssaIdsIt != retSSAIdMap.end() && sinfo.readBeforeWrite)
    1450     {
    1451         auto& ssaIds = ssaIdsIt->second.ssaIds;
    1452         ssaId = ssaIds.front()+1; // plus one
    1453         retSSAIdMap.erase(ssaIdsIt);
    1454     }
    1455     else if (ssaIdsIt != retSSAIdMap.end() && sinfo.ssaIdChange!=0)
    1456     {
    1457         // put before removing to revert for other ways after calls
    1458         auto res = entry.prevRetSSAIdSets.insert(*ssaIdsIt);
    1459         if (res.second)
    1460             res.first->second = ssaIdsIt->second;
    1461         // just remove, if some change without read before
    1462         retSSAIdMap.erase(ssaIdsIt);
    1463     }
    1464 }
    1465 
    1466 // reduce retSSAIds (last SSAIds for regvar) while passing by code block
    1467 // and emits SSA replaces for these ssaids
    1468 static bool reduceSSAIds(std::unordered_map<AsmSingleVReg, size_t>& curSSAIdMap,
    1469             RetSSAIdMap& retSSAIdMap, RoutineMap& routineMap,
    1470             SSAReplacesMap& ssaReplacesMap, FlowStackEntry& entry, SSAEntry& ssaEntry)
    1471 {
    1472     SSAInfo& sinfo = ssaEntry.second;
    1473     size_t& ssaId = curSSAIdMap[ssaEntry.first];
    1474     auto ssaIdsIt = retSSAIdMap.find(ssaEntry.first);
    1475     if (ssaIdsIt != retSSAIdMap.end() && sinfo.readBeforeWrite)
    1476     {
    1477         auto& ssaIds = ssaIdsIt->second.ssaIds;
    1478        
    1479         if (sinfo.ssaId != SIZE_MAX)
    1480         {
    1481             VectorSet<size_t> outSSAIds = ssaIds;
    1482             outSSAIds.insertValue(ssaId-1); // ???
    1483             // already set
    1484             if (outSSAIds.size() >= 1)
    1485             {
    1486                 // reduce to minimal ssaId from all calls
    1487                 std::sort(outSSAIds.begin(), outSSAIds.end());
    1488                 outSSAIds.resize(std::unique(outSSAIds.begin(), outSSAIds.end()) -
    1489                             outSSAIds.begin());
    1490                 // insert SSA replaces
    1491                 if (outSSAIds.size() >= 2)
    1492                 {
    1493                     size_t minSSAId = outSSAIds.front();
    1494                     for (auto sit = outSSAIds.begin()+1; sit != outSSAIds.end(); ++sit)
    1495                         insertReplace(ssaReplacesMap, ssaEntry.first, *sit, minSSAId);
    1496                 }
    1497             }
    1498         }
    1499         else if (ssaIds.size() >= 2)
    1500         {
    1501             // reduce to minimal ssaId from all calls
    1502             std::sort(ssaIds.begin(), ssaIds.end());
    1503             ssaIds.resize(std::unique(ssaIds.begin(), ssaIds.end()) - ssaIds.begin());
    1504             // insert SSA replaces
    1505             size_t minSSAId = ssaIds.front();
    1506             for (auto sit = ssaIds.begin()+1; sit != ssaIds.end(); ++sit)
    1507                 insertReplace(ssaReplacesMap, ssaEntry.first, *sit, minSSAId);
    1508             ssaId = minSSAId+1; // plus one
    1509         }
    1510         else if (ssaIds.size() == 1)
    1511             ssaId = ssaIds.front()+1; // plus one
    1512        
    1513         std::cout << "retssa ssaid: " << ssaEntry.first.regVar << ":" <<
    1514                 ssaEntry.first.index << ": " << ssaId << std::endl;
    1515         // replace smallest ssaId in routineMap lastSSAId entry
    1516         // reduce SSAIds replaces
    1517         for (BlockIndex rblock: ssaIdsIt->second.routines)
    1518         {
    1519             RoutineData& rdata = routineMap.find(rblock)->second;
    1520             size_t rbwRetSSAId = SIZE_MAX;
    1521             auto rbwIt = rdata.rbwSSAIdMap.find(ssaEntry.first);
    1522             auto rlsit = rdata.lastSSAIdMap.find(ssaEntry.first);
    1523             if (rbwIt != rdata.rbwSSAIdMap.end() && rlsit->second.hasValue(rbwIt->second))
    1524                 rbwRetSSAId = rbwIt->second;
    1525             rlsit->second = VectorSet<size_t>({ ssaId-1 });
    1526             if (rbwRetSSAId != SIZE_MAX)
    1527             {
    1528                 std::cout << "  keep retSSAId rbw: " << rbwRetSSAId << std::endl;
    1529                 // add retSSAId without changes (in way without regvar changes)
    1530                 rlsit->second.insertValue(rbwRetSSAId);
    1531             }
    1532         }
    1533         // finally remove from container (because obsolete)
    1534         retSSAIdMap.erase(ssaIdsIt);
    1535         return true;
    1536     }
    1537     else if (ssaIdsIt != retSSAIdMap.end() && sinfo.ssaIdChange!=0)
    1538     {
    1539         // put before removing to revert for other ways after calls
    1540         auto res = entry.prevRetSSAIdSets.insert(*ssaIdsIt);
    1541         if (res.second)
    1542             res.first->second = ssaIdsIt->second;
    1543         // just remove, if some change without read before
    1544         retSSAIdMap.erase(ssaIdsIt);
    1545     }
    1546     return false;
    1547 }
    1548 
    1549 // update single current SSAId for routine and optionally lastSSAIdMap if returns
    1550 // has been encountered but not regvar
    1551 static void updateRoutineData(RoutineData& rdata, const SSAEntry& ssaEntry,
    1552                 size_t prevSSAId)
    1553 {
    1554     const SSAInfo& sinfo = ssaEntry.second;
    1555     bool beforeFirstAccess = true;
    1556     // put first SSAId before write
    1557     if (sinfo.readBeforeWrite)
    1558     {
    1559         //std::cout << "PutCRBW: " << sinfo.ssaIdBefore << std::endl;
    1560         if (!rdata.rbwSSAIdMap.insert({ ssaEntry.first, prevSSAId }).second)
    1561             // if already added
    1562             beforeFirstAccess = false;
    1563        
    1564         rdata.origRbwSSAIdMap.insert({ ssaEntry.first,
    1565                         ssaEntry.second.ssaIdBefore }).second;
    1566     }
    1567    
    1568     if (sinfo.ssaIdChange != 0)
    1569     {
    1570         //std::cout << "PutC: " << sinfo.ssaIdLast << std::endl;
    1571         auto res = rdata.curSSAIdMap.insert({ ssaEntry.first, { sinfo.ssaIdLast } });
    1572         // put last SSAId
    1573         if (!res.second)
    1574         {
    1575             beforeFirstAccess = false;
    1576             // if not inserted
    1577             VectorSet<size_t>& ssaIds = res.first->second;
    1578             ssaIds.clear(); // clear all ssaIds in currentSSAID entry
    1579             ssaIds.insertValue(sinfo.ssaIdLast);
    1580         }
    1581         // add readbefore if in previous returns if not added yet
    1582         if (rdata.notFirstReturn && beforeFirstAccess)
    1583         {
    1584             rdata.lastSSAIdMap.insert({ ssaEntry.first, { prevSSAId } });
    1585             for (auto& loopEnd: rdata.loopEnds)
    1586                 loopEnd.second.ssaIdMap.insert({ ssaEntry.first, { prevSSAId } });
    1587         }
    1588     }
    1589     else
    1590     {
    1591         // insert read ssaid if no change
    1592         auto res = rdata.curSSAIdMap.insert({ ssaEntry.first, { prevSSAId } });
    1593         if (!res.second)
    1594         {
    1595             VectorSet<size_t>& ssaIds = res.first->second;
    1596             ssaIds.insertValue(prevSSAId);
    1597         }
    1598     }
    1599 }
    1600 
    1601 static void initializePrevRetSSAIds(
    1602             const std::unordered_map<AsmSingleVReg, size_t>& curSSAIdMap,
    1603             const RetSSAIdMap& retSSAIdMap, const RoutineData& rdata,
    1604             FlowStackEntry& entry)
    1605 {
    1606     for (const auto& v: rdata.lastSSAIdMap)
    1607     {
    1608         auto res = entry.prevRetSSAIdSets.insert({v.first, {}});
    1609         if (!res.second)
    1610             continue; // already added, do not change
    1611         auto rfit = retSSAIdMap.find(v.first);
    1612         if (rfit != retSSAIdMap.end())
    1613             res.first->second = rfit->second;
    1614        
    1615         auto csit = curSSAIdMap.find(v.first);
    1616         res.first->second.prevSSAId = (csit!=curSSAIdMap.end() ? csit->second : 1);
    1617     }
    1618 }
    1619 
    1620 // revert retSSAIdMap while leaving from code block
    1621 static void revertRetSSAIdMap(std::unordered_map<AsmSingleVReg, size_t>& curSSAIdMap,
    1622             RetSSAIdMap& retSSAIdMap, FlowStackEntry& entry, RoutineData* rdata)
    1623 {
    1624     // revert retSSAIdMap
    1625     for (auto v: entry.prevRetSSAIdSets)
    1626     {
    1627         auto rfit = retSSAIdMap.find(v.first);
    1628         if (rdata!=nullptr && rfit != retSSAIdMap.end())
    1629         {
    1630             VectorSet<size_t>& ssaIds = rdata->curSSAIdMap[v.first];
    1631             for (size_t ssaId: rfit->second.ssaIds)
    1632                 ssaIds.eraseValue(ssaId);
    1633         }
    1634        
    1635         if (!v.second.ssaIds.empty())
    1636         {
    1637             // just add if previously present
    1638             if (rfit != retSSAIdMap.end())
    1639                 rfit->second = v.second;
    1640             else
    1641                 retSSAIdMap.insert(v);
    1642         }
    1643         else // erase if empty
    1644             retSSAIdMap.erase(v.first);
    1645        
    1646         size_t oldSSAId = curSSAIdMap[v.first]-1;
    1647         curSSAIdMap[v.first] = v.second.prevSSAId;
    1648         if (rdata!=nullptr)
    1649         {
    1650             VectorSet<size_t>& ssaIds = rdata->curSSAIdMap[v.first];
    1651             ssaIds.eraseValue(oldSSAId); // ??? need extra constraints
    1652             for (size_t ssaId: v.second.ssaIds)
    1653                 ssaIds.insertValue(ssaId);
    1654             if (v.second.ssaIds.empty())
    1655             {
    1656                 auto cit = curSSAIdMap.find(v.first);
    1657                 ssaIds.insertValue((cit!=curSSAIdMap.end() ? cit->second : 1)-1);
    1658             }
    1659            
    1660             std::cout << " popentry2 " << entry.blockIndex << ": " <<
    1661                     v.first.regVar << ":" << v.first.index << ":";
    1662             for (size_t v: ssaIds)
    1663                 std::cout << " " << v;
    1664             std::cout << std::endl;
    1665         }
    1666     }
    1667 }
    1668 
    1669 // update current SSAId in curSSAIdMap for routine while leaving from code block
    1670 static void updateRoutineCurSSAIdMap(RoutineData* rdata, const SSAEntry& ssaEntry,
    1671             const FlowStackEntry& entry, size_t curSSAId, size_t nextSSAId)
    1672 {
    1673     VectorSet<size_t>& ssaIds = rdata->curSSAIdMap[ssaEntry.first];
    1674     std::cout << " pushentry " << entry.blockIndex << ": " <<
    1675                 ssaEntry.first.regVar << ":" << ssaEntry.first.index << ":";
    1676     for (size_t v: ssaIds)
    1677         std::cout << " " << v;
    1678     std::cout << std::endl;
    1679    
    1680     // if cblock with some children
    1681     if (nextSSAId != curSSAId)
    1682         ssaIds.eraseValue(nextSSAId-1);
    1683    
    1684     // push previous SSAId to lastSSAIdMap (later will be replaced)
    1685     ssaIds.insertValue(curSSAId-1);
    1686    
    1687     std::cout << " popentry " << entry.blockIndex << ": " <<
    1688                 ssaEntry.first.regVar << ":" << ssaEntry.first.index << ":";
    1689     for (size_t v: ssaIds)
    1690         std::cout << " " << v;
    1691     std::cout << std::endl;
    1692 }
    1693 
    1694 static bool tryAddLoopEnd(const FlowStackEntry& entry, BlockIndex routineBlock,
    1695                 RoutineData& rdata, bool isLoop, bool noMainLoop)
    1696 {
    1697     if (isLoop && (!noMainLoop || routineBlock != entry.blockIndex))
    1698     {
    1699         // handle loops
    1700         std::cout << "  join loop ssaids: " << entry.blockIndex << std::endl;
    1701         // add to routine data loopEnds
    1702         auto loopsit2 = rdata.loopEnds.find(entry.blockIndex);
    1703         if (loopsit2 != rdata.loopEnds.end())
    1704         {
    1705             if (!loopsit2->second.passed)
    1706                 // still in loop join ssaid map
    1707                 joinLastSSAIdMap(loopsit2->second.ssaIdMap, rdata.curSSAIdMap);
    1708         }
    1709         else
    1710             rdata.loopEnds.insert({ entry.blockIndex, { rdata.curSSAIdMap, false } });
    1711         return true;
    1712     }
    1713     return false;
    1714 }
    1715 
    1716 
    1717 static void createRoutineData(const std::vector<CodeBlock>& codeBlocks,
    1718         std::unordered_map<AsmSingleVReg, size_t>& curSSAIdMap,
    1719         const std::unordered_set<BlockIndex>& loopBlocks,
    1720         const std::unordered_set<BlockIndex>& callBlocks,
    1721         const ResSecondPointsToCache& subroutToCache,
    1722         SimpleCache<BlockIndex, RoutineData>& subroutinesCache,
    1723         const RoutineMap& routineMap, RoutineData& rdata,
    1724         BlockIndex routineBlock, bool noMainLoop = false,
    1725         const CBlockBitPool& prevFlowStackBlocks = {})
    1726 {
    1727     std::cout << "--------- createRoutineData ----------------\n";
    1728     CBlockBitPool visited(codeBlocks.size(), false);
    1729     CBlockBitPool haveReturnBlocks(codeBlocks.size(), false);
    1730    
    1731     VectorSet<BlockIndex> activeLoops;
    1732     SubrLoopsMap subrLoopsMap;
    1733     SubrLoopsMap loopSubrsMap;
    1734     RoutineMap subrDataForLoopMap;
    1735     std::deque<FlowStackEntry> flowStack;
    1736     CBlockBitPool flowStackBlocks(codeBlocks.size(), false);
    1737     if (!prevFlowStackBlocks.empty())
    1738         flowStackBlocks = prevFlowStackBlocks;
    1739     // last SSA ids map from returns
    1740     RetSSAIdMap retSSAIdMap;
    1741     flowStack.push_back({ routineBlock, 0 });
    1742     flowStackBlocks[routineBlock] = true;
    1743    
    1744    
    1745     while (!flowStack.empty())
    1746     {
    1747         FlowStackEntry& entry = flowStack.back();
    1748         const CodeBlock& cblock = codeBlocks[entry.blockIndex.index];
    1749        
    1750         /*std::cout << ":: rdata.curSSAIdMap #" << entry.blockIndex << "\n";
    1751         for (const auto& v: rdata.curSSAIdMap)
    1752         {
    1753             std::cout << "  :: " << v.first.regVar << ":" << v.first.index << ":";
    1754             for (size_t ssaId: v.second)
    1755                 std::cout << " " << ssaId;
    1756             std::cout << "\n";
    1757         }*/
    1758        
    1759         auto addSubroutine = [&](
    1760             std::unordered_map<BlockIndex, LoopSSAIdMap>::const_iterator loopsit2,
    1761             bool applyToMainRoutine)
    1762         {
    1763             if (subroutinesCache.hasKey(entry.blockIndex))
    1764             {
    1765                 // if already put, just applyToMainRoutine if needed
    1766                 if (applyToMainRoutine &&
    1767                     loopBlocks.find(entry.blockIndex) != loopBlocks.end() &&
    1768                     loopsit2 != rdata.loopEnds.end())
    1769                 {
    1770                     RoutineData* subRdata = subroutinesCache.use(entry.blockIndex);
    1771                     joinLastSSAIdMap(rdata.lastSSAIdMap, loopsit2->second.ssaIdMap,
    1772                                         *subRdata, true);
    1773                 }
    1774                 return;
    1775             }
    1776            
    1777             RoutineData subrData;
    1778             const bool oldFB = flowStackBlocks[entry.blockIndex];
    1779             flowStackBlocks[entry.blockIndex] = !oldFB;
    1780             createRoutineData(codeBlocks, curSSAIdMap, loopBlocks, callBlocks,
    1781                     subroutToCache, subroutinesCache, routineMap, subrData,
    1782                     entry.blockIndex, true, flowStackBlocks);
    1783             RoutineData subrDataCopy;
    1784             flowStackBlocks[entry.blockIndex] = oldFB;
    1785            
    1786             if (loopBlocks.find(entry.blockIndex) != loopBlocks.end())
    1787             {   // leave from loop point
    1788                 std::cout << "   loopfound " << entry.blockIndex << std::endl;
    1789                 if (loopsit2 != rdata.loopEnds.end())
    1790                 {
    1791                     subrDataCopy = subrData;
    1792                     subrDataForLoopMap.insert({ entry.blockIndex, subrDataCopy });
    1793                     std::cout << "   loopssaId2Map: " <<
    1794                             entry.blockIndex << std::endl;
    1795                     joinLastSSAIdMap(subrData.lastSSAIdMap,
    1796                             loopsit2->second.ssaIdMap, subrData, true);
    1797                     std::cout << "   loopssaIdMap2End: " << std::endl;
    1798                     if (applyToMainRoutine)
    1799                         joinLastSSAIdMap(rdata.lastSSAIdMap, loopsit2->second.ssaIdMap,
    1800                                         subrDataCopy, true);
    1801                 }
    1802             }
    1803            
    1804             // apply loop to subroutines
    1805             auto it = loopSubrsMap.find(entry.blockIndex);
    1806             if (it != loopSubrsMap.end())
    1807             {
    1808                 std::cout << "    found loopsubrsmap: " << entry.blockIndex << ":";
    1809                 for (BlockIndex subr: it->second)
    1810                 {
    1811                     std::cout << " " << subr;
    1812                     RoutineData* subrData2 = subroutinesCache.use(subr);
    1813                     if (subrData2 == nullptr)
    1814                         continue;
    1815                     RoutineData subrData2Copy = *subrData2;
    1816                     std::cout << "*";
    1817                     joinLastSSAIdMap(subrData2Copy.lastSSAIdMap,
    1818                             loopsit2->second.ssaIdMap, subrDataCopy, false);
    1819                     // reinsert subroutine into subroutine cache
    1820                     subrData2Copy.calculateWeight();
    1821                     subroutinesCache.put(subr, subrData2Copy);
    1822                 }
    1823                 std::cout << "\n";
    1824             }
    1825             // apply loops to this subroutine
    1826             auto it2 = subrLoopsMap.find(entry.blockIndex);
    1827             if (it2 != subrLoopsMap.end())
    1828             {
    1829                 std::cout << "    found subrloopsmap: " << entry.blockIndex << ":";
    1830                 for (auto lit2 = it2->second.rbegin(); lit2 != it2->second.rend(); ++lit2)
    1831                 {
    1832                     BlockIndex loop = *lit2;
    1833                     auto loopsit3 = rdata.loopEnds.find(loop);
    1834                     if (loopsit3 == rdata.loopEnds.end() ||
    1835                         activeLoops.hasValue(loop))
    1836                         continue;
    1837                     std::cout << " " << loop;
    1838                     auto  itx = subrDataForLoopMap.find(loop);
    1839                     if (itx != subrDataForLoopMap.end())
    1840                         joinLastSSAIdMap(subrData.lastSSAIdMap,
    1841                                 loopsit3->second.ssaIdMap, itx->second, false);
    1842                 }
    1843                 std::cout << "\n";
    1844             }
    1845            
    1846             subrData.calculateWeight();
    1847             subroutinesCache.put(entry.blockIndex, subrData);
    1848         };
    1849        
    1850         if (entry.nextIndex == 0)
    1851         {
    1852             bool isLoop = loopBlocks.find(entry.blockIndex) != loopBlocks.end();
    1853            
    1854             if (!prevFlowStackBlocks.empty() && prevFlowStackBlocks[entry.blockIndex])
    1855             {
    1856                 tryAddLoopEnd(entry, routineBlock, rdata, isLoop, noMainLoop);
    1857                
    1858                 flowStackBlocks[entry.blockIndex] = !flowStackBlocks[entry.blockIndex];
    1859                 flowStack.pop_back();
    1860                 continue;
    1861             }
    1862            
    1863             // process current block
    1864             const RoutineData* cachedRdata = nullptr;
    1865            
    1866             if (routineBlock != entry.blockIndex)
    1867             {
    1868                 cachedRdata = subroutinesCache.use(entry.blockIndex);
    1869                 if (cachedRdata == nullptr)
    1870                 {
    1871                     // try in routine map
    1872                     auto rit = routineMap.find(entry.blockIndex);
    1873                     if (rit != routineMap.end())
    1874                         cachedRdata = &rit->second;
    1875                 }
    1876                 if (!isLoop && visited[entry.blockIndex] && cachedRdata == nullptr &&
    1877                     subroutToCache.count(entry.blockIndex)!=0)
    1878                 {
    1879                     auto loopsit2 = rdata.loopEnds.find(entry.blockIndex);
    1880                     std::cout << "-- subrcache2 for " << entry.blockIndex << std::endl;
    1881                     addSubroutine(loopsit2, false);
    1882                     cachedRdata = subroutinesCache.use(entry.blockIndex);
    1883                 }
    1884             }
    1885            
    1886             if (cachedRdata != nullptr)
    1887             {
    1888                 std::cout << "use cached subr " << entry.blockIndex << std::endl;
    1889                 std::cout << "procret2: " << entry.blockIndex << std::endl;
    1890                 if (visited[entry.blockIndex] && !haveReturnBlocks[entry.blockIndex])
    1891                 {
    1892                     // no joining. no returns
    1893                     std::cout << "procretend2 nojoin" << std::endl;
    1894                     flowStackBlocks[entry.blockIndex] = !flowStackBlocks[entry.blockIndex];
    1895                     flowStack.pop_back();
    1896                     continue;
    1897                 }
    1898                 joinLastSSAIdMap(rdata.lastSSAIdMap, rdata.curSSAIdMap, *cachedRdata);
    1899                 // get not given rdata curSSAIdMap ssaIds but present in cachedRdata
    1900                 // curSSAIdMap
    1901                 for (const auto& entry: cachedRdata->curSSAIdMap)
    1902                     if (rdata.curSSAIdMap.find(entry.first) == rdata.curSSAIdMap.end())
    1903                     {
    1904                         auto cit = curSSAIdMap.find(entry.first);
    1905                         size_t prevSSAId = (cit!=curSSAIdMap.end() ? cit->second : 1)-1;
    1906                         rdata.curSSAIdMap.insert({ entry.first, { prevSSAId } });
    1907                        
    1908                         if (rdata.notFirstReturn)
    1909                         {
    1910                             rdata.lastSSAIdMap.insertSSAId(entry.first, prevSSAId);
    1911                             for (auto& loopEnd: rdata.loopEnds)
    1912                                 loopEnd.second.ssaIdMap.
    1913                                         insertSSAId(entry.first, prevSSAId);
    1914                         }
    1915                     }
    1916                
    1917                 // join loopEnds
    1918                 for (const auto& loopEnd: cachedRdata->loopEnds)
    1919                 {
    1920                     auto res = rdata.loopEnds.insert({ loopEnd.first, LoopSSAIdMap{} });
    1921                     // true - do not add cached rdata loopend, because it was added
    1922                     joinLastSSAIdMapInt(res.first->second.ssaIdMap, rdata.curSSAIdMap,
    1923                                 cachedRdata->curSSAIdMap, loopEnd.second.ssaIdMap, true);
    1924                 }
    1925                 std::cout << "procretend2" << std::endl;
    1926                 flowStackBlocks[entry.blockIndex] = !flowStackBlocks[entry.blockIndex];
    1927                 flowStack.pop_back();
    1928                 // propagate haveReturn to previous block
    1929                 flowStack.back().haveReturn = true;
    1930                 haveReturnBlocks[flowStack.back().blockIndex] = true;
    1931                 continue;
    1932             }
    1933             else if (!visited[entry.blockIndex])
    1934             {
    1935                 // set up loops for which subroutine is present
    1936                 if (subroutToCache.count(entry.blockIndex)!=0 && !activeLoops.empty())
    1937                 {
    1938                     subrLoopsMap.insert({ entry.blockIndex, activeLoops });
    1939                     for (BlockIndex loop: activeLoops)
    1940                     {
    1941                         auto res = loopSubrsMap.insert({ loop, { entry.blockIndex } });
    1942                         if (!res.second)
    1943                             res.first->second.insertValue(entry.blockIndex);
    1944                     }
    1945                 }
    1946                
    1947                 if (loopBlocks.find(entry.blockIndex) != loopBlocks.end())
    1948                     activeLoops.insertValue(entry.blockIndex);
    1949                 std::cout << "proc: " << entry.blockIndex << std::endl;
    1950                 visited[entry.blockIndex] = true;
    1951                
    1952                 for (const auto& ssaEntry: cblock.ssaInfoMap)
    1953                     if (ssaEntry.first.regVar != nullptr)
    1954                     {
    1955                         reduceSSAIds2(curSSAIdMap, retSSAIdMap, entry, ssaEntry);
    1956                         // put data to routine data
    1957                         updateRoutineData(rdata, ssaEntry, curSSAIdMap[ssaEntry.first]-1);
    1958                        
    1959                         if (ssaEntry.second.ssaIdChange!=0)
    1960                             curSSAIdMap[ssaEntry.first] = ssaEntry.second.ssaIdLast+1;
    1961                     }
    1962             }
    1963             else
    1964             {
    1965                 tryAddLoopEnd(entry, routineBlock, rdata, isLoop, noMainLoop);
    1966                 flowStackBlocks[entry.blockIndex] = !flowStackBlocks[entry.blockIndex];
    1967                 flowStack.pop_back();
    1968                 continue;
    1969             }
    1970         }
    1971        
    1972         // join and skip calls
    1973         {
    1974             std::vector<BlockIndex> calledRoutines;
    1975             for (; entry.nextIndex < cblock.nexts.size() &&
    1976                         cblock.nexts[entry.nextIndex].isCall; entry.nextIndex++)
    1977             {
    1978                 BlockIndex rblock = cblock.nexts[entry.nextIndex].block;
    1979                 if (callBlocks.find(rblock) != callBlocks.end())
    1980                     rblock.pass = 1;
    1981                 if (rblock != routineBlock)
    1982                     calledRoutines.push_back(rblock);
    1983             }
    1984            
    1985             if (!calledRoutines.empty())
    1986             {
    1987                 // toNotClear - regvar to no keep (because is used in called routines)
    1988                 std::unordered_set<AsmSingleVReg> toNotClear;
    1989                 // if regvar any called routine (used)
    1990                 std::unordered_set<AsmSingleVReg> allInCalls;
    1991                 for (BlockIndex rblock: calledRoutines)
    1992                 {
    1993                     const RoutineData& srcRdata = routineMap.find(rblock)->second;
    1994                     // for next recursion pass call - choose origRvwSSAIdMap
    1995                     // otherwise - standard rbwSsaIdMap
    1996                     const std::unordered_map<AsmSingleVReg, size_t>& srcRbwSSAIdMap =
    1997                         (entry.blockIndex.pass == 0 && rblock.pass!=0) ?
    1998                         srcRdata.origRbwSSAIdMap : srcRdata.rbwSSAIdMap;
    1999                     if (entry.blockIndex.pass == 0 && rblock.pass!=0)
    2000                         std::cout << "choose origRbwSSAIdMap: " << rblock << std::endl;
    2001                        
    2002                     for (const auto& rbw: srcRbwSSAIdMap)
    2003                     {
    2004                         allInCalls.insert(rbw.first);
    2005                         auto lsit = srcRdata.lastSSAIdMap.find(rbw.first);
    2006                         if (lsit != srcRdata.lastSSAIdMap.end() &&
    2007                              lsit->second.hasValue(rbw.second))
    2008                             // if returned not modified, then do not clear this regvar
    2009                             toNotClear.insert(rbw.first);
    2010                     }
    2011                     for (const auto& rbw: srcRdata.lastSSAIdMap)
    2012                         allInCalls.insert(rbw.first);
    2013                 }
    2014                 for (auto& entry: rdata.curSSAIdMap)
    2015                     // if any called routine and if to clear
    2016                     if (allInCalls.find(entry.first) != allInCalls.end() &&
    2017                         toNotClear.find(entry.first) == toNotClear.end())
    2018                         // not found
    2019                         entry.second.clear();
    2020            
    2021                 for (BlockIndex rblock: calledRoutines)
    2022                     joinRoutineData(rdata, routineMap.find(rblock)->second,
    2023                                     curSSAIdMap, rdata.notFirstReturn);
    2024             }
    2025         }
    2026        
    2027         if (entry.nextIndex < cblock.nexts.size())
    2028         {
    2029             const BlockIndex nextBlock = { cblock.nexts[entry.nextIndex].block,
    2030                         entry.blockIndex.pass };
    2031             flowStack.push_back({ nextBlock, 0 });
    2032             // negate - if true (already in flowstack, then popping keep this state)
    2033             flowStackBlocks[nextBlock] = !flowStackBlocks[nextBlock];
    2034             entry.nextIndex++;
    2035         }
    2036         else if (((entry.nextIndex==0 && cblock.nexts.empty()) ||
    2037                 // if have any call then go to next block
    2038                 (cblock.haveCalls && entry.nextIndex==cblock.nexts.size())) &&
    2039                  !cblock.haveReturn && !cblock.haveEnd)
    2040         {
    2041             if (entry.nextIndex!=0) // if back from calls (just return from calls)
    2042             {
    2043                 for (const NextBlock& next: cblock.nexts)
    2044                     if (next.isCall)
    2045                     {
    2046                         //std::cout << "joincall:"<< next.block << std::endl;
    2047                         BlockIndex rblock(next.block, entry.blockIndex.pass);
    2048                         if (callBlocks.find(next.block) != callBlocks.end())
    2049                             rblock.pass = 1;
    2050                         auto it = routineMap.find(rblock); // must find
    2051                         initializePrevRetSSAIds(curSSAIdMap, retSSAIdMap,
    2052                                     it->second, entry);
    2053                        
    2054                         joinRetSSAIdMap(retSSAIdMap, it->second.lastSSAIdMap, rblock);
    2055                     }
    2056             }
    2057             const BlockIndex nextBlock = entry.blockIndex+1;
    2058             flowStack.push_back({ nextBlock, 0 });
    2059             // negate - if true (already in flowstack, then popping keep this state)
    2060             flowStackBlocks[nextBlock] = !flowStackBlocks[nextBlock];
    2061             entry.nextIndex++;
    2062         }
    2063         else
    2064         {
    2065             std::cout << "popstart: " << entry.blockIndex << std::endl;
    2066             if (cblock.haveReturn)
    2067             {
    2068                 std::cout << "procret: " << entry.blockIndex << std::endl;
    2069                 joinLastSSAIdMap(rdata.lastSSAIdMap, rdata.curSSAIdMap);
    2070                 std::cout << "procretend" << std::endl;
    2071                 rdata.notFirstReturn = true;
    2072                 entry.haveReturn = true;
    2073                 haveReturnBlocks[entry.blockIndex] = true;
    2074             }
    2075            
    2076             const bool curHaveReturn = entry.haveReturn;
    2077            
    2078             // revert retSSAIdMap
    2079             revertRetSSAIdMap(curSSAIdMap, retSSAIdMap, entry, &rdata);
    2080             //
    2081            
    2082             for (const auto& ssaEntry: cblock.ssaInfoMap)
    2083             {
    2084                 if (ssaEntry.first.regVar == nullptr)
    2085                     continue;
    2086                 size_t curSSAId = ssaEntry.second.ssaIdBefore+1;
    2087                 size_t nextSSAId = (ssaEntry.second.ssaIdLast != SIZE_MAX) ?
    2088                     ssaEntry.second.ssaIdLast+1 : curSSAId;
    2089                 curSSAIdMap[ssaEntry.first] = curSSAId;
    2090                
    2091                 std::cout << "popcurnext: " << ssaEntry.first.regVar <<
    2092                             ":" << ssaEntry.first.index << ": " <<
    2093                             nextSSAId << ", " << curSSAId << std::endl;
    2094                
    2095                 updateRoutineCurSSAIdMap(&rdata, ssaEntry, entry, curSSAId, nextSSAId);
    2096             }
    2097            
    2098             activeLoops.eraseValue(entry.blockIndex);
    2099            
    2100             auto loopsit2 = rdata.loopEnds.find(entry.blockIndex);
    2101             if (loopBlocks.find(entry.blockIndex) != loopBlocks.end())
    2102             {
    2103                 if (loopsit2 != rdata.loopEnds.end())
    2104                 {
    2105                     std::cout << "   mark loopblocks passed: " <<
    2106                                 entry.blockIndex << std::endl;
    2107                     // mark that loop has passed fully
    2108                     loopsit2->second.passed = true;
    2109                 }
    2110                 else
    2111                     std::cout << "   loopblocks nopassed: " <<
    2112                                 entry.blockIndex << std::endl;
    2113             }
    2114            
    2115             if ((!noMainLoop || flowStack.size() > 1) &&
    2116                 subroutToCache.count(entry.blockIndex)!=0)
    2117             { //put to cache
    2118                 std::cout << "-- subrcache for " << entry.blockIndex << std::endl;
    2119                 addSubroutine(loopsit2, true);
    2120             }
    2121            
    2122             flowStackBlocks[entry.blockIndex] = false;
    2123             std::cout << "pop: " << entry.blockIndex << std::endl;
    2124            
    2125             flowStack.pop_back();
    2126             // set up haveReturn
    2127             if (!flowStack.empty())
    2128             {
    2129                 flowStack.back().haveReturn |= curHaveReturn;
    2130                 haveReturnBlocks[flowStack.back().blockIndex] =
    2131                         flowStack.back().haveReturn;
    2132             }
    2133         }
    2134     }
    2135     std::cout << "--------- createRoutineData end ------------\n";
    2136 }
    2137 
    2138 void AsmRegAllocator::createSSAData(ISAUsageHandler& usageHandler)
    2139 {
    2140     if (codeBlocks.empty())
    2141         return;
    2142     usageHandler.rewind();
    2143     auto cbit = codeBlocks.begin();
    2144     AsmRegVarUsage rvu;
    2145     if (!usageHandler.hasNext())
    2146         return; // do nothing if no regusages
    2147     rvu = usageHandler.nextUsage();
    2148    
    2149     cxuint regRanges[MAX_REGTYPES_NUM*2];
    2150     cxuint realRegsCount[MAX_REGTYPES_NUM];
    2151     std::fill(realRegsCount, realRegsCount+MAX_REGTYPES_NUM, 0);
    2152     size_t regTypesNum;
    2153     assembler.isaAssembler->getRegisterRanges(regTypesNum, regRanges);
    2154    
    2155     while (true)
    2156     {
    2157         while (cbit != codeBlocks.end() && cbit->end <= rvu.offset)
    2158         {
    2159             cbit->usagePos = usageHandler.getReadPos();
    2160             ++cbit;
    2161         }
    2162         if (cbit == codeBlocks.end())
    2163             break;
    2164         // skip rvu's before codeblock
    2165         while (rvu.offset < cbit->start && usageHandler.hasNext())
    2166             rvu = usageHandler.nextUsage();
    2167         if (rvu.offset < cbit->start)
    2168             break;
    2169        
    2170         cbit->usagePos = usageHandler.getReadPos();
    2171         while (rvu.offset < cbit->end)
    2172         {
    2173             // process rvu
    2174             // only if regVar
    2175             for (uint16_t rindex = rvu.rstart; rindex < rvu.rend; rindex++)
    2176             {
    2177                 auto res = cbit->ssaInfoMap.insert(
    2178                         { AsmSingleVReg{ rvu.regVar, rindex }, SSAInfo() });
    2179                
    2180                 SSAInfo& sinfo = res.first->second;
    2181                 if (res.second)
    2182                     sinfo.firstPos = rvu.offset;
    2183                 if ((rvu.rwFlags & ASMRVU_READ) != 0 && (sinfo.ssaIdChange == 0 ||
    2184                     // if first write RVU instead read RVU
    2185                     (sinfo.ssaIdChange == 1 && sinfo.firstPos==rvu.offset)))
    2186                     sinfo.readBeforeWrite = true;
    2187                 /* change SSA id only for write-only regvars -
    2188                  *   read-write place can not have two different variables */
    2189                 if (rvu.rwFlags == ASMRVU_WRITE && rvu.regField!=ASMFIELD_NONE)
    2190                     sinfo.ssaIdChange++;
    2191                 if (rvu.regVar==nullptr)
    2192                     sinfo.ssaIdBefore = sinfo.ssaIdFirst =
    2193                             sinfo.ssaId = sinfo.ssaIdLast = 0;
    2194             }
    2195             // get next rvusage
    2196             if (!usageHandler.hasNext())
    2197                 break;
    2198             rvu = usageHandler.nextUsage();
    2199         }
    2200         ++cbit;
    2201     }
    2202    
    2203     size_t rbwCount = 0;
    2204     size_t wrCount = 0;
    2205    
    2206     SimpleCache<BlockIndex, RoutineData> subroutinesCache(codeBlocks.size()<<3);
    2207    
    2208     std::deque<CallStackEntry> callStack;
    2209     std::deque<FlowStackEntry> flowStack;
    2210     // total SSA count
    2211     std::unordered_map<AsmSingleVReg, size_t> totalSSACountMap;
    2212     // last SSA ids map from returns
    2213     RetSSAIdMap retSSAIdMap;
    2214     // last SSA ids in current way in code flow
    2215     std::unordered_map<AsmSingleVReg, size_t> curSSAIdMap;
    2216     // routine map - routine datas map, value - last SSA ids map
    2217     RoutineMap routineMap;
    2218     // key - current res first key, value - previous first key and its flowStack pos
    2219     PrevWaysIndexMap prevWaysIndexMap;
    2220     // to track ways last block indices pair: block index, flowStackPos)
    2221     std::pair<BlockIndex, size_t> lastCommonCacheWayPoint{ SIZE_MAX, SIZE_MAX };
    2222     CBlockBitPool isRoutineGen(codeBlocks.size(), false);
    2223    
    2224     CBlockBitPool waysToCache(codeBlocks.size(), false);
    2225     CBlockBitPool flowStackBlocks(codeBlocks.size(), false);
    2226     // subroutToCache - true if given block begin subroutine to cache
    2227     ResSecondPointsToCache cblocksToCache(codeBlocks.size());
    2228     CBlockBitPool visited(codeBlocks.size(), false);
    2229     flowStack.push_back({ 0, 0 });
    2230     flowStackBlocks[0] = true;
    2231     std::unordered_set<BlockIndex> callBlocks;
    2232     std::unordered_set<BlockIndex> loopBlocks;
    2233     std::unordered_set<size_t> recurseBlocks;
    2234    
    2235     /** INFO if you want to get code changedRegVars between recursions you get 3984
    2236      * this stuff has been deleted */
    2237    
    2238     std::unordered_map<size_t, std::unordered_map<AsmSingleVReg, size_t> >
    2239             curSSAIdMapStateMap;
    2240    
    2241     /*
    2242      * main loop to fill up ssaInfos
    2243      */
    2244     while (!flowStack.empty())
    2245     {
    2246         FlowStackEntry& entry = flowStack.back();
    2247         CodeBlock& cblock = codeBlocks[entry.blockIndex.index];
    2248        
    2249         if (entry.nextIndex == 0)
    2250         {
    2251             // process current block
    2252             if (!visited[entry.blockIndex])
    2253             {
    2254                 std::cout << "proc: " << entry.blockIndex << std::endl;
    2255                 visited[entry.blockIndex] = true;
    2256                
    2257                 for (auto& ssaEntry: cblock.ssaInfoMap)
    2258                 {
    2259                     SSAInfo& sinfo = ssaEntry.second;
    2260                     if (ssaEntry.first.regVar==nullptr)
    2261                     {
    2262                         // TODO - pass registers through SSA marking and resolving
    2263                         sinfo.ssaIdChange = 0; // zeroing SSA changes
    2264                         continue; // no change for registers
    2265                     }
    2266                    
    2267                     if (sinfo.ssaId != SIZE_MAX)
    2268                     {
    2269                         // already initialized
    2270                         reduceSSAIds(curSSAIdMap, retSSAIdMap,
    2271                                 routineMap, ssaReplacesMap, entry, ssaEntry);
    2272                         if (sinfo.ssaIdChange!=0)
    2273                             curSSAIdMap[ssaEntry.first] = sinfo.ssaIdLast+1;
    2274                        
    2275                         // count read before writes (for cache weight)
    2276                         if (sinfo.readBeforeWrite)
    2277                             rbwCount++;
    2278                         if (sinfo.ssaIdChange!=0)
    2279                             wrCount++;
    2280                         continue;
    2281                     }
    2282                    
    2283                     bool reducedSSAId = reduceSSAIds(curSSAIdMap, retSSAIdMap,
    2284                                 routineMap, ssaReplacesMap, entry, ssaEntry);
    2285                    
    2286                     size_t& ssaId = curSSAIdMap[ssaEntry.first];
    2287                    
    2288                     size_t& totalSSACount = totalSSACountMap[ssaEntry.first];
    2289                     if (totalSSACount == 0)
    2290                     {
    2291                         // first read before write at all, need change totalcount, ssaId
    2292                         ssaId++;
    2293                         totalSSACount++;
    2294                     }
    2295                    
    2296                     sinfo.ssaId = totalSSACount;
    2297                     sinfo.ssaIdFirst = sinfo.ssaIdChange!=0 ? totalSSACount : SIZE_MAX;
    2298                     sinfo.ssaIdBefore = ssaId-1;
    2299                    
    2300                     totalSSACount += sinfo.ssaIdChange;
    2301                     sinfo.ssaIdLast = sinfo.ssaIdChange!=0 ? totalSSACount-1 : SIZE_MAX;
    2302                     //totalSSACount = std::max(totalSSACount, ssaId);
    2303                     if (!reducedSSAId || sinfo.ssaIdChange!=0)
    2304                         ssaId = totalSSACount;
    2305                    
    2306                     // count read before writes (for cache weight)
    2307                     if (sinfo.readBeforeWrite)
    2308                         rbwCount++;
    2309                     if (sinfo.ssaIdChange!=0)
    2310                         wrCount++;
    2311                 }
    2312             }
    2313             else
    2314             {
    2315                 cblocksToCache.increase(entry.blockIndex);
    2316                 std::cout << "cblockToCache: " << entry.blockIndex << "=" <<
    2317                             cblocksToCache.count(entry.blockIndex) << std::endl;
    2318                 // back, already visited
    2319                 flowStackBlocks[entry.blockIndex] = !flowStackBlocks[entry.blockIndex];
    2320                 flowStack.pop_back();
    2321                
    2322                 BlockIndex curWayBIndex = flowStack.back().blockIndex;
    2323                 if (lastCommonCacheWayPoint.first != SIZE_MAX)
    2324                 {
    2325                     // mark point of way to cache (res first point)
    2326                     waysToCache[lastCommonCacheWayPoint.first] = true;
    2327                     std::cout << "mark to pfcache " <<
    2328                             lastCommonCacheWayPoint.first << ", " <<
    2329                             curWayBIndex << std::endl;
    2330                     prevWaysIndexMap[curWayBIndex] = lastCommonCacheWayPoint;
    2331                 }
    2332                 lastCommonCacheWayPoint = { curWayBIndex, flowStack.size()-1 };
    2333                 std::cout << "lastCcwP: " << curWayBIndex << std::endl;
    2334                 continue;
    2335             }
    2336         }
    2337        
    2338         if (!callStack.empty() &&
    2339             entry.blockIndex == callStack.back().callBlock &&
    2340             entry.nextIndex-1 == callStack.back().callNextIndex)
    2341         {
    2342             std::cout << " ret: " << entry.blockIndex << std::endl;
    2343             const BlockIndex routineBlock = callStack.back().routineBlock;
    2344             RoutineData& prevRdata = routineMap.find(routineBlock)->second;
    2345             if (!isRoutineGen[routineBlock])
    2346             {
    2347                 createRoutineData(codeBlocks, curSSAIdMap, loopBlocks, callBlocks,
    2348                             cblocksToCache, subroutinesCache, routineMap, prevRdata,
    2349                             routineBlock);
    2350                 //prevRdata.compare(myRoutineData);
    2351                 isRoutineGen[routineBlock] = true;
    2352                
    2353                 auto csimsmit = curSSAIdMapStateMap.find(routineBlock.index);
    2354                 if (csimsmit != curSSAIdMapStateMap.end() && entry.blockIndex.pass==0)
    2355                 {
    2356                     std::cout << " get curSSAIdMap from back recur 2" << std::endl;
    2357                     curSSAIdMap = csimsmit->second;
    2358                     curSSAIdMapStateMap.erase(csimsmit);
    2359                 }
    2360             }
    2361            
    2362             callStack.pop_back(); // just return from call
    2363             callBlocks.erase(routineBlock);
    2364         }
    2365        
    2366         if (entry.nextIndex < cblock.nexts.size())
    2367         {
    2368             bool isCall = false;
    2369             BlockIndex nextBlock = cblock.nexts[entry.nextIndex].block;
    2370             nextBlock.pass = entry.blockIndex.pass;
    2371             if (cblock.nexts[entry.nextIndex].isCall)
    2372             {
    2373                 if (!callBlocks.insert(nextBlock).second)
    2374                 {
    2375                     // if already called (then it is recursion)
    2376                     if (recurseBlocks.insert(nextBlock.index).second)
    2377                     {
    2378                         std::cout << "   -- recursion: " << nextBlock << std::endl;
    2379                         nextBlock.pass = 1;
    2380                        
    2381                         curSSAIdMapStateMap.insert({ nextBlock.index,  curSSAIdMap });
    2382                     }
    2383                     else if (entry.blockIndex.pass==1)
    2384                     {
    2385                         entry.nextIndex++;
    2386                         std::cout << " NO call (rec): " << entry.blockIndex << std::endl;
    2387                         continue;
    2388                     }
    2389                 }
    2390                 else if (entry.blockIndex.pass==1 &&
    2391                     recurseBlocks.find(nextBlock.index) != recurseBlocks.end())
    2392                 {
    2393                     entry.nextIndex++;
    2394                     std::cout << " NO call (rec)2: " << entry.blockIndex << std::endl;
    2395                     continue;
    2396                 }
    2397                
    2398                 std::cout << " call: " << entry.blockIndex << std::endl;
    2399                                
    2400                 callStack.push_back({ entry.blockIndex, entry.nextIndex, nextBlock });
    2401                 routineMap.insert({ nextBlock, { } });
    2402                 isCall = true;
    2403             }
    2404            
    2405             flowStack.push_back({ nextBlock, 0, isCall });
    2406             if (flowStackBlocks[nextBlock])
    2407             {
    2408                 if (!cblock.nexts[entry.nextIndex].isCall)
    2409                     loopBlocks.insert(nextBlock);
    2410                 flowStackBlocks[nextBlock] = false; // keep to inserted in popping
    2411             }
    2412             else
    2413                 flowStackBlocks[nextBlock] = true;
    2414             entry.nextIndex++;
    2415         }
    2416         else if (((entry.nextIndex==0 && cblock.nexts.empty()) ||
    2417                 // if have any call then go to next block
    2418                 (cblock.haveCalls && entry.nextIndex==cblock.nexts.size())) &&
    2419                  !cblock.haveReturn && !cblock.haveEnd)
    2420         {
    2421             if (entry.nextIndex!=0) // if back from calls (just return from calls)
    2422             {
    2423                 reduceSSAIdsForCalls(entry, codeBlocks, retSSAIdMap, routineMap,
    2424                                      ssaReplacesMap);
    2425                 //
    2426                 for (const NextBlock& next: cblock.nexts)
    2427                     if (next.isCall)
    2428                     {
    2429                         //std::cout << "joincall:"<< next.block << std::endl;
    2430                         size_t pass = 0;
    2431                         if (callBlocks.find(next.block) != callBlocks.end())
    2432                         {
    2433                             std::cout << " is secpass: " << entry.blockIndex << " : " <<
    2434                                     next.block << std::endl;
    2435                             pass = 1; // it ways second pass
    2436                         }
    2437                        
    2438                         auto it = routineMap.find({ next.block, pass }); // must find
    2439                         initializePrevRetSSAIds(curSSAIdMap, retSSAIdMap,
    2440                                     it->second, entry);
    2441                        
    2442                         BlockIndex rblock(next.block, entry.blockIndex.pass);
    2443                         if (callBlocks.find(next.block) != callBlocks.end())
    2444                             rblock.pass = 1;
    2445                        
    2446                         joinRetSSAIdMap(retSSAIdMap, it->second.lastSSAIdMap, rblock);
    2447                     }
    2448             }
    2449            
    2450             flowStack.push_back({ entry.blockIndex+1, 0, false });
    2451             if (flowStackBlocks[entry.blockIndex+1])
    2452             {
    2453                 loopBlocks.insert(entry.blockIndex+1);
    2454                  // keep to inserted in popping
    2455                 flowStackBlocks[entry.blockIndex+1] = false;
    2456             }
    2457             else
    2458                 flowStackBlocks[entry.blockIndex+1] = true;
    2459             entry.nextIndex++;
    2460         }
    2461         else // back
    2462         {
    2463             // revert retSSAIdMap
    2464             revertRetSSAIdMap(curSSAIdMap, retSSAIdMap, entry, nullptr);
    2465             //
    2466            
    2467             for (const auto& ssaEntry: cblock.ssaInfoMap)
    2468             {
    2469                 if (ssaEntry.first.regVar == nullptr)
    2470                     continue;
    2471                
    2472                 size_t& curSSAId = curSSAIdMap[ssaEntry.first];
    2473                 const size_t nextSSAId = curSSAId;
    2474                 curSSAId = ssaEntry.second.ssaIdBefore+1;
    2475                
    2476                 std::cout << "popcurnext: " << ssaEntry.first.regVar <<
    2477                             ":" << ssaEntry.first.index << ": " <<
    2478                             nextSSAId << ", " << curSSAId << std::endl;
    2479             }
    2480            
    2481             std::cout << "pop: " << entry.blockIndex << std::endl;
    2482             flowStackBlocks[entry.blockIndex] = false;
    2483            
    2484             if (!flowStack.empty() && flowStack.back().isCall)
    2485             {
    2486                 auto csimsmit = curSSAIdMapStateMap.find(entry.blockIndex.index);
    2487                 if (csimsmit != curSSAIdMapStateMap.end())
    2488                 {
    2489                     std::cout << " get curSSAIdMap from back recur" << std::endl;
    2490                     curSSAIdMap = csimsmit->second;
    2491                 }
    2492             }
    2493            
    2494             flowStack.pop_back();
    2495            
    2496             if (!flowStack.empty() && lastCommonCacheWayPoint.first != SIZE_MAX &&
    2497                     lastCommonCacheWayPoint.second >= flowStack.size())
    2498             {
    2499                 lastCommonCacheWayPoint =
    2500                         { flowStack.back().blockIndex, flowStack.size()-1 };
    2501                 std::cout << "POPlastCcwP: " << lastCommonCacheWayPoint.first << std::endl;
    2502             }
    2503         }
    2504     }
    2505    
    2506     /**********
    2507      * after that, we find points to resolve conflicts
    2508      **********/
    2509     flowStack.clear();
    2510     std::deque<FlowStackEntry2> flowStack2;
    2511    
    2512     std::fill(visited.begin(), visited.end(), false);
    2513     flowStack2.push_back({ 0, 0 });
    2514    
    2515     SimpleCache<BlockIndex, LastSSAIdMap> resFirstPointsCache(wrCount<<1);
    2516     SimpleCache<BlockIndex, RBWSSAIdMap> resSecondPointsCache(rbwCount<<1);
    2517    
    2518     while (!flowStack2.empty())
    2519     {
    2520         FlowStackEntry2& entry = flowStack2.back();
    2521         CodeBlock& cblock = codeBlocks[entry.blockIndex.index];
    2522        
    2523         if (entry.nextIndex == 0)
    2524         {
    2525             // process current block
    2526             if (!visited[entry.blockIndex])
    2527                 visited[entry.blockIndex] = true;
    2528             else
    2529             {
    2530                 resolveSSAConflicts(flowStack2, routineMap, codeBlocks,
    2531                             prevWaysIndexMap, waysToCache, cblocksToCache,
    2532                             resFirstPointsCache, resSecondPointsCache, ssaReplacesMap);
    2533                
    2534                 // back, already visited
    2535                 flowStack2.pop_back();
    2536                 continue;
    2537             }
    2538         }
    2539        
    2540         if (entry.nextIndex < cblock.nexts.size())
    2541         {
    2542             flowStack2.push_back({
    2543                 { cblock.nexts[entry.nextIndex].block, entry.blockIndex.pass }, 0 });
    2544             entry.nextIndex++;
    2545         }
    2546         else if (((entry.nextIndex==0 && cblock.nexts.empty()) ||
    2547                 // if have any call then go to next block
    2548                 (cblock.haveCalls && entry.nextIndex==cblock.nexts.size())) &&
    2549                  !cblock.haveReturn && !cblock.haveEnd)
    2550         {
    2551             flowStack2.push_back({ entry.blockIndex+1, 0 });
    2552             entry.nextIndex++;
    2553         }
    2554         else // back
    2555         {
    2556             if (cblocksToCache.count(entry.blockIndex)==2 &&
    2557                 !resSecondPointsCache.hasKey(entry.blockIndex))
    2558                 // add to cache
    2559                 addResSecCacheEntry(routineMap, codeBlocks, resSecondPointsCache,
    2560                             entry.blockIndex);
    2561             flowStack2.pop_back();
    2562         }
    2563     }
    2564 }
    2565449
    2566450void AsmRegAllocator::applySSAReplaces()
  • CLRadeonExtender/trunk/amdasm/CMakeLists.txt

    r3575 r3991  
    2929        AsmROCmFormat.cpp
    3030        AsmRegAlloc.cpp
     31        AsmRegAllocSSAData.cpp
    3132        AsmSource.cpp
    3233        Assembler.cpp
Note: See TracChangeset for help on using the changeset viewer.