[LoopVectorize] Use MapVector rather than DenseMap for MinBWs.

[• chatur01]

Summary

The order in which instructions are truncated in truncateToMinimalBitwidths
effects code generation. Switch to a map with a determinisic order, since the
iteration order over a DenseMap is not defined.

This code is not hot, so the difference in container performance isn't
interesting.

Many thanks to David Blaikie for making me aware of MapVector!

Fixes PR25490.

[sbaranga]

Hi Charlie,

The iteration order over std::map is defined by the order of the keys (Instruction *). Wouldn't this also be non-deterministic?

Thanks,
Silviu

[• chatur01]

Yep, thanks Silviu. I messed this up. I fixed the small testcase in the PR (by luck) and not the larger ones I have access to. Apologies.

[dblaikie]

We have mapvector, if the insertion order is stable

[• chatur01]

Nice one David! This saved me from publishing a nasty hack to maintain my own vector in LoopVectorize.

The insertion order looks stable to me. It comes from computeMinimumValueSizes in VectorUtils. They get inserted into the MapVector from the equivalence class iterators (driven underneath by an ordered set), which in turn are created from a vector of Value* in basic block order.

My larger test case no longer has non-determinisic order, as well as the test-case in the PR.

[dblaikie]

Looks good. I assume you're going to (re)commit the now-stable test along with this?

(generally I think it better to revert the actual instability (it is a bug - we really don't want unstable output of the compiler) along with the test if it's got problems - then recommit with the fix together)

A couple of places look like they're doing excess copying of this data structure - perhaps you could fix those (if I've correctly diagnosed them) in a separate commit?

lib/Transforms/Vectorize/LoopVectorize.cpp

329 ↗

(On Diff #41158)

Tangentially related: Isn't there a std::move missing here? (the argument is passed by value, allowing movement from the caller, then copied into the member when it could be moved instead)

1893 ↗

(On Diff #41158)

looks like MinBWs isn't used after this point (similarly in the else clause) & could be std::moved in both places?

[• chatur01]

Added a test-case. This might violate the test guidelines of only comitting robust test cases. By definition I can't do that for a non-determinism bug, but I'm running the test case 5 times, which at least locally was always enough to catch the non-determinism on my computer, of course I can't guarantee that.

I'm requesting a sanity check on my test case before comitting it.

Many thanks again David for your review.

[mcrosier]

FWIW, the test case provided in the PR was reduced from an external benchmark. I don't believe a simpler test can be created.

llvm/trunk/include/llvm/Analysis/VectorUtils.h

 // This file defines some vectorizer utilities.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_TRANSFORMS_UTILS_VECTORUTILS_H
 #define LLVM_TRANSFORMS_UTILS_VECTORUTILS_H
 
 #include "llvm/ADT/ArrayRef.h"
+#include "llvm/ADT/MapVector.h"
 #include "llvm/Analysis/TargetLibraryInfo.h"
 #include "llvm/IR/IntrinsicInst.h"
 #include "llvm/IR/Intrinsics.h"
 
 namespace llvm {
 
 struct DemandedBits;
 class GetElementPtrInst;

 ///   %6 = add i32 %4, %5
 ///   %7 = trunc i32 %6 to i16
 ///
 /// Instruction %6 must be done at least in i16, so computeMinimumValueSizes
 /// will return: {%1: 16, %2: 16, %3: 16, %4: 16, %5: 16, %6: 16, %7: 16}.
 ///
 /// If the optional TargetTransformInfo is provided, this function tries harder
 /// to do less work by only looking at illegal types.
-DenseMap<Instruction*, uint64_t>
+MapVector<Instruction*, uint64_t>
 computeMinimumValueSizes(ArrayRef<BasicBlock*> Blocks,
                          DemandedBits &DB,
                          const TargetTransformInfo *TTI=nullptr);
     
 } // llvm namespace
 
 #endif

llvm/trunk/lib/Analysis/VectorUtils.cpp

auto *InsertEltInst =
     dyn_cast<InsertElementInst>(ShuffleInst->getOperand(0));
   if (!InsertEltInst || !isa<ConstantInt>(InsertEltInst->getOperand(2)) ||
       !cast<ConstantInt>(InsertEltInst->getOperand(2))->isNullValue())
     return nullptr;
 
   return InsertEltInst->getOperand(1);
 }
 
-DenseMap<Instruction *, uint64_t>
+MapVector<Instruction *, uint64_t>
 llvm::computeMinimumValueSizes(ArrayRef<BasicBlock *> Blocks, DemandedBits &DB,
                                const TargetTransformInfo *TTI) {
 
   // DemandedBits will give us every value's live-out bits. But we want
   // to ensure no extra casts would need to be inserted, so every DAG
   // of connected values must have the same minimum bitwidth.
   EquivalenceClasses<Value *> ECs;
   SmallVector<Value *, 16> Worklist;
   SmallPtrSet<Value *, 4> Roots;
   SmallPtrSet<Value *, 16> Visited;
   DenseMap<Value *, uint64_t> DBits;
   SmallPtrSet<Instruction *, 4> InstructionSet;
-  DenseMap<Instruction *, uint64_t> MinBWs;
+  MapVector<Instruction *, uint64_t> MinBWs;
 
   // Determine the roots. We work bottom-up, from truncs or icmps.
   bool SeenExtFromIllegalType = false;
   for (auto *BB : Blocks)
     for (auto &I : *BB) {
       InstructionSet.insert(&I);
 
       if (TTI && (isa<ZExtInst>(&I) || isa<SExtInst>(&I)) &&
while (!Worklist.empty()) {
     // Non-instructions terminate a chain successfully.
     if (!isa<Instruction>(Val))
       continue;
     Instruction *I = cast<Instruction>(Val);
 
     // If we encounter a type that is larger than 64 bits, we can't represent
     // it so bail out.
     if (DB.getDemandedBits(I).getBitWidth() > 64)
-      return DenseMap<Instruction *, uint64_t>();
+      return MapVector<Instruction *, uint64_t>();
 
     uint64_t V = DB.getDemandedBits(I).getZExtValue();
     DBits[Leader] |= V;
 
     // Casts, loads and instructions outside of our range terminate a chain
     // successfully.
     if (isa<SExtInst>(I) || isa<ZExtInst>(I) || isa<LoadInst>(I) ||
         !InstructionSet.count(I))

llvm/trunk/lib/Transforms/Vectorize/LoopVectorize.cpp

InnerLoopVectorizer(Loop *OrigLoop, ScalarEvolution *SE, LoopInfo *LI,
         TripCount(nullptr), VectorTripCount(nullptr), Legal(nullptr),
         AddedSafetyChecks(false), Preds(Preds) {}
 
   // Perform the actual loop widening (vectorization).
   // MinimumBitWidths maps scalar integer values to the smallest bitwidth they
   // can be validly truncated to. The cost model has assumed this truncation
   // will happen when vectorizing.
   void vectorize(LoopVectorizationLegality *L,
-                 DenseMap<Instruction*,uint64_t> MinimumBitWidths) {
+                 MapVector<Instruction*,uint64_t> MinimumBitWidths) {
     MinBWs = MinimumBitWidths;
     Legal = L;
     // Create a new empty loop. Unlink the old loop and connect the new one.
     createEmptyLoop();
     // Widen each instruction in the old loop to a new one in the new loop.
     // Use the Legality module to find the induction and reduction variables.
     vectorizeLoop();
   }
protected:
   /// Trip count of the original loop.
   Value *TripCount;
   /// Trip count of the widened loop (TripCount - TripCount % (VF*UF))
   Value *VectorTripCount;
 
   /// Map of scalar integer values to the smallest bitwidth they can be legally
   /// represented as. The vector equivalents of these values should be truncated
   /// to this type.
-  DenseMap<Instruction*,uint64_t> MinBWs;
+  MapVector<Instruction*,uint64_t> MinBWs;
   LoopVectorizationLegality *Legal;
 
   // Record whether runtime check is added.
   bool AddedSafetyChecks;
 
   /// The SCEV predicate containing all the SCEV-related assumptions.
   /// The predicate is used to simplify existing expressions in the
   /// context of existing SCEV assumptions. Since legality checking is
private:
   void emitAnalysis(const LoopAccessReport &Message) const {
     emitAnalysisDiag(TheFunction, TheLoop, *Hints, Message);
   }
 
 public:
   /// Map of scalar integer values to the smallest bitwidth they can be legally
   /// represented as. The vector equivalents of these values should be truncated
   /// to this type.
-  DenseMap<Instruction*,uint64_t> MinBWs;
+  MapVector<Instruction*,uint64_t> MinBWs;
 
   /// The loop that we evaluate.
   Loop *TheLoop;
   /// Scev analysis.
   ScalarEvolution *SE;
   /// Loop Info analysis.
   LoopInfo *LI;
   /// Vectorization legality.

llvm/trunk/test/Transforms/LoopVectorize/AArch64/deterministic-type-shrinkage.ll

+; RUN: opt -S < %s -loop-vectorize -instcombine 2>&1 | FileCheck %s
+
+target datalayout = "e-m:e-i64:64-i128:128-n32:64-S128"
+target triple = "aarch64"
+
+;; See https://llvm.org/bugs/show_bug.cgi?id=25490
+;; Due to the data structures used, the LLVM IR was not determinisic.
+;; This test comes from the PR.
+
+;; CHECK-LABEL: @test(
+; CHECK: load <16 x i8>
+; CHECK-NEXT: getelementptr
+; CHECK-NEXT: bitcast
+; CHECK-NEXT: load <16 x i8>
+; CHECK-NEXT: zext <16 x i8>
+; CHECK-NEXT: zext <16 x i8>
+define void @test(i32 %n, i8* nocapture %a, i8* nocapture %b, i8* nocapture readonly %c) {
+entry:
+  %cmp.28 = icmp eq i32 %n, 0
+  br i1 %cmp.28, label %for.cond.cleanup, label %for.body.preheader
+
+for.body.preheader:                               ; preds = %entry
+  br label %for.body
+
+for.cond.cleanup.loopexit:                        ; preds = %for.body
+  br label %for.cond.cleanup
+
+for.cond.cleanup:                                 ; preds = %for.cond.cleanup.loopexit, %entry
+  ret void
+
+for.body:                                         ; preds = %for.body.preheader, %for.body
+  %indvars.iv = phi i64 [ %indvars.iv.next, %for.body ], [ 0, %for.body.preheader ]
+  %arrayidx = getelementptr inbounds i8, i8* %c, i64 %indvars.iv
+  %0 = load i8, i8* %arrayidx, align 1
+  %conv = zext i8 %0 to i32
+  %arrayidx2 = getelementptr inbounds i8, i8* %a, i64 %indvars.iv
+  %1 = load i8, i8* %arrayidx2, align 1
+  %conv3 = zext i8 %1 to i32
+  %mul = mul nuw nsw i32 %conv3, %conv
+  %shr.26 = lshr i32 %mul, 8
+  %conv4 = trunc i32 %shr.26 to i8
+  store i8 %conv4, i8* %arrayidx2, align 1
+  %arrayidx8 = getelementptr inbounds i8, i8* %b, i64 %indvars.iv
+  %2 = load i8, i8* %arrayidx8, align 1
+  %conv9 = zext i8 %2 to i32
+  %mul10 = mul nuw nsw i32 %conv9, %conv
+  %shr11.27 = lshr i32 %mul10, 8
+  %conv12 = trunc i32 %shr11.27 to i8
+  store i8 %conv12, i8* %arrayidx8, align 1
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  %lftr.wideiv = trunc i64 %indvars.iv.next to i32
+  %exitcond = icmp eq i32 %lftr.wideiv, %n
+  br i1 %exitcond, label %for.cond.cleanup.loopexit, label %for.body
+}