1 //===--- HexagonCommonGEP.cpp ---------------------------------------------===// 2 // 3 // The LLVM Compiler Infrastructure 4 // 5 // This file is distributed under the University of Illinois Open Source 6 // License. See LICENSE.TXT for details. 7 // 8 //===----------------------------------------------------------------------===// 9 10 #define DEBUG_TYPE "commgep" 11 12 #include "llvm/Pass.h" 13 #include "llvm/ADT/FoldingSet.h" 14 #include "llvm/ADT/STLExtras.h" 15 #include "llvm/Analysis/LoopInfo.h" 16 #include "llvm/Analysis/PostDominators.h" 17 #include "llvm/CodeGen/MachineFunctionAnalysis.h" 18 #include "llvm/IR/Constants.h" 19 #include "llvm/IR/Dominators.h" 20 #include "llvm/IR/Function.h" 21 #include "llvm/IR/Instructions.h" 22 #include "llvm/IR/Verifier.h" 23 #include "llvm/Support/Allocator.h" 24 #include "llvm/Support/CommandLine.h" 25 #include "llvm/Support/Debug.h" 26 #include "llvm/Support/raw_ostream.h" 27 #include "llvm/Transforms/Scalar.h" 28 #include "llvm/Transforms/Utils/Local.h" 29 30 #include <map> 31 #include <set> 32 #include <vector> 33 34 #include "HexagonTargetMachine.h" 35 36 using namespace llvm; 37 38 static cl::opt<bool> OptSpeculate("commgep-speculate", cl::init(true), 39 cl::Hidden, cl::ZeroOrMore); 40 41 static cl::opt<bool> OptEnableInv("commgep-inv", cl::init(true), cl::Hidden, 42 cl::ZeroOrMore); 43 44 static cl::opt<bool> OptEnableConst("commgep-const", cl::init(true), 45 cl::Hidden, cl::ZeroOrMore); 46 47 namespace llvm { 48 void initializeHexagonCommonGEPPass(PassRegistry&); 49 } 50 51 namespace { 52 struct GepNode; 53 typedef std::set<GepNode*> NodeSet; 54 typedef std::map<GepNode*,Value*> NodeToValueMap; 55 typedef std::vector<GepNode*> NodeVect; 56 typedef std::map<GepNode*,NodeVect> NodeChildrenMap; 57 typedef std::set<Use*> UseSet; 58 typedef std::map<GepNode*,UseSet> NodeToUsesMap; 59 60 // Numbering map for gep nodes. Used to keep track of ordering for 61 // gep nodes. 62 struct NodeOrdering { 63 NodeOrdering() : LastNum(0) {} 64 65 void insert(const GepNode *N) { Map.insert(std::make_pair(N, ++LastNum)); } 66 void clear() { Map.clear(); } 67 68 bool operator()(const GepNode *N1, const GepNode *N2) const { 69 auto F1 = Map.find(N1), F2 = Map.find(N2); 70 assert(F1 != Map.end() && F2 != Map.end()); 71 return F1->second < F2->second; 72 } 73 74 private: 75 std::map<const GepNode *, unsigned> Map; 76 unsigned LastNum; 77 }; 78 79 class HexagonCommonGEP : public FunctionPass { 80 public: 81 static char ID; 82 HexagonCommonGEP() : FunctionPass(ID) { 83 initializeHexagonCommonGEPPass(*PassRegistry::getPassRegistry()); 84 } 85 virtual bool runOnFunction(Function &F); 86 virtual const char *getPassName() const { 87 return "Hexagon Common GEP"; 88 } 89 90 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 91 AU.addRequired<DominatorTreeWrapperPass>(); 92 AU.addPreserved<DominatorTreeWrapperPass>(); 93 AU.addRequired<PostDominatorTreeWrapperPass>(); 94 AU.addPreserved<PostDominatorTreeWrapperPass>(); 95 AU.addRequired<LoopInfoWrapperPass>(); 96 AU.addPreserved<LoopInfoWrapperPass>(); 97 FunctionPass::getAnalysisUsage(AU); 98 } 99 100 private: 101 typedef std::map<Value*,GepNode*> ValueToNodeMap; 102 typedef std::vector<Value*> ValueVect; 103 typedef std::map<GepNode*,ValueVect> NodeToValuesMap; 104 105 void getBlockTraversalOrder(BasicBlock *Root, ValueVect &Order); 106 bool isHandledGepForm(GetElementPtrInst *GepI); 107 void processGepInst(GetElementPtrInst *GepI, ValueToNodeMap &NM); 108 void collect(); 109 void common(); 110 111 BasicBlock *recalculatePlacement(GepNode *Node, NodeChildrenMap &NCM, 112 NodeToValueMap &Loc); 113 BasicBlock *recalculatePlacementRec(GepNode *Node, NodeChildrenMap &NCM, 114 NodeToValueMap &Loc); 115 bool isInvariantIn(Value *Val, Loop *L); 116 bool isInvariantIn(GepNode *Node, Loop *L); 117 bool isInMainPath(BasicBlock *B, Loop *L); 118 BasicBlock *adjustForInvariance(GepNode *Node, NodeChildrenMap &NCM, 119 NodeToValueMap &Loc); 120 void separateChainForNode(GepNode *Node, Use *U, NodeToValueMap &Loc); 121 void separateConstantChains(GepNode *Node, NodeChildrenMap &NCM, 122 NodeToValueMap &Loc); 123 void computeNodePlacement(NodeToValueMap &Loc); 124 125 Value *fabricateGEP(NodeVect &NA, BasicBlock::iterator At, 126 BasicBlock *LocB); 127 void getAllUsersForNode(GepNode *Node, ValueVect &Values, 128 NodeChildrenMap &NCM); 129 void materialize(NodeToValueMap &Loc); 130 131 void removeDeadCode(); 132 133 NodeVect Nodes; 134 NodeToUsesMap Uses; 135 NodeOrdering NodeOrder; // Node ordering, for deterministic behavior. 136 SpecificBumpPtrAllocator<GepNode> *Mem; 137 LLVMContext *Ctx; 138 LoopInfo *LI; 139 DominatorTree *DT; 140 PostDominatorTree *PDT; 141 Function *Fn; 142 }; 143 } 144 145 146 char HexagonCommonGEP::ID = 0; 147 INITIALIZE_PASS_BEGIN(HexagonCommonGEP, "hcommgep", "Hexagon Common GEP", 148 false, false) 149 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) 150 INITIALIZE_PASS_DEPENDENCY(PostDominatorTreeWrapperPass) 151 INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass) 152 INITIALIZE_PASS_END(HexagonCommonGEP, "hcommgep", "Hexagon Common GEP", 153 false, false) 154 155 namespace { 156 struct GepNode { 157 enum { 158 None = 0, 159 Root = 0x01, 160 Internal = 0x02, 161 Used = 0x04 162 }; 163 164 uint32_t Flags; 165 union { 166 GepNode *Parent; 167 Value *BaseVal; 168 }; 169 Value *Idx; 170 Type *PTy; // Type of the pointer operand. 171 172 GepNode() : Flags(0), Parent(0), Idx(0), PTy(0) {} 173 GepNode(const GepNode *N) : Flags(N->Flags), Idx(N->Idx), PTy(N->PTy) { 174 if (Flags & Root) 175 BaseVal = N->BaseVal; 176 else 177 Parent = N->Parent; 178 } 179 friend raw_ostream &operator<< (raw_ostream &OS, const GepNode &GN); 180 }; 181 182 183 Type *next_type(Type *Ty, Value *Idx) { 184 // Advance the type. 185 if (!Ty->isStructTy()) { 186 Type *NexTy = cast<SequentialType>(Ty)->getElementType(); 187 return NexTy; 188 } 189 // Otherwise it is a struct type. 190 ConstantInt *CI = dyn_cast<ConstantInt>(Idx); 191 assert(CI && "Struct type with non-constant index"); 192 int64_t i = CI->getValue().getSExtValue(); 193 Type *NextTy = cast<StructType>(Ty)->getElementType(i); 194 return NextTy; 195 } 196 197 198 raw_ostream &operator<< (raw_ostream &OS, const GepNode &GN) { 199 OS << "{ {"; 200 bool Comma = false; 201 if (GN.Flags & GepNode::Root) { 202 OS << "root"; 203 Comma = true; 204 } 205 if (GN.Flags & GepNode::Internal) { 206 if (Comma) 207 OS << ','; 208 OS << "internal"; 209 Comma = true; 210 } 211 if (GN.Flags & GepNode::Used) { 212 if (Comma) 213 OS << ','; 214 OS << "used"; 215 } 216 OS << "} "; 217 if (GN.Flags & GepNode::Root) 218 OS << "BaseVal:" << GN.BaseVal->getName() << '(' << GN.BaseVal << ')'; 219 else 220 OS << "Parent:" << GN.Parent; 221 222 OS << " Idx:"; 223 if (ConstantInt *CI = dyn_cast<ConstantInt>(GN.Idx)) 224 OS << CI->getValue().getSExtValue(); 225 else if (GN.Idx->hasName()) 226 OS << GN.Idx->getName(); 227 else 228 OS << "<anon> =" << *GN.Idx; 229 230 OS << " PTy:"; 231 if (GN.PTy->isStructTy()) { 232 StructType *STy = cast<StructType>(GN.PTy); 233 if (!STy->isLiteral()) 234 OS << GN.PTy->getStructName(); 235 else 236 OS << "<anon-struct>:" << *STy; 237 } 238 else 239 OS << *GN.PTy; 240 OS << " }"; 241 return OS; 242 } 243 244 245 template <typename NodeContainer> 246 void dump_node_container(raw_ostream &OS, const NodeContainer &S) { 247 typedef typename NodeContainer::const_iterator const_iterator; 248 for (const_iterator I = S.begin(), E = S.end(); I != E; ++I) 249 OS << *I << ' ' << **I << '\n'; 250 } 251 252 raw_ostream &operator<< (raw_ostream &OS, 253 const NodeVect &S) LLVM_ATTRIBUTE_UNUSED; 254 raw_ostream &operator<< (raw_ostream &OS, const NodeVect &S) { 255 dump_node_container(OS, S); 256 return OS; 257 } 258 259 260 raw_ostream &operator<< (raw_ostream &OS, 261 const NodeToUsesMap &M) LLVM_ATTRIBUTE_UNUSED; 262 raw_ostream &operator<< (raw_ostream &OS, const NodeToUsesMap &M){ 263 typedef NodeToUsesMap::const_iterator const_iterator; 264 for (const_iterator I = M.begin(), E = M.end(); I != E; ++I) { 265 const UseSet &Us = I->second; 266 OS << I->first << " -> #" << Us.size() << '{'; 267 for (UseSet::const_iterator J = Us.begin(), F = Us.end(); J != F; ++J) { 268 User *R = (*J)->getUser(); 269 if (R->hasName()) 270 OS << ' ' << R->getName(); 271 else 272 OS << " <?>(" << *R << ')'; 273 } 274 OS << " }\n"; 275 } 276 return OS; 277 } 278 279 280 struct in_set { 281 in_set(const NodeSet &S) : NS(S) {} 282 bool operator() (GepNode *N) const { 283 return NS.find(N) != NS.end(); 284 } 285 private: 286 const NodeSet &NS; 287 }; 288 } 289 290 291 inline void *operator new(size_t, SpecificBumpPtrAllocator<GepNode> &A) { 292 return A.Allocate(); 293 } 294 295 296 void HexagonCommonGEP::getBlockTraversalOrder(BasicBlock *Root, 297 ValueVect &Order) { 298 // Compute block ordering for a typical DT-based traversal of the flow 299 // graph: "before visiting a block, all of its dominators must have been 300 // visited". 301 302 Order.push_back(Root); 303 DomTreeNode *DTN = DT->getNode(Root); 304 typedef GraphTraits<DomTreeNode*> GTN; 305 typedef GTN::ChildIteratorType Iter; 306 for (Iter I = GTN::child_begin(DTN), E = GTN::child_end(DTN); I != E; ++I) 307 getBlockTraversalOrder((*I)->getBlock(), Order); 308 } 309 310 311 bool HexagonCommonGEP::isHandledGepForm(GetElementPtrInst *GepI) { 312 // No vector GEPs. 313 if (!GepI->getType()->isPointerTy()) 314 return false; 315 // No GEPs without any indices. (Is this possible?) 316 if (GepI->idx_begin() == GepI->idx_end()) 317 return false; 318 return true; 319 } 320 321 322 void HexagonCommonGEP::processGepInst(GetElementPtrInst *GepI, 323 ValueToNodeMap &NM) { 324 DEBUG(dbgs() << "Visiting GEP: " << *GepI << '\n'); 325 GepNode *N = new (*Mem) GepNode; 326 Value *PtrOp = GepI->getPointerOperand(); 327 ValueToNodeMap::iterator F = NM.find(PtrOp); 328 if (F == NM.end()) { 329 N->BaseVal = PtrOp; 330 N->Flags |= GepNode::Root; 331 } else { 332 // If PtrOp was a GEP instruction, it must have already been processed. 333 // The ValueToNodeMap entry for it is the last gep node in the generated 334 // chain. Link to it here. 335 N->Parent = F->second; 336 } 337 N->PTy = PtrOp->getType(); 338 N->Idx = *GepI->idx_begin(); 339 340 // Collect the list of users of this GEP instruction. Will add it to the 341 // last node created for it. 342 UseSet Us; 343 for (Value::user_iterator UI = GepI->user_begin(), UE = GepI->user_end(); 344 UI != UE; ++UI) { 345 // Check if this gep is used by anything other than other geps that 346 // we will process. 347 if (isa<GetElementPtrInst>(*UI)) { 348 GetElementPtrInst *UserG = cast<GetElementPtrInst>(*UI); 349 if (isHandledGepForm(UserG)) 350 continue; 351 } 352 Us.insert(&UI.getUse()); 353 } 354 Nodes.push_back(N); 355 NodeOrder.insert(N); 356 357 // Skip the first index operand, since we only handle 0. This dereferences 358 // the pointer operand. 359 GepNode *PN = N; 360 Type *PtrTy = cast<PointerType>(PtrOp->getType())->getElementType(); 361 for (User::op_iterator OI = GepI->idx_begin()+1, OE = GepI->idx_end(); 362 OI != OE; ++OI) { 363 Value *Op = *OI; 364 GepNode *Nx = new (*Mem) GepNode; 365 Nx->Parent = PN; // Link Nx to the previous node. 366 Nx->Flags |= GepNode::Internal; 367 Nx->PTy = PtrTy; 368 Nx->Idx = Op; 369 Nodes.push_back(Nx); 370 NodeOrder.insert(Nx); 371 PN = Nx; 372 373 PtrTy = next_type(PtrTy, Op); 374 } 375 376 // After last node has been created, update the use information. 377 if (!Us.empty()) { 378 PN->Flags |= GepNode::Used; 379 Uses[PN].insert(Us.begin(), Us.end()); 380 } 381 382 // Link the last node with the originating GEP instruction. This is to 383 // help with linking chained GEP instructions. 384 NM.insert(std::make_pair(GepI, PN)); 385 } 386 387 388 void HexagonCommonGEP::collect() { 389 // Establish depth-first traversal order of the dominator tree. 390 ValueVect BO; 391 getBlockTraversalOrder(&Fn->front(), BO); 392 393 // The creation of gep nodes requires DT-traversal. When processing a GEP 394 // instruction that uses another GEP instruction as the base pointer, the 395 // gep node for the base pointer should already exist. 396 ValueToNodeMap NM; 397 for (ValueVect::iterator I = BO.begin(), E = BO.end(); I != E; ++I) { 398 BasicBlock *B = cast<BasicBlock>(*I); 399 for (BasicBlock::iterator J = B->begin(), F = B->end(); J != F; ++J) { 400 if (!isa<GetElementPtrInst>(J)) 401 continue; 402 GetElementPtrInst *GepI = cast<GetElementPtrInst>(J); 403 if (isHandledGepForm(GepI)) 404 processGepInst(GepI, NM); 405 } 406 } 407 408 DEBUG(dbgs() << "Gep nodes after initial collection:\n" << Nodes); 409 } 410 411 412 namespace { 413 void invert_find_roots(const NodeVect &Nodes, NodeChildrenMap &NCM, 414 NodeVect &Roots) { 415 typedef NodeVect::const_iterator const_iterator; 416 for (const_iterator I = Nodes.begin(), E = Nodes.end(); I != E; ++I) { 417 GepNode *N = *I; 418 if (N->Flags & GepNode::Root) { 419 Roots.push_back(N); 420 continue; 421 } 422 GepNode *PN = N->Parent; 423 NCM[PN].push_back(N); 424 } 425 } 426 427 void nodes_for_root(GepNode *Root, NodeChildrenMap &NCM, NodeSet &Nodes) { 428 NodeVect Work; 429 Work.push_back(Root); 430 Nodes.insert(Root); 431 432 while (!Work.empty()) { 433 NodeVect::iterator First = Work.begin(); 434 GepNode *N = *First; 435 Work.erase(First); 436 NodeChildrenMap::iterator CF = NCM.find(N); 437 if (CF != NCM.end()) { 438 Work.insert(Work.end(), CF->second.begin(), CF->second.end()); 439 Nodes.insert(CF->second.begin(), CF->second.end()); 440 } 441 } 442 } 443 } 444 445 446 namespace { 447 typedef std::set<NodeSet> NodeSymRel; 448 typedef std::pair<GepNode*,GepNode*> NodePair; 449 typedef std::set<NodePair> NodePairSet; 450 451 const NodeSet *node_class(GepNode *N, NodeSymRel &Rel) { 452 for (NodeSymRel::iterator I = Rel.begin(), E = Rel.end(); I != E; ++I) 453 if (I->count(N)) 454 return &*I; 455 return 0; 456 } 457 458 // Create an ordered pair of GepNode pointers. The pair will be used in 459 // determining equality. The only purpose of the ordering is to eliminate 460 // duplication due to the commutativity of equality/non-equality. 461 NodePair node_pair(GepNode *N1, GepNode *N2) { 462 uintptr_t P1 = uintptr_t(N1), P2 = uintptr_t(N2); 463 if (P1 <= P2) 464 return std::make_pair(N1, N2); 465 return std::make_pair(N2, N1); 466 } 467 468 unsigned node_hash(GepNode *N) { 469 // Include everything except flags and parent. 470 FoldingSetNodeID ID; 471 ID.AddPointer(N->Idx); 472 ID.AddPointer(N->PTy); 473 return ID.ComputeHash(); 474 } 475 476 bool node_eq(GepNode *N1, GepNode *N2, NodePairSet &Eq, NodePairSet &Ne) { 477 // Don't cache the result for nodes with different hashes. The hash 478 // comparison is fast enough. 479 if (node_hash(N1) != node_hash(N2)) 480 return false; 481 482 NodePair NP = node_pair(N1, N2); 483 NodePairSet::iterator FEq = Eq.find(NP); 484 if (FEq != Eq.end()) 485 return true; 486 NodePairSet::iterator FNe = Ne.find(NP); 487 if (FNe != Ne.end()) 488 return false; 489 // Not previously compared. 490 bool Root1 = N1->Flags & GepNode::Root; 491 bool Root2 = N2->Flags & GepNode::Root; 492 NodePair P = node_pair(N1, N2); 493 // If the Root flag has different values, the nodes are different. 494 // If both nodes are root nodes, but their base pointers differ, 495 // they are different. 496 if (Root1 != Root2 || (Root1 && N1->BaseVal != N2->BaseVal)) { 497 Ne.insert(P); 498 return false; 499 } 500 // Here the root flags are identical, and for root nodes the 501 // base pointers are equal, so the root nodes are equal. 502 // For non-root nodes, compare their parent nodes. 503 if (Root1 || node_eq(N1->Parent, N2->Parent, Eq, Ne)) { 504 Eq.insert(P); 505 return true; 506 } 507 return false; 508 } 509 } 510 511 512 void HexagonCommonGEP::common() { 513 // The essence of this commoning is finding gep nodes that are equal. 514 // To do this we need to compare all pairs of nodes. To save time, 515 // first, partition the set of all nodes into sets of potentially equal 516 // nodes, and then compare pairs from within each partition. 517 typedef std::map<unsigned,NodeSet> NodeSetMap; 518 NodeSetMap MaybeEq; 519 520 for (NodeVect::iterator I = Nodes.begin(), E = Nodes.end(); I != E; ++I) { 521 GepNode *N = *I; 522 unsigned H = node_hash(N); 523 MaybeEq[H].insert(N); 524 } 525 526 // Compute the equivalence relation for the gep nodes. Use two caches, 527 // one for equality and the other for non-equality. 528 NodeSymRel EqRel; // Equality relation (as set of equivalence classes). 529 NodePairSet Eq, Ne; // Caches. 530 for (NodeSetMap::iterator I = MaybeEq.begin(), E = MaybeEq.end(); 531 I != E; ++I) { 532 NodeSet &S = I->second; 533 for (NodeSet::iterator NI = S.begin(), NE = S.end(); NI != NE; ++NI) { 534 GepNode *N = *NI; 535 // If node already has a class, then the class must have been created 536 // in a prior iteration of this loop. Since equality is transitive, 537 // nothing more will be added to that class, so skip it. 538 if (node_class(N, EqRel)) 539 continue; 540 541 // Create a new class candidate now. 542 NodeSet C; 543 for (NodeSet::iterator NJ = std::next(NI); NJ != NE; ++NJ) 544 if (node_eq(N, *NJ, Eq, Ne)) 545 C.insert(*NJ); 546 // If Tmp is empty, N would be the only element in it. Don't bother 547 // creating a class for it then. 548 if (!C.empty()) { 549 C.insert(N); // Finalize the set before adding it to the relation. 550 std::pair<NodeSymRel::iterator, bool> Ins = EqRel.insert(C); 551 (void)Ins; 552 assert(Ins.second && "Cannot add a class"); 553 } 554 } 555 } 556 557 DEBUG({ 558 dbgs() << "Gep node equality:\n"; 559 for (NodePairSet::iterator I = Eq.begin(), E = Eq.end(); I != E; ++I) 560 dbgs() << "{ " << I->first << ", " << I->second << " }\n"; 561 562 dbgs() << "Gep equivalence classes:\n"; 563 for (NodeSymRel::iterator I = EqRel.begin(), E = EqRel.end(); I != E; ++I) { 564 dbgs() << '{'; 565 const NodeSet &S = *I; 566 for (NodeSet::const_iterator J = S.begin(), F = S.end(); J != F; ++J) { 567 if (J != S.begin()) 568 dbgs() << ','; 569 dbgs() << ' ' << *J; 570 } 571 dbgs() << " }\n"; 572 } 573 }); 574 575 576 // Create a projection from a NodeSet to the minimal element in it. 577 typedef std::map<const NodeSet*,GepNode*> ProjMap; 578 ProjMap PM; 579 for (NodeSymRel::iterator I = EqRel.begin(), E = EqRel.end(); I != E; ++I) { 580 const NodeSet &S = *I; 581 GepNode *Min = *std::min_element(S.begin(), S.end(), NodeOrder); 582 std::pair<ProjMap::iterator,bool> Ins = PM.insert(std::make_pair(&S, Min)); 583 (void)Ins; 584 assert(Ins.second && "Cannot add minimal element"); 585 586 // Update the min element's flags, and user list. 587 uint32_t Flags = 0; 588 UseSet &MinUs = Uses[Min]; 589 for (NodeSet::iterator J = S.begin(), F = S.end(); J != F; ++J) { 590 GepNode *N = *J; 591 uint32_t NF = N->Flags; 592 // If N is used, append all original values of N to the list of 593 // original values of Min. 594 if (NF & GepNode::Used) 595 MinUs.insert(Uses[N].begin(), Uses[N].end()); 596 Flags |= NF; 597 } 598 if (MinUs.empty()) 599 Uses.erase(Min); 600 601 // The collected flags should include all the flags from the min element. 602 assert((Min->Flags & Flags) == Min->Flags); 603 Min->Flags = Flags; 604 } 605 606 // Commoning: for each non-root gep node, replace "Parent" with the 607 // selected (minimum) node from the corresponding equivalence class. 608 // If a given parent does not have an equivalence class, leave it 609 // unchanged (it means that it's the only element in its class). 610 for (NodeVect::iterator I = Nodes.begin(), E = Nodes.end(); I != E; ++I) { 611 GepNode *N = *I; 612 if (N->Flags & GepNode::Root) 613 continue; 614 const NodeSet *PC = node_class(N->Parent, EqRel); 615 if (!PC) 616 continue; 617 ProjMap::iterator F = PM.find(PC); 618 if (F == PM.end()) 619 continue; 620 // Found a replacement, use it. 621 GepNode *Rep = F->second; 622 N->Parent = Rep; 623 } 624 625 DEBUG(dbgs() << "Gep nodes after commoning:\n" << Nodes); 626 627 // Finally, erase the nodes that are no longer used. 628 NodeSet Erase; 629 for (NodeVect::iterator I = Nodes.begin(), E = Nodes.end(); I != E; ++I) { 630 GepNode *N = *I; 631 const NodeSet *PC = node_class(N, EqRel); 632 if (!PC) 633 continue; 634 ProjMap::iterator F = PM.find(PC); 635 if (F == PM.end()) 636 continue; 637 if (N == F->second) 638 continue; 639 // Node for removal. 640 Erase.insert(*I); 641 } 642 NodeVect::iterator NewE = std::remove_if(Nodes.begin(), Nodes.end(), 643 in_set(Erase)); 644 Nodes.resize(std::distance(Nodes.begin(), NewE)); 645 646 DEBUG(dbgs() << "Gep nodes after post-commoning cleanup:\n" << Nodes); 647 } 648 649 650 namespace { 651 template <typename T> 652 BasicBlock *nearest_common_dominator(DominatorTree *DT, T &Blocks) { 653 DEBUG({ 654 dbgs() << "NCD of {"; 655 for (typename T::iterator I = Blocks.begin(), E = Blocks.end(); 656 I != E; ++I) { 657 if (!*I) 658 continue; 659 BasicBlock *B = cast<BasicBlock>(*I); 660 dbgs() << ' ' << B->getName(); 661 } 662 dbgs() << " }\n"; 663 }); 664 665 // Allow null basic blocks in Blocks. In such cases, return 0. 666 typename T::iterator I = Blocks.begin(), E = Blocks.end(); 667 if (I == E || !*I) 668 return 0; 669 BasicBlock *Dom = cast<BasicBlock>(*I); 670 while (++I != E) { 671 BasicBlock *B = cast_or_null<BasicBlock>(*I); 672 Dom = B ? DT->findNearestCommonDominator(Dom, B) : 0; 673 if (!Dom) 674 return 0; 675 } 676 DEBUG(dbgs() << "computed:" << Dom->getName() << '\n'); 677 return Dom; 678 } 679 680 template <typename T> 681 BasicBlock *nearest_common_dominatee(DominatorTree *DT, T &Blocks) { 682 // If two blocks, A and B, dominate a block C, then A dominates B, 683 // or B dominates A. 684 typename T::iterator I = Blocks.begin(), E = Blocks.end(); 685 // Find the first non-null block. 686 while (I != E && !*I) 687 ++I; 688 if (I == E) 689 return DT->getRoot(); 690 BasicBlock *DomB = cast<BasicBlock>(*I); 691 while (++I != E) { 692 if (!*I) 693 continue; 694 BasicBlock *B = cast<BasicBlock>(*I); 695 if (DT->dominates(B, DomB)) 696 continue; 697 if (!DT->dominates(DomB, B)) 698 return 0; 699 DomB = B; 700 } 701 return DomB; 702 } 703 704 // Find the first use in B of any value from Values. If no such use, 705 // return B->end(). 706 template <typename T> 707 BasicBlock::iterator first_use_of_in_block(T &Values, BasicBlock *B) { 708 BasicBlock::iterator FirstUse = B->end(), BEnd = B->end(); 709 typedef typename T::iterator iterator; 710 for (iterator I = Values.begin(), E = Values.end(); I != E; ++I) { 711 Value *V = *I; 712 // If V is used in a PHI node, the use belongs to the incoming block, 713 // not the block with the PHI node. In the incoming block, the use 714 // would be considered as being at the end of it, so it cannot 715 // influence the position of the first use (which is assumed to be 716 // at the end to start with). 717 if (isa<PHINode>(V)) 718 continue; 719 if (!isa<Instruction>(V)) 720 continue; 721 Instruction *In = cast<Instruction>(V); 722 if (In->getParent() != B) 723 continue; 724 BasicBlock::iterator It = In->getIterator(); 725 if (std::distance(FirstUse, BEnd) < std::distance(It, BEnd)) 726 FirstUse = It; 727 } 728 return FirstUse; 729 } 730 731 bool is_empty(const BasicBlock *B) { 732 return B->empty() || (&*B->begin() == B->getTerminator()); 733 } 734 } 735 736 737 BasicBlock *HexagonCommonGEP::recalculatePlacement(GepNode *Node, 738 NodeChildrenMap &NCM, NodeToValueMap &Loc) { 739 DEBUG(dbgs() << "Loc for node:" << Node << '\n'); 740 // Recalculate the placement for Node, assuming that the locations of 741 // its children in Loc are valid. 742 // Return 0 if there is no valid placement for Node (for example, it 743 // uses an index value that is not available at the location required 744 // to dominate all children, etc.). 745 746 // Find the nearest common dominator for: 747 // - all users, if the node is used, and 748 // - all children. 749 ValueVect Bs; 750 if (Node->Flags & GepNode::Used) { 751 // Append all blocks with uses of the original values to the 752 // block vector Bs. 753 NodeToUsesMap::iterator UF = Uses.find(Node); 754 assert(UF != Uses.end() && "Used node with no use information"); 755 UseSet &Us = UF->second; 756 for (UseSet::iterator I = Us.begin(), E = Us.end(); I != E; ++I) { 757 Use *U = *I; 758 User *R = U->getUser(); 759 if (!isa<Instruction>(R)) 760 continue; 761 BasicBlock *PB = isa<PHINode>(R) 762 ? cast<PHINode>(R)->getIncomingBlock(*U) 763 : cast<Instruction>(R)->getParent(); 764 Bs.push_back(PB); 765 } 766 } 767 // Append the location of each child. 768 NodeChildrenMap::iterator CF = NCM.find(Node); 769 if (CF != NCM.end()) { 770 NodeVect &Cs = CF->second; 771 for (NodeVect::iterator I = Cs.begin(), E = Cs.end(); I != E; ++I) { 772 GepNode *CN = *I; 773 NodeToValueMap::iterator LF = Loc.find(CN); 774 // If the child is only used in GEP instructions (i.e. is not used in 775 // non-GEP instructions), the nearest dominator computed for it may 776 // have been null. In such case it won't have a location available. 777 if (LF == Loc.end()) 778 continue; 779 Bs.push_back(LF->second); 780 } 781 } 782 783 BasicBlock *DomB = nearest_common_dominator(DT, Bs); 784 if (!DomB) 785 return 0; 786 // Check if the index used by Node dominates the computed dominator. 787 Instruction *IdxI = dyn_cast<Instruction>(Node->Idx); 788 if (IdxI && !DT->dominates(IdxI->getParent(), DomB)) 789 return 0; 790 791 // Avoid putting nodes into empty blocks. 792 while (is_empty(DomB)) { 793 DomTreeNode *N = (*DT)[DomB]->getIDom(); 794 if (!N) 795 break; 796 DomB = N->getBlock(); 797 } 798 799 // Otherwise, DomB is fine. Update the location map. 800 Loc[Node] = DomB; 801 return DomB; 802 } 803 804 805 BasicBlock *HexagonCommonGEP::recalculatePlacementRec(GepNode *Node, 806 NodeChildrenMap &NCM, NodeToValueMap &Loc) { 807 DEBUG(dbgs() << "LocRec begin for node:" << Node << '\n'); 808 // Recalculate the placement of Node, after recursively recalculating the 809 // placements of all its children. 810 NodeChildrenMap::iterator CF = NCM.find(Node); 811 if (CF != NCM.end()) { 812 NodeVect &Cs = CF->second; 813 for (NodeVect::iterator I = Cs.begin(), E = Cs.end(); I != E; ++I) 814 recalculatePlacementRec(*I, NCM, Loc); 815 } 816 BasicBlock *LB = recalculatePlacement(Node, NCM, Loc); 817 DEBUG(dbgs() << "LocRec end for node:" << Node << '\n'); 818 return LB; 819 } 820 821 822 bool HexagonCommonGEP::isInvariantIn(Value *Val, Loop *L) { 823 if (isa<Constant>(Val) || isa<Argument>(Val)) 824 return true; 825 Instruction *In = dyn_cast<Instruction>(Val); 826 if (!In) 827 return false; 828 BasicBlock *HdrB = L->getHeader(), *DefB = In->getParent(); 829 return DT->properlyDominates(DefB, HdrB); 830 } 831 832 833 bool HexagonCommonGEP::isInvariantIn(GepNode *Node, Loop *L) { 834 if (Node->Flags & GepNode::Root) 835 if (!isInvariantIn(Node->BaseVal, L)) 836 return false; 837 return isInvariantIn(Node->Idx, L); 838 } 839 840 841 bool HexagonCommonGEP::isInMainPath(BasicBlock *B, Loop *L) { 842 BasicBlock *HB = L->getHeader(); 843 BasicBlock *LB = L->getLoopLatch(); 844 // B must post-dominate the loop header or dominate the loop latch. 845 if (PDT->dominates(B, HB)) 846 return true; 847 if (LB && DT->dominates(B, LB)) 848 return true; 849 return false; 850 } 851 852 853 namespace { 854 BasicBlock *preheader(DominatorTree *DT, Loop *L) { 855 if (BasicBlock *PH = L->getLoopPreheader()) 856 return PH; 857 if (!OptSpeculate) 858 return 0; 859 DomTreeNode *DN = DT->getNode(L->getHeader()); 860 if (!DN) 861 return 0; 862 return DN->getIDom()->getBlock(); 863 } 864 } 865 866 867 BasicBlock *HexagonCommonGEP::adjustForInvariance(GepNode *Node, 868 NodeChildrenMap &NCM, NodeToValueMap &Loc) { 869 // Find the "topmost" location for Node: it must be dominated by both, 870 // its parent (or the BaseVal, if it's a root node), and by the index 871 // value. 872 ValueVect Bs; 873 if (Node->Flags & GepNode::Root) { 874 if (Instruction *PIn = dyn_cast<Instruction>(Node->BaseVal)) 875 Bs.push_back(PIn->getParent()); 876 } else { 877 Bs.push_back(Loc[Node->Parent]); 878 } 879 if (Instruction *IIn = dyn_cast<Instruction>(Node->Idx)) 880 Bs.push_back(IIn->getParent()); 881 BasicBlock *TopB = nearest_common_dominatee(DT, Bs); 882 883 // Traverse the loop nest upwards until we find a loop in which Node 884 // is no longer invariant, or until we get to the upper limit of Node's 885 // placement. The traversal will also stop when a suitable "preheader" 886 // cannot be found for a given loop. The "preheader" may actually be 887 // a regular block outside of the loop (i.e. not guarded), in which case 888 // the Node will be speculated. 889 // For nodes that are not in the main path of the containing loop (i.e. 890 // are not executed in each iteration), do not move them out of the loop. 891 BasicBlock *LocB = cast_or_null<BasicBlock>(Loc[Node]); 892 if (LocB) { 893 Loop *Lp = LI->getLoopFor(LocB); 894 while (Lp) { 895 if (!isInvariantIn(Node, Lp) || !isInMainPath(LocB, Lp)) 896 break; 897 BasicBlock *NewLoc = preheader(DT, Lp); 898 if (!NewLoc || !DT->dominates(TopB, NewLoc)) 899 break; 900 Lp = Lp->getParentLoop(); 901 LocB = NewLoc; 902 } 903 } 904 Loc[Node] = LocB; 905 906 // Recursively compute the locations of all children nodes. 907 NodeChildrenMap::iterator CF = NCM.find(Node); 908 if (CF != NCM.end()) { 909 NodeVect &Cs = CF->second; 910 for (NodeVect::iterator I = Cs.begin(), E = Cs.end(); I != E; ++I) 911 adjustForInvariance(*I, NCM, Loc); 912 } 913 return LocB; 914 } 915 916 917 namespace { 918 struct LocationAsBlock { 919 LocationAsBlock(const NodeToValueMap &L) : Map(L) {} 920 const NodeToValueMap ⤅ 921 }; 922 923 raw_ostream &operator<< (raw_ostream &OS, 924 const LocationAsBlock &Loc) LLVM_ATTRIBUTE_UNUSED ; 925 raw_ostream &operator<< (raw_ostream &OS, const LocationAsBlock &Loc) { 926 for (NodeToValueMap::const_iterator I = Loc.Map.begin(), E = Loc.Map.end(); 927 I != E; ++I) { 928 OS << I->first << " -> "; 929 BasicBlock *B = cast<BasicBlock>(I->second); 930 OS << B->getName() << '(' << B << ')'; 931 OS << '\n'; 932 } 933 return OS; 934 } 935 936 inline bool is_constant(GepNode *N) { 937 return isa<ConstantInt>(N->Idx); 938 } 939 } 940 941 942 void HexagonCommonGEP::separateChainForNode(GepNode *Node, Use *U, 943 NodeToValueMap &Loc) { 944 User *R = U->getUser(); 945 DEBUG(dbgs() << "Separating chain for node (" << Node << ") user: " 946 << *R << '\n'); 947 BasicBlock *PB = cast<Instruction>(R)->getParent(); 948 949 GepNode *N = Node; 950 GepNode *C = 0, *NewNode = 0; 951 while (is_constant(N) && !(N->Flags & GepNode::Root)) { 952 // XXX if (single-use) dont-replicate; 953 GepNode *NewN = new (*Mem) GepNode(N); 954 Nodes.push_back(NewN); 955 Loc[NewN] = PB; 956 957 if (N == Node) 958 NewNode = NewN; 959 NewN->Flags &= ~GepNode::Used; 960 if (C) 961 C->Parent = NewN; 962 C = NewN; 963 N = N->Parent; 964 } 965 if (!NewNode) 966 return; 967 968 // Move over all uses that share the same user as U from Node to NewNode. 969 NodeToUsesMap::iterator UF = Uses.find(Node); 970 assert(UF != Uses.end()); 971 UseSet &Us = UF->second; 972 UseSet NewUs; 973 for (UseSet::iterator I = Us.begin(); I != Us.end(); ) { 974 User *S = (*I)->getUser(); 975 UseSet::iterator Nx = std::next(I); 976 if (S == R) { 977 NewUs.insert(*I); 978 Us.erase(I); 979 } 980 I = Nx; 981 } 982 if (Us.empty()) { 983 Node->Flags &= ~GepNode::Used; 984 Uses.erase(UF); 985 } 986 987 // Should at least have U in NewUs. 988 NewNode->Flags |= GepNode::Used; 989 DEBUG(dbgs() << "new node: " << NewNode << " " << *NewNode << '\n'); 990 assert(!NewUs.empty()); 991 Uses[NewNode] = NewUs; 992 } 993 994 995 void HexagonCommonGEP::separateConstantChains(GepNode *Node, 996 NodeChildrenMap &NCM, NodeToValueMap &Loc) { 997 // First approximation: extract all chains. 998 NodeSet Ns; 999 nodes_for_root(Node, NCM, Ns); 1000 1001 DEBUG(dbgs() << "Separating constant chains for node: " << Node << '\n'); 1002 // Collect all used nodes together with the uses from loads and stores, 1003 // where the GEP node could be folded into the load/store instruction. 1004 NodeToUsesMap FNs; // Foldable nodes. 1005 for (NodeSet::iterator I = Ns.begin(), E = Ns.end(); I != E; ++I) { 1006 GepNode *N = *I; 1007 if (!(N->Flags & GepNode::Used)) 1008 continue; 1009 NodeToUsesMap::iterator UF = Uses.find(N); 1010 assert(UF != Uses.end()); 1011 UseSet &Us = UF->second; 1012 // Loads/stores that use the node N. 1013 UseSet LSs; 1014 for (UseSet::iterator J = Us.begin(), F = Us.end(); J != F; ++J) { 1015 Use *U = *J; 1016 User *R = U->getUser(); 1017 // We're interested in uses that provide the address. It can happen 1018 // that the value may also be provided via GEP, but we won't handle 1019 // those cases here for now. 1020 if (LoadInst *Ld = dyn_cast<LoadInst>(R)) { 1021 unsigned PtrX = LoadInst::getPointerOperandIndex(); 1022 if (&Ld->getOperandUse(PtrX) == U) 1023 LSs.insert(U); 1024 } else if (StoreInst *St = dyn_cast<StoreInst>(R)) { 1025 unsigned PtrX = StoreInst::getPointerOperandIndex(); 1026 if (&St->getOperandUse(PtrX) == U) 1027 LSs.insert(U); 1028 } 1029 } 1030 // Even if the total use count is 1, separating the chain may still be 1031 // beneficial, since the constant chain may be longer than the GEP alone 1032 // would be (e.g. if the parent node has a constant index and also has 1033 // other children). 1034 if (!LSs.empty()) 1035 FNs.insert(std::make_pair(N, LSs)); 1036 } 1037 1038 DEBUG(dbgs() << "Nodes with foldable users:\n" << FNs); 1039 1040 for (NodeToUsesMap::iterator I = FNs.begin(), E = FNs.end(); I != E; ++I) { 1041 GepNode *N = I->first; 1042 UseSet &Us = I->second; 1043 for (UseSet::iterator J = Us.begin(), F = Us.end(); J != F; ++J) 1044 separateChainForNode(N, *J, Loc); 1045 } 1046 } 1047 1048 1049 void HexagonCommonGEP::computeNodePlacement(NodeToValueMap &Loc) { 1050 // Compute the inverse of the Node.Parent links. Also, collect the set 1051 // of root nodes. 1052 NodeChildrenMap NCM; 1053 NodeVect Roots; 1054 invert_find_roots(Nodes, NCM, Roots); 1055 1056 // Compute the initial placement determined by the users' locations, and 1057 // the locations of the child nodes. 1058 for (NodeVect::iterator I = Roots.begin(), E = Roots.end(); I != E; ++I) 1059 recalculatePlacementRec(*I, NCM, Loc); 1060 1061 DEBUG(dbgs() << "Initial node placement:\n" << LocationAsBlock(Loc)); 1062 1063 if (OptEnableInv) { 1064 for (NodeVect::iterator I = Roots.begin(), E = Roots.end(); I != E; ++I) 1065 adjustForInvariance(*I, NCM, Loc); 1066 1067 DEBUG(dbgs() << "Node placement after adjustment for invariance:\n" 1068 << LocationAsBlock(Loc)); 1069 } 1070 if (OptEnableConst) { 1071 for (NodeVect::iterator I = Roots.begin(), E = Roots.end(); I != E; ++I) 1072 separateConstantChains(*I, NCM, Loc); 1073 } 1074 DEBUG(dbgs() << "Node use information:\n" << Uses); 1075 1076 // At the moment, there is no further refinement of the initial placement. 1077 // Such a refinement could include splitting the nodes if they are placed 1078 // too far from some of its users. 1079 1080 DEBUG(dbgs() << "Final node placement:\n" << LocationAsBlock(Loc)); 1081 } 1082 1083 1084 Value *HexagonCommonGEP::fabricateGEP(NodeVect &NA, BasicBlock::iterator At, 1085 BasicBlock *LocB) { 1086 DEBUG(dbgs() << "Fabricating GEP in " << LocB->getName() 1087 << " for nodes:\n" << NA); 1088 unsigned Num = NA.size(); 1089 GepNode *RN = NA[0]; 1090 assert((RN->Flags & GepNode::Root) && "Creating GEP for non-root"); 1091 1092 Value *NewInst = 0; 1093 Value *Input = RN->BaseVal; 1094 Value **IdxList = new Value*[Num+1]; 1095 unsigned nax = 0; 1096 do { 1097 unsigned IdxC = 0; 1098 // If the type of the input of the first node is not a pointer, 1099 // we need to add an artificial i32 0 to the indices (because the 1100 // actual input in the IR will be a pointer). 1101 if (!NA[nax]->PTy->isPointerTy()) { 1102 Type *Int32Ty = Type::getInt32Ty(*Ctx); 1103 IdxList[IdxC++] = ConstantInt::get(Int32Ty, 0); 1104 } 1105 1106 // Keep adding indices from NA until we have to stop and generate 1107 // an "intermediate" GEP. 1108 while (++nax <= Num) { 1109 GepNode *N = NA[nax-1]; 1110 IdxList[IdxC++] = N->Idx; 1111 if (nax < Num) { 1112 // We have to stop, if the expected type of the output of this node 1113 // is not the same as the input type of the next node. 1114 Type *NextTy = next_type(N->PTy, N->Idx); 1115 if (NextTy != NA[nax]->PTy) 1116 break; 1117 } 1118 } 1119 ArrayRef<Value*> A(IdxList, IdxC); 1120 Type *InpTy = Input->getType(); 1121 Type *ElTy = cast<PointerType>(InpTy->getScalarType())->getElementType(); 1122 NewInst = GetElementPtrInst::Create(ElTy, Input, A, "cgep", &*At); 1123 DEBUG(dbgs() << "new GEP: " << *NewInst << '\n'); 1124 Input = NewInst; 1125 } while (nax <= Num); 1126 1127 delete[] IdxList; 1128 return NewInst; 1129 } 1130 1131 1132 void HexagonCommonGEP::getAllUsersForNode(GepNode *Node, ValueVect &Values, 1133 NodeChildrenMap &NCM) { 1134 NodeVect Work; 1135 Work.push_back(Node); 1136 1137 while (!Work.empty()) { 1138 NodeVect::iterator First = Work.begin(); 1139 GepNode *N = *First; 1140 Work.erase(First); 1141 if (N->Flags & GepNode::Used) { 1142 NodeToUsesMap::iterator UF = Uses.find(N); 1143 assert(UF != Uses.end() && "No use information for used node"); 1144 UseSet &Us = UF->second; 1145 for (UseSet::iterator I = Us.begin(), E = Us.end(); I != E; ++I) 1146 Values.push_back((*I)->getUser()); 1147 } 1148 NodeChildrenMap::iterator CF = NCM.find(N); 1149 if (CF != NCM.end()) { 1150 NodeVect &Cs = CF->second; 1151 Work.insert(Work.end(), Cs.begin(), Cs.end()); 1152 } 1153 } 1154 } 1155 1156 1157 void HexagonCommonGEP::materialize(NodeToValueMap &Loc) { 1158 DEBUG(dbgs() << "Nodes before materialization:\n" << Nodes << '\n'); 1159 NodeChildrenMap NCM; 1160 NodeVect Roots; 1161 // Compute the inversion again, since computing placement could alter 1162 // "parent" relation between nodes. 1163 invert_find_roots(Nodes, NCM, Roots); 1164 1165 while (!Roots.empty()) { 1166 NodeVect::iterator First = Roots.begin(); 1167 GepNode *Root = *First, *Last = *First; 1168 Roots.erase(First); 1169 1170 NodeVect NA; // Nodes to assemble. 1171 // Append to NA all child nodes up to (and including) the first child 1172 // that: 1173 // (1) has more than 1 child, or 1174 // (2) is used, or 1175 // (3) has a child located in a different block. 1176 bool LastUsed = false; 1177 unsigned LastCN = 0; 1178 // The location may be null if the computation failed (it can legitimately 1179 // happen for nodes created from dead GEPs). 1180 Value *LocV = Loc[Last]; 1181 if (!LocV) 1182 continue; 1183 BasicBlock *LastB = cast<BasicBlock>(LocV); 1184 do { 1185 NA.push_back(Last); 1186 LastUsed = (Last->Flags & GepNode::Used); 1187 if (LastUsed) 1188 break; 1189 NodeChildrenMap::iterator CF = NCM.find(Last); 1190 LastCN = (CF != NCM.end()) ? CF->second.size() : 0; 1191 if (LastCN != 1) 1192 break; 1193 GepNode *Child = CF->second.front(); 1194 BasicBlock *ChildB = cast_or_null<BasicBlock>(Loc[Child]); 1195 if (ChildB != 0 && LastB != ChildB) 1196 break; 1197 Last = Child; 1198 } while (true); 1199 1200 BasicBlock::iterator InsertAt = LastB->getTerminator()->getIterator(); 1201 if (LastUsed || LastCN > 0) { 1202 ValueVect Urs; 1203 getAllUsersForNode(Root, Urs, NCM); 1204 BasicBlock::iterator FirstUse = first_use_of_in_block(Urs, LastB); 1205 if (FirstUse != LastB->end()) 1206 InsertAt = FirstUse; 1207 } 1208 1209 // Generate a new instruction for NA. 1210 Value *NewInst = fabricateGEP(NA, InsertAt, LastB); 1211 1212 // Convert all the children of Last node into roots, and append them 1213 // to the Roots list. 1214 if (LastCN > 0) { 1215 NodeVect &Cs = NCM[Last]; 1216 for (NodeVect::iterator I = Cs.begin(), E = Cs.end(); I != E; ++I) { 1217 GepNode *CN = *I; 1218 CN->Flags &= ~GepNode::Internal; 1219 CN->Flags |= GepNode::Root; 1220 CN->BaseVal = NewInst; 1221 Roots.push_back(CN); 1222 } 1223 } 1224 1225 // Lastly, if the Last node was used, replace all uses with the new GEP. 1226 // The uses reference the original GEP values. 1227 if (LastUsed) { 1228 NodeToUsesMap::iterator UF = Uses.find(Last); 1229 assert(UF != Uses.end() && "No use information found"); 1230 UseSet &Us = UF->second; 1231 for (UseSet::iterator I = Us.begin(), E = Us.end(); I != E; ++I) { 1232 Use *U = *I; 1233 U->set(NewInst); 1234 } 1235 } 1236 } 1237 } 1238 1239 1240 void HexagonCommonGEP::removeDeadCode() { 1241 ValueVect BO; 1242 BO.push_back(&Fn->front()); 1243 1244 for (unsigned i = 0; i < BO.size(); ++i) { 1245 BasicBlock *B = cast<BasicBlock>(BO[i]); 1246 DomTreeNode *N = DT->getNode(B); 1247 typedef GraphTraits<DomTreeNode*> GTN; 1248 typedef GTN::ChildIteratorType Iter; 1249 for (Iter I = GTN::child_begin(N), E = GTN::child_end(N); I != E; ++I) 1250 BO.push_back((*I)->getBlock()); 1251 } 1252 1253 for (unsigned i = BO.size(); i > 0; --i) { 1254 BasicBlock *B = cast<BasicBlock>(BO[i-1]); 1255 BasicBlock::InstListType &IL = B->getInstList(); 1256 typedef BasicBlock::InstListType::reverse_iterator reverse_iterator; 1257 ValueVect Ins; 1258 for (reverse_iterator I = IL.rbegin(), E = IL.rend(); I != E; ++I) 1259 Ins.push_back(&*I); 1260 for (ValueVect::iterator I = Ins.begin(), E = Ins.end(); I != E; ++I) { 1261 Instruction *In = cast<Instruction>(*I); 1262 if (isInstructionTriviallyDead(In)) 1263 In->eraseFromParent(); 1264 } 1265 } 1266 } 1267 1268 1269 bool HexagonCommonGEP::runOnFunction(Function &F) { 1270 if (skipFunction(F)) 1271 return false; 1272 1273 // For now bail out on C++ exception handling. 1274 for (Function::iterator A = F.begin(), Z = F.end(); A != Z; ++A) 1275 for (BasicBlock::iterator I = A->begin(), E = A->end(); I != E; ++I) 1276 if (isa<InvokeInst>(I) || isa<LandingPadInst>(I)) 1277 return false; 1278 1279 Fn = &F; 1280 DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree(); 1281 PDT = &getAnalysis<PostDominatorTreeWrapperPass>().getPostDomTree(); 1282 LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo(); 1283 Ctx = &F.getContext(); 1284 1285 Nodes.clear(); 1286 Uses.clear(); 1287 NodeOrder.clear(); 1288 1289 SpecificBumpPtrAllocator<GepNode> Allocator; 1290 Mem = &Allocator; 1291 1292 collect(); 1293 common(); 1294 1295 NodeToValueMap Loc; 1296 computeNodePlacement(Loc); 1297 materialize(Loc); 1298 removeDeadCode(); 1299 1300 #ifdef EXPENSIVE_CHECKS 1301 // Run this only when expensive checks are enabled. 1302 verifyFunction(F); 1303 #endif 1304 return true; 1305 } 1306 1307 1308 namespace llvm { 1309 FunctionPass *createHexagonCommonGEP() { 1310 return new HexagonCommonGEP(); 1311 } 1312 } 1313