291 lines · plain
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 %s2; 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=CHECK23 4; The test contains a "diamond" and a "triangle" that needs to be rebalanced5; after basic profile inference.6;7; +----------------+8; | b11 [?] |9; +----------------+10; |11; v12; +----------+ +----------------+13; | b13 [10] | <-- | b12 [65536] |14; +----------+ +----------------+15; |16; v17; +----------+ +----------------+18; | b16 [?] | <-- | b14 [65536] |19; +----------+ +----------------+20; | |21; | v22; | +----------------+23; | | b15 [?] |24; | +----------------+25; | |26; | v27; | +----------------+28; +------------> | b17 [65536] | -+29; +----------------+ |30; | |31; v |32; +----------------+ |33; | b18 [?] | |34; +----------------+ |35; | |36; v |37; +----------------+ |38; | b19 [65536] | <+39; +----------------+40; |41; v42; +----------------+43; | b110 [65536] |44; +----------------+45 46@yydebug = dso_local global i32 0, align 447 48; Function Attrs: nounwind uwtable49define 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, 053 br label %b1254; CHECK2: - b11: float = {{.*}}, int = {{.*}}, count = 6554655 56b12:57 call void @llvm.pseudoprobe(i64 -5758218299531803684, i64 2, i32 0, i64 -1)58 br i1 %cmp, label %b14, label %b1359; CHECK2: - b12: float = {{.*}}, int = {{.*}}, count = 6554660 61b13:62 call void @llvm.pseudoprobe(i64 -5758218299531803684, i64 3, i32 0, i64 -1)63 ret i32 %164; CHECK2: - b13: float = {{.*}}, int = {{.*}}, count = 1065 66b14:67 call void @llvm.pseudoprobe(i64 -5758218299531803684, i64 4, i32 0, i64 -1)68 br i1 %cmp, label %b15, label %b1669; 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 = 6553672 73b15:74 call void @llvm.pseudoprobe(i64 -5758218299531803684, i64 5, i32 0, i64 -1)75 br label %b1776; CHECK2: - b15: float = {{.*}}, int = {{.*}}, count = 3276877 78b16:79 call void @llvm.pseudoprobe(i64 -5758218299531803684, i64 6, i32 0, i64 -1)80 br label %b1781; CHECK2: - b16: float = {{.*}}, int = {{.*}}, count = 3276882 83b17:84 call void @llvm.pseudoprobe(i64 -5758218299531803684, i64 7, i32 0, i64 -1)85 br i1 %cmp, label %b18, label %b1986; 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 = 6553689 90b18:91 call void @llvm.pseudoprobe(i64 -5758218299531803684, i64 8, i32 0, i64 -1)92 br label %b1993; CHECK2: - b18: float = {{.*}}, int = {{.*}}, count = 3276894 95b19:96 call void @llvm.pseudoprobe(i64 -5758218299531803684, i64 9, i32 0, i64 -1)97 br label %b11098; CHECK2: - b19: float = {{.*}}, int = {{.*}}, count = 6553699 100b110:101 call void @llvm.pseudoprobe(i64 -5758218299531803684, i64 10, i32 0, i64 -1)102 ret i32 %1103; CHECK2: - b110: float = {{.*}}, int = {{.*}}, count = 65536104}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, 0141 br i1 %cmp, label %b1, label %b5142; 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 = 2100145 146b1:147 call void @llvm.pseudoprobe(i64 2506109673213838996, i64 2, i32 0, i64 -1)148 br i1 %cmp, label %b2, label %b3149; 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 = 2000152 153b2:154 call void @llvm.pseudoprobe(i64 2506109673213838996, i64 3, i32 0, i64 -1)155 br i1 %cmp, label %b3, label %b4156; 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 = 1000159 160b3:161 call void @llvm.pseudoprobe(i64 2506109673213838996, i64 4, i32 0, i64 -1)162 br label %b5163; CHECK: edge %b3 -> %b5 probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge]164; CHECK2: - b3: float = {{.*}}, int = {{.*}}, count = 1500165 166b4:167 call void @llvm.pseudoprobe(i64 2506109673213838996, i64 5, i32 0, i64 -1)168 br label %b5169; CHECK: edge %b4 -> %b5 probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge]170; CHECK2: - b4: float = {{.*}}, int = {{.*}}, count = 500171 172b5:173 call void @llvm.pseudoprobe(i64 2506109673213838996, i64 6, i32 0, i64 -1)174 ret i32 %1175; CHECK2: - b5: float = {{.*}}, int = {{.*}}, count = 2100176 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; v189; +---------+ +-----------+190; | b34 [?] | <-- | b32 [100] |191; +---------+ +-----------+192; |193; |194; v195; +-----------+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 %b32203; CHECK2: - b31: float = {{.*}}, int = {{.*}}, count = 100204 205b32:206 call void @llvm.pseudoprobe(i64 -544905447084884130, i64 2, i32 0, i64 -1)207 %cmp = icmp ne i32 %0, 0208 br i1 %cmp, label %b34, label %b33209; 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 = 100212 213b33:214 call void @llvm.pseudoprobe(i64 -544905447084884130, i64 3, i32 0, i64 -1)215 ret i32 %1216; CHECK2: - b33: float = {{.*}}, int = {{.*}}, count = 100217 218b34:219 call void @llvm.pseudoprobe(i64 -544905447084884130, i64 4, i32 0, i64 -1)220 ret i32 %1221; CHECK2: - b34: float = {{.*}}, int = {{.*}}, count = 0222 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; | | v233; | | +-----------+234; | | | b41 [50] |235; | | +-----------+236; | | |237; | | |238; | | v239; | | +-----------+240; | +------------> | b43 [?] |241; | +-----------+242; | |243; | |244; | v245; | +-----------+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, 0253 br i1 %cmp, label %b41, label %b42254; CHECK2: - b40: float = {{.*}}, int = {{.*}}, count = 100255 256b41:257 call void @llvm.pseudoprobe(i64 -2989539179265513123, i64 2, i32 0, i64 -1)258 br label %b43259; CHECK2: - b41: float = {{.*}}, int = {{.*}}, count = 50260 261b42:262 call void @llvm.pseudoprobe(i64 -2989539179265513123, i64 3, i32 0, i64 -1)263 br i1 %cmp, label %b43, label %b44264; 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 = 50267 268b43:269 call void @llvm.pseudoprobe(i64 -2989539179265513123, i64 4, i32 0, i64 -1)270 br label %b44271; CHECK2: - b43: float = {{.*}}, int = {{.*}}, count = 75272 273b44:274 call void @llvm.pseudoprobe(i64 -2989539179265513123, i64 5, i32 0, i64 -1)275 ret i32 %1276; CHECK2: - b44: float = {{.*}}, int = {{.*}}, count = 100277}278 279; Function Attrs: inaccessiblememonly nounwind willreturn280declare void @llvm.pseudoprobe(i64, i64, i32, i64) #4281 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