[PATCH 16/27] [noalias] Clone scopes and llvm.noalias.decl when unrolling.

[jeroen.dobbelaere]

Summary

This is part of the series started by D68484.

Restrict variables that are declared inside a loop must get
an unique scope when the loop body is unrolled.

Note: this is a stable point and tests should run fine with the patches applied up to this point.

[jeroen.dobbelaere]

Rebased

[marksl]

I assume that a similar fix would then be necessary for loop peeling (and any such loop optimization that clones blocks).

[jeroen.dobbelaere]

In D68510#1945043, @marksl wrote:

I assume that a similar fix would then be necessary for loop peeling (and any such loop optimization that clones blocks).

Yes. Whenever a body that contains a restrict declaration (llvm.noalias.decl), care must be taken to handle the associated noalias scope in a correct way:

• when the cloning is done because of 'unrolling' (or peeling), the scopes associated to those declarations must be made unique (aka, each iteration has its own scope)
  • As D68511 shows, loop rotation is more complicated, as only parts of a body are duplicated..
• when the cloning is done for efficiency of different code paths (loop unswitching could be a good example here), both versions can (re)use the same scope.
  • Note: it would also be valid to uniquify them, but it is not needed for correctness.

[danilaml]

llvm/lib/Transforms/Utils/NoAliasUtils.cpp

174

SNAN name can conflict with SNAN macro in math.h

[jeroen.dobbelaere]

Rebased to c06b7e2ab5167ad031745a706204abed1aefd823 (July 14, 2020)

[jeroen.dobbelaere]

Rebased to 9fb46a452d4e5666828c95610ceac8dcd9e4ce16 (September 7, 2020)

[jeroen.dobbelaere]

Rebased to f8dbd61074176bae92ec360a093ac7bc498c9321.

llvm/include/llvm/Transforms/Utils/NoAliasUtils.h

 //===- llvm/Transforms/Utils/NoAliasUtils.h - NoAlias utilities -*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
 // This file defines utilities for noalias metadata and intrinsics.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_TRANSFORMS_UTILS_NOALIASUTILS_H
 #define LLVM_TRANSFORMS_UTILS_NOALIASUTILS_H
 
+#include "llvm/ADT/ArrayRef.h"
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/SetVector.h"
+#include "llvm/ADT/SmallPtrSet.h"
+#include "llvm/ADT/SmallVector.h"
+#include "llvm/ADT/StringRef.h"
+#include "llvm/IR/Instructions.h"
+#include "llvm/IR/IntrinsicInst.h"
+
 namespace llvm {
 class Function;
 
 /// Connect llvm.noalias.decl to noalias/side.noalias intrinsics that are
 /// associated with the unknown function scope and based on the same alloca.
 /// At the same time, propagate the p.addr, p.objId and p.scope.
 bool propagateAndConnectNoAliasDecl(Function *F);
+
+/// Find back the 'llvm.noalias.decl' intrinsics in the specified basic blocks
+/// and extract their scope. This are candidates for duplication when cloning.
+template <typename C>
+void identifyNoAliasScopesToClone(ArrayRef<BasicBlock *> BBs,
+                                  C &out_NoAliasDeclScopes) {
+  for (auto BB : BBs) {
+    for (Instruction &I : *BB) {
+      if (auto II = dyn_cast<IntrinsicInst>(&I)) {
+        if (II->getIntrinsicID() == Intrinsic::noalias_decl) {
+          out_NoAliasDeclScopes.push_back(cast<MetadataAsValue>(
+              II->getOperand(Intrinsic::NoAliasDeclScopeArg)));
+        }
+      }
+    }
+  }
+}
+
+/// Duplicate the specified list of noalias decl scopes.
+/// The 'Ext' string is added as an extension to the name.
+/// Afterwards, the out_ClonedMVScopes contains a mapping of the original MV
+/// onto the cloned version.
+/// The out_ClonedScopes contains the mapping of the original scope MDNode
+/// onto the cloned scope.
+void cloneNoAliasScopes(
+    ArrayRef<MetadataAsValue *> NoAliasDeclScopes,
+    DenseMap<MDNode *, MDNode *> &out_ClonedScopes,
+    DenseMap<MetadataAsValue *, MetadataAsValue *> &out_ClonedMVScopes,
+    StringRef Ext, LLVMContext &Context);
+
+/// Adapt the metadata for the specified instruction according to the
+/// provided mapping. This is normally used after cloning an instruction, when
+/// some noalias scopes needed to be cloned.
+void adaptNoAliasScopes(
+    Instruction *I, DenseMap<MDNode *, MDNode *> &ClonedScopes,
+    DenseMap<MetadataAsValue *, MetadataAsValue *> &ClonedMVScopes,
+    LLVMContext &Context);
+
+/// Clone the specified noalias decl scopes. Then adapt all instructions in the
+/// NewBlocks basicblocks to the cloned versions.
+/// 'Ext' will be added to the duplicate scope names
+void cloneAndAdaptNoAliasScopes(ArrayRef<MetadataAsValue *> NoAliasDeclScopes,
+                                ArrayRef<BasicBlock *> NewBlocks,
+                                LLVMContext &Context, StringRef Ext);
 } // end namespace llvm
 
 #endif // LLVM_TRANSFORMS_UTILS_NOALIASUTILS_H

llvm/lib/Transforms/Utils/LoopUnroll.cpp

 
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/AssumptionCache.h"
 #include "llvm/Analysis/InstructionSimplify.h"
 #include "llvm/Analysis/LoopIterator.h"
 #include "llvm/Analysis/OptimizationRemarkEmitter.h"
 #include "llvm/Analysis/ScalarEvolution.h"
-#include "llvm/Transforms/Utils/Local.h"
 #include "llvm/IR/BasicBlock.h"
 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/DebugInfoMetadata.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/IntrinsicInst.h"
 #include "llvm/IR/LLVMContext.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/raw_ostream.h"
 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
 #include "llvm/Transforms/Utils/Cloning.h"
+#include "llvm/Transforms/Utils/Local.h"
 #include "llvm/Transforms/Utils/LoopSimplify.h"
 #include "llvm/Transforms/Utils/LoopUtils.h"
+#include "llvm/Transforms/Utils/NoAliasUtils.h"
 #include "llvm/Transforms/Utils/SimplifyIndVar.h"
 #include "llvm/Transforms/Utils/UnrollLoop.h"
 using namespace llvm;
 
 #define DEBUG_TYPE "loop-unroll"
 
 // TODO: Should these be here or in LoopUnroll?
 STATISTIC(NumCompletelyUnrolled, "Number of loops completely unrolled");
for (BasicBlock *BB : L->getBlocks())
             if (NewDIL)
               I.setDebugLoc(NewDIL.getValue());
             else
               LLVM_DEBUG(dbgs()
                          << "Failed to create new discriminator: "
                          << DIL->getFilename() << " Line: " << DIL->getLine());
           }
 
+  // Phase1: Identify what noalias metadata is inside the loop: if it is inside
+  // the loop, the associated metadata must be clone for each iteration.
+  SmallVector<MetadataAsValue *, 6> LoopLocalNoAliasDeclScopes;
+  llvm::identifyNoAliasScopesToClone(L->getBlocks(),
+                                     LoopLocalNoAliasDeclScopes);
+
   for (unsigned It = 1; It != ULO.Count; ++It) {
     std::vector<BasicBlock*> NewBlocks;
     SmallDenseMap<const Loop *, Loop *, 4> NewLoops;
     NewLoops[L] = L;
 
     for (LoopBlocksDFS::RPOIterator BB = BlockBegin; BB != BlockEnd; ++BB) {
       ValueToValueMapTy VMap;
       BasicBlock *New = CloneBasicBlock(*BB, VMap, "." + Twine(It));
for (unsigned It = 1; It != ULO.Count; ++It) {
     for (BasicBlock *NewBlock : NewBlocks) {
       for (Instruction &I : *NewBlock) {
         ::remapInstruction(&I, LastValueMap);
         if (auto *II = dyn_cast<IntrinsicInst>(&I))
           if (II->getIntrinsicID() == Intrinsic::assume)
             AC->registerAssumption(II);
       }
     }
+
+    {
+      // Phase2: identify what other metadata depends on the cloned version
+      // Phase3: after cloning, replace the metadata with the corrected version
+      // for both memory instructions and noalias intrinsics
+      std::string ext = "It";
+      ext += utostr(It);
+      cloneAndAdaptNoAliasScopes(LoopLocalNoAliasDeclScopes, NewBlocks,
+                                 Header->getContext(), ext);
+    }
   }
 
   // Loop over the PHI nodes in the original block, setting incoming values.
   for (PHINode *PN : OrigPHINode) {
     if (CompletelyUnroll) {
       PN->replaceAllUsesWith(PN->getIncomingValueForBlock(Preheader));
       Header->getInstList().erase(PN);
     } else if (ULO.Count > 1) {

llvm/lib/Transforms/Utils/NoAliasUtils.cpp

#if !defined(NDEBUG)
                       "PHI/select - YET: "
                    << *UO[0] << "\n");
       }
 #endif
     }
   }
   return Changed;
 }
+
+void llvm::cloneNoAliasScopes(
+    ArrayRef<MetadataAsValue *> NoAliasDeclScopes,
+    DenseMap<MDNode *, MDNode *> &out_ClonedScopes,
+    DenseMap<MetadataAsValue *, MetadataAsValue *> &out_ClonedMVScopes,
+    StringRef Ext, LLVMContext &Context) {
+  MDBuilder MDB(Context);
+
+  for (auto *MV : NoAliasDeclScopes) {
+    SmallVector<Metadata *, 4> ScopeList;
+    for (auto &MDOperand : cast<MDNode>(MV->getMetadata())->operands()) {
+      if (MDNode *MD = dyn_cast<MDNode>(MDOperand)) {
+        llvm::AliasScopeNode SNAN(MD);
+
+        std::string Name;
+        auto ScopeName = SNAN.getName();
+        if (!ScopeName.empty()) {
+          Name = ScopeName;
+          Name += ":";
+          Name += Ext;
+        } else {
+          Name = Ext;
+        }
+
+        MDNode *NewScope = MDB.createAnonymousAliasScope(
+            const_cast<MDNode *>(SNAN.getDomain()), Name);
+        out_ClonedScopes.insert(std::make_pair(MD, NewScope));
+        ScopeList.push_back(NewScope);
+      }
+    }
+    MDNode *NewScopeList = MDNode::get(Context, ScopeList);
+    out_ClonedMVScopes.insert(
+        std::make_pair(MV, MetadataAsValue::get(Context, NewScopeList)));
+  }
+}
+
+void llvm::adaptNoAliasScopes(
+    Instruction *I, DenseMap<MDNode *, MDNode *> &ClonedScopes,
+    DenseMap<MetadataAsValue *, MetadataAsValue *> &ClonedMVScopes,
+    LLVMContext &Context) {
+  // MetadataAsValue will always be replaced !
+  for (int opI = 0, opIEnd = I->getNumOperands(); opI < opIEnd; ++opI) {
+    if (MetadataAsValue *MV = dyn_cast<MetadataAsValue>(I->getOperand(opI))) {
+      auto MvIt = ClonedMVScopes.find(MV);
+      if (MvIt != ClonedMVScopes.end()) {
+        I->setOperand(opI, MvIt->second);
+      }
+    }
+  }
+  if (const MDNode *CSNoAlias = I->getMetadata(LLVMContext::MD_noalias)) {
+    bool needsReplacement = false;
+    SmallVector<Metadata *, 8> NewScopeList;
+    for (auto &MDOp : CSNoAlias->operands()) {
+      if (MDNode *MD = dyn_cast_or_null<MDNode>(MDOp)) {
+        auto MdIt = ClonedScopes.find(MD);
+        if (MdIt != ClonedScopes.end()) {
+          NewScopeList.push_back(MdIt->second);
+          needsReplacement = true;
+          continue;
+        }
+        NewScopeList.push_back(MD);
+      }
+    }
+    if (needsReplacement) {
+      I->setMetadata(LLVMContext::MD_noalias,
+                     MDNode::get(Context, NewScopeList));
+    }
+  }
+}
+
+void llvm::cloneAndAdaptNoAliasScopes(
+    ArrayRef<MetadataAsValue *> NoAliasDeclScopes,
+    ArrayRef<BasicBlock *> NewBlocks, LLVMContext &Context, StringRef Ext) {
+  if (NoAliasDeclScopes.empty())
+    return;
+
+  DenseMap<MDNode *, MDNode *> ClonedScopes;
+  DenseMap<MetadataAsValue *, MetadataAsValue *> ClonedMVScopes;
+  LLVM_DEBUG(llvm::dbgs() << "cloneAndAdaptNoAliasScopes: cloning "
+                          << NoAliasDeclScopes.size() << " node(s)\n");
+
+  cloneNoAliasScopes(NoAliasDeclScopes, ClonedScopes, ClonedMVScopes, Ext,
+                     Context);
+  // Identify instructions using metadata that needs adaptation
+  for (BasicBlock *NewBlock : NewBlocks) {
+    for (Instruction &I : *NewBlock) {
+      adaptNoAliasScopes(&I, ClonedScopes, ClonedMVScopes, Context);
+    }
+  }
+}

llvm/test/Transforms/LoopUnroll/noalias.ll

+; RUN: opt < %s -S -unroll-runtime -unroll-count=2 -loop-unroll | FileCheck %s
+
+target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+; Function Attrs: nounwind
+define dso_local void @test_loop_unroll_01(i32* nocapture %_pA) local_unnamed_addr #0 {
+entry:
+  %0 = tail call i8* @llvm.noalias.decl.p0i8.p0p0i32.i32(i32** null, i32 0, metadata !2)
+  %1 = tail call i32* @llvm.side.noalias.p0i32.p0i8.p0p0i32.p0p0i32.i32(i32* %_pA, i8* %0, i32** null, i32** undef, i32 0, metadata !2), !tbaa !5, !noalias !2
+  br label %for.body
+
+for.cond.cleanup:                                 ; preds = %for.body
+  ret void
+
+for.body:                                         ; preds = %for.body, %entry
+  %i.06 = phi i32 [ 0, %entry ], [ %inc, %for.body ]
+  %arrayidx = getelementptr inbounds i32, i32* %_pA, i32 %i.06
+  store i32 %i.06, i32* %arrayidx, noalias_sidechannel i32* %1, align 4, !tbaa !9, !noalias !2
+  %inc = add nuw nsw i32 %i.06, 1
+  %exitcond = icmp eq i32 %inc, 4
+  br i1 %exitcond, label %for.cond.cleanup, label %for.body
+}
+
+; CHECK: define dso_local void @test_loop_unroll_01(i32* nocapture %_pA) local_unnamed_addr #0 {
+; CHECK: entry:
+; CHECK:   %0 = tail call i8* @llvm.noalias.decl.p0i8.p0p0i32.i32(i32** null, i32 0, metadata !2)
+; CHECK:   %1 = tail call i32* @llvm.side.noalias.p0i32.p0i8.p0p0i32.p0p0i32.i32(i32* %_pA, i8* %0, i32** null, i32** undef, i32 0, metadata !2), !tbaa !5, !noalias !2
+; CHECK:   br label %for.body
+; CHECK: for.cond.cleanup:                                 ; preds = %for.body
+; CHECK:   ret void
+; CHECK: for.body:                                         ; preds = %for.body, %entry
+; CHECK:   %i.06 = phi i32 [ 0, %entry ], [ %inc.1, %for.body ]
+; CHECK:   %arrayidx = getelementptr inbounds i32, i32* %_pA, i32 %i.06
+; CHECK:   store i32 %i.06, i32* %arrayidx, noalias_sidechannel i32* %1, align 4, !tbaa !9, !noalias !2
+; CHECK:   %inc = add nuw nsw i32 %i.06, 1
+; CHECK:   %arrayidx.1 = getelementptr inbounds i32, i32* %_pA, i32 %inc
+; CHECK:   store i32 %inc, i32* %arrayidx.1, noalias_sidechannel i32* %1, align 4, !tbaa !9, !noalias !2
+; CHECK:   %inc.1 = add nuw nsw i32 %inc, 1
+; CHECK:   %exitcond.1 = icmp eq i32 %inc.1, 4
+; CHECK:   br i1 %exitcond.1, label %for.cond.cleanup, label %for.body, !llvm.loop !11
+; CHECK: }
+
+
+; Function Attrs: argmemonly nounwind
+declare i8* @llvm.noalias.decl.p0i8.p0p0i32.i32(i32**, i32, metadata) #1
+
+; Function Attrs: nounwind
+define dso_local void @test_loop_unroll_02(i32* nocapture %_pA) local_unnamed_addr #0 {
+entry:
+  br label %for.body
+
+for.cond.cleanup:                                 ; preds = %for.body
+  ret void
+
+for.body:                                         ; preds = %for.body, %entry
+  %i.06 = phi i32 [ 0, %entry ], [ %inc, %for.body ]
+  %0 = tail call i8* @llvm.noalias.decl.p0i8.p0p0i32.i32(i32** null, i32 0, metadata !11)
+  %1 = tail call i32* @llvm.side.noalias.p0i32.p0i8.p0p0i32.p0p0i32.i32(i32* %_pA, i8* %0, i32** null, i32** undef, i32 0, metadata !11), !tbaa !5, !noalias !11
+  %arrayidx = getelementptr inbounds i32, i32* %_pA, i32 %i.06
+  store i32 %i.06, i32* %arrayidx, noalias_sidechannel i32* %1, align 4, !tbaa !9, !noalias !11
+  %inc = add nuw nsw i32 %i.06, 1
+  %exitcond = icmp eq i32 %inc, 4
+  br i1 %exitcond, label %for.cond.cleanup, label %for.body
+}
+
+; CHECK: define dso_local void @test_loop_unroll_02(i32* nocapture %_pA) local_unnamed_addr #0 {
+; CHECK: entry:
+; CHECK:   br label %for.body
+; CHECK: for.cond.cleanup:                                 ; preds = %for.body
+; CHECK:   ret void
+; CHECK: for.body:                                         ; preds = %for.body, %entry
+; CHECK:   %i.06 = phi i32 [ 0, %entry ], [ %inc.1, %for.body ]
+; CHECK:   %0 = tail call i8* @llvm.noalias.decl.p0i8.p0p0i32.i32(i32** null, i32 0, metadata !13)
+; CHECK:   %1 = tail call i32* @llvm.side.noalias.p0i32.p0i8.p0p0i32.p0p0i32.i32(i32* %_pA, i8* %0, i32** null, i32** undef, i32 0, metadata !13), !tbaa !5, !noalias !13
+; CHECK:   %arrayidx = getelementptr inbounds i32, i32* %_pA, i32 %i.06
+; CHECK:   store i32 %i.06, i32* %arrayidx, noalias_sidechannel i32* %1, align 4, !tbaa !9, !noalias !13
+; CHECK:   %inc = add nuw nsw i32 %i.06, 1
+; CHECK:   %2 = tail call i8* @llvm.noalias.decl.p0i8.p0p0i32.i32(i32** null, i32 0, metadata !16)
+; CHECK:   %3 = tail call i32* @llvm.side.noalias.p0i32.p0i8.p0p0i32.p0p0i32.i32(i32* %_pA, i8* %2, i32** null, i32** undef, i32 0, metadata !16), !tbaa !5, !noalias !16
+; CHECK:   %arrayidx.1 = getelementptr inbounds i32, i32* %_pA, i32 %inc
+; CHECK:   store i32 %inc, i32* %arrayidx.1, noalias_sidechannel i32* %3, align 4, !tbaa !9, !noalias !16
+; CHECK:   %inc.1 = add nuw nsw i32 %inc, 1
+; CHECK:   %exitcond.1 = icmp eq i32 %inc.1, 4
+; CHECK:   br i1 %exitcond.1, label %for.cond.cleanup, label %for.body, !llvm.loop !18
+; CHECK: }
+
+
+; Function Attrs: nounwind readnone speculatable
+declare i32* @llvm.side.noalias.p0i32.p0i8.p0p0i32.p0p0i32.i32(i32*, i8*, i32**, i32**, i32, metadata) #2
+
+attributes #0 = { nounwind "correctly-rounded-divide-sqrt-fp-math"="false" "disable-tail-calls"="false" "frame-pointer"="all" "less-precise-fpmad"="false" "min-legal-vector-width"="0" "no-infs-fp-math"="false" "no-jump-tables"="false" "no-nans-fp-math"="false" "no-signed-zeros-fp-math"="false" "no-trapping-math"="false" "stack-protector-buffer-size"="8" "unsafe-fp-math"="false" "use-soft-float"="false" }
+attributes #1 = { argmemonly nounwind }
+attributes #2 = { nounwind readnone speculatable }
+
+!llvm.module.flags = !{!0}
+!llvm.ident = !{!1}
+
+!0 = !{i32 1, !"wchar_size", i32 4}
+!1 = !{!"clang"}
+!2 = !{!3}
+!3 = distinct !{!3, !4, !"test_loop_unroll_01: pA"}
+!4 = distinct !{!4, !"test_loop_unroll_01"}
+!5 = !{!6, !6, i64 0, i64 4}
+!6 = !{!7, i64 4, !"any pointer"}
+!7 = !{!8, i64 1, !"omnipotent char"}
+!8 = !{!"Simple C/C++ TBAA"}
+!9 = !{!10, !10, i64 0, i64 4}
+!10 = !{!7, i64 4, !"int"}
+!11 = !{!12}
+!12 = distinct !{!12, !13, !"test_loop_unroll_02: pA"}
+!13 = distinct !{!13, !"test_loop_unroll_02"}
+
+; CHECK: !0 = !{i32 1, !"wchar_size", i32 4}
+; CHECK: !1 = !{!"clang"}
+; CHECK: !2 = !{!3}
+; CHECK: !3 = distinct !{!3, !4, !"test_loop_unroll_01: pA"}
+; CHECK: !4 = distinct !{!4, !"test_loop_unroll_01"}
+; CHECK: !5 = !{!6, !6, i64 0, i64 4}
+; CHECK: !6 = !{!7, i64 4, !"any pointer"}
+; CHECK: !7 = !{!8, i64 1, !"omnipotent char"}
+; CHECK: !8 = !{!"Simple C/C++ TBAA"}
+; CHECK: !9 = !{!10, !10, i64 0, i64 4}
+; CHECK: !10 = !{!7, i64 4, !"int"}
+; CHECK: !11 = distinct !{!11, !12}
+; CHECK: !12 = !{!"llvm.loop.unroll.disable"}
+; CHECK: !13 = !{!14}
+; CHECK: !14 = distinct !{!14, !15, !"test_loop_unroll_02: pA"}
+; CHECK: !15 = distinct !{!15, !"test_loop_unroll_02"}
+; CHECK: !16 = !{!17}
+; CHECK: !17 = distinct !{!17, !15, !"test_loop_unroll_02: pA:It1"}
+; CHECK: !18 = distinct !{!18, !12}