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