[Local] Make DoesKMove required for combineMetadata.

[fhahn]

Summary

This patch makes the DoesKMove argument non-optional, to force people
to think about it. Most cases where it is false are either code hoisting
or code sinking, where we pick one instruction from a set of
equal instructions among different code paths.

[efriedma]

Yes, this makes sense. But definitely needs tests.

[fhahn]

Added tests for most cases. Missing are tests for MemCpyOptimizer and SimplifyCFG, but for those nothing changed, so would that be enough?

[efriedma]

lib/Transforms/Utils/Local.cpp

2075

Is it actually correct to use the same metadata list if KDominatesJ is false?

It's undefined behavior if a nonnull load actually produces null. So preserving nonnull metadata on a hoisted load requires proving that the hoisted load never produces null (separately from proving the load is safe to hoist).

[• dberlin]

lib/Transforms/Utils/Local.cpp

2075

Yeah, i'm pretty sure there are some pre-existing bugs here, and this looks like it may be one of them.

I admit to wondering what we actually expect here.
The langref just says "The existence of the !nonnull metadata on the instruction tells the optimizer that the value loaded is known to never be null. "

Does that mean "never to be null when performed in this place in the instruction stream" or just "never be null. "

If the former, then yeah, when hoisting, we need to prove nonnullness or drop it.
If the latter, then hoisting would be fine.

I wonder how this is getting used in practice (IE are people treating it like the former/latter, and if the latter, do they expect hoisting to drop non-nullness).

[efriedma]

lib/Transforms/Utils/Local.cpp

2075

Actually, I guess none of the existing callers actually do that sort of hoisting.

But combineMetadataForCSE needs better documentation for when, exactly, it's correct to use.

[efriedma]

lib/Transforms/Utils/Local.cpp

2075

I'm not sure how you could usefully interpret the definition of !nonnull as anything other than "if the loaded value is null, the behavior is undefined", given that the optimizer can introduce impossible codepaths.

[fhahn]

lib/Transforms/Utils/Local.cpp

2075

Is it actually correct to use the same metadata list if KDominatesJ is false?

The default behavior for nonnull metadata did not change if KDominatesJ is false, it only combines nonnull md if both K and J have it.

IIUC if combineMetadata is used correctly, propagating nonnull from K to a dominated instr J is OK.

It would not be OK, (1) if K is later hoisted to a place where nonnull is not guaranteed to hold, but moving K is causing the undefined behavior, not combining of the metadata. And (2) if the loaded value might become null between K and J. For that to happen, the value needs to be modified and K would not be a valid replacement for J.

Am I missing something? The docs for combineMetadataForCSE state that K must be able to replace J, but is it worth to spelling it out more explicitly what that means?

[efriedma]

lib/Transforms/Utils/Local.cpp

2075

Yes, it would be better to spell it out.

[nlopes]

lib/Transforms/Utils/Local.cpp

2075

Just seconding what Daniel wrote: if a "load !nonnull" is UB if it loads null, then it cannot be hoisted (without dropping the flag). Instead it could rather yield poison.
Either is fine; I haven't done any study on what are common uses of !nonnull to be able vote either way.
While at it, updating LangRef to be more explicit about this case would be very much appreciated :)

[fhahn]

Rebased after Local.h got moved. I've also added additional details to the comment for combineMetadataForCSE and added a few more CHECK-NOT lines to the negative tests.

[fhahn]

lib/Transforms/Utils/Local.cpp

2075

I've tweaked the comment, does it make sense now? Thanks Eli for updating the LangRef in D47747

[fhahn]

ping. The langref now says the following about !nonnull loads: The existence of the !nonnull metadata on the instruction tells the optimizer that the value loaded is known to never be null. If the value is null at runtime, the behavior is undefined.. With the value being null at runetime being UB, keeping nonnull on dominating loads should be ok IIUC.

[efriedma]

Given that it's UB to violate nonnull metadata, the metadata on J doesn't actually matter; the important question is whether K moves. If it does, we have to strip the nonnull metadata; it it doesn't, we don't. So "KDominatesJ" shouldn't exist, as far as I can tell; the boolean should just be "DoesKMove".

[fhahn]

In D47475#1167326, @efriedma wrote:

Given that it's UB to violate nonnull metadata, the metadata on J doesn't actually matter; the important question is whether K moves. If it does, we have to strip the nonnull metadata; it it doesn't, we don't. So "KDominatesJ" shouldn't exist, as far as I can tell; the boolean should just be "DoesKMove".

Hm I realize "KDominatesJ" is not too clear, as we could hoist an instruction before running combineMetadata. It was meant to mean "in the original IR, K dominated J", so before any moving/hoisting. "DoesKMove" sounds slightly clearer. D47339 only uses the fact to not drop K's metadata if K does not move, as this enables keeping nonnull in more valid cases.

If combineMetadata is used to combine the metadata from l1 and l2 (which would preserve !nonnull, as both loads have it) and l1 gets hoisted, that would be illegal IIUC. However it looks like when we do hoisting, we create a new load without metadata, so this should not be a problem in existing code. Also it allows sinking a load and preserving the nonnull metadata, if there are loads in all predecessors and they all have nonnull.

  br i1 %x, label %bb2, label %bb2

bb1:
  ....
  %l1 = load .... !nonnull !0
  ....

bb2:
  ...
  %l2 = load .... !nonnull !0

What do you think?

[efriedma]

Also it allows sinking a load and preserving the nonnull metadata, if there are loads in all predecessors and they all have nonnull.

I would prefer to handle that specific case in some different way; it's not the same sort of reasoning. In the CSE case, it doesn't matter whether J has nonnull metadata.

[fhahn]

In D47475#1168792, @efriedma wrote:

Also it allows sinking a load and preserving the nonnull metadata, if there are loads in all predecessors and they all have nonnull.

I would prefer to handle that specific case in some different way; it's not the same sort of reasoning. In the CSE case, it doesn't matter whether J has nonnull metadata.

Sounds good. Would it be OK to make combineMetadata stricter in that respect for the relevant metadata kinds in a follow up commit? Doing it step-by-step seems slightly easier to me, but I could also fold it into this or the previous patch if you think that's better.

[efriedma]

Doing it in steps is fine, sure.

[fhahn]

Update to account for DoesKMove.

[fhahn]

Ping. Once that's in, I'll prepare a patch to handle the the CSE case outside of combineMetadata

[fhahn]

ping

[davide]

I think this is fine, but I would be happier if Eli can take a look, as I'm not particularly familiar with this.

[efriedma]

LGTM

include/llvm/Analysis/Utils/Local.h

 bool removeUnreachableBlocks(Function &F, LazyValueInfo *LVI = nullptr,
                              DeferredDominance *DDT = nullptr);
 
 /// Combine the metadata of two instructions so that K can replace J. Some
 /// metadata kinds can only be kept if K dominates J.
 ///
 /// Metadata not listed as known via KnownIDs is removed
 void combineMetadata(Instruction *K, const Instruction *J,
-                     ArrayRef<unsigned> KnownIDs, bool KDominatesJ = false);
+                     ArrayRef<unsigned> KnownIDs, bool KDominatesJ);
 
 /// Combine the metadata of two instructions so that K can replace J. This
 /// specifically handles the case of CSE-like transformations.
 ///
 /// Unknown metadata is removed.
-void combineMetadataForCSE(Instruction *K, const Instruction *J);
+void combineMetadataForCSE(Instruction *K, const Instruction *J,
+                           bool KDominatesJ);
 
 /// Patch the replacement so that it is not more restrictive than the value
 /// being replaced. It assumes Repl dominates I.
 void patchReplacementInstruction(Instruction *I, Value *Repl);
 
 // Replace each use of 'From' with 'To', if that use does not belong to basic
 // block where 'From' is defined. Returns the number of replacements made.
 unsigned replaceNonLocalUsesWith(Instruction *From, Value *To);

lib/Transforms/InstCombine/InstCombineLoadStoreAlloca.cpp

Instruction *InstCombiner::visitLoadInst(LoadInst &LI) {
   // Do really simple store-to-load forwarding and load CSE, to catch cases
   // where there are several consecutive memory accesses to the same location,
   // separated by a few arithmetic operations.
   BasicBlock::iterator BBI(LI);
   bool IsLoadCSE = false;
   if (Value *AvailableVal = FindAvailableLoadedValue(
           &LI, LI.getParent(), BBI, DefMaxInstsToScan, AA, &IsLoadCSE)) {
     if (IsLoadCSE)
-      combineMetadataForCSE(cast<LoadInst>(AvailableVal), &LI);
+      combineMetadataForCSE(cast<LoadInst>(AvailableVal), &LI, true);
 
     return replaceInstUsesWith(
         LI, Builder.CreateBitOrPointerCast(AvailableVal, LI.getType(),
                                            LI.getName() + ".cast"));
   }
 
   // None of the following transforms are legal for volatile/ordered atomic
   // loads.  Most of them do apply for unordered atomics.

lib/Transforms/InstCombine/InstCombinePHI.cpp

Instruction *InstCombiner::FoldPHIArgLoadIntoPHI(PHINode &PN) {
   };
 
   for (unsigned ID : KnownIDs)
     NewLI->setMetadata(ID, FirstLI->getMetadata(ID));
 
   // Add all operands to the new PHI and combine TBAA metadata.
   for (unsigned i = 1, e = PN.getNumIncomingValues(); i != e; ++i) {
     LoadInst *LI = cast<LoadInst>(PN.getIncomingValue(i));
-    combineMetadata(NewLI, LI, KnownIDs);
+    combineMetadata(NewLI, LI, KnownIDs, false);
     Value *NewInVal = LI->getOperand(0);
     if (NewInVal != InVal)
       InVal = nullptr;
     NewPN->addIncoming(NewInVal, PN.getIncomingBlock(i));
   }
 
   if (InVal) {
     // The new PHI unions all of the same values together.  This is really

lib/Transforms/Scalar/GVNHoist.cpp

 };
 
 static void combineKnownMetadata(Instruction *ReplInst, Instruction *I) {
   static const unsigned KnownIDs[] = {
       LLVMContext::MD_tbaa,           LLVMContext::MD_alias_scope,
       LLVMContext::MD_noalias,        LLVMContext::MD_range,
       LLVMContext::MD_fpmath,         LLVMContext::MD_invariant_load,
       LLVMContext::MD_invariant_group};
-  combineMetadata(ReplInst, I, KnownIDs);
+  combineMetadata(ReplInst, I, KnownIDs, false);
 }
 
 // This pass hoists common computations across branches sharing common
 // dominator. The primary goal is to reduce the code size, and in some
 // cases reduce critical path (by exposing more ILP).
 class GVNHoist {
 public:
   GVNHoist(DominatorTree *DT, PostDominatorTree *PDT, AliasAnalysis *AA,

lib/Transforms/Scalar/GVNSink.cpp

void GVNSink::sinkLastInstruction(ArrayRef<BasicBlock *> Blocks,
   // and move it to the start of the successor block.
   for (unsigned O = 0, E = I0->getNumOperands(); O != E; ++O)
     I0->getOperandUse(O).set(NewOperands[O]);
   I0->moveBefore(&*BBEnd->getFirstInsertionPt());
 
   // Update metadata and IR flags.
   for (auto *I : Insts)
     if (I != I0) {
-      combineMetadataForCSE(I0, I);
+      combineMetadataForCSE(I0, I, false);
       I0->andIRFlags(I);
     }
 
   for (auto *I : Insts)
     if (I != I0)
       I->replaceAllUsesWith(I0);
   foldPointlessPHINodes(BBEnd);
 

lib/Transforms/Scalar/JumpThreading.cpp

bool JumpThreadingPass::SimplifyPartiallyRedundantLoad(LoadInst *LoadI) {
   bool IsLoadCSE;
   if (Value *AvailableVal = FindAvailableLoadedValue(
           LoadI, LoadBB, BBIt, DefMaxInstsToScan, AA, &IsLoadCSE)) {
     // If the value of the load is locally available within the block, just use
     // it.  This frequently occurs for reg2mem'd allocas.
 
     if (IsLoadCSE) {
       LoadInst *NLoadI = cast<LoadInst>(AvailableVal);
-      combineMetadataForCSE(NLoadI, LoadI);
+      combineMetadataForCSE(NLoadI, LoadI, true);
     };
 
     // If the returned value is the load itself, replace with an undef. This can
     // only happen in dead loops.
     if (AvailableVal == LoadI)
       AvailableVal = UndefValue::get(LoadI->getType());
     if (AvailableVal->getType() != LoadI->getType())
       AvailableVal = CastInst::CreateBitOrPointerCast(
for (pred_iterator PI = PB; PI != PE; ++PI) {
     if (PredV->getType() != LoadI->getType())
       PredV = CastInst::CreateBitOrPointerCast(PredV, LoadI->getType(), "",
                                                P->getTerminator());
 
     PN->addIncoming(PredV, I->first);
   }
 
   for (LoadInst *PredLoadI : CSELoads) {
-    combineMetadataForCSE(PredLoadI, LoadI);
+    combineMetadataForCSE(PredLoadI, LoadI, false);
   }
 
   LoadI->replaceAllUsesWith(PN);
   LoadI->eraseFromParent();
 
   return true;
 }
 

lib/Transforms/Scalar/MemCpyOptimizer.cpp

bool MemCpyOptPass::performCallSlotOptzn(Instruction *cpy, Value *cpyDest,
   MD->removeInstruction(C);
 
   // Update AA metadata
   // FIXME: MD_tbaa_struct and MD_mem_parallel_loop_access should also be
   // handled here, but combineMetadata doesn't support them yet
   unsigned KnownIDs[] = {LLVMContext::MD_tbaa, LLVMContext::MD_alias_scope,
                          LLVMContext::MD_noalias,
                          LLVMContext::MD_invariant_group};
-  combineMetadata(C, cpy, KnownIDs);
+  combineMetadata(C, cpy, KnownIDs, false);
 
   // Remove the memcpy.
   MD->removeInstruction(cpy);
   ++NumMemCpyInstr;
 
   return true;
 }
 

lib/Transforms/Utils/Local.cpp

void llvm::combineMetadata(Instruction *K, const Instruction *J,
   // could produce bitcast with invariant.group metadata, which is invalid.
   // FIXME: we should try to preserve both invariant.group md if they are
   // different, but right now instruction can only have one invariant.group.
   if (auto *JMD = J->getMetadata(LLVMContext::MD_invariant_group))
     if (isa<LoadInst>(K) || isa<StoreInst>(K))
       K->setMetadata(LLVMContext::MD_invariant_group, JMD);
 }
 
-void llvm::combineMetadataForCSE(Instruction *K, const Instruction *J) {
+void llvm::combineMetadataForCSE(Instruction *K, const Instruction *J,
+                                 bool KDominatesJ) {
   unsigned KnownIDs[] = {
       LLVMContext::MD_tbaa,            LLVMContext::MD_alias_scope,
       LLVMContext::MD_noalias,         LLVMContext::MD_range,
       LLVMContext::MD_invariant_load,  LLVMContext::MD_nonnull,
       LLVMContext::MD_invariant_group, LLVMContext::MD_align,
       LLVMContext::MD_dereferenceable,
       LLVMContext::MD_dereferenceable_or_null};
-  combineMetadata(K, J, KnownIDs);
+  combineMetadata(K, J, KnownIDs, KDominatesJ);
 }
 
 void llvm::patchReplacementInstruction(Instruction *I, Value *Repl) {
   auto *ReplInst = dyn_cast<Instruction>(Repl);
   if (!ReplInst)
     return;
 
   // Patch the replacement so that it is not more restrictive than the value

lib/Transforms/Utils/SimplifyCFG.cpp

if (isa<DbgInfoIntrinsic>(I1) || isa<DbgInfoIntrinsic>(I2)) {
                              LLVMContext::MD_fpmath,
                              LLVMContext::MD_invariant_load,
                              LLVMContext::MD_nonnull,
                              LLVMContext::MD_invariant_group,
                              LLVMContext::MD_align,
                              LLVMContext::MD_dereferenceable,
                              LLVMContext::MD_dereferenceable_or_null,
                              LLVMContext::MD_mem_parallel_loop_access};
-      combineMetadata(I1, I2, KnownIDs);
+      combineMetadata(I1, I2, KnownIDs, false);
 
       // I1 and I2 are being combined into a single instruction.  Its debug
       // location is the merged locations of the original instructions.
       I1->applyMergedLocation(I1->getDebugLoc(), I2->getDebugLoc());
 
       I2->eraseFromParent();
       Changed = true;
     }
if (I != I0) {
       // The debug location for the "common" instruction is the merged locations
       // of all the commoned instructions.  We start with the original location
       // of the "common" instruction and iteratively merge each location in the
       // loop below.
       // This is an N-way merge, which will be inefficient if I0 is a CallInst.
       // However, as N-way merge for CallInst is rare, so we use simplified API
       // instead of using complex API for N-way merge.
       I0->applyMergedLocation(I0->getDebugLoc(), I->getDebugLoc());
-      combineMetadataForCSE(I0, I);
+      combineMetadataForCSE(I0, I, false);
       I0->andIRFlags(I);
     }
 
   if (!isa<StoreInst>(I0)) {
     // canSinkLastInstruction checked that all instructions were used by
     // one and only one PHI node. Find that now, RAUW it to our common
     // instruction and nuke it.
     assert(I0->hasOneUse());