1; RUN: opt < %s -passes=pseudo-probe,sample-profile -sample-profile-use-profi -sample-profile-file=%S/Inputs/profile-inference-rebalance.prof | opt -passes='print<branch-prob>' -disable-output 2>&1 | FileCheck %s 2; RUN: opt < %s -passes=pseudo-probe,sample-profile -sample-profile-use-profi -sample-profile-file=%S/Inputs/profile-inference-rebalance.prof | opt -passes='print<block-freq>' -disable-output 2>&1 | FileCheck %s --check-prefix=CHECK2 3 4; The test contains a "diamond" and a "triangle" that needs to be rebalanced 5; after basic profile inference. 6; 7; +----------------+ 8; | b11 [?] | 9; +----------------+ 10; | 11; v 12; +----------+ +----------------+ 13; | b13 [10] | <-- | b12 [65536] | 14; +----------+ +----------------+ 15; | 16; v 17; +----------+ +----------------+ 18; | b16 [?] | <-- | b14 [65536] | 19; +----------+ +----------------+ 20; | | 21; | v 22; | +----------------+ 23; | | b15 [?] | 24; | +----------------+ 25; | | 26; | v 27; | +----------------+ 28; +------------> | b17 [65536] | -+ 29; +----------------+ | 30; | | 31; v | 32; +----------------+ | 33; | b18 [?] | | 34; +----------------+ | 35; | | 36; v | 37; +----------------+ | 38; | b19 [65536] | <+ 39; +----------------+ 40; | 41; v 42; +----------------+ 43; | b110 [65536] | 44; +----------------+ 45 46@yydebug = dso_local global i32 0, align 4 47 48; Function Attrs: nounwind uwtable 49define dso_local i32 @countMultipliers(i32 %0, i32 %1) #0 { 50b11: 51 call void @llvm.pseudoprobe(i64 -5758218299531803684, i64 1, i32 0, i64 -1) 52 %cmp = icmp ne i32 %0, 0 53 br label %b12 54; CHECK2: - b11: float = {{.*}}, int = {{.*}}, count = 65546 55 56b12: 57 call void @llvm.pseudoprobe(i64 -5758218299531803684, i64 2, i32 0, i64 -1) 58 br i1 %cmp, label %b14, label %b13 59; CHECK2: - b12: float = {{.*}}, int = {{.*}}, count = 65546 60 61b13: 62 call void @llvm.pseudoprobe(i64 -5758218299531803684, i64 3, i32 0, i64 -1) 63 ret i32 %1 64; CHECK2: - b13: float = {{.*}}, int = {{.*}}, count = 10 65 66b14: 67 call void @llvm.pseudoprobe(i64 -5758218299531803684, i64 4, i32 0, i64 -1) 68 br i1 %cmp, label %b15, label %b16 69; CHECK: edge %b14 -> %b15 probability is 0x40000000 / 0x80000000 = 50.00% 70; CHECK: edge %b14 -> %b16 probability is 0x40000000 / 0x80000000 = 50.00% 71; CHECK2: - b14: float = {{.*}}, int = {{.*}}, count = 65536 72 73b15: 74 call void @llvm.pseudoprobe(i64 -5758218299531803684, i64 5, i32 0, i64 -1) 75 br label %b17 76; CHECK2: - b15: float = {{.*}}, int = {{.*}}, count = 32768 77 78b16: 79 call void @llvm.pseudoprobe(i64 -5758218299531803684, i64 6, i32 0, i64 -1) 80 br label %b17 81; CHECK2: - b16: float = {{.*}}, int = {{.*}}, count = 32768 82 83b17: 84 call void @llvm.pseudoprobe(i64 -5758218299531803684, i64 7, i32 0, i64 -1) 85 br i1 %cmp, label %b18, label %b19 86; CHECK: edge %b17 -> %b18 probability is 0x40000000 / 0x80000000 = 50.00% 87; CHECK: edge %b17 -> %b19 probability is 0x40000000 / 0x80000000 = 50.00% 88; CHECK2: - b17: float = {{.*}}, int = {{.*}}, count = 65536 89 90b18: 91 call void @llvm.pseudoprobe(i64 -5758218299531803684, i64 8, i32 0, i64 -1) 92 br label %b19 93; CHECK2: - b18: float = {{.*}}, int = {{.*}}, count = 32768 94 95b19: 96 call void @llvm.pseudoprobe(i64 -5758218299531803684, i64 9, i32 0, i64 -1) 97 br label %b110 98; CHECK2: - b19: float = {{.*}}, int = {{.*}}, count = 65536 99 100b110: 101 call void @llvm.pseudoprobe(i64 -5758218299531803684, i64 10, i32 0, i64 -1) 102 ret i32 %1 103; CHECK2: - b110: float = {{.*}}, int = {{.*}}, count = 65536 104} 105 106 107; The test contains a triangle comprised of dangling blocks. 108; 109; +-----------+ 110; | b0 [2100] | -+ 111; +-----------+ | 112; | | 113; | | 114; v | 115; +-----------+ | 116; +- | b1 [2000] | | 117; | +-----------+ | 118; | | | 119; | | | 120; | v | 121; +--------+ | +-----------+ | 122; | b4 [?] | <-----+- | b2 [?] | | 123; +--------+ | +-----------+ | 124; | | | | 125; | | | | 126; | | v | 127; | | +-----------+ | 128; | +> | b3 [?] | | 129; | +-----------+ | 130; | | | 131; | | | 132; | v | 133; | +-----------+ | 134; +---------------> | b5 [2100] | <+ 135; +-----------+ 136 137define dso_local i32 @countMultipliers2(i32 %0, i32 %1) #0 { 138b0: 139 call void @llvm.pseudoprobe(i64 2506109673213838996, i64 1, i32 0, i64 -1) 140 %cmp = icmp ne i32 %0, 0 141 br i1 %cmp, label %b1, label %b5 142; CHECK: edge %b0 -> %b1 probability is 0x79e79e7a / 0x80000000 = 95.24% [HOT edge] 143; CHECK: edge %b0 -> %b5 probability is 0x06186186 / 0x80000000 = 4.76% 144; CHECK2: - b0: float = {{.*}}, int = {{.*}}, count = 2100 145 146b1: 147 call void @llvm.pseudoprobe(i64 2506109673213838996, i64 2, i32 0, i64 -1) 148 br i1 %cmp, label %b2, label %b3 149; CHECK: edge %b1 -> %b2 probability is 0x40000000 / 0x80000000 = 50.00% 150; CHECK: edge %b1 -> %b3 probability is 0x40000000 / 0x80000000 = 50.00% 151; CHECK2: - b1: float = {{.*}}, int = {{.*}}, count = 2000 152 153b2: 154 call void @llvm.pseudoprobe(i64 2506109673213838996, i64 3, i32 0, i64 -1) 155 br i1 %cmp, label %b3, label %b4 156; CHECK: edge %b2 -> %b3 probability is 0x40000000 / 0x80000000 = 50.00% 157; CHECK: edge %b2 -> %b4 probability is 0x40000000 / 0x80000000 = 50.00% 158; CHECK2: - b2: float = {{.*}}, int = {{.*}}, count = 1000 159 160b3: 161 call void @llvm.pseudoprobe(i64 2506109673213838996, i64 4, i32 0, i64 -1) 162 br label %b5 163; CHECK: edge %b3 -> %b5 probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge] 164; CHECK2: - b3: float = {{.*}}, int = {{.*}}, count = 1500 165 166b4: 167 call void @llvm.pseudoprobe(i64 2506109673213838996, i64 5, i32 0, i64 -1) 168 br label %b5 169; CHECK: edge %b4 -> %b5 probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge] 170; CHECK2: - b4: float = {{.*}}, int = {{.*}}, count = 500 171 172b5: 173 call void @llvm.pseudoprobe(i64 2506109673213838996, i64 6, i32 0, i64 -1) 174 ret i32 %1 175; CHECK2: - b5: float = {{.*}}, int = {{.*}}, count = 2100 176 177} 178 179 180; The test contains a dangling subgraph that contains an exit dangling block. 181; No rebalancing is necessary here. 182; 183; +-----------+ 184; | b31 [100] | 185; +-----------+ 186; | 187; | 188; v 189; +---------+ +-----------+ 190; | b34 [?] | <-- | b32 [100] | 191; +---------+ +-----------+ 192; | 193; | 194; v 195; +-----------+ 196; | b33 [100] | 197; +-----------+ 198 199define dso_local i32 @countMultipliers3(i32 %0, i32 %1) #0 { 200b31: 201 call void @llvm.pseudoprobe(i64 -544905447084884130, i64 1, i32 0, i64 -1) 202 br label %b32 203; CHECK2: - b31: float = {{.*}}, int = {{.*}}, count = 100 204 205b32: 206 call void @llvm.pseudoprobe(i64 -544905447084884130, i64 2, i32 0, i64 -1) 207 %cmp = icmp ne i32 %0, 0 208 br i1 %cmp, label %b34, label %b33 209; CHECK: edge %b32 -> %b34 probability is 0x00000000 / 0x80000000 = 0.00% 210; CHECK: edge %b32 -> %b33 probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge] 211; CHECK2: - b32: float = {{.*}}, int = {{.*}}, count = 100 212 213b33: 214 call void @llvm.pseudoprobe(i64 -544905447084884130, i64 3, i32 0, i64 -1) 215 ret i32 %1 216; CHECK2: - b33: float = {{.*}}, int = {{.*}}, count = 100 217 218b34: 219 call void @llvm.pseudoprobe(i64 -544905447084884130, i64 4, i32 0, i64 -1) 220 ret i32 %1 221; CHECK2: - b34: float = {{.*}}, int = {{.*}}, count = 0 222 223} 224 225; Another dangling subgraph (b42, b43, b44) containing a single dangling block. 226; 227; +----------+ +-----------+ 228; +- | b42 [50] | <-- | b40 [100] | 229; | +----------+ +-----------+ 230; | | | 231; | | | 232; | | v 233; | | +-----------+ 234; | | | b41 [50] | 235; | | +-----------+ 236; | | | 237; | | | 238; | | v 239; | | +-----------+ 240; | +------------> | b43 [?] | 241; | +-----------+ 242; | | 243; | | 244; | v 245; | +-----------+ 246; +-----------------> | b44 [100] | 247; +-----------+ 248 249define dso_local i32 @countMultipliers4(i32 %0, i32 %1) #0 { 250b40: 251 call void @llvm.pseudoprobe(i64 -2989539179265513123, i64 1, i32 0, i64 -1) 252 %cmp = icmp ne i32 %0, 0 253 br i1 %cmp, label %b41, label %b42 254; CHECK2: - b40: float = {{.*}}, int = {{.*}}, count = 100 255 256b41: 257 call void @llvm.pseudoprobe(i64 -2989539179265513123, i64 2, i32 0, i64 -1) 258 br label %b43 259; CHECK2: - b41: float = {{.*}}, int = {{.*}}, count = 50 260 261b42: 262 call void @llvm.pseudoprobe(i64 -2989539179265513123, i64 3, i32 0, i64 -1) 263 br i1 %cmp, label %b43, label %b44 264; CHECK: edge %b42 -> %b43 probability is 0x40000000 / 0x80000000 = 50.00% 265; CHECK: edge %b42 -> %b44 probability is 0x40000000 / 0x80000000 = 50.00% 266; CHECK2: - b42: float = {{.*}}, int = {{.*}}, count = 50 267 268b43: 269 call void @llvm.pseudoprobe(i64 -2989539179265513123, i64 4, i32 0, i64 -1) 270 br label %b44 271; CHECK2: - b43: float = {{.*}}, int = {{.*}}, count = 75 272 273b44: 274 call void @llvm.pseudoprobe(i64 -2989539179265513123, i64 5, i32 0, i64 -1) 275 ret i32 %1 276; CHECK2: - b44: float = {{.*}}, int = {{.*}}, count = 100 277} 278 279; Function Attrs: inaccessiblememonly nounwind willreturn 280declare void @llvm.pseudoprobe(i64, i64, i32, i64) #4 281 282attributes #0 = { noinline nounwind uwtable "use-sample-profile" } 283attributes #4 = { inaccessiblememonly nounwind willreturn } 284 285!llvm.pseudo_probe_desc = !{!7, !8, !9, !10} 286 287!7 = !{i64 -5758218299531803684, i64 223598586707, !"countMultipliers", null} 288!8 = !{i64 2506109673213838996, i64 2235985, !"countMultipliers2", null} 289!9 = !{i64 -544905447084884130, i64 22985, !"countMultipliers3", null} 290!10 = !{i64 -2989539179265513123, i64 2298578, !"countMultipliers4", null} 291