| ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py |
| ; RUN: opt < %s -unify-loop-exits -structurizecfg -enable-new-pm=0 -S | FileCheck %s |
| |
| ; The structurizer uses an RPO traversal over a region, along with a |
| ; manual hack that is meant to sort ensure that blocks within a loop |
| ; are all visited before visiting blocks outside the loop. But this |
| ; does not always work as expected. For example the results are |
| ; incorrect when multiple nested loops are involved. |
| |
| ; The workaround for this is to unify loop exits. Each loop now |
| ; becomes an SESE region with a single header and a single exit. The |
| ; structurizer is a region pass, and it no longer sees the entire loop |
| ; nest in a single region. More importantly, for each loop, the only |
| ; block reachable outside the loop is the region exit, which avoids |
| ; any confusion in the hacked RPO traversal. |
| |
| ; In the function below, B1 is an exiting block in outer loop H1. It's |
| ; successor inside the loop is the header of another loop H2. Due to |
| ; the incorrect traversal, B1 dominates all the blocks in the |
| ; structurized program, except the header H1. |
| |
| define void @exiting-block(i1 %PredH1, i1 %PredB2, i1 %PredB1, i1 %PredH2) { |
| ; CHECK-LABEL: @exiting-block( |
| ; CHECK-NEXT: entry: |
| ; CHECK-NEXT: [[PREDH1_INV:%.*]] = xor i1 [[PREDH1:%.*]], true |
| ; CHECK-NEXT: [[PREDB2_INV:%.*]] = xor i1 [[PREDB2:%.*]], true |
| ; CHECK-NEXT: br label [[H1:%.*]] |
| ; CHECK: H1: |
| ; CHECK-NEXT: br i1 [[PREDH1_INV]], label [[B1:%.*]], label [[FLOW3:%.*]] |
| ; CHECK: Flow3: |
| ; CHECK-NEXT: [[TMP0:%.*]] = phi i1 [ [[PREDB1:%.*]], [[B1]] ], [ [[PREDH1]], [[H1]] ] |
| ; CHECK-NEXT: br i1 [[TMP0]], label [[H2:%.*]], label [[FLOW4:%.*]] |
| ; CHECK: H2: |
| ; CHECK-NEXT: br i1 [[PREDH2:%.*]], label [[B2:%.*]], label [[FLOW:%.*]] |
| ; CHECK: B2: |
| ; CHECK-NEXT: br i1 [[PREDB2_INV]], label [[L2:%.*]], label [[FLOW2:%.*]] |
| ; CHECK: Flow: |
| ; CHECK-NEXT: [[TMP1:%.*]] = phi i1 [ false, [[FLOW2]] ], [ true, [[H2]] ] |
| ; CHECK-NEXT: [[TMP2:%.*]] = phi i1 [ [[TMP4:%.*]], [[FLOW2]] ], [ true, [[H2]] ] |
| ; CHECK-NEXT: br i1 [[TMP2]], label [[LOOP_EXIT_GUARD1:%.*]], label [[H2]] |
| ; CHECK: L2: |
| ; CHECK-NEXT: br label [[FLOW2]] |
| ; CHECK: L1: |
| ; CHECK-NEXT: br label [[FLOW5:%.*]] |
| ; CHECK: B1: |
| ; CHECK-NEXT: br label [[FLOW3]] |
| ; CHECK: C: |
| ; CHECK-NEXT: br label [[EXIT:%.*]] |
| ; CHECK: exit: |
| ; CHECK-NEXT: ret void |
| ; CHECK: Flow5: |
| ; CHECK-NEXT: [[TMP3:%.*]] = phi i1 [ false, [[L1:%.*]] ], [ true, [[LOOP_EXIT_GUARD1]] ] |
| ; CHECK-NEXT: br label [[FLOW4]] |
| ; CHECK: loop.exit.guard: |
| ; CHECK-NEXT: br i1 [[TMP5:%.*]], label [[C:%.*]], label [[EXIT]] |
| ; CHECK: Flow2: |
| ; CHECK-NEXT: [[TMP4]] = phi i1 [ false, [[L2]] ], [ true, [[B2]] ] |
| ; CHECK-NEXT: br label [[FLOW]] |
| ; CHECK: Flow4: |
| ; CHECK-NEXT: [[TMP5]] = phi i1 [ false, [[FLOW5]] ], [ true, [[FLOW3]] ] |
| ; CHECK-NEXT: [[TMP6:%.*]] = phi i1 [ [[TMP3]], [[FLOW5]] ], [ true, [[FLOW3]] ] |
| ; CHECK-NEXT: br i1 [[TMP6]], label [[LOOP_EXIT_GUARD:%.*]], label [[H1]] |
| ; CHECK: loop.exit.guard1: |
| ; CHECK-NEXT: br i1 [[TMP1]], label [[L1]], label [[FLOW5]] |
| ; |
| entry: |
| br label %H1 |
| |
| H1: ; preds = %L1, %entry |
| br i1 %PredH1, label %H2, label %B1 |
| |
| H2: ; preds = %B1, %L2, %H1 |
| br i1 %PredH2, label %B2, label %L1 |
| |
| B2: ; preds = %H2 |
| br i1 %PredB2, label %exit, label %L2 |
| |
| L2: ; preds = %B2 |
| br label %H2 |
| |
| L1: ; preds = %H2 |
| br label %H1 |
| |
| B1: ; preds = %H1 |
| br i1 %PredB1, label %H2, label %C |
| |
| C: ; preds = %B1 |
| br label %exit |
| |
| exit: ; preds = %C, %B2 |
| ret void |
| } |
| |
| ; The function below has three nested loops. Due to the incorrect |
| ; traversal, H2 dominates H3 in the structurized program, and the |
| ; backedge from L13 to H3 has no equivalent path. |
| |
| define void @incorrect-backedge(i1 %PredH2, i1 %PredH3, i1 %PredL2, i1 %PredL13, i1 %PredL1) |
| ; CHECK-LABEL: @incorrect-backedge( |
| ; CHECK-NEXT: entry: |
| ; CHECK-NEXT: [[PREDH2_INV:%.*]] = xor i1 [[PREDH2:%.*]], true |
| ; CHECK-NEXT: [[PREDL2_INV:%.*]] = xor i1 [[PREDL2:%.*]], true |
| ; CHECK-NEXT: [[PREDH3_INV:%.*]] = xor i1 [[PREDH3:%.*]], true |
| ; CHECK-NEXT: [[PREDL13_INV:%.*]] = xor i1 [[PREDL13:%.*]], true |
| ; CHECK-NEXT: br label [[H1:%.*]] |
| ; CHECK: H1: |
| ; CHECK-NEXT: br label [[H2:%.*]] |
| ; CHECK: H2: |
| ; CHECK-NEXT: br i1 [[PREDH2_INV]], label [[H3:%.*]], label [[FLOW4:%.*]] |
| ; CHECK: H3: |
| ; CHECK-NEXT: br i1 [[PREDH3_INV]], label [[L2:%.*]], label [[FLOW:%.*]] |
| ; CHECK: L2: |
| ; CHECK-NEXT: br i1 [[PREDL2_INV]], label [[L13:%.*]], label [[FLOW3:%.*]] |
| ; CHECK: Flow: |
| ; CHECK-NEXT: [[TMP0:%.*]] = phi i1 [ false, [[FLOW3]] ], [ true, [[H3]] ] |
| ; CHECK-NEXT: [[TMP1:%.*]] = phi i1 [ [[TMP6:%.*]], [[FLOW3]] ], [ true, [[H3]] ] |
| ; CHECK-NEXT: [[TMP2:%.*]] = phi i1 [ [[TMP7:%.*]], [[FLOW3]] ], [ true, [[H3]] ] |
| ; CHECK-NEXT: br i1 [[TMP2]], label [[LOOP_EXIT_GUARD2:%.*]], label [[H3]] |
| ; CHECK: L13: |
| ; CHECK-NEXT: br label [[FLOW3]] |
| ; CHECK: Flow5: |
| ; CHECK-NEXT: [[TMP3:%.*]] = phi i1 [ [[TMP8:%.*]], [[LOOP_EXIT_GUARD1:%.*]] ], [ true, [[LOOP_EXIT_GUARD:%.*]] ] |
| ; CHECK-NEXT: [[TMP4:%.*]] = phi i1 [ false, [[LOOP_EXIT_GUARD1]] ], [ true, [[LOOP_EXIT_GUARD]] ] |
| ; CHECK-NEXT: br i1 [[TMP4]], label [[L1:%.*]], label [[FLOW6:%.*]] |
| ; CHECK: L1: |
| ; CHECK-NEXT: br label [[FLOW6]] |
| ; CHECK: Flow6: |
| ; CHECK-NEXT: [[TMP5:%.*]] = phi i1 [ [[PREDL1:%.*]], [[L1]] ], [ [[TMP3]], [[FLOW5:%.*]] ] |
| ; CHECK-NEXT: br i1 [[TMP5]], label [[EXIT:%.*]], label [[H1]] |
| ; CHECK: exit: |
| ; CHECK-NEXT: ret void |
| ; CHECK: loop.exit.guard: |
| ; CHECK-NEXT: br i1 [[TMP11:%.*]], label [[LOOP_EXIT_GUARD1]], label [[FLOW5]] |
| ; CHECK: loop.exit.guard1: |
| ; CHECK-NEXT: br label [[FLOW5]] |
| ; CHECK: Flow3: |
| ; CHECK-NEXT: [[TMP6]] = phi i1 [ true, [[L13]] ], [ false, [[L2]] ] |
| ; CHECK-NEXT: [[TMP7]] = phi i1 [ [[PREDL13_INV]], [[L13]] ], [ true, [[L2]] ] |
| ; CHECK-NEXT: br label [[FLOW]] |
| ; CHECK: Flow4: |
| ; CHECK-NEXT: [[TMP8]] = phi i1 [ [[TMP0]], [[LOOP_EXIT_GUARD2]] ], [ false, [[H2]] ] |
| ; CHECK-NEXT: [[TMP9:%.*]] = phi i1 [ false, [[LOOP_EXIT_GUARD2]] ], [ true, [[H2]] ] |
| ; CHECK-NEXT: [[TMP10:%.*]] = phi i1 [ [[TMP1]], [[LOOP_EXIT_GUARD2]] ], [ true, [[H2]] ] |
| ; CHECK-NEXT: [[TMP11]] = xor i1 [[TMP9]], true |
| ; CHECK-NEXT: br i1 [[TMP10]], label [[LOOP_EXIT_GUARD]], label [[H2]] |
| ; CHECK: loop.exit.guard2: |
| ; CHECK-NEXT: br label [[FLOW4]] |
| ; |
| { |
| entry: |
| br label %H1 |
| |
| H1: |
| br label %H2 |
| |
| H2: |
| br i1 %PredH2, label %L1, label %H3 |
| |
| H3: |
| br i1 %PredH3, label %exit, label %L2 |
| |
| L2: |
| br i1 %PredL2, label %H2, label %L13 |
| |
| L13: |
| br i1 %PredL13, label %H3, label %H1 |
| |
| L1: |
| br i1 %PredL1, label %exit, label %H1 |
| |
| exit: |
| ret void |
| } |