[RFC][BPF] Implement getUserCost() for BPFTargetTransformInfo

[yonghong-song]

Summary

This patch tries to partially prevent speculative code motion for BPF.

First, some use cases on why we want to prevent speculative code motion.

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.

This patch tries to do with a more user friendly way.
BPF backend TargetTransformInfo implements getUserCost()
to return UserCost INT_MAX for TCK_SizeAndLatency
to prevent compiler moving codes speculatively.
An option "adjustopt", false by default, is added to
enable this adjustment.

[yonghong-song]

Abandon this one. The current approach is to add "user barriers" in an IR phase before simplifyCFG/instrcombine to disable unfavorable speculative code motion.

clang/lib/Basic/Targets/BPF.h

BPFTargetInfo(const llvm::Triple &Triple, const TargetOptions &)
     MaxAtomicInlineWidth = 64;
     TLSSupported = false;
   }
 
   void getTargetDefines(const LangOptions &Opts,
                         MacroBuilder &Builder) const override;
 
   bool hasFeature(StringRef Feature) const override {
-    return Feature == "bpf" || Feature == "alu32" || Feature == "dwarfris";
+    return Feature == "bpf" || Feature == "alu32" || Feature == "dwarfris" ||
+           Feature == "adjustopt";
   }
 
   void setFeatureEnabled(llvm::StringMap<bool> &Features, StringRef Name,
                          bool Enabled) const override {
     Features[Name] = Enabled;
   }
 
   ArrayRef<Builtin::Info> getTargetBuiltins() const override;

llvm/lib/Target/BPF/BPF.td

def DummyFeature : SubtargetFeature<"dummy", "isDummyMode",
                                     "true", "unused feature">;
 
 def ALU32 : SubtargetFeature<"alu32", "HasAlu32", "true",
                              "Enable ALU32 instructions">;
 
 def DwarfRIS: SubtargetFeature<"dwarfris", "UseDwarfRIS", "true",
                                "Disable MCAsmInfo DwarfUsesRelocationsAcrossSections">;
 
+def AdjustOpt : SubtargetFeature<"adjustopt", "HasAdjustOpt", "true",
+                                 "Adjust Optimizations for Verifier Friendly Code">;
+
 def BPFInstPrinter : AsmWriter {
   string AsmWriterClassName  = "InstPrinter";
   bit isMCAsmWriter = 1;
 }
 
 def BPFAsmParser : AsmParser {
   bit HasMnemonicFirst = 0;
 }

llvm/lib/Target/BPF/BPFSubtarget.h

protected:
   bool HasJmp32;
 
   // whether the cpu supports alu32 instructions.
   bool HasAlu32;
 
   // whether we should enable MCAsmInfo DwarfUsesRelocationsAcrossSections
   bool UseDwarfRIS;
 
+  // whether to adjust optimization for verifier friendly codes
+  bool HasAdjustOpt;
+
 public:
   // This constructor initializes the data members to match that
   // of the specified triple.
   BPFSubtarget(const Triple &TT, const std::string &CPU, const std::string &FS,
                const TargetMachine &TM);
 
   BPFSubtarget &initializeSubtargetDependencies(StringRef CPU, StringRef FS);
 
   // ParseSubtargetFeatures - Parses features string setting specified
   // subtarget options.  Definition of function is auto generated by tblgen.
   void ParseSubtargetFeatures(StringRef CPU, StringRef FS);
   bool getHasJmpExt() const { return HasJmpExt; }
   bool getHasJmp32() const { return HasJmp32; }
   bool getHasAlu32() const { return HasAlu32; }
   bool getUseDwarfRIS() const { return UseDwarfRIS; }
+  bool getHasAdjustOpt() const { return HasAdjustOpt; }
 
   const BPFInstrInfo *getInstrInfo() const override { return &InstrInfo; }
   const BPFFrameLowering *getFrameLowering() const override {
     return &FrameLowering;
   }
   const BPFTargetLowering *getTargetLowering() const override {
     return &TLInfo;
   }

llvm/lib/Target/BPF/BPFSubtarget.cpp

BPFSubtarget &BPFSubtarget::initializeSubtargetDependencies(StringRef CPU,
   return *this;
 }
 
 void BPFSubtarget::initializeEnvironment() {
   HasJmpExt = false;
   HasJmp32 = false;
   HasAlu32 = false;
   UseDwarfRIS = false;
+  HasAdjustOpt = false;
 }
 
 void BPFSubtarget::initSubtargetFeatures(StringRef CPU, StringRef FS) {
   if (CPU == "probe")
     CPU = sys::detail::getHostCPUNameForBPF();
   if (CPU == "generic" || CPU == "v1")
     return;
   if (CPU == "v2") {

llvm/lib/Target/BPF/BPFTargetMachine.h

public:
 
   const BPFSubtarget *getSubtargetImpl() const { return &Subtarget; }
   const BPFSubtarget *getSubtargetImpl(const Function &) const override {
     return &Subtarget;
   }
 
   TargetPassConfig *createPassConfig(PassManagerBase &PM) override;
 
+  TargetTransformInfo getTargetTransformInfo(const Function &F) override;
+
   TargetLoweringObjectFile *getObjFileLowering() const override {
     return TLOF.get();
   }
 };
 }
 
 #endif

llvm/lib/Target/BPF/BPFTargetMachine.cpp

 //===-- BPFTargetMachine.cpp - Define TargetMachine for BPF ---------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
 // Implements the info about BPF target spec.
 //
 //===----------------------------------------------------------------------===//
 
 #include "BPFTargetMachine.h"
 #include "BPF.h"
+#include "BPFTargetTransformInfo.h"
 #include "MCTargetDesc/BPFMCAsmInfo.h"
 #include "TargetInfo/BPFTargetInfo.h"
+#include "llvm/Analysis/TargetTransformInfo.h"
+#include "llvm/CodeGen/BasicTTIImpl.h"
 #include "llvm/CodeGen/Passes.h"
 #include "llvm/CodeGen/TargetLoweringObjectFileImpl.h"
 #include "llvm/CodeGen/TargetPassConfig.h"
 #include "llvm/IR/LegacyPassManager.h"
 #include "llvm/Support/FormattedStream.h"
 #include "llvm/Support/TargetRegistry.h"
 #include "llvm/Target/TargetOptions.h"
 using namespace llvm;
public:
   void addPreEmitPass() override;
 };
 }
 
 TargetPassConfig *BPFTargetMachine::createPassConfig(PassManagerBase &PM) {
   return new BPFPassConfig(*this, PM);
 }
 
+TargetTransformInfo
+BPFTargetMachine::getTargetTransformInfo(const Function &F) {
+  return TargetTransformInfo(BPFTTIImpl(this, F));
+}
+
 void BPFPassConfig::addIRPasses() {
 
   addPass(createBPFAdjustOpt());
   addPass(createBPFAbstractMemberAccess(&getBPFTargetMachine()));
   addPass(createBPFPreserveDIType());
 
   TargetPassConfig::addIRPasses();
 }

llvm/lib/Target/BPF/BPFTargetTransformInfo.h

+//===------ BPFTargetTransformInfo.h - BPF specific TTI ---------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// This file a TargetTransformInfo::Concept conforming object specific to the
+// BPF target machine. It uses the target's detailed information to
+// provide more precise answers to certain TTI queries, while letting the
+// target independent and default TTI implementations handle the rest.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_LIB_TARGET_BPF_BPFTARGETTRANSFORMINFO_H
+#define LLVM_LIB_TARGET_BPF_BPFTARGETTRANSFORMINFO_H
+
+#include "BPFTargetMachine.h"
+#include "llvm/Analysis/TargetTransformInfo.h"
+#include "llvm/CodeGen/BasicTTIImpl.h"
+
+namespace llvm {
+class BPFTTIImpl : public BasicTTIImplBase<BPFTTIImpl> {
+  typedef BasicTTIImplBase<BPFTTIImpl> BaseT;
+  typedef TargetTransformInfo TTI;
+  friend BaseT;
+
+  const BPFSubtarget *ST;
+  const BPFTargetLowering *TLI;
+
+  const BPFSubtarget *getST() const { return ST; }
+  const BPFTargetLowering *getTLI() const { return TLI; }
+
+public:
+  explicit BPFTTIImpl(const BPFTargetMachine *TM, const Function &F)
+      : BaseT(TM, F.getParent()->getDataLayout()), ST(TM->getSubtargetImpl(F)),
+        TLI(ST->getTargetLowering()) {}
+
+  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;
+  }
+};
+
+} // end namespace llvm
+
+#endif // LLVM_LIB_TARGET_BPF_BPFTARGETTRANSFORMINFO_H