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  in run()
110     // Compute the total flow and its cost  in run()
115         if (Edge.Flow > 0) {  in run()
116           TotalCost += Edge.Cost * Edge.Flow;  in run()
118             TotalFlow += Edge.Flow;  in run()
123                       << " iterations with " << TotalFlow << " total flow"  in run()
141     SrcEdge.Flow = 0;  in addEdge()
148     DstEdge.Flow = 0;  in addEdge()
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;  in getFlow()  local
165       if (Edge.Flow > 0)  in getFlow()
166         Flow.push_back(std::make_pair(Edge.Dst, Edge.Flow));  in getFlow()
168     return Flow;  in getFlow()
171   /// Get the total flow between a pair of nodes.
173     int64_t Flow = 0;  in getFlow()  local
176         Flow += Edge.Flow;  in getFlow()
179     return Flow;  in getFlow()
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");  in computeAugmentingPathCapacity()
224       uint64_t EdgeCapacity = uint64_t(Edge.Capacity - Edge.Flow);  in computeAugmentingPathCapacity()
272         if (Edge.Flow < Edge.Capacity) {  in findAugmentingPath()
293   /// Update the current flow along the augmenting path.
302       Edge.Flow += PathCapacity;  in augmentFlowAlongPath()
303       RevEdge.Flow -= PathCapacity;  in augmentFlowAlongPath()
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  in augmentFlowAlongDAG()
420              "incorrectly computed fractional flow");  in augmentFlowAlongDAG()
421       // Distribute flow evenly among successors of Src  in augmentFlowAlongDAG()
428         uint64_t MaxIntFlow = double(Edge->Capacity - Edge->Flow) / EdgeFlow;  in augmentFlowAlongDAG()
432     // Stop early if we cannot send any (integral) flow from Source to Target  in augmentFlowAlongDAG()
436     // Phase 2: Send an integral flow of MaxFlowAmount  in augmentFlowAlongDAG()
441       // Distribute flow evenly among successors of Src, rounding up to make  in augmentFlowAlongDAG()
442       // sure all flow is sent  in augmentFlowAlongDAG()
449         EdgeFlow = std::min(EdgeFlow, uint64_t(Edge->Capacity - Edge->Flow));  in augmentFlowAlongDAG()
458     // Phase 3: Send excess flow back traversing the nodes backwards.  in augmentFlowAlongDAG()
459     // Because of rounding, not all flow can be sent along the edges of Src.  in augmentFlowAlongDAG()
460     // Hence, sending the remaining flow back to maintain flow conservation  in augmentFlowAlongDAG()
463       // Try to send excess flow back along each edge.  in augmentFlowAlongDAG()
464       // Make sure we only send back flow we just augmented (AugmentedFlow).  in augmentFlowAlongDAG()
476     // Phase 4: Update flow values along all edges  in augmentFlowAlongDAG()
479       // Verify that we have sent all the excess flow from the node  in augmentFlowAlongDAG()
482         assert(uint64_t(Edge->Capacity - Edge->Flow) >= Edge->AugmentedFlow);  in augmentFlowAlongDAG()
483         // Update flow values along the edge and its reverse copy  in augmentFlowAlongDAG()
485         Edge->Flow += Edge->AugmentedFlow;  in augmentFlowAlongDAG()
486         RevEdge.Flow -= Edge->AugmentedFlow;  in augmentFlowAlongDAG()
487         if (Edge->Capacity == Edge->Flow && Edge->AugmentedFlow > 0)  in augmentFlowAlongDAG()
517             Edge.Capacity > Edge.Flow &&  in identifyShortestEdges()
518             uint64_t(Edge.Capacity - Edge.Flow) >= MinCapacity;  in identifyShortestEdges()
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;  member
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  in run()
613       // Rebalance the flow inside unknown subgraphs  in run()
627       if (Block.Flow > 0 && !Visited[I]) {  in joinIsolatedComponents()
630         // Increase the flow along the path  in joinIsolatedComponents()
632                "incorrectly computed path adjusting control flow");  in joinIsolatedComponents()
633         Func.Blocks[Func.Entry].Flow += 1;  in joinIsolatedComponents()
635           Jump->Flow += 1;  in joinIsolatedComponents()
636           Func.Blocks[Jump->Target].Flow += 1;  in joinIsolatedComponents()
644   /// Run BFS from a given block along the jumps with a positive flow and mark
657         if (Jump->Flow > 0 && !Visited[Dst]) {  in findReachable()
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,  in jumpDistance()
760     if (Jump->Flow > 0)  in jumpDistance()
761       return BaseDistance + BaseDistance / Jump->Flow;  in jumpDistance()
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  in rebalanceUnknownSubgraphs()
803     // zero-flow block  in canRebalanceAtRoot()
804     if (SrcBlock->HasUnknownWeight || SrcBlock->Flow == 0)  in canRebalanceAtRoot()
899     // Ignore unlikely jumps with zero flow  in ignoreJump()
900     if (Jump->IsUnlikely && Jump->Flow == 0)  in ignoreJump()
914     // Ignore jumps to known blocks with zero flow  in ignoreJump()
915     if (!JumpTarget->HasUnknownWeight && JumpTarget->Flow == 0)  in ignoreJump()
981     assert(SrcBlock->Flow > 0 && "zero-flow block in unknown subgraph");  in rebalanceUnknownSubgraph()
983     // Ditribute flow from the source block  in rebalanceUnknownSubgraph()
985     // SrcBlock's flow is the sum of outgoing flows along non-ignored jumps  in rebalanceUnknownSubgraph()
989       BlockFlow += Jump->Flow;  in rebalanceUnknownSubgraph()
993     // Ditribute flow from the remaining blocks  in rebalanceUnknownSubgraph()
997       // Block's flow is the sum of incoming flows  in rebalanceUnknownSubgraph()
999         BlockFlow += Jump->Flow;  in rebalanceUnknownSubgraph()
1001       Block->Flow = BlockFlow;  in rebalanceUnknownSubgraph()
1006   /// Redistribute flow for a block in a subgraph rooted at SrcBlock,
1010     // Process all successor jumps and update corresponding flow values  in rebalanceBlock()
1022     // Each of the Block's successors gets the following amount of flow.  in rebalanceBlock()
1023     // Rounding the value up so that all flow is propagated  in rebalanceBlock()
1028       uint64_t Flow = std::min(SuccFlow, BlockFlow);  in rebalanceBlock()  local
1029       Jump->Flow = Flow;  in rebalanceBlock()
1030       BlockFlow -= Flow;  in rebalanceBlock()
1032     assert(BlockFlow == 0 && "not all flow is propagated");  in rebalanceBlock()
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.  in initializeNetwork()
1074   // Initialize nodes of the flow network  in initializeNetwork()
1102   // Initialize edges of the flow network  in initializeNetwork()
1122   // Make sure we have a valid flow circulation  in initializeNetwork()
1183 /// Extract resulting block and edge counts from the flow network.
1195     int64_t Flow = 0;  in extractWeights()  local
1198       Flow = int64_t(Jump.Weight) + AuxFlow;  in extractWeights()
1200       Flow = int64_t(Jump.Weight) + (AuxFlow > 0 ? AuxFlow : 0);  in extractWeights()
1202     Jump.Flow = Flow;  in extractWeights()
1203     assert(Flow >= 0 && "negative jump flow");  in extractWeights()
1210     InFlow[Jump.Target] += Jump.Flow;  in extractWeights()
1211     OutFlow[Jump.Source] += Jump.Flow;  in extractWeights()
1215     Block.Flow = std::max(OutFlow[B], InFlow[B]);  in extractWeights()
1257 /// Verify that the computed flow values satisfy flow conservation rules.
1263     InFlow[Jump.Target] += Jump.Flow;  in verifyOutput()
1264     OutFlow[Jump.Source] += Jump.Flow;  in verifyOutput()
1272       TotalInFlow += Block.Flow;  in verifyOutput()
1273       assert(Block.Flow == OutFlow[I] && "incorrectly computed control flow");  in verifyOutput()
1275       TotalOutFlow += Block.Flow;  in verifyOutput()
1276       assert(Block.Flow == InFlow[I] && "incorrectly computed control flow");  in verifyOutput()
1278       assert(Block.Flow == OutFlow[I] && "incorrectly computed control flow");  in verifyOutput()
1279       assert(Block.Flow == InFlow[I] && "incorrectly computed control flow");  in verifyOutput()
1282   assert(TotalInFlow == TotalOutFlow && "incorrectly computed control flow");  in verifyOutput()
1284   // Verify that there are no isolated flow components  in verifyOutput()
1289     if (Jump.Flow > 0) {  in verifyOutput()
1294   // Run BFS from the source along edges with positive flow  in verifyOutput()
1310   // Verify that every block that has a positive flow is reached from the source  in verifyOutput()
1311   // along edges with a positive flow  in verifyOutput()
1314     assert((Visited[I] || Block.Flow == 0) && "an isolated flow component");  in verifyOutput()
1324   // Check if the function has samples and assign initial flow values  in applyFlowInference()
1329     Block.Flow = Block.Weight;  in applyFlowInference()
1334     Jump.Flow = Jump.Weight;  in applyFlowInference()
1351   // Extract flow values for every block and every edge  in applyFlowInference()
1354   // Post-processing adjustments to the flow  in applyFlowInference()
1364 /// Apply the profile inference algorithm for a given flow function