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