[ADCE] Fix incorrect reporting of CFG changes

[mkazantsev]

Summary

This patch fixes 2 related bugs in ADCE:

• performDeadCodeElimination does not report changes if it did ONLY CFG changes (affects both old and new pass managers);
• When control flow removal is enabled, new pass manager does not drop CFG analyses.

Both can lead to incorrect loop info after ADCE that does only CFG changes.

[dantrushin]

Good catch!
LGTM

[mkazantsev]

Made preservation logic tad smarter (do not preserve DT analyzes twice)

llvm/lib/Transforms/Scalar/ADCE.cpp

class AggressiveDeadCodeElimination {
   void markLiveBranchesFromControlDependences();
 
   /// Remove instructions not marked live, return if any instruction was
   /// removed.
   bool removeDeadInstructions();
 
   /// Identify connected sections of the control flow graph which have
   /// dead terminators and rewrite the control flow graph to remove them.
-  void updateDeadRegions();
+  bool updateDeadRegions();
 
   /// Set the BlockInfo::PostOrder field based on a post-order
   /// numbering of the reverse control flow graph.
   void computeReversePostOrder();
 
   /// Make the terminator of this block an unconditional branch to \p Target.
   void makeUnconditional(BasicBlock *BB, BasicBlock *Target);
 

 
 //===----------------------------------------------------------------------===//
 //
 //  Routines to update the CFG and SSA information before removing dead code.
 //
 //===----------------------------------------------------------------------===//
 bool AggressiveDeadCodeElimination::removeDeadInstructions() {
   // Updates control and dataflow around dead blocks
-  updateDeadRegions();
+  bool RegionsUpdated = updateDeadRegions();
 
   LLVM_DEBUG({
     for (Instruction &I : instructions(F)) {
       // Check if the instruction is alive.
       if (isLive(&I))
         continue;
 
       if (auto *DII = dyn_cast<DbgVariableIntrinsic>(&I)) {
for (Instruction &I : instructions(F)) {
     I.dropAllReferences();
   }
 
   for (Instruction *&I : Worklist) {
     ++NumRemoved;
     I->eraseFromParent();
   }
 
-  return !Worklist.empty();
+  return !Worklist.empty() || RegionsUpdated;
 }
 
 // A dead region is the set of dead blocks with a common live post-dominator.
-void AggressiveDeadCodeElimination::updateDeadRegions() {
+bool AggressiveDeadCodeElimination::updateDeadRegions() {
   LLVM_DEBUG({
     dbgs() << "final dead terminator blocks: " << '\n';
     for (auto *BB : BlocksWithDeadTerminators)
       dbgs() << '\t' << BB->getName()
              << (BlockInfo[BB].Live ? " LIVE\n" : "\n");
   });
 
   // Don't compute the post ordering unless we needed it.
   bool HavePostOrder = false;
+  bool Changed = false;
 
   for (auto *BB : BlocksWithDeadTerminators) {
     auto &Info = BlockInfo[BB];
     if (Info.UnconditionalBranch) {
       InstInfo[Info.Terminator].Live = true;
       continue;
     }
 
for (auto *Succ : RemovedSuccessors) {
         DeletedEdges.push_back({DominatorTree::Delete, BB, Succ});
       }
     }
 
     DomTreeUpdater(DT, &PDT, DomTreeUpdater::UpdateStrategy::Eager)
         .applyUpdates(DeletedEdges);
 
     NumBranchesRemoved += 1;
+    Changed = true;
   }
+
+  return Changed;
 }
 
 // reverse top-sort order
 void AggressiveDeadCodeElimination::computeReversePostOrder() {
   // This provides a post-order numbering of the reverse control flow graph
   // Note that it is incomplete in the presence of infinite loops but we don't
   // need numbers blocks which don't reach the end of the functions since
   // all branches in those blocks are forced live.
PreservedAnalyses ADCEPass::run(Function &F, FunctionAnalysisManager &FAM) {
   // ADCE does not need DominatorTree, but require DominatorTree here
   // to update analysis if it is already available.
   auto *DT = FAM.getCachedResult<DominatorTreeAnalysis>(F);
   auto &PDT = FAM.getResult<PostDominatorTreeAnalysis>(F);
   if (!AggressiveDeadCodeElimination(F, DT, PDT).performDeadCodeElimination())
     return PreservedAnalyses::all();
 
   PreservedAnalyses PA;
+  // TODO: We could track if we have actually done CFG changes.
+  if (!RemoveControlFlowFlag)
     PA.preserveSet<CFGAnalyses>();
-  PA.preserve<GlobalsAA>();
+  else {
     PA.preserve<DominatorTreeAnalysis>();
     PA.preserve<PostDominatorTreeAnalysis>();
+  }
+  PA.preserve<GlobalsAA>();
   return PA;
 }
 
 namespace {
 
 struct ADCELegacyPass : public FunctionPass {
   static char ID; // Pass identification, replacement for typeid
 

llvm/test/Transforms/ADCE/broken-loop-info.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt -licm -adce -licm -S < %s | FileCheck %s
 ; RUN: opt -passes='loop(licm),adce,loop(licm)' -S < %s | FileCheck %s
 ;
-; XFAIL: *
-; REQUIRES: asserts
-;
-; This test demonstrates a bug in ADCE's work with loop info. It does some
-; changes that make loop's block unreachable, but never bothers to update
-; loop info accordingly.
 
 target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128-ni:1-p2:32:8:8:32-ni:2"
 target triple = "x86_64-unknown-linux-gnu"
 
 define void @test() {
-; CHECK-LABEL: test
+; CHECK-LABEL: @test(
+; CHECK-NEXT:  bb:
+; CHECK-NEXT:    br label [[BB2:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    ret void
+; CHECK:       bb2:
+; CHECK-NEXT:    br label [[BB4:%.*]]
+; CHECK:       bb3:
+; CHECK-NEXT:    unreachable
+; CHECK:       bb4:
+; CHECK-NEXT:    br i1 true, label [[BB1:%.*]], label [[BB2]]
+;
 
 bb:
   br label %bb2
 
 bb1:                                              ; preds = %bb4
   ret void
 
 bb2:                                              ; preds = %bb4, %bb
   br i1 undef, label %bb4, label %bb3
 
 bb3:                                              ; preds = %bb2
   br label %bb4
 
 bb4:                                              ; preds = %bb3, %bb2
   br i1 undef, label %bb1, label %bb2
 }