Changeset 4134 in CLRX


Ignore:
Timestamp:
May 10, 2018, 2:48:23 PM (2 months ago)
Author:
matszpk
Message:

CLRadeonExtender: AsmRegAlloc?: Move createLiveness to separate source code (AsmRegAllocLive?.cpp).

Location:
CLRadeonExtender/trunk
Files:
1 added
3 edited

Legend:

Unmodified
Added
Removed
  • CLRadeonExtender/trunk/amdasm/AsmRegAlloc.cpp

    r4131 r4134  
    684684}
    685685
    686 /*********
    687  * createLivenesses stuff
    688  *********/
    689 
    690 static cxuint getRegType(size_t regTypesNum, const cxuint* regRanges,
    691             const AsmSingleVReg& svreg)
    692 {
    693     cxuint regType; // regtype
    694     if (svreg.regVar!=nullptr)
    695         regType = svreg.regVar->type;
    696     else
    697         for (regType = 0; regType < regTypesNum; regType++)
    698             if (svreg.index >= regRanges[regType<<1] &&
    699                 svreg.index < regRanges[(regType<<1)+1])
    700                 break;
    701     return regType;
    702 }
    703 
    704 static void getVIdx(const AsmSingleVReg& svreg, size_t ssaIdIdx,
    705         const AsmRegAllocator::SSAInfo& ssaInfo,
    706         const VarIndexMap* vregIndexMaps, size_t regTypesNum, const cxuint* regRanges,
    707         cxuint& regType, size_t& vidx)
    708 {
    709     size_t ssaId;
    710     if (svreg.regVar==nullptr)
    711         ssaId = 0;
    712     else if (ssaIdIdx==0)
    713         ssaId = ssaInfo.ssaIdBefore;
    714     else if (ssaIdIdx==1)
    715         ssaId = ssaInfo.ssaIdFirst;
    716     else if (ssaIdIdx<ssaInfo.ssaIdChange)
    717         ssaId = ssaInfo.ssaId + ssaIdIdx-1;
    718     else // last
    719         ssaId = ssaInfo.ssaIdLast;
    720    
    721     regType = getRegType(regTypesNum, regRanges, svreg); // regtype
    722     const VarIndexMap& vregIndexMap = vregIndexMaps[regType];
    723     const std::vector<size_t>& vidxes = vregIndexMap.find(svreg)->second;
    724     /*ARDOut << "lvn[" << regType << "][" << vidxes[ssaId] << "]. ssaIdIdx: " <<
    725             ssaIdIdx << ". ssaId: " << ssaId << ". svreg: " << svreg.regVar << ":" <<
    726             svreg.index << "\n";*/
    727     //return livenesses[regType][ssaIdIndices[ssaId]];
    728     vidx = vidxes[ssaId];
    729 }
    730 
    731 static inline Liveness& getLiveness(const AsmSingleVReg& svreg, size_t ssaIdIdx,
    732         const AsmRegAllocator::SSAInfo& ssaInfo, std::vector<Liveness>* livenesses,
    733         const VarIndexMap* vregIndexMaps, size_t regTypesNum, const cxuint* regRanges)
    734 {
    735     cxuint regType;
    736     size_t vidx;
    737     getVIdx(svreg, ssaIdIdx, ssaInfo, vregIndexMaps, regTypesNum, regRanges,
    738             regType, vidx);
    739     return livenesses[regType][vidx];
    740 }
    741 
    742 static void getVIdx2(const AsmSingleVReg& svreg, size_t ssaId,
    743         const VarIndexMap* vregIndexMaps, size_t regTypesNum, const cxuint* regRanges,
    744         cxuint& regType, size_t& vidx)
    745 {
    746     regType = getRegType(regTypesNum, regRanges, svreg); // regtype
    747     const VarIndexMap& vregIndexMap = vregIndexMaps[regType];
    748     const std::vector<size_t>& vidxes = vregIndexMap.find(svreg)->second;
    749     /*ARDOut << "lvn[" << regType << "][" << vidxes[ssaId] << "]. ssaId: " <<
    750             ssaId << ". svreg: " << svreg.regVar << ":" << svreg.index << "\n";*/
    751     vidx = vidxes[ssaId];
    752 }
    753 
    754 
    755 static void addVIdxToCallEntry(size_t blockIndex, cxuint regType, size_t vidx,
    756             const std::vector<CodeBlock>& codeBlocks,
    757             std::unordered_map<size_t, VIdxSetEntry>& vidxCallMap,
    758             const std::unordered_map<size_t, VIdxSetEntry>& vidxRoutineMap)
    759 {
    760     const CodeBlock& cblock = codeBlocks[blockIndex];
    761     if (cblock.haveCalls)
    762     {
    763         VIdxSetEntry& varCallEntry = vidxCallMap[blockIndex];
    764         for (const NextBlock& next: cblock.nexts)
    765             if (next.isCall)
    766             {
    767                 const auto& allLvs = vidxRoutineMap.find(next.block)->second;
    768                 if (allLvs.vs[regType].find(vidx) == allLvs.vs[regType].end())
    769                     // add callLiveTime only if vreg not present in routine
    770                     varCallEntry.vs[regType].insert(vidx);
    771             }
    772     }
    773 }
    774 
    775 static void fillUpInsideRoutine(std::unordered_set<size_t>& visited,
    776             const std::vector<CodeBlock>& codeBlocks,
    777             std::unordered_map<size_t, VIdxSetEntry>& vidxCallMap,
    778             const std::unordered_map<size_t, VIdxSetEntry>& vidxRoutineMap,
    779             size_t startBlock, const AsmSingleVReg& svreg, Liveness& lv,
    780             cxuint lvRType /* lv register type */, size_t vidx)
    781 {
    782     std::deque<FlowStackEntry3> flowStack;
    783     flowStack.push_back({ startBlock, 0 });
    784    
    785     //if (lv.contain(codeBlocks[startBlock].end-1))
    786         // already filled, then do nothing
    787         //return;
    788    
    789     while (!flowStack.empty())
    790     {
    791         FlowStackEntry3& entry = flowStack.back();
    792         const CodeBlock& cblock = codeBlocks[entry.blockIndex];
    793        
    794         if (entry.nextIndex == 0)
    795         {
    796             if (visited.insert(entry.blockIndex).second)
    797             {
    798                 size_t cbStart = cblock.start;
    799                 if (flowStack.size() == 1)
    800                 {
    801                     // if first block, then get last occurrence in this path
    802                     auto sinfoIt = cblock.ssaInfoMap.find(svreg);
    803                     if (sinfoIt != cblock.ssaInfoMap.end())
    804                         cbStart = sinfoIt->second.lastPos+1;
    805                 }
    806                 // just insert
    807                 lv.insert(cbStart, cblock.end);
    808                
    809                 addVIdxToCallEntry(entry.blockIndex, lvRType, vidx,
    810                         codeBlocks, vidxCallMap, vidxRoutineMap);
    811             }
    812             else
    813             {
    814                 flowStack.pop_back();
    815                 continue;
    816             }
    817         }
    818        
    819         // skip calls
    820         for (; entry.nextIndex < cblock.nexts.size() &&
    821                     cblock.nexts[entry.nextIndex].isCall; entry.nextIndex++);
    822        
    823         if (entry.nextIndex < cblock.nexts.size())
    824         {
    825             flowStack.push_back({ cblock.nexts[entry.nextIndex].block, 0 });
    826             entry.nextIndex++;
    827         }
    828         else if (((entry.nextIndex==0 && cblock.nexts.empty()) ||
    829                 // if have any call then go to next block
    830                 (cblock.haveCalls && entry.nextIndex==cblock.nexts.size())) &&
    831                  !cblock.haveReturn && !cblock.haveEnd)
    832         {
    833             flowStack.push_back({ entry.blockIndex+1, 0 });
    834             entry.nextIndex++;
    835         }
    836         else // back
    837             flowStack.pop_back();
    838     }
    839 }
    840 
    841 static void joinVRegRecur(const std::deque<FlowStackEntry3>& flowStack,
    842             const std::vector<CodeBlock>& codeBlocks, const RoutineLvMap& routineMap,
    843             std::unordered_map<size_t, VIdxSetEntry>& vidxCallMap,
    844             const std::unordered_map<size_t, VIdxSetEntry>& vidxRoutineMap,
    845             LastVRegStackPos flowStkStart, const AsmSingleVReg& svreg, size_t ssaId,
    846             const VarIndexMap* vregIndexMaps, std::vector<Liveness>* livenesses,
    847             size_t regTypesNum, const cxuint* regRanges, bool skipLastBlock = false)
    848 {
    849     struct JoinEntry
    850     {
    851         size_t blockIndex; // block index where is call
    852         size_t nextIndex; // next index of routine call
    853         size_t lastAccessIndex; // last access pos index
    854         bool inSubroutines;
    855     };
    856    
    857     FlowStackCIter flitEnd = flowStack.end();
    858     if (skipLastBlock)
    859         --flitEnd; // before last element
    860     cxuint lvRegType;
    861     size_t vidx;
    862     getVIdx2(svreg, ssaId, vregIndexMaps, regTypesNum, regRanges, lvRegType, vidx);
    863     Liveness& lv = livenesses[lvRegType][vidx];
    864    
    865     std::unordered_set<size_t> visited;
    866    
    867     std::stack<JoinEntry> rjStack; // routine join stack
    868     if (flowStkStart.inSubroutines)
    869         rjStack.push({ flowStack[flowStkStart.stackPos].blockIndex, 0, 0, true });
    870    
    871     while (!rjStack.empty())
    872     {
    873         JoinEntry& entry = rjStack.top();
    874         const CodeBlock& cblock = codeBlocks[entry.blockIndex];
    875        
    876         if (entry.inSubroutines && entry.nextIndex < cblock.nexts.size())
    877         {
    878             bool doNextIndex = false; // true if to next call
    879             if (cblock.nexts[entry.nextIndex].isCall)
    880             {
    881                 const RoutineDataLv& rdata =
    882                         routineMap.find(cblock.nexts[entry.nextIndex].block)->second;
    883                 auto lastAccessIt = rdata.lastAccessMap.find(svreg);
    884                 if (lastAccessIt != rdata.lastAccessMap.end())
    885                 {
    886                     if (entry.lastAccessIndex < lastAccessIt->second.size())
    887                     {
    888                         const auto& lastAccess =
    889                                 lastAccessIt->second[entry.lastAccessIndex];
    890                         rjStack.push({ lastAccess.blockIndex, 0,
    891                                     0, lastAccess.inSubroutines });
    892                         entry.lastAccessIndex++;
    893                         if (entry.lastAccessIndex == lastAccessIt->second.size())
    894                             doNextIndex = true;
    895                     }
    896                     else
    897                         doNextIndex = true;
    898                 }
    899                 else
    900                     doNextIndex = true;
    901             }
    902             else
    903                 doNextIndex = true;
    904            
    905             if (doNextIndex)
    906             {
    907                 // to next call
    908                 entry.nextIndex++;
    909                 entry.lastAccessIndex = 0;
    910             }
    911         }
    912         else
    913         {
    914             // fill up next block in path (do not fill start block)
    915             /* if inSubroutines, then first block
    916              * (that with subroutines calls) will be skipped */
    917             if (rjStack.size() > 1)
    918                 fillUpInsideRoutine(visited, codeBlocks, vidxCallMap, vidxRoutineMap,
    919                         entry.blockIndex + (entry.inSubroutines), svreg,
    920                         lv, lvRegType, vidx);
    921             rjStack.pop();
    922         }
    923     }
    924    
    925     /*if (flitEnd != flowStack.begin())
    926     {
    927         const CodeBlock& cbLast = codeBlocks[(flitEnd-1)->blockIndex];
    928         if (lv.contain(cbLast.end-1))
    929             // if already filled up
    930             return;
    931     }*/
    932    
    933     auto flit = flowStack.begin() + flowStkStart.stackPos + (flowStkStart.inSubroutines);
    934     const CodeBlock& lastBlk = codeBlocks[flit->blockIndex];
    935    
    936     if (flit != flitEnd)
    937     {
    938         auto sinfoIt = lastBlk.ssaInfoMap.find(svreg);
    939         size_t lastPos = lastBlk.start;
    940         if (sinfoIt != lastBlk.ssaInfoMap.end())
    941         {
    942             if (flit->nextIndex > lastBlk.nexts.size())
    943                 // only if pass this routine
    944                 addVIdxToCallEntry(flit->blockIndex, lvRegType, vidx,
    945                         codeBlocks, vidxCallMap, vidxRoutineMap);
    946             // if begin at some point at last block
    947             lastPos = sinfoIt->second.lastPos;
    948             lv.insert(lastPos + 1, lastBlk.end);
    949             ++flit; // skip last block in stack
    950         }
    951     }
    952     // fill up to this
    953     for (; flit != flitEnd; ++flit)
    954     {
    955         const CodeBlock& cblock = codeBlocks[flit->blockIndex];
    956         if (flit->nextIndex > cblock.nexts.size())
    957             // only if pass this routine
    958             addVIdxToCallEntry(flit->blockIndex, lvRegType, vidx, codeBlocks,
    959                         vidxCallMap, vidxRoutineMap);
    960         lv.insert(cblock.start, cblock.end);
    961     }
    962 }
    963 
    964 /* handle many start points in this code (for example many kernel's in same code)
    965  * replace sets by vector, and sort and remove same values on demand
    966  */
    967 
    968 /* join livenesses between consecutive code blocks */
    969 static void putCrossBlockLivenesses(const std::deque<FlowStackEntry3>& flowStack,
    970         const std::vector<CodeBlock>& codeBlocks, const RoutineLvMap& routineMap,
    971         std::unordered_map<size_t, VIdxSetEntry>& vidxCallMap,
    972         const std::unordered_map<size_t, VIdxSetEntry>& vidxRoutineMap,
    973         const LastVRegMap& lastVRegMap, std::vector<Liveness>* livenesses,
    974         const VarIndexMap* vregIndexMaps, size_t regTypesNum, const cxuint* regRanges)
    975 {
    976     ARDOut << "putCrossBlockLv block: " << flowStack.back().blockIndex << "\n";
    977     const CodeBlock& cblock = codeBlocks[flowStack.back().blockIndex];
    978     for (const auto& entry: cblock.ssaInfoMap)
    979         if (entry.second.readBeforeWrite)
    980         {
    981             // find last
    982             auto lvrit = lastVRegMap.find(entry.first);
    983             LastVRegStackPos flowStackStart = (lvrit != lastVRegMap.end()) ?
    984                 lvrit->second.back() : LastVRegStackPos{ 0, false };
    985            
    986             joinVRegRecur(flowStack, codeBlocks, routineMap, vidxCallMap, vidxRoutineMap,
    987                     flowStackStart, entry.first, entry.second.ssaIdBefore,
    988                     vregIndexMaps, livenesses, regTypesNum, regRanges, true);
    989         }
    990 }
    991 
    992 // add new join second cache entry with readBeforeWrite for all encountered regvars
    993 static void addJoinSecCacheEntry(const RoutineLvMap& routineMap,
    994                 const std::vector<CodeBlock>& codeBlocks,
    995                 SimpleCache<size_t, SVRegMap>& joinSecondPointsCache,
    996                 size_t nextBlock)
    997 {
    998     ARDOut << "addJoinSecCacheEntry: " << nextBlock << "\n";
    999     //std::stack<CallStackEntry> callStack = prevCallStack;
    1000     // traverse by graph from next block
    1001     std::deque<FlowStackEntry3> flowStack;
    1002     flowStack.push_back({ nextBlock, 0 });
    1003     std::unordered_set<size_t> visited;
    1004    
    1005     SVRegBlockMap alreadyReadMap;
    1006     SVRegMap cacheSecPoints;
    1007    
    1008     while (!flowStack.empty())
    1009     {
    1010         FlowStackEntry3& entry = flowStack.back();
    1011         const CodeBlock& cblock = codeBlocks[entry.blockIndex];
    1012        
    1013         if (entry.nextIndex == 0)
    1014         {
    1015             // process current block
    1016             if (visited.insert(entry.blockIndex).second)
    1017             {
    1018                 ARDOut << "  resolv (cache): " << entry.blockIndex << "\n";
    1019                
    1020                 const SVRegMap* resSecondPoints =
    1021                             joinSecondPointsCache.use(entry.blockIndex);
    1022                 if (resSecondPoints == nullptr)
    1023                 {
    1024                     // if joinSecondPointCache not found
    1025                     for (auto& sentry: cblock.ssaInfoMap)
    1026                     {
    1027                         const SSAInfo& sinfo = sentry.second;
    1028                         auto res = alreadyReadMap.insert(
    1029                                     { sentry.first, entry.blockIndex });
    1030                        
    1031                         if (res.second && sinfo.readBeforeWrite)
    1032                             cacheSecPoints[sentry.first] = sinfo.ssaIdBefore;
    1033                     }
    1034                 }
    1035                 else // to use cache
    1036                 {
    1037                     // add to current cache sec points
    1038                     for (const auto& rsentry: *resSecondPoints)
    1039                     {
    1040                         const bool alreadyRead =
    1041                             alreadyReadMap.find(rsentry.first) != alreadyReadMap.end();
    1042                         if (!alreadyRead)
    1043                             cacheSecPoints[rsentry.first] = rsentry.second;
    1044                     }
    1045                     flowStack.pop_back();
    1046                     continue;
    1047                 }
    1048             }
    1049             else
    1050             {
    1051                 // back, already visited
    1052                 ARDOut << "join already (cache): " << entry.blockIndex << "\n";
    1053                 flowStack.pop_back();
    1054                 continue;
    1055             }
    1056         }
    1057        
    1058         if (entry.nextIndex < cblock.nexts.size())
    1059         {
    1060             flowStack.push_back({ cblock.nexts[entry.nextIndex].block, 0 });
    1061             entry.nextIndex++;
    1062         }
    1063         else if (((entry.nextIndex==0 && cblock.nexts.empty()) ||
    1064                 // if have any call then go to next block
    1065                 (cblock.haveCalls && entry.nextIndex==cblock.nexts.size())) &&
    1066                  !cblock.haveReturn && !cblock.haveEnd)
    1067         {
    1068             // add toResolveMap ssaIds inside called routines
    1069             for (const auto& next: cblock.nexts)
    1070                 if (next.isCall)
    1071                 {
    1072                     const RoutineDataLv& rdata = routineMap.find(next.block)->second;
    1073                     for (const auto& v: rdata.rbwSSAIdMap)
    1074                         alreadyReadMap.insert({v.first, entry.blockIndex });
    1075                     for (const auto& v: rdata.lastAccessMap)
    1076                         alreadyReadMap.insert({v.first, entry.blockIndex });
    1077                 }
    1078            
    1079             flowStack.push_back({ entry.blockIndex+1, 0 });
    1080             entry.nextIndex++;
    1081         }
    1082         else // back
    1083         {
    1084             // remove old to resolve in leaved way to allow collecting next ssaId
    1085             // before write (can be different due to earlier visit)
    1086             for (const auto& next: cblock.nexts)
    1087                 if (next.isCall)
    1088                 {
    1089                     const RoutineDataLv& rdata = routineMap.find(next.block)->second;
    1090                     for (const auto& v: rdata.rbwSSAIdMap)
    1091                     {
    1092                         auto it = alreadyReadMap.find(v.first);
    1093                         if (it != alreadyReadMap.end() && it->second == entry.blockIndex)
    1094                             alreadyReadMap.erase(it);
    1095                     }
    1096                     for (const auto& v: rdata.lastAccessMap)
    1097                     {
    1098                         auto it = alreadyReadMap.find(v.first);
    1099                         if (it != alreadyReadMap.end() && it->second == entry.blockIndex)
    1100                             alreadyReadMap.erase(it);
    1101                     }
    1102                 }
    1103            
    1104             for (const auto& sentry: cblock.ssaInfoMap)
    1105             {
    1106                 auto it = alreadyReadMap.find(sentry.first);
    1107                 if (it != alreadyReadMap.end() && it->second == entry.blockIndex)
    1108                     // remove old to resolve in leaved way to allow collecting next ssaId
    1109                     // before write (can be different due to earlier visit)
    1110                     alreadyReadMap.erase(it);
    1111             }
    1112             ARDOut << "  popjoin (cache)\n";
    1113             flowStack.pop_back();
    1114         }
    1115     }
    1116    
    1117     joinSecondPointsCache.put(nextBlock, cacheSecPoints);
    1118 }
    1119 
    1120 // apply calls (changes from these calls) from code blocks to stack var map
    1121 static void applyCallToStackVarMap(const CodeBlock& cblock, const RoutineLvMap& routineMap,
    1122         LastStackPosMap& stackVarMap, size_t pfPos, size_t nextIndex)
    1123 {
    1124     for (const NextBlock& next: cblock.nexts)
    1125         if (next.isCall)
    1126         {
    1127             ARDOut << "  japplycall: " << pfPos << ": " <<
    1128                     nextIndex << ": " << next.block << "\n";
    1129             const LastAccessMap& regVarMap =
    1130                     routineMap.find(next.block)->second.lastAccessMap;
    1131             for (const auto& sentry: regVarMap)
    1132             {
    1133                 // MSVC error fix
    1134                 auto& v = stackVarMap[sentry.first];
    1135                 v = LastVRegStackPos{ pfPos, true };
    1136             }
    1137         }
    1138 }
    1139 
    1140 static void joinRegVarLivenesses(const std::deque<FlowStackEntry3>& prevFlowStack,
    1141         const std::vector<CodeBlock>& codeBlocks, const RoutineLvMap& routineMap,
    1142         std::unordered_map<size_t, VIdxSetEntry>& vidxCallMap,
    1143         const std::unordered_map<size_t, VIdxSetEntry>& vidxRoutineMap,
    1144         const PrevWaysIndexMap& prevWaysIndexMap,
    1145         const std::vector<bool>& waysToCache, ResSecondPointsToCache& cblocksToCache,
    1146         SimpleCache<size_t, LastStackPosMap>& joinFirstPointsCache,
    1147         SimpleCache<size_t, SVRegMap>& joinSecondPointsCache,
    1148         const VarIndexMap* vregIndexMaps,
    1149         std::vector<Liveness>* livenesses, size_t regTypesNum, const cxuint* regRanges)
    1150 {
    1151     size_t nextBlock = prevFlowStack.back().blockIndex;
    1152     auto pfEnd = prevFlowStack.end();
    1153     --pfEnd;
    1154     ARDOut << "startJoinLv: " << (pfEnd-1)->blockIndex << "," << nextBlock << "\n";
    1155     // key - varreg, value - last position in previous flowStack
    1156     LastStackPosMap stackVarMap;
    1157    
    1158     size_t pfStartIndex = 0;
    1159     {
    1160         auto pfPrev = pfEnd;
    1161         --pfPrev;
    1162         auto it = prevWaysIndexMap.find(pfPrev->blockIndex);
    1163         if (it != prevWaysIndexMap.end())
    1164         {
    1165             const LastStackPosMap* cached = joinFirstPointsCache.use(it->second.first);
    1166             if (cached!=nullptr)
    1167             {
    1168                 ARDOut << "use pfcached: " << it->second.first << ", " <<
    1169                         it->second.second << "\n";
    1170                 stackVarMap = *cached;
    1171                 pfStartIndex = it->second.second+1;
    1172                
    1173                 // apply missing calls at end of the cached
    1174                 const CodeBlock& cblock = codeBlocks[it->second.first];
    1175                
    1176                 const FlowStackEntry3& entry = *(prevFlowStack.begin()+pfStartIndex-1);
    1177                 if (entry.nextIndex > cblock.nexts.size())
    1178                     applyCallToStackVarMap(cblock, routineMap, stackVarMap,
    1179                                     pfStartIndex-1, -1);
    1180             }
    1181         }
    1182     }
    1183    
    1184     for (auto pfit = prevFlowStack.begin()+pfStartIndex; pfit != pfEnd; ++pfit)
    1185     {
    1186         const FlowStackEntry3& entry = *pfit;
    1187         const CodeBlock& cblock = codeBlocks[entry.blockIndex];
    1188         for (const auto& sentry: cblock.ssaInfoMap)
    1189         {
    1190             // MSVC error fix
    1191             auto& v = stackVarMap[sentry.first];
    1192             v = { size_t(pfit - prevFlowStack.begin()), false };
    1193         }
    1194        
    1195         if (entry.nextIndex > cblock.nexts.size())
    1196             applyCallToStackVarMap(cblock, routineMap, stackVarMap,
    1197                         pfit - prevFlowStack.begin(), entry.nextIndex);
    1198        
    1199         // put to first point cache
    1200         if (waysToCache[pfit->blockIndex] &&
    1201             !joinFirstPointsCache.hasKey(pfit->blockIndex))
    1202         {
    1203             ARDOut << "put pfcache " << pfit->blockIndex << "\n";
    1204             joinFirstPointsCache.put(pfit->blockIndex, stackVarMap);
    1205         }
    1206     }
    1207    
    1208     SVRegMap cacheSecPoints;
    1209     const bool toCache = (!joinSecondPointsCache.hasKey(nextBlock)) &&
    1210                 cblocksToCache.count(nextBlock)>=2;
    1211    
    1212     // traverse by graph from next block
    1213     std::deque<FlowStackEntry3> flowStack;
    1214     flowStack.push_back({ nextBlock, 0 });
    1215     std::vector<bool> visited(codeBlocks.size(), false);
    1216    
    1217     // already read in current path
    1218     // key - vreg, value - source block where vreg of conflict found
    1219     SVRegMap alreadyReadMap;
    1220    
    1221     while (!flowStack.empty())
    1222     {
    1223         FlowStackEntry3& entry = flowStack.back();
    1224         const CodeBlock& cblock = codeBlocks[entry.blockIndex];
    1225        
    1226         if (entry.nextIndex == 0)
    1227         {
    1228             // process current block
    1229             if (!visited[entry.blockIndex])
    1230             {
    1231                 visited[entry.blockIndex] = true;
    1232                 ARDOut << "  lvjoin: " << entry.blockIndex << "\n";
    1233                
    1234                 const SVRegMap* joinSecondPoints =
    1235                         joinSecondPointsCache.use(entry.blockIndex);
    1236                
    1237                 if (joinSecondPoints == nullptr)
    1238                     for (const auto& sentry: cblock.ssaInfoMap)
    1239                     {
    1240                         const SSAInfo& sinfo = sentry.second;
    1241                         auto res = alreadyReadMap.insert(
    1242                                     { sentry.first, entry.blockIndex });
    1243                        
    1244                         if (toCache)
    1245                             cacheSecPoints[sentry.first] = sinfo.ssaIdBefore;
    1246                        
    1247                         if (res.second && sinfo.readBeforeWrite)
    1248                         {
    1249                             auto it = stackVarMap.find(sentry.first);
    1250                             LastVRegStackPos stackPos = (it != stackVarMap.end() ?
    1251                                         it->second : LastVRegStackPos{ 0, false });
    1252                            
    1253                             joinVRegRecur(prevFlowStack, codeBlocks, routineMap,
    1254                                 vidxCallMap, vidxRoutineMap,
    1255                                 stackPos, sentry.first, sentry.second.ssaIdBefore,
    1256                                 vregIndexMaps, livenesses, regTypesNum, regRanges, true);
    1257                         }
    1258                     }
    1259                 else
    1260                 {
    1261                     ARDOut << "use join secPointCache: " << entry.blockIndex << "\n";
    1262                     // add to current cache sec points
    1263                     for (const auto& rsentry: *joinSecondPoints)
    1264                     {
    1265                         const bool alreadyRead =
    1266                             alreadyReadMap.find(rsentry.first) != alreadyReadMap.end();
    1267                        
    1268                         if (!alreadyRead)
    1269                         {
    1270                             if (toCache)
    1271                                 cacheSecPoints[rsentry.first] = rsentry.second;
    1272                            
    1273                             auto it = stackVarMap.find(rsentry.first);
    1274                             LastVRegStackPos stackPos = (it != stackVarMap.end() ?
    1275                                         it->second : LastVRegStackPos{ 0, false });
    1276                            
    1277                             joinVRegRecur(prevFlowStack, codeBlocks, routineMap,
    1278                                 vidxCallMap, vidxRoutineMap,
    1279                                 stackPos, rsentry.first, rsentry.second, vregIndexMaps,
    1280                                 livenesses, regTypesNum, regRanges, true);
    1281                         }
    1282                     }
    1283                     flowStack.pop_back();
    1284                     continue;
    1285                 }
    1286             }
    1287             else
    1288             {
    1289                 cblocksToCache.increase(entry.blockIndex);
    1290                 ARDOut << "jcblockToCache: " << entry.blockIndex << "=" <<
    1291                             cblocksToCache.count(entry.blockIndex) << "\n";
    1292                 // back, already visited
    1293                 ARDOut << "join already: " << entry.blockIndex << "\n";
    1294                 flowStack.pop_back();
    1295                 continue;
    1296             }
    1297         }
    1298        
    1299         if (entry.nextIndex < cblock.nexts.size())
    1300         {
    1301             flowStack.push_back({ cblock.nexts[entry.nextIndex].block, 0 });
    1302             entry.nextIndex++;
    1303         }
    1304         else if (((entry.nextIndex==0 && cblock.nexts.empty()) ||
    1305                 // if have any call then go to next block
    1306                 (cblock.haveCalls && entry.nextIndex==cblock.nexts.size())) &&
    1307                  !cblock.haveReturn && !cblock.haveEnd)
    1308         {
    1309             // add toResolveMap ssaIds inside called routines
    1310             for (const auto& next: cblock.nexts)
    1311                 if (next.isCall)
    1312                 {
    1313                     const RoutineDataLv& rdata = routineMap.find(next.block)->second;
    1314                     for (const auto& v: rdata.rbwSSAIdMap)
    1315                         alreadyReadMap.insert({v.first, entry.blockIndex });
    1316                     for (const auto& v: rdata.lastAccessMap)
    1317                         alreadyReadMap.insert({v.first, entry.blockIndex });
    1318                 }
    1319            
    1320             flowStack.push_back({ entry.blockIndex+1, 0 });
    1321             entry.nextIndex++;
    1322         }
    1323         else // back
    1324         {
    1325             // remove old to resolve in leaved way to allow collecting next ssaId
    1326             // before write (can be different due to earlier visit)
    1327             for (const auto& next: cblock.nexts)
    1328                 if (next.isCall)
    1329                 {
    1330                     const RoutineDataLv& rdata = routineMap.find(next.block)->second;
    1331                     for (const auto& v: rdata.rbwSSAIdMap)
    1332                     {
    1333                         auto it = alreadyReadMap.find(v.first);
    1334                         if (it != alreadyReadMap.end() && it->second == entry.blockIndex)
    1335                             alreadyReadMap.erase(it);
    1336                     }
    1337                     for (const auto& v: rdata.lastAccessMap)
    1338                     {
    1339                         auto it = alreadyReadMap.find(v.first);
    1340                         if (it != alreadyReadMap.end() && it->second == entry.blockIndex)
    1341                             alreadyReadMap.erase(it);
    1342                     }
    1343                 }
    1344            
    1345             for (const auto& sentry: cblock.ssaInfoMap)
    1346             {
    1347                 auto it = alreadyReadMap.find(sentry.first);
    1348                 if (it != alreadyReadMap.end() && it->second == entry.blockIndex)
    1349                     // remove old to resolve in leaved way to allow collecting next ssaId
    1350                     // before write (can be different due to earlier visit)
    1351                     alreadyReadMap.erase(it);
    1352             }
    1353             ARDOut << "  popjoin\n";
    1354            
    1355             if (cblocksToCache.count(entry.blockIndex)==2 &&
    1356                 !joinSecondPointsCache.hasKey(entry.blockIndex))
    1357                 // add to cache
    1358                 addJoinSecCacheEntry(routineMap, codeBlocks, joinSecondPointsCache,
    1359                             entry.blockIndex);
    1360            
    1361             flowStack.pop_back();
    1362         }
    1363     }
    1364    
    1365     if (toCache)
    1366         joinSecondPointsCache.put(nextBlock, cacheSecPoints);
    1367 }
    1368 
    1369 static void addUsageDeps(const cxbyte* ldeps, cxuint rvusNum,
    1370             const AsmRegVarUsage* rvus, LinearDepMap* ldepsOut,
    1371             const VarIndexMap* vregIndexMaps, const SVRegMap& ssaIdIdxMap,
    1372             size_t regTypesNum, const cxuint* regRanges)
    1373 {
    1374     // add linear deps
    1375     cxuint count = ldeps[0];
    1376     cxuint pos = 1;
    1377     cxbyte rvuAdded = 0;
    1378     for (cxuint i = 0; i < count; i++)
    1379     {
    1380         cxuint ccount = ldeps[pos++];
    1381         std::vector<size_t> vidxes;
    1382         cxuint regType = UINT_MAX;
    1383         cxbyte align = rvus[ldeps[pos]].align;
    1384         for (cxuint j = 0; j < ccount; j++)
    1385         {
    1386             rvuAdded |= 1U<<ldeps[pos];
    1387             const AsmRegVarUsage& rvu = rvus[ldeps[pos++]];
    1388             if (rvu.regVar == nullptr)
    1389                 continue;
    1390             for (uint16_t k = rvu.rstart; k < rvu.rend; k++)
    1391             {
    1392                 AsmSingleVReg svreg = {rvu.regVar, k};
    1393                 auto sit = ssaIdIdxMap.find(svreg);
    1394                 if (regType==UINT_MAX)
    1395                     regType = getRegType(regTypesNum, regRanges, svreg);
    1396                 const VarIndexMap& vregIndexMap = vregIndexMaps[regType];
    1397                 const std::vector<size_t>& ssaIdIndices =
    1398                             vregIndexMap.find(svreg)->second;
    1399                 // push variable index
    1400                 vidxes.push_back(ssaIdIndices[sit->second]);
    1401             }
    1402         }
    1403         ldepsOut[regType][vidxes[0]].align = align;
    1404         for (size_t k = 1; k < vidxes.size(); k++)
    1405         {
    1406             ldepsOut[regType][vidxes[k-1]].nextVidxes.insertValue(vidxes[k]);
    1407             ldepsOut[regType][vidxes[k]].prevVidxes.insertValue(vidxes[k-1]);
    1408         }
    1409     }
    1410     // add single arg linear dependencies
    1411     for (cxuint i = 0; i < rvusNum; i++)
    1412         if ((rvuAdded & (1U<<i)) == 0 && rvus[i].rstart+1<rvus[i].rend)
    1413         {
    1414             const AsmRegVarUsage& rvu = rvus[i];
    1415             if (rvu.regVar == nullptr)
    1416                 continue;
    1417             std::vector<size_t> vidxes;
    1418             cxuint regType = UINT_MAX;
    1419             cxbyte align = rvus[i].align;
    1420             for (uint16_t k = rvu.rstart; k < rvu.rend; k++)
    1421             {
    1422                 AsmSingleVReg svreg = {rvu.regVar, k};
    1423                 auto sit = ssaIdIdxMap.find(svreg);
    1424                 assert(sit != ssaIdIdxMap.end());
    1425                 if (regType==UINT_MAX)
    1426                     regType = getRegType(regTypesNum, regRanges, svreg);
    1427                 const VarIndexMap& vregIndexMap = vregIndexMaps[regType];
    1428                 const std::vector<size_t>& ssaIdIndices =
    1429                             vregIndexMap.find(svreg)->second;
    1430                 // push variable index
    1431                 vidxes.push_back(ssaIdIndices[sit->second]);
    1432             }
    1433             ldepsOut[regType][vidxes[0]].align = align;
    1434             for (size_t j = 1; j < vidxes.size(); j++)
    1435             {
    1436                 ldepsOut[regType][vidxes[j-1]].nextVidxes.insertValue(vidxes[j]);
    1437                 ldepsOut[regType][vidxes[j]].prevVidxes.insertValue(vidxes[j-1]);
    1438             }
    1439         }
    1440 }
    1441 
    1442 static void joinRoutineDataLv(RoutineDataLv& dest, VIdxSetEntry& destVars,
    1443             RoutineCurAccessMap& curSVRegMap, FlowStackEntry4& entry,
    1444             const RoutineDataLv& src, const VIdxSetEntry& srcVars)
    1445 {
    1446     dest.rbwSSAIdMap.insert(src.rbwSSAIdMap.begin(), src.rbwSSAIdMap.end());
    1447     for (size_t i = 0; i < MAX_REGTYPES_NUM; i++)
    1448         destVars.vs[i].insert(srcVars.vs[i].begin(), srcVars.vs[i].end());
    1449    
    1450     // join source lastAccessMap with curSVRegMap
    1451     for (const auto& sentry: src.lastAccessMap)
    1452     {
    1453         auto res = curSVRegMap.insert({ sentry.first, { entry.blockIndex, true } });
    1454         if (!res.second)
    1455         {   // not added because is present in map
    1456             if (res.first->second.blockIndex != entry.blockIndex)
    1457                 entry.prevCurSVRegMap.insert(*res.first);
    1458             // otherwise, it is same code block but inside routines
    1459             // and do not change prevCurSVRegMap for revert
    1460             // update entry
    1461             res.first->second = { entry.blockIndex, true };
    1462         }
    1463         else
    1464             entry.prevCurSVRegMap.insert({ sentry.first, { SIZE_MAX, true } });
    1465     }
    1466 }
    1467 
    1468 static void createRoutineDataLv(const std::vector<CodeBlock>& codeBlocks,
    1469         const RoutineLvMap& routineMap,
    1470         const std::unordered_map<size_t, VIdxSetEntry>& vidxRoutineMap,
    1471         RoutineDataLv& rdata, VIdxSetEntry& routineVIdxes,
    1472         size_t routineBlock, const VarIndexMap* vregIndexMaps,
    1473         size_t regTypesNum, const cxuint* regRanges)
    1474 {
    1475     std::deque<FlowStackEntry4> flowStack;
    1476     std::unordered_set<size_t> visited;
    1477    
    1478     // already read in current path
    1479     // key - vreg, value - source block where vreg of conflict found
    1480     SVRegMap alreadyReadMap;
    1481     std::unordered_set<AsmSingleVReg> vregsNotInAllRets;
    1482     std::unordered_set<AsmSingleVReg> vregsInFirstReturn;
    1483    
    1484     bool notFirstReturn = false;
    1485     flowStack.push_back({ routineBlock, 0 });
    1486     RoutineCurAccessMap curSVRegMap; // key - svreg, value - block index
    1487    
    1488     while (!flowStack.empty())
    1489     {
    1490         FlowStackEntry4& entry = flowStack.back();
    1491         const CodeBlock& cblock = codeBlocks[entry.blockIndex];
    1492        
    1493         if (entry.nextIndex == 0)
    1494         {
    1495             // process current block
    1496             if (visited.insert(entry.blockIndex).second)
    1497             {
    1498                 for (const auto& sentry: cblock.ssaInfoMap)
    1499                 {
    1500                     if (sentry.second.readBeforeWrite)
    1501                         if (alreadyReadMap.insert(
    1502                                     { sentry.first, entry.blockIndex }).second)
    1503                         {
    1504                             auto res = rdata.rbwSSAIdMap.insert({ sentry.first,
    1505                                         sentry.second.ssaIdBefore });
    1506                             if (res.second && notFirstReturn)
    1507                                 // first readBeforeWrite and notFirstReturn
    1508                                 vregsNotInAllRets.insert(sentry.first);
    1509                         }
    1510                    
    1511                     auto res = curSVRegMap.insert({ sentry.first,
    1512                         LastAccessBlockPos{ entry.blockIndex, false } });
    1513                     if (!res.second)
    1514                     {   // not added because is present in map
    1515                         entry.prevCurSVRegMap.insert(*res.first);
    1516                         res.first->second = { entry.blockIndex, false };
    1517                     }
    1518                     else
    1519                         entry.prevCurSVRegMap.insert(
    1520                                         { sentry.first, { SIZE_MAX, false } });
    1521                    
    1522                     // all SSAs
    1523                     const SSAInfo& sinfo = sentry.second;
    1524                     const AsmSingleVReg& svreg = sentry.first;
    1525                     cxuint regType = getRegType(regTypesNum, regRanges, svreg);
    1526                     const VarIndexMap& vregIndexMap = vregIndexMaps[regType];
    1527                     const std::vector<size_t>& vidxes =
    1528                                 vregIndexMap.find(svreg)->second;
    1529                    
    1530                     // add SSA indices to allSSAs
    1531                     if (sinfo.readBeforeWrite)
    1532                         routineVIdxes.vs[regType].insert(vidxes[sinfo.ssaIdBefore]);
    1533                     if (sinfo.ssaIdChange != 0)
    1534                     {
    1535                         routineVIdxes.vs[regType].insert(vidxes[sinfo.ssaIdFirst]);
    1536                         for (size_t i = 1; i < sinfo.ssaIdChange; i++)
    1537                             routineVIdxes.vs[regType].insert(vidxes[sinfo.ssaId+i]);
    1538                         routineVIdxes.vs[regType].insert(vidxes[sinfo.ssaIdLast]);
    1539                     }
    1540                 }
    1541             }
    1542             else
    1543             {
    1544                 flowStack.pop_back();
    1545                 continue;
    1546             }
    1547         }
    1548        
    1549         // join and skip calls
    1550         {
    1551             std::vector<size_t> calledRoutines;
    1552             for (; entry.nextIndex < cblock.nexts.size() &&
    1553                         cblock.nexts[entry.nextIndex].isCall; entry.nextIndex++)
    1554             {
    1555                 size_t rblock = cblock.nexts[entry.nextIndex].block;
    1556                 if (rblock != routineBlock)
    1557                     calledRoutines.push_back(rblock);
    1558             }
    1559            
    1560             for (size_t srcRoutBlock: calledRoutines)
    1561             {
    1562                 // update svregs 'not in all returns'
    1563                 const RoutineDataLv& srcRdata = routineMap.find(srcRoutBlock)->second;
    1564                 if (notFirstReturn)
    1565                     for (const auto& vrentry: srcRdata.rbwSSAIdMap)
    1566                         if (rdata.rbwSSAIdMap.find(vrentry.first)==rdata.rbwSSAIdMap.end())
    1567                             vregsNotInAllRets.insert(vrentry.first);
    1568                
    1569                 joinRoutineDataLv(rdata, routineVIdxes, curSVRegMap, entry,
    1570                         srcRdata, vidxRoutineMap.find(srcRoutBlock)->second);
    1571             }
    1572         }
    1573        
    1574         if (entry.nextIndex < cblock.nexts.size())
    1575         {
    1576             flowStack.push_back({ cblock.nexts[entry.nextIndex].block, 0 });
    1577             entry.nextIndex++;
    1578         }
    1579         else if (((entry.nextIndex==0 && cblock.nexts.empty()) ||
    1580                 // if have any call then go to next block
    1581                 (cblock.haveCalls && entry.nextIndex==cblock.nexts.size())) &&
    1582                  !cblock.haveReturn && !cblock.haveEnd)
    1583         {
    1584             flowStack.push_back({ entry.blockIndex+1, 0 });
    1585             entry.nextIndex++;
    1586         }
    1587         else
    1588         {
    1589             if (cblock.haveReturn)
    1590             {
    1591                 // handle return
    1592                 // add curSVReg access positions to lastAccessMap
    1593                 for (const auto& entry: curSVRegMap)
    1594                 {
    1595                     auto res = rdata.lastAccessMap.insert({ entry.first,
    1596                                     { entry.second } });
    1597                     if (!res.second)
    1598                         res.first->second.insertValue(entry.second);
    1599                     if (!notFirstReturn)
    1600                         // fill up vregs for first return
    1601                         vregsInFirstReturn.insert(entry.first);
    1602                 }
    1603                 if (notFirstReturn)
    1604                     for (const AsmSingleVReg& vreg: vregsInFirstReturn)
    1605                         if (curSVRegMap.find(vreg) == curSVRegMap.end())
    1606                             // not found in this path then add to 'not in all paths'
    1607                             vregsNotInAllRets.insert(vreg);
    1608                
    1609                 notFirstReturn = true;
    1610             }
    1611             // revert curSVRegMap
    1612             for (const auto& sentry: entry.prevCurSVRegMap)
    1613                 if (sentry.second.blockIndex != SIZE_MAX)
    1614                     curSVRegMap.find(sentry.first)->second = sentry.second;
    1615                 else // no before that
    1616                     curSVRegMap.erase(sentry.first);
    1617            
    1618             for (const auto& sentry: cblock.ssaInfoMap)
    1619             {
    1620                 auto it = alreadyReadMap.find(sentry.first);
    1621                 if (it != alreadyReadMap.end() && it->second == entry.blockIndex)
    1622                     // remove old to resolve in leaved way to allow collecting next ssaId
    1623                     // before write (can be different due to earlier visit)
    1624                     alreadyReadMap.erase(it);
    1625             }
    1626             ARDOut << "  popjoin\n";
    1627             flowStack.pop_back();
    1628         }
    1629     }
    1630    
    1631     // handle unused svregs in this path (from routine start) and
    1632     // used other paths and have this same ssaId as at routine start.
    1633     // just add to lastAccessMap svreg for start to join through all routine
    1634     for (const AsmSingleVReg& svreg: vregsNotInAllRets)
    1635     {
    1636         auto res = rdata.lastAccessMap.insert({ svreg, { { routineBlock, false } } });
    1637         if (!res.second)
    1638             res.first->second.insertValue({ routineBlock, false });
    1639     }
    1640 }
    1641 
    1642 static inline void revertLastSVReg(LastVRegMap& lastVRegMap, const AsmSingleVReg& svreg)
    1643 {
    1644     auto lvrit = lastVRegMap.find(svreg);
    1645     if (lvrit != lastVRegMap.end())
    1646     {
    1647         std::vector<LastVRegStackPos>& lastPos = lvrit->second;
    1648         lastPos.pop_back();
    1649         if (lastPos.empty()) // just remove from lastVRegs
    1650             lastVRegMap.erase(lvrit);
    1651     }
    1652 }
    1653 
    1654 /* TODO: handling livenesses between routine call:
    1655  *   for any routine call in call point:
    1656  *     add extra liveness point which will be added to liveness of the vars used between
    1657  *     call point and to liveness of the vars used inside routine
    1658  */
    1659 
    1660 void AsmRegAllocator::createLivenesses(ISAUsageHandler& usageHandler)
    1661 {
    1662     ARDOut << "----- createLivenesses ------\n";
    1663     // construct var index maps
    1664     cxuint regRanges[MAX_REGTYPES_NUM*2];
    1665     std::fill(graphVregsCounts, graphVregsCounts+MAX_REGTYPES_NUM, size_t(0));
    1666     size_t regTypesNum;
    1667     assembler.isaAssembler->getRegisterRanges(regTypesNum, regRanges);
    1668    
    1669     for (const CodeBlock& cblock: codeBlocks)
    1670         for (const auto& entry: cblock.ssaInfoMap)
    1671         {
    1672             const SSAInfo& sinfo = entry.second;
    1673             cxuint regType = getRegType(regTypesNum, regRanges, entry.first);
    1674             VarIndexMap& vregIndices = vregIndexMaps[regType];
    1675             size_t& graphVregsCount = graphVregsCounts[regType];
    1676             std::vector<size_t>& vidxes = vregIndices[entry.first];
    1677             size_t ssaIdCount = 0;
    1678             if (sinfo.readBeforeWrite)
    1679                 ssaIdCount = sinfo.ssaIdBefore+1;
    1680             if (sinfo.ssaIdChange!=0)
    1681             {
    1682                 ssaIdCount = std::max(ssaIdCount, sinfo.ssaIdLast+1);
    1683                 ssaIdCount = std::max(ssaIdCount, sinfo.ssaId+sinfo.ssaIdChange-1);
    1684                 ssaIdCount = std::max(ssaIdCount, sinfo.ssaIdFirst+1);
    1685             }
    1686             // if not readBeforeWrite and neither ssaIdChanges but it is write to
    1687             // normal register
    1688             if (entry.first.regVar==nullptr)
    1689                 ssaIdCount = 1;
    1690            
    1691             if (vidxes.size() < ssaIdCount)
    1692                 vidxes.resize(ssaIdCount, SIZE_MAX);
    1693            
    1694             // set liveness index to vidxes
    1695             if (sinfo.readBeforeWrite)
    1696             {
    1697                 if (vidxes[sinfo.ssaIdBefore] == SIZE_MAX)
    1698                     vidxes[sinfo.ssaIdBefore] = graphVregsCount++;
    1699             }
    1700             if (sinfo.ssaIdChange!=0)
    1701             {
    1702                 // fill up vidxes (with graph Ids)
    1703                 if (vidxes[sinfo.ssaIdFirst] == SIZE_MAX)
    1704                     vidxes[sinfo.ssaIdFirst] = graphVregsCount++;
    1705                 for (size_t ssaId = sinfo.ssaId+1;
    1706                         ssaId < sinfo.ssaId+sinfo.ssaIdChange-1; ssaId++)
    1707                     vidxes[ssaId] = graphVregsCount++;
    1708                 if (vidxes[sinfo.ssaIdLast] == SIZE_MAX)
    1709                     vidxes[sinfo.ssaIdLast] = graphVregsCount++;
    1710             }
    1711             // if not readBeforeWrite and neither ssaIdChanges but it is write to
    1712             // normal register
    1713             if (entry.first.regVar==nullptr && vidxes[0] == SIZE_MAX)
    1714                 vidxes[0] = graphVregsCount++;
    1715         }
    1716    
    1717     // construct vreg liveness
    1718     std::deque<CallStackEntry2> callStack;
    1719     std::deque<FlowStackEntry3> flowStack;
    1720     std::vector<bool> visited(codeBlocks.size(), false);
    1721     // hold last vreg ssaId and position
    1722     LastVRegMap lastVRegMap;
    1723    
    1724     // key - current res first key, value - previous first key and its flowStack pos
    1725     PrevWaysIndexMap prevWaysIndexMap;
    1726     // to track ways last block indices pair: block index, flowStackPos)
    1727     std::pair<size_t, size_t> lastCommonCacheWayPoint{ SIZE_MAX, SIZE_MAX };
    1728     std::vector<bool> waysToCache(codeBlocks.size(), false);
    1729     ResSecondPointsToCache cblocksToCache(codeBlocks.size());
    1730    
    1731     size_t rbwCount = 0;
    1732     size_t wrCount = 0;
    1733    
    1734     RoutineLvMap routineMap;
    1735     std::vector<Liveness> livenesses[MAX_REGTYPES_NUM];
    1736    
    1737     for (size_t i = 0; i < regTypesNum; i++)
    1738         livenesses[i].resize(graphVregsCounts[i]);
    1739    
    1740     // callLiveTime - call live time where routine will be called
    1741     // reverse counted, begin from SIZE_MAX, used for joining svreg from routines
    1742     // and svreg used in this time
    1743     size_t curLiveTime = 0;
    1744     flowStack.push_back({ 0, 0 });
    1745    
    1746     while (!flowStack.empty())
    1747     {
    1748         FlowStackEntry3& entry = flowStack.back();
    1749         CodeBlock& cblock = codeBlocks[entry.blockIndex];
    1750        
    1751         if (entry.nextIndex == 0)
    1752         {
    1753             curLiveTime = cblock.start;
    1754             // process current block
    1755             if (!visited[entry.blockIndex])
    1756             {
    1757                 visited[entry.blockIndex] = true;
    1758                 ARDOut << "joinpush: " << entry.blockIndex << "\n";
    1759                 if (flowStack.size() > 1)
    1760                     putCrossBlockLivenesses(flowStack, codeBlocks, routineMap,
    1761                             vidxCallMap, vidxRoutineMap, lastVRegMap,
    1762                             livenesses, vregIndexMaps, regTypesNum, regRanges);
    1763                 // update last vreg position
    1764                 for (const auto& sentry: cblock.ssaInfoMap)
    1765                 {
    1766                     // update
    1767                     auto res = lastVRegMap.insert({ sentry.first,
    1768                                 { { flowStack.size()-1, false } } });
    1769                     if (!res.second) // if not first seen, just update
    1770                         // update last
    1771                         res.first->second.push_back({ flowStack.size()-1, false });
    1772                    
    1773                     // count read before writes (for cache weight)
    1774                     if (sentry.second.readBeforeWrite)
    1775                         rbwCount++;
    1776                     if (sentry.second.ssaIdChange!=0)
    1777                         wrCount++;
    1778                 }
    1779                
    1780                 // main routine to handle ssaInfos
    1781                 SVRegMap ssaIdIdxMap;
    1782                 AsmRegVarUsage instrRVUs[8];
    1783                 cxuint instrRVUsCount = 0;
    1784                
    1785                 size_t oldOffset = cblock.usagePos.readOffset;
    1786                 std::vector<AsmSingleVReg> readSVRegs;
    1787                 std::vector<AsmSingleVReg> writtenSVRegs;
    1788                
    1789                 usageHandler.setReadPos(cblock.usagePos);
    1790                 // register in liveness
    1791                 while (true)
    1792                 {
    1793                     AsmRegVarUsage rvu = { 0U, nullptr, 0U, 0U };
    1794                     bool hasNext = false;
    1795                     if (usageHandler.hasNext() && oldOffset < cblock.end)
    1796                     {
    1797                         hasNext = true;
    1798                         rvu = usageHandler.nextUsage();
    1799                     }
    1800                     const size_t liveTime = oldOffset;
    1801                     if ((!hasNext || rvu.offset > oldOffset) && oldOffset < cblock.end)
    1802                     {
    1803                         ARDOut << "apply to liveness. offset: " << oldOffset << "\n";
    1804                         // apply to liveness
    1805                         for (AsmSingleVReg svreg: readSVRegs)
    1806                         {
    1807                             auto svrres = ssaIdIdxMap.insert({ svreg, 0 });
    1808                             Liveness& lv = getLiveness(svreg, svrres.first->second,
    1809                                     cblock.ssaInfoMap.find(svreg)->second,
    1810                                     livenesses, vregIndexMaps, regTypesNum, regRanges);
    1811                             if (svrres.second)
    1812                                 // begin region from this block
    1813                                 lv.newRegion(curLiveTime);
    1814                             lv.expand(liveTime);
    1815                         }
    1816                         for (AsmSingleVReg svreg: writtenSVRegs)
    1817                         {
    1818                             size_t& ssaIdIdx = ssaIdIdxMap[svreg];
    1819                             if (svreg.regVar != nullptr)
    1820                                 ssaIdIdx++;
    1821                             SSAInfo& sinfo = cblock.ssaInfoMap.find(svreg)->second;
    1822                             Liveness& lv = getLiveness(svreg, ssaIdIdx, sinfo,
    1823                                     livenesses, vregIndexMaps, regTypesNum, regRanges);
    1824                             // works only with ISA where smallest instruction have 2 bytes!
    1825                             // after previous read, but not after instruction.
    1826                             // if var is not used anywhere then this liveness region
    1827                             // blocks assignment for other vars
    1828                             lv.insert(liveTime+1, liveTime+2);
    1829                         }
    1830                         // get linear deps and equal to
    1831                         cxbyte lDeps[16];
    1832                         usageHandler.getUsageDependencies(instrRVUsCount, instrRVUs, lDeps);
    1833                        
    1834                         addUsageDeps(lDeps, instrRVUsCount, instrRVUs,
    1835                                 linearDepMaps, vregIndexMaps, ssaIdIdxMap,
    1836                                 regTypesNum, regRanges);
    1837                        
    1838                         readSVRegs.clear();
    1839                         writtenSVRegs.clear();
    1840                         if (!hasNext)
    1841                             break;
    1842                         oldOffset = rvu.offset;
    1843                         instrRVUsCount = 0;
    1844                     }
    1845                     if (hasNext && oldOffset < cblock.end && !rvu.useRegMode)
    1846                         instrRVUs[instrRVUsCount++] = rvu;
    1847                     if (oldOffset >= cblock.end)
    1848                         break;
    1849                    
    1850                     for (uint16_t rindex = rvu.rstart; rindex < rvu.rend; rindex++)
    1851                     {
    1852                         // per register/singlvreg
    1853                         AsmSingleVReg svreg{ rvu.regVar, rindex };
    1854                         if (rvu.rwFlags == ASMRVU_WRITE && rvu.regField!=ASMFIELD_NONE)
    1855                             writtenSVRegs.push_back(svreg);
    1856                         else // read or treat as reading // expand previous region
    1857                             readSVRegs.push_back(svreg);
    1858                     }
    1859                 }
    1860             }
    1861             else
    1862             {
    1863                 cblocksToCache.increase(entry.blockIndex);
    1864                 ARDOut << "jcblockToCache: " << entry.blockIndex << "=" <<
    1865                             cblocksToCache.count(entry.blockIndex) << "\n";
    1866                
    1867                 // back, already visited
    1868                 flowStack.pop_back();
    1869                
    1870                 size_t curWayBIndex = flowStack.back().blockIndex;
    1871                 if (lastCommonCacheWayPoint.first != SIZE_MAX)
    1872                 {
    1873                     // mark point of way to cache (res first point)
    1874                     waysToCache[lastCommonCacheWayPoint.first] = true;
    1875                     ARDOut << "mark to pfcache " <<
    1876                             lastCommonCacheWayPoint.first << ", " <<
    1877                             curWayBIndex << "\n";
    1878                     prevWaysIndexMap[curWayBIndex] = lastCommonCacheWayPoint;
    1879                 }
    1880                 lastCommonCacheWayPoint = { curWayBIndex, flowStack.size()-1 };
    1881                 ARDOut << "lastCcwP: " << curWayBIndex << "\n";
    1882                 continue;
    1883             }
    1884         }
    1885        
    1886         if (!callStack.empty() &&
    1887             entry.blockIndex == callStack.back().callBlock &&
    1888             entry.nextIndex-1 == callStack.back().callNextIndex)
    1889         {
    1890             ARDOut << " ret: " << entry.blockIndex << "\n";
    1891             const size_t routineBlock = callStack.back().routineBlock;
    1892             auto res = routineMap.insert({ routineBlock, { } });
    1893            
    1894             if (res.second)
    1895             {
    1896                 auto varRes = vidxRoutineMap.insert({ routineBlock, VIdxSetEntry{} });
    1897                 createRoutineDataLv(codeBlocks, routineMap, vidxRoutineMap,
    1898                         res.first->second, varRes.first->second,
    1899                         routineBlock, vregIndexMaps, regTypesNum, regRanges);
    1900             }
    1901             else
    1902             {
    1903                 // already added join livenesses from all readBeforeWrites
    1904                 for (const auto& entry: res.first->second.rbwSSAIdMap)
    1905                 {
    1906                     // find last
    1907                     auto lvrit = lastVRegMap.find(entry.first);
    1908                     LastVRegStackPos flowStackStart = (lvrit != lastVRegMap.end()) ?
    1909                             lvrit->second.back() : LastVRegStackPos{ 0, false };
    1910                    
    1911                     joinVRegRecur(flowStack, codeBlocks, routineMap,
    1912                                   vidxCallMap, vidxRoutineMap,
    1913                             flowStackStart, entry.first, entry.second, vregIndexMaps,
    1914                             livenesses, regTypesNum, regRanges, false);
    1915                 }
    1916             }
    1917             callStack.pop_back(); // just return from call
    1918         }
    1919        
    1920         if (entry.nextIndex < cblock.nexts.size())
    1921         {
    1922             //bool isCall = false;
    1923             size_t nextBlock = cblock.nexts[entry.nextIndex].block;
    1924             if (cblock.nexts[entry.nextIndex].isCall)
    1925             {
    1926                 callStack.push_back({ entry.blockIndex, entry.nextIndex, nextBlock });
    1927                 //isCall = true;
    1928             }
    1929            
    1930             flowStack.push_back({ cblock.nexts[entry.nextIndex].block, 0 });
    1931             entry.nextIndex++;
    1932         }
    1933         else if (((entry.nextIndex==0 && cblock.nexts.empty()) ||
    1934                 // if have any call then go to next block
    1935                 (cblock.haveCalls && entry.nextIndex==cblock.nexts.size())) &&
    1936                  !cblock.haveReturn && !cblock.haveEnd)
    1937         {
    1938             if (entry.nextIndex!=0) // if back from calls (just return from calls)
    1939             {
    1940                 std::unordered_set<AsmSingleVReg> regSVRegs;
    1941                 // just add last access of svreg from call routines to lastVRegMap
    1942                 // and join svregs from routine with svreg used at this time
    1943                 for (const NextBlock& next: cblock.nexts)
    1944                     if (next.isCall)
    1945                     {
    1946                         const RoutineDataLv& rdata = routineMap.find(next.block)->second;
    1947                         for (const auto& entry: rdata.lastAccessMap)
    1948                             if (regSVRegs.insert(entry.first).second)
    1949                             {
    1950                                 auto res = lastVRegMap.insert({ entry.first,
    1951                                         { { flowStack.size()-1, true } } });
    1952                                 if (!res.second) // if not first seen, just update
    1953                                     // update last
    1954                                     res.first->second.push_back(
    1955                                                 { flowStack.size()-1, true });
    1956                             }
    1957                     }
    1958             }
    1959            
    1960             flowStack.push_back({ entry.blockIndex+1, 0 });
    1961             entry.nextIndex++;
    1962         }
    1963         else // back
    1964         {
    1965             // revert lastSSAIdMap
    1966             flowStack.pop_back();
    1967            
    1968             // revert lastVRegs in call
    1969             std::unordered_set<AsmSingleVReg> revertedSVRegs;
    1970             for (const NextBlock& next: cblock.nexts)
    1971                 if (next.isCall)
    1972                 {
    1973                     const RoutineDataLv& rdata = routineMap.find(next.block)->second;
    1974                     for (const auto& entry: rdata.lastAccessMap)
    1975                         if (revertedSVRegs.insert(entry.first).second)
    1976                             revertLastSVReg(lastVRegMap, entry.first);
    1977                 }
    1978            
    1979             for (const auto& sentry: cblock.ssaInfoMap)
    1980                 revertLastSVReg(lastVRegMap, sentry.first);
    1981            
    1982             if (!flowStack.empty() && lastCommonCacheWayPoint.first != SIZE_MAX &&
    1983                     lastCommonCacheWayPoint.second >= flowStack.size())
    1984             {
    1985                 lastCommonCacheWayPoint =
    1986                         { flowStack.back().blockIndex, flowStack.size()-1 };
    1987                 ARDOut << "POPlastCcwP: " << lastCommonCacheWayPoint.first << "\n";
    1988             }
    1989         }
    1990     }
    1991    
    1992     // after, that resolve joins (join with already visited code)
    1993     // SVRegMap in this cache: key - vreg, value - last flowStack entry position
    1994     SimpleCache<size_t, LastStackPosMap> joinFirstPointsCache(wrCount<<1);
    1995     // SVRegMap in this cache: key - vreg, value - first readBefore in second part
    1996     SimpleCache<size_t, SVRegMap> joinSecondPointsCache(rbwCount<<1);
    1997    
    1998     flowStack.clear();
    1999     std::fill(visited.begin(), visited.end(), false);
    2000    
    2001     flowStack.push_back({ 0, 0 });
    2002    
    2003     while (!flowStack.empty())
    2004     {
    2005         FlowStackEntry3& entry = flowStack.back();
    2006         CodeBlock& cblock = codeBlocks[entry.blockIndex];
    2007        
    2008         if (entry.nextIndex == 0)
    2009         {
    2010             // process current block
    2011             if (!visited[entry.blockIndex])
    2012                 visited[entry.blockIndex] = true;
    2013             else
    2014             {
    2015                 joinRegVarLivenesses(flowStack, codeBlocks, routineMap,
    2016                         vidxCallMap, vidxRoutineMap,
    2017                         prevWaysIndexMap, waysToCache, cblocksToCache,
    2018                         joinFirstPointsCache, joinSecondPointsCache,
    2019                         vregIndexMaps, livenesses, regTypesNum, regRanges);
    2020                 // back, already visited
    2021                 flowStack.pop_back();
    2022                 continue;
    2023             }
    2024         }
    2025        
    2026         if (entry.nextIndex < cblock.nexts.size())
    2027         {
    2028             flowStack.push_back({ cblock.nexts[entry.nextIndex].block, 0 });
    2029             entry.nextIndex++;
    2030         }
    2031         else if (((entry.nextIndex==0 && cblock.nexts.empty()) ||
    2032                 // if have any call then go to next block
    2033                 (cblock.haveCalls && entry.nextIndex==cblock.nexts.size())) &&
    2034                  !cblock.haveReturn && !cblock.haveEnd)
    2035         {
    2036             flowStack.push_back({ entry.blockIndex+1, 0 });
    2037             entry.nextIndex++;
    2038         }
    2039         else // back
    2040         {
    2041             if (cblocksToCache.count(entry.blockIndex)==2 &&
    2042                 !joinSecondPointsCache.hasKey(entry.blockIndex))
    2043                 // add to cache
    2044                 addJoinSecCacheEntry(routineMap, codeBlocks, joinSecondPointsCache,
    2045                             entry.blockIndex);
    2046             flowStack.pop_back();
    2047         }
    2048     }
    2049    
    2050     // move livenesses to AsmRegAllocator outLivenesses
    2051     for (size_t regType = 0; regType < regTypesNum; regType++)
    2052     {
    2053         std::vector<Liveness>& livenesses2 = livenesses[regType];
    2054         Array<OutLiveness>& outLivenesses2 = outLivenesses[regType];
    2055         outLivenesses2.resize(livenesses2.size());
    2056         for (size_t li = 0; li < livenesses2.size(); li++)
    2057         {
    2058             outLivenesses2[li].resize(livenesses2[li].l.size());
    2059             std::copy(livenesses2[li].l.begin(), livenesses2[li].l.end(),
    2060                       outLivenesses2[li].begin());
    2061             livenesses2[li].clear();
    2062         }
    2063         livenesses2.clear();
    2064     }
    2065 }
    2066 
    2067686void AsmRegAllocator::createInterferenceGraph()
    2068687{
  • CLRadeonExtender/trunk/amdasm/CMakeLists.txt

    r3991 r4134  
    2929        AsmROCmFormat.cpp
    3030        AsmRegAlloc.cpp
     31        AsmRegAllocLive.cpp
    3132        AsmRegAllocSSAData.cpp
    3233        AsmSource.cpp
  • CLRadeonExtender/trunk/tests/amdasm/AsmRegAlloc3.cpp

    r4131 r4134  
    13431343        }, // vidxRoutineMap
    13441344        {
    1345             // TODO: check!
    13461345            { 0, { { { 5, 12 }, { 5 }, { }, { } } } },
    13471346            { 3, { { { 9, 10, 11 }, { 0, 1, 2, 4 }, { }, { } } } },
Note: See TracChangeset for help on using the changeset viewer.