Bugpoint-reduced testcase

Valgrind trace:

==30339==
==30339== Process terminating with default action of signal 11 (SIGSEGV)
==30339== Access not within mapped region at address 0x1C
==30339== at 0x856B7F5: llvm::ETNode::Below(llvm::ETNode*) (Dominators.cpp:690)
==30339== by 0x83E4513: llvm::ETNode::DominatedBySlow(llvm::ETNode*)
(ET-Forest.h:251)
==30339== by 0x83E44F0: llvm::ETForestBase::dominates(llvm::BasicBlock*,
llvm::BasicBlock*) (Dominators.h:295)
==30339== by 0x848222E: llvm::SplitCriticalEdge(llvm::TerminatorInst*,
unsigned, llvm::Pass*, bool) (BreakCriticalEdges.cpp:187)
==30339== by 0x84489C6: (anonymous
namespace)::LoopUnswitch::SplitEdge(llvm::BasicBlock*, llvm::BasicBlock*)
(LoopUnswitch.cpp:412)
==30339== by 0x844937E: (anonymous
namespace)::LoopUnswitch::UnswitchNontrivialCondition(llvm::Value*,
llvm::Constant*, llvm::Loop*) (LoopUnswitch.cpp:572)
==30339== by 0x844882C: (anonymous
namespace)::LoopUnswitch::UnswitchIfProfitable(llvm::Value*, llvm::Constant*,
llvm::Loop*) (LoopUnswitch.cpp:375)
==30339== by 0x8448008: (anonymous
namespace)::LoopUnswitch::runOnLoop(llvm::Loop*, llvm::LPPassManager&)
(LoopUnswitch.cpp:162)
==30339== by 0x84F4F40: llvm::LPPassManager::runOnFunction(llvm::Function&)
(LoopPass.cpp:201)
==30339== by 0x859E421: llvm::FPPassManager::runOnFunction(llvm::Function&)
(PassManager.cpp:1074)
==30339== by 0x859E5D1: llvm::FPPassManager::runOnModule(llvm::Module&)
(PassManager.cpp:1093)
==30339== by 0x859E741: llvm::MPPassManager::runOnModule(llvm::Module&)
(PassManager.cpp:1142)

This is due to a bug in the pass manager where BreakCriticalEdges, called via Loop Unswitch, thinks it
should update the DomTree/ETForest when in fact it shouldn't. This raises two points:

1. LoopUnswitch really ought to preserve DomTree and ETForest. This will probably happen once I finish
   my work on LLVM needs a generic update SSA mechanism #589 .

2. Someone should look at what's causing LoopPassManager->getAnalysisToUpdate() to
   return something when it should return null.

Dom info is available at loop-unswitch pass entry. So it is appropriate for pass manager to return its
reference. PM removes dom info from the list of available analysis info after loop-unswitch is run,
because dom info is not preserved.

One alternative is to remove not-preserved not-required info before running a pass. However, it won't
work in this particular example.

No, it's not appropriate for the pass manager to return it, because getAnalysisToUpdate<...>() is being
called, not getAnalysis<...>. In the used-but-not-updated case, the former should return null while the
latter should return the analysis. In the not-used-and-not-updated case, both should return null.

You are mistaken.

1. getAnalysis<..>( ) never returns NULL. It will assert if analysis is not available.
2. getAnalysisToUpdate<...>() returns NULL, if analysis is not available, irrespective of whether it is listed
   as required analysis or not.

In this particular example, analysis is available.

You're right that I was mistaken about getAnalysis<..>( ). I forgot that it returns a reference rather than a
pointer, so it should assert if called in any not-used case.

What I am saying, however, is that the behavior of getAnalysisToUpdate<...>() is not consistent with its
intended use, i.e. that it should return null in a pass that does not preserve the analysis. Several passes
make decisions based on the null-ness or non-nullness of the returned pointer, so, while none has caused
a bug before, it is entirely possible that it is causing unneeded work to be done.

If a pass is not preserving analysis A then it should not call getAnalysisToUpdate() :)

In this example, LoopUnswitch is not preserving dom info and it is not calling getAnalysisToUpdate. Here,
BreakCriticalEdge invokes getAnalysisToUpdate<>() because it is trying to preserve analysis. But guess
what, pass manager does not know about BreakCriticalEdge! LoopUnswitch pass made unfortunate choice
of using another pass indirectly (or directly, depending on how you see it) without conveying another
pass's getAnalysisUsage() info to pass manager.

It may be possible to over engineer this in pass manager, but in this example right thing to do is fix loop
unswitch.

If getAnalysisToUpdate<...>() should never be called on a non-preserving Pass, could we make it assert if
it is? That would at least prevent such mistakes in the future.

I do agree that LoopUnswitch should preserve dominator analyses, but I won't have a chance to implement
it until after I finish changing around the analyses themselves.

Another crash case of the same issue
Here's another bytecode that exhibits the same problem that Evan found.

Candidate patch to fix crash.

Filed PR 1402 to track dom info update in LoopUnswitch pass

Fixed by updating LoopUnswitch pass to preserve loop info after invoking SplitCriticalEdge(). Now,
LoopUnswitch does not request SplitCriticalEdge() to update dominator info and loop info. This means,
loop unswitch does not preserve dominator info at the moment.

http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20070507/049453.html

mentioned in issue llvm/llvm-bugzilla-archive#1342

mentioned in issue llvm/llvm-bugzilla-archive#1724