1 /*========================== begin_copyright_notice ============================ 2 3 Copyright (C) 2017-2021 Intel Corporation 4 5 SPDX-License-Identifier: MIT 6 7 ============================= end_copyright_notice ===========================*/ 8 9 #ifndef _REGALLOC_H_ 10 #define _REGALLOC_H_ 11 #include "PhyRegUsage.h" 12 #include <memory> 13 #include <vector> 14 15 #include "BitSet.h" 16 #include "LocalRA.h" 17 #include "LinearScanRA.h" 18 19 // 20 // Indirect tracking type 21 // 22 enum G4_IndrTrackType 23 { 24 Track_IndrAddr = 0, // Track indirect addressing 25 Track_MsgGateWay = 1 // Track message gateway 26 }; 27 28 // 29 // Structure for Indirect Accessing Tracking Parameter 30 // 31 struct IndrAccessTrackPara 32 { 33 vISA::G4_BB * bb; // starting bb of the indirect accessing tracking 34 vISA::G4_Operand * ptr; // a0 pointer for indirect accessing 35 vISA::G4_RegVar * addrTaken; // a0 pointed GRF variable 36 INST_LIST_ITER currInst; // starting instruction for the indirect accessing tracking 37 G4_IndrTrackType trackType; // tracking type 38 IndrAccessTrackParaIndrAccessTrackPara39 IndrAccessTrackPara(vISA::G4_BB * startBB, vISA::G4_Operand * pointer, vISA::G4_RegVar * pointedVar, INST_LIST_ITER startInst, 40 G4_IndrTrackType type) 41 : bb(startBB), ptr(pointer), addrTaken(pointedVar), currInst(startInst), trackType(type) {} 42 //void* operator new(size_t sz, Mem_Manager& m) {return m.alloc(sz);} 43 }; 44 45 struct pointInfo { 46 vISA::G4_RegVar* var; 47 unsigned char off; 48 }; 49 50 typedef std::vector<pointInfo> REGVAR_VECTOR; 51 typedef std::vector<vISA::G4_RegVar*> ORG_REGVAR_VECTOR; 52 53 /* 54 * Performs flow-insensitive points-to analysis. 55 * Points-to analysis is performed once at the beginning of RA, 56 * and is used to compute the indirect uses of GRF variables for liveness analysis. 57 * Each address variable in the declare list is associated with a points-to set, 58 * which is a list of GRF RegVars. 59 */ 60 namespace vISA 61 { 62 class PointsToAnalysis 63 { 64 private: 65 const unsigned int numBBs; 66 unsigned int numAddrs; 67 68 // keeps track of the indirect variables used in each BB 69 const std::unique_ptr<REGVAR_VECTOR[]> indirectUses; 70 // vector of points-to set for each address variable 71 std::vector<REGVAR_VECTOR> pointsToSets; 72 // index of an address's points-to set in the pointsToSets vector 73 std::vector<unsigned> addrPointsToSetIndex; 74 // original regvar ptrs 75 ORG_REGVAR_VECTOR regVars; 76 resizePointsToSet(unsigned int newsize)77 void resizePointsToSet(unsigned int newsize) 78 { 79 // Reallocate larger sets, change numAddrs. 80 // Number of basic blocks is assumed to be unchanged. 81 82 pointsToSets.resize(newsize); 83 84 addrPointsToSetIndex.resize(newsize); 85 for (unsigned i = numAddrs; i < newsize; i++) 86 { 87 addrPointsToSetIndex[i] = i; 88 } 89 90 numAddrs = newsize; 91 } 92 addPointsToSetToBB(int bbId,const G4_RegVar * addr)93 void addPointsToSetToBB(int bbId, const G4_RegVar* addr) 94 { 95 MUST_BE_TRUE(addr->getDeclare()->getRegFile() == G4_ADDRESS || addr->getDeclare()->getRegFile() == G4_SCALAR, 96 "expect address variable"); 97 const REGVAR_VECTOR& addrTakens = pointsToSets[addrPointsToSetIndex[addr->getId()]]; 98 for (auto addrTaken : addrTakens) 99 { 100 addIndirectUseToBB(bbId, addrTaken); 101 } 102 } 103 isVar(G4_RegVar * var,pointInfo & pt)104 bool isVar(G4_RegVar* var, pointInfo &pt) 105 { 106 return pt.var == var; 107 } 108 addIndirectUseToBB(unsigned int bbId,pointInfo pt)109 void addIndirectUseToBB(unsigned int bbId, pointInfo pt) 110 { 111 MUST_BE_TRUE(bbId < numBBs, "invalid basic block id"); 112 REGVAR_VECTOR& vec = indirectUses[bbId]; 113 auto it = std::find_if(vec.begin(), vec.end(), 114 [&pt](const pointInfo& element) {return element.var == pt.var && element.off == pt.off; }); 115 116 if (it == vec.end()) 117 { 118 vec.push_back(pt); 119 } 120 } 121 addToPointsToSet(const G4_RegVar * addr,G4_RegVar * var,unsigned char offset)122 void addToPointsToSet(const G4_RegVar* addr, G4_RegVar* var, unsigned char offset) 123 { 124 MUST_BE_TRUE(addr->getDeclare()->getRegFile() == G4_ADDRESS || addr->getDeclare()->getRegFile() == G4_SCALAR, 125 "expect address variable"); 126 MUST_BE_TRUE(addr->getId() < numAddrs, "addr id is not set"); 127 int addrPTIndex = addrPointsToSetIndex[addr->getId()]; 128 REGVAR_VECTOR& vec = pointsToSets[addrPTIndex]; 129 pointInfo pi = { var, offset }; 130 auto it = std::find_if(vec.begin(), vec.end(), 131 [&pi](const pointInfo& element) {return element.var == pi.var && element.off == pi.off; }); 132 133 if (it == vec.end()) 134 { 135 vec.push_back(pi); 136 DEBUG_VERBOSE("Addr " << addr->getId() << " <-- " << var->getDeclare()->getName() << "\n"); 137 } 138 } 139 140 // Merge addr2's points-to set into addr1's 141 // basically we copy the content of addr2's points-to to addr1, 142 // and have addr2 point to addr1's points-to set mergePointsToSet(const G4_RegVar * addr1,const G4_RegVar * addr2)143 void mergePointsToSet(const G4_RegVar* addr1, const G4_RegVar* addr2) 144 { 145 MUST_BE_TRUE(addr1->getDeclare()->getRegFile() == G4_ADDRESS && 146 addr2->getDeclare()->getRegFile() == G4_ADDRESS, 147 "expect address variable"); 148 int addr2PTIndex = addrPointsToSetIndex[addr2->getId()]; 149 REGVAR_VECTOR& vec = pointsToSets[addr2PTIndex]; 150 for (int i = 0; i < (int)vec.size(); i++) 151 { 152 addToPointsToSet(addr1, vec[i].var, vec[i].off); 153 } 154 int addr1PTIndex = addrPointsToSetIndex[addr1->getId()]; 155 addrPointsToSetIndex[addr2->getId()] = addr1PTIndex; 156 DEBUG_VERBOSE("merge Addr " << addr1->getId() << " with Addr " << addr2->getId()); 157 } 158 getIndexOfRegVar(const G4_RegVar * r)159 unsigned int getIndexOfRegVar(const G4_RegVar* r) const 160 { 161 // Given a regvar pointer, return the index it was 162 // found. This function is useful when regvar ids 163 // are reset. 164 165 const auto it = std::find(regVars.begin(), regVars.end(), r); 166 return it == regVars.end() ? UINT_MAX : static_cast<unsigned int>(it - regVars.begin()); 167 } 168 169 public: 170 PointsToAnalysis(const DECLARE_LIST& declares, unsigned numBBs); 171 172 void doPointsToAnalysis(FlowGraph& fg); 173 getIndrUseVectorForBB(unsigned int bbId)174 const REGVAR_VECTOR& getIndrUseVectorForBB(unsigned int bbId) const 175 { 176 MUST_BE_TRUE(bbId < numBBs, "invalid basic block id"); 177 return indirectUses[bbId]; 178 } 179 180 // Following methods were added to support address taken spill/fill 181 // Since ids of addr regvars will be reset, we fall back to using 182 // the regvar ptr insertAndMergeFilledAddr(const G4_RegVar * addr1,G4_RegVar * addr2)183 void insertAndMergeFilledAddr(const G4_RegVar* addr1, G4_RegVar* addr2) 184 { 185 unsigned int oldid = addr2->getId(); 186 addr2->setId(numAddrs); 187 MUST_BE_TRUE(regVars.size() == numAddrs, "Inconsistency found between size of regvars and number of addr vars"); 188 189 if (addr2->getId() >= numAddrs) 190 resizePointsToSet(numAddrs + 1); 191 192 regVars.push_back(addr2); 193 194 mergePointsToSet(addr1, addr2); 195 addr2->setId(oldid); 196 } 197 getAllInPointsTo(const G4_RegVar * addr)198 const REGVAR_VECTOR* getAllInPointsTo(const G4_RegVar* addr) const 199 { 200 MUST_BE_TRUE(addr->getDeclare()->getRegFile() == G4_ADDRESS || addr->getDeclare()->getRegFile() == G4_SCALAR, 201 "expect address variable"); 202 unsigned int id = getIndexOfRegVar(addr); 203 204 if (id == UINT_MAX) 205 return nullptr; 206 207 const REGVAR_VECTOR* vec = &pointsToSets[addrPointsToSetIndex[id]]; 208 209 return vec; 210 } 211 getAllInPointsToOrIndrUse(const G4_Operand * opnd,const G4_BB * bb)212 const REGVAR_VECTOR& getAllInPointsToOrIndrUse(const G4_Operand* opnd, const G4_BB* bb) const 213 { 214 const REGVAR_VECTOR* pointsToSet = getAllInPointsTo(opnd->getBase()->asRegVar()); 215 if (pointsToSet != nullptr) 216 return *pointsToSet; 217 // this can happen if the address is coming from addr spill 218 // ToDo: we can avoid this by linking the spilled addr with its new temp addr 219 return getIndrUseVectorForBB(bb->getId()); 220 } 221 getPointsTo(const G4_RegVar * addr,int idx)222 G4_RegVar* getPointsTo(const G4_RegVar* addr, int idx) const 223 { 224 MUST_BE_TRUE(addr->getDeclare()->getRegFile() == G4_ADDRESS || addr->getDeclare()->getRegFile() == G4_SCALAR, 225 "expect address variable"); 226 unsigned int id = getIndexOfRegVar(addr); 227 228 if (id == UINT_MAX) 229 return NULL; 230 231 const REGVAR_VECTOR& vec = pointsToSets[addrPointsToSetIndex[id]]; 232 233 if (idx < (int)vec.size()) 234 return vec[idx].var; 235 else 236 return NULL; 237 } 238 getPointsTo(const G4_RegVar * addr,int idx,unsigned char & offset)239 G4_RegVar* getPointsTo(const G4_RegVar* addr, int idx, unsigned char& offset) const 240 { 241 MUST_BE_TRUE(addr->getDeclare()->getRegFile() == G4_ADDRESS || addr->getDeclare()->getRegFile() == G4_SCALAR, 242 "expect address variable"); 243 unsigned int id = getIndexOfRegVar(addr); 244 245 if (id == UINT_MAX) 246 return NULL; 247 int addrPTIndex = addrPointsToSetIndex[id]; 248 249 const REGVAR_VECTOR& vec = pointsToSets[addrPTIndex]; 250 251 if (idx < (int)vec.size()) 252 { 253 offset = vec[idx].off; 254 return vec[idx].var; 255 } 256 else 257 return NULL; 258 } 259 isPresentInPointsTo(const G4_RegVar * addr,const G4_RegVar * var)260 bool isPresentInPointsTo(const G4_RegVar* addr, const G4_RegVar* var) const 261 { 262 MUST_BE_TRUE(addr->getDeclare()->getRegFile() == G4_ADDRESS || addr->getDeclare()->getRegFile() == G4_SCALAR, 263 "expect address variable"); 264 unsigned int id = getIndexOfRegVar(addr); 265 266 if (id == UINT_MAX) 267 return false; 268 269 const REGVAR_VECTOR& vec = pointsToSets[addrPointsToSetIndex[id]]; 270 for (const pointInfo pointsTo : vec) 271 { 272 if (pointsTo.var->getId() == var->getId()) 273 { 274 return true; 275 } 276 } 277 278 return false; 279 } 280 addFillToPointsTo(unsigned int bbid,G4_RegVar * addr,G4_RegVar * newvar)281 void addFillToPointsTo(unsigned int bbid, G4_RegVar* addr, G4_RegVar* newvar) 282 { 283 // Adds to points to as well as indirect use in basic block 284 MUST_BE_TRUE(addr->getDeclare()->getRegFile() == G4_ADDRESS || addr->getDeclare()->getRegFile() == G4_SCALAR, 285 "expect address variable"); 286 unsigned int id = getIndexOfRegVar(addr); 287 288 if (id == UINT_MAX) 289 { 290 MUST_BE_TRUE(false, "Could not find addr in points to set"); 291 } 292 293 REGVAR_VECTOR& vec = pointsToSets[addrPointsToSetIndex[id]]; 294 pointInfo pt = { newvar, 0 }; 295 vec.push_back(pt); 296 297 addIndirectUseToBB(bbid, pt); 298 } 299 removeFromPointsTo(G4_RegVar * addr,G4_RegVar * vartoremove)300 void removeFromPointsTo(G4_RegVar* addr, G4_RegVar* vartoremove) 301 { 302 MUST_BE_TRUE(addr->getDeclare()->getRegFile() == G4_ADDRESS || addr->getDeclare()->getRegFile() == G4_SCALAR, 303 "expect address variable"); 304 unsigned int id = getIndexOfRegVar(addr); 305 306 if (id == UINT_MAX) 307 { 308 MUST_BE_TRUE(false, "Could not find addr in points to set"); 309 } 310 311 REGVAR_VECTOR& vec = pointsToSets[addrPointsToSetIndex[id]]; 312 bool removed = false; 313 314 for (REGVAR_VECTOR::iterator it = vec.begin(); 315 it != vec.end(); 316 it++) 317 { 318 pointInfo cur = (*it); 319 320 if (cur.var->getId() == vartoremove->getId()) 321 { 322 vec.erase(it); 323 removed = true; 324 break; 325 } 326 } 327 328 MUST_BE_TRUE(removed == true, "Could not find spilled ref from points to"); 329 330 // If an addr taken live-range is spilled then any basic block that has 331 // an indirect use of it will no longer have it because we would have 332 // inserted addr taken spill/fill code. So remove any indirect uses of 333 // the var from all basic blocks. Currently this set is used when 334 // constructing liveness sets before RA. 335 for (unsigned int i = 0; i < numBBs; i++) 336 { 337 REGVAR_VECTOR& vec = indirectUses[i]; 338 339 for (REGVAR_VECTOR::iterator it = vec.begin(); 340 it != vec.end(); 341 it++) 342 { 343 pointInfo cur = (*it); 344 345 if (cur.var->getId() == vartoremove->getId()) 346 { 347 vec.erase(it); 348 break; 349 } 350 } 351 } 352 } 353 }; 354 355 struct VarRange 356 { 357 unsigned int leftBound; 358 unsigned int rightBound; 359 }; 360 361 typedef std::vector<VarRange* > VAR_RANGE_LIST; 362 typedef std::vector<VarRange* >::iterator VAR_RANGE_LIST_ITER; 363 typedef std::vector<VarRange* >::reverse_iterator VAR_RANGE_LIST_REV_ITER; 364 365 struct VarRangeListPackage 366 { 367 bool usedInSend; 368 unsigned char rangeUnit; 369 VAR_RANGE_LIST list; 370 }; 371 372 class LivenessAnalysis 373 { 374 unsigned numVarId = 0; // the var count 375 unsigned numGlobalVarId = 0; // the global var count 376 unsigned numSplitVar = 0; // the split var count 377 unsigned numSplitStartID = 0; // the split var count 378 unsigned numUnassignedVarId = 0; // the unassigned var count 379 unsigned numAddrId = 0; // the addr count 380 unsigned numBBId = 0; // the block count 381 unsigned numFnId = 0; // the function count 382 const unsigned char selectedRF = 0; // the selected reg file kind for performing liveness 383 const PointsToAnalysis& pointsToAnalysis; 384 std::unordered_map<G4_Declare*, BitSet> neverDefinedRows; 385 386 vISA::Mem_Manager m; 387 388 void computeGenKillandPseudoKill(G4_BB* bb, 389 BitSet& def_out, 390 BitSet& use_in, 391 BitSet& use_gen, 392 BitSet& use_kill) const; 393 394 bool contextFreeUseAnalyze(G4_BB* bb, bool isChanged); 395 bool contextFreeDefAnalyze(G4_BB* bb, bool isChanged); 396 397 bool livenessCandidate(const G4_Declare* decl, bool verifyRA) const; 398 399 void dump_bb_vector(char* vname, std::vector<BitSet>& vec); 400 void dump_fn_vector(char* vname, std::vector<FuncInfo*>& fns, std::vector<BitSet>& vec); 401 402 void updateKillSetForDcl(G4_Declare* dcl, BitSet* curBBGen, BitSet* curBBKill, G4_BB* curBB, BitSet* entryBBGen, BitSet* entryBBKill, 403 G4_BB* entryBB, unsigned scopeID); 404 void footprintDst(const G4_BB* bb, const G4_INST* i, G4_Operand* opnd, BitSet* dstfootprint) const; 405 static void footprintSrc(const G4_INST* i, G4_Operand *opnd, BitSet* srcfootprint); 406 void detectNeverDefinedVarRows(); 407 408 public: 409 GlobalRA& gra; 410 std::vector<G4_RegVar*> vars; 411 BitSet addr_taken; 412 FlowGraph& fg; 413 414 // 415 // Bitsets used for data flow. 416 // 417 std::vector<BitSet> def_in; 418 std::vector<BitSet> def_out; 419 std::vector<BitSet> use_in; 420 std::vector<BitSet> use_out; 421 std::vector<BitSet> use_gen; 422 std::vector<BitSet> use_kill; 423 std::vector<BitSet> indr_use; 424 std::unordered_map<FuncInfo*, BitSet> subroutineMaydef; 425 426 bool isLocalVar(G4_Declare* decl) const; 427 bool setGlobalVarIDs(bool verifyRA, bool areAllPhyRegAssigned); 428 bool setLocalVarIDs(bool verifyRA, bool areAllPhyRegAssigned); 429 bool setVarIDs(bool verifyRA, bool areAllPhyRegAssigned); 430 LivenessAnalysis(GlobalRA& gra, unsigned char kind, bool verifyRA = false, bool forceRun = false); 431 ~LivenessAnalysis(); 432 void computeLiveness(); 433 bool isLiveAtEntry(const G4_BB* bb, unsigned var_id) const; 434 bool isUseThrough(const G4_BB* bb, unsigned var_id) const; 435 bool isDefThrough(const G4_BB* bb, unsigned var_id) const; 436 bool isLiveAtExit(const G4_BB* bb, unsigned var_id) const; 437 bool isUseOut(const G4_BB* bb, unsigned var_id) const; 438 bool isUseIn(const G4_BB* bb, unsigned var_id) const; isAddressSensitive(unsigned num)439 bool isAddressSensitive (unsigned num) const // returns true if the variable is address taken and also has indirect access 440 { 441 return addr_taken.isSet(num); 442 } livenessClass(G4_RegFileKind regKind)443 bool livenessClass(G4_RegFileKind regKind) const 444 { 445 return (selectedRF & regKind) != 0; 446 } getNumSelectedVar()447 unsigned getNumSelectedVar() const {return numVarId;} getNumSelectedGlobalVar()448 unsigned getNumSelectedGlobalVar() const { return numGlobalVarId; } getNumSplitVar()449 unsigned getNumSplitVar() const {return numSplitVar;} getNumSplitStartID()450 unsigned getNumSplitStartID() const {return numSplitStartID;} getNumUnassignedVar()451 unsigned getNumUnassignedVar() const {return numUnassignedVarId;} 452 void dump() const; 453 void dumpBB(G4_BB* bb) const; 454 void dumpLive(BitSet& live) const; 455 void dumpGlobalVarNum() const; 456 bool isEmptyLiveness() const; 457 bool writeWholeRegion(const G4_BB* bb, const G4_INST* prd, G4_DstRegRegion* dst, const Options *opt) const; 458 459 bool writeWholeRegion(const G4_BB* bb, const G4_INST* prd, const G4_VarBase* flagReg) const; 460 461 void performScoping(BitSet* curBBGen, BitSet* curBBKill, G4_BB* curBB, BitSet* entryBBGen, BitSet* entryBBKill, G4_BB* entryBB); 462 463 void hierarchicalIPA(const BitSet& kernelInput, const BitSet& kernelOutput); 464 void useAnalysis(FuncInfo* subroutine); 465 void useAnalysisWithArgRetVal(FuncInfo* subroutine, 466 const std::unordered_map<FuncInfo*, BitSet>& args, const std::unordered_map<FuncInfo*, BitSet>& retVal); 467 void defAnalysis(FuncInfo* subroutine); 468 void maydefAnalysis(); 469 getPointsToAnalysis()470 const PointsToAnalysis& getPointsToAnalysis() const { return pointsToAnalysis; } 471 performIPA()472 bool performIPA() const 473 { 474 return fg.builder->getOption(vISA_IPA) && livenessClass(G4_GRF) && 475 fg.getNumCalls() > 0; 476 } 477 }; 478 479 // 480 // entry point of register allocation 481 // 482 class IR_Builder; // forward declaration 483 } 484 int regAlloc(vISA::IR_Builder& builder, vISA::PhyRegPool& regPool, vISA::G4_Kernel& kernel); 485 486 #endif 487