[clang][Interp] Implement __builtin_strcmp

[tbaeder]

Summary

Make our Function class keep a list of parameter offsets so we can
simply get a parameter by index when evaluating builtin functions.

[aaron.ballman]

clang/lib/AST/Interp/Function.h

166–169

Nit: this interface should be taking llvm::SmallVectorImpl<Type> rather than the concrete small vector type.

clang/lib/AST/Interp/InterpBuiltin.cpp

21–22

Thought: it would be nice if we could hoist as much of this implementation as we can into a helper function so that we can share most of the guts with __builtin_memcmp() as well.

Also, it would be good to generalize this so it works for __builtin_wcscmp() and __builtin_wmemcmp() as well.

[tbaeder]

clang/lib/AST/Interp/InterpBuiltin.cpp

21–22

Definitely, but I think it makes more sense to do that when we implement those functions.

[aaron.ballman]

clang/lib/AST/Interp/InterpBuiltin.cpp

21–22

I guess I was mostly wondering why we don't generalize that now given that we know the need exists. In fact, it seems like you could be handling __builtin_strncmp and others at the same time with one generalized implementation.

[tbaeder]

clang/lib/AST/Interp/InterpBuiltin.cpp

21–22

Because smaller patches get reviewed faster :)

[aaron.ballman]

LGTM

clang/lib/AST/Interp/InterpBuiltin.cpp

21–22

LoL fair.

[shafik]

clang/test/AST/Interp/builtin-functions.cpp

9

Both empty strings "" would be good as well.

[shafik]

clang/lib/AST/Interp/ByteCodeEmitter.cpp

 using APSInt = llvm::APSInt;
 using Error = llvm::Error;
 
 Expected<Function *>
 ByteCodeEmitter::compileFunc(const FunctionDecl *FuncDecl) {
   // Set up argument indices.
   unsigned ParamOffset = 0;
   SmallVector<PrimType, 8> ParamTypes;
+  SmallVector<unsigned, 8> ParamOffsets;
   llvm::DenseMap<unsigned, Function::ParamDescriptor> ParamDescriptors;
 
   // If the return is not a primitive, a pointer to the storage where the
   // value is initialized in is passed as the first argument. See 'RVO'
   // elsewhere in the code.
   QualType Ty = FuncDecl->getReturnType();
   bool HasRVO = false;
   if (!Ty->isVoidType() && !Ctx.classify(Ty)) {
     HasRVO = true;
     ParamTypes.push_back(PT_Ptr);
+    ParamOffsets.push_back(ParamOffset);
     ParamOffset += align(primSize(PT_Ptr));
   }
 
   // If the function decl is a member decl, the next parameter is
   // the 'this' pointer. This parameter is pop()ed from the
   // InterpStack when calling the function.
   bool HasThisPointer = false;
   if (const auto *MD = dyn_cast<CXXMethodDecl>(FuncDecl)) {
     if (MD->isInstance()) {
       HasThisPointer = true;
       ParamTypes.push_back(PT_Ptr);
+      ParamOffsets.push_back(ParamOffset);
       ParamOffset += align(primSize(PT_Ptr));
     }
 
     // Set up lambda capture to closure record field mapping.
     if (isLambdaCallOperator(MD)) {
       const Record *R = P.getOrCreateRecord(MD->getParent());
       llvm::DenseMap<const ValueDecl *, FieldDecl *> LC;
       FieldDecl *LTC;
ByteCodeEmitter::compileFunc(const FunctionDecl *FuncDecl) {
 
   // Assign descriptors to all parameters.
   // Composite objects are lowered to pointers.
   for (const ParmVarDecl *PD : FuncDecl->parameters()) {
     PrimType Ty = Ctx.classify(PD->getType()).value_or(PT_Ptr);
     Descriptor *Desc = P.createDescriptor(PD, Ty);
     ParamDescriptors.insert({ParamOffset, {Ty, Desc}});
     Params.insert({PD, ParamOffset});
+    ParamOffsets.push_back(ParamOffset);
     ParamOffset += align(primSize(Ty));
     ParamTypes.push_back(Ty);
   }
 
   // Create a handle over the emitted code.
   Function *Func = P.getFunction(FuncDecl);
   if (!Func)
-    Func =
-        P.createFunction(FuncDecl, ParamOffset, std::move(ParamTypes),
-                         std::move(ParamDescriptors), HasThisPointer, HasRVO);
+    Func = P.createFunction(FuncDecl, ParamOffset, std::move(ParamTypes),
+                            std::move(ParamDescriptors),
+                            std::move(ParamOffsets), HasThisPointer, HasRVO);
 
   assert(Func);
   // For not-yet-defined functions, we only create a Function instance and
   // compile their body later.
   if (!FuncDecl->isDefined())
     return Func;
 
   // Compile the function body.

clang/lib/AST/Interp/Function.h

public:
 
   /// Checks if the function already has a body attached.
   bool hasBody() const { return HasBody; }
 
   unsigned getBuiltinID() const { return F->getBuiltinID(); }
 
   unsigned getNumParams() const { return ParamTypes.size(); }
 
+  unsigned getParamOffset(unsigned ParamIndex) const {
+    return ParamOffsets[ParamIndex];
+  }
+
 private:
   /// Construct a function representing an actual function.
   Function(Program &P, const FunctionDecl *F, unsigned ArgSize,
-           llvm::SmallVector<PrimType, 8> &&ParamTypes,
+           llvm::SmallVectorImpl<PrimType> &&ParamTypes,
            llvm::DenseMap<unsigned, ParamDescriptor> &&Params,
-           bool HasThisPointer, bool HasRVO);
+           llvm::SmallVectorImpl<unsigned> &&ParamOffsets, bool HasThisPointer,
+           bool HasRVO);
 
   /// Sets the code of a function.
   void setCode(unsigned NewFrameSize, std::vector<std::byte> &&NewCode,
                SourceMap &&NewSrcMap, llvm::SmallVector<Scope, 2> &&NewScopes,
                bool NewHasBody) {
     FrameSize = NewFrameSize;
     Code = std::move(NewCode);
     SrcMap = std::move(NewSrcMap);
private:
   /// Opcode-to-expression mapping.
   SourceMap SrcMap;
   /// List of block descriptors.
   llvm::SmallVector<Scope, 2> Scopes;
   /// List of argument types.
   llvm::SmallVector<PrimType, 8> ParamTypes;
   /// Map from byte offset to parameter descriptor.
   llvm::DenseMap<unsigned, ParamDescriptor> Params;
+  /// List of parameter offsets.
+  llvm::SmallVector<unsigned, 8> ParamOffsets;
   /// Flag to indicate if the function is valid.
   bool IsValid = false;
   /// Flag to indicate if the function is done being
   /// compiled to bytecode.
   bool IsFullyCompiled = false;
   /// Flag indicating if this function takes the this pointer
   /// as the first implicit argument
   bool HasThisPointer = false;

clang/lib/AST/Interp/Function.cpp

 #include "Opcode.h"
 #include "clang/AST/Decl.h"
 #include "clang/AST/DeclCXX.h"
 
 using namespace clang;
 using namespace clang::interp;
 
 Function::Function(Program &P, const FunctionDecl *F, unsigned ArgSize,
-                   llvm::SmallVector<PrimType, 8> &&ParamTypes,
+                   llvm::SmallVectorImpl<PrimType> &&ParamTypes,
                    llvm::DenseMap<unsigned, ParamDescriptor> &&Params,
+                   llvm::SmallVectorImpl<unsigned> &&ParamOffsets,
                    bool HasThisPointer, bool HasRVO)
     : P(P), Loc(F->getBeginLoc()), F(F), ArgSize(ArgSize),
       ParamTypes(std::move(ParamTypes)), Params(std::move(Params)),
-      HasThisPointer(HasThisPointer), HasRVO(HasRVO) {}
+      ParamOffsets(std::move(ParamOffsets)), HasThisPointer(HasThisPointer),
+      HasRVO(HasRVO) {}
 
 Function::ParamDescriptor Function::getParamDescriptor(unsigned Offset) const {
   auto It = Params.find(Offset);
   assert(It != Params.end() && "Invalid parameter offset");
   return It->second;
 }
 
 SourceInfo Function::getSource(CodePtr PC) const {

clang/lib/AST/Interp/Interp.h

 /// Checks if the result is a floating-point operation is valid
 /// in the current context.
 bool CheckFloatResult(InterpState &S, CodePtr OpPC, APFloat::opStatus Status);
 
 /// Interpreter entry point.
 bool Interpret(InterpState &S, APValue &Result);
 
 /// Interpret a builtin function.
-bool InterpretBuiltin(InterpState &S, CodePtr &PC, unsigned BuiltinID);
+bool InterpretBuiltin(InterpState &S, CodePtr OpPC, const Function *F);
 
 enum class ArithOp { Add, Sub };
 
 //===----------------------------------------------------------------------===//
 // Returning values
 //===----------------------------------------------------------------------===//
 
 template <PrimType Name, bool Builtin = false,

 }
 
 inline bool CallBI(InterpState &S, CodePtr &PC, const Function *Func) {
   auto NewFrame = std::make_unique<InterpFrame>(S, Func, PC);
 
   InterpFrame *FrameBefore = S.Current;
   S.Current = NewFrame.get();
 
-  if (InterpretBuiltin(S, PC, Func->getBuiltinID())) {
+  if (InterpretBuiltin(S, PC, Func)) {
     NewFrame.release();
     return true;
   }
   S.Current = FrameBefore;
   return false;
 }
 
 inline bool CallPtr(InterpState &S, CodePtr OpPC) {

clang/lib/AST/Interp/InterpBuiltin.cpp

 //===--- InterpBuiltin.cpp - Interpreter for the constexpr VM ---*- 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
 //
 //===----------------------------------------------------------------------===//
 #include "Boolean.h"
 #include "Interp.h"
 #include "PrimType.h"
 #include "clang/Basic/Builtins.h"
 
 namespace clang {
 namespace interp {
 
-bool InterpretBuiltin(InterpState &S, CodePtr &PC, unsigned BuiltinID) {
+template <typename T> T getParam(InterpFrame *Frame, unsigned Index) {
+  unsigned Offset = Frame->getFunction()->getParamOffset(Index);
+  return Frame->getParam<T>(Offset);
+}
+
+static bool interp__builtin_strcmp(InterpState &S, CodePtr OpPC,
+                                   InterpFrame *Frame) {
+  const Pointer &A = getParam<Pointer>(Frame, 0);
+  const Pointer &B = getParam<Pointer>(Frame, 1);
+
+  if (!CheckLive(S, OpPC, A, AK_Read) || !CheckLive(S, OpPC, B, AK_Read))
+    return false;
+
+  assert(A.getFieldDesc()->isPrimitiveArray());
+  assert(B.getFieldDesc()->isPrimitiveArray());
+
+  unsigned IndexA = A.getIndex();
+  unsigned IndexB = B.getIndex();
+  int32_t Result = 0;
+  for (;; ++IndexA, ++IndexB) {
+    const Pointer &PA = A.atIndex(IndexA);
+    const Pointer &PB = B.atIndex(IndexB);
+    if (!CheckRange(S, OpPC, PA, AK_Read) ||
+        !CheckRange(S, OpPC, PB, AK_Read)) {
+      return false;
+    }
+    uint8_t CA = PA.deref<uint8_t>();
+    uint8_t CB = PB.deref<uint8_t>();
+
+    if (CA > CB) {
+      Result = 1;
+      break;
+    } else if (CA < CB) {
+      Result = -1;
+      break;
+    }
+    if (CA == 0 || CB == 0)
+      break;
+  }
+
+  S.Stk.push<Integral<32, true>>(Integral<32, true>::from(Result));
+  return true;
+}
+
+bool InterpretBuiltin(InterpState &S, CodePtr OpPC, const Function *F) {
+  InterpFrame *Frame = S.Current;
   APValue Dummy;
 
-  switch (BuiltinID) {
+  switch (F->getBuiltinID()) {
   case Builtin::BI__builtin_is_constant_evaluated:
     S.Stk.push<Boolean>(Boolean::from(S.inConstantContext()));
-    return Ret<PT_Bool, true>(S, PC, Dummy);
+    return Ret<PT_Bool, true>(S, OpPC, Dummy);
   case Builtin::BI__builtin_assume:
-    return RetVoid<true>(S, PC, Dummy);
+    return RetVoid<true>(S, OpPC, Dummy);
+  case Builtin::BI__builtin_strcmp:
+    if (interp__builtin_strcmp(S, OpPC, Frame))
+      return Ret<PT_Sint32, true>(S, OpPC, Dummy);
+    return false;
   default:
     return false;
   }
 
   return false;
 }
 
 } // namespace interp
 } // namespace clang

clang/lib/AST/Interp/Pointer.h

if (isArrayRoot())
       return *reinterpret_cast<T *>(Pointee->rawData() + Base +
                                     sizeof(InitMap *));
 
     return *reinterpret_cast<T *>(Pointee->rawData() + Offset);
   }
 
   /// Dereferences a primitive element.
   template <typename T> T &elem(unsigned I) const {
-    return reinterpret_cast<T *>(Pointee->rawData())[I];
+    assert(I < getNumElems());
+    return reinterpret_cast<T *>(Pointee->data() + sizeof(InitMap *))[I];
   }
 
   /// Initializes a field.
   void initialize() const;
   /// Activats a field.
   void activate() const;
   /// Deactivates an entire strurcutre.
   void deactivate() const;

clang/test/AST/Interp/builtin-functions.cpp

+// RUN: %clang_cc1 -fexperimental-new-constant-interpreter %s -verify
+// RUN: %clang_cc1 -verify=ref %s -Wno-constant-evaluated
+
+namespace strcmp {
+  constexpr char kFoobar[6] = {'f','o','o','b','a','r'};
+  constexpr char kFoobazfoobar[12] = {'f','o','o','b','a','z','f','o','o','b','a','r'};
+
+  static_assert(__builtin_strcmp("", "") == 0);
+  static_assert(__builtin_strcmp("abab", "abab") == 0);
+  static_assert(__builtin_strcmp("abab", "abba") == -1);
+  static_assert(__builtin_strcmp("abab", "abaa") == 1);
+  static_assert(__builtin_strcmp("ababa", "abab") == 1);
+  static_assert(__builtin_strcmp("abab", "ababa") == -1);
+  static_assert(__builtin_strcmp("a\203", "a") == 1);
+  static_assert(__builtin_strcmp("a\203", "a\003") == 1);
+  static_assert(__builtin_strcmp("abab\0banana", "abab") == 0);
+  static_assert(__builtin_strcmp("abab", "abab\0banana") == 0);
+  static_assert(__builtin_strcmp("abab\0banana", "abab\0canada") == 0);
+  static_assert(__builtin_strcmp(0, "abab") == 0); // expected-error {{not an integral constant}} \
+                                                   // expected-note {{dereferenced null}} \
+                                                   // expected-note {{in call to}} \
+                                                   // ref-error {{not an integral constant}} \
+                                                   // ref-note {{dereferenced null}}
+  static_assert(__builtin_strcmp("abab", 0) == 0); // expected-error {{not an integral constant}} \
+                                                   // expected-note {{dereferenced null}} \
+                                                   // expected-note {{in call to}} \
+                                                   // ref-error {{not an integral constant}} \
+                                                   // ref-note {{dereferenced null}}
+
+  static_assert(__builtin_strcmp(kFoobar, kFoobazfoobar) == -1);
+  static_assert(__builtin_strcmp(kFoobar, kFoobazfoobar + 6) == 0); // expected-error {{not an integral constant}} \
+                                                                    // expected-note {{dereferenced one-past-the-end}} \
+                                                                    // expected-note {{in call to}} \
+                                                                    // ref-error {{not an integral constant}} \
+                                                                    // ref-note {{dereferenced one-past-the-end}}
+}