shylie/llvm-project
1
0
Fork 0
Code Issues Pull Requests Actions Packages Projects Releases Wiki Activity
llvm-project/llvm/test/Transforms/InstCombine/branch.ll
Yingwei Zheng 380fa875ab
[InstCombine] Replace all dominated uses of condition with constants (#105510) 
This patch replaces all dominated uses of condition with true/false to
improve context-sensitive optimizations. It eliminates a bunch of
branches in llvm-opt-benchmark.

As a side effect, it may introduce new phi nodes in some corner cases.
See the following case:
```
define i1 @test(i1 %cmp, i1 %cond) {
entry:
   br i1 %cond, label %bb1, label %bb2
bb1:
   br i1 %cmp, label %if.then, label %if.else
if.then:
   br %bb2
if.else:
   br %bb2
bb2:
  %res = phi i1 [%cmp, %entry], [%cmp, %if.then], [%cmp, %if.else]
  ret i1 %res
}
```
It will be simplified into:
```
define i1 @test(i1 %cmp, i1 %cond) {
entry:
   br i1 %cond, label %bb1, label %bb2
bb1:
   br i1 %cmp, label %if.then, label %if.else
if.then:
   br %bb2
if.else:
   br %bb2
bb2:
  %res = phi i1 [%cmp, %entry], [true, %if.then], [false, %if.else]
  ret i1 %res
}
```

I am planning to fix this in late pipeline/CGP since this problem exists
before the patch.
2024-09-01 09:49:23 +08:00

341 lines
7.9 KiB
LLVM
Raw Permalink Blame History

; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
; RUN: opt -passes=instcombine -S < %s | FileCheck %s
declare void @use(i1)
; Check that we fold the condition of branches of the
; form: br <condition> dest1, dest2, where dest1 == dest2.
define i32 @test(i32 %x) {
; CHECK-LABEL: @test(
; CHECK-NEXT: entry:
; CHECK-NEXT: br i1 false, label [[MERGE:%.*]], label [[MERGE]]
; CHECK: merge:
; CHECK-NEXT: ret i32 [[X:%.*]]
;
entry:
%cmp = icmp ult i32 %x, 7
br i1 %cmp, label %merge, label %merge
merge:
ret i32 %x
}
@global = global i8 0
define i32 @pat(i32 %x) {
; CHECK-LABEL: @pat(
; CHECK-NEXT: br i1 false, label [[PATATINO:%.*]], label [[PATATINO]]
; CHECK: patatino:
; CHECK-NEXT: ret i32 [[X:%.*]]
;
%y = icmp eq i32 27, ptrtoint(ptr @global to i32)
br i1 %y, label %patatino, label %patatino
patatino:
ret i32 %x
}
define i1 @test01(i1 %cond) {
; CHECK-LABEL: @test01(
; CHECK-NEXT: entry:
; CHECK-NEXT: br i1 [[COND:%.*]], label [[IF_TRUE_1:%.*]], label [[IF_FALSE_1:%.*]]
; CHECK: if.true.1:
; CHECK-NEXT: br label [[MERGE_1:%.*]]
; CHECK: if.false.1:
; CHECK-NEXT: br label [[MERGE_1]]
; CHECK: merge.1:
; CHECK-NEXT: br i1 [[COND]], label [[IF_TRUE_2:%.*]], label [[IF_FALSE_2:%.*]]
; CHECK: if.true.2:
; CHECK-NEXT: br label [[MERGE_2:%.*]]
; CHECK: if.false.2:
; CHECK-NEXT: br label [[MERGE_2]]
; CHECK: merge.2:
; CHECK-NEXT: ret i1 [[COND]]
;
entry:
br i1 %cond, label %if.true.1, label %if.false.1
if.true.1:
br label %merge.1
if.false.1:
br label %merge.1
merge.1:
%merge.cond.1 = phi i1 [true, %if.true.1], [false, %if.false.1]
br i1 %merge.cond.1, label %if.true.2, label %if.false.2
if.true.2:
br label %merge.2
if.false.2:
br label %merge.2
merge.2:
%merge.cond.2 = phi i1 [true, %if.true.2], [false, %if.false.2]
ret i1 %merge.cond.2
}
define i1 @test02(i1 %cond) {
; CHECK-LABEL: @test02(
; CHECK-NEXT: entry:
; CHECK-NEXT: br i1 [[COND:%.*]], label [[IF_TRUE_1:%.*]], label [[IF_FALSE_1:%.*]]
; CHECK: if.true.1:
; CHECK-NEXT: br label [[MERGE_1:%.*]]
; CHECK: if.false.1:
; CHECK-NEXT: br label [[MERGE_1]]
; CHECK: merge.1:
; CHECK-NEXT: br i1 [[COND]], label [[IF_FALSE_2:%.*]], label [[IF_TRUE_2:%.*]]
; CHECK: if.true.2:
; CHECK-NEXT: br label [[MERGE_2:%.*]]
; CHECK: if.false.2:
; CHECK-NEXT: br label [[MERGE_2]]
; CHECK: merge.2:
; CHECK-NEXT: ret i1 [[COND]]
;
entry:
br i1 %cond, label %if.true.1, label %if.false.1
if.true.1:
br label %merge.1
if.false.1:
br label %merge.1
merge.1:
%merge.cond.1 = phi i1 [false, %if.true.1], [true, %if.false.1]
br i1 %merge.cond.1, label %if.true.2, label %if.false.2
if.true.2:
br label %merge.2
if.false.2:
br label %merge.2
merge.2:
%merge.cond.2 = phi i1 [false, %if.true.2], [true, %if.false.2]
ret i1 %merge.cond.2
}
; if (x && !y) ret 42; ret 3 --> if (!x || y) ret 3; ret 42
define i32 @logical_and_not(i1 %x, i1 %y) {
; CHECK-LABEL: @logical_and_not(
; CHECK-NEXT: entry:
; CHECK-NEXT: [[NOT_X:%.*]] = xor i1 [[X:%.*]], true
; CHECK-NEXT: [[TMP0:%.*]] = select i1 [[NOT_X]], i1 true, i1 [[Y:%.*]]
; CHECK-NEXT: br i1 [[TMP0]], label [[F:%.*]], label [[T:%.*]]
; CHECK: t:
; CHECK-NEXT: ret i32 42
; CHECK: f:
; CHECK-NEXT: ret i32 3
;
entry:
%noty = xor i1 %y, true
%and = select i1 %x, i1 %noty, i1 false
br i1 %and, label %t, label %f
t:
ret i32 42
f:
ret i32 3
}
; if (x && y || !x) ret 3; ret 42 --> if (!x || y) ret 3; ret 42
define i32 @logical_and_or(i1 %x, i1 %y) {
; CHECK-LABEL: @logical_and_or(
; CHECK-NEXT: entry:
; CHECK-NEXT: [[NOT_X:%.*]] = xor i1 [[X:%.*]], true
; CHECK-NEXT: [[AND:%.*]] = select i1 [[NOT_X]], i1 true, i1 [[Y:%.*]]
; CHECK-NEXT: br i1 [[AND]], label [[F:%.*]], label [[T:%.*]]
; CHECK: t:
; CHECK-NEXT: ret i32 42
; CHECK: f:
; CHECK-NEXT: ret i32 3
;
entry:
%and = select i1 %x, i1 %y, i1 true
br i1 %and, label %f, label %t
t:
ret i32 42
f:
ret i32 3
}
; if (!x || y) ret 3; ret 42
define i32 @logical_or_not(i1 %x, i1 %y) {
; CHECK-LABEL: @logical_or_not(
; CHECK-NEXT: entry:
; CHECK-NEXT: [[NOTX:%.*]] = xor i1 [[X:%.*]], true
; CHECK-NEXT: [[AND:%.*]] = select i1 [[NOTX]], i1 true, i1 [[Y:%.*]]
; CHECK-NEXT: br i1 [[AND]], label [[F:%.*]], label [[T:%.*]]
; CHECK: t:
; CHECK-NEXT: ret i32 42
; CHECK: f:
; CHECK-NEXT: ret i32 3
;
entry:
%notx = xor i1 %x, true
%and = select i1 %notx, i1 true, i1 %y
br i1 %and, label %f, label %t
t:
ret i32 42
f:
ret i32 3
}
; negative test
define i32 @logical_and_not_use1(i1 %x, i1 %y) {
; CHECK-LABEL: @logical_and_not_use1(
; CHECK-NEXT: entry:
; CHECK-NEXT: [[NOTY:%.*]] = xor i1 [[Y:%.*]], true
; CHECK-NEXT: call void @use(i1 [[NOTY]])
; CHECK-NEXT: [[AND:%.*]] = select i1 [[X:%.*]], i1 [[NOTY]], i1 false
; CHECK-NEXT: br i1 [[AND]], label [[T:%.*]], label [[F:%.*]]
; CHECK: t:
; CHECK-NEXT: ret i32 42
; CHECK: f:
; CHECK-NEXT: ret i32 3
;
entry:
%noty = xor i1 %y, true
call void @use(i1 %noty)
%and = select i1 %x, i1 %noty, i1 false
br i1 %and, label %t, label %f
t:
ret i32 42
f:
ret i32 3
}
; negative test
define i32 @logical_and_not_use2(i1 %x, i1 %y) {
; CHECK-LABEL: @logical_and_not_use2(
; CHECK-NEXT: entry:
; CHECK-NEXT: [[NOTY:%.*]] = xor i1 [[Y:%.*]], true
; CHECK-NEXT: [[AND:%.*]] = select i1 [[X:%.*]], i1 [[NOTY]], i1 false
; CHECK-NEXT: call void @use(i1 [[AND]])
; CHECK-NEXT: br i1 [[AND]], label [[T:%.*]], label [[F:%.*]]
; CHECK: t:
; CHECK-NEXT: ret i32 42
; CHECK: f:
; CHECK-NEXT: ret i32 3
;
entry:
%noty = xor i1 %y, true
%and = select i1 %x, i1 %noty, i1 false
call void @use(i1 %and)
br i1 %and, label %t, label %f
t:
ret i32 42
f:
ret i32 3
}
define i32 @dom_true(i1 %cmp) {
; CHECK-LABEL: @dom_true(
; CHECK-NEXT: br i1 [[CMP:%.*]], label [[IF_THEN:%.*]], label [[IF_ELSE:%.*]]
; CHECK: if.then:
; CHECK-NEXT: ret i32 1
; CHECK: if.else:
; CHECK-NEXT: ret i32 0
;
br i1 %cmp, label %if.then, label %if.else
if.then:
%zext = zext i1 %cmp to i32
ret i32 %zext
if.else:
ret i32 0
}
define i32 @dom_false(i1 %cmp) {
; CHECK-LABEL: @dom_false(
; CHECK-NEXT: br i1 [[CMP:%.*]], label [[IF_ELSE:%.*]], label [[IF_THEN:%.*]]
; CHECK: if.then:
; CHECK-NEXT: ret i32 0
; CHECK: if.else:
; CHECK-NEXT: ret i32 0
;
br i1 %cmp, label %if.else, label %if.then
if.then:
%zext = zext i1 %cmp to i32
ret i32 %zext
if.else:
ret i32 0
}
define i32 @dom_true_phi(i1 %cmp) {
; CHECK-LABEL: @dom_true_phi(
; CHECK-NEXT: br i1 [[CMP:%.*]], label [[IF_THEN:%.*]], label [[IF_ELSE:%.*]]
; CHECK: if.then:
; CHECK-NEXT: br label [[IF_END:%.*]]
; CHECK: if.else:
; CHECK-NEXT: br label [[IF_END]]
; CHECK: if.end:
; CHECK-NEXT: [[ZEXT:%.*]] = zext i1 [[CMP]] to i32
; CHECK-NEXT: ret i32 [[ZEXT]]
;
br i1 %cmp, label %if.then, label %if.else
if.then:
br label %if.end
if.else:
br label %if.end
if.end:
%phi = phi i1 [ true, %if.then ], [ %cmp, %if.else ]
%zext = zext i1 %phi to i32
ret i32 %zext
}
; Negative tests
define i32 @same_dest(i1 %cmp) {
; CHECK-LABEL: @same_dest(
; CHECK-NEXT: br i1 false, label [[IF_THEN:%.*]], label [[IF_THEN]]
; CHECK: if.then:
; CHECK-NEXT: [[ZEXT:%.*]] = zext i1 [[CMP:%.*]] to i32
; CHECK-NEXT: ret i32 [[ZEXT]]
;
br i1 %cmp, label %if.then, label %if.then
if.then:
%zext = zext i1 %cmp to i32
ret i32 %zext
}
define i32 @not_dom(i1 %cmp) {
; CHECK-LABEL: @not_dom(
; CHECK-NEXT: br i1 [[CMP:%.*]], label [[IF_THEN:%.*]], label [[IF_ELSE:%.*]]
; CHECK: if.then:
; CHECK-NEXT: br label [[IF_ELSE]]
; CHECK: if.else:
; CHECK-NEXT: [[ZEXT:%.*]] = zext i1 [[CMP]] to i32
; CHECK-NEXT: ret i32 [[ZEXT]]
;
br i1 %cmp, label %if.then, label %if.else
if.then:
br label %if.else
if.else:
%zext = zext i1 %cmp to i32
ret i32 %zext
}
Reference in New Issue View Git Blame Copy Permalink