[SCCP] Mark CFG as preserved.

[fhahn]

Summary

SCCP does not change the CFG, so we can mark it as preserved.

[davide]

If I recall correctly the sparse constant propagation implementation in LLVM (interproceturally, at least), calls changeToUnreachable which modifies the CFG.
(this is, quite unfortunate, as it's declared in Local.h). So, I'm afraid the patch as is is not correct. That said, it's been a while since I last worked on this area so I might recall incorrectly :)

[• dberlin]

This is, AFAIK, right but your assumption is wrong.

In particular, DT is preserved, but the CFG is definitely changed by SCCP.
See changeToUnreachable and what it does under the covers.

(this has confused people before :P).

[• dberlin]

Davide beat me to it.

DT is still preserved.

[fhahn]

Right, IPSCCP does use changeToUnreachable, but it can be told to update the DT. The thing that confused me is that we use removeAllNonTerminatorInstruction... in runSCCP with a comment that we should not change the CFG. Is there a reason we use changeToUnreachable in IPSCCP but removeAllNonTerminatorInstruction... in SCCP?

[davide]

Florian, I won't be opposed if you decide to preserve the dominator tree as part of changeToUnreachable, but, as we discussed with Dan in the past, do we really need to? I mean, we could just change changeToUnreachable (no pun intended) to do something sane and not modify the CFG (if the block is really unreachable, it's very likely that the next round of DCE is going to remove it anyway) [and in case it doesn't I'm really not worried about running DCE again because it's really basically free].

[davide]

In D47149#1106684, @fhahn wrote:

Right, IPSCCP does use changeToUnreachable, but it can be told to update the DT. The thing that confused me is that we use removeAllNonTerminatorInstruction... in runSCCP with a comment that we should not change the CFG. Is there a reason we use changeToUnreachable in IPSCCP but removeAllNonTerminatorInstruction... in SCCP?

I don't think there's a good one, FWIW.

[fhahn]

Thanks Davide. It should be fairly straight forward to preserve the DT on top of D45330, which requires dominators anyways for IPSCCP. If we could get away not modifying that would be great, I just want to avoid pessimizing passes close to IPSCCP.

[fhahn]

Removed DT preservation for IPSCCP, which uses changeToUnreachable. SCCP uses removeAllNonTerminatorInstruction... and should not change the CFG.

[fhahn]

ping

[efriedma]

LGTM

[efriedma]

Err, actually, thinking about it a big more, can you use setPreservesCFG() instead, if we're not modifying the CFG at all?

[fhahn]

Yep I think we could preserve all CFG analysis. But wouldn't that potentially lead to worse results, if a preserved analysis could benefit from the propagated constants?

[efriedma]

setPreservesCFG preserves passes which *only* depend on the CFG, like domtree/loopinfo/etc.

[fhahn]

Updated to mark CFG as preserved. I also added a test case.

[davide]

LGTM.

lib/Transforms/IPO/SCCP.cpp

 #include "llvm/Transforms/IPO/SCCP.h"
 #include "llvm/Analysis/TargetLibraryInfo.h"
+#include "llvm/IR/Dominators.h"
 #include "llvm/Transforms/IPO.h"
 #include "llvm/Transforms/Scalar/SCCP.h"
 
 using namespace llvm;
 
 PreservedAnalyses IPSCCPPass::run(Module &M, ModuleAnalysisManager &AM) {
   const DataLayout &DL = M.getDataLayout();
   auto &TLI = AM.getResult<TargetLibraryAnalysis>(M);
   if (!runIPSCCP(M, DL, &TLI))
     return PreservedAnalyses::all();
-  return PreservedAnalyses::none();
+
+  PreservedAnalyses PA;
+  PA.preserve<DominatorTreeAnalysis>();
+  return PA;
 }
 
 namespace {
 
 //===--------------------------------------------------------------------===//
 //
 /// IPSCCP Class - This class implements interprocedural Sparse Conditional
 /// Constant Propagation.
bool runOnModule(Module &M) override {
     const DataLayout &DL = M.getDataLayout();
     const TargetLibraryInfo *TLI =
         &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
     return runIPSCCP(M, DL, TLI);
   }
 
   void getAnalysisUsage(AnalysisUsage &AU) const override {
     AU.addRequired<TargetLibraryInfoWrapperPass>();
+    AU.addPreserved<DominatorTreeWrapperPass>();
   }
 };
 
 } // end anonymous namespace
 
 char IPSCCPLegacyPass::ID = 0;
 
 INITIALIZE_PASS_BEGIN(IPSCCPLegacyPass, "ipsccp",

lib/Transforms/Scalar/SCCP.cpp

 
 PreservedAnalyses SCCPPass::run(Function &F, FunctionAnalysisManager &AM) {
   const DataLayout &DL = F.getParent()->getDataLayout();
   auto &TLI = AM.getResult<TargetLibraryAnalysis>(F);
   if (!runSCCP(F, DL, &TLI))
     return PreservedAnalyses::all();
 
   auto PA = PreservedAnalyses();
+  PA.preserve<DominatorTreeAnalysis>();
   PA.preserve<GlobalsAA>();
   return PA;
 }
 
 namespace {
 
 //===--------------------------------------------------------------------===//
 //
 /// SCCP Class - This class uses the SCCPSolver to implement a per-function
 /// Sparse Conditional Constant Propagator.
 ///
 class SCCPLegacyPass : public FunctionPass {
 public:
   // Pass identification, replacement for typeid
   static char ID;
 
   SCCPLegacyPass() : FunctionPass(ID) {
     initializeSCCPLegacyPassPass(*PassRegistry::getPassRegistry());
   }
 
   void getAnalysisUsage(AnalysisUsage &AU) const override {
     AU.addRequired<TargetLibraryInfoWrapperPass>();
+    AU.addPreserved<DominatorTreeWrapperPass>();
     AU.addPreserved<GlobalsAAWrapperPass>();
   }
 
   // runOnFunction - Run the Sparse Conditional Constant Propagation
   // algorithm, and return true if the function was modified.
   bool runOnFunction(Function &F) override {
     if (skipFunction(F))
       return false;

test/Other/opt-O2-pipeline.ll

 ; CHECK-NEXT:         Lazy Block Frequency Analysis
 ; CHECK-NEXT:         Optimization Remark Emitter
 ; CHECK-NEXT:         Global Value Numbering
 ; CHECK-NEXT:         Basic Alias Analysis (stateless AA impl)
 ; CHECK-NEXT:         Function Alias Analysis Results
 ; CHECK-NEXT:         Memory Dependence Analysis
 ; CHECK-NEXT:         MemCpy Optimization
 ; CHECK-NEXT:         Sparse Conditional Constant Propagation
-; CHECK-NEXT:         Dominator Tree Construction
 ; CHECK-NEXT:         Demanded bits analysis
 ; CHECK-NEXT:         Bit-Tracking Dead Code Elimination
 ; CHECK-NEXT:         Basic Alias Analysis (stateless AA impl)
 ; CHECK-NEXT:         Function Alias Analysis Results
 ; CHECK-NEXT:         Natural Loop Information
 ; CHECK-NEXT:         Lazy Branch Probability Analysis
 ; CHECK-NEXT:         Lazy Block Frequency Analysis
 ; CHECK-NEXT:         Optimization Remark Emitter

test/Other/opt-O3-pipeline.ll

 ; CHECK-NEXT:         Lazy Block Frequency Analysis
 ; CHECK-NEXT:         Optimization Remark Emitter
 ; CHECK-NEXT:         Global Value Numbering
 ; CHECK-NEXT:         Basic Alias Analysis (stateless AA impl)
 ; CHECK-NEXT:         Function Alias Analysis Results
 ; CHECK-NEXT:         Memory Dependence Analysis
 ; CHECK-NEXT:         MemCpy Optimization
 ; CHECK-NEXT:         Sparse Conditional Constant Propagation
-; CHECK-NEXT:         Dominator Tree Construction
 ; CHECK-NEXT:         Demanded bits analysis
 ; CHECK-NEXT:         Bit-Tracking Dead Code Elimination
 ; CHECK-NEXT:         Basic Alias Analysis (stateless AA impl)
 ; CHECK-NEXT:         Function Alias Analysis Results
 ; CHECK-NEXT:         Natural Loop Information
 ; CHECK-NEXT:         Lazy Branch Probability Analysis
 ; CHECK-NEXT:         Lazy Block Frequency Analysis
 ; CHECK-NEXT:         Optimization Remark Emitter

test/Other/opt-Os-pipeline.ll

 ; CHECK-NEXT:         Lazy Block Frequency Analysis
 ; CHECK-NEXT:         Optimization Remark Emitter
 ; CHECK-NEXT:         Global Value Numbering
 ; CHECK-NEXT:         Basic Alias Analysis (stateless AA impl)
 ; CHECK-NEXT:         Function Alias Analysis Results
 ; CHECK-NEXT:         Memory Dependence Analysis
 ; CHECK-NEXT:         MemCpy Optimization
 ; CHECK-NEXT:         Sparse Conditional Constant Propagation
-; CHECK-NEXT:         Dominator Tree Construction
 ; CHECK-NEXT:         Demanded bits analysis
 ; CHECK-NEXT:         Bit-Tracking Dead Code Elimination
 ; CHECK-NEXT:         Basic Alias Analysis (stateless AA impl)
 ; CHECK-NEXT:         Function Alias Analysis Results
 ; CHECK-NEXT:         Natural Loop Information
 ; CHECK-NEXT:         Lazy Branch Probability Analysis
 ; CHECK-NEXT:         Lazy Block Frequency Analysis
 ; CHECK-NEXT:         Optimization Remark Emitter