25 #define DEBUG_TYPE "sample-profile-inference"
31 cl::desc(
"Try to evenly distribute counts when there are multiple equally "
36 cl::desc(
"Maximum number of dfs iterations for even count distribution."));
40 cl::desc(
"A cost of increasing a block's count by one."));
44 cl::desc(
"A cost of decreasing a block's count by one."));
48 cl::desc(
"A cost of increasing a count of zero-weight block by one."));
52 cl::desc(
"A cost of increasing the entry block's count by one."));
56 cl::desc(
"A cost of decreasing the entry block's count by one."));
61 static constexpr int64_t
INF = ((int64_t)1) << 50;
77 class MinCostMaxFlow {
84 Nodes = std::vector<Node>(NodeCount);
85 Edges = std::vector<std::vector<Edge>>(NodeCount, std::vector<Edge>());
86 if (SampleProfileEvenCountDistribution)
88 std::vector<std::vector<Edge *>>(NodeCount, std::vector<Edge *>());
95 size_t AugmentationIters = applyFlowAugmentation();
98 int64_t TotalCost = 0;
99 int64_t TotalFlow = 0;
100 for (
uint64_t Src = 0; Src < Nodes.size(); Src++) {
101 for (
auto &Edge : Edges[Src]) {
103 TotalCost += Edge.Cost * Edge.Flow;
105 TotalFlow += Edge.Flow;
109 LLVM_DEBUG(
dbgs() <<
"Completed profi after " << AugmentationIters
110 <<
" iterations with " << TotalFlow <<
" total flow"
111 <<
" of " << TotalCost <<
" cost\n");
113 (void)AugmentationIters;
121 assert(Capacity > 0 &&
"adding an edge of zero capacity");
122 assert(Src != Dst &&
"loop edge are not supported");
127 SrcEdge.Capacity = Capacity;
129 SrcEdge.RevEdgeIndex = Edges[Dst].size();
133 DstEdge.Cost = -Cost;
134 DstEdge.Capacity = 0;
136 DstEdge.RevEdgeIndex = Edges[Src].size();
138 Edges[Src].push_back(SrcEdge);
139 Edges[Dst].push_back(DstEdge);
149 const std::vector<std::pair<uint64_t, int64_t>> getFlow(
uint64_t Src)
const {
150 std::vector<std::pair<uint64_t, int64_t>>
Flow;
151 for (
auto &Edge : Edges[Src]) {
153 Flow.push_back(std::make_pair(Edge.Dst, Edge.Flow));
161 for (
auto &Edge : Edges[Src]) {
162 if (Edge.Dst == Dst) {
170 static constexpr int64_t AuxCostUnlikely = ((int64_t)1) << 30;
172 static constexpr
uint64_t MinBaseDistance = 10000;
177 size_t applyFlowAugmentation() {
178 size_t AugmentationIters = 0;
179 while (findAugmentingPath()) {
180 uint64_t PathCapacity = computeAugmentingPathCapacity();
181 while (PathCapacity > 0) {
182 bool Progress =
false;
183 if (SampleProfileEvenCountDistribution) {
185 identifyShortestEdges(PathCapacity);
188 auto AugmentingOrder = findAugmentingDAG();
191 Progress = augmentFlowAlongDAG(AugmentingOrder);
192 PathCapacity = computeAugmentingPathCapacity();
196 augmentFlowAlongPath(PathCapacity);
203 return AugmentationIters;
208 uint64_t computeAugmentingPathCapacity() {
212 uint64_t Pred = Nodes[Now].ParentNode;
213 auto &Edge = Edges[Pred][Nodes[Now].ParentEdgeIndex];
215 assert(Edge.Capacity >= Edge.Flow &&
"incorrect edge flow");
217 PathCapacity =
std::min(PathCapacity, EdgeCapacity);
225 bool findAugmentingPath() {
227 for (
auto &Node : Nodes) {
230 Node.ParentEdgeIndex =
uint64_t(-1);
234 std::queue<uint64_t> Queue;
236 Nodes[
Source].Distance = 0;
237 Nodes[
Source].Taken =
true;
238 while (!Queue.empty()) {
241 Nodes[Src].Taken =
false;
256 if (!SampleProfileEvenCountDistribution && Nodes[
Target].Distance == 0)
258 if (Nodes[Src].Distance > Nodes[
Target].Distance)
262 for (
uint64_t EdgeIdx = 0; EdgeIdx < Edges[Src].size(); EdgeIdx++) {
263 auto &Edge = Edges[Src][EdgeIdx];
264 if (Edge.Flow < Edge.Capacity) {
266 int64_t NewDistance = Nodes[Src].Distance + Edge.Cost;
267 if (Nodes[Dst].Distance > NewDistance) {
269 Nodes[Dst].Distance = NewDistance;
270 Nodes[Dst].ParentNode = Src;
271 Nodes[Dst].ParentEdgeIndex = EdgeIdx;
273 if (!Nodes[Dst].Taken) {
275 Nodes[Dst].Taken =
true;
286 void augmentFlowAlongPath(
uint64_t PathCapacity) {
287 assert(PathCapacity > 0 &&
"found an incorrect augmenting path");
290 uint64_t Pred = Nodes[Now].ParentNode;
291 auto &Edge = Edges[Pred][Nodes[Now].ParentEdgeIndex];
292 auto &RevEdge = Edges[Now][Edge.RevEdgeIndex];
294 Edge.Flow += PathCapacity;
295 RevEdge.Flow -= PathCapacity;
308 std::vector<uint64_t> findAugmentingDAG() {
314 typedef std::pair<uint64_t, uint64_t> StackItemType;
315 std::stack<StackItemType> Stack;
316 std::vector<uint64_t> AugmentingOrder;
319 for (
auto &Node : Nodes) {
328 Nodes[
Target].Taken =
true;
332 Nodes[
Source].Discovery = ++Time;
333 while (!Stack.empty()) {
334 auto NodeIdx = Stack.top().first;
335 auto EdgeIdx = Stack.top().second;
338 if (EdgeIdx < Edges[NodeIdx].
size()) {
339 auto &Edge = Edges[NodeIdx][EdgeIdx];
340 auto &Dst = Nodes[Edge.Dst];
341 Stack.top().second++;
343 if (Edge.OnShortestPath) {
345 if (Dst.Discovery == 0 && Dst.NumCalls < SampleProfileMaxDfsCalls) {
346 Dst.Discovery = ++Time;
347 Stack.emplace(Edge.Dst, 0);
349 }
else if (Dst.Taken && Dst.Finish != 0) {
351 Nodes[NodeIdx].Taken =
true;
358 if (!Nodes[NodeIdx].Taken) {
359 Nodes[NodeIdx].Discovery = 0;
363 Nodes[NodeIdx].Finish = ++Time;
366 assert(!Stack.empty() &&
"empty stack while running dfs");
367 Nodes[Stack.top().first].Taken =
true;
369 AugmentingOrder.push_back(NodeIdx);
374 std::reverse(AugmentingOrder.begin(), AugmentingOrder.end());
377 for (
size_t Src : AugmentingOrder) {
378 AugmentingEdges[Src].clear();
379 for (
auto &Edge : Edges[Src]) {
381 if (Edge.OnShortestPath && Nodes[Src].Taken && Nodes[Dst].Taken &&
382 Nodes[Dst].Finish < Nodes[Src].Finish) {
383 AugmentingEdges[Src].push_back(&Edge);
387 "incorrectly constructed augmenting edges");
390 return AugmentingOrder;
397 bool augmentFlowAlongDAG(
const std::vector<uint64_t> &AugmentingOrder) {
399 for (
uint64_t Src : AugmentingOrder) {
400 Nodes[Src].FracFlow = 0;
401 Nodes[Src].IntFlow = 0;
402 for (
auto &Edge : AugmentingEdges[Src]) {
403 Edge->AugmentedFlow = 0;
409 Nodes[
Source].FracFlow = 1.0;
410 for (
uint64_t Src : AugmentingOrder) {
412 "incorrectly computed fractional flow");
414 uint64_t Degree = AugmentingEdges[Src].size();
415 for (
auto &Edge : AugmentingEdges[Src]) {
416 double EdgeFlow = Nodes[Src].FracFlow / Degree;
417 Nodes[Edge->Dst].FracFlow += EdgeFlow;
418 if (Edge->Capacity ==
INF)
420 uint64_t MaxIntFlow =
double(Edge->Capacity - Edge->Flow) / EdgeFlow;
421 MaxFlowAmount =
std::min(MaxFlowAmount, MaxIntFlow);
425 if (MaxFlowAmount == 0)
429 Nodes[
Source].IntFlow = MaxFlowAmount;
430 for (
uint64_t Src : AugmentingOrder) {
435 uint64_t Degree = AugmentingEdges[Src].size();
437 uint64_t SuccFlow = (Nodes[Src].IntFlow + Degree - 1) / Degree;
438 for (
auto &Edge : AugmentingEdges[Src]) {
442 Nodes[Dst].IntFlow += EdgeFlow;
443 Nodes[Src].IntFlow -= EdgeFlow;
444 Edge->AugmentedFlow += EdgeFlow;
448 Nodes[
Target].IntFlow = 0;
453 for (
size_t Idx = AugmentingOrder.size() - 1; Idx > 0; Idx--) {
454 uint64_t Src = AugmentingOrder[Idx - 1];
457 for (
auto &Edge : AugmentingEdges[Src]) {
459 if (Nodes[Dst].IntFlow == 0)
462 Nodes[Dst].IntFlow -= EdgeFlow;
463 Nodes[Src].IntFlow += EdgeFlow;
464 Edge->AugmentedFlow -= EdgeFlow;
469 bool HasSaturatedEdges =
false;
470 for (
uint64_t Src : AugmentingOrder) {
473 for (
auto &Edge : AugmentingEdges[Src]) {
474 assert(
uint64_t(Edge->Capacity - Edge->Flow) >= Edge->AugmentedFlow);
476 auto &RevEdge = Edges[Edge->Dst][Edge->RevEdgeIndex];
477 Edge->Flow += Edge->AugmentedFlow;
478 RevEdge.Flow -= Edge->AugmentedFlow;
479 if (Edge->Capacity == Edge->Flow && Edge->AugmentedFlow > 0)
480 HasSaturatedEdges =
true;
485 return HasSaturatedEdges;
489 void identifyShortestEdges(
uint64_t PathCapacity) {
490 assert(PathCapacity > 0 &&
"found an incorrect augmenting DAG");
498 for (
size_t Src = 0; Src < Nodes.size(); Src++) {
500 if (Nodes[Src].Distance > Nodes[
Target].Distance)
503 for (
auto &Edge : Edges[Src]) {
505 Edge.OnShortestPath =
507 Nodes[Dst].Distance <= Nodes[
Target].Distance &&
508 Nodes[Dst].Distance == Nodes[Src].Distance + Edge.Cost &&
509 Edge.Capacity > Edge.Flow &&
510 uint64_t(Edge.Capacity - Edge.Flow) >= MinCapacity;
560 std::vector<Node> Nodes;
562 std::vector<std::vector<Edge>> Edges;
568 std::vector<std::vector<Edge *>> AugmentingEdges;
571 constexpr int64_t MinCostMaxFlow::AuxCostUnlikely;
572 constexpr
uint64_t MinCostMaxFlow::MinBaseDistance;
593 assert(Func.Blocks[Func.Entry].isEntry() &&
594 "incorrect index of the entry block");
600 joinIsolatedComponents();
603 rebalanceUnknownSubgraphs();
607 void joinIsolatedComponents() {
609 auto Visited =
BitVector(NumBlocks(),
false);
610 findReachable(Func.Entry, Visited);
614 auto &Block = Func.Blocks[
I];
615 if (Block.Flow > 0 && !Visited[
I]) {
617 auto Path = findShortestPath(
I);
619 assert(Path.size() > 0 && Path[0]->Source == Func.Entry &&
620 "incorrectly computed path adjusting control flow");
621 Func.Blocks[Func.Entry].Flow += 1;
622 for (
auto &Jump : Path) {
624 Func.Blocks[Jump->Target].Flow += 1;
626 findReachable(Jump->Target, Visited);
637 std::queue<uint64_t> Queue;
640 while (!Queue.empty()) {
643 for (
auto Jump : Func.Blocks[Src].SuccJumps) {
645 if (Jump->Flow > 0 && !Visited[Dst]) {
655 std::vector<FlowJump *> findShortestPath(
uint64_t BlockIdx) {
657 auto ForwardPath = findShortestPath(Func.Entry, BlockIdx);
659 auto BackwardPath = findShortestPath(BlockIdx, AnyExitBlock);
662 std::vector<FlowJump *> Result;
663 Result.insert(Result.end(), ForwardPath.begin(), ForwardPath.end());
664 Result.insert(Result.end(), BackwardPath.begin(), BackwardPath.end());
674 return std::vector<FlowJump *>();
675 if (Func.Blocks[
Source].isExit() &&
Target == AnyExitBlock)
676 return std::vector<FlowJump *>();
679 auto Distance = std::vector<int64_t>(NumBlocks(),
INF);
680 auto Parent = std::vector<FlowJump *>(NumBlocks(),
nullptr);
682 std::set<std::pair<uint64_t, uint64_t>> Queue;
686 while (!Queue.empty()) {
687 uint64_t Src = Queue.begin()->second;
688 Queue.erase(Queue.begin());
691 (Func.Blocks[Src].isExit() &&
Target == AnyExitBlock))
694 for (
auto Jump : Func.Blocks[Src].SuccJumps) {
696 int64_t JumpDist = jumpDistance(Jump);
697 if (Distance[Dst] > Distance[Src] + JumpDist) {
698 Queue.erase(std::make_pair(Distance[Dst], Dst));
700 Distance[Dst] = Distance[Src] + JumpDist;
703 Queue.insert(std::make_pair(Distance[Dst], Dst));
708 if (
Target == AnyExitBlock) {
710 if (Func.Blocks[
I].isExit() && Parent[
I] !=
nullptr) {
711 if (
Target == AnyExitBlock || Distance[
Target] > Distance[
I]) {
717 assert(Parent[
Target] !=
nullptr &&
"a path does not exist");
720 std::vector<FlowJump *> Result;
723 assert(Now == Parent[Now]->
Target &&
"incorrect parent jump");
724 Result.push_back(Parent[Now]);
725 Now = Parent[Now]->Source;
741 int64_t jumpDistance(
FlowJump *Jump)
const {
744 std::min(Func.Blocks[Func.Entry].Flow,
745 MinCostMaxFlow::AuxCostUnlikely / NumBlocks()));
747 return MinCostMaxFlow::AuxCostUnlikely;
749 return BaseDistance + BaseDistance / Jump->
Flow;
750 return BaseDistance * NumBlocks();
753 uint64_t NumBlocks()
const {
return Func.Blocks.size(); }
759 void rebalanceUnknownSubgraphs() {
761 for (
uint64_t I = 0;
I < Func.Blocks.size();
I++) {
762 auto SrcBlock = &Func.Blocks[
I];
764 if (!canRebalanceAtRoot(SrcBlock))
769 std::vector<FlowBlock *> UnknownBlocks;
770 std::vector<FlowBlock *> KnownDstBlocks;
771 findUnknownSubgraph(SrcBlock, KnownDstBlocks, UnknownBlocks);
776 if (!canRebalanceSubgraph(SrcBlock, KnownDstBlocks, UnknownBlocks,
781 if (!isAcyclicSubgraph(SrcBlock, DstBlock, UnknownBlocks))
785 rebalanceUnknownSubgraph(SrcBlock, DstBlock, UnknownBlocks);
790 bool canRebalanceAtRoot(
const FlowBlock *SrcBlock) {
797 bool HasUnknownSuccs =
false;
799 if (Func.Blocks[Jump->
Target].UnknownWeight) {
800 HasUnknownSuccs =
true;
804 if (!HasUnknownSuccs)
812 void findUnknownSubgraph(
const FlowBlock *SrcBlock,
813 std::vector<FlowBlock *> &KnownDstBlocks,
814 std::vector<FlowBlock *> &UnknownBlocks) {
817 auto Visited =
BitVector(NumBlocks(),
false);
818 std::queue<uint64_t> Queue;
820 Queue.push(SrcBlock->
Index);
821 Visited[SrcBlock->
Index] =
true;
822 while (!Queue.empty()) {
823 auto &Block = Func.Blocks[Queue.front()];
826 for (
auto Jump : Block.SuccJumps) {
828 if (ignoreJump(SrcBlock,
nullptr, Jump))
837 if (!Func.Blocks[Dst].UnknownWeight) {
838 KnownDstBlocks.
push_back(&Func.Blocks[Dst]);
841 UnknownBlocks.push_back(&Func.Blocks[Dst]);
849 bool canRebalanceSubgraph(
const FlowBlock *SrcBlock,
850 const std::vector<FlowBlock *> &KnownDstBlocks,
851 const std::vector<FlowBlock *> &UnknownBlocks,
854 if (UnknownBlocks.empty())
858 if (KnownDstBlocks.size() > 1)
860 DstBlock = KnownDstBlocks.empty() ? nullptr : KnownDstBlocks.front();
863 for (
auto Block : UnknownBlocks) {
864 if (Block->SuccJumps.empty()) {
866 if (DstBlock !=
nullptr)
870 size_t NumIgnoredJumps = 0;
871 for (
auto Jump : Block->SuccJumps) {
872 if (ignoreJump(SrcBlock, DstBlock, Jump))
877 if (NumIgnoredJumps == Block->SuccJumps.size())
892 auto JumpSource = &Func.Blocks[Jump->
Source];
893 auto JumpTarget = &Func.Blocks[Jump->
Target];
896 if (DstBlock !=
nullptr && JumpTarget == DstBlock)
900 if (!JumpTarget->UnknownWeight && JumpSource == SrcBlock)
904 if (!JumpTarget->UnknownWeight && JumpTarget->Flow == 0)
913 std::vector<FlowBlock *> &UnknownBlocks) {
915 auto LocalInDegree = std::vector<uint64_t>(NumBlocks(), 0);
916 auto fillInDegree = [&](
const FlowBlock *Block) {
917 for (
auto Jump : Block->SuccJumps) {
918 if (ignoreJump(SrcBlock, DstBlock, Jump))
920 LocalInDegree[Jump->
Target]++;
923 fillInDegree(SrcBlock);
924 for (
auto Block : UnknownBlocks) {
928 if (LocalInDegree[SrcBlock->
Index] > 0)
931 std::vector<FlowBlock *> AcyclicOrder;
932 std::queue<uint64_t> Queue;
933 Queue.push(SrcBlock->
Index);
934 while (!Queue.empty()) {
935 FlowBlock *Block = &Func.Blocks[Queue.front()];
938 if (DstBlock !=
nullptr && Block == DstBlock)
942 if (Block->UnknownWeight && Block != SrcBlock)
943 AcyclicOrder.push_back(Block);
946 for (
auto Jump : Block->SuccJumps) {
947 if (ignoreJump(SrcBlock, DstBlock, Jump))
950 LocalInDegree[Dst]--;
951 if (LocalInDegree[Dst] == 0) {
959 if (UnknownBlocks.size() != AcyclicOrder.size())
961 UnknownBlocks = AcyclicOrder;
967 void rebalanceUnknownSubgraph(
const FlowBlock *SrcBlock,
969 const std::vector<FlowBlock *> &UnknownBlocks) {
970 assert(SrcBlock->
Flow > 0 &&
"zero-flow block in unknown subgraph");
976 if (ignoreJump(SrcBlock, DstBlock, Jump))
978 BlockFlow += Jump->
Flow;
980 rebalanceBlock(SrcBlock, DstBlock, SrcBlock, BlockFlow);
983 for (
auto Block : UnknownBlocks) {
984 assert(Block->UnknownWeight &&
"incorrect unknown subgraph");
987 for (
auto Jump : Block->PredJumps) {
988 BlockFlow += Jump->
Flow;
990 Block->Flow = BlockFlow;
991 rebalanceBlock(SrcBlock, DstBlock, Block, BlockFlow);
1000 size_t BlockDegree = 0;
1001 for (
auto Jump : Block->SuccJumps) {
1002 if (ignoreJump(SrcBlock, DstBlock, Jump))
1007 if (DstBlock ==
nullptr && BlockDegree == 0)
1009 assert(BlockDegree > 0 &&
"all outgoing jumps are ignored");
1013 uint64_t SuccFlow = (BlockFlow + BlockDegree - 1) / BlockDegree;
1014 for (
auto Jump : Block->SuccJumps) {
1015 if (ignoreJump(SrcBlock, DstBlock, Jump))
1021 assert(BlockFlow == 0 &&
"not all flow is propagated");
1036 void initializeNetwork(MinCostMaxFlow &Network,
FlowFunction &Func) {
1037 uint64_t NumBlocks = Func.Blocks.size();
1038 assert(NumBlocks > 1 &&
"Too few blocks in a function");
1039 LLVM_DEBUG(
dbgs() <<
"Initializing profi for " << NumBlocks <<
" blocks\n");
1042 if (Func.Blocks[Func.Entry].Weight == 0) {
1043 Func.Blocks[Func.Entry].Weight = 1;
1053 Network.initialize(3 * NumBlocks + 4, S1,
T1);
1057 auto &Block = Func.Blocks[
B];
1058 assert((!Block.UnknownWeight || Block.Weight == 0 || Block.isEntry()) &&
1059 "non-zero weight of a block w/o weight except for an entry");
1065 if (Block.Weight > 0) {
1066 Network.addEdge(S1, Bout, Block.Weight, 0);
1067 Network.addEdge(
Bin,
T1, Block.Weight, 0);
1071 assert((!Block.isEntry() || !Block.isExit()) &&
1072 "a block cannot be an entry and an exit");
1073 if (Block.isEntry()) {
1074 Network.addEdge(
S,
Bin, 0);
1075 }
else if (Block.isExit()) {
1076 Network.addEdge(Bout,
T, 0);
1083 int64_t AuxCostInc = SampleProfileProfiCostInc;
1084 int64_t AuxCostDec = SampleProfileProfiCostDec;
1085 if (Block.UnknownWeight) {
1092 if (Block.Weight == 0) {
1093 AuxCostInc = SampleProfileProfiCostIncZero;
1096 if (Block.isEntry()) {
1097 AuxCostInc = SampleProfileProfiCostIncEntry;
1098 AuxCostDec = SampleProfileProfiCostDecEntry;
1103 if (Block.HasSelfEdge) {
1107 Network.addEdge(
Bin, Baux, AuxCostInc);
1108 Network.addEdge(Baux, Bout, AuxCostInc);
1109 if (Block.Weight > 0) {
1110 Network.addEdge(Bout, Baux, AuxCostDec);
1111 Network.addEdge(Baux,
Bin, AuxCostDec);
1116 for (
auto &Jump : Func.Jumps) {
1122 uint64_t Cost = Jump.IsUnlikely ? MinCostMaxFlow::AuxCostUnlikely : 0;
1123 Network.addEdge(SrcOut, DstIn, Cost);
1128 Network.addEdge(
T,
S, 0);
1133 uint64_t NumBlocks = Func.Blocks.size();
1136 for (
uint64_t Src = 0; Src < NumBlocks; Src++) {
1137 auto &Block = Func.Blocks[Src];
1140 for (
auto &Adj : Network.getFlow(SrcOut)) {
1142 int64_t DstFlow = Adj.second;
1143 bool IsAuxNode = (DstIn < 3 * NumBlocks && DstIn % 3 == 2);
1144 if (!IsAuxNode || Block.HasSelfEdge) {
1153 for (
auto &Jump : Func.Jumps) {
1160 Flow = Network.getFlow(SrcOut, DstIn);
1164 int64_t AuxFlow = Network.getFlow(SrcOut, SrcAux);
1176 const uint64_t NumBlocks = Func.Blocks.size();
1177 auto InFlow = std::vector<uint64_t>(NumBlocks, 0);
1178 auto OutFlow = std::vector<uint64_t>(NumBlocks, 0);
1179 for (
auto &Jump : Func.Jumps) {
1180 InFlow[Jump.Target] += Jump.Flow;
1181 OutFlow[Jump.Source] += Jump.Flow;
1187 auto &Block = Func.Blocks[
I];
1188 if (Block.isEntry()) {
1189 TotalInFlow += Block.Flow;
1190 assert(Block.Flow == OutFlow[
I] &&
"incorrectly computed control flow");
1191 }
else if (Block.isExit()) {
1192 TotalOutFlow += Block.Flow;
1193 assert(Block.Flow == InFlow[
I] &&
"incorrectly computed control flow");
1195 assert(Block.Flow == OutFlow[
I] &&
"incorrectly computed control flow");
1196 assert(Block.Flow == InFlow[
I] &&
"incorrectly computed control flow");
1199 assert(TotalInFlow == TotalOutFlow &&
"incorrectly computed control flow");
1204 auto PositiveFlowEdges = std::vector<std::vector<uint64_t>>(NumBlocks);
1205 for (
auto &Jump : Func.Jumps) {
1206 if (Jump.Flow > 0) {
1207 PositiveFlowEdges[Jump.Source].push_back(Jump.Target);
1212 std::queue<uint64_t> Queue;
1213 auto Visited =
BitVector(NumBlocks,
false);
1214 Queue.push(Func.Entry);
1215 Visited[Func.Entry] =
true;
1216 while (!Queue.empty()) {
1219 for (
uint64_t Dst : PositiveFlowEdges[Src]) {
1220 if (!Visited[Dst]) {
1222 Visited[Dst] =
true;
1230 auto &Block = Func.Blocks[
I];
1231 assert((Visited[
I] || Block.Flow == 0) &&
"an isolated flow component");
1241 auto InferenceNetwork = MinCostMaxFlow();
1242 initializeNetwork(InferenceNetwork, Func);
1243 InferenceNetwork.run();
1249 auto Adjuster = FlowAdjuster(Func);
1254 verifyWeights(Func);