[RFC][SimplifyCFG] Allow target to control SpeculateOneExpensiveInst

[yonghong-song]

Summary

This RFC patch is part of effort to control code motion across
control flow boundaries in BPF. First, some use cases on why
we want to prevent speculative code motion. The patch is on
top of another patch https://reviews.llvm.org/D82112
("[RFC][BPF] Implement getUserCost() for BPFTargetTransformInfo").

Use case 1: bpf map value or some other data with a range.

data = bpf_map_lookup_elem(&map, &key);
if (!data) return 0;
payload = data->payload;
len = bpf_probe_read_kernel_str(payload, 16, &task->comm);
if (len <= 16) 
  payload += len;
...

The compiler may generate code like:

data = bpf_map_lookup_elem(&map, &key);
if (!data) return 0;
payload = data->payload;
len = bpf_probe_read_kernel_str(payload, 16, &task->comm);
new_payload = payload + len;
if (len > 16) 
  new_payload = payload
...

The "payload + len" may cause kernel verifier failure as
the "len" can be anything at this moment.

Use case 2: CO-RE relocatons

field_exist = ... 
if (field_exist) {
  offset = non-memory-access-builtin-expr1;
} else {
  offset = non-memory-access-builtin-expr2;
}   
use "offset" to read kernel memory

The compiler may generate code like:

field_exist = ... 
offset = non-memory-access-builtin-expr1;
if (!field_exist)
  offset = non-memory-access-builtin-expr2;
use "offset" to read kernel memory

This may cause failures since if field_exist is false and
libbpf is not able to perform relation
for "offset = non-memory-access-builtin-expr1".
The instruction itself will be rewritten as
an illegal instruction and this will cause
program load failures.

To address the above issues, people use

. inline assembly
. artificial complex control flow

to prevent the above optimizations.

Another BPF patch will have target specific
implementation of TTI.getUserCost() to control
the cost of code motion across control flows.

This patch mostly focused on SimplifyCFG commandline
option SpeculateOneExpensiveInst, which has default
true. We could like to disable it if a particular
BPF backend attribute is set. This patch implemented
a mechanism for backend can disallow SpeculateOneExpensiveInst.
Specifically, BPF target will disallow SpeculateOneExpensiveInst
if BPF attribute "adjustopt" is set.

[yonghong-song]

more detailed implementation in BPF backend getUserCost() implementation to fix a few kernel bpf selftests issues.

[yonghong-song]

separate BPF changes to another patch (https://reviews.llvm.org/D82112), so this patch can focus on solely the core change.

[yonghong-song]

Abandon this one. The current approach is to introduce some kind of user barriers before instcombine to prevent such optimization in IR level.

llvm/include/llvm/Analysis/TargetTransformInfo.h

 
   /// \name Vector Predication Information
   /// @{
   /// Whether the target supports the %evl parameter of VP intrinsic efficiently
   /// in hardware. (see LLVM Language Reference - "Vector Predication
   /// Intrinsics") Use of %evl is discouraged when that is not the case.
   bool hasActiveVectorLength() const;
 
+  /// \returns True if the target permits SpeculateOneExpensiveInst in
+  /// SimplifyCFG. Both this and SimplifyCFG commandline option
+  /// SpeculateOneExpensiveInst need to be True for the actual transformation
+  /// taking place.
+  bool allowSpeculateOneExpensiveInst() const;
+
   /// @}
 
   /// @}
 
 private:
   /// Estimate the latency of specified instruction.
   /// Returns 1 as the default value.
   int getInstructionLatency(const Instruction *I) const;
public:
   virtual unsigned getStoreVectorFactor(unsigned VF, unsigned StoreSize,
                                         unsigned ChainSizeInBytes,
                                         VectorType *VecTy) const = 0;
   virtual bool useReductionIntrinsic(unsigned Opcode, Type *Ty,
                                      ReductionFlags) const = 0;
   virtual bool shouldExpandReduction(const IntrinsicInst *II) const = 0;
   virtual unsigned getGISelRematGlobalCost() const = 0;
   virtual bool hasActiveVectorLength() const = 0;
+  virtual bool allowSpeculateOneExpensiveInst() const = 0;
   virtual int getInstructionLatency(const Instruction *I) = 0;
 };
 
 template <typename T>
 class TargetTransformInfo::Model final : public TargetTransformInfo::Concept {
   T Impl;
 
 public:
public:
   unsigned getGISelRematGlobalCost() const override {
     return Impl.getGISelRematGlobalCost();
   }
 
   bool hasActiveVectorLength() const override {
     return Impl.hasActiveVectorLength();
   }
 
+  bool allowSpeculateOneExpensiveInst() const override {
+    return Impl.allowSpeculateOneExpensiveInst();
+  }
+
   int getInstructionLatency(const Instruction *I) override {
     return Impl.getInstructionLatency(I);
   }
 };
 
 template <typename T>
 TargetTransformInfo::TargetTransformInfo(T Impl)
     : TTIImpl(new Model<T>(Impl)) {}

llvm/include/llvm/Analysis/TargetTransformInfoImpl.h

public:
   }
 
   bool shouldExpandReduction(const IntrinsicInst *II) const { return true; }
 
   unsigned getGISelRematGlobalCost() const { return 1; }
 
   bool hasActiveVectorLength() const { return false; }
 
+  bool allowSpeculateOneExpensiveInst() const { return true; }
+
 protected:
   // Obtain the minimum required size to hold the value (without the sign)
   // In case of a vector it returns the min required size for one element.
   unsigned minRequiredElementSize(const Value *Val, bool &isSigned) {
     if (isa<ConstantDataVector>(Val) || isa<ConstantVector>(Val)) {
       const auto *VectorValue = cast<Constant>(Val);
 
       // In case of a vector need to pick the max between the min

llvm/lib/Analysis/TargetTransformInfo.cpp

 bool TargetTransformInfo::shouldExpandReduction(const IntrinsicInst *II) const {
   return TTIImpl->shouldExpandReduction(II);
 }
 
 unsigned TargetTransformInfo::getGISelRematGlobalCost() const {
   return TTIImpl->getGISelRematGlobalCost();
 }
 
+bool TargetTransformInfo::allowSpeculateOneExpensiveInst() const {
+  return TTIImpl->allowSpeculateOneExpensiveInst();
+}
+
 int TargetTransformInfo::getInstructionLatency(const Instruction *I) const {
   return TTIImpl->getInstructionLatency(I);
 }
 
 static bool matchPairwiseShuffleMask(ShuffleVectorInst *SI, bool IsLeft,
                                      unsigned Level) {
   // We don't need a shuffle if we just want to have element 0 in position 0 of
   // the vector.

llvm/lib/Target/BPF/BPFTargetTransformInfo.h

public:
 
   unsigned getUserCost(const User *U, ArrayRef<const Value *> Operands,
                        TTI::TargetCostKind CostKind) {
     if (!ST->getHasAdjustOpt() || CostKind != TTI::TCK_SizeAndLatency)
       return BaseT::getUserCost(U, Operands, CostKind);
 
     return INT_MAX;
   }
+
+  bool allowSpeculateOneExpensiveInst() const { return !ST->getHasAdjustOpt(); }
 };
 
 } // end namespace llvm
 
 #endif // LLVM_LIB_TARGET_BPF_BPFTARGETTRANSFORMINFO_H

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

static bool DominatesMergePoint(Value *V, BasicBlock *BB,
   BudgetRemaining -= ComputeSpeculationCost(I, TTI);
 
   // Allow exactly one instruction to be speculated regardless of its cost
   // (as long as it is safe to do so).
   // This is intended to flatten the CFG even if the instruction is a division
   // or other expensive operation. The speculation of an expensive instruction
   // is expected to be undone in CodeGenPrepare if the speculation has not
   // enabled further IR optimizations.
+  bool AllowSpeculateOneExpensiveInst = SpeculateOneExpensiveInst &&
+      TTI.allowSpeculateOneExpensiveInst();
   if (BudgetRemaining < 0 &&
-      (!SpeculateOneExpensiveInst || !AggressiveInsts.empty() || Depth > 0))
+      (!AllowSpeculateOneExpensiveInst || !AggressiveInsts.empty() ||
+       Depth > 0))
     return false;
 
   // Okay, we can only really hoist these out if their operands do
   // not take us over the cost threshold.
   for (User::op_iterator i = I->op_begin(), e = I->op_end(); i != e; ++i)
     if (!DominatesMergePoint(*i, BB, AggressiveInsts, BudgetRemaining, TTI,
                              Depth + 1))
       return false;