| 241 | } |
| 242 | |
| 243 | std::set<llvm::Instruction *> |
| 244 | RDSpace::getLastMemInsts(Function &F, Instruction &I, |
| 245 | std::set<BasicBlock *> &V) { |
| 246 | |
| 247 | // 1. Get Memory SSA Analyses Result |
| 248 | auto &SSA = FAM.getResult<MemorySSAAnalysis>(F).getMSSA(); |
| 249 | |
| 250 | // 2. Get Memory Access Info about current instruction |
| 251 | auto *MA = SSA.getMemoryAccess(&I); |
| 252 | if (MA && !isa<MemoryUse>(MA)) { |
| 253 | // 2-1. Connect Function -> Instructions that has memory access to write |
| 254 | return getInstructions(*MA); |
| 255 | } |
| 256 | |
| 257 | // 3. Not Found Memory Access. Continue to find (backtrace) |
| 258 | Instruction *Prev = I.getPrevNode(); |
| 259 | if (Prev) { |
| 260 | return getLastMemInsts(F, *Prev, V); |
| 261 | } |
| 262 | assert(I.getParent() && "Unexpected Program State"); |
| 263 | |
| 264 | // 4. Go to Last Instruction of Previous Basic Block (backtrace) |
| 265 | // Happens when previous instruction is an entry instruction of a basic block |
| 266 | BasicBlock &B = *I.getParent(); |
| 267 | if (&B == &F.front()) |
| 268 | return {}; |
| 269 | // NOTE: Sometimes, there is a basic block does not have predecessor. |
| 270 | // Still not understand why such basic blocks exist, anyway. |
| 271 | if (pred_empty(&B)) |
| 272 | return {}; |
| 273 | |
| 274 | std::set<BasicBlock *> NextBs; |
| 275 | // 5. Find previous basic blocks using CFG in LLVM Analyses without Loop |
| 276 | for (auto S = pred_begin(&B), E = pred_end(&B); S != E; ++S) |
| 277 | if (V.find(*S) == V.end()) |
| 278 | NextBs.insert(*S); |
| 279 | |
| 280 | // 6. Sometimes, reaching entry basic block is impossible because |
| 281 | // revisiting basic block is prevented. In this case, go to |
| 282 | // immediate dominator of basic block. |
| 283 | auto &Tree = FAM.getResult<DominatorTreeAnalysis>(F); |
| 284 | auto *DomB = &B; |
| 285 | while (NextBs.size() == 0) { |
| 286 | auto DomNode = Tree.getNode(DomB); |
| 287 | |
| 288 | assert(DomNode && "Unexpected Program State"); |
| 289 | auto IDomNode = DomNode->getIDom(); |
| 290 | |
| 291 | assert(IDomNode && "Unexpected Program State"); |
| 292 | DomB = IDomNode->getBlock(); |
| 293 | |
| 294 | assert(DomB && "Unexpected Program State"); |
| 295 | if (V.find(DomB) == V.end()) |
| 296 | NextBs.insert(DomB); |
| 297 | } |
| 298 | assert(NextBs.size() > 0 && "Unexpected Program State"); |
| 299 | |
| 300 | // 7. back-trace found basic block using CFG and dominator tree |