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