diff --git a/llvm/lib/Transforms/Scalar/LoopSink.cpp b/llvm/lib/Transforms/Scalar/LoopSink.cpp --- a/llvm/lib/Transforms/Scalar/LoopSink.cpp +++ b/llvm/lib/Transforms/Scalar/LoopSink.cpp @@ -177,13 +177,33 @@ SmallPtrSet BBs; for (auto &U : I.uses()) { Instruction *UI = cast(U.getUser()); - // We cannot sink I to PHI-uses. - if (isa(UI)) - return false; + // We cannot sink I if it has uses outside of the loop. if (!L.contains(LI.getLoopFor(UI->getParent()))) return false; - BBs.insert(UI->getParent()); + + if (!isa(UI)) { + BBs.insert(UI->getParent()); + continue; + } + + // We cannot sink I to PHI-uses, try to look through PHI to find the incoming + // block of the value being used. + PHINode *PN = dyn_cast(UI); + BasicBlock *PhiBB = nullptr; + for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) { + Value *PhiVal = PN->getIncomingValue(i); + if (PhiVal != U) + continue; + + // If value's incoming block is from loop preheader directly, there's no + // place to sink to, bailout. + PhiBB = PN->getIncomingBlock(i); + if (L.getLoopPreheader() == PhiBB) + return false; + + BBs.insert(PhiBB); + } } // findBBsToSinkInto is O(BBs.size() * ColdLoopBBs.size()). We cap the max diff --git a/llvm/test/Transforms/LICM/loopsink-phi.ll b/llvm/test/Transforms/LICM/loopsink-phi.ll new file mode 100644 --- /dev/null +++ b/llvm/test/Transforms/LICM/loopsink-phi.ll @@ -0,0 +1,142 @@ +; NOTE: Assertions have been autogenerated by utils/update_test_checks.py UTC_ARGS: --version 2 +; RUN: opt -S -verify-memoryssa -passes=loop-sink < %s | FileCheck %s +; Make sure that unprofitable loop ICM can be undone by loop sink, and loop sink can handle +; sinking through PHI use. + + +define dso_local i32 @_Z3fooii(i32 %arg, i32 %arg1) local_unnamed_addr #0 !prof !30 { +; CHECK-LABEL: define dso_local i32 @_Z3fooii +; CHECK-SAME: (i32 [[ARG:%.*]], i32 [[ARG1:%.*]]) local_unnamed_addr #[[ATTR0:[0-9]+]] !prof [[PROF30:![0-9]+]] { +; CHECK-NEXT: bb: +; CHECK-NEXT: [[I:%.*]] = tail call i32 @_Z3bari(i32 [[ARG1]]), !prof [[PROF31:![0-9]+]] +; CHECK-NEXT: [[I2:%.*]] = icmp eq i32 [[ARG]], 0 +; CHECK-NEXT: br i1 [[I2]], label [[DOTL_RET:%.*]], label [[DOTL_CHECK_PREHEADER:%.*]] +; CHECK: .l.check.preheader: +; CHECK-NEXT: br label [[DOTL_CHECK:%.*]] +; CHECK: .l.ret.loopexit: +; CHECK-NEXT: [[DOTLCSSA:%.*]] = phi i32 [ [[I10:%.*]], [[DOTL_ITERATE:%.*]] ] +; CHECK-NEXT: br label [[DOTL_RET]] +; CHECK: .l.ret: +; CHECK-NEXT: [[I3:%.*]] = phi i32 [ 0, [[BB:%.*]] ], [ [[DOTLCSSA]], [[DOTL_RET_LOOPEXIT:%.*]] ] +; CHECK-NEXT: ret i32 [[I3]] +; CHECK: .l.check: +; CHECK-NEXT: [[I4:%.*]] = phi i32 [ 0, [[DOTL_CHECK_PREHEADER]] ], [ [[I11:%.*]], [[DOTL_ITERATE]] ] +; CHECK-NEXT: [[I5:%.*]] = phi i32 [ [[ARG]], [[DOTL_CHECK_PREHEADER]] ], [ [[I10]], [[DOTL_ITERATE]] ] +; CHECK-NEXT: [[I6:%.*]] = icmp eq i32 [[I4]], [[ARG1]] +; CHECK-NEXT: br i1 [[I6]], label [[DOTL_COLD:%.*]], label [[DOTL_ITERATE]], !prof [[PROF32:![0-9]+]] +; CHECK: .l.cold: +; CHECK-NEXT: [[FLAG:%.*]] = icmp eq i32 [[ARG1]], 5 +; CHECK-NEXT: br i1 [[FLAG]], label [[DOTL_COLD1:%.*]], label [[DOTL_COLD2:%.*]] +; CHECK: .l.cold1: +; CHECK-NEXT: [[TMP1:%.*]] = mul nsw i32 [[I]], [[I]] +; CHECK-NEXT: br label [[DOTL_COLD3:%.*]] +; CHECK: .l.cold2: +; CHECK-NEXT: [[TMP2:%.*]] = add nsw i32 [[I]], [[I]] +; CHECK-NEXT: br label [[DOTL_COLD3]] +; CHECK: .l.cold3: +; CHECK-NEXT: [[I7:%.*]] = phi i32 [ [[TMP1]], [[DOTL_COLD1]] ], [ [[TMP2]], [[DOTL_COLD2]] ] +; CHECK-NEXT: [[I8:%.*]] = tail call i32 @_Z3bari(i32 [[I5]]) +; CHECK-NEXT: [[I9:%.*]] = add nsw i32 [[I8]], [[I7]] +; CHECK-NEXT: br label [[DOTL_ITERATE]] +; CHECK: .l.iterate: +; CHECK-NEXT: [[I10]] = phi i32 [ [[I9]], [[DOTL_COLD3]] ], [ [[I5]], [[DOTL_CHECK]] ] +; CHECK-NEXT: [[I11]] = add nuw nsw i32 [[I4]], 1 +; CHECK-NEXT: [[I12:%.*]] = icmp eq i32 [[I11]], [[I10]] +; CHECK-NEXT: br i1 [[I12]], label [[DOTL_RET_LOOPEXIT]], label [[DOTL_CHECK]], !llvm.loop [[LOOP33:![0-9]+]] +; +bb: + %i = tail call i32 @_Z3bari(i32 %arg1), !prof !31 + %i2 = icmp eq i32 %arg, 0 + br i1 %i2, label %.l.ret, label %.l.check.preheader + +.l.check.preheader: ; preds = %bb + %flag = icmp eq i32 %arg1, 5 + %tmp2 = add nsw i32 %i, %i + %tmp1 = mul nsw i32 %i, %i + br label %.l.check + +.l.ret.loopexit: ; preds = %.l.iterate + %.lcssa = phi i32 [ %i10, %.l.iterate ] + br label %.l.ret + +.l.ret: ; preds = %.l.ret.loopexit, %bb + %i3 = phi i32 [ 0, %bb ], [ %.lcssa, %.l.ret.loopexit ] + ret i32 %i3 + +.l.check: ; preds = %.l.iterate, %.l.check.preheader + %i4 = phi i32 [ 0, %.l.check.preheader ], [ %i11, %.l.iterate ] + %i5 = phi i32 [ %arg, %.l.check.preheader ], [ %i10, %.l.iterate ] + %i6 = icmp eq i32 %i4, %arg1 + br i1 %i6, label %.l.cold, label %.l.iterate, !prof !32 + +.l.cold: ; preds = %.l.check + br i1 %flag, label %.l.cold1, label %.l.cold2 + +.l.cold1: ; preds = %.l.cold + br label %.l.cold3 + +.l.cold2: ; preds = %.l.cold + br label %.l.cold3 + +.l.cold3: ; preds = %.l.cold2, %.l.cold1 + %i7 = phi i32 [ %tmp1, %.l.cold1 ], [ %tmp2, %.l.cold2 ] + %i8 = tail call i32 @_Z3bari(i32 %i5) + %i9 = add nsw i32 %i8, %i7 + br label %.l.iterate + +.l.iterate: ; preds = %.l.cold3, %.l.check + %i10 = phi i32 [ %i9, %.l.cold3 ], [ %i5, %.l.check ] + %i11 = add nuw nsw i32 %i4, 1 + %i12 = icmp eq i32 %i11, %i10 + br i1 %i12, label %.l.ret.loopexit, label %.l.check, !llvm.loop !33 +} + +declare dso_local i32 @_Z3bari(i32) local_unnamed_addr + +attributes #0 = { "use-sample-profile" } + +!llvm.module.flags = !{!0, !1} + +!0 = !{i32 2, !"Debug Info Version", i32 3} +!1 = !{i32 1, !"ProfileSummary", !2} +!2 = !{!3, !4, !5, !6, !7, !8, !9, !10, !11, !12} +!3 = !{!"ProfileFormat", !"SampleProfile"} +!4 = !{!"TotalCount", i64 403} +!5 = !{!"MaxCount", i64 200} +!6 = !{!"MaxInternalCount", i64 0} +!7 = !{!"MaxFunctionCount", i64 1} +!8 = !{!"NumCounts", i64 6} +!9 = !{!"NumFunctions", i64 1} +!10 = !{!"IsPartialProfile", i64 0} +!11 = !{!"PartialProfileRatio", double 0.000000e+00} +!12 = !{!"DetailedSummary", !13} +!13 = !{!14, !15, !16, !17, !18, !19, !20, !21, !22, !23, !24, !25, !26, !27, !28, !29} +!14 = !{i32 10000, i64 200, i32 2} +!15 = !{i32 100000, i64 200, i32 2} +!16 = !{i32 200000, i64 200, i32 2} +!17 = !{i32 300000, i64 200, i32 2} +!18 = !{i32 400000, i64 200, i32 2} +!19 = !{i32 500000, i64 200, i32 2} +!20 = !{i32 600000, i64 200, i32 2} +!21 = !{i32 700000, i64 200, i32 2} +!22 = !{i32 800000, i64 200, i32 2} +!23 = !{i32 900000, i64 200, i32 2} +!24 = !{i32 950000, i64 200, i32 2} +!25 = !{i32 990000, i64 200, i32 2} +!26 = !{i32 999000, i64 1, i32 5} +!27 = !{i32 999900, i64 1, i32 5} +!28 = !{i32 999990, i64 1, i32 5} +!29 = !{i32 999999, i64 1, i32 5} +!30 = !{!"function_entry_count", i64 2} +!31 = !{!"branch_weights", i32 2} +!32 = !{!"branch_weights", i32 1, i32 201} +!33 = distinct !{!33, !34, !42} +!34 = !DILocation(line: 4, column: 3, scope: !35) +!35 = distinct !DILexicalBlock(scope: !37, file: !36, line: 4, column: 3) +!36 = !DIFile(filename: "foo.cpp", directory: "/tmp/gather_pgo") +!37 = distinct !DISubprogram(name: "foo", linkageName: "_Z3fooii", scope: !36, file: !36, line: 2, type: !38, scopeLine: 2, flags: DIFlagPrototyped, spFlags: DISPFlagDefinition | DISPFlagOptimized, unit: !41) +!38 = !DISubroutineType(types: !39) +!39 = !{!40, !40, !40} +!40 = !DIBasicType(name: "int", size: 32, encoding: DW_ATE_signed) +!41 = distinct !DICompileUnit(language: DW_LANG_C_plus_plus, file: !36, producer: "clang version 8.0.20181009 ", isOptimized: true, runtimeVersion: 0, emissionKind: FullDebug, nameTableKind: None) +!42 = !DILocation(line: 6, column: 38, scope: !35)