0159a26744
Recursive functions are generally not inlined to avoid issues like infinite inlining or excessive code expansion. However, this conservative approach misses opportunities for optimization in cases where a recursive call is guaranteed to execute only once. This patch detects a scenario where a guarding branch condition of a recursive call will become false after the first iteration of the recursive function. If such a condition is met, and the recursion depth is confirmed to be one, the Inliner will now consider this recursive function for inlining. A new test case (`test/Transforms/Inline/inline-recursive-fn.ll`) has been added to verify this behaviour.
194 lines
8.2 KiB
LLVM
194 lines
8.2 KiB
LLVM
; NOTE: Assertions have been autogenerated by utils/update_test_checks.py UTC_ARGS: --version 5
|
|
; RUN: opt -S -passes='inline,instcombine' < %s | FileCheck %s
|
|
|
|
define float @inline_rec_true_successor(float %x, float %scale) {
|
|
; CHECK-LABEL: define float @inline_rec_true_successor(
|
|
; CHECK-SAME: float [[X:%.*]], float [[SCALE:%.*]]) {
|
|
; CHECK-NEXT: [[ENTRY:.*:]]
|
|
; CHECK-NEXT: [[CMP:%.*]] = fcmp olt float [[X]], 0.000000e+00
|
|
; CHECK-NEXT: br i1 [[CMP]], label %[[IF_THEN:.*]], label %[[IF_END:.*]]
|
|
; CHECK: [[COMMON_RET18:.*]]:
|
|
; CHECK-NEXT: [[COMMON_RET18_OP:%.*]] = phi float [ [[COMMON_RET18_OP_I:%.*]], %[[INLINE_REC_TRUE_SUCCESSOR_EXIT:.*]] ], [ [[MUL:%.*]], %[[IF_END]] ]
|
|
; CHECK-NEXT: ret float [[COMMON_RET18_OP]]
|
|
; CHECK: [[IF_THEN]]:
|
|
; CHECK-NEXT: br i1 false, label %[[IF_THEN_I:.*]], label %[[IF_END_I:.*]]
|
|
; CHECK: [[IF_THEN_I]]:
|
|
; CHECK-NEXT: br label %[[INLINE_REC_TRUE_SUCCESSOR_EXIT]]
|
|
; CHECK: [[IF_END_I]]:
|
|
; CHECK-NEXT: [[FNEG:%.*]] = fneg float [[X]]
|
|
; CHECK-NEXT: [[MUL_I:%.*]] = fmul float [[SCALE]], [[FNEG]]
|
|
; CHECK-NEXT: br label %[[INLINE_REC_TRUE_SUCCESSOR_EXIT]]
|
|
; CHECK: [[INLINE_REC_TRUE_SUCCESSOR_EXIT]]:
|
|
; CHECK-NEXT: [[COMMON_RET18_OP_I]] = phi float [ poison, %[[IF_THEN_I]] ], [ [[MUL_I]], %[[IF_END_I]] ]
|
|
; CHECK-NEXT: br label %[[COMMON_RET18]]
|
|
; CHECK: [[IF_END]]:
|
|
; CHECK-NEXT: [[MUL]] = fmul float [[X]], [[SCALE]]
|
|
; CHECK-NEXT: br label %[[COMMON_RET18]]
|
|
;
|
|
entry:
|
|
%cmp = fcmp olt float %x, 0.000000e+00
|
|
br i1 %cmp, label %if.then, label %if.end
|
|
|
|
common.ret18: ; preds = %if.then, %if.end
|
|
%common.ret18.op = phi float [ %call, %if.then ], [ %mul, %if.end ]
|
|
ret float %common.ret18.op
|
|
|
|
if.then: ; preds = %entry
|
|
%fneg = fneg float %x
|
|
%call = tail call float @inline_rec_true_successor(float %fneg, float %scale)
|
|
br label %common.ret18
|
|
|
|
if.end: ; preds = %entry
|
|
%mul = fmul float %x, %scale
|
|
br label %common.ret18
|
|
}
|
|
|
|
; Same as previous test except that the recursive callsite is in the false successor
|
|
define float @inline_rec_false_successor(float %x, float %scale) {
|
|
; CHECK-LABEL: define float @inline_rec_false_successor(
|
|
; CHECK-SAME: float [[Y:%.*]], float [[SCALE:%.*]]) {
|
|
; CHECK-NEXT: [[ENTRY:.*:]]
|
|
; CHECK-NEXT: [[CMP:%.*]] = fcmp uge float [[Y]], 0.000000e+00
|
|
; CHECK-NEXT: br i1 [[CMP]], label %[[IF_THEN:.*]], label %[[IF_END:.*]]
|
|
; CHECK: [[COMMON_RET18:.*]]:
|
|
; CHECK-NEXT: [[COMMON_RET18_OP:%.*]] = phi float [ [[MUL:%.*]], %[[IF_THEN]] ], [ [[COMMON_RET18_OP_I:%.*]], %[[INLINE_REC_FALSE_SUCCESSOR_EXIT:.*]] ]
|
|
; CHECK-NEXT: ret float [[COMMON_RET18_OP]]
|
|
; CHECK: [[IF_THEN]]:
|
|
; CHECK-NEXT: [[MUL]] = fmul float [[Y]], [[SCALE]]
|
|
; CHECK-NEXT: br label %[[COMMON_RET18]]
|
|
; CHECK: [[IF_END]]:
|
|
; CHECK-NEXT: br i1 true, label %[[IF_THEN_I:.*]], label %[[IF_END_I:.*]]
|
|
; CHECK: [[IF_THEN_I]]:
|
|
; CHECK-NEXT: [[FNEG:%.*]] = fneg float [[Y]]
|
|
; CHECK-NEXT: [[MUL_I:%.*]] = fmul float [[SCALE]], [[FNEG]]
|
|
; CHECK-NEXT: br label %[[INLINE_REC_FALSE_SUCCESSOR_EXIT]]
|
|
; CHECK: [[IF_END_I]]:
|
|
; CHECK-NEXT: br label %[[INLINE_REC_FALSE_SUCCESSOR_EXIT]]
|
|
; CHECK: [[INLINE_REC_FALSE_SUCCESSOR_EXIT]]:
|
|
; CHECK-NEXT: [[COMMON_RET18_OP_I]] = phi float [ [[MUL_I]], %[[IF_THEN_I]] ], [ poison, %[[IF_END_I]] ]
|
|
; CHECK-NEXT: br label %[[COMMON_RET18]]
|
|
;
|
|
entry:
|
|
%cmp = fcmp uge float %x, 0.000000e+00
|
|
br i1 %cmp, label %if.then, label %if.end
|
|
|
|
common.ret18: ; preds = %if.then, %if.end
|
|
%common.ret18.op = phi float [ %mul, %if.then ], [ %call, %if.end ]
|
|
ret float %common.ret18.op
|
|
|
|
if.then: ; preds = %entry
|
|
%mul = fmul float %x, %scale
|
|
br label %common.ret18
|
|
|
|
if.end: ; preds = %entry
|
|
%fneg = fneg float %x
|
|
%call = tail call float @inline_rec_false_successor(float %fneg, float %scale)
|
|
br label %common.ret18
|
|
}
|
|
|
|
; Test when the BR has Value not cmp instruction
|
|
define float @inline_rec_no_cmp(i1 %flag, float %scale) {
|
|
; CHECK-LABEL: define float @inline_rec_no_cmp(
|
|
; CHECK-SAME: i1 [[FLAG:%.*]], float [[SCALE:%.*]]) {
|
|
; CHECK-NEXT: [[ENTRY:.*:]]
|
|
; CHECK-NEXT: br i1 [[FLAG]], label %[[IF_THEN:.*]], label %[[IF_END:.*]]
|
|
; CHECK: [[IF_THEN]]:
|
|
; CHECK-NEXT: [[SUM:%.*]] = fadd float [[SCALE]], 5.000000e+00
|
|
; CHECK-NEXT: [[SUM1:%.*]] = fadd float [[SUM]], [[SCALE]]
|
|
; CHECK-NEXT: br label %[[COMMON_RET:.*]]
|
|
; CHECK: [[IF_END]]:
|
|
; CHECK-NEXT: [[SUM2:%.*]] = fadd float [[SCALE]], 5.000000e+00
|
|
; CHECK-NEXT: br label %[[COMMON_RET]]
|
|
; CHECK: [[COMMON_RET]]:
|
|
; CHECK-NEXT: [[COMMON_RET_RES:%.*]] = phi float [ [[SUM1]], %[[IF_THEN]] ], [ [[SUM2]], %[[IF_END]] ]
|
|
; CHECK-NEXT: ret float [[COMMON_RET_RES]]
|
|
;
|
|
entry:
|
|
br i1 %flag, label %if.then, label %if.end
|
|
if.then:
|
|
%res = tail call float @inline_rec_no_cmp(i1 false, float %scale)
|
|
%sum1 = fadd float %res, %scale
|
|
br label %common.ret
|
|
if.end:
|
|
%sum2 = fadd float %scale, 5.000000e+00
|
|
br label %common.ret
|
|
common.ret:
|
|
%common.ret.res = phi float [ %sum1, %if.then ], [ %sum2, %if.end ]
|
|
ret float %common.ret.res
|
|
}
|
|
|
|
define float @no_inline_rec(float %x, float %scale) {
|
|
; CHECK-LABEL: define float @no_inline_rec(
|
|
; CHECK-SAME: float [[Z:%.*]], float [[SCALE:%.*]]) {
|
|
; CHECK-NEXT: [[ENTRY:.*:]]
|
|
; CHECK-NEXT: [[CMP:%.*]] = fcmp olt float [[Z]], 5.000000e+00
|
|
; CHECK-NEXT: br i1 [[CMP]], label %[[IF_THEN:.*]], label %[[IF_END:.*]]
|
|
; CHECK: [[COMMON_RET18:.*]]:
|
|
; CHECK-NEXT: [[COMMON_RET18_OP:%.*]] = phi float [ [[FNEG1:%.*]], %[[IF_THEN]] ], [ [[MUL:%.*]], %[[IF_END]] ]
|
|
; CHECK-NEXT: ret float [[COMMON_RET18_OP]]
|
|
; CHECK: [[IF_THEN]]:
|
|
; CHECK-NEXT: [[FADD:%.*]] = fadd float [[Z]], 5.000000e+00
|
|
; CHECK-NEXT: [[CALL:%.*]] = tail call float @no_inline_rec(float [[FADD]], float [[SCALE]])
|
|
; CHECK-NEXT: [[FNEG1]] = fneg float [[CALL]]
|
|
; CHECK-NEXT: br label %[[COMMON_RET18]]
|
|
; CHECK: [[IF_END]]:
|
|
; CHECK-NEXT: [[MUL]] = fmul float [[Z]], [[SCALE]]
|
|
; CHECK-NEXT: br label %[[COMMON_RET18]]
|
|
;
|
|
entry:
|
|
%cmp = fcmp olt float %x, 5.000000e+00
|
|
br i1 %cmp, label %if.then, label %if.end
|
|
|
|
common.ret18: ; preds = %if.then, %if.end
|
|
%common.ret18.op = phi float [ %fneg1, %if.then ], [ %mul, %if.end ]
|
|
ret float %common.ret18.op
|
|
|
|
if.then: ; preds = %entry
|
|
%fadd = fadd float %x, 5.000000e+00
|
|
%call = tail call float @no_inline_rec(float %fadd, float %scale)
|
|
%fneg1 = fneg float %call
|
|
br label %common.ret18
|
|
|
|
if.end: ; preds = %entry
|
|
%mul = fmul float %x, %scale
|
|
br label %common.ret18
|
|
}
|
|
|
|
; Test when the icmp can be simplified but the recurison depth is NOT 1,
|
|
; so the recursive call will not be inlined.
|
|
define float @no_inline_rec_depth_not_1(float %x, float %scale) {
|
|
; CHECK-LABEL: define float @no_inline_rec_depth_not_1(
|
|
; CHECK-SAME: float [[X:%.*]], float [[SCALE:%.*]]) {
|
|
; CHECK-NEXT: [[ENTRY:.*:]]
|
|
; CHECK-NEXT: [[CMP:%.*]] = fcmp olt float [[X]], 0.000000e+00
|
|
; CHECK-NEXT: br i1 [[CMP]], label %[[IF_THEN:.*]], label %[[IF_END:.*]]
|
|
; CHECK: [[COMMON_RET18:.*]]:
|
|
; CHECK-NEXT: [[COMMON_RET18_OP:%.*]] = phi float [ [[CALL:%.*]], %[[IF_THEN]] ], [ [[MUL:%.*]], %[[IF_END]] ]
|
|
; CHECK-NEXT: ret float [[COMMON_RET18_OP]]
|
|
; CHECK: [[IF_THEN]]:
|
|
; CHECK-NEXT: [[CALL]] = tail call float @no_inline_rec_depth_not_1(float [[X]], float [[SCALE]])
|
|
; CHECK-NEXT: br label %[[COMMON_RET18]]
|
|
; CHECK: [[IF_END]]:
|
|
; CHECK-NEXT: [[MUL]] = fmul float [[X]], [[SCALE]]
|
|
; CHECK-NEXT: br label %[[COMMON_RET18]]
|
|
;
|
|
entry:
|
|
%cmp = fcmp olt float %x, 0.000000e+00
|
|
br i1 %cmp, label %if.then, label %if.end
|
|
|
|
common.ret18: ; preds = %if.then, %if.end
|
|
%common.ret18.op = phi float [ %call, %if.then ], [ %mul, %if.end ]
|
|
ret float %common.ret18.op
|
|
|
|
if.then: ; preds = %entry
|
|
%fneg1 = fneg float %x
|
|
%fneg = fneg float %fneg1
|
|
%call = tail call float @no_inline_rec_depth_not_1(float %fneg, float %scale)
|
|
br label %common.ret18
|
|
|
|
if.end: ; preds = %entry
|
|
%mul = fmul float %x, %scale
|
|
br label %common.ret18
|
|
}
|
|
|