search

llvm / llvm-project

The LLVM Project is a collection of modular and reusable compiler and toolchain technologies.
http://llvm.org
Other
28.41k stars 11.74k forks source link

[SimplifyCFG] Conversion of comparisons to switch only partial #63470

Open nikic opened 1 year ago

nikic commented 1 year ago 
define i1 @test1(i32 %c) {
entry: 
  %i1 = icmp eq i32 %c, 115
  br i1 %i1, label %bb12, label %bb11

bb11:                                             ; preds = %entry
  %_6 = icmp eq i32 %c, 109
  br label %bb12

bb12:                                             ; preds = %entry, %bb11
  %_4.0 = phi i1 [ %_6, %bb11 ], [ true, %entry ]
  br i1 %_4.0, label %bb9, label %bb8

bb8:                                              ; preds = %bb12
  %_8 = icmp eq i32 %c, 104
  br label %bb9  

bb9:                                              ; preds = %bb12, %bb8
  %_3.0 = phi i1 [ %_8, %bb8 ], [ true, %bb12 ]
  br i1 %_3.0, label %bb6, label %bb5

bb5:                                              ; preds = %bb9
  %_10 = icmp eq i32 %c, 100
  br label %bb6  

bb6:                                              ; preds = %bb9, %bb5
  %_2.0 = phi i1 [ %_10, %bb5 ], [ true, %bb9 ]
  br i1 %_2.0, label %bb3, label %bb2

bb2:                                              ; preds = %bb6
  %_12 = icmp eq i32 %c, 119
  br label %bb3

bb3:                                              ; preds = %bb6, %bb2
  %i.0 = phi i1 [ %_12, %bb2 ], [ true, %bb6 ]
  ret i1 %i.0                    
}

opt -S -passes=simplifycfg produces:

define i1 @test1(i32 %c) {
entry:
  switch i32 %c, label %bb8 [
    i32 115, label %bb9
    i32 109, label %bb9
    i32 104, label %bb9
  ]

bb8:                                              ; preds = %entry
  br label %bb9

bb9:                                              ; preds = %entry, %entry, %entry, %bb8
  %_3.0 = phi i1 [ false, %bb8 ], [ true, %entry ], [ true, %entry ], [ true, %entry ]
  %_10 = icmp eq i32 %c, 100
  %spec.select1 = select i1 %_3.0, i1 true, i1 %_10
  %_12 = icmp eq i32 %c, 119
  %spec.select = select i1 %spec.select1, i1 true, i1 %_12
  ret i1 %spec.select
}

Three of the comparisons have been converted into a switch, but the last two use selects.

antoniofrighetto commented 1 year ago

@nikic, this is how the IR looks after optimizing the third case:

define i1 @test1(i32 %c) {
entry:
  switch i32 %c, label %bb8 [
    i32 115, label %bb9
    i32 109, label %bb9
    i32 104, label %switch.edge
  ]

switch.edge:                                      ; preds = %entry
  br label %bb9

bb8:                                              ; preds = %entry
  br label %bb9

bb9:                                              ; preds = %switch.edge, %entry, %entry, %bb8
  %_3.0 = phi i1 [ false, %bb8 ], [ true, %entry ], [ true, %switch.edge ]
  %_10 = icmp eq i32 %c, 100
  %spec.select1 = select i1 %_3.0, i1 true, i1 %_10
  br i1 %spec.select1, label %bb3, label %bb2

bb2:                                              ; preds = %bb9
  %_12 = icmp eq i32 %c, 119
  br label %bb3

bb3:                                              ; preds = %bb2, %bb9
  %i.0 = phi i1 [ %_12, %bb2 ], [ true, %bb9 ], [ true, %entry ]
  ret i1 %i.0
}

I think a possible a idea would be to support handling of bb9 terminator here. Thus, besides allowing only one setcond (icmp eq), we would also handle the case in which a select is used as a condition of the branch instruction and reuse the logic inside FoldValueComparisonIntoPredecessors. Alternatively, we may fold the two cases at the very end here, by introducing support for ret instruction (still trying to reuse FoldValueComparisonIntoPredecessors). Any insight?

antoniofrighetto commented 1 year ago

I'm adding a similar case that does not seem to be further optimized.

define i1 @test1(i32 %c) {
entry:
  switch i32 %c, label %bb8 [
    i32 115, label %bb9
    i32 109, label %bb9
    i32 104, label %bb9
  ]

bb8:                                              ; preds = %entry
  br label %bb9

bb9:                                              ; preds = %bb8, %entry, %entry, %entry
  %_3.0 = phi i1 [ false, %bb8 ], [ true, %entry ], [ true, %entry ], [ true, %entry ]
  %_10 = icmp eq i32 %c, 100
  br i1 %_3.0, label %common.ret, label %bb11

common.ret:                                       ; preds = %bb11, %bb9
  %common.ret.op = phi i1 [ true, %bb9 ], [ %._12, %bb11 ]
  ret i1 %common.ret.op

bb11:                                             ; preds = %bb9
  %_12 = icmp eq i32 %c, 119
  %._12 = select i1 %_10, i1 true, i1 %_12
  br label %common.ret
}

Godbolt: https://llvm.godbolt.org/z/xbbYhWMqc.