[SampleFDO] New hierarchical discriminator for Flow Sensitive SampleFDO

[xur]

Summary

This patch implements first part of Flow Sensitive SampleFDO (FSAFDO). It has
the following changes:
(1) disable current discriminator coding scheme,
(2) new hierarchical discriminator for FSAFDO.

For this patch, "-enable-fs-discriminator=true" turns on the new functionality.
"-enable-fs-discriminator=false" (the default) keeps the current SampleFDO
behavior. When the fs-discriminator is enabled, we insert a flag variable,
llvm_fs_discriminator, to the object.
This symbol will checked by create_llvm_prof tool, and used to generate a
profile with FS-AFDO discriminators enabled.
If this happens, for an extbinary format profile, create_llvm_prof tool will add a
flag to profile summary section. For other format profiles, the
users need to use an internal option (-profile-isfs) to tell the compiler that the
profile uses FS-AFDO discriminators.

[wmi]

Can you split the changes under ProfileData into a separate patch?

llvm/include/llvm/IR/DebugInfoMetadata.h

65

This may introduce undefined variable problem if llvm library user only use LLVMCore and not LLVMProfileData. The locations of definition and declaration need to be swapped.

1771

If the first bit is the 0th bit, the 1 in 0x1FF is in the 8th bit and why input B = 7 can clear it?

[xur]

In D102246#2754153, @wmi wrote:

Can you split the changes under ProfileData into a separate patch?

OK. I will do that.

llvm/include/llvm/IR/DebugInfoMetadata.h

65

OK. This makes sense. I'll fix this.

1771

The comment is not accurate. It should be "Zero out the (B+1)-th and above bits for D.

[hoy]

llvm/include/llvm/CodeGen/FSAFDODiscriminator.h

12

Nit: its

llvm/include/llvm/IR/DebugInfoMetadata.h

1771

Looks like B == 0 is a special case, can you please update the comment for that too?

llvm/lib/CodeGen/FSAFDODiscriminator.cpp

48

BB.getName() and getSubprogram()->getLinkageName() could be empty. Could it be a problem?

78

The xor could result in 1 for higher bits above HighBit. Does it matter?

llvm/lib/ProfileData/SampleProfReader.cpp

260 ↗

(On Diff #344417)

Set FunctionSamples::ProfileIsFS as well to be consistent with the extbin reader?

[xur]

Hoy, Thanks for comments!

llvm/include/llvm/IR/DebugInfoMetadata.h

1771

Thanks. Will update this.

llvm/lib/CodeGen/FSAFDODiscriminator.cpp

48

MD5Hash can take empty string. I did not encounter issues for this.

78

This should not happen. The bits higher than HighBit should be 0 for for variables.

llvm/lib/ProfileData/SampleProfReader.cpp

260 ↗

(On Diff #344417)

Extbin format is a little different from other formats. We assume the format is encoded in summary section.
It's in function SampleProfileReaderExtBinaryBase::readOneSection().

I did not overwrite the flag in summary section with the internal flag -- this flag is mostly used in test and debug with text and binary format. I assume most users will be using extbinary format where flag variable in summary section should have been set properly.

[xur]

llvm/include/llvm/IR/DebugInfoMetadata.h

1771

Think again, I'll remove the special case of B==0. Currently there is not caller with B==0.

[xur]

Integrated Wi and Hongtao's review comments. Split changes in ProfileData and llvm-profdata to separated patches.

[snehasish]

llvm/include/llvm/Support/FSAFDODiscriminator.h

42

I don't think these helpers are used in this patch. If so can we remove them from this patch and add it when they are actually used?

llvm/lib/CodeGen/FSAFDODiscriminator.cpp

25

This seems to be unused?

69

Why not just use the MF reference throughout? I don't see any uses in this function where a pointer is necessary.

91

nit: I think this can simply be written as
Location L{DIL->getFilename(), LineNo};

same for LocationDiscriminator LD below.

119

I think this should not be set unless we actually set the DILocation for the instruction (i.e. only when the else part is executed). Perhaps just add a continue on L110 inside the if() so that you can remove the else indentation block making it a bit easier to read as well.

125

Just use const char * since this string is immutable?
Also typo in FSDisriminatorVar -> FSDiscriminatorVar

llvm/lib/CodeGen/TargetPassConfig.cpp

169

Can you also augment the comment to indicate where this option might be useful? It wasn't clear to me why this is needed.

llvm/lib/Transforms/Utils/LoopUnroll.cpp

579–581

Can you add a comment here and below why this loop is skipped when FSDiscriminators are requested?

llvm/test/CodeGen/X86/fsafdo_test2.ll

9

nit: I think ;; is used for comments. Adding a new line before the comment wouldn't hurt either.

24

Since the IR for this test is non-trivial, can you include the c source and the invocation used to generate this?
Probably good to do for the previous test as well.

[xur]

snehasish, thanks for the reviewing comments! I'll integrate your comments and update the patch.

llvm/include/llvm/Support/FSAFDODiscriminator.h

42

Yes. That are for the FS profile loader. I'll remove them and add later when they are used.

llvm/lib/CodeGen/FSAFDODiscriminator.cpp

25

This is left over from refactor. I'll remove this.

69

This code has been changed quite a bit over time. But you are right that now we can use reference directly. I will make the change.

91

Yes. will fix.

119

It's rarely that cloneWithDiscriminator return empty DIL. But you are right here -- I should only set in the else clause.
I will fix this.

125

Right. I'll fix.

llvm/lib/CodeGen/TargetPassConfig.cpp

169

This is for debuging and tuning purpose. I don't think this gonna hurt anything. If later we found this rarely used, we can remove by then.

llvm/lib/Transforms/Utils/LoopUnroll.cpp

579–581

This is just to disable the existing multiply factor in discriminators.
I will add a comment here (and a few other places like this).

llvm/test/CodeGen/X86/fsafdo_test2.ll

9

will fix.

24

Yes. This is a good idea.

[xur]

Integrated Snehasish's review comments.

[snehasish]

lgtm, however please wait a bit for any follow up comments from other reviewers. Thanks!

[wmi]

Thanks for splitting the patches.

llvm/include/llvm/IR/DebugInfoMetadata.h

2246

It will be slightly clearer if the cases of EnableFSDiscriminator being true and false are not interleaved, so that it is easy to know that there won't be undefined use for DF and CI.

if (EnableFSDiscriminator) {
  return ...;
}
...

llvm/lib/CodeGen/FSAFDODiscriminator.cpp

55

Could you describe how FSDiscriminator is computed here?

60–61

How about using tuple for LocationDiscriminator?

llvm/lib/CodeGen/TargetPassConfig.cpp

169

typo: discriminators

173

typo: discriminators

llvm/test/Transforms/SampleProfile/Inputs/fsafdo.prof

1

fsafdo.prof and fsafdo.extbinary.afdo may only be used in the other splitted patch.

[xur]

llvm/include/llvm/IR/DebugInfoMetadata.h

2246

agreed. I will change this.

llvm/lib/CodeGen/FSAFDODiscriminator.cpp

60–61

Yes. I think that's a better choice.

[wenlei]

llvm/include/llvm/CodeGen/FSAFDODiscriminator.h

1

IIUC, FSDiscriminator can be added to IR pass too, possibly with the existing AddDiscriminator IR pass plus tweak on discriminator encoding.

The current implementation makes it look like FSDiscriminator is tied to MIR pass alone.. Perhaps name the files/pass for MIR AddMIR[FS]Discriminator etc so it doesn't convey the message that FSDiscriminator is tied to MIR?

llvm/include/llvm/Support/FSAFDODiscriminator.h

1

I wondering if it also makes sense to pull all existing discriminator encoding stuff into a single header, for consistency. Then it can be Discriminator.h

encodeDiscriminator/decodeDiscriminator for today's discriminator encoding are static functions that does pure encoding and can live anywhere.

17

Is this needed?

36

Is N>31 actually expected? could assert?

llvm/lib/CodeGen/FSAFDODiscriminator.cpp

48

Empty string may not be a big/noticeable problem as it just slightly increase the chance of hash collision. I think in many places, we fall back to getName when getLinkageName is empty.

llvm/lib/Transforms/Utils/LoopUnroll.cpp

586

It's probably cleaner to just bail out inside cloneByMultiplyingDuplicationFactor by checking EnableFSDiscriminator, return this if that flag is on. That would avoid checks for the 3 loop passes. But for compile time, there's no reason to go through the IR if we aren't going to do anything.

If we skip these from the loop passes, how about also assert in cloneByMultiplyingDuplicationFactor that EnableFSDiscriminator if off as a safe guard.

[xur]

Thanks to Wei for the comments. Here is the version integrate his suggestions.

[wenlei]

llvm/lib/CodeGen/FSAFDODiscriminator.cpp

90

When discriminator passes run in order, do we actually expect anything to add bits outside of BitMaskBefore?

100

This seems different from the description in original RFC where you talked about using count of total discriminators and sequential id as seed for a fs-discriminator. Given that we still use inline stack as part of line info, and discriminator is on top of line stack, what extra benefit does hashing the entire inline stack bring us?

[xur]

Thanks to Wenlei for the comments!

llvm/include/llvm/CodeGen/FSAFDODiscriminator.h

1

Yes. This is true. The IR level FSDiscriminator could a revised version of current AddDiscriminator pass. I'll follow your suggestion and do the renaming.

llvm/include/llvm/Support/FSAFDODiscriminator.h

1

This is doable. Let me try.

17

This was needed by other functions that were split from this patch. Thanks for catching this. I'll remove it.

36

should not be greater than 31. Assert is good idea.

llvm/lib/CodeGen/FSAFDODiscriminator.cpp

48

For the case of empty name and linkagename, they do return the same hash and may result in a conflict. But I don't thing we can do much here - it just means we cannot use call stack to differentiate.

llvm/lib/Transforms/Utils/LoopUnroll.cpp

586

I was thinking the same. But decided to do this way to favor the compile time. We might want to deprecate multiply factor later, so all this might be just a temporary thing.
I will add an assert in cloneByMultiplyingDuplicationFactor

[xur]

llvm/lib/CodeGen/FSAFDODiscriminator.cpp

90

I'm not fully understand the question.

This is to compute the bits that can be set in this pass. BitMaskBefore for the mask for the bits that have been set by previous passes -- it assumes the the previous discriminators only touch the lower bits.

100

yes. this part has gone through quite some change before and after RFC. Here we still uses a sequential id.
Add a callstack hash is just one more safety measure to catch the mismatches.

[wenlei]

cc: @wlei

llvm/lib/CodeGen/FSAFDODiscriminator.cpp

90

I was wondering whether (Discriminator &= BitMaskBefore) == Discriminator is expected here since we haven't set extra bits for current pass yet. If that's true, then the &= is not needed or could be an assert?

(I think somehow the comment got associated with the wrong line, it should about Discriminator &= BitMaskBefore;).

100

Not a big deal, but I think since we always have line stack, and discriminator always has paired line stack, it doesn't need to have that info captured. Could saving the walk over inlineAt chain?

[xur]

llvm/lib/CodeGen/FSAFDODiscriminator.cpp

90

Yes. you are right here. I'll remove that stmt.

100

when we insert the discriminator, we just just check the lineno (I meant the tuple of <filename, lineno, discriminator) -- this is not line stack.
I did some pretty large build and did not find this part consume much time.

I'll keep this in mind and gonna revisit in the tuning.

[xur]

Integrated Wenlei's suggestions.

@wenlei: I only moved encoding / decoding static functions from DebugInfoMetadata.h to the new Support/Discriminator.h and left other discriminator codes in DebugInfoMetadata.h. Not sure if this is what you meant in the comments.

[wenlei]

llvm/lib/CodeGen/FSAFDODiscriminator.cpp

100

ok, it's fine for now. For existing sample loader, we use nested FunctionSamples to get profile for instruction based on its line stack (FunctionSamples::findFunctionSamples), so the use of line stack is implicit there. Not sure if FS sample loader is different.

[wenlei]

In D102246#2760712, @xur wrote:

Integrated Wenlei's suggestions.

@wenlei: I only moved encoding / decoding static functions from DebugInfoMetadata.h to the new Support/Discriminator.h and left other discriminator codes in DebugInfoMetadata.h. Not sure if this is what you meant in the comments.

Right, that's what I meant. Thanks for the refactoring.

[xur]

llvm/lib/CodeGen/FSAFDODiscriminator.cpp

100

ok, it's fine for now. For existing sample loader, we use nested FunctionSamples to get profile for instruction based on its line stack (FunctionSamples::findFunctionSamples), so the use of line stack is implicit there. Not sure if FS sample loader is different.

Oh. I see what you meant here now. FS sample loader uses the same mechanism. In this sense, yes, the location has the call stack info. I'll do some more experiments on this. For now, let's just keep it.

[hoy]

llvm/lib/CodeGen/MIRFSDiscriminator.cpp

67 ↗

(On Diff #345549)

Nit: not sure if std::unordered_multimap can be a bit faster by not constructing a BBSet if most instructions are not duplicated.

llvm/lib/CodeGen/TargetPassConfig.cpp

1181

Wondering why using PASS_LAST_DIS_BIT_BEG here. Will other bits be used in later patches?

[xur]

llvm/lib/CodeGen/MIRFSDiscriminator.cpp

67 ↗

(On Diff #345549)

Do you mean line line 67 using
std::unordered_multimap<LocationDiscriminator, const MachineBasicBlock *> ?

I'm not sure.
My impression is DenseMap performs closely to unordered_multimap. You are considering the cost of constructing BBSet. I agree with your on this. But for some cases, there are lot instruction duplicattion for some <line, discriminator> -- like some codes in stl header. In these cases, unordered_multimap might not perform well as it needs to store all the BBs.

Let me run an experiments to compare. I will report back.

llvm/lib/CodeGen/TargetPassConfig.cpp

1181

This is to catch all the clones in the optimization pipeline, so we could sum the samples instead of using max. We will have a FS profile loader here. For earlier pass, there will be an FS Profile loader for each AddFSDiscriminatorPass.

[xur]

llvm/lib/CodeGen/MIRFSDiscriminator.cpp

67 ↗

(On Diff #345549)

When I tried the multimap, I found it did not fit here well here. The problem is for the same <file, lineno, discriminator> tuple, if they are in the same BB, BBset will aggregate them together. For the multimap, they are of different entries. Without checking all the entries with the same key, I could not tell if they are with the same BB, or with different BB. In short, we need to check all the entries and find out (1) if they are from the same BB (2) if there are two distinct BBs in the map. The code is not as clean as using a set.

Anyway, I tested both implementations using SPEC2006/Xalancbmk and one large google benchmark. The compiler time for these two about the same (note that compiler time has a pretty large noise range).

I think I would like to keep DenseSet version.

[wmi]

LGTM.

[hoy]

llvm/lib/CodeGen/MIRFSDiscriminator.cpp

67 ↗

(On Diff #345549)

Sounds good. Thanks for the analysis and experiment.

[wenlei]

lgtm too, thanks. looking forward to complete fs-adfo support and we'd be happy to give it a try.

llvm/include/llvm/CodeGen/FSAFDODiscriminator.h

+//===----- FSAFDODiscriminator.h: FS Discriminator Support --0---*- 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 contains the supporting functions for adding Flow Sensitive
+// discriminators to the instruction debug information.  With this, a cloned
+// machine instruction in a different MachineBasicBlock will have its own
+// discriminator value.  This is done in a AddFSDiscriminators pass.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CODEGEN_FSAFDODISCRIMINATOR_H
+#define LLVM_CODEGEN_FSAFDODISCRIMINATOR_H
+
+#include "llvm/Analysis/ProfileSummaryInfo.h"
+#include "llvm/CodeGen/MachineBasicBlock.h"
+#include "llvm/CodeGen/MachineBlockFrequencyInfo.h"
+#include "llvm/CodeGen/MachineBranchProbabilityInfo.h"
+#include "llvm/CodeGen/MachineDominators.h"
+#include "llvm/CodeGen/MachineFunction.h"
+#include "llvm/CodeGen/MachineFunctionPass.h"
+#include "llvm/CodeGen/MachineInstr.h"
+#include "llvm/CodeGen/MachineLoopInfo.h"
+#include "llvm/CodeGen/MachineOptimizationRemarkEmitter.h"
+#include "llvm/CodeGen/MachinePostDominators.h"
+#include "llvm/CodeGen/Passes.h"
+#include "llvm/IR/DebugInfoMetadata.h"
+#include "llvm/IR/Function.h"
+#include "llvm/IR/Module.h"
+#include "llvm/InitializePasses.h"
+#include "llvm/ProfileData/InstrProf.h"
+#include "llvm/ProfileData/SampleProf.h"
+#include "llvm/ProfileData/SampleProfReader.h"
+
+#include <cassert>
+
+namespace llvm {
+
+class AddFSDiscriminators : public MachineFunctionPass {
+  MachineFunction *MF;
+  unsigned LowBit;
+  unsigned HighBit;
+
+public:
+  static char ID;
+  /// FS bits that will be used in this pass (numbers are 0 based and
+  /// inclusive).
+  AddFSDiscriminators(unsigned LowBit = 0, unsigned HighBit = 0)
+      : MachineFunctionPass(ID), LowBit(LowBit), HighBit(HighBit) {
+    assert(LowBit < HighBit && "HighBit needs to be greater than Lowbit");
+  }
+
+  /// getNumFSBBs() - Return the number of machine BBs that have FS samples.
+  unsigned getNumFSBBs();
+
+  /// getNumFSSamples() - Return the number of samples that have flow sensitive
+  /// values.
+  uint64_t getNumFSSamples();
+
+  /// getMachineFunction - Return the current machine function.
+  const MachineFunction *getMachineFunction() const { return MF; }
+
+private:
+  bool runOnMachineFunction(MachineFunction &) override;
+};
+
+} // namespace llvm
+
+#endif // LLVM_CODEGEN_FSAFDODISCRIMINATOR_H

llvm/include/llvm/CodeGen/Passes.h

namespace llvm {
   extern char &DeadMachineInstructionElimID;
 
   /// This pass adds dead/undef flags after analyzing subregister lanes.
   extern char &DetectDeadLanesID;
 
   /// This pass perform post-ra machine sink for COPY instructions.
   extern char &PostRAMachineSinkingID;
 
+  /// This pass adds flow sensitive discriminators.
+  extern char &AddFSDiscriminatorsID;
+
   /// FastRegisterAllocation Pass - This pass register allocates as fast as
   /// possible. It is best suited for debug code where live ranges are short.
   ///
   FunctionPass *createFastRegisterAllocator();
 
   /// BasicRegisterAllocation Pass - This pass implements a degenerate global
   /// register allocator using the basic regalloc framework.
   ///
namespace llvm {
   FunctionPass *createHardwareLoopsPass();
 
   /// This pass inserts pseudo probe annotation for callsite profiling.
   FunctionPass *createPseudoProbeInserter();
 
   /// Create IR Type Promotion pass. \see TypePromotion.cpp
   FunctionPass *createTypePromotionPass();
 
+  /// Add Flow Sensitive Discriminators.
+  FunctionPass *createAddFSDiscriminatorsPass(unsigned LowBit,
+                                              unsigned HighBit);
+
   /// Creates MIR Debugify pass. \see MachineDebugify.cpp
   ModulePass *createDebugifyMachineModulePass();
 
   /// Creates MIR Strip Debug pass. \see MachineStripDebug.cpp
   /// If OnlyDebugified is true then it will only strip debug info if it was
   /// added by a Debugify pass. The module will be left unchanged if the debug
   /// info was generated by another source such as clang.
   ModulePass *createStripDebugMachineModulePass(bool OnlyDebugified);

llvm/include/llvm/IR/DebugInfoMetadata.h

 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/ADT/iterator_range.h"
 #include "llvm/BinaryFormat/Dwarf.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/Metadata.h"
 #include "llvm/Support/Casting.h"
+#include "llvm/Support/CommandLine.h"
+#include "llvm/Support/FSAFDODiscriminator.h"
 #include <cassert>
 #include <climits>
 #include <cstddef>
 #include <cstdint>
 #include <iterator>
 #include <type_traits>
 #include <vector>
 
static CLASS *getIfExists(LLVMContext &Context,                              \
                             DEFINE_MDNODE_GET_UNPACK(FORMAL)) {                \
     return getImpl(Context, DEFINE_MDNODE_GET_UNPACK(ARGS), Uniqued,           \
                    /* ShouldCreate */ false);                                  \
   }                                                                            \
   DEFINE_MDNODE_GET_DISTINCT_TEMPORARY(CLASS, FORMAL, ARGS)
 
 namespace llvm {
 
+extern cl::opt<bool> EnableFSDiscriminator;
+
 class DITypeRefArray {
   const MDTuple *N = nullptr;
 
 public:
   DITypeRefArray() = default;
   DITypeRefArray(const MDTuple *N) : N(N) {}
 
   explicit operator bool() const { return get(); }
public:
 
   /// Try to combine the vector of locations passed as input in a single one.
   /// This function applies getMergedLocation() repeatedly left-to-right.
   ///
   /// \p Locs: The locations to be merged.
   static
   const DILocation *getMergedLocations(ArrayRef<const DILocation *> Locs);
 
+  /// Return the masked discriminator value for an input discrimnator value D
+  /// (i.e. zero out the (B+1)-th and above bits for D (B is 0-base).
+  // Example: an input of (0x1FF, 7) returns 0xFF.
+  static unsigned getMaskedDiscriminator(unsigned D, unsigned B) {
+    return (D & getN1Bits(B));
+  }
+
+  /// Return the bits used for base discriminators.
+  static unsigned getBaseDiscriminatorBits() { return BASE_DIS_BIT_END; }
+
   /// Returns the base discriminator for a given encoded discriminator \p D.
   static unsigned getBaseDiscriminatorFromDiscriminator(unsigned D) {
+    if (EnableFSDiscriminator)
+      return getMaskedDiscriminator(D, getBaseDiscriminatorBits());
     return getUnsignedFromPrefixEncoding(D);
   }
 
   /// Raw encoding of the discriminator. APIs such as cloneWithDuplicationFactor
   /// have certain special case behavior (e.g. treating empty duplication factor
   /// as the value '1').
   /// This API, in conjunction with cloneWithDiscriminator, may be used to encode
   /// the raw values provided. \p BD: base discriminator \p DF: duplication factor
   /// \p CI: copy index
   /// The return is None if the values cannot be encoded in 32 bits - for
   /// example, values for BD or DF larger than 12 bits. Otherwise, the return
   /// is the encoded value.
   static Optional<unsigned> encodeDiscriminator(unsigned BD, unsigned DF, unsigned CI);
 
   /// Raw decoder for values in an encoded discriminator D.
   static void decodeDiscriminator(unsigned D, unsigned &BD, unsigned &DF,
                                   unsigned &CI);
 
   /// Returns the duplication factor for a given encoded discriminator \p D, or
   /// 1 if no value or 0 is encoded.
   static unsigned getDuplicationFactorFromDiscriminator(unsigned D) {
+    if (EnableFSDiscriminator)
+      return 1;
     D = getNextComponentInDiscriminator(D);
     unsigned Ret = getUnsignedFromPrefixEncoding(D);
     if (Ret == 0)
       return 1;
     return Ret;
   }
 
   /// Returns the copy identifier for a given encoded discriminator \p D.
unsigned DILocation::getDuplicationFactor() const {
   return getDuplicationFactorFromDiscriminator(getDiscriminator());
 }
 
 unsigned DILocation::getCopyIdentifier() const {
   return getCopyIdentifierFromDiscriminator(getDiscriminator());
 }
 
 Optional<const DILocation *> DILocation::cloneWithBaseDiscriminator(unsigned D) const {
   unsigned BD, DF, CI;
+  if (EnableFSDiscriminator)
+    BD = getBaseDiscriminator();
+  else
     decodeDiscriminator(getDiscriminator(), BD, DF, CI);
   if (D == BD)
     return this;
+  if (EnableFSDiscriminator)
+    return cloneWithDiscriminator(D);
   if (Optional<unsigned> Encoded = encodeDiscriminator(D, DF, CI))
     return cloneWithDiscriminator(*Encoded);
   return None;
 }
 
 Optional<const DILocation *> DILocation::cloneByMultiplyingDuplicationFactor(unsigned DF) const {
   DF *= getDuplicationFactor();
   if (DF <= 1)

llvm/include/llvm/InitializePasses.h

 
 /// Initialize all passes linked into the CodeGen library.
 void initializeTarget(PassRegistry&);
 
 void initializeAAEvalLegacyPassPass(PassRegistry&);
 void initializeAAResultsWrapperPassPass(PassRegistry&);
 void initializeADCELegacyPassPass(PassRegistry&);
 void initializeAddDiscriminatorsLegacyPassPass(PassRegistry&);
+void initializeAddFSDiscriminatorsPass(PassRegistry &);
 void initializeModuleAddressSanitizerLegacyPassPass(PassRegistry &);
 void initializeASanGlobalsMetadataWrapperPassPass(PassRegistry &);
 void initializeAddressSanitizerLegacyPassPass(PassRegistry &);
 void initializeAggressiveInstCombinerLegacyPassPass(PassRegistry&);
 void initializeAliasSetPrinterPass(PassRegistry&);
 void initializeAlignmentFromAssumptionsPass(PassRegistry&);
 void initializeAlwaysInlinerLegacyPassPass(PassRegistry&);
 void initializeAssumeSimplifyPassLegacyPassPass(PassRegistry &);

llvm/include/llvm/LTO/Config.h

struct Config {
   bool TimeTraceEnabled = false;
 
   /// Time trace granularity.
   unsigned TimeTraceGranularity = 500;
 
   bool ShouldDiscardValueNames = true;
   DiagnosticHandlerFunction DiagHandler;
 
+  /// Add FSAFDO discriminators.
+  bool AddFSDiscriminator = false;
+
   /// If this field is set, LTO will write input file paths and symbol
   /// resolutions here in llvm-lto2 command line flag format. This can be
   /// used for testing and for running the LTO pipeline outside of the linker
   /// with llvm-lto2.
   std::unique_ptr<raw_ostream> ResolutionFile;
 
   /// Tunable parameters for passes in the default pipelines.
   PipelineTuningOptions PTO;

llvm/include/llvm/Support/FSAFDODiscriminator.h

+//===- llvm/Support/FSAFDODiscriminator.h -----------------------*- 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 the constants and utility functions used by the FSAFDO
+// passes.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_SUPPORT_FSAFDODISCRIMINATOR_H
+#define LLVM_SUPPORT_FSAFDODISCRIMINATOR_H
+
+#include "llvm/Support/ErrorHandling.h"
+
+#define BASE_DIS_BIT_BEG 0
+#define BASE_DIS_BIT_END 7
+
+#define PASS_1_DIS_BIT_BEG 8
+#define PASS_1_DIS_BIT_END 13
+
+#define PASS_2_DIS_BIT_BEG 14
+#define PASS_2_DIS_BIT_END 19
+
+#define PASS_3_DIS_BIT_BEG 20
+#define PASS_3_DIS_BIT_END 25
+
+#define PASS_LAST_DIS_BIT_BEG 26
+#define PASS_LAST_DIS_BIT_END 31
+
+// Set bits range [0 .. n] to 1.
+static inline unsigned getN1Bits(int N) {
+  if (N >= 31)
+    return 0xFFFFFFFF;
+  return (1 << (N + 1)) - 1;
+}
+
+#endif /* LLVM_SUPPORT_FSAFDODISCRIMINATOR_H */

llvm/lib/CodeGen/CMakeLists.txt

add_llvm_component_library(LLVMCodeGen
   ExpandPostRAPseudos.cpp
   ExpandReductions.cpp
   ExpandVectorPredication.cpp
   FaultMaps.cpp
   FEntryInserter.cpp
   FinalizeISel.cpp
   FixupStatepointCallerSaved.cpp
   FuncletLayout.cpp
+  FSAFDODiscriminator.cpp
   GCMetadata.cpp
   GCMetadataPrinter.cpp
   GCRootLowering.cpp
   GCStrategy.cpp
   GlobalMerge.cpp
   HardwareLoops.cpp
   IfConversion.cpp
   ImplicitNullChecks.cpp

llvm/lib/CodeGen/FSAFDODiscriminator.cpp

+//===-------- FSAFDODiscriminator.cpp: Flow Sensitive Discriminator--------===//
+//
+// 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 provides the implementation of a machine pass that adds the flow
+// sensitive discriminator to the instruction debug information.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/CodeGen/FSAFDODiscriminator.h"
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/DenseSet.h"
+#include "llvm/Analysis/BlockFrequencyInfoImpl.h"
+#include "llvm/IR/Function.h"
+#include "llvm/Support/CommandLine.h"
+#include "llvm/Support/Debug.h"
+#include "llvm/Support/raw_ostream.h"
+
+using namespace llvm;
+
+#define DEBUG_TYPE "fs-discriminators"
+
+char AddFSDiscriminators::ID = 0;
+
+INITIALIZE_PASS(AddFSDiscriminators, DEBUG_TYPE,
+                "Add Flow Sensitive Discriminators",
+                /* cfg = */ false, /* is_analysis = */ false)
+
+char &llvm::AddFSDiscriminatorsID = AddFSDiscriminators::ID;
+
+FunctionPass *llvm::createAddFSDiscriminatorsPass(unsigned LowBit,
+                                                  unsigned HighBit) {
+  return new AddFSDiscriminators(LowBit, HighBit);
+}
+
+// Compute a hash value using debug line number, and the line numbers from the
+// inline stack.
+static uint64_t getCallStackHash(const MachineBasicBlock &BB,
+                                 const MachineInstr &MI,
+                                 const DILocation *DIL) {
+  uint64_t Ret = MD5Hash(std::to_string(DIL->getLine()));
+  Ret ^= MD5Hash(BB.getName());
+  Ret ^= MD5Hash(DIL->getScope()->getSubprogram()->getLinkageName());
+  for (DIL = DIL->getInlinedAt(); DIL; DIL = DIL->getInlinedAt()) {
+    Ret ^= MD5Hash(std::to_string(DIL->getLine()));
+    Ret ^= MD5Hash(DIL->getScope()->getSubprogram()->getLinkageName());
+  }
+  return Ret;
+}
+
+bool AddFSDiscriminators::runOnMachineFunction(MachineFunction &MF) {
+  if (!EnableFSDiscriminator)
+    return false;
+
+  bool Changed = false;
+  using Location = std::pair<StringRef, unsigned>;
+  using LocationDiscriminator = std::pair<Location, unsigned>;
+  using BBSet = DenseSet<const MachineBasicBlock *>;
+  using LocationDiscriminatorBBMap = DenseMap<LocationDiscriminator, BBSet>;
+  using LocationDiscriminatorCurrPassMap =
+      DenseMap<LocationDiscriminator, unsigned>;
+
+  LocationDiscriminatorBBMap LDBM;
+  LocationDiscriminatorCurrPassMap LDCM;
+
+  // Mask of discriminators before this pass.
+  unsigned BitMaskBefore = getN1Bits(LowBit);
+  // Mask of discriminators including this pass.
+  unsigned BitMaskNow = getN1Bits(HighBit);
+  // Mask of discriminators for bits specific to this pass.
+  unsigned BitMaskThisPass = BitMaskNow ^ BitMaskBefore;
+  unsigned NumNewD = 0;
+
+  LLVM_DEBUG(dbgs() << "AddFSDiscriminators working on Func: "
+                    << MF.getFunction().getName() << "\n");
+  for (MachineBasicBlock &BB : MF) {
+    for (MachineInstr &I : BB) {
+      const DILocation *DIL = I.getDebugLoc().get();
+      if (!DIL)
+        continue;
+      unsigned LineNo = DIL->getLine();
+      if (LineNo == 0)
+        continue;
+      Location L = {DIL->getFilename(), LineNo};
+      unsigned Discriminator = DIL->getDiscriminator();
+      Discriminator &= BitMaskBefore;
+      LocationDiscriminator LD = {L, Discriminator};
+      auto &BBMap = LDBM[LD];
+      auto R = BBMap.insert(&BB);
+      if (BBMap.size() == 1)
+        continue;
+      unsigned DiscriminatorCurrPass;
+
+      DiscriminatorCurrPass = R.second ? ++LDCM[LD] : LDCM[LD];
+      DiscriminatorCurrPass = DiscriminatorCurrPass << LowBit;
+      DiscriminatorCurrPass += getCallStackHash(BB, I, DIL);
+      DiscriminatorCurrPass &= BitMaskThisPass;
+      unsigned NewD = Discriminator | DiscriminatorCurrPass;
+      const auto NewDIL = DIL->cloneWithDiscriminator(NewD);
+      if (!NewDIL) {
+        LLVM_DEBUG(dbgs() << "Could not encode discriminator: "
+                          << DIL->getFilename() << ":" << DIL->getLine() << ":"
+                          << DIL->getColumn() << ":" << Discriminator << " "
+                          << I << "\n");
+        continue;
+      }
+
+      I.setDebugLoc(NewDIL);
+      NumNewD++;
+      LLVM_DEBUG(dbgs() << DIL->getFilename() << ":" << DIL->getLine() << ":"
+                        << DIL->getColumn() << ": add FS discriminator, from "
+                        << Discriminator << " -> " << NewD << "\n");
+      Changed = true;
+    }
+  }
+
+  if (Changed) {
+    Module *M = MF.getFunction().getParent();
+    const char *FSDiscriminatorVar = "__llvm_fs_discriminator__";
+    if (!M->getGlobalVariable(FSDiscriminatorVar)) {
+      auto &Context = M->getContext();
+      // Create a global variable to flag that FSDiscriminators are used.
+      new GlobalVariable(*M, Type::getInt1Ty(Context), true,
+                         GlobalValue::WeakAnyLinkage,
+                         ConstantInt::getTrue(Context), FSDiscriminatorVar);
+    }
+
+    LLVM_DEBUG(dbgs() << "Num of FS Discriminators: " << NumNewD << "\n");
+  }
+
+  return Changed;
+}

llvm/lib/CodeGen/TargetPassConfig.cpp

 #include "llvm/MC/MCAsmInfo.h"
 #include "llvm/MC/MCTargetOptions.h"
 #include "llvm/Pass.h"
 #include "llvm/Support/CodeGen.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Compiler.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/ErrorHandling.h"
+#include "llvm/Support/FSAFDODiscriminator.h"
 #include "llvm/Support/SaveAndRestore.h"
 #include "llvm/Support/Threading.h"
 #include "llvm/Target/CGPassBuilderOption.h"
 #include "llvm/Target/TargetMachine.h"
 #include "llvm/Transforms/Scalar.h"
 #include "llvm/Transforms/Utils.h"
 #include "llvm/Transforms/Utils/SymbolRewriter.h"
 #include <cassert>
static cl::opt<GlobalISelAbortMode> EnableGlobalISelAbort(
     cl::desc("Enable abort calls when \"global\" instruction selection "
              "fails to lower/select an instruction"),
     cl::values(
         clEnumValN(GlobalISelAbortMode::Disable, "0", "Disable the abort"),
         clEnumValN(GlobalISelAbortMode::Enable, "1", "Enable the abort"),
         clEnumValN(GlobalISelAbortMode::DisableWithDiag, "2",
                    "Disable the abort but emit a diagnostic on failure")));
 
+// An option that disables inserting FS-AFDO discrmintators before emit.
+// This is mainly for debugging and tuning purpose.
+static cl::opt<bool>
+    FSNoFinalDiscrim("fs-no-final-discrim", cl::init(false), cl::Hidden,
+                     cl::desc("Do not insert FS-AFDO discrimnators before "
+                              "emit."));
+
 // Temporary option to allow experimenting with MachineScheduler as a post-RA
 // scheduler. Targets can "properly" enable this with
 // substitutePass(&PostRASchedulerID, &PostMachineSchedulerID).
 // Targets can return true in targetSchedulesPostRAScheduling() and
 // insert a PostRA scheduling pass wherever it wants.
 static cl::opt<bool> MISchedPostRA(
     "misched-postra", cl::Hidden,
     cl::desc(
Pass *getInsertedPass() const {
     return NP;
   }
 };
 
 } // end anonymous namespace
 
 namespace llvm {
 
+extern cl::opt<bool> EnableFSDiscriminator;
+
 class PassConfigImpl {
 public:
   // List of passes explicitly substituted by this target. Normally this is
   // empty, but it is a convenient way to suppress or replace specific passes
   // that are part of a standard pass pipeline without overridding the entire
   // pipeline. This mechanism allows target options to inherit a standard pass's
   // user interface. For example, a target may disable a standard pass by
   // default by substituting a pass ID of zero, and the user may still enable
if (getOptLevel() != CodeGenOpt::None)
     addBlockPlacement();
 
   // Insert before XRay Instrumentation.
   addPass(&FEntryInserterID);
 
   addPass(&XRayInstrumentationID);
   addPass(&PatchableFunctionID);
 
+  if (EnableFSDiscriminator && !FSNoFinalDiscrim)
+    addPass(createAddFSDiscriminatorsPass(PASS_LAST_DIS_BIT_BEG,
+                                          PASS_LAST_DIS_BIT_END));
+
   addPreEmitPass();
 
   if (TM->Options.EnableIPRA)
     // Collect register usage information and produce a register mask of
     // clobbered registers, to be used to optimize call sites.
     addPass(createRegUsageInfoCollector());
 
   // FIXME: Some backends are incompatible with running the verifier after

llvm/lib/IR/DebugInfoMetadata.cpp

 #include "llvm/IR/DIBuilder.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/Instructions.h"
 
 #include <numeric>
 
 using namespace llvm;
 
+namespace llvm {
+// Use FS-AFDO discriminator.
+cl::opt<bool> EnableFSDiscriminator(
+    "enable-fs-discriminator", cl::Hidden, cl::init(false),
+    cl::desc("Enable adding flow sensitive discriminators"));
+} // namespace llvm
+
 const DIExpression::FragmentInfo DebugVariable::DefaultFragment = {
     std::numeric_limits<uint64_t>::max(), std::numeric_limits<uint64_t>::min()};
 
 DILocation::DILocation(LLVMContext &C, StorageType Storage, unsigned Line,
                        unsigned Column, ArrayRef<Metadata *> MDs,
                        bool ImplicitCode)
     : MDNode(C, DILocationKind, Storage, MDs) {
   assert((MDs.size() == 1 || MDs.size() == 2) &&

llvm/lib/LTO/LTOBackend.cpp

static void runNewPMPasses(const Config &Conf, Module &Mod, TargetMachine *TM,
                            ModuleSummaryIndex *ExportSummary,
                            const ModuleSummaryIndex *ImportSummary) {
   Optional<PGOOptions> PGOOpt;
   if (!Conf.SampleProfile.empty())
     PGOOpt = PGOOptions(Conf.SampleProfile, "", Conf.ProfileRemapping,
                         PGOOptions::SampleUse, PGOOptions::NoCSAction, true);
   else if (Conf.RunCSIRInstr) {
     PGOOpt = PGOOptions("", Conf.CSIRProfile, Conf.ProfileRemapping,
-                        PGOOptions::IRUse, PGOOptions::CSIRInstr);
+                        PGOOptions::IRUse, PGOOptions::CSIRInstr,
+                        Conf.AddFSDiscriminator);
   } else if (!Conf.CSIRProfile.empty()) {
     PGOOpt = PGOOptions(Conf.CSIRProfile, "", Conf.ProfileRemapping,
-                        PGOOptions::IRUse, PGOOptions::CSIRUse);
+                        PGOOptions::IRUse, PGOOptions::CSIRUse,
+                        Conf.AddFSDiscriminator);
+  } else if (Conf.AddFSDiscriminator) {
+    PGOOpt = PGOOptions("", "", "", PGOOptions::NoAction,
+                        PGOOptions::NoCSAction, true);
   }
 
   LoopAnalysisManager LAM;
   FunctionAnalysisManager FAM;
   CGSCCAnalysisManager CGAM;
   ModuleAnalysisManager MAM;
 
   PassInstrumentationCallbacks PIC;

llvm/lib/Transforms/Utils/LoopUnroll.cpp

LoopUnrollResult llvm::UnrollLoop(Loop *L, UnrollLoopOptions ULO, LoopInfo *LI,
   // 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 (Header->getParent()->isDebugInfoForProfiling())
+  // When a FSDiscriminator is enabled, we don't need to add the multiply
+  // factors to the discriminators.
+  if (Header->getParent()->isDebugInfoForProfiling() && !EnableFSDiscriminator)
     for (BasicBlock *BB : L->getBlocks())
       for (Instruction &I : *BB)
         if (!isa<DbgInfoIntrinsic>(&I))
           if (const DILocation *DIL = I.getDebugLoc()) {
             auto NewDIL = DIL->cloneByMultiplyingDuplicationFactor(ULO.Count);
             if (NewDIL)
               I.setDebugLoc(NewDIL.getValue());
             else
               LLVM_DEBUG(dbgs()
                          << "Failed to create new discriminator: "
                          << DIL->getFilename() << " Line: " << DIL->getLine());
           }
 

llvm/lib/Transforms/Utils/LoopUnrollAndJam.cpp

llvm::UnrollAndJamLoop(Loop *L, unsigned Count, unsigned TripCount,
   // reverse postorder so that LastValueMap contains the correct value at each
   // exit.
   LoopBlocksDFS DFS(L);
   DFS.perform(LI);
   // Stash the DFS iterators before adding blocks to the loop.
   LoopBlocksDFS::RPOIterator BlockBegin = DFS.beginRPO();
   LoopBlocksDFS::RPOIterator BlockEnd = DFS.endRPO();
 
-  if (Header->getParent()->isDebugInfoForProfiling())
+  // When a FSDiscriminator is enabled, we don't need to add the multiply
+  // factors to the discriminators.
+  if (Header->getParent()->isDebugInfoForProfiling() && !EnableFSDiscriminator)
     for (BasicBlock *BB : L->getBlocks())
       for (Instruction &I : *BB)
         if (!isa<DbgInfoIntrinsic>(&I))
           if (const DILocation *DIL = I.getDebugLoc()) {
             auto NewDIL = DIL->cloneByMultiplyingDuplicationFactor(Count);
             if (NewDIL)
               I.setDebugLoc(NewDIL.getValue());
             else

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

static Instruction *getDebugLocFromInstOrOperands(Instruction *I) {
   }
 
   return I;
 }
 
 void InnerLoopVectorizer::setDebugLocFromInst(IRBuilder<> &B, const Value *Ptr) {
   if (const Instruction *Inst = dyn_cast_or_null<Instruction>(Ptr)) {
     const DILocation *DIL = Inst->getDebugLoc();
+
+    // When a FSDiscriminator is enabled, we don't need to add the multiply
+    // factors to the discriminators.
     if (DIL && Inst->getFunction()->isDebugInfoForProfiling() &&
-        !isa<DbgInfoIntrinsic>(Inst)) {
+        !isa<DbgInfoIntrinsic>(Inst) && !EnableFSDiscriminator) {
       assert(!VF.isScalable() && "scalable vectors not yet supported.");
       auto NewDIL =
           DIL->cloneByMultiplyingDuplicationFactor(UF * VF.getKnownMinValue());
       if (NewDIL)
         B.SetCurrentDebugLocation(NewDIL.getValue());
       else
         LLVM_DEBUG(dbgs()
                    << "Failed to create new discriminator: "
                    << DIL->getFilename() << " Line: " << DIL->getLine());
-    }
-    else
+    } else
       B.SetCurrentDebugLocation(DIL);
   } else
     B.SetCurrentDebugLocation(DebugLoc());
 }
 
 /// Write a \p DebugMsg about vectorization to the debug output stream. If \p I
 /// is passed, the message relates to that particular instruction.
 #ifndef NDEBUG

llvm/test/CodeGen/X86/fsafdo_test1.ll

+; RUN: llc -enable-fs-discriminator < %s | FileCheck %s
+;
+; Check that fs-afdo discriminators are generated.
+; CHECK: .loc    1 7 3 is_stmt 0 discriminator 2 # foo.c:7:3
+; Check: .loc    1 9 5 is_stmt 1 discriminator 2 # foo.c:9:5
+; CHECK: .loc    1 9 5 is_stmt 0 discriminator 3623878658 # foo.c:9:5
+; CHECK: .loc    1 7 3 is_stmt 1 discriminator 805306370 # foo.c:7:3
+; Check that variable __llvm_fs_discriminator__ is generated.
+; CHECK: .type   __llvm_fs_discriminator__,@object # @__llvm_fs_discriminator__
+; CHECK: .section        .rodata,"a",@progbits
+; CHECK: .weak   __llvm_fs_discriminator__
+; CHECK: __llvm_fs_discriminator__:
+; CHECK: .byte   1
+; CHECK: .size   __llvm_fs_discriminator__, 1
+
+target triple = "x86_64-unknown-linux-gnu"
+
+%struct.Node = type { %struct.Node* }
+
+define i32 @foo(%struct.Node* readonly %node, %struct.Node* readnone %root) !dbg !6 {
+entry:
+  %cmp = icmp eq %struct.Node* %node, %root, !dbg !8
+  br i1 %cmp, label %while.end4, label %while.cond1.preheader.lr.ph, !dbg !10
+
+while.cond1.preheader.lr.ph:
+  %tobool = icmp eq %struct.Node* %node, null
+  br i1 %tobool, label %while.cond1.preheader.us.preheader, label %while.body2.preheader, !dbg !11
+
+while.body2.preheader:
+  br label %while.body2, !dbg !11
+
+while.cond1.preheader.us.preheader:
+  br label %while.cond1.preheader.us, !dbg !10
+
+while.cond1.preheader.us:
+  br label %while.cond1.preheader.us, !dbg !10
+
+while.body2:
+  br label %while.body2, !dbg !11
+
+while.end4:
+  ret i32 0, !dbg !12
+}
+
+!llvm.dbg.cu = !{!0}
+!llvm.module.flags = !{!3, !4}
+
+!0 = distinct !DICompileUnit(language: DW_LANG_C99, file: !1, isOptimized: true, emissionKind: LineTablesOnly)
+!1 = !DIFile(filename: "foo.c", directory: "b/")
+!2 = !{}
+!3 = !{i32 2, !"Dwarf Version", i32 4}
+!4 = !{i32 2, !"Debug Info Version", i32 3}
+!5 = !{}
+!6 = distinct !DISubprogram(name: "foo", scope: !1, file: !1, line: 5, type: !7, isLocal: false, isDefinition: true, scopeLine: 5, flags: DIFlagPrototyped, isOptimized: true, unit: !0, retainedNodes: !2)
+!7 = !DISubroutineType(types: !2)
+!8 = !DILocation(line: 7, column: 15, scope: !9)
+!9 = !DILexicalBlockFile(scope: !6, file: !1, discriminator: 2)
+!10 = !DILocation(line: 7, column: 3, scope: !9)
+!11 = !DILocation(line: 9, column: 5, scope: !9)
+!12 = !DILocation(line: 14, column: 3, scope: !6)

llvm/test/CodeGen/X86/fsafdo_test2.ll

+; RUN: llc -enable-fs-discriminator < %s | FileCheck %s
+;;
+;; C source code for the test (compiler at -O3):
+;; // A test case for loop unroll.
+;;
+;; __attribute__((noinline)) int bar(int i){
+;;   volatile int j;
+;;   j = i;
+;;   return j;
+;; }
+;;
+;; unsigned sum;
+;; __attribute__((noinline)) void work(int i){
+;;   if (sum % 7)
+;;     sum += i;
+;;   else
+;;     sum -= i;
+;; }
+;;
+;; __attribute__((noinline)) void foo(){
+;;   int i, j;
+;;   for (j = 0; j < 48; j++)
+;;     for (i = 0; i < 4; i++) {
+;;       int ii = bar(i+j*48);
+;;       if (ii % 2)
+;;         work(ii*2);
+;;       if (ii % 4)
+;;         work(ii*3);
+;;   }
+;; }
+;;
+;; int main() {
+;;   int i;
+;;   for (i = 0; i < 10000000; i++) {
+;;     foo();
+;;   }
+;; }
+;;
+;; Check that fs-afdo discriminators are generated.
+; CHECK: .loc    1 23 9 is_stmt 0 discriminator 1 # unroll.c:23:9
+; CHECK: .loc    1 23 9 is_stmt 0 discriminator 1073741825 # unroll.c:23:9
+; CHECK: .loc    1 23 9 is_stmt 0 discriminator 2147483649 # unroll.c:23:9
+; CHECK: .loc    1 23 9 is_stmt 0 discriminator 268435457 # unroll.c:23:9
+;;
+;; Check that variable __llvm_fs_discriminator__ is generated.
+; CHECK: .type   __llvm_fs_discriminator__,@object # @__llvm_fs_discriminator__
+; CHECK: .section        .rodata,"a",@progbits
+; CHECK: .weak   __llvm_fs_discriminator__
+; CHECK: __llvm_fs_discriminator__:
+; CHECK: .byte   1
+; CHECK: .size   __llvm_fs_discriminator__, 1
+
+target triple = "x86_64-unknown-linux-gnu"
+
+@sum = dso_local local_unnamed_addr global i32 0, align 4
+
+declare i32 @bar(i32 %i) #0
+declare void @work(i32 %i) #2
+
+define dso_local void @foo() #0 !dbg !29 {
+entry:
+  br label %for.cond1.preheader, !dbg !30
+
+for.cond1.preheader:
+  %j.012 = phi i32 [ 0, %entry ], [ %inc11, %if.end9.3 ]
+  %mul = mul nuw nsw i32 %j.012, 48
+  %call = tail call i32 @bar(i32 %mul), !dbg !32
+  %0 = and i32 %call, 1, !dbg !33
+  %tobool.not = icmp eq i32 %0, 0, !dbg !33
+  br i1 %tobool.not, label %if.end, label %if.then, !dbg !35
+
+if.then:
+  %mul4 = shl nsw i32 %call, 1, !dbg !36
+  tail call void @work(i32 %mul4), !dbg !37
+  br label %if.end, !dbg !38
+
+if.end:
+  %1 = and i32 %call, 3, !dbg !39
+  %tobool6.not = icmp eq i32 %1, 0, !dbg !39
+  br i1 %tobool6.not, label %if.end9, label %if.then7, !dbg !40
+
+if.then7:
+  %mul8 = mul nsw i32 %call, 3, !dbg !41
+  tail call void @work(i32 %mul8), !dbg !42
+  br label %if.end9, !dbg !43
+
+if.end9:
+  %add.1 = or i32 %mul, 1, !dbg !44
+  %call.1 = tail call i32 @bar(i32 %add.1), !dbg !32
+  %2 = and i32 %call.1, 1, !dbg !33
+  %tobool.not.1 = icmp eq i32 %2, 0, !dbg !33
+  br i1 %tobool.not.1, label %if.end.1, label %if.then.1, !dbg !35
+
+for.end12:
+  ret void, !dbg !45
+
+if.then.1:
+  %mul4.1 = shl nsw i32 %call.1, 1, !dbg !36
+  tail call void @work(i32 %mul4.1), !dbg !37
+  br label %if.end.1, !dbg !38
+
+if.end.1:
+  %3 = and i32 %call.1, 3, !dbg !39
+  %tobool6.not.1 = icmp eq i32 %3, 0, !dbg !39
+  br i1 %tobool6.not.1, label %if.end9.1, label %if.then7.1, !dbg !40
+
+if.then7.1:
+  %mul8.1 = mul nsw i32 %call.1, 3, !dbg !41
+  tail call void @work(i32 %mul8.1), !dbg !42
+  br label %if.end9.1, !dbg !43
+
+if.end9.1:
+  %add.2 = or i32 %mul, 2, !dbg !44
+  %call.2 = tail call i32 @bar(i32 %add.2), !dbg !32
+  %4 = and i32 %call.2, 1, !dbg !33
+  %tobool.not.2 = icmp eq i32 %4, 0, !dbg !33
+  br i1 %tobool.not.2, label %if.end.2, label %if.then.2, !dbg !35
+
+if.then.2:
+  %mul4.2 = shl nsw i32 %call.2, 1, !dbg !36
+  tail call void @work(i32 %mul4.2), !dbg !37
+  br label %if.end.2, !dbg !38
+
+if.end.2:
+  %5 = and i32 %call.2, 3, !dbg !39
+  %tobool6.not.2 = icmp eq i32 %5, 0, !dbg !39
+  br i1 %tobool6.not.2, label %if.end9.2, label %if.then7.2, !dbg !40
+
+if.then7.2:
+  %mul8.2 = mul nsw i32 %call.2, 3, !dbg !41
+  tail call void @work(i32 %mul8.2), !dbg !42
+  br label %if.end9.2, !dbg !43
+
+if.end9.2:
+  %add.3 = or i32 %mul, 3, !dbg !44
+  %call.3 = tail call i32 @bar(i32 %add.3), !dbg !32
+  %6 = and i32 %call.3, 1, !dbg !33
+  %tobool.not.3 = icmp eq i32 %6, 0, !dbg !33
+  br i1 %tobool.not.3, label %if.end.3, label %if.then.3, !dbg !35
+
+if.then.3:
+  %mul4.3 = shl nsw i32 %call.3, 1, !dbg !36
+  tail call void @work(i32 %mul4.3), !dbg !37
+  br label %if.end.3, !dbg !38
+
+if.end.3:
+  %7 = and i32 %call.3, 3, !dbg !39
+  %tobool6.not.3 = icmp eq i32 %7, 0, !dbg !39
+  br i1 %tobool6.not.3, label %if.end9.3, label %if.then7.3, !dbg !40
+
+if.then7.3:
+  %mul8.3 = mul nsw i32 %call.3, 3, !dbg !41
+  tail call void @work(i32 %mul8.3), !dbg !42
+  br label %if.end9.3, !dbg !43
+
+if.end9.3:
+  %inc11 = add nuw nsw i32 %j.012, 1, !dbg !46
+  %exitcond.not = icmp eq i32 %inc11, 48, !dbg !48
+  br i1 %exitcond.not, label %for.end12, label %for.cond1.preheader, !dbg !30, !llvm.loop !49
+}
+
+
+attributes #0 = { noinline nounwind uwtable "disable-tail-calls"="false" "frame-pointer"="none" "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"="true" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+cx8,+fxsr,+mmx,+sse,+sse2,+x87" "tune-cpu"="generic" "unsafe-fp-math"="false" "use-soft-float"="false" }
+attributes #1 = { argmemonly nounwind willreturn }
+attributes #2 = { nofree noinline norecurse nounwind uwtable "disable-tail-calls"="false" "frame-pointer"="none" "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"="true" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+cx8,+fxsr,+mmx,+sse,+sse2,+x87" "tune-cpu"="generic" "unsafe-fp-math"="false" "use-soft-float"="false" }
+attributes #3 = { nounwind uwtable "disable-tail-calls"="false" "frame-pointer"="none" "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"="true" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+cx8,+fxsr,+mmx,+sse,+sse2,+x87" "tune-cpu"="generic" "unsafe-fp-math"="false" "use-soft-float"="false" }
+
+!llvm.dbg.cu = !{!0}
+!llvm.module.flags = !{!3, !4, !5}
+
+!0 = distinct !DICompileUnit(language: DW_LANG_C99, file: !1, isOptimized: true, runtimeVersion: 0, emissionKind: LineTablesOnly, enums: !2, splitDebugInlining: false, debugInfoForProfiling: true, nameTableKind: None)
+!1 = !DIFile(filename: "unroll.c", directory: "a/")
+!2 = !{}
+!3 = !{i32 7, !"Dwarf Version", i32 4}
+!4 = !{i32 2, !"Debug Info Version", i32 3}
+!5 = !{i32 1, !"wchar_size", i32 4}
+!7 = distinct !DISubprogram(name: "bar", scope: !1, file: !1, line: 3, type: !8, scopeLine: 3, flags: DIFlagPrototyped | DIFlagAllCallsDescribed, spFlags: DISPFlagDefinition | DISPFlagOptimized, unit: !0, retainedNodes: !2)
+!8 = !DISubroutineType(types: !2)
+!9 = !DILocation(line: 4, column: 3, scope: !7)
+!10 = !DILocation(line: 5, column: 5, scope: !7)
+!11 = !{!12, !12, i64 0}
+!12 = !{!"int", !13, i64 0}
+!13 = !{!"omnipotent char", !14, i64 0}
+!14 = !{!"Simple C/C++ TBAA"}
+!15 = !DILocation(line: 6, column: 10, scope: !7)
+!16 = !DILocation(line: 7, column: 1, scope: !7)
+!17 = !DILocation(line: 6, column: 3, scope: !18)
+!18 = !DILexicalBlockFile(scope: !7, file: !1, discriminator: 1)
+!19 = distinct !DISubprogram(name: "work", scope: !1, file: !1, line: 10, type: !8, scopeLine: 10, flags: DIFlagPrototyped | DIFlagAllCallsDescribed, spFlags: DISPFlagDefinition | DISPFlagOptimized, unit: !0, retainedNodes: !2)
+!20 = !DILocation(line: 11, column: 7, scope: !19)
+!21 = !DILocation(line: 11, column: 11, scope: !22)
+!22 = !DILexicalBlockFile(scope: !19, file: !1, discriminator: 1)
+!23 = !DILocation(line: 11, column: 11, scope: !24)
+!24 = !DILexicalBlockFile(scope: !19, file: !1, discriminator: 2)
+!25 = !DILocation(line: 11, column: 7, scope: !26)
+!26 = !DILexicalBlockFile(scope: !19, file: !1, discriminator: 3)
+!27 = !DILocation(line: 0, scope: !22)
+!28 = !DILocation(line: 15, column: 1, scope: !19)
+!29 = distinct !DISubprogram(name: "foo", scope: !1, file: !1, line: 17, type: !8, scopeLine: 17, flags: DIFlagAllCallsDescribed, spFlags: DISPFlagDefinition | DISPFlagOptimized, unit: !0, retainedNodes: !2)
+!30 = !DILocation(line: 19, column: 3, scope: !31)
+!31 = !DILexicalBlockFile(scope: !29, file: !1, discriminator: 2)
+!32 = !DILocation(line: 21, column: 16, scope: !31)
+!33 = !DILocation(line: 22, column: 14, scope: !34)
+!34 = !DILexicalBlockFile(scope: !29, file: !1, discriminator: 1)
+!35 = !DILocation(line: 22, column: 11, scope: !31)
+!36 = !DILocation(line: 23, column: 16, scope: !29)
+!37 = !DILocation(line: 23, column: 9, scope: !34)
+!38 = !DILocation(line: 23, column: 9, scope: !31)
+!39 = !DILocation(line: 24, column: 14, scope: !34)
+!40 = !DILocation(line: 24, column: 11, scope: !31)
+!41 = !DILocation(line: 25, column: 16, scope: !29)
+!42 = !DILocation(line: 25, column: 9, scope: !34)
+!43 = !DILocation(line: 25, column: 9, scope: !31)
+!44 = !DILocation(line: 21, column: 21, scope: !34)
+!45 = !DILocation(line: 27, column: 1, scope: !29)
+!46 = !DILocation(line: 19, column: 24, scope: !47)
+!47 = !DILexicalBlockFile(scope: !29, file: !1, discriminator: 3)
+!48 = !DILocation(line: 19, column: 17, scope: !34)
+!49 = distinct !{!49, !50, !51}
+!50 = !DILocation(line: 19, column: 3, scope: !29)
+!51 = !DILocation(line: 26, column: 3, scope: !29)
+!52 = distinct !DISubprogram(name: "main", scope: !1, file: !1, line: 29, type: !8, scopeLine: 29, flags: DIFlagAllCallsDescribed, spFlags: DISPFlagDefinition | DISPFlagOptimized, unit: !0, retainedNodes: !2)
+!53 = !DILocation(line: 31, column: 3, scope: !54)
+!54 = !DILexicalBlockFile(scope: !52, file: !1, discriminator: 2)
+!55 = !DILocation(line: 32, column: 5, scope: !52)
+!56 = !DILocation(line: 31, column: 30, scope: !57)
+!57 = !DILexicalBlockFile(scope: !52, file: !1, discriminator: 3)
+!58 = !DILocation(line: 31, column: 17, scope: !59)
+!59 = !DILexicalBlockFile(scope: !52, file: !1, discriminator: 1)
+!60 = distinct !{!60, !61, !62}
+!61 = !DILocation(line: 31, column: 3, scope: !52)
+!62 = !DILocation(line: 33, column: 3, scope: !52)
+!63 = !DILocation(line: 34, column: 1, scope: !52)

llvm/test/Transforms/SampleProfile/Inputs/fsafdo.prof

+work:33383580:1068858
+ 1: 981870
+ 5: 981870
+foo:22388581:3449
+ 0: 3449
+ 2.1: 204820
+ 4: 213086 bar:205247
+ 4.2013265920: 222893 bar:218378
+ 4.2281701376: 214552 bar:217479
+ 4.2550136832: 210692 bar:220056
+ 5: 213086
+ 5.1207959552: 210692
+ 5.1610612736: 202301
+ 5.2952790016: 222893
+ 6: 4780
+ 6.268435456: 202301 work:198259
+ 6.1073741824: 222893 work:231680
+ 6.2147483648: 4780
+ 7: 219065
+ 7.134217728: 217053
+ 7.2013265920: 183304
+ 7.3758096384: 222101
+ 8: 4780
+ 8.2818572288: 222101 work:238765
+ 8.3489660928: 183304 work:181615
+ 8.4160749568: 217053 work:218539
+ 10: 3281
+bar:7622325:861160
+ 2: 846925
+ 3: 846925
+main:16419:0
+ 0: 0
+ 2.1: 3280
+ 3: 3299 foo:3449
+ 5: 0