Lines Matching full:edge
286 // Compute the context ids for this node from the union of its edge context
294 for (auto &Edge : *Edges) in getContextIds()
295 Count += Edge->getContextIds().size(); in getContextIds()
297 for (auto &Edge : *Edges) in getContextIds()
298 ContextIds.insert(Edge->getContextIds().begin(), in getContextIds()
299 Edge->getContextIds().end()); in getContextIds()
303 // Compute the allocation type for this node from the OR of its edge
312 for (auto &Edge : *Edges) { in computeAllocType()
313 AllocType |= Edge->AllocTypes; in computeAllocType()
321 // The context ids set for this node is empty if its edge context ids are
327 for (auto &Edge : *Edges) { in emptyContextIds()
328 if (!Edge->getContextIds().empty()) in emptyContextIds()
367 void eraseCalleeEdge(const ContextEdge *Edge);
368 void eraseCallerEdge(const ContextEdge *Edge);
393 /// Edge in the Callsite Context Graph from a ContextNode N to a caller or
400 // for contexts including this edge.
403 // The set of IDs for contexts including this edge.
416 friend raw_ostream &operator<<(raw_ostream &OS, const ContextEdge &Edge) { in operator <<() argument
417 Edge.print(OS); in operator <<()
492 /// ids moved to the newly created edge.
504 /// Returns true if the given call targets the callee of the given edge, or if
585 /// Create a clone of Edge's callee and move Edge to that new callee node,
587 /// If callee's caller edge iterator is supplied, it is updated when removing
588 /// the edge from that list. If ContextIdsToMove is non-empty, only that
589 /// subset of Edge's ids are moved to an edge to the new callee.
591 moveEdgeToNewCalleeClone(const std::shared_ptr<ContextEdge> &Edge,
595 /// Change the callee of Edge to existing callee clone NewCallee, performing
597 /// If callee's caller edge iterator is supplied, it is updated when removing
598 /// the edge from that list. If ContextIdsToMove is non-empty, only that
599 /// subset of Edge's ids are moved to an edge to the new callee.
600 void moveEdgeToExistingCalleeClone(const std::shared_ptr<ContextEdge> &Edge,
840 // care about the type along that edge as it doesn't in allocTypesMatch()
883 for (auto &Edge : CallerEdges) { in addOrUpdateCallerEdge() local
884 if (Edge->Caller == Caller) { in addOrUpdateCallerEdge()
885 Edge->AllocTypes |= (uint8_t)AllocType; in addOrUpdateCallerEdge()
886 Edge->getContextIds().insert(ContextId); in addOrUpdateCallerEdge()
890 std::shared_ptr<ContextEdge> Edge = std::make_shared<ContextEdge>( in addOrUpdateCallerEdge() local
892 CallerEdges.push_back(Edge); in addOrUpdateCallerEdge()
893 Caller->CalleeEdges.push_back(Edge); in addOrUpdateCallerEdge()
900 auto Edge = *EI; in removeNoneTypeCalleeEdges() local
901 if (Edge->AllocTypes == (uint8_t)AllocationType::None) { in removeNoneTypeCalleeEdges()
902 assert(Edge->ContextIds.empty()); in removeNoneTypeCalleeEdges()
903 Edge->Callee->eraseCallerEdge(Edge.get()); in removeNoneTypeCalleeEdges()
914 for (const auto &Edge : CalleeEdges) in findEdgeFromCallee() local
915 if (Edge->Callee == Callee) in findEdgeFromCallee()
916 return Edge.get(); in findEdgeFromCallee()
924 for (const auto &Edge : CallerEdges) in findEdgeFromCaller() local
925 if (Edge->Caller == Caller) in findEdgeFromCaller()
926 return Edge.get(); in findEdgeFromCaller()
932 eraseCalleeEdge(const ContextEdge *Edge) { in eraseCalleeEdge() argument
934 CalleeEdges, [Edge](const std::shared_ptr<ContextEdge> &CalleeEdge) { in eraseCalleeEdge()
935 return CalleeEdge.get() == Edge; in eraseCalleeEdge()
943 eraseCallerEdge(const ContextEdge *Edge) { in eraseCallerEdge() argument
945 CallerEdges, [Edge](const std::shared_ptr<ContextEdge> &CallerEdge) { in eraseCallerEdge()
946 return CallerEdge.get() == Edge; in eraseCallerEdge()
1113 for (const auto &Edge : Node->CallerEdges) { in propagateDuplicateContextIds() local
1114 auto Inserted = Visited.insert(Edge.get()); in propagateDuplicateContextIds()
1117 ContextNode *NextNode = Edge->Caller; in propagateDuplicateContextIds()
1118 DenseSet<uint32_t> NewIdsToAdd = GetNewIds(Edge->getContextIds()); in propagateDuplicateContextIds()
1119 // Only need to recursively iterate to NextNode via this caller edge if in propagateDuplicateContextIds()
1122 Edge->getContextIds().insert(NewIdsToAdd.begin(), NewIdsToAdd.end()); in propagateDuplicateContextIds()
1145 auto Edge = *EI; in connectNewNode() local
1146 // Remove any matching context ids from Edge, return set that were found and in connectNewNode()
1147 // removed, these are the new edge's context ids. Also update the remaining in connectNewNode()
1150 set_subtract(Edge->getContextIds(), RemainingContextIds, NewEdgeContextIds, in connectNewNode()
1153 // If no matching context ids for this edge, skip it. in connectNewNode()
1161 Edge->Callee, NewNode, NewAllocType, std::move(NewEdgeContextIds)); in connectNewNode()
1167 NewNode, Edge->Caller, NewAllocType, std::move(NewEdgeContextIds)); in connectNewNode()
1171 // Remove old edge if context ids empty. in connectNewNode()
1172 if (Edge->getContextIds().empty()) { in connectNewNode()
1174 Edge->Callee->eraseCallerEdge(Edge.get()); in connectNewNode()
1177 Edge->Caller->eraseCalleeEdge(Edge.get()); in connectNewNode()
1188 const std::shared_ptr<ContextEdge<DerivedCCG, FuncTy, CallTy>> &Edge) { in checkEdge() argument
1191 assert(Edge->AllocTypes != (uint8_t)AllocationType::None); in checkEdge()
1192 assert(!Edge->ContextIds.empty()); in checkEdge()
1204 // Node's context ids should be the union of both its callee and caller edge in checkNode()
1209 for (const auto &Edge : llvm::drop_begin(Node->CallerEdges)) { in checkNode() local
1211 checkEdge<DerivedCCG, FuncTy, CallTy>(Edge); in checkNode()
1212 set_union(CallerEdgeContextIds, Edge->ContextIds); in checkNode()
1222 for (const auto &Edge : llvm::drop_begin(Node->CalleeEdges)) { in checkNode() local
1224 checkEdge<DerivedCCG, FuncTy, CallTy>(Edge); in checkNode()
1225 set_union(CalleeEdgeContextIds, Edge->getContextIds()); in checkNode()
1242 // iterator over the original edge vector. We don't need to process these in assignStackNodesPostOrder()
1245 for (auto &Edge : CallerEdges) { in assignStackNodesPostOrder() local
1247 if (!Edge) in assignStackNodesPostOrder()
1249 assignStackNodesPostOrder(Edge->Caller, Visited, StackIdToMatchingCalls); in assignStackNodesPostOrder()
1318 auto *Edge = CurNode->findEdgeFromCallee(PrevNode); in assignStackNodesPostOrder() local
1319 if (!Edge) { in assignStackNodesPostOrder()
1324 set_intersect(SavedContextIds, Edge->getContextIds()); in assignStackNodesPostOrder()
1360 // edge from the prior node. in assignStackNodesPostOrder()
1491 auto *Edge = CurNode->findEdgeFromCaller(PrevNode); in updateStackNodes() local
1492 // If there is no edge then the nodes belong to different MIB contexts, in updateStackNodes()
1501 if (!Edge) { in updateStackNodes()
1509 set_intersect(StackSequenceContextIds, Edge->getContextIds()); in updateStackNodes()
1839 auto Edge = *EI; in handleCallsitesWithMultipleTargets() local
1840 if (!Edge->Callee->hasCall()) in handleCallsitesWithMultipleTargets()
1842 assert(NodeToCallingFunc.count(Edge->Callee)); in handleCallsitesWithMultipleTargets()
1883 auto Edge = *EI; in calleesMatch() local
1884 const FuncTy *ProfiledCalleeFunc = NodeToCallingFunc[Edge->Callee]; in calleesMatch()
1885 const FuncTy *CallerFunc = NodeToCallingFunc[Edge->Caller]; in calleesMatch()
1897 auto AddEdge = [Edge, &EI](ContextNode *Caller, ContextNode *Callee) { in calleesMatch()
1899 // If there is already an edge between these nodes, simply update it and in calleesMatch()
1902 CurEdge->ContextIds.insert(Edge->ContextIds.begin(), in calleesMatch()
1903 Edge->ContextIds.end()); in calleesMatch()
1904 CurEdge->AllocTypes |= Edge->AllocTypes; in calleesMatch()
1907 // Otherwise, create a new edge and insert it into the caller and callee in calleesMatch()
1910 Callee, Caller, Edge->AllocTypes, Edge->ContextIds); in calleesMatch()
1912 if (Caller == Edge->Caller) { in calleesMatch()
1913 // If we are inserting the new edge into the current edge's caller, insert in calleesMatch()
1914 // the new edge before the current iterator position, and then increment in calleesMatch()
1915 // back to the current edge. in calleesMatch()
1918 assert(*EI == Edge && in calleesMatch()
1926 auto *CurCalleeNode = Edge->Callee; in calleesMatch()
1932 NewNode->AllocTypes |= Edge->AllocTypes; in calleesMatch()
1941 NewNode->AllocTypes = Edge->AllocTypes; in calleesMatch()
1950 // Hook up edge's original caller to new callee node. in calleesMatch()
1951 AddEdge(Edge->Caller, CurCalleeNode); in calleesMatch()
1953 // Remove old edge in calleesMatch()
1954 Edge->Callee->eraseCallerEdge(Edge.get()); in calleesMatch()
1955 EI = Edge->Caller->CalleeEdges.erase(EI); in calleesMatch()
1958 // In the final AddEdge call we would have either added a new callee edge, in calleesMatch()
1959 // to Edge->Caller, or found an existing one. Either way we are guaranteed in calleesMatch()
1960 // that there is at least one callee edge. in calleesMatch()
1961 assert(!Edge->Caller->CalleeEdges.empty()); in calleesMatch()
2238 for (auto &Edge : CalleeEdges) in print() local
2239 OS << "\t\t" << *Edge << "\n"; in print()
2241 for (auto &Edge : CallerEdges) in print() local
2242 OS << "\t\t" << *Edge << "\n"; in print()
2264 OS << "Edge from Callee " << Callee << " to Caller: " << Caller in print()
2320 for (auto &Edge : Node->CallerEdges) in check() local
2321 checkEdge<DerivedCCG, FuncTy, CallTy>(Edge); in check()
2417 auto &Edge = *(ChildIter.getCurrent()); in getEdgeAttributes() local
2418 return (Twine("tooltip=\"") + getContextIds(Edge->ContextIds) + "\"" + in getEdgeAttributes()
2419 Twine(",fillcolor=\"") + getColor(Edge->AllocTypes) + "\"") in getEdgeAttributes()
2474 const std::shared_ptr<ContextEdge> &Edge, EdgeIter *CallerEdgeI, in moveEdgeToNewCalleeClone() argument
2476 ContextNode *Node = Edge->Callee; in moveEdgeToNewCalleeClone()
2483 moveEdgeToExistingCalleeClone(Edge, Clone, CallerEdgeI, /*NewClone=*/true, in moveEdgeToNewCalleeClone()
2490 moveEdgeToExistingCalleeClone(const std::shared_ptr<ContextEdge> &Edge, in moveEdgeToExistingCalleeClone() argument
2494 // NewCallee and Edge's current callee must be clones of the same original in moveEdgeToExistingCalleeClone()
2495 // node (Edge's current callee may be the original node too). in moveEdgeToExistingCalleeClone()
2496 assert(NewCallee->getOrigNode() == Edge->Callee->getOrigNode()); in moveEdgeToExistingCalleeClone()
2498 ContextNode *OldCallee = Edge->Callee; in moveEdgeToExistingCalleeClone()
2500 // We might already have an edge to the new callee from earlier cloning for a in moveEdgeToExistingCalleeClone()
2502 auto ExistingEdgeToNewCallee = NewCallee->findEdgeFromCaller(Edge->Caller); in moveEdgeToExistingCalleeClone()
2505 // edge. Copy in Edge's ids for simplicity. in moveEdgeToExistingCalleeClone()
2507 ContextIdsToMove = Edge->getContextIds(); in moveEdgeToExistingCalleeClone()
2509 // If we are moving all of Edge's ids, then just move the whole Edge. in moveEdgeToExistingCalleeClone()
2510 // Otherwise only move the specified subset, to a new edge if needed. in moveEdgeToExistingCalleeClone()
2511 if (Edge->getContextIds().size() == ContextIdsToMove.size()) { in moveEdgeToExistingCalleeClone()
2512 // Moving the whole Edge. in moveEdgeToExistingCalleeClone()
2516 OldCallee->eraseCallerEdge(Edge.get()); in moveEdgeToExistingCalleeClone()
2518 // Since we already have an edge to NewCallee, simply move the ids in moveEdgeToExistingCalleeClone()
2519 // onto it, and remove the existing Edge. in moveEdgeToExistingCalleeClone()
2522 ExistingEdgeToNewCallee->AllocTypes |= Edge->AllocTypes; in moveEdgeToExistingCalleeClone()
2523 assert(Edge->ContextIds == ContextIdsToMove); in moveEdgeToExistingCalleeClone()
2524 Edge->ContextIds.clear(); in moveEdgeToExistingCalleeClone()
2525 Edge->AllocTypes = (uint8_t)AllocationType::None; in moveEdgeToExistingCalleeClone()
2526 Edge->Caller->eraseCalleeEdge(Edge.get()); in moveEdgeToExistingCalleeClone()
2528 // Otherwise just reconnect Edge to NewCallee. in moveEdgeToExistingCalleeClone()
2529 Edge->Callee = NewCallee; in moveEdgeToExistingCalleeClone()
2530 NewCallee->CallerEdges.push_back(Edge); in moveEdgeToExistingCalleeClone()
2531 // Don't need to update Edge's context ids since we are simply in moveEdgeToExistingCalleeClone()
2535 NewCallee->AllocTypes |= Edge->AllocTypes; in moveEdgeToExistingCalleeClone()
2537 // Only moving a subset of Edge's ids. in moveEdgeToExistingCalleeClone()
2543 // Since we already have an edge to NewCallee, simply move the ids in moveEdgeToExistingCalleeClone()
2549 // Otherwise, create a new edge to NewCallee for the ids being moved. in moveEdgeToExistingCalleeClone()
2551 NewCallee, Edge->Caller, CallerEdgeAllocType, ContextIdsToMove); in moveEdgeToExistingCalleeClone()
2552 Edge->Caller->CalleeEdges.push_back(NewEdge); in moveEdgeToExistingCalleeClone()
2556 // those ids and update the alloc type on the original Edge. in moveEdgeToExistingCalleeClone()
2558 set_subtract(Edge->ContextIds, ContextIdsToMove); in moveEdgeToExistingCalleeClone()
2559 Edge->AllocTypes = computeAllocType(Edge->ContextIds); in moveEdgeToExistingCalleeClone()
2561 // Now walk the old callee node's callee edges and move Edge's context ids in moveEdgeToExistingCalleeClone()
2562 // over to the corresponding edge into the clone (which is created here if in moveEdgeToExistingCalleeClone()
2565 // The context ids moving to the new callee are the subset of this edge's in moveEdgeToExistingCalleeClone()
2566 // context ids and the context ids on the caller edge being moved. in moveEdgeToExistingCalleeClone()
2573 // Update context ids / alloc type on corresponding edge to NewCallee. in moveEdgeToExistingCalleeClone()
2577 // a corresponding edge there, fall through to the cloning below. in moveEdgeToExistingCalleeClone()
2626 for (auto &Edge : CallerEdges) { in recursivelyRemoveNoneTypeCalleeEdges() local
2628 if (Edge->Callee == nullptr && Edge->Caller == nullptr) { in recursivelyRemoveNoneTypeCalleeEdges()
2629 assert(!is_contained(Node->CallerEdges, Edge)); in recursivelyRemoveNoneTypeCalleeEdges()
2632 recursivelyRemoveNoneTypeCalleeEdges(Edge->Caller, Visited); in recursivelyRemoveNoneTypeCalleeEdges()
2680 // The recursive call to identifyClones may delete the current edge from the in identifyClones()
2687 for (auto &Edge : CallerEdges) { in identifyClones() local
2689 if (Edge->Callee == nullptr && Edge->Caller == nullptr) { in identifyClones()
2690 assert(!llvm::count(Node->CallerEdges, Edge)); in identifyClones()
2693 // Ignore any caller we previously visited via another edge. in identifyClones()
2694 if (!Visited.count(Edge->Caller) && !Edge->Caller->CloneOf) { in identifyClones()
2695 identifyClones(Edge->Caller, Visited, AllocContextIds); in identifyClones()
2711 // Give NotCold edge the lowest sort priority so those edges are at the end of in identifyClones()
2736 // Use the first context id for each edge as a in identifyClones()
2748 // We need to be able to remove Edge from CallerEdges, so need to adjust in identifyClones()
2753 // See if cloning the prior caller edge left this node with a single alloc in identifyClones()
2758 // Only need to process the ids along this edge pertaining to the given in identifyClones()
2768 // Compute the node callee edge alloc types corresponding to the context ids in identifyClones()
2769 // for this caller edge. in identifyClones()
2812 // The edge iterator is adjusted when we move the CallerEdge to the clone. in identifyClones()
3088 const std::shared_ptr<ContextEdge> &Edge = *EI; in assignFunctions() local
3090 CallsiteToCalleeFuncCloneMap[Edge->Caller]; in assignFunctions()
3165 // Moving the edge may have resulted in some none type in assignFunctions()
3213 // We need to be able to remove Edge from CallerEdges, so need to adjust in assignFunctions()
3217 auto Edge = *EI; in assignFunctions() local
3219 if (!Edge->Caller->hasCall()) { in assignFunctions()
3225 if (CallsiteToCalleeFuncCloneMap.count(Edge->Caller)) { in assignFunctions()
3227 CallsiteToCalleeFuncCloneMap[Edge->Caller]; in assignFunctions()
3233 // been assigned to the same function clone called by Edge's caller in assignFunctions()
3234 // - if Edge's caller calls another callsite within Node's original in assignFunctions()
3261 // function clone. If so, we can move this edge to that new clone in assignFunctions()
3267 moveEdgeToExistingCalleeClone(Edge, NewClone, &EI); in assignFunctions()
3272 ContextNode *NewClone = moveEdgeToNewCalleeClone(Edge, &EI); in assignFunctions()
3282 // Moving the caller edge may have resulted in some none type in assignFunctions()
3287 // already adjusted iterator EI while moving the edge. in assignFunctions()
3332 RecordCalleeFuncOfCallsite(Edge->Caller, in assignFunctions()
3366 for (auto &Edge : Node->CallerEdges) in assignFunctions() local
3367 UpdateCalls(Edge->Caller, Visited, UpdateCalls); in assignFunctions()