Changeset 3837 in CLRX
 Timestamp:
 Feb 22, 2018, 5:51:47 PM (17 months ago)
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

CLRadeonExtender/trunk/amdasm/AsmRegAlloc.cpp
r3658 r3837 444 444 // map of last SSAId for routine, key  varid, value  last SSA ids 445 445 typedef std::unordered_map<AsmSingleVReg, std::vector<size_t> > LastSSAIdMap; 446 447 typedef std::unordered_map<AsmSingleVReg, std::vector<bool> > LastOccurMap;448 446 449 447 struct RetSSAEntry … … 892 890 } 893 891 892 static void reduceSSAIds(std::unordered_map<AsmSingleVReg, size_t>& curSSAIdMap, 893 RetSSAIdMap& retSSAIdMap, std::unordered_map<size_t, RoutineData>& routineMap, 894 SSAReplacesMap& ssaReplacesMap, 895 std::pair<const AsmSingleVReg, AsmRegAllocator::SSAInfo>& ssaEntry) 896 { 897 SSAInfo& sinfo = ssaEntry.second; 898 size_t& ssaId = curSSAIdMap[ssaEntry.first]; 899 auto ssaIdsIt = retSSAIdMap.find(ssaEntry.first); 900 if (ssaIdsIt != retSSAIdMap.end() && sinfo.readBeforeWrite) 901 { 902 auto& ssaIds = ssaIdsIt>second.ssaIds; 903 904 if (ssaIds.size() >= 2) 905 { 906 // reduce to minimal ssaId from all calls 907 std::sort(ssaIds.begin(), ssaIds.end()); 908 ssaIds.resize(std::unique(ssaIds.begin(), ssaIds.end())  ssaIds.begin()); 909 // insert SSA replaces 910 size_t minSSAId = ssaIds.front(); 911 for (auto sit = ssaIds.begin()+1; sit != ssaIds.end(); ++sit) 912 insertReplace(ssaReplacesMap, ssaEntry.first, *sit, minSSAId); 913 ssaId = minSSAId+1; // plus one 914 } 915 else if (ssaIds.size() == 1) 916 ssaId = ssaIds.front()+1; // plus one 917 918 std::cout << "retssa ssaid: " << ssaEntry.first.regVar << ":" << 919 ssaEntry.first.index << ": " << ssaId << std::endl; 920 // replace smallest ssaId in routineMap lastSSAId entry 921 // reduce SSAIds replaces 922 for (size_t rblock: ssaIdsIt>second.routines) 923 routineMap.find(rblock)>second.lastSSAIdMap[ssaEntry.first] = 924 std::vector<size_t>({ ssaId1 }); 925 // finally remove from container (because obsolete) 926 retSSAIdMap.erase(ssaIdsIt); 927 } 928 } 929 930 static void updateRoutineData(RoutineData& rdata, 931 std::pair<const AsmSingleVReg, AsmRegAllocator::SSAInfo>& ssaEntry) 932 { 933 const SSAInfo& sinfo = ssaEntry.second; 934 // put first SSAId before write 935 if (sinfo.readBeforeWrite) 936 { 937 //std::cout << "PutCRBW: " << sinfo.ssaIdBefore << std::endl; 938 rdata.rbwSSAIdMap.insert({ ssaEntry.first, sinfo.ssaIdBefore }); 939 } 940 941 if (sinfo.ssaIdChange != 0) 942 { 943 // put last SSAId 944 //std::cout << "PutC: " << sinfo.ssaIdLast << std::endl; 945 auto res = rdata.curSSAIdMap.insert({ ssaEntry.first, 946 { sinfo.ssaIdLast } }); 947 if (!res.second) 948 { 949 // if not inserted 950 std::vector<size_t>& ssaIds = res.first>second; 951 auto ssaIdIt = ssaIds.end(); 952 if (sinfo.readBeforeWrite) 953 ssaIdIt = std::find(ssaIds.begin(), ssaIds.end(), 954 sinfo.ssaIdBefore); 955 if (ssaIdIt == ssaIds.end()) 956 ssaIds.push_back(sinfo.ssaIdLast); 957 else 958 *ssaIdIt = sinfo.ssaIdLast; 959 } 960 } 961 } 962 963 static void initializePrevRetSSAIds(const RetSSAIdMap& retSSAIdMap, 964 const RoutineData& rdata, FlowStackEntry& entry) 965 { 966 for (const auto& v: rdata.lastSSAIdMap) 967 { 968 auto res = entry.prevRetSSAIdSets.insert({v.first, {}}); 969 if (!res.second) 970 continue; // already added, do not change 971 auto rfit = retSSAIdMap.find(v.first); 972 if (rfit != retSSAIdMap.end()) 973 res.first>second = rfit>second; 974 } 975 } 976 977 static void revertRetSSAIdMap(std::unordered_map<AsmSingleVReg, size_t>& curSSAIdMap, 978 RetSSAIdMap& retSSAIdMap, FlowStackEntry& entry, RoutineData* rdata) 979 { 980 // revert retSSAIdMap 981 for (auto v: entry.prevRetSSAIdSets) 982 { 983 auto rfit = retSSAIdMap.find(v.first); 984 if (rdata!=nullptr) 985 { 986 std::vector<size_t>& ssaIds = rdata>curSSAIdMap[v.first]; 987 for (size_t ssaId: rfit>second.ssaIds) 988 { 989 auto ssaIdsIt = std::find(ssaIds.begin(), ssaIds.end(), ssaId); 990 if (ssaIdsIt != ssaIds.end()) 991 ssaIds.erase(ssaIdsIt); 992 } 993 } 994 995 if (!v.second.ssaIds.empty()) 996 rfit>second = v.second; 997 else // erase if empty 998 retSSAIdMap.erase(v.first); 999 1000 if (rdata!=nullptr) 1001 { 1002 std::vector<size_t>& ssaIds = rdata>curSSAIdMap[v.first]; 1003 for (size_t ssaId: v.second.ssaIds) 1004 { 1005 auto ssaIdsIt = std::find(ssaIds.begin(), ssaIds.end(), ssaId); 1006 if (ssaIdsIt == ssaIds.end()) 1007 ssaIds.push_back(ssaId); 1008 } 1009 if (v.second.ssaIds.empty()) 1010 ssaIds.push_back(curSSAIdMap[v.first]1); 1011 1012 std::cout << " popentry2 " << entry.blockIndex << ": " << 1013 v.first.regVar << ":" << v.first.index << ":"; 1014 for (size_t v: ssaIds) 1015 std::cout << " " << v; 1016 std::cout << std::endl; 1017 } 1018 } 1019 } 1020 1021 static void updateRoutineCurSSAIdMap(RoutineData* rdata, 1022 const std::pair<const AsmSingleVReg, AsmRegAllocator::SSAInfo>& ssaEntry, 1023 const FlowStackEntry& entry, size_t curSSAId, size_t nextSSAId) 1024 { 1025 std::vector<size_t>& ssaIds = rdata>curSSAIdMap[ssaEntry.first]; 1026 std::cout << " pushentry " << entry.blockIndex << ": " << 1027 ssaEntry.first.regVar << ":" << ssaEntry.first.index << ":"; 1028 for (size_t v: ssaIds) 1029 std::cout << " " << v; 1030 std::cout << std::endl; 1031 1032 { // if cblock with some children 1033 auto nit = std::find(ssaIds.begin(), ssaIds.end(), nextSSAId1); 1034 if (nit != ssaIds.end() && nextSSAId != curSSAId) 1035 { 1036 std::cout << "erase in blk2: " << ssaEntry.first.regVar << 1037 ":" << ssaEntry.first.index << ": " << 1038 entry.blockIndex << " ssaId=" << *nit << std::endl; 1039 ssaIds.erase(nit); // just remove 1040 } 1041 } 1042 // push previous SSAId to lastSSAIdMap (later will be replaced) 1043 /*std::cout << "call back: " << nextSSAId << "," << 1044 (curSSAId) << std::endl;*/ 1045 auto fit = std::find(ssaIds.begin(), ssaIds.end(), curSSAId1); 1046 if (fit == ssaIds.end()) 1047 ssaIds.push_back(curSSAId1); 1048 1049 std::cout << " popentry " << entry.blockIndex << ": " << 1050 ssaEntry.first.regVar << ":" << ssaEntry.first.index << ":"; 1051 for (size_t v: ssaIds) 1052 std::cout << " " << v; 1053 std::cout << std::endl; 1054 } 1055 894 1056 void AsmRegAllocator::createSSAData(ISAUsageHandler& usageHandler) 895 1057 { … … 968 1130 std::unordered_map<size_t, RoutineData> routineMap; 969 1131 970 LastOccurMap lastOccurMap;971 972 1132 std::vector<bool> visited(codeBlocks.size(), false); 973 1133 flowStack.push_back({ 0, 0 }); … … 996 1156 } 997 1157 998 if (sinfo.ssaIdChange != 0) 999 { 1000 /*std::cout << "loccurpush: " << ssaEntry.first.regVar << ":" << 1001 ssaEntry.first.index << ": " << 1002 entry.blockIndex << std::endl;*/ 1003 lastOccurMap[ssaEntry.first].push_back(false); 1004 } 1158 reduceSSAIds(curSSAIdMap, retSSAIdMap, routineMap, ssaReplacesMap, 1159 ssaEntry); 1005 1160 1006 1161 size_t& ssaId = curSSAIdMap[ssaEntry.first]; 1007 auto ssaIdsIt = retSSAIdMap.find(ssaEntry.first);1008 if (ssaIdsIt != retSSAIdMap.end() && sinfo.readBeforeWrite)1009 {1010 auto& ssaIds = ssaIdsIt>second.ssaIds;1011 1012 if (ssaIds.size() >= 2)1013 {1014 // reduce to minimal ssaId from all calls1015 std::sort(ssaIds.begin(), ssaIds.end());1016 ssaIds.resize(std::unique(ssaIds.begin(), ssaIds.end()) 1017 ssaIds.begin());1018 // insert SSA replaces1019 size_t minSSAId = ssaIds.front();1020 for (auto sit = ssaIds.begin()+1; sit != ssaIds.end(); ++sit)1021 insertReplace(ssaReplacesMap, ssaEntry.first,1022 *sit, minSSAId);1023 ssaId = minSSAId+1; // plus one1024 }1025 else if (ssaIds.size() == 1)1026 ssaId = ssaIds.front()+1; // plus one1027 1028 std::cout << "retssa ssaid: " << ssaEntry.first.regVar << ":" <<1029 ssaEntry.first.index << ": " << ssaId << std::endl;1030 // replace smallest ssaId in routineMap lastSSAId entry1031 // reduce SSAIds replaces1032 for (size_t rblock: ssaIdsIt>second.routines)1033 routineMap.find(rblock)>second.lastSSAIdMap[ssaEntry.first] =1034 std::vector<size_t>({ ssaId1 });1035 // finally remove from container (because obsolete)1036 retSSAIdMap.erase(ssaIdsIt);1037 }1038 1162 1039 1163 size_t& totalSSACount = totalSSACountMap[ssaEntry.first]; … … 1058 1182 1059 1183 if (!callStack.empty()) 1060 {1061 1184 // put data to routine data 1062 RoutineData& rdata = 1063 routineMap.find(callStack.back().routineBlock)>second; 1064 // put first SSAId before write 1065 if (sinfo.readBeforeWrite) 1066 { 1067 //std::cout << "PutCRBW: " << sinfo.ssaIdBefore << std::endl; 1068 rdata.rbwSSAIdMap.insert({ ssaEntry.first, sinfo.ssaIdBefore }); 1069 } 1070 1071 if (sinfo.ssaIdChange != 0) 1072 { 1073 // put last SSAId 1074 //std::cout << "PutC: " << sinfo.ssaIdLast << std::endl; 1075 auto res = rdata.curSSAIdMap.insert({ ssaEntry.first, 1076 { sinfo.ssaIdLast } }); 1077 if (!res.second) 1078 { 1079 // if not inserted 1080 std::vector<size_t>& ssaIds = res.first>second; 1081 auto ssaIdIt = ssaIds.end(); 1082 if (sinfo.readBeforeWrite) 1083 ssaIdIt = std::find(ssaIds.begin(), ssaIds.end(), 1084 sinfo.ssaIdBefore); 1085 if (ssaIdIt == ssaIds.end()) 1086 ssaIds.push_back(sinfo.ssaIdLast); 1087 else 1088 *ssaIdIt = sinfo.ssaIdLast; 1089 } 1090 } 1091 } 1185 updateRoutineData(routineMap.find( 1186 callStack.back().routineBlock)>second, ssaEntry); 1092 1187 } 1093 1188 } … … 1139 1234 //std::cout << "joincall:"<< next.block << std::endl; 1140 1235 auto it = routineMap.find(next.block); // must find 1141 for (const auto& v: it>second.lastSSAIdMap) 1142 { 1143 auto res = entry.prevRetSSAIdSets.insert({v.first, {}}); 1144 if (!res.second) 1145 continue; // already added, do not change 1146 auto rfit = retSSAIdMap.find(v.first); 1147 if (rfit != retSSAIdMap.end()) 1148 res.first>second = rfit>second; 1149 } 1150 1236 initializePrevRetSSAIds(retSSAIdMap, it>second, entry); 1151 1237 joinRetSSAIdMap(retSSAIdMap, it>second.lastSSAIdMap, next.block); 1152 1238 } … … 1169 1255 1170 1256 // revert retSSAIdMap 1171 for (auto v: entry.prevRetSSAIdSets) 1172 { 1173 auto rfit = retSSAIdMap.find(v.first); 1174 if (rdata!=nullptr) 1175 { 1176 std::vector<size_t>& ssaIds = rdata>curSSAIdMap[v.first]; 1177 for (size_t ssaId: rfit>second.ssaIds) 1178 { 1179 auto ssaIdsIt = std::find(ssaIds.begin(), ssaIds.end(), ssaId); 1180 if (ssaIdsIt != ssaIds.end()) 1181 ssaIds.erase(ssaIdsIt); 1182 } 1183 } 1184 1185 if (!v.second.ssaIds.empty()) 1186 rfit>second = v.second; 1187 else // erase if empty 1188 retSSAIdMap.erase(v.first); 1189 1190 if (rdata!=nullptr) 1191 { 1192 std::vector<size_t>& ssaIds = rdata>curSSAIdMap[v.first]; 1193 for (size_t ssaId: v.second.ssaIds) 1194 { 1195 auto ssaIdsIt = std::find(ssaIds.begin(), ssaIds.end(), ssaId); 1196 if (ssaIdsIt == ssaIds.end()) 1197 ssaIds.push_back(ssaId); 1198 } 1199 if (v.second.ssaIds.empty()) 1200 ssaIds.push_back(curSSAIdMap[v.first]1); 1201 1202 std::cout << " popentry2 " << entry.blockIndex << ": " << 1203 v.first.regVar << ":" << 1204 v.first.index << ":"; 1205 for (size_t v: ssaIds) 1206 std::cout << " " << v; 1207 std::cout << std::endl; 1208 1209 } 1210 } 1257 revertRetSSAIdMap(curSSAIdMap, retSSAIdMap, entry, rdata); 1211 1258 // 1212 1259 … … 1229 1276 1230 1277 if (rdata!=nullptr) 1278 updateRoutineCurSSAIdMap(rdata, ssaEntry, entry, curSSAId, nextSSAId); 1231 1279 { 1232 std::vector<size_t>& ssaIds = rdata>curSSAIdMap[ssaEntry.first];1233 1280 1234 std::cout << " pushentry " << entry.blockIndex << ": " <<1235 ssaEntry.first.regVar << ":" <<1236 ssaEntry.first.index << ":";1237 for (size_t v: ssaIds)1238 std::cout << " " << v;1239 std::cout << std::endl;1240 1241 /*if (ssaEntry.second.ssaIdChange != 0 &&1242 lastOccurMap[ssaEntry.first].back())*/1243 { // if cblock with some children1244 auto nit = std::find(ssaIds.begin(), ssaIds.end(), nextSSAId1);1245 if (nit != ssaIds.end() && nextSSAId != curSSAId)1246 {1247 std::cout << "erase in blk2: " << ssaEntry.first.regVar <<1248 ":" << ssaEntry.first.index << ": " <<1249 entry.blockIndex << " ssaId=" << *nit << std::endl;1250 ssaIds.erase(nit); // just remove1251 }1252 }1253 // push previous SSAId to lastSSAIdMap (later will be replaced)1254 /*std::cout << "call back: " << nextSSAId << "," <<1255 (curSSAId) << std::endl;*/1256 auto fit = std::find(ssaIds.begin(), ssaIds.end(), curSSAId1);1257 /*if (entry.blockIndex == callStack.back().routineBlock)1258 { // just erase if end of traverse in routine1259 if (fit != ssaIds.end())1260 {1261 std::cout << "erase in blk: " << ssaEntry.first.regVar <<1262 ":" << ssaEntry.first.index << ": " <<1263 entry.blockIndex << " ssaId=" << *fit << std::endl;1264 ssaIds.erase(fit);1265 }1266 }1267 else*/ if (fit == ssaIds.end())1268 ssaIds.push_back(curSSAId1);1269 1270 std::cout << " popentry " << entry.blockIndex << ": " <<1271 ssaEntry.first.regVar << ":" <<1272 ssaEntry.first.index << ":";1273 for (size_t v: ssaIds)1274 std::cout << " " << v;1275 std::cout << std::endl;1276 }1277 1278 if (ssaEntry.second.ssaIdChange != 0)1279 {1280 /*std::cout << "loccurpop: " << ssaEntry.first.regVar << ":" <<1281 ssaEntry.first.index << ": " <<1282 entry.blockIndex << std::endl;*/1283 std::vector<bool>& lastOccur = lastOccurMap[ssaEntry.first];1284 // erase indicator for last SSAEntry1285 lastOccur.pop_back();1286 if (!lastOccur.empty())1287 // mark that parent have children1288 lastOccur.back() = true;1289 1281 } 1290 1282 }
Note: See TracChangeset
for help on using the changeset viewer.