Lines Matching full:flow
11 // and edge counts that satisfy flow conservation rules, while minimally modify
31 "sample-profile-even-flow-distribution", cl::init(true), cl::Hidden,
32 cl::desc("Try to evenly distribute flow when there are multiple equally "
37 cl::desc("Evenly re-distribute flow among unknown subgraphs."));
41 cl::desc("Join isolated components having positive flow."));
67 /// A value indicating an infinite flow/capacity/weight of a block/edge.
72 /// The minimum-cost maximum flow algorithm.
74 /// The algorithm finds the maximum flow of minimum cost on a given (directed)
77 /// flow is sent along paths of positive capacity from the source to the sink.
80 /// value of the maximum flow. However, the observed running time on typical
84 /// of nodes (source and sink). The output is the flow along each edge of the
107 // flow along its edges
110 // Compute the total flow and its cost
115 if (Edge.Flow > 0) {
116 TotalCost += Edge.Cost * Edge.Flow;
118 TotalFlow += Edge.Flow;
123 << " iterations with " << TotalFlow << " total flow"
141 SrcEdge.Flow = 0;
148 DstEdge.Flow = 0;
160 /// Get the total flow from a given source node.
161 /// Returns a list of pairs (target node, amount of flow to the target).
163 std::vector<std::pair<uint64_t, int64_t>> Flow;
165 if (Edge.Flow > 0)
166 Flow.push_back(std::make_pair(Edge.Dst, Edge.Flow));
168 return Flow;
171 /// Get the total flow between a pair of nodes.
173 int64_t Flow = 0;
176 Flow += Edge.Flow;
179 return Flow;
184 /// flow along its edges. The method returns the number of applied iterations.
215 /// saturated (that is, no flow can be sent along the path), then return 0.
223 assert(Edge.Capacity >= Edge.Flow && "incorrect edge flow");
224 uint64_t EdgeCapacity = uint64_t(Edge.Capacity - Edge.Flow);
272 if (Edge.Flow < Edge.Capacity) {
293 /// Update the current flow along the augmenting path.
302 Edge.Flow += PathCapacity;
303 RevEdge.Flow -= PathCapacity;
401 /// Update the current flow along the given (acyclic) subgraph specified by
402 /// the vertex order, AugmentingOrder. The objective is to send as much flow
403 /// as possible while evenly distributing flow among successors of each node.
415 // Phase 1: Send a unit of fractional flow along the DAG
420 "incorrectly computed fractional flow");
421 // Distribute flow evenly among successors of Src
428 uint64_t MaxIntFlow = double(Edge->Capacity - Edge->Flow) / EdgeFlow;
432 // Stop early if we cannot send any (integral) flow from Source to Target
436 // Phase 2: Send an integral flow of MaxFlowAmount
441 // Distribute flow evenly among successors of Src, rounding up to make
442 // sure all flow is sent
449 EdgeFlow = std::min(EdgeFlow, uint64_t(Edge->Capacity - Edge->Flow));
458 // Phase 3: Send excess flow back traversing the nodes backwards.
459 // Because of rounding, not all flow can be sent along the edges of Src.
460 // Hence, sending the remaining flow back to maintain flow conservation
463 // Try to send excess flow back along each edge.
464 // Make sure we only send back flow we just augmented (AugmentedFlow).
476 // Phase 4: Update flow values along all edges
479 // Verify that we have sent all the excess flow from the node
482 assert(uint64_t(Edge->Capacity - Edge->Flow) >= Edge->AugmentedFlow);
483 // Update flow values along the edge and its reverse copy
485 Edge->Flow += Edge->AugmentedFlow;
486 RevEdge.Flow -= Edge->AugmentedFlow;
487 if (Edge->Capacity == Edge->Flow && Edge->AugmentedFlow > 0)
517 Edge.Capacity > Edge.Flow &&
518 uint64_t(Edge.Capacity - Edge.Flow) >= MinCapacity;
526 /// A node in a flow network.
538 /// Fractional flow.
540 /// Integral flow.
550 /// An edge in a flow network.
556 /// The current flow on the edge.
557 int64_t Flow;
566 /// Extra flow along the edge.
574 /// Source node of the flow.
576 /// Target (sink) node of the flow.
580 /// Params for flow computation.
584 /// A post-processing adjustment of the control flow. It applies two steps by
585 /// rerouting some flow and making it more realistic:
587 /// - First, it removes all isolated components ("islands") with a positive flow
590 /// and increase the flow by one unit along the path.
593 /// with no sampled counts. Then it rebalnces the flow that goes through such
608 // Adjust the flow to get rid of isolated components
613 // Rebalance the flow inside unknown subgraphs
627 if (Block.Flow > 0 && !Visited[I]) {
630 // Increase the flow along the path
632 "incorrectly computed path adjusting control flow");
633 Func.Blocks[Func.Entry].Flow += 1;
635 Jump->Flow += 1;
636 Func.Blocks[Jump->Target].Flow += 1;
644 /// Run BFS from a given block along the jumps with a positive flow and mark
657 if (Jump->Flow > 0 && !Visited[Dst]) {
745 /// In order to incite the path to use blocks/jumps with large positive flow,
749 /// - to minimize the number of Flow == 0 jumps used and subject to that,
750 /// - minimizes total multiplicative Flow increase for the remaining edges.
758 std::min(Func.Blocks[Func.Entry].Flow,
760 if (Jump->Flow > 0)
761 return BaseDistance + BaseDistance / Jump->Flow;
767 /// Rebalance unknown subgraphs so that the flow is split evenly across the
770 /// blocks. Then it verifies if flow rebalancing is feasible and applies it.
795 // Rebalance the flow
803 // zero-flow block
804 if (SrcBlock->HasUnknownWeight || SrcBlock->Flow == 0)
899 // Ignore unlikely jumps with zero flow
900 if (Jump->IsUnlikely && Jump->Flow == 0)
914 // Ignore jumps to known blocks with zero flow
915 if (!JumpTarget->HasUnknownWeight && JumpTarget->Flow == 0)
981 assert(SrcBlock->Flow > 0 && "zero-flow block in unknown subgraph");
983 // Ditribute flow from the source block
985 // SrcBlock's flow is the sum of outgoing flows along non-ignored jumps
989 BlockFlow += Jump->Flow;
993 // Ditribute flow from the remaining blocks
997 // Block's flow is the sum of incoming flows
999 BlockFlow += Jump->Flow;
1001 Block->Flow = BlockFlow;
1006 /// Redistribute flow for a block in a subgraph rooted at SrcBlock,
1010 // Process all successor jumps and update corresponding flow values
1022 // Each of the Block's successors gets the following amount of flow.
1023 // Rounding the value up so that all flow is propagated
1028 uint64_t Flow = std::min(SuccFlow, BlockFlow);
1029 Jump->Flow = Flow;
1030 BlockFlow -= Flow;
1032 assert(BlockFlow == 0 && "not all flow is propagated");
1040 /// Params for flow computation.
1051 /// Initializing flow network for a given function.
1054 /// incoming flow, (ii) an outgoing flow; they penalize an increase or a
1063 // Introducing dummy source/sink pairs to allow flow circulation.
1074 // Initialize nodes of the flow network
1102 // Initialize edges of the flow network
1122 // Make sure we have a valid flow circulation
1183 /// Extract resulting block and edge counts from the flow network.
1195 int64_t Flow = 0;
1198 Flow = int64_t(Jump.Weight) + AuxFlow;
1200 Flow = int64_t(Jump.Weight) + (AuxFlow > 0 ? AuxFlow : 0);
1202 Jump.Flow = Flow;
1203 assert(Flow >= 0 && "negative jump flow");
1210 InFlow[Jump.Target] += Jump.Flow;
1211 OutFlow[Jump.Source] += Jump.Flow;
1215 Block.Flow = std::max(OutFlow[B], InFlow[B]);
1257 /// Verify that the computed flow values satisfy flow conservation rules.
1263 InFlow[Jump.Target] += Jump.Flow;
1264 OutFlow[Jump.Source] += Jump.Flow;
1272 TotalInFlow += Block.Flow;
1273 assert(Block.Flow == OutFlow[I] && "incorrectly computed control flow");
1275 TotalOutFlow += Block.Flow;
1276 assert(Block.Flow == InFlow[I] && "incorrectly computed control flow");
1278 assert(Block.Flow == OutFlow[I] && "incorrectly computed control flow");
1279 assert(Block.Flow == InFlow[I] && "incorrectly computed control flow");
1282 assert(TotalInFlow == TotalOutFlow && "incorrectly computed control flow");
1284 // Verify that there are no isolated flow components
1289 if (Jump.Flow > 0) {
1294 // Run BFS from the source along edges with positive flow
1310 // Verify that every block that has a positive flow is reached from the source
1311 // along edges with a positive flow
1314 assert((Visited[I] || Block.Flow == 0) && "an isolated flow component");
1324 // Check if the function has samples and assign initial flow values
1329 Block.Flow = Block.Weight;
1334 Jump.Flow = Jump.Weight;
1351 // Extract flow values for every block and every edge
1354 // Post-processing adjustments to the flow
1364 /// Apply the profile inference algorithm for a given flow function