Lines Matching +full:d3 +full:- +full:force
1 //===- LazyCallGraphTest.cpp - Unit tests for the lazy CG analysis --------===//
8 //===----------------------------------------------------------------------===//
41 IR forming a call graph with a diamond of triangle-shaped SCCs:
45 d3--d2
49 b3--b2 c3--c2
53 a3--a2
78 " call void @d3()\n"
114 " call void @d3()\n"
117 "define void @d3() {\n"
132 LazyCallGraph::Node &A1 = (I++)->getNode(CG); in TEST()
134 LazyCallGraph::Node &A2 = (I++)->getNode(CG); in TEST()
136 LazyCallGraph::Node &A3 = (I++)->getNode(CG); in TEST()
138 LazyCallGraph::Node &B1 = (I++)->getNode(CG); in TEST()
140 LazyCallGraph::Node &B2 = (I++)->getNode(CG); in TEST()
142 LazyCallGraph::Node &B3 = (I++)->getNode(CG); in TEST()
144 LazyCallGraph::Node &C1 = (I++)->getNode(CG); in TEST()
146 LazyCallGraph::Node &C2 = (I++)->getNode(CG); in TEST()
148 LazyCallGraph::Node &C3 = (I++)->getNode(CG); in TEST()
150 LazyCallGraph::Node &D1 = (I++)->getNode(CG); in TEST()
152 LazyCallGraph::Node &D2 = (I++)->getNode(CG); in TEST()
154 LazyCallGraph::Node &D3 = (I++)->getNode(CG); in TEST() local
155 EXPECT_EQ("d3", D3.getFunction().getName()); in TEST()
171 EXPECT_EQ("a3", A2.begin()->getFunction().getName()); in TEST()
173 EXPECT_EQ("a1", A3.begin()->getFunction().getName()); in TEST()
179 EXPECT_EQ("d3", Nodes[1]); in TEST()
183 EXPECT_EQ("b3", B2.begin()->getFunction().getName()); in TEST()
185 EXPECT_EQ("b1", B3.begin()->getFunction().getName()); in TEST()
195 EXPECT_EQ("c3", C2.begin()->getFunction().getName()); in TEST()
197 EXPECT_EQ("c1", C3.begin()->getFunction().getName()); in TEST()
200 EXPECT_EQ("d2", D1.begin()->getFunction().getName()); in TEST()
202 EXPECT_EQ("d3", D2.begin()->getFunction().getName()); in TEST()
203 EXPECT_EQ(D3.end(), std::next(D3.begin())); in TEST()
204 EXPECT_EQ("d1", D3.begin()->getFunction().getName()); in TEST()
217 EXPECT_EQ("d3", Nodes[2]); in TEST()
308 LazyCallGraph::Node &C = B.begin()->getNode(CG); in TEST()
313 EXPECT_EQ(&B, C.begin()->getNode()); in TEST()
317 EXPECT_EQ(&B, C.begin()->getNode()); in TEST()
318 EXPECT_EQ(&C, std::next(C.begin())->getNode()); in TEST()
322 EXPECT_EQ(&C, C.begin()->getNode()); in TEST()
350 // Now walk the four SCCs which should be in post-order. in TEST()
359 EXPECT_EQ("d3", Nodes[2]); in TEST()
429 // Force the graph to be fully expanded. in TEST()
479 // Force the graph to be fully expanded. in TEST()
587 // d3--d2 | in TEST()
591 // b3--b2 c3--c2 | in TEST()
595 // a3--a2 | in TEST()
600 // Force the graph to be fully expanded. in TEST()
615 LazyCallGraph::Node &D3 = *CG.lookup(lookupFunction(*M, "d3")); in TEST() local
627 ASSERT_EQ(&DRC, CG.lookupRefSCC(D3)); in TEST()
634 // d3--d2---. | in TEST()
638 // b3--b2 c3--c2 | in TEST()
642 // a3--a2 | in TEST()
646 if (E.getNode() == &D3) in TEST()
650 // And marked the D ref-SCC as no longer valid. in TEST()
666 EXPECT_EQ(&CRC, CG.lookupRefSCC(D3)); in TEST()
701 LazyCallGraph::Node &D3 = *CG.lookup(lookupFunction(*M, "d3")); in TEST() local
707 ASSERT_EQ(&DRC, CG.lookupRefSCC(D3)); in TEST()
713 if (E.getNode() == &D3) in TEST()
717 // And marked the D ref-SCC as no longer valid. in TEST()
727 EXPECT_EQ(&CRC, CG.lookupRefSCC(D3)); in TEST()
769 // Force the graph to be fully expanded. in TEST()
804 // The SCCs must be in *post-order* which means successors before in TEST()
832 // A nice fully connected (including self-edges) RefSCC. in TEST()
857 // Force the graph to be fully expanded. in TEST()
869 // Remove the edge from b -> a, which should leave the 3 functions still in in TEST()
870 // a single connected component because of a -> b -> c -> a. in TEST()
878 // Remove the edge from c -> a, which should leave 'a' in the original RefSCC in TEST()
891 // A nice fully connected (including self-edges) SCC (and RefSCC) in TEST()
915 // Force the graph to be fully expanded. in TEST()
930 // Remove the call edge from b -> a to a ref edge, which should leave the in TEST()
931 // 3 functions still in a single connected component because of a -> b -> in TEST()
932 // c -> a. in TEST()
939 // Remove the edge from c -> a, which should leave 'a' in the original SCC in TEST()
949 --J; in TEST()
953 // Remove the edge from c -> b, which should leave 'b' in the original SCC in TEST()
964 --J; in TEST()
966 --J; in TEST()
1002 // Force the graph to be fully expanded. in TEST()
1016 // Check the initial post-order. Note that B and C could be flipped here (and in TEST()
1024 // Switch the ref edge from A -> D to a call edge. This should have no in TEST()
1034 // Switch B -> C to a call edge. This doesn't form any new cycles but does in TEST()
1044 // Switch C -> B to a call edge. This forms a cycle and forces merging SCCs. in TEST()
1059 // Test for having a post-order prior to changing a ref edge to a call edge in TEST()
1114 // Force the graph to be fully expanded. in TEST()
1136 // Several call edges are initially present to force a particual post-order. in TEST()
1137 // Remove them now, leaving an interleaved post-order pattern. in TEST()
1144 // Check the initial post-order. We ensure this order with the extra edges in TEST()
1156 // Switch C3 -> B1 to a call edge. This doesn't form any new cycles but does in TEST()
1183 // To achieve this we construct a heavily connected graph to force in TEST()
1184 // a particular post-order. Then we remove the forcing edges and connect in TEST()
1187 // Diagram for the graph we want on the left and the graph we use to force in TEST()
1194 // | D | | C-D-E | in TEST()
1244 // Force the graph to be fully expanded. in TEST()
1264 // Remove the extra edges that were used to force a particular post-order. in TEST()
1268 // Check the initial post-order. We ensure this order with the extra edges in TEST()
1279 // Switch F -> B to a call edge. This merges B, D, and F into a single SCC, in TEST()
1285 // | D | -> B | in TEST()