Pipe potentially invalid InstructionCost through CodeMetrics

[reames]

Summary

Per the documentation in Support/InstructionCost.h, the purpose of an invalid cost is so that clients can change behavior on impossible to cost inputs. CodeMetrics was instead asserting that invalid costs never occurred.

On a target with an incomplete cost model - e.g. RISCV - this means that transformations would crash on (falsely) invalid constructs - e.g. scalable vectors. While we certainly should improve the cost model - and I plan to do so in the near future - we also shouldn't be crashing. This violates the explicitly stated purpose of an invalid InstructionCost.

I updated all of the "easy" consumers where bailouts were locally obvious. I plan to follow up with loop unroll in a following change.

Testing wise, I don't have a good answer. I'm about to update the RISC-V model which means that using riscv for tests won't work long term. I could in theory pick some architecture without scalable support (e.g. x86), but that seems somewhat weird. I'm tempted to just leave this untested in the patch. Thoughts?

[frasercrmck]

Thanks for the patch, @reames. I agree that invalid costs should never crash. Not just because it allows targets with incomplete models to work but there might always be something that's truly invalid for a target even with a complete model.

For testing, would we possibly be able to test scalable vectors on RISC-V without V enabled?

llvm/lib/Transforms/Scalar/LoopUnrollPass.cpp

678

gracefully

[reames]

In D127131#3562661, @frasercrmck wrote:

Thanks for the patch, @reames. I agree that invalid costs should never crash. Not just because it allows targets with incomplete models to work but there might always be something that's truly invalid for a target even with a complete model.

For testing, would we possibly be able to test scalable vectors on RISC-V without V enabled?

Good idea. I'll add some basic test coverage for the cost model printer itself with that approach. I don't plan on adding individual tests for each transform pass - mostly because figuring out to trigger each with a small test case seems quite tedious and not particularly worthwhile.

[reames]

In D127131#3563610, @reames wrote:

In D127131#3562661, @frasercrmck wrote:

Thanks for the patch, @reames. I agree that invalid costs should never crash. Not just because it allows targets with incomplete models to work but there might always be something that's truly invalid for a target even with a complete model.

For testing, would we possibly be able to test scalable vectors on RISC-V without V enabled?

Good idea. I'll add some basic test coverage for the cost model printer itself with that approach. I don't plan on adding individual tests for each transform pass - mostly because figuring out to trigger each with a small test case seems quite tedious and not particularly worthwhile.

Actually, I wasn't thinking here. We already have a CostModel test for this, the CodeMetrics layer is one level up and we don't have a dedicated printer pass for that. Given that, the only options would be a) add a printer pass, or b) exercise through one of the transforms. The only transform I'd have even a clue how to approach is rotate, so I'll start there. If that turns out not to be straight forward, I'll come back and ask for permission to land without tests. :)

[craig.topper]

llvm/lib/Transforms/Scalar/DFAJumpThreading.cpp

834

Are we using "illegal" or "invalid""? In LoopRotationUtils.cpp you used "invalid"

[reames]

llvm/lib/Transforms/Scalar/DFAJumpThreading.cpp

834

Invalid is the right term. I'll fix the others. Thanks.

[reames]

Address review comments.

[nikic]

llvm/lib/Transforms/Scalar/DFAJumpThreading.cpp

836

ConvergentInst here probably copy&paste mistake?

[reames]

llvm/lib/Transforms/Scalar/DFAJumpThreading.cpp

836

Yep, will fix.

[reames]

Since we seem to be down to type fixes, any chance I can get an LGTM? Will of course fix any typos noted before landing.

[craig.topper]

LGTM

llvm/include/llvm/Analysis/CodeMetrics.h

52

Is this field misnamed? It seems like that was already the case so I won't block the patch.

llvm/include/llvm/Analysis/CodeMetrics.h

 // the Inliner and other passes decide whether to duplicate its contents.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_ANALYSIS_CODEMETRICS_H
 #define LLVM_ANALYSIS_CODEMETRICS_H
 
 #include "llvm/ADT/DenseMap.h"
+#include "llvm/Support/InstructionCost.h"
 
 namespace llvm {
 class AssumptionCache;
 class BasicBlock;
 class Loop;
 class Function;
 template <class T> class SmallPtrSetImpl;
 class TargetTransformInfo;
struct CodeMetrics {
   bool notDuplicatable = false;
 
   /// True if this function contains a call to a convergent function.
   bool convergent = false;
 
   /// True if this function calls alloca (in the C sense).
   bool usesDynamicAlloca = false;
 
-  /// Number of instructions in the analyzed blocks.
-  unsigned NumInsts = false;
+  /// Code size cost of the analyzed blocks.
+  InstructionCost NumInsts = 0;
 
   /// Number of analyzed blocks.
   unsigned NumBlocks = false;
 
   /// Keeps track of basic block code size estimates.
-  DenseMap<const BasicBlock *, unsigned> NumBBInsts;
+  DenseMap<const BasicBlock *, InstructionCost> NumBBInsts;
 
   /// Keep track of the number of calls to 'big' functions.
   unsigned NumCalls = false;
 
   /// The number of calls to internal functions with a single caller.
   ///
   /// These are likely targets for future inlining, likely exposed by
   /// interleaved devirtualization.

llvm/lib/Analysis/CodeMetrics.cpp

 }
 
 /// Fill in the current structure with information gleaned from the specified
 /// block.
 void CodeMetrics::analyzeBasicBlock(
     const BasicBlock *BB, const TargetTransformInfo &TTI,
     const SmallPtrSetImpl<const Value *> &EphValues, bool PrepareForLTO) {
   ++NumBlocks;
-  // Use a proxy variable for NumInsts of type InstructionCost, so that it can
-  // use InstructionCost's arithmetic properties such as saturation when this
-  // feature is added to InstructionCost.
-  // When storing the value back to NumInsts, we can assume all costs are Valid
-  // because the IR should not contain any nodes that cannot be costed. If that
-  // happens the cost-model is broken.
-  InstructionCost NumInstsProxy = NumInsts;
   InstructionCost NumInstsBeforeThisBB = NumInsts;
   for (const Instruction &I : *BB) {
     // Skip ephemeral values.
     if (EphValues.count(&I))
       continue;
 
     // Special handling for calls.
     if (const auto *Call = dyn_cast<CallBase>(&I)) {
if (const CallInst *CI = dyn_cast<CallInst>(&I)) {
       if (CI->isConvergent())
         convergent = true;
     }
 
     if (const InvokeInst *InvI = dyn_cast<InvokeInst>(&I))
       if (InvI->cannotDuplicate())
         notDuplicatable = true;
 
-    NumInstsProxy += TTI.getUserCost(&I, TargetTransformInfo::TCK_CodeSize);
-    NumInsts = *NumInstsProxy.getValue();
+    NumInsts += TTI.getUserCost(&I, TargetTransformInfo::TCK_CodeSize);
   }
 
   if (isa<ReturnInst>(BB->getTerminator()))
     ++NumRets;
 
   // We never want to inline functions that contain an indirectbr.  This is
   // incorrect because all the blockaddress's (in static global initializers
   // for example) would be referring to the original function, and this indirect
   // jump would jump from the inlined copy of the function into the original
   // function which is extremely undefined behavior.
   // FIXME: This logic isn't really right; we can safely inline functions
   // with indirectbr's as long as no other function or global references the
   // blockaddress of a block within the current function.  And as a QOI issue,
   // if someone is using a blockaddress without an indirectbr, and that
   // reference somehow ends up in another function or global, we probably
   // don't want to inline this function.
   notDuplicatable |= isa<IndirectBrInst>(BB->getTerminator());
 
   // Remember NumInsts for this BB.
-  InstructionCost NumInstsThisBB = NumInstsProxy - NumInstsBeforeThisBB;
-  NumBBInsts[BB] = *NumInstsThisBB.getValue();
+  InstructionCost NumInstsThisBB = NumInsts - NumInstsBeforeThisBB;
+  NumBBInsts[BB] = NumInstsThisBB;
 }

llvm/lib/Transforms/IPO/FunctionSpecialization.cpp

private:
 
   /// Compute and return the cost of specializing function \p F.
   InstructionCost getSpecializationCost(Function *F) {
     CodeMetrics &Metrics = analyzeFunction(F);
     // If the code metrics reveal that we shouldn't duplicate the function, we
     // shouldn't specialize it. Set the specialization cost to Invalid.
     // Or if the lines of codes implies that this function is easy to get
     // inlined so that we shouldn't specialize it.
-    if (Metrics.notDuplicatable ||
+    if (Metrics.notDuplicatable || !Metrics.NumInsts.isValid() ||
         (!ForceFunctionSpecialization &&
-         Metrics.NumInsts < SmallFunctionThreshold)) {
+         *Metrics.NumInsts.getValue() < SmallFunctionThreshold)) {
       InstructionCost C{};
       C.setInvalid();
       return C;
     }
 
     // Otherwise, set the specialization cost to be the cost of all the
     // instructions in the function and penalty for specializing more functions.
     unsigned Penalty = NbFunctionsSpecialized + 1;

llvm/lib/Transforms/Scalar/DFAJumpThreading.cpp

for (ThreadingPath &TPath : SwitchPaths->getThreadingPaths()) {
         LLVM_DEBUG(dbgs() << "DFA Jump Threading: Not jump threading, contains "
                           << "convergent instructions.\n");
         ORE->emit([&]() {
           return OptimizationRemarkMissed(DEBUG_TYPE, "ConvergentInst", Switch)
                  << "Contains convergent instructions.";
         });
         return false;
       }
+
+      if (!Metrics.NumInsts.isValid()) {
+        LLVM_DEBUG(dbgs() << "DFA Jump Threading: Not jump threading, contains "
+                          << "instructions with invalid cost.\n");
+        ORE->emit([&]() {
+          return OptimizationRemarkMissed(DEBUG_TYPE, "ConvergentInst", Switch)
+                 << "Contains instructions with invalid cost.";
+        });
+        return false;
+      }
     }
 
     unsigned DuplicationCost = 0;
 
     unsigned JumpTableSize = 0;
     TTI->getEstimatedNumberOfCaseClusters(*Switch, JumpTableSize, nullptr,
                                           nullptr);
     if (JumpTableSize == 0) {
       // Factor in the number of conditional branches reduced from jump
       // threading. Assume that lowering the switch block is implemented by
       // using binary search, hence the LogBase2().
       unsigned CondBranches =
           APInt(32, Switch->getNumSuccessors()).ceilLogBase2();
-      DuplicationCost = Metrics.NumInsts / CondBranches;
+      DuplicationCost = *Metrics.NumInsts.getValue() / CondBranches;
     } else {
       // Compared with jump tables, the DFA optimizer removes an indirect branch
       // on each loop iteration, thus making branch prediction more precise. The
       // more branch targets there are, the more likely it is for the branch
       // predictor to make a mistake, and the more benefit there is in the DFA
       // optimizer. Thus, the more branch targets there are, the lower is the
       // cost of the DFA opt.
-      DuplicationCost = Metrics.NumInsts / JumpTableSize;
+      DuplicationCost = *Metrics.NumInsts.getValue() / JumpTableSize;
     }
 
     LLVM_DEBUG(dbgs() << "\nDFA Jump Threading: Cost to jump thread block "
                       << SwitchPaths->getSwitchBlock()->getName()
                       << " is: " << DuplicationCost << "\n\n");
 
     if (DuplicationCost > CostThreshold) {
       LLVM_DEBUG(dbgs() << "Not jump threading, duplication cost exceeds the "

llvm/lib/Transforms/Scalar/LoopDataPrefetch.cpp

for (auto &I : *BB) {
             HasCall = true;
         } else { // indirect call.
           HasCall = true;
         }
       }
     }
     Metrics.analyzeBasicBlock(BB, *TTI, EphValues);
   }
-  unsigned LoopSize = Metrics.NumInsts;
+
+  if (!Metrics.NumInsts.isValid())
+    return MadeChange;
+
+  unsigned LoopSize = *Metrics.NumInsts.getValue();
   if (!LoopSize)
     LoopSize = 1;
 
   unsigned ItersAhead = getPrefetchDistance() / LoopSize;
   if (!ItersAhead)
     ItersAhead = 1;
 
   if (ItersAhead > getMaxPrefetchIterationsAhead())

llvm/lib/Transforms/Scalar/LoopUnrollPass.cpp

unsigned llvm::ApproximateLoopSize(
     const SmallPtrSetImpl<const Value *> &EphValues, unsigned BEInsns) {
   CodeMetrics Metrics;
   for (BasicBlock *BB : L->blocks())
     Metrics.analyzeBasicBlock(BB, TTI, EphValues);
   NumCalls = Metrics.NumInlineCandidates;
   NotDuplicatable = Metrics.notDuplicatable;
   Convergent = Metrics.convergent;
 
-  unsigned LoopSize = Metrics.NumInsts;
+  // FIXME: This will crash for invalid InstructionCost, we should update the
+  // callers to gracefully bailout in this case.
+  unsigned LoopSize = *Metrics.NumInsts.getValue();
 
   // Don't allow an estimate of size zero.  This would allows unrolling of loops
   // with huge iteration counts, which is a compile time problem even if it's
   // not a problem for code quality. Also, the code using this size may assume
   // that each loop has at least three instructions (likely a conditional
   // branch, a comparison feeding that branch, and some kind of loop increment
   // feeding that comparison instruction).
   LoopSize = std::max(LoopSize, BEInsns + 1);

llvm/lib/Transforms/Utils/LoopRotationUtils.cpp

// duplicate blocks inside it.
         return Rotated;
       }
       if (Metrics.convergent) {
         LLVM_DEBUG(dbgs() << "LoopRotation: NOT rotating - contains convergent "
                    "instructions: ";
                    L->dump());
         return Rotated;
       }
-      if (Metrics.NumInsts > MaxHeaderSize) {
+      if (!Metrics.NumInsts.isValid()) {
+        LLVM_DEBUG(dbgs() << "LoopRotation: NOT rotating - contains instructions"
+                   " with invalid cost: ";
+                   L->dump());
+        return Rotated;
+      }
+      if (*Metrics.NumInsts.getValue() > MaxHeaderSize) {
         LLVM_DEBUG(dbgs() << "LoopRotation: NOT rotating - contains "
                           << Metrics.NumInsts
                           << " instructions, which is more than the threshold ("
                           << MaxHeaderSize << " instructions): ";
                    L->dump());
         ++NumNotRotatedDueToHeaderSize;
         return Rotated;
       }

llvm/test/Transforms/LoopRotate/RISCV/invalid-cost.ll

for.body:                                         ; preds = %for.cond
   store <vscale x 1 x i8> %b, <vscale x 1 x i8>* %p
   %inc = add nsw i32 %i.0, 1
   br label %for.cond
 
 for.end:                                          ; preds = %for.cond
   ret void
 }
 
+; This demonstrates a case where a) loop rotate needs a cost estimate to
+; know if rotation is profitable, and b) there is no cost estimate available
+; due to invalid costs in the loop.  We can't rotate this loop.
+define void @invalid_dup_required(<vscale x 1 x i8>* %p) nounwind ssp {
+; CHECK-LABEL: @invalid_dup_required(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br label [[FOR_COND:%.*]]
+; CHECK:       for.cond:
+; CHECK-NEXT:    [[I_0:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[INC:%.*]], [[FOR_BODY:%.*]] ]
+; CHECK-NEXT:    [[A:%.*]] = load <vscale x 1 x i8>, <vscale x 1 x i8>* [[P:%.*]], align 1
+; CHECK-NEXT:    [[B:%.*]] = add <vscale x 1 x i8> [[A]], [[A]]
+; CHECK-NEXT:    store <vscale x 1 x i8> [[B]], <vscale x 1 x i8>* [[P]], align 1
+; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i32 [[I_0]], 100
+; CHECK-NEXT:    br i1 [[CMP]], label [[FOR_BODY]], label [[FOR_END:%.*]]
+; CHECK:       for.body:
+; CHECK-NEXT:    call void @f()
+; CHECK-NEXT:    [[INC]] = add nsw i32 [[I_0]], 1
+; CHECK-NEXT:    br label [[FOR_COND]]
+; CHECK:       for.end:
+; CHECK-NEXT:    ret void
+;
+entry:
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.body, %entry
+  %i.0 = phi i32 [ 0, %entry ], [ %inc, %for.body ]
+  %a = load <vscale x 1 x i8>, <vscale x 1 x i8>* %p
+  %b = add <vscale x 1 x i8> %a, %a
+  store <vscale x 1 x i8> %b, <vscale x 1 x i8>* %p
+  %cmp = icmp slt i32 %i.0, 100
+  br i1 %cmp, label %for.body, label %for.end
+
+
+for.body:                                         ; preds = %for.cond
+  call void @f()
+  %inc = add nsw i32 %i.0, 1
+  br label %for.cond
+
+for.end:                                          ; preds = %for.cond
+  ret void
+}
+
+declare void @f()