419 lines · plain
1; RUN: opt < %s -passes='print<block-freq>' -disable-output 2>&1 | FileCheck %s2 3; A loop with multiple exits isn't irreducible. It should be handled4; correctly.5;6; CHECK-LABEL: Printing analysis {{.*}} for function 'multiexit':7; CHECK-NEXT: block-frequency-info: multiexit8define void @multiexit(i1 %x) {9; CHECK-NEXT: entry: float = 1.0, int = [[ENTRY:[0-9]+]]10entry:11 br label %loop.112 13; CHECK-NEXT: loop.1: float = 2.0,14loop.1:15 br i1 %x, label %exit.1, label %loop.2, !prof !016 17; CHECK-NEXT: loop.2: float = 1.75,18loop.2:19 br i1 %x, label %exit.2, label %loop.1, !prof !120 21; CHECK-NEXT: exit.1: float = 0.25,22exit.1:23 br label %return24 25; CHECK-NEXT: exit.2: float = 0.75,26exit.2:27 br label %return28 29; CHECK-NEXT: return: float = 1.0, int = [[ENTRY]]30return:31 ret void32}33 34!0 = !{!"branch_weights", i32 1, i32 7}35!1 = !{!"branch_weights", i32 3, i32 4}36 37; Irreducible control flow38; ========================39;40; LoopInfo defines a loop as a non-trivial SCC dominated by a single block,41; called the header. A given loop, L, can have sub-loops, which are loops42; within the subgraph of L that excludes the header.43;44; In addition to loops, -block-freq has limited support for irreducible SCCs,45; which are SCCs with multiple entry blocks. Irreducible SCCs are discovered46; on the fly, and modelled as loops with multiple headers.47;48; The headers of irreducible sub-SCCs consist of its entry blocks and all nodes49; that are targets of a backedge within it (excluding backedges within true50; sub-loops).51;52; -block-freq is currently designed to act like a block is inserted that53; intercepts all the edges to the headers. All backedges and entries point to54; this block. Its successors are the headers, which split the frequency55; evenly.56;57; There are a number of testcases below. Only the first two have detailed58; explanations.59;60; Testcase #161; ===========62;63; In this case c1 and c2 should have frequencies of 15/7 and 13/7,64; respectively. To calculate this, consider assigning 1.0 to entry, and65; distributing frequency iteratively (to infinity). At the first iteration,66; entry gives 3/4 to c1 and 1/4 to c2. At every step after, c1 and c2 give 3/467; of what they have to each other. Somehow, all of it comes out to exit.68;69; c1 = 3/4 + 1/4*3/4 + 3/4*3^2/4^2 + 1/4*3^3/4^3 + 3/4*3^3/4^3 + ...70; c2 = 1/4 + 3/4*3/4 + 1/4*3^2/4^2 + 3/4*3^3/4^3 + 1/4*3^3/4^3 + ...71;72; Simplify by splitting up the odd and even terms of the series and taking out73; factors so that the infite series matches:74;75; c1 = 3/4 *(9^0/16^0 + 9^1/16^1 + 9^2/16^2 + ...)76; + 3/16*(9^0/16^0 + 9^1/16^1 + 9^2/16^2 + ...)77; c2 = 1/4 *(9^0/16^0 + 9^1/16^1 + 9^2/16^2 + ...)78; + 9/16*(9^0/16^0 + 9^1/16^1 + 9^2/16^2 + ...)79;80; c1 = 15/16*(9^0/16^0 + 9^1/16^1 + 9^2/16^2 + ...)81; c2 = 13/16*(9^0/16^0 + 9^1/16^1 + 9^2/16^2 + ...)82;83; Since this geometric series sums to 16/7:84;85; c1 = 15/786; c2 = 13/787;88; If we treat c1 and c2 as members of the same loop, the exit frequency of the89; loop as a whole is 1/4, so the loop scale should be 4. Summing c1 and c290; gives 28/7, or 4.0, which is nice confirmation of the math above.91;92; -block-freq currently treats the two nodes as equals.93define void @multientry(i1 %x) {94; CHECK-LABEL: Printing analysis {{.*}} for function 'multientry':95; CHECK-NEXT: block-frequency-info: multientry96entry:97; CHECK-NEXT: entry: float = 1.0, int = [[ENTRY:[0-9]+]]98 br i1 %x, label %c1, label %c2, !prof !299 100c1:101; CHECK-NEXT: c1: float = 2.0,102; The "correct" answer is: float = 2.142857{{[0-9]*}},103 br i1 %x, label %c2, label %exit, !prof !2104 105c2:106; CHECK-NEXT: c2: float = 2.0,107; The "correct" answer is: float = 1.857142{{[0-9]*}},108 br i1 %x, label %c1, label %exit, !prof !2109 110exit:111; CHECK-NEXT: exit: float = 1.0, int = [[ENTRY]]112 ret void113}114 115!2 = !{!"branch_weights", i32 3, i32 1}116 117; Testcase #2118; ===========119;120; In this case c1 and c2 should be treated as equals in a single loop. The121; exit frequency is 1/3, so the scaling factor for the loop should be 3.0. The122; loop is entered 2/3 of the time, and c1 and c2 split the total loop frequency123; evenly (1/2), so they should each have frequencies of 1.0 (3.0*2/3*1/2).124; Another way of computing this result is by assigning 1.0 to entry and showing125; that c1 and c2 should accumulate frequencies of:126;127; 1/3 + 2/9 + 4/27 + 8/81 + ...128; 2^0/3^1 + 2^1/3^2 + 2^2/3^3 + 2^3/3^4 + ...129;130; At the first step, c1 and c2 each get 1/3 of the entry. At each subsequent131; step, c1 and c2 each get 1/3 of what's left in c1 and c2 combined. This132; infinite series sums to 1.133define void @crossloops(i2 %x) {134; CHECK-LABEL: Printing analysis {{.*}} for function 'crossloops':135; CHECK-NEXT: block-frequency-info: crossloops136entry:137; CHECK-NEXT: entry: float = 1.0, int = [[ENTRY:[0-9]+]]138 switch i2 %x, label %exit [ i2 1, label %c1139 i2 2, label %c2 ], !prof !3140 141c1:142; CHECK-NEXT: c1: float = 1.0,143 switch i2 %x, label %exit [ i2 1, label %c1144 i2 2, label %c2 ], !prof !3145 146c2:147; CHECK-NEXT: c2: float = 1.0,148 switch i2 %x, label %exit [ i2 1, label %c1149 i2 2, label %c2 ], !prof !3150 151exit:152; CHECK-NEXT: exit: float = 1.0, int = [[ENTRY]]153 ret void154}155 156!3 = !{!"branch_weights", i32 2, i32 2, i32 2}157 158; A true loop with irreducible control flow inside.159define void @loop_around_irreducible(i1 %x) {160; CHECK-LABEL: Printing analysis {{.*}} for function 'loop_around_irreducible':161; CHECK-NEXT: block-frequency-info: loop_around_irreducible162entry:163; CHECK-NEXT: entry: float = 1.0, int = [[ENTRY:[0-9]+]]164 br label %loop165 166loop:167; CHECK-NEXT: loop: float = 4.0, int = [[HEAD:[0-9]+]]168 br i1 %x, label %left, label %right, !prof !4169 170left:171; CHECK-NEXT: left: float = 8.0,172 br i1 %x, label %right, label %loop.end, !prof !5173 174right:175; CHECK-NEXT: right: float = 8.0,176 br i1 %x, label %left, label %loop.end, !prof !5177 178loop.end:179; CHECK-NEXT: loop.end: float = 4.0, int = [[HEAD]]180 br i1 %x, label %loop, label %exit, !prof !5181 182exit:183; CHECK-NEXT: exit: float = 1.0, int = [[ENTRY]]184 ret void185}186!4 = !{!"branch_weights", i32 1, i32 1}187!5 = !{!"branch_weights", i32 3, i32 1}188 189; Two unrelated irreducible SCCs.190define void @two_sccs(i1 %x) {191; CHECK-LABEL: Printing analysis {{.*}} for function 'two_sccs':192; CHECK-NEXT: block-frequency-info: two_sccs193entry:194; CHECK-NEXT: entry: float = 1.0, int = [[ENTRY:[0-9]+]]195 br i1 %x, label %a, label %b, !prof !6196 197a:198; CHECK-NEXT: a: float = 0.75,199 br i1 %x, label %a.left, label %a.right, !prof !7200 201a.left:202; CHECK-NEXT: a.left: float = 1.5,203 br i1 %x, label %a.right, label %exit, !prof !6204 205a.right:206; CHECK-NEXT: a.right: float = 1.5,207 br i1 %x, label %a.left, label %exit, !prof !6208 209b:210; CHECK-NEXT: b: float = 0.25,211 br i1 %x, label %b.left, label %b.right, !prof !7212 213b.left:214; CHECK-NEXT: b.left: float = 0.625,215 br i1 %x, label %b.right, label %exit, !prof !8216 217b.right:218; CHECK-NEXT: b.right: float = 0.625,219 br i1 %x, label %b.left, label %exit, !prof !8220 221exit:222; CHECK-NEXT: exit: float = 1.0, int = [[ENTRY]]223 ret void224}225!6 = !{!"branch_weights", i32 3, i32 1}226!7 = !{!"branch_weights", i32 1, i32 1}227!8 = !{!"branch_weights", i32 4, i32 1}228 229; A true loop inside irreducible control flow.230define void @loop_inside_irreducible(i1 %x) {231; CHECK-LABEL: Printing analysis {{.*}} for function 'loop_inside_irreducible':232; CHECK-NEXT: block-frequency-info: loop_inside_irreducible233entry:234; CHECK-NEXT: entry: float = 1.0, int = [[ENTRY:[0-9]+]]235 br i1 %x, label %left, label %right, !prof !9236 237left:238; CHECK-NEXT: left: float = 2.0,239 br i1 %x, label %right, label %exit, !prof !10240 241right:242; CHECK-NEXT: right: float = 2.0, int = [[RIGHT:[0-9]+]]243 br label %loop244 245loop:246; CHECK-NEXT: loop: float = 6.0,247 br i1 %x, label %loop, label %right.end, !prof !11248 249right.end:250; CHECK-NEXT: right.end: float = 2.0, int = [[RIGHT]]251 br i1 %x, label %left, label %exit, !prof !10252 253exit:254; CHECK-NEXT: exit: float = 1.0, int = [[ENTRY]]255 ret void256}257!9 = !{!"branch_weights", i32 1, i32 1}258!10 = !{!"branch_weights", i32 3, i32 1}259!11 = !{!"branch_weights", i32 2, i32 1}260 261; Irreducible control flow in a branch that's in a true loop.262define void @loop_around_branch_with_irreducible(i1 %x) {263; CHECK-LABEL: Printing analysis {{.*}} for function 'loop_around_branch_with_irreducible':264; CHECK-NEXT: block-frequency-info: loop_around_branch_with_irreducible265entry:266; CHECK-NEXT: entry: float = 1.0, int = [[ENTRY:[0-9]+]]267 br label %loop268 269loop:270; CHECK-NEXT: loop: float = 2.0, int = [[LOOP:[0-9]+]]271 br i1 %x, label %normal, label %irreducible.entry, !prof !12272 273normal:274; CHECK-NEXT: normal: float = 1.5,275 br label %loop.end276 277irreducible.entry:278; CHECK-NEXT: irreducible.entry: float = 0.5, int = [[IRREDUCIBLE:[0-9]+]]279 br i1 %x, label %left, label %right, !prof !13280 281left:282; CHECK-NEXT: left: float = 1.0,283 br i1 %x, label %right, label %irreducible.exit, !prof !12284 285right:286; CHECK-NEXT: right: float = 1.0,287 br i1 %x, label %left, label %irreducible.exit, !prof !12288 289irreducible.exit:290; CHECK-NEXT: irreducible.exit: float = 0.5, int = [[IRREDUCIBLE]]291 br label %loop.end292 293loop.end:294; CHECK-NEXT: loop.end: float = 2.0, int = [[LOOP]]295 br i1 %x, label %loop, label %exit, !prof !13296 297exit:298; CHECK-NEXT: exit: float = 1.0, int = [[ENTRY]]299 ret void300}301!12 = !{!"branch_weights", i32 3, i32 1}302!13 = !{!"branch_weights", i32 1, i32 1}303 304; Irreducible control flow between two true loops.305define void @loop_around_branch_with_irreducible_around_loop(i1 %x) {306; CHECK-LABEL: Printing analysis {{.*}} for function 'loop_around_branch_with_irreducible_around_loop':307; CHECK-NEXT: block-frequency-info: loop_around_branch_with_irreducible_around_loop308entry:309; CHECK-NEXT: entry: float = 1.0, int = [[ENTRY:[0-9]+]]310 br label %loop311 312loop:313; CHECK-NEXT: loop: float = 3.0, int = [[LOOP:[0-9]+]]314 br i1 %x, label %normal, label %irreducible, !prof !14315 316normal:317; CHECK-NEXT: normal: float = 2.0,318 br label %loop.end319 320irreducible:321; CHECK-NEXT: irreducible: float = 1.0,322 br i1 %x, label %left, label %right, !prof !15323 324left:325; CHECK-NEXT: left: float = 2.0,326 br i1 %x, label %right, label %loop.end, !prof !16327 328right:329; CHECK-NEXT: right: float = 2.0, int = [[RIGHT:[0-9]+]]330 br label %right.loop331 332right.loop:333; CHECK-NEXT: right.loop: float = 10.0,334 br i1 %x, label %right.loop, label %right.end, !prof !17335 336right.end:337; CHECK-NEXT: right.end: float = 2.0, int = [[RIGHT]]338 br i1 %x, label %left, label %loop.end, !prof !16339 340loop.end:341; CHECK-NEXT: loop.end: float = 3.0, int = [[LOOP]]342 br i1 %x, label %loop, label %exit, !prof !14343 344exit:345; CHECK-NEXT: exit: float = 1.0, int = [[ENTRY]]346 ret void347}348!14 = !{!"branch_weights", i32 2, i32 1}349!15 = !{!"branch_weights", i32 1, i32 1}350!16 = !{!"branch_weights", i32 3, i32 1}351!17 = !{!"branch_weights", i32 4, i32 1}352 353; An irreducible SCC with a non-header.354define void @nonheader(i1 %x) {355; CHECK-LABEL: Printing analysis {{.*}} for function 'nonheader':356; CHECK-NEXT: block-frequency-info: nonheader357entry:358; CHECK-NEXT: entry: float = 1.0, int = [[ENTRY:[0-9]+]]359 br i1 %x, label %left, label %right, !prof !18360 361left:362; CHECK-NEXT: left: float = 1.0,363 br i1 %x, label %bottom, label %exit, !prof !19364 365right:366; CHECK-NEXT: right: float = 1.0,367 br i1 %x, label %bottom, label %exit, !prof !20368 369bottom:370; CHECK-NEXT: bottom: float = 1.0,371 br i1 %x, label %left, label %right, !prof !18372 373exit:374; CHECK-NEXT: exit: float = 1.0, int = [[ENTRY]]375 ret void376}377!18 = !{!"branch_weights", i32 1, i32 1}378!19 = !{!"branch_weights", i32 1, i32 3}379!20 = !{!"branch_weights", i32 3, i32 1}380 381; An irreducible SCC with an irreducible sub-SCC. In the current version of382; -block-freq, this means an extra header.383;384; This testcases uses non-trivial branch weights. The CHECK statements here385; will start to fail if we change -block-freq to be more accurate. Currently,386; loop headers are affected by the weight of their corresponding back edges.387define void @nonentry_header(i1 %x, i2 %y) {388; CHECK-LABEL: Printing analysis {{.*}} for function 'nonentry_header':389; CHECK-NEXT: block-frequency-info: nonentry_header390entry:391; CHECK-NEXT: entry: float = 1.0, int = [[ENTRY:[0-9]+]]392 br i1 %x, label %left, label %right, !prof !21393 394left:395; CHECK-NEXT: left: float = 0.14396 br i1 %x, label %top, label %bottom, !prof !22397 398right:399; CHECK-NEXT: right: float = 0.42400 br i1 %x, label %top, label %bottom, !prof !22401 402top:403; CHECK-NEXT: top: float = 8.43404 switch i2 %y, label %exit [ i2 0, label %left405 i2 1, label %right406 i2 2, label %bottom ], !prof !23407 408bottom:409; CHECK-NEXT: bottom: float = 4.5,410 br label %top411 412exit:413; CHECK-NEXT: exit: float = 1.0, int = [[ENTRY]]414 ret void415}416!21 = !{!"branch_weights", i32 2, i32 1}417!22 = !{!"branch_weights", i32 1, i32 1}418!23 = !{!"branch_weights", i32 8, i32 1, i32 3, i32 12}419