Allow BB duplication threshold to be adjusted through JumpThreading's ctor

[hliao]

Summary

Some targets may not want to duplicate BB when threading jumps or use different threshold. Adding threshold parameter in that pass's ctor and initializer allows customization on BB duplication.

[spatel]

lib/Transforms/Scalar/JumpThreading.cpp

50

I have no opinion about the functionality of this patch, but how about giving a name to that magic '6'...like:

static unsigned BBDuplicateThresholdDefault = 6;

Then you can use that constant as the default parameter assignment, and you don't have to introduce yet another magic number (-1) and cast signed to unsigned.

[hliao]

PING again

lib/Transforms/Scalar/JumpThreading.cpp

50

'-1' here is used to tell whether a value other that default threshold is specified or not. However, that default threshold would be changed through command line option. Adding a name for that magic '6' and using it as default parameter does work correctly when that default threshold is changed through command option but no value is specified through pass creator.

[nadav]

The functionality of the patch looks okay. Please add a comment that says that non-negative values override the internal default.

[hfinkel]

If this is supposed to allow for target customization, should the number come from TTI? What is the underlying hardware constraint(s) you're trying to model? Also, a test case would be nice.

[nadav]

I think that he is trying to disable code duplication because GPU languages may contain barriers that must not be duplicated.

[hfinkel]

I think that he is trying to disable code duplication because GPU languages may contain barriers that must not be duplicated.

If that's the motivation, then I wonder why our "noduplicate" function attribute is not already sufficient.

[hliao]

Hi Hal

Yeah, "noduplicate" could prevent duplicating of barrier calls but that
patch wants to address the potential issue on processors with divergent
control flow, commonly found in GPUs, e.g. AMD/NVIDIA ones. The
scenario is that, if BB is duplicated to exploit more jump threading,
targets with divergent CF may execute more instructions if the
condition is a divergent one.

For updating that threshold from TTI, yeah, if we are interested in
that case. I could come another patch considering both TTI and
user-specified threshold.

Yours

• Michael

[hfinkel]

• Original Message -----

From: "Michael Liao" <[e-mail]>
To: "michael liao" <[e-mail]>, [e-mail], [e-mail]
Cc: [e-mail], [e-mail]
Sent: Monday, September 29, 2014 6:34:36 PM
Subject: Re: [PATCH] Allow BB duplication threshold to be adjusted through JumpThreading's ctor

Hi Hal

Yeah, "noduplicate" could prevent duplicating of barrier calls but
that
patch wants to address the potential issue on processors with
divergent
control flow, commonly found in GPUs, e.g. AMD/NVIDIA ones. The
scenario is that, if BB is duplicated to exploit more jump threading,
targets with divergent CF may execute more instructions if the
condition is a divergent one.

For updating that threshold from TTI, yeah, if we are interested in
that case. I could come another patch considering both TTI and
user-specified threshold.

I suppose that I don't understand what you mean by "if we are interested." Generally speaking, ctor parameters are useful only for clients who are not using the standard optimization pipeline, and we'd like the standard optimization pipeline to generally work well for a wide range of targets. Thus, a TTI interface is preferred.

From a cost modeling perspective, how can you tell whether the instruction duplication will be worthwhile. Can this be something like 2*(instruction costs) <= (branch cost)?

Thanks again,
Hal

Yours

• Michael

http://reviews.llvm.org/D5444

[hliao]

Hi Hal

[sebpop]

This patch has been committed as https://reviews.llvm.org/rL218375

include/llvm/Transforms/Scalar.h

 // JumpThreading - Thread control through mult-pred/multi-succ blocks where some
 // preds always go to some succ.
 //
-FunctionPass *createJumpThreadingPass();
+FunctionPass *createJumpThreadingPass(int Threshold = -1);
 
 //===----------------------------------------------------------------------===//
 //

lib/Transforms/Scalar/JumpThreading.cpp

 STATISTIC(NumDupes,   "Number of branch blocks duplicated to eliminate phi");
 
 static cl::opt<unsigned>
-Threshold("jump-threading-threshold",
+BBDuplicateThreshold("jump-threading-threshold",
           cl::desc("Max block size to duplicate for jump threading"),
           cl::init(6), cl::Hidden);
 

 #endif
     DenseSet<std::pair<Value*, BasicBlock*> > RecursionSet;
 
+    unsigned BBDupThreshold;
+
     // RAII helper for updating the recursion stack.
     struct RecursionSetRemover {
       DenseSet<std::pair<Value*, BasicBlock*> > &TheSet;

     };
   public:
     static char ID; // Pass identification
-    JumpThreading() : FunctionPass(ID) {
+    JumpThreading(int T = -1) : FunctionPass(ID) {
+      BBDupThreshold = (T == -1) ? BBDuplicateThreshold : unsigned(T);
       initializeJumpThreadingPass(*PassRegistry::getPassRegistry());
     }
 

                 "Jump Threading", false, false)
 
 // Public interface to the Jump Threading pass
-FunctionPass *llvm::createJumpThreadingPass() { return new JumpThreading(); }
+FunctionPass *llvm::createJumpThreadingPass(int Threshold) { return new JumpThreading(Threshold); }
 
 /// runOnFunction - Top level algorithm.
 ///

     return false;
   }
 
-  unsigned JumpThreadCost = getJumpThreadDuplicationCost(BB, Threshold);
-  if (JumpThreadCost > Threshold) {
+  unsigned JumpThreadCost = getJumpThreadDuplicationCost(BB, BBDupThreshold);
+  if (JumpThreadCost > BBDupThreshold) {
     DEBUG(dbgs() << "  Not threading BB '" << BB->getName()
           << "' - Cost is too high: " << JumpThreadCost << "\n");
     return false;

     return false;
   }
 
-  unsigned DuplicationCost = getJumpThreadDuplicationCost(BB, Threshold);
-  if (DuplicationCost > Threshold) {
+  unsigned DuplicationCost = getJumpThreadDuplicationCost(BB, BBDupThreshold);
+  if (DuplicationCost > BBDupThreshold) {
     DEBUG(dbgs() << "  Not duplicating BB '" << BB->getName()
           << "' - Cost is too high: " << DuplicationCost << "\n");
     return false;