[Instruction] Introduce a predicate mustOperandBeConstant()

[jmolloy]

Summary

Some operands to instructions may not be variables. Examples are shufflevector masks,
GEP indices when the type is a struct and extractvalue indices.

As this blacklist is difficult to get right, promote it from a SimplifyCFG helper
function into Instruction proper.

[spatel]

lib/Transforms/Utils/SimplifyCFG.cpp

1383–1385

Is this check removed intentionally? Ie, we must assume that the instruction may be malformed?

[jmolloy]

lib/Transforms/Utils/SimplifyCFG.cpp

1383–1385

I removed it because I felt that having the predicate in Instruction provide possibly different results based on the current operands would be confusing to debug.

Thinking about it though, having a predicate say "this operand must be constant" when it is currently a variable (because the predicate is being conservative) probably isn't ideal.

I'm conflicted about the right way to go here.

[spatel]

lib/Transforms/Utils/SimplifyCFG.cpp

1383–1385

The difference comes into play with intrinsics. And that's one of the motivating cases in SimplifyCFG, right?

Without the extra check, we'll say that all intrinsics require all constant argument operands, and so we won't be able to sink them using phis. If we add the check and see that the intrinsic operand is already a variable, then we may still be able to do the sinking transform on the intrinsic.

In order to keep this patch 'NFC', I'd keep the check. If we decide to change the behavior, I think it should be another patch.

Side note on intrinsic operand requirements: it seems the only place that a constant requirement is encoded/enforced is in the Verifier. Ie, it's not part of the td def itself. If that's right, that part of the Verifier should be refactored, so we can use it here and have a single point of truth for intrinsic operand const-ness.

[jmolloy]

Hi Sanjay,

That sounds good to me. This new patch has the const checking factored out of the Verifier and used in both places.

Cheers,

James

[spatel]

Grabbed the wrong diff? Phab says there were no changes from the earlier rev.

[jmolloy]

:( Evening coding never goes well for me. Here's the actual diff.

[spatel]

lib/IR/Verifier.cpp

3872–3878

Now that we have a function dedicated to verifying the constant params, shouldn't the corresponding checks in the switch below this be removed?

Either way, I think we have 2 patches in 1 at this point, so it should be split when committing into:

1. Add IntrinsicInst::mustOperandBeConstant()
2. Add Instruction::mustOperandBeConstant()

[jmolloy]

Hi Sanjay,

I agree with splitting the patches prior to commit.

I didn't remove the duplicate asserts because I thought it'd be very strange coding style to downcast and then not check the result of that downcast in a verifier, even if that is also checked elsewhere. I'm open to input on this though.

James

[spatel]

lib/IR/Verifier.cpp

3872–3877

Hmm...I'm not sure if I'm following the downcast argument. When we reach this code, we've verified that the function signature and name are ok.

1. Can we assert that this line:

if (auto *II = dyn_cast<IntrinsicInst>(IF))

cannot fail? Ie, Assert(isa<IntrinsicInst>(IF)).

2. Should we also assert that

II.getIntrinsicID() == ID

after #1?

I think that would ensure that the subsequent switch const arg checks are redundant (and therefore could be removed), or do you see some other way that we might fall through?

[majnemer]

There are more specific constraints for some intrinsics. For example, stackprotector must not have a phi or select as its operand: it must be an AllocaInst.

I wonder if the right thing to do here is have a different function (somewhere) which determines if an llvm::Value * is an appropriate operand for some llvm::User *.

lib/IR/Instruction.cpp

499–500

This will not work, Invokes are not descendants of IntrinsicInst.

lib/IR/IntrinsicInst.cpp

88–89

This seems incomplete (it is missing at least prefetch and coro_id).

lib/IR/Verifier.cpp

3872–3877

An IntrinsicInst is a descendant of CallInst but the CallSite might be an InvokeInst of an intrinsic function. IIUC, this would make it possible for the dyn_cast to fail.

[jmolloy]

Hi David,

Thanks for your comments. I'm a little wary of creating an all-singing-all-dancing version of this predicate for the same reason I don't like this patch very much - duplicating logic in the Verifier. It seems to me that such a predicate "isValueAppropriateForUser()" would replicate a lot of the Verifier logic. The Verifier would need to keep its own logic in place too as it does more stringent checks, for example recursing into dbgIntrinsics and validating metadata.

A very heavy hammer would possibly be to change the verifier to, instead of asserting on a failure, call a callback so we could call it as a predicate. But the verifier isn't really written for speed or to be used in production code.

My rationale with this patch was that, by keeping the scope of the predicate small, I could avoid duplicating as much of the verifier code as possible. I'd appreciate any advice here.

Cheers,

James

[spatel]

Abandon?
D57825 created an alternate way to specify const-ness with intrinsics.
D58233 would extend that.

include/llvm/IR/Instruction.h

public:
   /// @brief Determine if one instruction is the same operation as another.
   bool isSameOperationAs(const Instruction *I, unsigned flags = 0) const;
 
   /// Return true if there are any uses of this instruction in blocks other than
   /// the specified block. Note that PHI nodes are considered to evaluate their
   /// operands in the corresponding predecessor block.
   bool isUsedOutsideOfBlock(const BasicBlock *BB) const;
 
+  /// Return true if operand number \c OpIdx must be a Constant. If this returns
+  /// false then it is safe to replace the operand with a variable.
+  bool mustOperandBeConstant(unsigned OpIdx) const;
 
   /// Methods for support type inquiry through isa, cast, and dyn_cast:
   static inline bool classof(const Value *V) {
     return V->getValueID() >= Value::InstructionVal;
   }
 
   //----------------------------------------------------------------------
   // Exported enumerations.

include/llvm/IR/IntrinsicInst.h

 // has state or virtual methods, which is an important part of this gross/neat
 // hack working.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_IR_INTRINSICINST_H
 #define LLVM_IR_INTRINSICINST_H
 
+#include "llvm/ADT/Optional.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/Intrinsics.h"
 #include "llvm/IR/Metadata.h"
 
 namespace llvm {
   /// A wrapper class for inspecting calls to intrinsic functions.
   /// This allows the standard isa/dyncast/cast functionality to work with calls
   /// to intrinsic functions.
   class IntrinsicInst : public CallInst {
     IntrinsicInst() = delete;
     IntrinsicInst(const IntrinsicInst&) = delete;
     void operator=(const IntrinsicInst&) = delete;
   public:
     /// Return the intrinsic ID of this intrinsic.
     Intrinsic::ID getIntrinsicID() const {
       return getCalledFunction()->getIntrinsicID();
     }
 
+    /// If the given argument to this intrinsic must be a subclass of Constant,
+    /// return a string giving the reason. Otherwise return None.
+    Optional<const char*> mustOperandBeConstant(unsigned OpIdx) const;
+      
     // Methods for support type inquiry through isa, cast, and dyn_cast:
     static inline bool classof(const CallInst *I) {
       if (const Function *CF = I->getCalledFunction())
         return CF->isIntrinsic();
       return false;
     }
     static inline bool classof(const Value *V) {
       return isa<CallInst>(V) && classof(cast<CallInst>(V));

lib/IR/Instruction.cpp

 //===-- Instruction.cpp - Implement the Instruction class -----------------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 // This file implements the Instruction class for the IR library.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/IR/Instruction.h"
 #include "llvm/IR/CallSite.h"
 #include "llvm/IR/Constants.h"
+#include "llvm/IR/GetElementPtrTypeIterator.h"
 #include "llvm/IR/Instructions.h"
+#include "llvm/IR/IntrinsicInst.h"
 #include "llvm/IR/Module.h"
 #include "llvm/IR/Operator.h"
 #include "llvm/IR/Type.h"
 using namespace llvm;
 
 Instruction::Instruction(Type *ty, unsigned it, Use *Ops, unsigned NumOps,
                          Instruction *InsertBefore)
   : User(ty, Value::InstructionVal + it, Ops, NumOps), Parent(nullptr) {
for (const Use &U : uses()) {
     }
 
     if (PN->getIncomingBlock(U) != BB)
       return true;
   }
   return false;
 }
 
+bool Instruction::mustOperandBeConstant(unsigned OpIdx) const {
+  switch (getOpcode()) {
+  default:
+    return false;
+  case Instruction::Call:
+  case Instruction::Invoke:
+    if (auto *I = dyn_cast<IntrinsicInst>(this))
+      return I->mustOperandBeConstant(OpIdx) != None;
+    return false;
+  case Instruction::ShuffleVector:
+    // Shufflevector masks are constant.
+    return OpIdx == 2;
+  case Instruction::ExtractValue:
+  case Instruction::InsertValue:
+    // All operands apart from the first are constant.
+    return OpIdx != 0;
+  case Instruction::Alloca:
+    return true;
+  case Instruction::GetElementPtr:
+    if (OpIdx == 0)
+      return false;
+    gep_type_iterator It = std::next(gep_type_begin(this), OpIdx - 1);
+    return It->isStructTy();
+  }
+}
+
 /// mayReadFromMemory - Return true if this instruction may read memory.
 ///
 bool Instruction::mayReadFromMemory() const {
   switch (getOpcode()) {
   default: return false;
   case Instruction::VAArg:
   case Instruction::Load:
   case Instruction::Fence: // FIXME: refine definition of mayReadFromMemory

lib/IR/IntrinsicInst.cpp

int llvm::Intrinsic::lookupLLVMIntrinsicByName(ArrayRef<const char *> NameTable,
   if (LastLow == NameTable.end())
     return -1;
   StringRef NameFound = *LastLow;
   if (Name == NameFound ||
       (Name.startswith(NameFound) && Name[NameFound.size()] == '.'))
     return LastLow - NameTable.begin();
   return -1;
 }
+
+Optional<const char*>
+IntrinsicInst::mustOperandBeConstant(unsigned OpIdx) const {
+  switch (getIntrinsicID()) {
+  default:
+    return None;
+  case Intrinsic::ctlz:
+  case Intrinsic::cttz:
+    if (OpIdx == 1)
+      return "is_zero_undef argument of bit counting intrinsics must be a "
+             "constant int";
+    break;
+  case Intrinsic::memcpy:
+  case Intrinsic::memmove:
+  case Intrinsic::memset:
+    if (OpIdx == 3)
+      return "alignment argument of memory intrinsics must be a constant int";
+    if (OpIdx == 4)
+      return "isvolatile argument of memory intrinsics must be a constant int";
+    break;
+  case Intrinsic::gcroot:
+  case Intrinsic::gcwrite:
+  case Intrinsic::gcread:
+    if (OpIdx == 1)
+      return "llvm.gcroot parameter #2 must be a constant.";
+    break;
+  case Intrinsic::lifetime_start:
+  case Intrinsic::lifetime_end:
+  case Intrinsic::invariant_start:
+    if (OpIdx == 0)
+      return "size argument of memory use markers must be a constant integer";
+    break;
+  case Intrinsic::invariant_end:
+    if (OpIdx == 1)
+      return "llvm.invariant.end parameter #2 must be a constant integer";
+    break;
+  case Intrinsic::localrecover:
+    if (OpIdx == 2)
+      return "idx argument of llvm.localrecover must be a constant int";
+    break;
+  case Intrinsic::experimental_gc_relocate:
+    if (OpIdx == 1)
+      return "gc.relocate operand #2 must be an integer offset";
+    if (OpIdx == 2)
+      return "gc.relocate operand #3 must be an integer offset";
+    break;
+  }
+  return None;
+}

lib/IR/Verifier.cpp

          IF);
 
   // If the intrinsic takes MDNode arguments, verify that they are either global
   // or are local to *this* function.
   for (Value *V : CS.args()) 
     if (auto *MD = dyn_cast<MetadataAsValue>(V))
       visitMetadataAsValue(*MD, CS.getCaller());
 
+  if (auto *II = dyn_cast<IntrinsicInst>(IF))
+    for (unsigned OpIdx = 0; OpIdx < CS.getNumArgOperands(); ++OpIdx) {
+      auto MaybeReason = II->mustOperandBeConstant(OpIdx);
+      if (MaybeReason != None)
+        Assert(isa<ConstantInt>(CS.getArgOperand(OpIdx)), MaybeReason.getValue());
+    }
+  
   switch (ID) {
   default:
     break;
   case Intrinsic::coro_id: {
     auto *InfoArg = CS.getArgOperand(2)->stripPointerCasts();
     if (isa<ConstantPointerNull>(InfoArg))
       break;
     auto *GV = dyn_cast<GlobalVariable>(InfoArg);

lib/Transforms/Utils/SimplifyCFG.cpp

   };
   if (std::any_of(std::next(I0->getIterator()), At0, WritesMemory))
     return false;
   if (std::any_of(std::next(I1->getIterator()), At1, WritesMemory))
     return false;
   return true;
 }
 
-// Is it legal to place a variable in operand \c OpIdx of \c I?
-// FIXME: This should be promoted to Instruction.
-static bool canReplaceOperandWithVariable(const Instruction *I,
-                                          unsigned OpIdx) {
-  // Early exit.
-  if (!isa<Constant>(I->getOperand(OpIdx)))
-    return true;
-
-  switch (I->getOpcode()) {
-  default:
-    return true;
-  case Instruction::Call:
-  case Instruction::Invoke:
-    // FIXME: many arithmetic intrinsics have no issue taking a
-    // variable, however it's hard to distingish these from
-    // specials such as @llvm.frameaddress that require a constant.
-    return !isa<IntrinsicInst>(I);
-  case Instruction::ShuffleVector:
-    // Shufflevector masks are constant.
-    return OpIdx != 2;
-  case Instruction::ExtractValue:
-  case Instruction::InsertValue:
-    // All operands apart from the first are constant.
-    return OpIdx == 0;
-  case Instruction::Alloca:
-    return false;
-  case Instruction::GetElementPtr:
-    if (OpIdx == 0)
-      return true;
-    gep_type_iterator It = std::next(gep_type_begin(I), OpIdx - 1);
-    return !It->isStructTy();
-  }
-}
-
 // All blocks in Blocks unconditionally jump to a common successor. Analyze
 // the last non-terminator instruction in each block and return true if it would
 // be possible to sink them into their successor, creating one common
 // instruction instead. Set NumPHIsRequired to the number of PHI nodes that
 // would need to be created during sinking.
 static bool canSinkLastInstruction(ArrayRef<BasicBlock*> Blocks,
                                    unsigned &NumPHIsRequired) {
   SmallVector<Instruction*,4> Insts;

     if (I0->getOperand(OI)->getType()->isTokenTy())
       // Don't touch any operand of token type.
       return false;
     auto SameAsI0 = [&I0, OI](const Instruction *I) {
       return areValuesTriviallySame(I->getOperand(OI), I->getIterator(),
                                     I0->getOperand(OI), I0->getIterator());
     };
     if (!all_of(Insts, SameAsI0)) {
-      if (!canReplaceOperandWithVariable(I0, OI))
+      if (I0->mustOperandBeConstant(OI))
         // We can't create a PHI from this GEP.
         return false;
       if ((isa<CallInst>(I0) || isa<InvokeInst>(I0)) && OI != 0)
         // Don't create indirect calls!
         // FIXME: if the call was *already* indirect, we should do this.
         return false;
       ++NumPHIsRequired;
     }