[GVN] Update BlockRPONumber prior to use.

[mattd]

Summary

The original patch addressed the use of BlockRPONumber by forcing a sequence point when accessing that map in a conditional. In short we found cases where that map was being accessed with blocks that had not yet been added to that structure. For context, I've kept the wall of text below, to what we are trying to fix, by always ensuring a updated BlockRPONumber.

Backstory

I was investigating an ICE (segfault accessing a DenseMap item). This failure happened non-deterministically, with no apparent reason and only on a Windows build of LLVM (from October 2018).

After looking into the crashes (multiple core files) and running DynamoRio, the cores and DynamoRio (DR) log pointed to the same code in GVN::performScalarPRE(). The values in the map are unsigned integers, the keys are llvm::BasicBlock*. Our test case that triggered this warning and periodic crash is rather involved. But the problematic line looks to be:

GVN.cpp: Line 2197

if (BlockRPONumber[P] >= BlockRPONumber[CurrentBlock] &&

To test things out, I cooked up a patch that accessed the items in the map outside of the condition, by forcing a sequence point between accesses. DynamoRio stopped warning of the issue, and the test didn't seem to crash after 1000+ runs.

My investigation was on an older version of LLVM, (source from October this year). What it looks like was occurring is the following, and the assembly from the latest pull of llvm in December seems to confirm this might still be an issue; however, I have not witnessed the crash on more recent builds. Of course the asm in question is generated from the host compiler on that Windows box (not clang), but it hints that we might want to consider how we access the BlockRPONumber map in this conditional (line 2197, listed above). In any case, I don't think the host compiler is wrong, rather I think it is pointing out a possibly latent bug in llvm.

1. There is no sequence point for the >= operation.

2. A call to a DenseMapBase::operator[] can have the side effect of the map reallocating a larger store (more Buckets, via a call to DenseMap::grow).

3. It seems perfectly legal for a host compiler to generate assembly that stores the result of a call to operator[] on the stack (that's what my host compile of GVN.cpp is doing) . A second call to operator[] might encourage the map to 'grow' thus making any pointers to the map's store invalid. The >= compares the first and second values. If the first happens to be a pointer produced from operator[], it could be invalid when dereferenced at the time of comparison.

The assembly generated from the Window's host compiler does show the result of the first access to the map via operator[] produces a pointer to an unsigned int. And that pointer is being stored on the stack. If a second call to the map (which does occur) causes the map to grow, that address (on the stack) is now invalid.

[efriedma]

If we're calling grow() on BlockRPONumber in this code, something has gone wrong. Both "P" and "CurrentBlock" should have an RPO number at this point in the code, so it shouldn't actually grow.

It looks like r225536 added a new caller to performScalarPRE(), and BlockRPONumber is not correctly initialized at that point. I'm surprised this hasn't led to any miscompiles.

[mattd]

Thanks for the feedback @efriedma.

In D55974#1338652, @efriedma wrote:

If we're calling grow() on BlockRPONumber in this code, something has gone wrong. Both "P" and "CurrentBlock" should have an RPO number at this point in the code, so it shouldn't actually grow.

In the body of GVN::performPRE() there is case where a block will split via a call to GVN::splitCriticalEdges. If the crit edge(s) are split, new basic blocks are introduced to the function but are not added to the BlockRPONumber map. In fact the test test/Transform/GVN/PRE/pre-basic-add.ll creates such a situation. This means that BlockRPONumber might be accessed for a basic block that has not been added to it.

It looks like r225536 added a new caller to performScalarPRE(), and BlockRPONumber is not correctly initialized at that point. I'm surprised this hasn't led to any miscompiles.

The message in r225536 does seem to suggest a periodic LTO related failure, and that is similar to what we were seeing.

[efriedma]

If the crit edge(s) are split, new basic blocks are introduced to the function but are not added to the BlockRPONumber map.

That's a bug. The RPO numbers need to be up-to-date for this check to make sense.

[mattd]

This patch aims to clean-up two items in GVN.

1 - The DenseMap BlockRPONumber in GVN should be populated by the time
performScalarPRE is called. That map is initialized when GVN starts, and only
if the EnablePRE ("-enable-pre") flag is passed (defaults to true). It seems
that no new blocks should be introduced to the function while it is being
analyzed if EnablePRE is set. If so, the values in the aforementioned map
might no longer be correct.

It turns out that performPRE can introduce new blocks via splitCriticalEdges.
performPRE can be called multiple times (until a fixed-point is found). That
routine introduces new blocks into the function being analyzed. Thus the
BlockRPONumber map should be updated when new blocks are added, but the code
currently does not update that map.

The solution in the patch here lazily updates the map just prior to its use.

2 - The other item that I think needs to be corrected was introduced in a more
recent change. That change introduced a code path that calls performScalarPRE
without checking the EnablePRE ("-enable-pre") flag. EnablePRE is responsible
for building up the BlockRPONumber map. If that flag is set to false when the
GVN pass starts, then the BlockRPONumber map will be empty.

EnablePRE is defaulted to true so it's unlikely someone will ever set it false,
outside of testing/debugging. This is probably why we we never actually see
case #2 occur (no test exists which tests "-enable-pre=false"). However,
I do think it is reasonable to add an assertion and EnablePRE check.

At this point, I'm not convinced we need a test for #1 above, as it is NFCI,
although I have a hard time saying "NFCI," because the mechanics change, but the
intended semantics should remain. It does make sense to add a test for #2 setting
'-enable-pre=false' (which no tests do) and just checking that nothing asserts. I
found an existing test that does call performScalarPRE even with EnablePRE set
to false, and have added a RUN line to test the newly added assertion does not trigger.

[efriedma]

This generally makes sense, I think.

The assumption here that blocks won't get erased during a GVN iteration is a little fragile... but probably okay. Please make BlockRPONumber a DenseMap<AssertingVH<BasicBlock>, uint32_t> to make sure no future change erases a block at an unexpected point.

lib/Transforms/Scalar/GVN.cpp

1652 ↗

(On Diff #180168)

This doesn't have the performance characteristics you want: F.size() is linear in the size of the function. Please use an explicit boolean to track invalidation.

[mattd]

• Add a bool to GVN that tracks the status (valid or invalid) of the BlockRPONumber map.
• Use that flag to indicate that the BlockRPONumber is invalid when blocks are added to the function being analyzed.
• Make the BlockRPONumber map: DenseMap<AssertingVH<BasicBlock>, uint32_t>

[efriedma]

Thinking about it a bit more, I think I'd prefer to put the change to make EnablePRE control PRE for GEPs in a separate patch. That will make it clear what's happening, and it could affect performance for anyone using that setting.

It should be straightforward to find a testcase where the old code would have used incorrect RPO numbers, even if EnablePRE isn't overridden; just add an assertion like assert(BlockRPONumber.count(P) && BlockRPONumber.count(CurrentBlock); to GVN::performScalarPRE, and run that compiler over some code. Actually, maybe worth adding that assert anyway.

[mattd]

• Moved the logic for controlling access to performPRE/performScalarPRE functions into a separate patch.
• Added an assertion that will trigger on 9 tests if the BlockRPONumber map is invalid. In particular, test/Transforms/GVN/nonescaping-malloc.ll, which also requires an assert build when testing.

[efriedma]

LGTM.

In theory, it's probably possible to construct a test where the lack of BlockRPONumber actually affects the generated IR. But it's not worth spending the time on that... the assertions give enough coverage.

llvm/trunk/include/llvm/Transforms/Scalar/GVN.h

 #include "llvm/ADT/SetVector.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/Analysis/AliasAnalysis.h"
 #include "llvm/Analysis/InstructionPrecedenceTracking.h"
 #include "llvm/Analysis/MemoryDependenceAnalysis.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/InstrTypes.h"
 #include "llvm/IR/PassManager.h"
+#include "llvm/IR/ValueHandle.h"
 #include "llvm/Support/Allocator.h"
 #include "llvm/Support/Compiler.h"
 #include <cstdint>
 #include <utility>
 #include <vector>
 
 namespace llvm {
 
private:
   // Block-local map of equivalent values to their leader, does not
   // propagate to any successors. Entries added mid-block are applied
   // to the remaining instructions in the block.
   SmallMapVector<Value *, Constant *, 4> ReplaceWithConstMap;
   SmallVector<Instruction *, 8> InstrsToErase;
 
   // Map the block to reversed postorder traversal number. It is used to
   // find back edge easily.
-  DenseMap<const BasicBlock *, uint32_t> BlockRPONumber;
+  DenseMap<AssertingVH<BasicBlock>, uint32_t> BlockRPONumber;
+
+  // This is set 'true' initially and also when new blocks have been added to
+  // the function being analyzed. This boolean is used to control the updating
+  // of BlockRPONumber prior to accessing the contents of BlockRPONumber.
+  bool InvalidBlockRPONumbers = true;
 
   using LoadDepVect = SmallVector<NonLocalDepResult, 64>;
   using AvailValInBlkVect = SmallVector<gvn::AvailableValueInBlock, 64>;
   using UnavailBlkVect = SmallVector<BasicBlock *, 64>;
 
   bool runImpl(Function &F, AssumptionCache &RunAC, DominatorTree &RunDT,
                const TargetLibraryInfo &RunTLI, AAResults &RunAA,
                MemoryDependenceResults *RunMD, LoopInfo *LI,

llvm/trunk/lib/Transforms/Scalar/GVN.cpp

static bool isOnlyReachableViaThisEdge(const BasicBlockEdge &E,
   // been changed to have only one predecessor, namely Src.
   const BasicBlock *Pred = E.getEnd()->getSinglePredecessor();
   assert((!Pred || Pred == E.getStart()) &&
          "No edge between these basic blocks!");
   return Pred != nullptr;
 }
 
 void GVN::assignBlockRPONumber(Function &F) {
+  BlockRPONumber.clear();
   uint32_t NextBlockNumber = 1;
   ReversePostOrderTraversal<Function *> RPOT(&F);
   for (BasicBlock *BB : RPOT)
     BlockRPONumber[BB] = NextBlockNumber++;
+  InvalidBlockRPONumbers = false;
 }
 
 // Tries to replace instruction with const, using information from
 // ReplaceWithConstMap.
 bool GVN::replaceOperandsWithConsts(Instruction *Instr) const {
   bool Changed = false;
   for (unsigned OpNum = 0; OpNum < Instr->getNumOperands(); ++OpNum) {
     Value *Operand = Instr->getOperand(OpNum);
bool GVN::runImpl(Function &F, AssumptionCache &RunAC, DominatorTree &RunDT,
   VN.setDomTree(DT);
   TLI = &RunTLI;
   VN.setAliasAnalysis(&RunAA);
   MD = RunMD;
   ImplicitControlFlowTracking ImplicitCFT(DT);
   ICF = &ImplicitCFT;
   VN.setMemDep(MD);
   ORE = RunORE;
+  InvalidBlockRPONumbers = true;
 
   bool Changed = false;
   bool ShouldContinue = true;
 
   DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Eager);
   // Merge unconditional branches, allowing PRE to catch more
   // optimization opportunities.
   for (Function::iterator FI = F.begin(), FE = F.end(); FI != FE; ) {
while (ShouldContinue) {
     Changed |= ShouldContinue;
     ++Iteration;
   }
 
   if (EnablePRE) {
     // Fabricate val-num for dead-code in order to suppress assertion in
     // performPRE().
     assignValNumForDeadCode();
-    assignBlockRPONumber(F);
     bool PREChanged = true;
     while (PREChanged) {
       PREChanged = performPRE(F);
       Changed |= PREChanged;
     }
   }
 
   // FIXME: Should perform GVN again after PRE does something.  PRE can move
bool GVN::performScalarPRE(Instruction *CurInst) {
   // but not the other.  We also explicitly disallow cases
   // where the successor is its own predecessor, because they're
   // more complicated to get right.
   unsigned NumWith = 0;
   unsigned NumWithout = 0;
   BasicBlock *PREPred = nullptr;
   BasicBlock *CurrentBlock = CurInst->getParent();
 
+  // Update the RPO numbers for this function.
+  if (InvalidBlockRPONumbers)
+    assignBlockRPONumber(*CurrentBlock->getParent());
+
   SmallVector<std::pair<Value *, BasicBlock *>, 8> predMap;
   for (BasicBlock *P : predecessors(CurrentBlock)) {
     // We're not interested in PRE where blocks with predecessors that are
     // not reachable.
     if (!DT->isReachableFromEntry(P)) {
       NumWithout = 2;
       break;
     }
     // It is not safe to do PRE when P->CurrentBlock is a loop backedge, and
     // when CurInst has operand defined in CurrentBlock (so it may be defined
     // by phi in the loop header).
+    assert(BlockRPONumber.count(P) && BlockRPONumber.count(CurrentBlock) &&
+           "Invalid BlockRPONumber map.");
     if (BlockRPONumber[P] >= BlockRPONumber[CurrentBlock] &&
         llvm::any_of(CurInst->operands(), [&](const Use &U) {
           if (auto *Inst = dyn_cast<Instruction>(U.get()))
             return Inst->getParent() == CurrentBlock;
           return false;
         })) {
       NumWithout = 2;
       break;

 
 /// Split the critical edge connecting the given two blocks, and return
 /// the block inserted to the critical edge.
 BasicBlock *GVN::splitCriticalEdges(BasicBlock *Pred, BasicBlock *Succ) {
   BasicBlock *BB =
       SplitCriticalEdge(Pred, Succ, CriticalEdgeSplittingOptions(DT));
   if (MD)
     MD->invalidateCachedPredecessors();
+  InvalidBlockRPONumbers = true;
   return BB;
 }
 
 /// Split critical edges found during the previous
 /// iteration that may enable further optimization.
 bool GVN::splitCriticalEdges() {
   if (toSplit.empty())
     return false;
   do {
     std::pair<Instruction *, unsigned> Edge = toSplit.pop_back_val();
     SplitCriticalEdge(Edge.first, Edge.second,
                       CriticalEdgeSplittingOptions(DT));
   } while (!toSplit.empty());
   if (MD) MD->invalidateCachedPredecessors();
+  InvalidBlockRPONumbers = true;
   return true;
 }
 
 /// Executes one iteration of GVN
 bool GVN::iterateOnFunction(Function &F) {
   cleanupGlobalSets();
 
   // Top-down walk of the dominator tree

 }
 
 void GVN::cleanupGlobalSets() {
   VN.clear();
   LeaderTable.clear();
   BlockRPONumber.clear();
   TableAllocator.Reset();
   ICF->clear();
+  InvalidBlockRPONumbers = true;
 }
 
 /// Verify that the specified instruction does not occur in our
 /// internal data structures.
 void GVN::verifyRemoved(const Instruction *Inst) const {
   VN.verifyRemoved(Inst);
 
   // Walk through the value number scope to make sure the instruction isn't