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