BPF: Implement TTI.getCmpSelInstrCost() properly

[yonghong-song]

Summary

The Select insn in BPF is expensive as BPF backend
needs to resolve with conditionals. This patch set
the getCmpSelInstrCost() to SCEVCheapExpansionBudget
for Select insn to prevent some Select insn related
optimizations.

This change is motivated during bcc code review for

https://github.com/iovisor/bcc/pull/3270

where IndVarSimplifyPass eventually caused generating
the following asm code:

;       for (i = 0; (i < VIRTIO_MAX_SGS) && (i < num); i++) {
    14:       16 05 40 00 00 00 00 00 if w5 == 0 goto +64 <LBB0_6>
    15:       bc 51 00 00 00 00 00 00 w1 = w5
    16:       04 01 00 00 ff ff ff ff w1 += -1
    17:       67 05 00 00 20 00 00 00 r5 <<= 32
    18:       77 05 00 00 20 00 00 00 r5 >>= 32
    19:       a6 01 01 00 05 00 00 00 if w1 < 5 goto +1 <LBB0_4>
    20:       b7 05 00 00 06 00 00 00 r5 = 6 
00000000000000a8 <LBB0_4>:
    21:       b7 02 00 00 00 00 00 00 r2 = 0 
    22:       b7 01 00 00 00 00 00 00 r1 = 0 
;       for (i = 0; (i < VIRTIO_MAX_SGS) && (i < num); i++) {
    23:       7b 1a e0 ff 00 00 00 00 *(u64 *)(r10 - 32) = r1
    24:       7b 5a c0 ff 00 00 00 00 *(u64 *)(r10 - 64) = r5

Note that insn #15 has w1 = w5 and w1 is refined later but r5(w5) is
eventually saved on stack at insn #24 for later use. This cause
later verifier failures.

With this change, IndVarSimplifyPass won't do the above
transformation any more.

[yonghong-song]

• change Select insn cost from 4 to SCEVCheapExpansionBudget. Using SCEVCheapExpansionBudget is more adaptive in that its value is changed in the future.

[ast]

Thanks!

llvm/lib/Target/BPF/BPFTargetTransformInfo.h

 //===----------------------------------------------------------------------===//
 
 #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"
+#include "llvm/Transforms/Utils/ScalarEvolutionExpander.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()) {}
 
   int getIntImmCost(const APInt &Imm, Type *Ty, TTI::TargetCostKind CostKind) {
     if (Imm.getBitWidth() <= 64 && isInt<32>(Imm.getSExtValue()))
       return TTI::TCC_Free;
 
     return TTI::TCC_Basic;
   }
+
+  int getCmpSelInstrCost(unsigned Opcode, Type *ValTy, Type *CondTy,
+                         CmpInst::Predicate VecPred,
+                         TTI::TargetCostKind CostKind,
+                         const llvm::Instruction *I = nullptr) {
+    if (Opcode == Instruction::Select)
+      return SCEVCheapExpansionBudget;
+
+    return BaseT::getCmpSelInstrCost(Opcode, ValTy, CondTy, VecPred, CostKind,
+                                     I);
+  }
 };
 
 } // end namespace llvm
 
 #endif // LLVM_LIB_TARGET_BPF_BPFTARGETTRANSFORMINFO_H