Teach optimizer that pthread_self does not trap. It can be speculatively executed.

[trentxintong]

Summary

Pass TargetLibraryInfo to isSafeToSpeculativelyExecute so that it can understand the behavior of known library functions.

With this patch, pthread_self is known to NOT trap, and therefore can be speculatively executed.

[trentxintong]

Adding Hal because he has been answering questions on LICM.

[joerg]

Why isn't attributing pthread_self as readonly or even readnone enough for this purpose?

[trentxintong]

Because, if pthread_self (or a function) could trap and is not guaranteed to execute. we cant pull it to the preheader. And readonly/readnone + nonunwind function does not imply the function cant trap.

The conditions for LI code to be pulled to the preheader is.

1. the operands of the instructions are invariant.
2. the results produced by the instructions are loop invariant, e.g. invariant load or calls that will return the same value everytime.
3. the instruction can be speculatively executed or is guaranteed to be executed.

Only know pthread_self is readnone+nounwind does not suffice. we need to teach the optimizer that it can not trap.

[joerg]

Well, readnone functions are safe to speculatively execute. The question is if pthread_self() does qualify for it, since strictly it does read global memory. My problem with this change is that this seems to add a very stricted form of readnone in a non-systematic and adhoc fashion.

[trentxintong]

readnone - On a function, this attribute indicates that the function computes its result (or decides to unwind an exception) based strictly on its arguments, without dereferencing any pointer arguments or otherwise accessing any mutable state ...

what if i have, this function is readnone and nounwind, but it can trap.

define int @unsafe_div(int a, int b) {

return a/b;

}

[joerg]

Your example is UB.

[trentxintong]

I, too, hope readnone+nounwind functions can be speculatively executed, but it does not seem to be the case =). Thats why i think we need to use TLI to teach the optimizer about functions which can.

[hfinkel]

In D26930#601972, @trentxintong wrote:

I, too, hope readnone+nounwind functions can be speculatively executed, but it does not seem to be the case =). Thats why i think we need to use TLI to teach the optimizer about functions which can.

In D26930#601971, @joerg wrote:

Your example is UB.

You're both right. We cannot speculate functions that might have UB. Thus, we cannot speculate general external functions (even if they're readnone, etc.). See also: D20116 where we're discussing adding a separate attribute for this.

[trentxintong]

In D26930#601975, @hfinkel wrote:

In D26930#601972, @trentxintong wrote:

I, too, hope readnone+nounwind functions can be speculatively executed, but it does not seem to be the case =). Thats why i think we need to use TLI to teach the optimizer about functions which can.

In D26930#601971, @joerg wrote:

Your example is UB.

You're both right. We cannot speculate functions that might have UB. Thus, we cannot speculate general external functions (even if they're readnone, etc.). See also: D20116 where we're discussing adding a separate attribute for this.

@hfinkel I see, do you think it would be a good to add "speculatable" attribute to pthread_self in FuncAttr once the patch for the attribute lands so that it can be hoisted ? or we can use TLI in isSafeToSpeculativelyExecute function.

[hfinkel]

In D26930#602002, @trentxintong wrote:

In D26930#601975, @hfinkel wrote:

In D26930#601972, @trentxintong wrote:

I, too, hope readnone+nounwind functions can be speculatively executed, but it does not seem to be the case =). Thats why i think we need to use TLI to teach the optimizer about functions which can.

In D26930#601971, @joerg wrote:

Your example is UB.

You're both right. We cannot speculate functions that might have UB. Thus, we cannot speculate general external functions (even if they're readnone, etc.). See also: D20116 where we're discussing adding a separate attribute for this.

@hfinkel I see, do you think it would be a good to add "speculatable" attribute to pthread_self in FuncAttr once the patch for the attribute lands so that it can be hoisted ? or we can use TLI in isSafeToSpeculativelyExecute function.

I'd prefer just to use the attribute.

[trentxintong]

In D26930#604260, @hfinkel wrote:

In D26930#602002, @trentxintong wrote:

In D26930#601975, @hfinkel wrote:

In D26930#601972, @trentxintong wrote:

I, too, hope readnone+nounwind functions can be speculatively executed, but it does not seem to be the case =). Thats why i think we need to use TLI to teach the optimizer about functions which can.

In D26930#601971, @joerg wrote:

Your example is UB.

You're both right. We cannot speculate functions that might have UB. Thus, we cannot speculate general external functions (even if they're readnone, etc.). See also: D20116 where we're discussing adding a separate attribute for this.

@hfinkel I see, do you think it would be a good to add "speculatable" attribute to pthread_self in FuncAttr once the patch for the attribute lands so that it can be hoisted ? or we can use TLI in isSafeToSpeculativelyExecute function.

I'd prefer just to use the attribute.

@hfinkel Ok, SGTM. Thanks for the pointer.

[trentxintong]

This patch needs to be completely rewritten (different approach) after the speculatable attribute lands.

include/llvm/Analysis/TargetLibraryInfo.def

 TLI_DEFINE_ENUM_INTERNAL(powl)
 TLI_DEFINE_STRING_INTERNAL("powl")
 /// ssize_t pread(int fildes, void *buf, size_t nbyte, off_t offset);
 TLI_DEFINE_ENUM_INTERNAL(pread)
 TLI_DEFINE_STRING_INTERNAL("pread")
 /// int printf(const char *format, ...);
 TLI_DEFINE_ENUM_INTERNAL(printf)
 TLI_DEFINE_STRING_INTERNAL("printf")
+/// pthread_t pthread_self(void);
+TLI_DEFINE_ENUM_INTERNAL(pthread_self)
+TLI_DEFINE_STRING_INTERNAL("pthread_self")
 /// int putc(int c, FILE *stream);
 TLI_DEFINE_ENUM_INTERNAL(putc)
 TLI_DEFINE_STRING_INTERNAL("putc")
 /// int putchar(int c);
 TLI_DEFINE_ENUM_INTERNAL(putchar)
 TLI_DEFINE_STRING_INTERNAL("putchar")
 /// int puts(const char *s);
 TLI_DEFINE_ENUM_INTERNAL(puts)

include/llvm/Analysis/ValueTracking.h

template <typename T> class ArrayRef;
   /// itself and its operands, so if this method returns true, it is safe to
   /// move the instruction as long as the correct dominance relationships for
   /// the operands and users hold.
   ///
   /// This method can return true for instructions that read memory;
   /// for such instructions, moving them may change the resulting value.
   bool isSafeToSpeculativelyExecute(const Value *V,
                                     const Instruction *CtxI = nullptr,
-                                    const DominatorTree *DT = nullptr);
+                                    const DominatorTree *DT = nullptr,
+                                    const TargetLibraryInfo *TLI = nullptr);
 
   /// Returns true if the result or effects of the given instructions \p I
   /// depend on or influence global memory.
   /// Memory dependence arises for example if the instruction reads from
   /// memory or may produce effects or undefined behaviour. Memory dependent
   /// instructions generally cannot be reorderd with respect to other memory
   /// dependent instructions or moved into non-dominated basic blocks.
   /// Instructions which just compute a value based on the values of their

include/llvm/Transforms/Utils/LoopUtils.h

 /// Returns true if the hoister and sinker can handle this instruction.
 /// If SafetyInfo is null, we are checking for sinking instructions from
 /// preheader to loop body (no speculation).
 /// If SafetyInfo is not null, we are checking for hoisting/sinking
 /// instructions from loop body to preheader/exit. Check if the instruction
 /// can execute specultatively.
 ///
 bool canSinkOrHoistInst(Instruction &I, AAResults *AA, DominatorTree *DT,
-                        Loop *CurLoop, AliasSetTracker *CurAST,
-                        LoopSafetyInfo *SafetyInfo);
+                        TargetLibraryInfo *TLI, Loop *CurLoop,
+                        AliasSetTracker *CurAST, LoopSafetyInfo *SafetyInfo);
 }
 
 #endif

lib/Analysis/TargetLibraryInfo.cpp

if (T.isOSWindows() && !T.isOSCygMing()) {
     TLI.setUnavailable(LibFunc::utimes);
     TLI.setUnavailable(LibFunc::write);
 
     // Win32 does *not* provide provide these functions, but they are
     // specified by C99:
     TLI.setUnavailable(LibFunc::atoll);
     TLI.setUnavailable(LibFunc::frexpf);
     TLI.setUnavailable(LibFunc::llabs);
+
+    // Win32 does *not* provide pthread_self.
+    TLI.setUnavailable(LibFunc::pthread_self);
   }
 
   switch (T.getOS()) {
   case Triple::MacOSX:
     // exp10 and exp10f are not available on OS X until 10.9 and iOS until 7.0
     // and their names are __exp10 and __exp10f. exp10l is not available on
     // OS X or iOS.
     TLI.setUnavailable(LibFunc::exp10l);

lib/Analysis/ValueTracking.cpp

for (const User *U : V->users()) {
 
     if (II->getIntrinsicID() != Intrinsic::lifetime_start &&
         II->getIntrinsicID() != Intrinsic::lifetime_end)
       return false;
   }
   return true;
 }
 
-bool llvm::isSafeToSpeculativelyExecute(const Value *V,
-                                        const Instruction *CtxI,
-                                        const DominatorTree *DT) {
+bool llvm::isSafeToSpeculativelyExecute(const Value *V, const Instruction *CtxI,
+                                        const DominatorTree *DT,
+                                        const TargetLibraryInfo *TLI) {
   const Operator *Inst = dyn_cast<Operator>(V);
   if (!Inst)
     return false;
 
   for (unsigned i = 0, e = Inst->getNumOperands(); i != e; ++i)
     if (Constant *C = dyn_cast<Constant>(Inst->getOperand(i)))
       if (C->canTrap())
         return false;
if (const IntrinsicInst *II = dyn_cast<IntrinsicInst>(Inst)) {
       case Intrinsic::rint:
       case Intrinsic::round:
         return true;
       // TODO: are convert_{from,to}_fp16 safe?
       // TODO: can we list target-specific intrinsics here?
       default: break;
       }
     }
+
+    // Use TargetLibraryInfo to determine whether a called function can be
+    // safely speculated.
+    if (TLI) {
+      LibFunc::Func LF;
+      const CallInst *CI = cast<CallInst>(Inst);
+      const Function *CF = CI->getCalledFunction();
+      // TODO: Add more library functions that are safe to speculate.
+      if (CF && TLI->getLibFunc(CF->getName(), LF)) {
+        // pthread_self will not trap.
+        if (LF == LibFunc::pthread_self)
+          return true;
+      }
+    }
     return false; // The called function could have undefined behavior or
                   // side-effects, even if marked readnone nounwind.
   }
   case Instruction::VAArg:
   case Instruction::Alloca:
   case Instruction::Invoke:
   case Instruction::PHI:
   case Instruction::Store:

lib/Transforms/Scalar/LICM.cpp

static bool isNotUsedInLoop(const Instruction &I, const Loop *CurLoop,
                             const LoopSafetyInfo *SafetyInfo);
 static bool hoist(Instruction &I, const DominatorTree *DT, const Loop *CurLoop,
                   const LoopSafetyInfo *SafetyInfo);
 static bool sink(Instruction &I, const LoopInfo *LI, const DominatorTree *DT,
                  const Loop *CurLoop, AliasSetTracker *CurAST,
                  const LoopSafetyInfo *SafetyInfo);
 static bool isSafeToExecuteUnconditionally(const Instruction &Inst,
                                            const DominatorTree *DT,
+                                           const TargetLibraryInfo *TLI,
                                            const Loop *CurLoop,
                                            const LoopSafetyInfo *SafetyInfo,
                                            const Instruction *CtxI = nullptr);
 static bool pointerInvalidatedByLoop(Value *V, uint64_t Size,
                                      const AAMDNodes &AAInfo,
                                      AliasSetTracker *CurAST);
 static Instruction *
 CloneInstructionInExitBlock(Instruction &I, BasicBlock &ExitBlock, PHINode &PN,
for (BasicBlock::iterator II = BB->end(); II != BB->begin();) {
     }
 
     // Check to see if we can sink this instruction to the exit blocks
     // of the loop.  We can do this if the all users of the instruction are
     // outside of the loop.  In this case, it doesn't even matter if the
     // operands of the instruction are loop invariant.
     //
     if (isNotUsedInLoop(I, CurLoop, SafetyInfo) &&
-        canSinkOrHoistInst(I, AA, DT, CurLoop, CurAST, SafetyInfo)) {
+        canSinkOrHoistInst(I, AA, DT, TLI, CurLoop, CurAST, SafetyInfo)) {
       ++II;
       Changed |= sink(I, LI, DT, CurLoop, CurAST, SafetyInfo);
     }
   }
   return Changed;
 }
 
 /// Walk the specified region of the CFG (defined by all blocks dominated by
for (BasicBlock::iterator II = BB->begin(), E = BB->end(); II != E;) {
         continue;
       }
 
       // Try hoisting the instruction out to the preheader.  We can only do this
       // if all of the operands of the instruction are loop invariant and if it
       // is safe to hoist the instruction.
       //
       if (CurLoop->hasLoopInvariantOperands(&I) &&
-          canSinkOrHoistInst(I, AA, DT, CurLoop, CurAST, SafetyInfo) &&
+          canSinkOrHoistInst(I, AA, DT, TLI, CurLoop, CurAST, SafetyInfo) &&
           isSafeToExecuteUnconditionally(
-              I, DT, CurLoop, SafetyInfo,
+              I, DT, TLI, CurLoop, SafetyInfo,
               CurLoop->getLoopPreheader()->getTerminator()))
         Changed |= hoist(I, DT, CurLoop, SafetyInfo);
     }
 
   const std::vector<DomTreeNode *> &Children = N->getChildren();
   for (DomTreeNode *Child : Children)
     Changed |= hoistRegion(Child, AA, LI, DT, TLI, CurLoop, CurAST, SafetyInfo);
   return Changed;
void llvm::computeLoopSafetyInfo(LoopSafetyInfo *SafetyInfo, Loop *CurLoop) {
   Function *Fn = CurLoop->getHeader()->getParent();
   if (Fn->hasPersonalityFn())
     if (Constant *PersonalityFn = Fn->getPersonalityFn())
       if (isFuncletEHPersonality(classifyEHPersonality(PersonalityFn)))
         SafetyInfo->BlockColors = colorEHFunclets(*Fn);
 }
 
 bool llvm::canSinkOrHoistInst(Instruction &I, AAResults *AA, DominatorTree *DT,
-                              Loop *CurLoop, AliasSetTracker *CurAST,
+                              TargetLibraryInfo *TLI, Loop *CurLoop,
+                              AliasSetTracker *CurAST,
                               LoopSafetyInfo *SafetyInfo) {
   // Loads have extra constraints we have to verify before we can hoist them.
   if (LoadInst *LI = dyn_cast<LoadInst>(&I)) {
     if (!LI->isUnordered())
       return false; // Don't hoist volatile/atomic loads!
 
     // Loads from constant memory are always safe to move, even if they end up
     // in the same alias set as something that ends up being modified.
bool llvm::canSinkOrHoistInst(Instruction &I, AAResults *AA, DominatorTree *DT,
   // SafetyInfo is nullptr if we are checking for sinking from preheader to
   // loop body. It will be always safe as there is no speculative execution.
   if (!SafetyInfo)
     return true;
 
   // TODO: Plumb the context instruction through to make hoisting and sinking
   // more powerful. Hoisting of loads already works due to the special casing
   // above.
-  return isSafeToExecuteUnconditionally(I, DT, CurLoop, SafetyInfo, nullptr);
+  return isSafeToExecuteUnconditionally(I, DT, TLI, CurLoop, SafetyInfo,
+                                        nullptr);
 }
 
 /// Returns true if a PHINode is a trivially replaceable with an
 /// Instruction.
 /// This is true when all incoming values are that instruction.
 /// This pattern occurs most often with LCSSA PHI nodes.
 ///
 static bool isTriviallyReplacablePHI(const PHINode &PN, const Instruction &I) {
static bool hoist(Instruction &I, const DominatorTree *DT, const Loop *CurLoop,
   return true;
 }
 
 /// Only sink or hoist an instruction if it is not a trapping instruction,
 /// or if the instruction is known not to trap when moved to the preheader.
 /// or if it is a trapping instruction and is guaranteed to execute.
 static bool isSafeToExecuteUnconditionally(const Instruction &Inst,
                                            const DominatorTree *DT,
+                                           const TargetLibraryInfo *TLI,
                                            const Loop *CurLoop,
                                            const LoopSafetyInfo *SafetyInfo,
                                            const Instruction *CtxI) {
-  if (isSafeToSpeculativelyExecute(&Inst, CtxI, DT))
+  if (isSafeToSpeculativelyExecute(&Inst, CtxI, DT, TLI))
     return true;
 
   return isGuaranteedToExecute(Inst, DT, CurLoop, SafetyInfo);
 }
 
 namespace {
 class LoopPromoter : public LoadAndStorePromoter {
   Value *SomePtr; // Designated pointer to store to.
for (User *U : ASIV->users()) {
       // it.
       if (const LoadInst *Load = dyn_cast<LoadInst>(UI)) {
         assert(!Load->isVolatile() && "AST broken");
         if (!Load->isSimple())
           return Changed;
 
         if (!GuaranteedToExecute && !CanSpeculateLoad)
           CanSpeculateLoad = isSafeToExecuteUnconditionally(
-              *Load, DT, CurLoop, SafetyInfo, Preheader->getTerminator());
+              *Load, DT, TLI, CurLoop, SafetyInfo, Preheader->getTerminator());
       } else if (const StoreInst *Store = dyn_cast<StoreInst>(UI)) {
         // Stores *of* the pointer are not interesting, only stores *to* the
         // pointer.
         if (UI->getOperand(1) != ASIV)
           continue;
         assert(!Store->isVolatile() && "AST broken");
         if (!Store->isSimple())
           return Changed;

lib/Transforms/Scalar/LoopSink.cpp

std::stable_sort(ColdLoopBBs.begin(), ColdLoopBBs.end(),
                    });
 
   // Traverse preheader's instructions in reverse order becaue if A depends
   // on B (A appears after B), A needs to be sinked first before B can be
   // sinked.
   for (auto II = Preheader->rbegin(), E = Preheader->rend(); II != E;) {
     Instruction *I = &*II++;
     if (!L.hasLoopInvariantOperands(I) ||
-        !canSinkOrHoistInst(*I, &AA, &DT, &L, &CurAST, nullptr))
+        !canSinkOrHoistInst(*I, &AA, &DT, nullptr, &L, &CurAST, nullptr))
       continue;
     if (sinkInstruction(L, *I, ColdLoopBBs, LoopBlockNumber, LI, DT, BFI))
       Changed = true;
   }
 
   if (Changed && SE)
     SE->forgetLoopDispositions(&L);
   return Changed;

test/Transforms/LICM/pthread.ll

+; RUN: opt < %s -S -licm | FileCheck %s
+
+; CHECK-LABEL: define void @pthread_self_safe(
+; CHECK: pthread_self()
+; CHECK: br label
+
+define void @pthread_self_safe(i32) {
+  br label %2
+
+; <label>:2:                                      ; preds = %7, %1
+  %idx = phi i32 [ 0, %1 ], [ %8, %7 ]
+  %3 = icmp slt i32 %idx, %0
+  br i1 %3, label %4, label %9
+
+; <label>:4:                                      ; preds = %2
+  call void @external_func_that_could_do_anything()
+  %5 = call i64 @pthread_self() #1
+  %6 = trunc i64 %5 to i32
+  call void @use_pthread_self(i32 %6)
+  br label %7
+
+; <label>:7:                                      ; preds = %4
+  %8 = add nsw i32 %idx, 1
+  br label %2
+
+; <label>:9:                                      ; preds = %2
+  ret void
+}
+
+; Function Attrs: nounwind readnone
+declare i64 @pthread_self() #1
+
+declare void @external_func_that_could_do_anything()
+
+declare void @use_pthread_self(i32)
+
+attributes #1 = { nounwind readnone }
+