Simplify the CFG after loop pass cleanup.

[filcab]

Summary

Otherwise we might end up with some empty basic blocks or
single-entry-single-exit basic blocks.

This fixes PR32085

[filcab]

Add PR32085 test.

[filcab]

Updated patch. Ping!

[RKSimon]

Please can you reduce the test case?

[davide]

I agree with what Simon said. Some comments inline.

test/Other/pr32085.ll

1–2 ↗

(On Diff #90873)

Not a very big fan of tests using -O2.
It's not the first time this has caused headaches to be while working on changes that make this kind of tests failing and tracking down becomes more and more fun.

That said. I think we need some infrastructure for integration testing (which we currently don't have). I also think the tests we have here should be kept as simple as possible to make sure we can debug them later easily.

103 ↗

(On Diff #90873)

the attributes should be not really useful, for example (and if some of them are you can probably trim them down).

[davide]

lib/Transforms/IPO/PassManagerBuilder.cpp

665–667 ↗

(On Diff #90873)

you need to add the equivalent in pass builder (in the new pass manager pipeline).

[filcab]

Minimized test, fixed new pass manager test.

[filcab]

Rebased to master.

[RKSimon]

No other comments from me.

[RKSimon]

test/Other/new-pm-defaults.ll

156 ↗

(On Diff #91581)

Just stop at the pass name - thats what the other checks do.

[davide]

No other comments from me, I'll be happy if @chandlerc can take a look

[mehdi_amini]

test/Other/pr32085.ll

8 ↗

(On Diff #91581)

This seems like an incredibly fragile test to me: relying on the absence of a label name after running O1/O2/O3 doesn't seem robust enough to me.

[davide]

I thought about the same problem Mehdi mentioned, but I have to say it's not Filipe's fault. In fact, the root cause is lack of proper integration testing in LLVM (GCC has infrastructure for that, FWIW).

[filcab]

Fix revision comments.
Made the test a "show that running simplifyCFG on the output is a no-op" type of test.

[RKSimon]

Looks alright to me and the new approach to the test seems solid. Any other comments from anyone (@davide @mehdi_amini)?

[RKSimon]

LGTM

llvm/trunk/lib/Passes/PassBuilder.cpp

PassBuilder::buildPerModuleDefaultPipeline(OptimizationLevel Level,
   // canonicalization pass that enables other optimizations. As a result,
   // LoopSink pass needs to be a very late IR pass to avoid undoing LICM
   // result too early.
   OptimizePM.addPass(LoopSinkPass());
 
   // And finally clean up LCSSA form before generating code.
   OptimizePM.addPass(InstSimplifierPass());
 
+  // LoopSink (and other loop passes since the last simplifyCFG) might have
+  // resulted in single-entry-single-exit or empty blocks. Clean up the CFG.
+  OptimizePM.addPass(SimplifyCFGPass());
+
   // Add the core optimizing pipeline.
   MPM.addPass(createModuleToFunctionPassAdaptor(std::move(OptimizePM)));
 
   // Now we need to do some global optimization transforms.
   // FIXME: It would seem like these should come first in the optimization
   // pipeline and maybe be the bottom of the canonicalization pipeline? Weird
   // ordering here.
   MPM.addPass(GlobalDCEPass());

llvm/trunk/lib/Transforms/IPO/PassManagerBuilder.cpp

void PassManagerBuilder::populateModulePassManager(
 
   // LoopSink pass sinks instructions hoisted by LICM, which serves as a
   // canonicalization pass that enables other optimizations. As a result,
   // LoopSink pass needs to be a very late IR pass to avoid undoing LICM
   // result too early.
   MPM.add(createLoopSinkPass());
   // Get rid of LCSSA nodes.
   MPM.add(createInstructionSimplifierPass());
+
+  // LoopSink (and other loop passes since the last simplifyCFG) might have
+  // resulted in single-entry-single-exit or empty blocks. Clean up the CFG.
+  MPM.add(createCFGSimplificationPass());
+
   addExtensionsToPM(EP_OptimizerLast, MPM);
 }
 
 void PassManagerBuilder::addLTOOptimizationPasses(legacy::PassManagerBase &PM) {
   // Remove unused virtual tables to improve the quality of code generated by
   // whole-program devirtualization and bitset lowering.
   PM.add(createGlobalDCEPass());
 

llvm/trunk/test/Other/new-pm-defaults.ll

 ; CHECK-O-NEXT: Running pass: InstCombinePass
 ; CHECK-O-NEXT: Running pass: FunctionToLoopPassAdaptor<{{.*}}LoopUnrollPass
 ; CHECK-O-NEXT: Running pass: InstCombinePass
 ; CHECK-O-NEXT: Running pass: RequireAnalysisPass<{{.*}}OptimizationRemarkEmitterAnalysis
 ; CHECK-O-NEXT: Running pass: FunctionToLoopPassAdaptor<{{.*}}LICMPass
 ; CHECK-O-NEXT: Running pass: AlignmentFromAssumptionsPass
 ; CHECK-O-NEXT: Running pass: LoopSinkPass
 ; CHECK-O-NEXT: Running pass: InstSimplifierPass
+; CHECK-O-NEXT: Running pass: SimplifyCFGPass
 ; CHECK-O-NEXT: Finished llvm::Function pass manager run.
 ; CHECK-O-NEXT: Running pass: GlobalDCEPass
 ; CHECK-O-NEXT: Running pass: ConstantMergePass
 ; CHECK-O-NEXT: Finished llvm::Module pass manager run.
 ; CHECK-O-NEXT: Running pass: PrintModulePass
 ;
 ; Make sure we get the IR back out without changes when we print the module.
 ; CHECK-O-LABEL: define void @foo(i32 %n) local_unnamed_addr {

llvm/trunk/test/Other/pass-pipelines.ll

 ; After vectorization and unrolling we try to do any cleanup of inserted code,
 ; including a run of LICM. This shouldn't run in the same loop pass manager as
 ; the runtime unrolling though.
 ; CHECK-O2: Loop Pass Manager
 ; CHECK-O2-NEXT: Loop Invariant Code Motion
 ; CHECK-O2: FunctionPass Manager
 ; CHECK-O2: Loop Pass Manager
 ; CHECK-O2-NEXT: Loop Sink
+; CHECK-O2: Simplify the CFG
 ; CHECK-O2-NOT: Manager
 ;
 ; FIXME: There really shouldn't be another pass manager, especially one that
 ; just builds the domtree. It doesn't even run the verifier.
 ; CHECK-O2: Pass Arguments:
 ; CHECK-O2-NEXT: FunctionPass Manager
 ; CHECK-O2-NEXT: Dominator Tree Construction
 
 define void @foo() {
   ret void
 }

llvm/trunk/test/Other/pr32085.ll

+; RUN: opt -S -O1 < %s -o %t1.ll
+;; Show that there's no difference after running another simplify CFG
+; RUN: opt -S -simplifycfg < %t1.ll -o %t2.ll
+; RUN: diff %t1.ll %t2.ll
+
+; Test from LoopSink pass, leaves some single-entry single-exit basic blocks.
+; After LoopSink, we get a basic block .exit.loopexit which has one entry and
+; one exit, the only instruction is a branch. Make sure it doesn't show up.
+; Make sure they disappear at -O1.
+
+@g = global i32 0, align 4
+
+define i32 @t1(i32, i32) {
+  %3 = icmp eq i32 %1, 0
+  br i1 %3, label %.exit, label %.preheader
+
+.preheader:
+  %invariant = load i32, i32* @g
+  br label %.b1
+
+.b1:
+  %iv = phi i32 [ %t7, %.b7 ], [ 0, %.preheader ]
+  %c1 = icmp sgt i32 %iv, %0
+  br i1 %c1, label %.b2, label %.b6
+
+.b2:
+  %c2 = icmp sgt i32 %iv, 1
+  br i1 %c2, label %.b3, label %.b4
+
+.b3:
+  %t3 = sub nsw i32 %invariant, %iv
+  br label %.b5
+
+.b4:
+  %t4 = add nsw i32 %invariant, %iv
+  br label %.b5
+
+.b5:
+  %p5 = phi i32 [ %t3, %.b3 ], [ %t4, %.b4 ]
+  %t5 = mul nsw i32 %p5, 5
+  br label %.b7
+
+.b6:
+  %t6 = add nsw i32 %iv, 100
+  br label %.b7
+
+.b7:
+  %p7 = phi i32 [ %t6, %.b6 ], [ %t5, %.b5 ]
+  %t7 = add nuw nsw i32 %iv, 1
+  %c7 = icmp eq i32 %t7, %p7
+  br i1 %c7, label %.b1, label %.exit
+
+.exit:
+  ret i32 10
+}
+