Lines Matching +full:dt +full:- +full:node
1 //===- HexagonCommonGEP.cpp -----------------------------------------------===//
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7 //===----------------------------------------------------------------------===//
54 static cl::opt<bool> OptSpeculate("commgep-speculate", cl::init(true),
57 static cl::opt<bool> OptEnableInv("commgep-inv", cl::init(true), cl::Hidden);
59 static cl::opt<bool> OptEnableConst("commgep-const", cl::init(true),
89 return F1->second < F2->second; in operator ()()
129 BasicBlock *recalculatePlacement(GepNode *Node, NodeChildrenMap &NCM,
131 BasicBlock *recalculatePlacementRec(GepNode *Node, NodeChildrenMap &NCM,
134 bool isInvariantIn(GepNode *Node, Loop *L);
136 BasicBlock *adjustForInvariance(GepNode *Node, NodeChildrenMap &NCM,
138 void separateChainForNode(GepNode *Node, Use *U, NodeToValueMap &Loc);
139 void separateConstantChains(GepNode *Node, NodeChildrenMap &NCM,
145 void getAllUsersForNode(GepNode *Node, ValueVect &Values,
153 NodeOrdering NodeOrder; // Node ordering, for deterministic behavior.
157 DominatorTree *DT; member in __anon9d81f58e0111::HexagonCommonGEP
188 // a composite type (at least not in the sense of having sub-types).
194 // will be stored in the PTy member, while the fact that the node
203 Type *PTy = nullptr; // Type indexed by this node. For pointer nodes
208 GepNode(const GepNode *N) : Flags(N->Flags), Idx(N->Idx), PTy(N->PTy) { in GepNode()
210 BaseVal = N->BaseVal; in GepNode()
212 Parent = N->Parent; in GepNode()
248 OS << "BaseVal:" << GN.BaseVal->getName() << '(' << GN.BaseVal << ')'; in operator <<()
254 OS << CI->getValue().getSExtValue(); in operator <<()
255 else if (GN.Idx->hasName()) in operator <<()
256 OS << GN.Idx->getName(); in operator <<()
261 if (GN.PTy->isStructTy()) { in operator <<()
263 if (!STy->isLiteral()) in operator <<()
264 OS << GN.PTy->getStructName(); in operator <<()
266 OS << "<anon-struct>:" << *STy; in operator <<()
294 OS << I.first << " -> #" << Us.size() << '{'; in operator <<()
296 User *R = U->getUser(); in operator <<()
297 if (R->hasName()) in operator <<()
298 OS << ' ' << R->getName(); in operator <<()
326 // Compute block ordering for a typical DT-based traversal of the flow in getBlockTraversalOrder()
331 for (auto *DTN : children<DomTreeNode*>(DT->getNode(Root))) in getBlockTraversalOrder()
332 getBlockTraversalOrder(DTN->getBlock(), Order); in getBlockTraversalOrder()
337 if (!GepI->getType()->isPointerTy()) in isHandledGepForm()
340 if (GepI->idx_begin() == GepI->idx_end()) in isHandledGepForm()
349 Value *PtrOp = GepI->getPointerOperand(); in processGepInst()
350 uint32_t InBounds = GepI->isInBounds() ? GepNode::InBounds : 0; in processGepInst()
353 N->BaseVal = PtrOp; in processGepInst()
354 N->Flags |= GepNode::Root | InBounds; in processGepInst()
357 // The ValueToNodeMap entry for it is the last gep node in the generated in processGepInst()
359 N->Parent = F->second; in processGepInst()
361 N->PTy = GepI->getSourceElementType(); in processGepInst()
362 N->Flags |= GepNode::Pointer; in processGepInst()
363 N->Idx = *GepI->idx_begin(); in processGepInst()
366 // last node created for it. in processGepInst()
368 for (Value::user_iterator UI = GepI->user_begin(), UE = GepI->user_end(); in processGepInst()
385 Type *PtrTy = GepI->getSourceElementType(); in processGepInst()
386 for (Use &U : llvm::drop_begin(GepI->indices())) { in processGepInst()
389 Nx->Parent = PN; // Link Nx to the previous node. in processGepInst()
390 Nx->Flags |= GepNode::Internal | InBounds; in processGepInst()
391 Nx->PTy = PtrTy; in processGepInst()
392 Nx->Idx = Op; in processGepInst()
400 // After last node has been created, update the use information. in processGepInst()
402 PN->Flags |= GepNode::Used; in processGepInst()
406 // Link the last node with the originating GEP instruction. This is to in processGepInst()
412 // Establish depth-first traversal order of the dominator tree. in collect()
414 getBlockTraversalOrder(&Fn->front(), BO); in collect()
416 // The creation of gep nodes requires DT-traversal. When processing a GEP in collect()
418 // gep node for the base pointer should already exist. in collect()
434 if (N->Flags & GepNode::Root) { in invert_find_roots()
438 GepNode *PN = N->Parent; in invert_find_roots()
455 llvm::append_range(Work, CF->second); in nodes_for_root()
456 Nodes.insert(CF->second.begin(), CF->second.end()); in nodes_for_root()
478 // duplication due to the commutativity of equality/non-equality.
490 ID.AddPointer(N->Idx); in node_hash()
491 ID.AddPointer(N->PTy); in node_hash()
510 bool Root1 = N1->Flags & GepNode::Root; in node_eq()
512 bool Different = (N1->Flags & CmpFlags) != (N2->Flags & CmpFlags); in node_eq()
518 if (Different || (Root1 && N1->BaseVal != N2->BaseVal)) { in node_eq()
524 // For non-root nodes, compare their parent nodes. in node_eq()
525 if (Root1 || node_eq(N1->Parent, N2->Parent, Eq, Ne)) { in node_eq()
546 // one for equality and the other for non-equality. in common()
553 // If node already has a class, then the class must have been created in common()
576 dbgs() << "Gep node equality:\n"; in common()
578 dbgs() << "{ " << I->first << ", " << I->second << " }\n"; in common()
605 uint32_t NF = N->Flags; in common()
616 assert((Min->Flags & Flags) == Min->Flags); in common()
617 Min->Flags = Flags; in common()
620 // Commoning: for each non-root gep node, replace "Parent" with the in common()
621 // selected (minimum) node from the corresponding equivalence class. in common()
625 if (N->Flags & GepNode::Root) in common()
627 const NodeSet *PC = node_class(N->Parent, EqRel); in common()
634 GepNode *Rep = F->second; in common()
635 N->Parent = Rep; in common()
649 if (N == F->second) in common()
651 // Node for removal. in common()
656 LLVM_DEBUG(dbgs() << "Gep nodes after post-commoning cleanup:\n" << Nodes); in common()
660 static BasicBlock *nearest_common_dominator(DominatorTree *DT, T &Blocks) { in nearest_common_dominator() argument
668 dbgs() << ' ' << B->getName(); in nearest_common_dominator()
680 Dom = B ? DT->findNearestCommonDominator(Dom, B) : nullptr; in nearest_common_dominator()
684 LLVM_DEBUG(dbgs() << "computed:" << Dom->getName() << '\n'); in nearest_common_dominator()
689 static BasicBlock *nearest_common_dominatee(DominatorTree *DT, T &Blocks) { in nearest_common_dominatee() argument
693 // Find the first non-null block. in nearest_common_dominatee()
697 return DT->getRoot(); in nearest_common_dominatee()
703 if (DT->dominates(B, DomB)) in nearest_common_dominatee()
705 if (!DT->dominates(DomB, B)) in nearest_common_dominatee()
713 // return B->end().
716 BasicBlock::iterator FirstUse = B->end(), BEnd = B->end(); in first_use_of_in_block()
722 // If V is used in a PHI node, the use belongs to the incoming block, in first_use_of_in_block()
723 // not the block with the PHI node. In the incoming block, the use in first_use_of_in_block()
732 if (In->getParent() != B) in first_use_of_in_block()
734 BasicBlock::iterator It = In->getIterator(); in first_use_of_in_block()
742 return B->empty() || (&*B->begin() == B->getTerminator()); in is_empty()
745 BasicBlock *HexagonCommonGEP::recalculatePlacement(GepNode *Node, in recalculatePlacement() argument
747 LLVM_DEBUG(dbgs() << "Loc for node:" << Node << '\n'); in recalculatePlacement()
748 // Recalculate the placement for Node, assuming that the locations of in recalculatePlacement()
750 // Return nullptr if there is no valid placement for Node (for example, it in recalculatePlacement()
755 // - all users, if the node is used, and in recalculatePlacement()
756 // - all children. in recalculatePlacement()
758 if (Node->Flags & GepNode::Used) { in recalculatePlacement()
761 NodeToUsesMap::iterator UF = Uses.find(Node); in recalculatePlacement()
762 assert(UF != Uses.end() && "Used node with no use information"); in recalculatePlacement()
763 UseSet &Us = UF->second; in recalculatePlacement()
765 User *R = U->getUser(); in recalculatePlacement()
769 ? cast<PHINode>(R)->getIncomingBlock(*U) in recalculatePlacement()
770 : cast<Instruction>(R)->getParent(); in recalculatePlacement()
775 NodeChildrenMap::iterator CF = NCM.find(Node); in recalculatePlacement()
777 NodeVect &Cs = CF->second; in recalculatePlacement()
781 // non-GEP instructions), the nearest dominator computed for it may in recalculatePlacement()
785 Bs.push_back(LF->second); in recalculatePlacement()
789 BasicBlock *DomB = nearest_common_dominator(DT, Bs); in recalculatePlacement()
792 // Check if the index used by Node dominates the computed dominator. in recalculatePlacement()
793 Instruction *IdxI = dyn_cast<Instruction>(Node->Idx); in recalculatePlacement()
794 if (IdxI && !DT->dominates(IdxI->getParent(), DomB)) in recalculatePlacement()
799 DomTreeNode *N = (*DT)[DomB]->getIDom(); in recalculatePlacement()
802 DomB = N->getBlock(); in recalculatePlacement()
806 Loc[Node] = DomB; in recalculatePlacement()
810 BasicBlock *HexagonCommonGEP::recalculatePlacementRec(GepNode *Node, in recalculatePlacementRec() argument
812 LLVM_DEBUG(dbgs() << "LocRec begin for node:" << Node << '\n'); in recalculatePlacementRec()
813 // Recalculate the placement of Node, after recursively recalculating the in recalculatePlacementRec()
815 NodeChildrenMap::iterator CF = NCM.find(Node); in recalculatePlacementRec()
817 NodeVect &Cs = CF->second; in recalculatePlacementRec()
821 BasicBlock *LB = recalculatePlacement(Node, NCM, Loc); in recalculatePlacementRec()
822 LLVM_DEBUG(dbgs() << "LocRec end for node:" << Node << '\n'); in recalculatePlacementRec()
832 BasicBlock *HdrB = L->getHeader(), *DefB = In->getParent(); in isInvariantIn()
833 return DT->properlyDominates(DefB, HdrB); in isInvariantIn()
836 bool HexagonCommonGEP::isInvariantIn(GepNode *Node, Loop *L) { in isInvariantIn() argument
837 if (Node->Flags & GepNode::Root) in isInvariantIn()
838 if (!isInvariantIn(Node->BaseVal, L)) in isInvariantIn()
840 return isInvariantIn(Node->Idx, L); in isInvariantIn()
844 BasicBlock *HB = L->getHeader(); in isInMainPath()
845 BasicBlock *LB = L->getLoopLatch(); in isInMainPath()
846 // B must post-dominate the loop header or dominate the loop latch. in isInMainPath()
847 if (PDT->dominates(B, HB)) in isInMainPath()
849 if (LB && DT->dominates(B, LB)) in isInMainPath()
854 static BasicBlock *preheader(DominatorTree *DT, Loop *L) { in preheader() argument
855 if (BasicBlock *PH = L->getLoopPreheader()) in preheader()
859 DomTreeNode *DN = DT->getNode(L->getHeader()); in preheader()
862 return DN->getIDom()->getBlock(); in preheader()
865 BasicBlock *HexagonCommonGEP::adjustForInvariance(GepNode *Node, in adjustForInvariance() argument
867 // Find the "topmost" location for Node: it must be dominated by both, in adjustForInvariance()
868 // its parent (or the BaseVal, if it's a root node), and by the index in adjustForInvariance()
871 if (Node->Flags & GepNode::Root) { in adjustForInvariance()
872 if (Instruction *PIn = dyn_cast<Instruction>(Node->BaseVal)) in adjustForInvariance()
873 Bs.push_back(PIn->getParent()); in adjustForInvariance()
875 Bs.push_back(Loc[Node->Parent]); in adjustForInvariance()
877 if (Instruction *IIn = dyn_cast<Instruction>(Node->Idx)) in adjustForInvariance()
878 Bs.push_back(IIn->getParent()); in adjustForInvariance()
879 BasicBlock *TopB = nearest_common_dominatee(DT, Bs); in adjustForInvariance()
881 // Traverse the loop nest upwards until we find a loop in which Node in adjustForInvariance()
882 // is no longer invariant, or until we get to the upper limit of Node's in adjustForInvariance()
886 // the Node will be speculated. in adjustForInvariance()
889 BasicBlock *LocB = cast_or_null<BasicBlock>(Loc[Node]); in adjustForInvariance()
891 Loop *Lp = LI->getLoopFor(LocB); in adjustForInvariance()
893 if (!isInvariantIn(Node, Lp) || !isInMainPath(LocB, Lp)) in adjustForInvariance()
895 BasicBlock *NewLoc = preheader(DT, Lp); in adjustForInvariance()
896 if (!NewLoc || !DT->dominates(TopB, NewLoc)) in adjustForInvariance()
898 Lp = Lp->getParentLoop(); in adjustForInvariance()
902 Loc[Node] = LocB; in adjustForInvariance()
905 NodeChildrenMap::iterator CF = NCM.find(Node); in adjustForInvariance()
907 NodeVect &Cs = CF->second; in adjustForInvariance()
926 OS << I.first << " -> "; in operator <<()
928 OS << B->getName() << '(' << B << ')'; in operator <<()
930 OS << "<null-block>"; in operator <<()
937 return isa<ConstantInt>(N->Idx); in is_constant()
942 void HexagonCommonGEP::separateChainForNode(GepNode *Node, Use *U, in separateChainForNode() argument
944 User *R = U->getUser(); in separateChainForNode()
945 LLVM_DEBUG(dbgs() << "Separating chain for node (" << Node << ") user: " << *R in separateChainForNode()
947 BasicBlock *PB = cast<Instruction>(R)->getParent(); in separateChainForNode()
949 GepNode *N = Node; in separateChainForNode()
951 while (is_constant(N) && !(N->Flags & GepNode::Root)) { in separateChainForNode()
952 // XXX if (single-use) dont-replicate; in separateChainForNode()
957 if (N == Node) in separateChainForNode()
959 NewN->Flags &= ~GepNode::Used; in separateChainForNode()
961 C->Parent = NewN; in separateChainForNode()
963 N = N->Parent; in separateChainForNode()
968 // Move over all uses that share the same user as U from Node to NewNode. in separateChainForNode()
969 NodeToUsesMap::iterator UF = Uses.find(Node); in separateChainForNode()
971 UseSet &Us = UF->second; in separateChainForNode()
974 if (U->getUser() == R) in separateChainForNode()
981 Node->Flags &= ~GepNode::Used; in separateChainForNode()
986 NewNode->Flags |= GepNode::Used; in separateChainForNode()
987 LLVM_DEBUG(dbgs() << "new node: " << NewNode << " " << *NewNode << '\n'); in separateChainForNode()
992 void HexagonCommonGEP::separateConstantChains(GepNode *Node, in separateConstantChains() argument
996 nodes_for_root(Node, NCM, Ns); in separateConstantChains()
998 LLVM_DEBUG(dbgs() << "Separating constant chains for node: " << Node << '\n'); in separateConstantChains()
1000 // where the GEP node could be folded into the load/store instruction. in separateConstantChains()
1003 if (!(N->Flags & GepNode::Used)) in separateConstantChains()
1007 UseSet &Us = UF->second; in separateConstantChains()
1008 // Loads/stores that use the node N. in separateConstantChains()
1011 User *R = U->getUser(); in separateConstantChains()
1017 if (&Ld->getOperandUse(PtrX) == U) in separateConstantChains()
1021 if (&St->getOperandUse(PtrX) == U) in separateConstantChains()
1027 // would be (e.g. if the parent node has a constant index and also has in separateConstantChains()
1044 // Compute the inverse of the Node.Parent links. Also, collect the set in computeNodePlacement()
1055 LLVM_DEBUG(dbgs() << "Initial node placement:\n" << LocationAsBlock(Loc)); in computeNodePlacement()
1061 LLVM_DEBUG(dbgs() << "Node placement after adjustment for invariance:\n" in computeNodePlacement()
1068 LLVM_DEBUG(dbgs() << "Node use information:\n" << Uses); in computeNodePlacement()
1074 LLVM_DEBUG(dbgs() << "Final node placement:\n" << LocationAsBlock(Loc)); in computeNodePlacement()
1079 LLVM_DEBUG(dbgs() << "Fabricating GEP in " << LocB->getName() in fabricateGEP()
1084 assert((RN->Flags & GepNode::Root) && "Creating GEP for non-root"); in fabricateGEP()
1087 Value *Input = RN->BaseVal; in fabricateGEP()
1088 Type *InpTy = RN->PTy; in fabricateGEP()
1093 // If the type of the input of the first node is not a pointer, in fabricateGEP()
1096 if (!(NA[Idx]->Flags & GepNode::Pointer)) { in fabricateGEP()
1104 GepNode *N = NA[Idx-1]; in fabricateGEP()
1105 IdxList.push_back(N->Idx); in fabricateGEP()
1108 if (NA[Idx]->Flags & GepNode::Pointer) in fabricateGEP()
1113 NewInst->setIsInBounds(RN->Flags & GepNode::InBounds); in fabricateGEP()
1117 InpTy = NA[Idx]->PTy; in fabricateGEP()
1124 void HexagonCommonGEP::getAllUsersForNode(GepNode *Node, ValueVect &Values, in getAllUsersForNode() argument
1127 Work.push_back(Node); in getAllUsersForNode()
1133 if (N->Flags & GepNode::Used) { in getAllUsersForNode()
1135 assert(UF != Uses.end() && "No use information for used node"); in getAllUsersForNode()
1136 UseSet &Us = UF->second; in getAllUsersForNode()
1138 Values.push_back(U->getUser()); in getAllUsersForNode()
1142 NodeVect &Cs = CF->second; in getAllUsersForNode()
1177 LastUsed = (Last->Flags & GepNode::Used); in materialize()
1181 LastCN = (CF != NCM.end()) ? CF->second.size() : 0; in materialize()
1184 GepNode *Child = CF->second.front(); in materialize()
1191 BasicBlock::iterator InsertAt = LastB->getTerminator()->getIterator(); in materialize()
1196 if (FirstUse != LastB->end()) in materialize()
1203 // Convert all the children of Last node into roots, and append them in materialize()
1208 CN->Flags &= ~GepNode::Internal; in materialize()
1209 CN->Flags |= GepNode::Root; in materialize()
1210 CN->BaseVal = NewInst; in materialize()
1215 // Lastly, if the Last node was used, replace all uses with the new GEP. in materialize()
1220 UseSet &Us = UF->second; in materialize()
1222 U->set(NewInst); in materialize()
1229 BO.push_back(&Fn->front()); in removeDeadCode()
1233 for (auto *DTN : children<DomTreeNode *>(DT->getNode(B))) in removeDeadCode()
1234 BO.push_back(DTN->getBlock()); in removeDeadCode()
1245 In->eraseFromParent(); in removeDeadCode()
1261 DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree(); in runOnFunction()