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

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

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

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

9

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

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());
 

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
 }

test/Other/pr32085.ll

+; RUN: opt -O2 -S < %s | FileCheck %s
+; In PR32085 we were getting single-entry-single-exit basic blocks due to the
+; lack of cleanup after some loop transformations.
+; Make sure we end up with a single basic block, no branches
+; CHECK-NOT: br label
+
+; ModuleID = 'a.cpp'
+source_filename = "a.cpp"
+target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-apple-macosx10.12.0"
+
+; Function Attrs: ssp uwtable
+define i8* @_Z3go4i(i32) #0 {
+  %2 = alloca i32, align 4
+  %3 = alloca i32*, align 8
+  %4 = alloca i32, align 4
+  %5 = alloca i32
+  %6 = alloca i32, align 4
+  store i32 %0, i32* %2, align 4, !tbaa !2
+  %7 = bitcast i32** %3 to i8*
+  call void @llvm.lifetime.start(i64 8, i8* %7) #3
+  %8 = call i8* @_Znam(i64 4096) #4
+  %9 = bitcast i8* %8 to i32*
+  store i32* %9, i32** %3, align 8, !tbaa !6
+  %10 = bitcast i32* %4 to i8*
+  call void @llvm.lifetime.start(i64 4, i8* %10) #3
+  store i32 0, i32* %4, align 4, !tbaa !2
+  br label %11
+
+; <label>:11:                                     ; preds = %36, %1
+  %12 = load i32, i32* %4, align 4, !tbaa !2
+  %13 = icmp slt i32 %12, 8
+  br i1 %13, label %16, label %14
+
+; <label>:14:                                     ; preds = %11
+  store i32 2, i32* %5, align 4
+  %15 = bitcast i32* %4 to i8*
+  call void @llvm.lifetime.end(i64 4, i8* %15) #3
+  br label %39
+
+; <label>:16:                                     ; preds = %11
+  %17 = bitcast i32* %6 to i8*
+  call void @llvm.lifetime.start(i64 4, i8* %17) #3
+  store i32 0, i32* %6, align 4, !tbaa !2
+  br label %18
+
+; <label>:18:                                     ; preds = %32, %16
+  %19 = load i32, i32* %6, align 4, !tbaa !2
+  %20 = icmp slt i32 %19, 128
+  br i1 %20, label %23, label %21
+
+; <label>:21:                                     ; preds = %18
+  store i32 5, i32* %5, align 4
+  %22 = bitcast i32* %6 to i8*
+  call void @llvm.lifetime.end(i64 4, i8* %22) #3
+  br label %35
+
+; <label>:23:                                     ; preds = %18
+  %24 = load i32, i32* %2, align 4, !tbaa !2
+  %25 = load i32*, i32** %3, align 8, !tbaa !6
+  %26 = load i32, i32* %4, align 4, !tbaa !2
+  %27 = mul nsw i32 %26, 128
+  %28 = load i32, i32* %6, align 4, !tbaa !2
+  %29 = add nsw i32 %27, %28
+  %30 = sext i32 %29 to i64
+  %31 = getelementptr inbounds i32, i32* %25, i64 %30
+  store i32 %24, i32* %31, align 4, !tbaa !2
+  br label %32
+
+; <label>:32:                                     ; preds = %23
+  %33 = load i32, i32* %6, align 4, !tbaa !2
+  %34 = add nsw i32 %33, 1
+  store i32 %34, i32* %6, align 4, !tbaa !2
+  br label %18
+
+; <label>:35:                                     ; preds = %21
+  br label %36
+
+; <label>:36:                                     ; preds = %35
+  %37 = load i32, i32* %4, align 4, !tbaa !2
+  %38 = add nsw i32 %37, 1
+  store i32 %38, i32* %4, align 4, !tbaa !2
+  br label %11
+
+; <label>:39:                                     ; preds = %14
+  %40 = load i32*, i32** %3, align 8, !tbaa !6
+  %41 = bitcast i32* %40 to i8*
+  store i32 1, i32* %5, align 4
+  %42 = bitcast i32** %3 to i8*
+  call void @llvm.lifetime.end(i64 8, i8* %42) #3
+  ret i8* %41
+}
+
+; Function Attrs: argmemonly nounwind
+declare void @llvm.lifetime.start(i64, i8* nocapture) #1
+
+; Function Attrs: nobuiltin
+declare noalias i8* @_Znam(i64) #2
+
+; Function Attrs: argmemonly nounwind
+declare void @llvm.lifetime.end(i64, i8* nocapture) #1
+
+attributes #0 = { ssp uwtable "correctly-rounded-divide-sqrt-fp-math"="false" "disable-tail-calls"="false" "less-precise-fpmad"="false" "no-frame-pointer-elim"="true" "no-frame-pointer-elim-non-leaf" "no-infs-fp-math"="false" "no-jump-tables"="false" "no-nans-fp-math"="false" "no-signed-zeros-fp-math"="false" "no-trapping-math"="false" "stack-protector-buffer-size"="8" "target-cpu"="core-avx2" "target-features"="+aes,+avx,+avx2,+bmi,+bmi2,+cx16,+f16c,+fma,+fsgsbase,+fxsr,+lzcnt,+mmx,+movbe,+pclmul,+popcnt,+rdrnd,+rtm,+sse,+sse2,+sse3,+sse4.1,+sse4.2,+ssse3,+x87,+xsave,+xsaveopt" "unsafe-fp-math"="false" "use-soft-float"="false" }
+attributes #1 = { argmemonly nounwind }
+attributes #2 = { nobuiltin "correctly-rounded-divide-sqrt-fp-math"="false" "disable-tail-calls"="false" "less-precise-fpmad"="false" "no-frame-pointer-elim"="true" "no-frame-pointer-elim-non-leaf" "no-infs-fp-math"="false" "no-nans-fp-math"="false" "no-signed-zeros-fp-math"="false" "no-trapping-math"="false" "stack-protector-buffer-size"="8" "target-cpu"="core-avx2" "target-features"="+aes,+avx,+avx2,+bmi,+bmi2,+cx16,+f16c,+fma,+fsgsbase,+fxsr,+lzcnt,+mmx,+movbe,+pclmul,+popcnt,+rdrnd,+rtm,+sse,+sse2,+sse3,+sse4.1,+sse4.2,+ssse3,+x87,+xsave,+xsaveopt" "unsafe-fp-math"="false" "use-soft-float"="false" }
+attributes #3 = { nounwind }
+attributes #4 = { builtin }
+
+!llvm.module.flags = !{!0}
+!llvm.ident = !{!1}
+
+!0 = !{i32 1, !"PIC Level", i32 2}
+!1 = !{!"clang version 5.0.0 (trunk 296485) (llvm/trunk 296488)"}
+!2 = !{!3, !3, i64 0}
+!3 = !{!"int", !4, i64 0}
+!4 = !{!"omnipotent char", !5, i64 0}
+!5 = !{!"Simple C++ TBAA"}
+!6 = !{!7, !7, i64 0}
+!7 = !{!"any pointer", !4, i64 0}