Encode duplication factor from loop vectorization and loop unrolling to discriminator.

[danielcdh]

Summary

This patch starts the implementation as discuss in the following RFC: http://lists.llvm.org/pipermail/llvm-dev/2016-October/106532.html

When optimization duplicates code that will scale down the execution count of a basic block, we will record the duplication factor as part of discriminator so that the offline process tool can find the duplication factor and collect the accurate execution frequency of the corresponding source code. Two important optimization that fall into this category is loop vectorization and loop unroll. This patch records the duplication factor for these 2 optimizations.

The recording will be guarded by a flag encode-duplication-in-discriminators, which is off by default.

[danielcdh]

ping

[aprantl]

include/llvm/IR/DebugInfoMetadata.h

1653–1654

1. This magic formula needs to be documented somewhere.
2. Is there anything preventing / detecting potential collisions here?

[hfinkel]

lib/Transforms/Vectorize/LoopVectorize.cpp

836

I apologize for rehashing this, but now I'm confused again. We have two situations:

1. Loop is unrolled (or code is otherwise duplicated). In this case, the discriminator value must be different (so that the relevant counts are summed)
2. Instruction is vectorized. In this case we need a discriminator value with a duplication factor (so that the counts are multiplied by the duplication factor because each vector instruction represents DF scalar instructions).

And both situations can obviously be combined. It seems like, in general, we're trying to take a shortcut here: instead of giving each instruction from an unrolled loop a different discriminator (so that all of the relevant counts will be summed), we're giving them all the same discriminator with a duplication factor. This will work in some cases, but not if some of the loop iterations (or instructions therein) are executed conditionally. I don't see why this is worthwhile. Can you please explain?

[danielcdh]

lib/Transforms/Vectorize/LoopVectorize.cpp

836

You are right. For unrolled loop, the most accurate way would be assign a distinct discriminator for each cloned body, and use "sum" to compute the source count. We are taking a short-cut here to assign all copies with one discriminator (with duplication factor), and use max*dup_factor to compute the source count. This works fine when all cloned copy has uniformed behavior and thus similar execution count, otherwise will overcount the source.

So the cons of using duplication factor for unrolled loop is less accuracy. The pros is that it saves on line table size.

Maybe a better solution would be: if there is control flow inside the unrolled loop, then use distinct discriminator for each clone, otherwise use duplication factor.

In this patch, I only added the logic for the duplication factor. I will have another patch to add the logic to "add distinct discriminator for clones" in another patch. How about I add a FIXME here and address loop-unroll-with-control-flow in that patch?

[danielcdh]

ping...

[hfinkel]

lib/Transforms/Vectorize/LoopVectorize.cpp

836

So the cons of using duplication factor for unrolled loop is less accuracy. The pros is that it saves on line table size.

Can you explain again why this saves on line-table size?

In this patch, I only added the logic for the duplication factor. I will have another patch to add the logic to "add distinct discriminator for clones" in another patch. How about I add a FIXME here and address loop-unroll-with-control-flow in that patch?

That's fine by me.

[danielcdh]

Thanks for the review.

Any update comments about the proposed encoding before it's ready to land?

Thanks,
Dehao

lib/Transforms/Vectorize/LoopVectorize.cpp

836

For the following case:

#1 for (i = 0; i < 4; i++)
#2 a[i] = b[i];

If we use duplication factor, the line table for the expanded code will be:

a[0] = b[0]; line 2, discriminator 0x400
a[1] = b[1]; line 2, discriminator 0x400
a[2] = b[2]; line 2, discriminator 0x400
a[3] = b[3]; line 2, discriminator 0x400

The all share the same location so there is no new line table entry for the clone code.

But with ditinct discriminator, the expanded code will be:

a[0] = b[0]; line 2, discriminator 0x10000
a[1] = b[1]; line 2, discriminator 0x20000
a[2] = b[2]; line 2, discriminator 0x30000
a[3] = b[3]; line 2, discriminator 0x40000

There are 2 issues:

1. each line has distinct location, so we need 4 entries in the debug line table.
2. the encoding for distinct discriminator is longer than duplication factor.

[hfinkel]

In D26420#601874, @danielcdh wrote:

Thanks for the review.

Any update comments about the proposed encoding before it's ready to land?

Could we be smarter about the encoding so that the distinct-copies case did not take up so much space? It seems like the design right now gives a fixed number of low bits to the duplication factor. Could we use a variable number of bits? For example, because of the underlying LEB128 encoding, we could use some of the lowest-order bits as indicators, or better, use a variable-length code:

low: < duplication factor > < copy id > : high

where each factor is a variable-length code (e.g. a prefix code: https://en.wikipedia.org/wiki/Prefix_code). For example, the Fibonacci code (https://en.wikipedia.org/wiki/Fibonacci_coding) is a well-known code which is good when the encoded numbers are likely to be small. In short, we might encode:

bitreverse( Fibonacci(copy-id + 1) | Fibonacci(dup-factor + 1) )

In this case, if either field is empty, then we waste only 2 bits encoding that field. Small numbers take only a small number of bits. What do you think?

Thanks,
Dehao

[danielcdh]

In D26420#601965, @hfinkel wrote:

In D26420#601874, @danielcdh wrote:

Thanks for the review.

Any update comments about the proposed encoding before it's ready to land?

Could we be smarter about the encoding so that the distinct-copies case did not take up so much space? It seems like the design right now gives a fixed number of low bits to the duplication factor. Could we use a variable number of bits? For example, because of the underlying LEB128 encoding, we could use some of the lowest-order bits as indicators, or better, use a variable-length code:

low: < duplication factor > < copy id > : high

where each factor is a variable-length code (e.g. a prefix code: https://en.wikipedia.org/wiki/Prefix_code). For example, the Fibonacci code (https://en.wikipedia.org/wiki/Fibonacci_coding) is a well-known code which is good when the encoded numbers are likely to be small. In short, we might encode:

bitreverse( Fibonacci(copy-id + 1) | Fibonacci(dup-factor + 1) )

In this case, if either field is empty, then we waste only 2 bits encoding that field. Small numbers take only a small number of bits. What do you think?

Thanks for the suggestion. I spent some time study the prefix based encoding, which is a great idea. But when it applies here, with fibonacci encoding, 3 bits can only represent numbers up to 3, 4 bits can represent up to 5 and 7 bits can represent up to 21. This does not seem enough as duplication factor usually will need 5+ bits, making it hard to fit multiple-pieces into 1-byte ULEB.

Another approach, as you mentioned, is to use the lower bits to encode which info it represents, so that when there is only 1 info available, we can more efficiently encode it into one byte. This is a great idea. I did some experiments to explore its potential: when assigning duplication factor, I always remove the original discriminator and put the DP in the lower 7 bits to make it always fit into 1 byte. The debug_line size increase comparing with the current patch is show below:

447.dealII 8.01% 6.16%
453.povray 6.50% 5.04%
482.sphinx3 7.54% 5.74%
470.lbm 0.00% 0.00%
444.namd 6.19% 4.89%
433.milc 23.12% 17.63%
450.soplex 2.66% 1.99%
445.gobmk 7.51% 5.02%
471.omnetpp 0.52% 0.36%
458.sjeng 10.31% 7.37%
473.astar 5.44% 4.26%
456.hmmer 9.74% 7.50%
401.bzip2 9.01% 6.33%
462.libquantum 10.79% 8.36%
403.gcc 2.74% 1.77%
464.h264ref 29.62% 21.14%
483.xalancbmk 1.42% 1.12%
429.mcf 9.55% 7.45%
400.perlbench 1.96% 1.21%
mean 7.81% 5.84%

The first column of data represents the current implementation. The 2nd column is the experiment (fitting all DP into one byte), which represent the upper-bound of any encoding.

From the data, looks like the improvement is marginal. So I'm wondering does it justify the added complexity comparing with fixed-width encoding?

Thanks,
Dehao

[hfinkel]

In D26420#603775, @danielcdh wrote:

In D26420#601965, @hfinkel wrote:

In D26420#601874, @danielcdh wrote:

Thanks for the review.

Any update comments about the proposed encoding before it's ready to land?

Could we be smarter about the encoding so that the distinct-copies case did not take up so much space? It seems like the design right now gives a fixed number of low bits to the duplication factor. Could we use a variable number of bits? For example, because of the underlying LEB128 encoding, we could use some of the lowest-order bits as indicators, or better, use a variable-length code:

low: < duplication factor > < copy id > : high

where each factor is a variable-length code (e.g. a prefix code: https://en.wikipedia.org/wiki/Prefix_code). For example, the Fibonacci code (https://en.wikipedia.org/wiki/Fibonacci_coding) is a well-known code which is good when the encoded numbers are likely to be small. In short, we might encode:

bitreverse( Fibonacci(copy-id + 1) | Fibonacci(dup-factor + 1) )

In this case, if either field is empty, then we waste only 2 bits encoding that field. Small numbers take only a small number of bits. What do you think?

Thanks for the suggestion. I spent some time study the prefix based encoding, which is a great idea. But when it applies here, with fibonacci encoding, 3 bits can only represent numbers up to 3, 4 bits can represent up to 5 and 7 bits can represent up to 21. This does not seem enough as duplication factor usually will need 5+ bits, making it hard to fit multiple-pieces into 1-byte ULEB.

Another approach, as you mentioned, is to use the lower bits to encode which info it represents, so that when there is only 1 info available, we can more efficiently encode it into one byte. This is a great idea. I did some experiments to explore its potential: when assigning duplication factor, I always remove the original discriminator and put the DP in the lower 7 bits to make it always fit into 1 byte. The debug_line size increase comparing with the current patch is show below:

447.dealII 8.01% 6.16%
453.povray 6.50% 5.04%
482.sphinx3 7.54% 5.74%
470.lbm 0.00% 0.00%
444.namd 6.19% 4.89%
433.milc 23.12% 17.63%
450.soplex 2.66% 1.99%
445.gobmk 7.51% 5.02%
471.omnetpp 0.52% 0.36%
458.sjeng 10.31% 7.37%
473.astar 5.44% 4.26%
456.hmmer 9.74% 7.50%
401.bzip2 9.01% 6.33%
462.libquantum 10.79% 8.36%
403.gcc 2.74% 1.77%
464.h264ref 29.62% 21.14%
483.xalancbmk 1.42% 1.12%
429.mcf 9.55% 7.45%
400.perlbench 1.96% 1.21%
mean 7.81% 5.84%

The first column of data represents the current implementation. The 2nd column is the experiment (fitting all DP into one byte), which represent the upper-bound of any encoding.

From the data, looks like the improvement is marginal. So I'm wondering does it justify the added complexity comparing with fixed-width encoding?

Thanks for doing those experiments! Regarding the second form, many of those changes are on the order of a few percent -- that seems worthwhile. Can you post the patch?

Thanks,
Dehao

[danielcdh]

Updated the encoding algorithm to use the lowest bit to represent whether BaseDiscriminator/DuplicationFactor is available.

With this change, the debug info size impact is demonstrated in the last column of below:

447.dealII 8.01% 6.16% 6.92%
453.povray 6.50% 5.04% 5.38%
482.sphinx3 7.54% 5.74% 6.22%
470.lbm 0.00% 0.00% 0.00%
444.namd 6.19% 4.89% 5.14%
433.milc 23.12% 17.63% 19.96%
450.soplex 2.66% 1.99% 2.25%
445.gobmk 7.51% 5.02% 6.22%
471.omnetpp 0.52% 0.36% 0.45%
458.sjeng 10.31% 7.37% 8.38%
473.astar 5.44% 4.26% 4.46%
456.hmmer 9.74% 7.50% 8.36%
401.bzip2 9.01% 6.33% 7.72%
462.libquantum 10.79% 8.36% 8.75%
403.gcc 2.74% 1.77% 2.28%
464.h264ref 29.62% 21.14% 27.37%
483.xalancbmk 1.42% 1.12% 1.16%
429.mcf 9.55% 7.45% 7.69%
400.perlbench 1.96% 1.21% 1.73%
mean 7.81% 5.84% 6.68%

[hfinkel]

In D26420#611383, @danielcdh wrote:

Updated the encoding algorithm to use the lowest bit to represent whether BaseDiscriminator/DuplicationFactor is available.

With this change, the debug info size impact is demonstrated in the last column of below:

What are the other columns?

[danielcdh]

In D26420#611614, @hfinkel wrote:

In D26420#611383, @danielcdh wrote:

Updated the encoding algorithm to use the lowest bit to represent whether BaseDiscriminator/DuplicationFactor is available.

With this change, the debug info size impact is demonstrated in the last column of below:

What are the other columns?

They are copied from the previous experiment:

The first column of data represents the current implementation. The 2nd column is the experiment (fitting all DP into one byte), which represent the upper-bound of any encoding.

[hfinkel]

include/llvm/IR/DebugInfoMetadata.h

1684

Please move the comments that explain the encoding to above DILocation::getBaseDiscriminator and write some text to explain what is going on.

lib/Transforms/Utils/AddDiscriminators.cpp

197

Please add a utility function for the encoding.

lib/Transforms/Vectorize/LoopVectorize.cpp

216

Based on one of the other threads, I suppose we're going to add some command-line flag to enable/disable this? That being the case, we'll read this setting from some function attribute string instead of using a cl::opt.

[danielcdh]

lib/Transforms/Utils/AddDiscriminators.cpp

197

Thanks for the comment!

I agree with all the comments, but before I address the comments and move forward with this encoding, let's discuss more whether we want to use lower bits to indicate discriminator type. Comparing with fixed position encoding (i.e. DP always consume 2 ULEB128 bytes):

Pros:

• saves ~1% debug line table size (on average)

Cons:

• added complexity to clang code and also offline profile creation code
• limited representation scope: with the new algorithm we need to have 1 extra bit to represent the profile type, which means we need to limit the useful bit to be 6 in order to fit it to 1-byte ULEB128. As a result, the maximum raw discriminator will be 63 instead of 127.

Comments?

lib/Transforms/Vectorize/LoopVectorize.cpp

216

Yes, we will guard all the logic by check profile-debug flag once https://reviews.llvm.org/D25435 is submitted. I'm not sure whether it will be a function attribute string, or simply a flag passed down from frontend.

Meanwhile, I think it will be worth to have a flag to control whether we will encode duplication in discriminator so that we have a choice to fall back to the old discriminator assignment algorithm. We can remove the flag later if we find it useless.

[hfinkel]

lib/Transforms/Utils/AddDiscriminators.cpp

197

saves ~1% debug line table size (on average)

Yes. but this 1% is 20% or more of the increase. More importantly for me, it reduces the relative expense (in terms of binary-size increase) of using distinct location tags vs. using duplication factors.

added complexity to clang code and also offline profile creation code

If this patch is any indication, then the extra complexity seems minor.

197

limited representation scope: with the new algorithm we need to have 1 extra bit to represent the profile type, which means we need to limit the useful bit to be 6 in order to fit it to 1-byte ULEB128. As a result, the maximum raw discriminator will be 63 instead of 127.

I don't like the fixed bit limit here. How about using the high bit to indicate that there are more bits in the discriminator (that's how ULEB128 itself works, right?)?

lib/Transforms/Vectorize/LoopVectorize.cpp

216

Yes, we will guard all the logic by check profile-debug flag once https://reviews.llvm.org/D25435 is submitted. I'm not sure whether it will be a function attribute string, or simply a flag passed down from frontend.

I think it needs to be an attribute. Otherwise, it won't work correctly with LTO.

[danielcdh]

update the encoding, add comments, update test.

lib/Transforms/Vectorize/LoopVectorize.cpp

216

I did not realize the LTO issue. But let's address that problem in https://reviews.llvm.org/D25435

[danielcdh]

ping...

Thanks,
Dehao

[danielcdh]

ping...

Thanks,
Dehao

[danielcdh]

ping...

Thanks,
Dehao

[danielcdh]

ping...

[hfinkel]

I apologize for my delay in getting back to this. Thanks for updating this with a more-flexible encoding scheme. It looks like in the future, should we desire, we can extend the number of fields (and/or their size). This LGTM. We can fixup replacing/supplementing the cl::opt with a function attribute in follow-up.

include/llvm/IR/DebugInfoMetadata.h

1274

We should say that, for example, the AddDiscriminators pass will do this.

lib/Transforms/Utils/AddDiscriminators.cpp

100

I'm assuming that this is for testing, correct? We'll need to add a function attribute to really control this.

[danielcdh]

lib/Transforms/Utils/AddDiscriminators.cpp

100

This is for testing purpose, and will be "true" by default when -fdebug-info-profiling is set.

I'm not sure why would we need this as a function attribute. I would suppose all binaries built with this on or off. Or am I missing something?

[hfinkel]

lib/Transforms/Utils/AddDiscriminators.cpp

100

Because we shouldn't use command-line options to communicate between the frontend and the backend. Some legacy aside, this is the strongly-preferred mechanism. It is also necessary for this to work correctly with LTO.

[danielcdh]

lib/Transforms/Utils/AddDiscriminators.cpp

100

How about using TargetOption.DebugInfoForProfiling to decide, as we check it in lib/CodeGen/AsmPrinter/DwarfDebug.cpp?

[hfinkel]

lib/Transforms/Utils/AddDiscriminators.cpp

100

I believe that's deprecated too (because it also does not work with LTO). @echristo , can you comment on this (i.e. do we need to use a function-attribute here)?

[danielcdh]

lib/Transforms/Utils/AddDiscriminators.cpp

100

Removed the flag and checks CompileUnit flag (debugInfoForProfiling) to decided if we want to encode or not.

[danielcdh]

rebase and remove the flag and use CompileUnit flag to decide if we want to encode duplication factor.

PTAL

[danielcdh]

ping...

[hfinkel]

In D26420#664205, @danielcdh wrote:

rebase and remove the flag and use CompileUnit flag to decide if we want to encode duplication factor.

PTAL

Makes sense to me, please go ahead.

Could you please add a note about debugInfoForProfiling to the LangRef section on DICompileUnit?

[danielcdh]

update LangRef

[hfinkel]

docs/LangRef.rst

4004 ↗

(On Diff #88024)

debugInfoForProfiling is not a 'tuple containing debug info to be emitted'. Instead of adding it to that list, how about adding another sentence like:

The ``debugInfoForProfiling:`` field is a boolean indicating whether or not line-table discriminators are updated to provide more-accurate profiling results.

[danielcdh]

update

[hfinkel]

In D26420#673911, @danielcdh wrote:

update

LGTM

include/llvm/IR/DebugInfoMetadata.h

public:
 
   /// Get the DWARF discriminator.
   ///
   /// DWARF discriminators distinguish identical file locations between
   /// instructions that are on different basic blocks.
   inline unsigned getDiscriminator() const;
 
   /// Returns a new DILocation with updated \p Discriminator.
   inline DILocation *cloneWithDiscriminator(unsigned Discriminator) const;
 
+  /// Returns the duplication factor stored in the discriminator.
+  inline unsigned getDuplicationFactor() const;
+
+  inline unsigned getCopyIdentifier() const;
+
+  inline unsigned getBaseDiscriminator() const;
+
+  /// Returns a new DILocation with duplication factor \p DF encoded in the
+  /// discriminator.
+  inline const DILocation *cloneWithDuplicationFactor(unsigned DF) const;
+
   Metadata *getRawScope() const { return getOperand(0); }
   Metadata *getRawInlinedAt() const {
     if (getNumOperands() == 2)
       return getOperand(1);
     return nullptr;
   }
 
   static bool classof(const Metadata *MD) {
for (auto *LBF = dyn_cast<DILexicalBlockFile>(Scope);
        LBF = dyn_cast<DILexicalBlockFile>(Scope))
     Scope = LBF->getScope();
   DILexicalBlockFile *NewScope =
       DILexicalBlockFile::get(getContext(), Scope, getFile(), Discriminator);
   return DILocation::get(getContext(), getLine(), getColumn(), NewScope,
                          getInlinedAt());
 }
 
+unsigned DILocation::getBaseDiscriminator() const {
+  unsigned D = getDiscriminator();
+  if ((D & 1) == 0)
+    return (D >> 1) & 0x3f;
+  else
+    return 0;
+}
+
+unsigned DILocation::getDuplicationFactor() const {
+  unsigned D = getDiscriminator();
+  if ((D & 1) == 0)
+    D >>= 7;
+  if (D & 1)
+    return 1;
+  return std::max(static_cast<unsigned>(1), (D >> 1) & 0x3f);
+}
+
+unsigned DILocation::getCopyIdentifier() const {
+  unsigned D = getDiscriminator();
+  if ((D & 1) == 0)
+    D >>= 7;
+  if ((D & 1) == 0)
+    D >>= 7;
+  return D;
+}
+
+const DILocation *DILocation::cloneWithDuplicationFactor(unsigned DF) const {
+  DF *= getDuplicationFactor();
+  if (DF <= 1)
+    return this;
+ 
+  unsigned BD = getBaseDiscriminator();
+  unsigned D = ((getCopyIdentifier() << 7) | DF) << 1;
+  if (BD)
+    D = (D << 7) | (BD << 1);
+  else
+    D = (D << 1) | 1;
+  return cloneWithDiscriminator(D);
+
+/*
+ unsigned D = getDiscriminator();
+  if (D & 1)
+  unsigned F = getDuplicationFactor() * DF;
+*/
+//    return cloneWithDiscriminator(0);//DF & 0x7f);
+//    return cloneWithDiscriminator(((DF * getDuplicationFactor()) << 7) |
+//                                  (getDiscriminator() & 0x7f));
+}
+
 class DINamespace : public DIScope {
   friend class LLVMContextImpl;
   friend class MDNode;
 
   unsigned Line;
   unsigned ExportSymbols : 1;
 
   DINamespace(LLVMContext &Context, StorageType Storage, unsigned Line,

lib/Transforms/Utils/AddDiscriminators.cpp

 
 // Command line option to disable discriminator generation even in the
 // presence of debug information. This is only needed when debugging
 // debug info generation issues.
 static cl::opt<bool> NoDiscriminators(
     "no-discriminators", cl::init(false),
     cl::desc("Disable generation of discriminator information."));
 
+cl::opt<bool> EncodeDuplicationInDiscriminators(
+    "encode-duplication-in-discriminators", cl::init(false),
+    cl::desc("Encode code duplication factor into the discriminator."));
+
 // Create the legacy AddDiscriminatorsPass.
 FunctionPass *llvm::createAddDiscriminatorsPass() {
   return new AddDiscriminatorsLegacyPass();
 }
 
 /// \brief Assign DWARF discriminators.
 ///
 /// To assign discriminators, we examine the boundaries of every
for (auto &I : B.getInstList()) {
       auto &BBMap = LBM[L];
       auto R = BBMap.insert(&B);
       if (BBMap.size() == 1)
         continue;
       // If we could insert more than one block with the same line+file, a
       // discriminator is needed to distinguish both instructions.
       // Only the lowest 7 bits are used to represent a discriminator to fit
       // it in 1 byte ULEB128 representation.
-      unsigned Discriminator = (R.second ? ++LDM[L] : LDM[L]) & 0x7f;
+      unsigned Discriminator = ((R.second ? ++LDM[L] : LDM[L]) << 1) & 0x7f;
       I.setDebugLoc(DIL->cloneWithDiscriminator(Discriminator));
       DEBUG(dbgs() << DIL->getFilename() << ":" << DIL->getLine() << ":"
                    << DIL->getColumn() << ":" << Discriminator << " " << I
                    << "\n");
       Changed = true;
     }
   }
 
for (auto &I : B.getInstList()) {
         continue;
 
       DILocation *CurrentDIL = Current->getDebugLoc();
       if (!CurrentDIL)
         continue;
       Location L =
           std::make_pair(CurrentDIL->getFilename(), CurrentDIL->getLine());
       if (!CallLocations.insert(L).second) {
-        Current->setDebugLoc(
-            CurrentDIL->cloneWithDiscriminator((++LDM[L]) & 0x7f));
+        unsigned Discriminator = ((++LDM[L]) << 1) & 0x7f;
+        Current->setDebugLoc(CurrentDIL->cloneWithDiscriminator(Discriminator));
         Changed = true;
       }
     }
   }
   return Changed;
 }
 
 bool AddDiscriminatorsLegacyPass::runOnFunction(Function &F) {

lib/Transforms/Utils/LoopUnroll.cpp

 #include "llvm/Analysis/AssumptionCache.h"
 #include "llvm/Analysis/InstructionSimplify.h"
 #include "llvm/Analysis/LoopIterator.h"
 #include "llvm/Analysis/LoopPass.h"
 #include "llvm/Analysis/OptimizationDiagnosticInfo.h"
 #include "llvm/Analysis/ScalarEvolution.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/SimplifyIndVar.h"
 using namespace llvm;
 
 #define DEBUG_TYPE "loop-unroll"
 
 // TODO: Should these be here or in LoopUnroll?
 STATISTIC(NumCompletelyUnrolled, "Number of loops completely unrolled");
 STATISTIC(NumUnrolled, "Number of loops unrolled (completely or otherwise)");
 
 static cl::opt<bool>
 UnrollRuntimeEpilog("unroll-runtime-epilog", cl::init(false), cl::Hidden,
                     cl::desc("Allow runtime unrolled loops to be unrolled "
                              "with epilog instead of prolog."));
 
+extern cl::opt<bool> EncodeDuplicationInDiscriminators;
+
 /// Convert the instruction operands from referencing the current values into
 /// those specified by VMap.
 static inline void remapInstruction(Instruction *I,
                                     ValueToValueMapTy &VMap) {
   for (unsigned op = 0, E = I->getNumOperands(); op != E; ++op) {
     Value *Op = I->getOperand(op);
     ValueToValueMapTy::iterator It = VMap.find(Op);
     if (It != VMap.end())
bool llvm::UnrollLoop(Loop *L, unsigned Count, unsigned TripCount, bool Force,
   // Loop Unrolling might create new loops. While we do preserve LoopInfo, we
   // might break loop-simplified form for these loops (as they, e.g., would
   // share the same exit blocks). We'll keep track of loops for which we can
   // break this so that later we can re-simplify them.
   SmallSetVector<Loop *, 4> LoopsToSimplify;
   for (Loop *SubLoop : *L)
     LoopsToSimplify.insert(SubLoop);
 
+  if (EncodeDuplicationInDiscriminators)
+    for (BasicBlock *BB : L->getBlocks())
+      for (Instruction &I : *BB)
+        if (const DILocation *DIL = I.getDebugLoc())
+          I.setDebugLoc(DIL->cloneWithDuplicationFactor(Count));
+
   for (unsigned It = 1; It != 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));

lib/Transforms/Vectorize/LoopVectorize.cpp

static cl::opt<unsigned> VectorizeSCEVCheckThreshold(
     "vectorize-scev-check-threshold", cl::init(16), cl::Hidden,
     cl::desc("The maximum number of SCEV checks allowed."));
 
 static cl::opt<unsigned> PragmaVectorizeSCEVCheckThreshold(
     "pragma-vectorize-scev-check-threshold", cl::init(128), cl::Hidden,
     cl::desc("The maximum number of SCEV checks allowed with a "
              "vectorize(enable) pragma"));
 
+extern cl::opt<bool> EncodeDuplicationInDiscriminators;
+
 /// Create an analysis remark that explains why vectorization failed
 ///
 /// \p PassName is the name of the pass (e.g. can be AlwaysPrint).  \p
 /// RemarkName is the identifier for the remark.  If \p I is passed it is an
 /// instruction that prevents vectorization.  Otherwise \p TheLoop is used for
 /// the location of the remark.  \return the remark object that can be
 /// streamed to.
 static OptimizationRemarkAnalysis
protected:
   /// addNewMetadata).  Use this for *newly created* instructions in the vector
   /// loop.
   void addMetadata(Instruction *To, Instruction *From);
 
   /// \brief Similar to the previous function but it adds the metadata to a
   /// vector of instructions.
   void addMetadata(ArrayRef<Value *> To, Instruction *From);
 
+  /// \brief Set the debug location in the builder using the debug location in
+  /// the instruction.
+  void setDebugLocFromInst(IRBuilder<> &B, const Value *Ptr);
+
   /// This is a helper class for maintaining vectorization state. It's used for
   /// mapping values from the original loop to their corresponding values in
   /// the new loop. Two mappings are maintained: one for vectorized values and
   /// one for scalarized values. Vectorized values are represented with UF
   /// vector values in the new loop, and scalarized values are represented with
   /// UF x VF scalar values in the new loop. UF and VF are the unroll and
   /// vectorization factors, respectively.
   ///
for (User::op_iterator OI = I->op_begin(), OE = I->op_end(); OI != OE; ++OI) {
     if (Instruction *OpInst = dyn_cast<Instruction>(*OI))
       if (OpInst->getDebugLoc() != Empty)
         return OpInst;
   }
 
   return I;
 }
 
-/// \brief Set the debug location in the builder using the debug location in the
-/// instruction.
-static void setDebugLocFromInst(IRBuilder<> &B, const Value *Ptr) {
-  if (const Instruction *Inst = dyn_cast_or_null<Instruction>(Ptr))
-    B.SetCurrentDebugLocation(Inst->getDebugLoc());
+void InnerLoopVectorizer::setDebugLocFromInst(IRBuilder<> &B, const Value *Ptr) {
+  if (const Instruction *Inst = dyn_cast_or_null<Instruction>(Ptr)) {
+    const DILocation *DIL = Inst->getDebugLoc();
+    if (DIL && EncodeDuplicationInDiscriminators)
+      B.SetCurrentDebugLocation(DIL->cloneWithDuplicationFactor(UF * VF));
     else
+      B.SetCurrentDebugLocation(DIL);
+  } else
     B.SetCurrentDebugLocation(DebugLoc());
 }
 
 #ifndef NDEBUG
 /// \return string containing a file name and a line # for the given loop.
 static std::string getDebugLocString(const Loop *L) {
   std::string Result;
   if (L) {

test/Transforms/LoopVectorize/discriminator.ll

+; RUN: opt -S -loop-vectorize -force-vector-width=4 -force-vector-interleave=1 < %s | FileCheck --check-prefix=LOOPVEC_NO_ENCODE %s
+; RUN: opt -S -loop-vectorize -force-vector-width=4 -force-vector-interleave=1 -encode-duplication-in-discriminators < %s | FileCheck --check-prefix=LOOPVEC_4_1 %s
+; RUN: opt -S -loop-vectorize -force-vector-width=2 -force-vector-interleave=3 -encode-duplication-in-discriminators < %s | FileCheck --check-prefix=LOOPVEC_2_3 %s
+; RUN: opt -S -loop-unroll  -unroll-count=5 < %s | FileCheck --check-prefix=LOOPUNROLL_NO_ENCODE %s
+; RUN: opt -S -loop-unroll  -unroll-count=5 -encode-duplication-in-discriminators < %s | FileCheck --check-prefix=LOOPUNROLL_5 %s
+; RUN: opt -S -loop-vectorize -force-vector-width=3 -force-vector-interleave=3 -loop-unroll -unroll-count=2 -encode-duplication-in-discriminators < %s | FileCheck --check-prefix=LOOPVEC_UNROLL %s
+
+; Test if vectorization/unroll factor is recorded in discriminator.
+;
+; Original source code:
+;  1 int *a;
+;  2 int *b;
+;  3 
+;  4 void foo() {
+;  5   for (int i = 0; i < 4096; i++)
+;  6     a[i] += b[i];
+;  7 }
+
+@a = local_unnamed_addr global i32* null, align 8
+@b = local_unnamed_addr global i32* null, align 8
+
+define void @_Z3foov() local_unnamed_addr #0 !dbg !6 {
+  %1 = load i32*, i32** @b, align 8, !dbg !8, !tbaa !9
+  %2 = load i32*, i32** @a, align 8, !dbg !13, !tbaa !9
+  br label %3, !dbg !14
+
+; <label>:3:                                      ; preds = %3, %0
+  %indvars.iv = phi i64 [ 0, %0 ], [ %indvars.iv.next, %3 ]
+  %4 = getelementptr inbounds i32, i32* %1, i64 %indvars.iv, !dbg !8
+  %5 = load i32, i32* %4, align 4, !dbg !8, !tbaa !15
+  %6 = getelementptr inbounds i32, i32* %2, i64 %indvars.iv, !dbg !13
+  %7 = load i32, i32* %6, align 4, !dbg !17, !tbaa !15
+  %8 = add nsw i32 %7, %5, !dbg !17
+  store i32 %8, i32* %6, align 4, !dbg !17, !tbaa !15
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1, !dbg !18
+  %exitcond = icmp eq i64 %indvars.iv.next, 4096, !dbg !19
+  br i1 %exitcond, label %9, label %3, !dbg !14, !llvm.loop !20
+
+; <label>:9:                                      ; preds = %3
+  ret void, !dbg !21
+}
+
+;LOOPVEC_NO_ENCODE-NOT: discriminator
+;LOOPVEC_4_1: discriminator: 512
+;LOOPVEC_2_3: discriminator: 768
+;LOOPUNROLL_NO_ENCODE-NOT: discriminator
+;LOOPUNROLL_5: discriminator: 640
+; When unrolling after loop vectorize, both vec_body and remainder loop
+; are unrolled.
+;LOOPVEC_UNROLL: discriminator: 2304
+;LOOPVEC_UNROLL: discriminator: 256
+
+!llvm.dbg.cu = !{!0}
+!llvm.module.flags = !{!3, !4}
+
+!0 = distinct !DICompileUnit(language: DW_LANG_C_plus_plus, file: !1)
+!1 = !DIFile(filename: "a.cc", directory: "/")
+!3 = !{i32 2, !"Dwarf Version", i32 4}
+!4 = !{i32 2, !"Debug Info Version", i32 3}
+!6 = distinct !DISubprogram(name: "foo", scope: !1, file: !1, line: 4, unit: !0)
+!8 = !DILocation(line: 6, column: 13, scope: !6)
+!9 = !{!10, !10, i64 0}
+!10 = !{!"any pointer", !11, i64 0}
+!11 = !{!"omnipotent char", !12, i64 0}
+!12 = !{!"Simple C++ TBAA"}
+!13 = !DILocation(line: 6, column: 5, scope: !6)
+!14 = !DILocation(line: 5, column: 3, scope: !6)
+!15 = !{!16, !16, i64 0}
+!16 = !{!"int", !11, i64 0}
+!17 = !DILocation(line: 6, column: 10, scope: !6)
+!18 = !DILocation(line: 5, column: 30, scope: !6)
+!19 = !DILocation(line: 5, column: 21, scope: !6)
+!20 = distinct !{!20, !14}
+!21 = !DILocation(line: 7, column: 1, scope: !6)