OmniSciDB  ca0c39ec8f
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
ResultSetReductionOps.h
Go to the documentation of this file.
1 /*
2  * Copyright 2022 HEAVY.AI, Inc.
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at
7  *
8  * http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */
16 
17 #pragma once
18 
19 #include <Logger/Logger.h>
20 
21 #include <memory>
22 #include <string>
23 #include <vector>
24 
25 extern thread_local size_t g_value_id;
26 
27 // A collection of operators heavily inspired from LLVM IR which are both easy to
28 // translated to LLVM IR and interpreted, for small result sets, to avoid compilation
29 // overhead. In order to keep things simple, there is no general-purpose control flow.
30 // Instead, there is ReturnEarly for early return from a function based on a logical
31 // condition and For, which iterates between a start and an index and executes the body.
32 
33 enum class Type {
34  Int1,
35  Int8,
36  Int32,
37  Int64,
38  Float,
39  Double,
40  Void,
41  Int8Ptr,
42  Int32Ptr,
43  Int64Ptr,
44  FloatPtr,
45  DoublePtr,
46  VoidPtr,
48 };
49 
50 inline std::ostream& operator<<(std::ostream& os, const Type& type) {
51  switch (type) {
52  case Type::Int1: {
53  os << "Int1";
54  break;
55  }
56  case Type::Int8: {
57  os << "Int8";
58  break;
59  }
60  case Type::Int32: {
61  os << "Int32";
62  break;
63  }
64  case Type::Int64: {
65  os << "Int64";
66  break;
67  }
68  case Type::Float: {
69  os << "Float";
70  break;
71  }
72  case Type::Double: {
73  os << "Double";
74  break;
75  }
76  case Type::Void: {
77  os << "Void";
78  break;
79  }
80  case Type::Int8Ptr: {
81  os << "Int8Ptr";
82  break;
83  }
84  case Type::Int32Ptr: {
85  os << "Int32Ptr";
86  break;
87  }
88  case Type::Int64Ptr: {
89  os << "Int64Ptr";
90  break;
91  }
92  case Type::FloatPtr: {
93  os << "FloatPtr";
94  break;
95  }
96  case Type::DoublePtr: {
97  os << "DoublePtr";
98  break;
99  }
100  case Type::VoidPtr: {
101  os << "VoidPtr";
102  break;
103  }
104  case Type::Int64PtrPtr: {
105  os << "Int64PtrPtr";
106  break;
107  }
108  }
109  return os;
110 }
111 
112 inline std::ostream& operator<<(std::ostream& os, const std::vector<Type>& types) {
113  os << "(";
114  for (const Type& type : types) {
115  os << type << ", ";
116  }
117  os << ")";
118  return os;
119 }
120 
121 // Retrieves the type a pointer type points to.
122 inline Type pointee_type(const Type pointer) {
123  switch (pointer) {
124  case Type::Int8Ptr: {
125  return Type::Int8;
126  }
127  case Type::Int32Ptr: {
128  return Type::Int32;
129  }
130  case Type::Int64Ptr: {
131  return Type::Int64;
132  }
133  case Type::FloatPtr: {
134  return Type::Float;
135  }
136  case Type::DoublePtr: {
137  return Type::Double;
138  }
139  case Type::Int64PtrPtr: {
140  return Type::Int64Ptr;
141  }
142  default: {
143  LOG(FATAL) << "Invalid pointer type: " << static_cast<int>(pointer);
144  }
145  }
146  return Type::Void;
147 }
148 
149 // Creates a pointer type from the given type.
150 inline Type pointer_type(const Type pointee) {
151  switch (pointee) {
152  case Type::Int8: {
153  return Type::Int8Ptr;
154  }
155  case Type::Int64: {
156  return Type::Int64Ptr;
157  }
158  case Type::Int64Ptr: {
159  return Type::Int64PtrPtr;
160  }
161  default: {
162  LOG(FATAL) << "Invalid pointee type: " << static_cast<int>(pointee);
163  }
164  }
165  return Type::Void;
166 }
167 
168 class Value {
169  public:
170  Value(const Type type, const std::string& label)
171  : type_(type), label_(label), id_(g_value_id++) {}
172 
173  Type type() const { return type_; }
174 
175  size_t id() const { return id_; }
176 
177  const std::string& label() const { return label_; }
178 
179  virtual ~Value() = default;
180 
181  private:
182  const Type type_;
183  // The label of the value, useful for debugging the generated LLVM IR.
184  const std::string label_;
185  // An unique id, starting from 0, relative to the function. Used by the interpreter to
186  // implement a dense map of evaluated values.
187  const size_t id_;
188 };
189 
190 class Constant : public Value {
191  public:
192  Constant(const Type type) : Value(type, "") {}
193 };
194 
195 class ConstantInt : public Constant {
196  public:
197  ConstantInt(const int64_t value, const Type target) : Constant(target), value_(value) {}
198 
199  int64_t value() const { return value_; }
200 
201  private:
202  const int64_t value_;
203 };
204 
205 class ConstantFP : public Constant {
206  public:
207  ConstantFP(const double value, const Type target) : Constant(target), value_(value) {}
208 
209  double value() const { return value_; }
210 
211  private:
212  const double value_;
213 };
214 
215 class Argument : public Value {
216  public:
217  Argument(const Type type, const std::string& label) : Value(type, label) {}
218 };
219 
221 
222 class Instruction : public Value {
223  public:
224  Instruction(const Type type, const std::string& label) : Value(type, label) {}
225 
226  // Run the instruction in the given interpreter.
227  virtual void run(ReductionInterpreterImpl* interpreter) = 0;
228 };
229 
230 // A function, defined by its signature and instructions, which it owns.
231 class Function {
232  public:
233  struct NamedArg {
234  std::string name;
236  };
237 
238  Function(const std::string name,
239  const std::vector<NamedArg>& arg_types,
240  const Type ret_type,
241  const bool always_inline)
242  : name_(name)
243  , arg_types_(arg_types)
244  , ret_type_(ret_type)
245  , always_inline_(always_inline) {
246  g_value_id = 0;
247  for (const auto& named_arg : arg_types_) {
248  arguments_.emplace_back(new Argument(named_arg.type, named_arg.name));
249  }
250  }
251 
252  const std::string& name() const { return name_; }
253 
254  const std::vector<NamedArg>& arg_types() const { return arg_types_; }
255 
256  Argument* arg(const size_t idx) const { return arguments_[idx].get(); }
257 
258  Type ret_type() const { return ret_type_; }
259 
260  const std::vector<std::unique_ptr<Instruction>>& body() const { return body_; }
261 
262  const std::vector<std::unique_ptr<Constant>>& constants() const { return constants_; }
263 
264  bool always_inline() const { return always_inline_; }
265 
266  template <typename Tp, typename... Args>
267  Value* add(Args&&... args) {
268  body_.emplace_back(new Tp(std::forward<Args>(args)...));
269  return body_.back().get();
270  }
271 
272  template <typename Tp, typename... Args>
273  Value* addConstant(Args&&... args) {
274  constants_.emplace_back(new Tp(std::forward<Args>(args)...));
275  return constants_.back().get();
276  }
277 
278  private:
279  const std::string name_;
280  const std::vector<NamedArg> arg_types_;
282  std::vector<std::unique_ptr<Instruction>> body_;
283  const bool always_inline_;
284  std::vector<std::unique_ptr<Argument>> arguments_;
285  std::vector<std::unique_ptr<Constant>> constants_;
286 };
287 
288 class GetElementPtr : public Instruction {
289  public:
290  GetElementPtr(const Value* base, const Value* index, const std::string& label)
291  : Instruction(base->type(), label), base_(base), index_(index) {}
292 
293  const Value* base() const { return base_; }
294 
295  const Value* index() const { return index_; }
296 
297  void run(ReductionInterpreterImpl* interpreter) override;
298 
299  private:
300  const Value* base_;
301  const Value* index_;
302 };
303 
304 class Load : public Instruction {
305  public:
306  Load(const Value* source, const std::string& label)
307  : Instruction(pointee_type(source->type()), label), source_(source) {}
308 
309  const Value* source() const { return source_; }
310 
311  void run(ReductionInterpreterImpl* interpreter) override;
312 
313  private:
314  const Value* source_;
315 };
316 
317 class ICmp : public Instruction {
318  public:
319  enum class Predicate {
320  NE,
321  EQ,
322  };
323 
325  const Value* lhs,
326  const Value* rhs,
327  const std::string& label)
328  : Instruction(Type::Int1, label), predicate_(predicate), lhs_(lhs), rhs_(rhs) {}
329 
330  Predicate predicate() const { return predicate_; }
331 
332  const Value* lhs() const { return lhs_; }
333 
334  const Value* rhs() const { return rhs_; }
335 
336  void run(ReductionInterpreterImpl* interpreter) override;
337 
338  private:
340  const Value* lhs_;
341  const Value* rhs_;
342 };
343 
344 class BinaryOperator : public Instruction {
345  public:
346  enum class BinaryOp {
347  Add,
348  Mul,
349  };
350 
352  const Value* lhs,
353  const Value* rhs,
354  const std::string& label)
355  : Instruction(Type::Int1, label), op_(op), lhs_(lhs), rhs_(rhs) {}
356 
357  BinaryOp op() const { return op_; }
358 
359  const Value* lhs() const { return lhs_; }
360 
361  const Value* rhs() const { return rhs_; }
362 
363  void run(ReductionInterpreterImpl* interpreter) override;
364 
365  private:
366  const BinaryOp op_;
367  const Value* lhs_;
368  const Value* rhs_;
369 };
370 
371 class Cast : public Instruction {
372  public:
373  enum class CastOp {
374  Trunc,
375  SExt,
376  BitCast,
377  };
378 
379  Cast(const CastOp op, const Value* source, const Type type, const std::string& label)
380  : Instruction(type, label), op_(op), source_(source) {}
381 
382  CastOp op() const { return op_; }
383 
384  const Value* source() const { return source_; }
385 
386  void run(ReductionInterpreterImpl* interpreter) override;
387 
388  private:
389  const CastOp op_;
390  const Value* source_;
391 };
392 
393 class Ret : public Instruction {
394  public:
395  Ret(const Value* value) : Instruction(value->type(), ""), value_(value) {}
396 
397  Ret() : Instruction(Type::Void, ""), value_(nullptr) {}
398 
399  const Value* value() const { return value_; }
400 
401  void run(ReductionInterpreterImpl* interpreter) override;
402 
403  private:
404  const Value* value_;
405 };
406 
407 // An internal runtime function. In this context, internal means either part of the
408 // bitcode runtime (given by name) or one of the reduction functions.
409 class Call : public Instruction {
410  public:
412  const std::vector<const Value*>& arguments,
413  const std::string& label)
414  : Instruction(callee->ret_type(), label)
415  , callee_(callee)
416  , arguments_(arguments)
417  , cached_callee_(nullptr) {}
418 
419  Call(const std::string& callee_name,
420  const std::vector<const Value*>& arguments,
421  const std::string& label)
422  : Instruction(Type::Void, label)
423  , callee_name_(callee_name)
424  , callee_(nullptr)
425  , arguments_(arguments)
426  , cached_callee_(nullptr) {}
427 
428  Call(const std::string& callee_name,
429  const Type returnType,
430  const std::vector<const Value*>& arguments,
431  const std::string& label)
432  : Instruction(returnType, label)
433  , callee_name_(callee_name)
434  , callee_(nullptr)
435  , arguments_(arguments)
436  , cached_callee_(nullptr) {}
437 
438  bool external() const { return false; }
439 
440  const std::string& callee_name() const { return callee_name_; }
441 
442  const Function* callee() const { return callee_; }
443 
444  const std::vector<const Value*>& arguments() const { return arguments_; }
445 
446  void run(ReductionInterpreterImpl* interpreter) override;
447 
448  void* cached_callee() const { return cached_callee_; }
449 
451 
452  private:
453  const std::string callee_name_;
455  const std::vector<const Value*> arguments_;
456  // For performance reasons, the pointer of the native function is stored in this field.
457  mutable void* cached_callee_;
458 };
459 
460 // An external runtime function, with C binding.
461 class ExternalCall : public Instruction {
462  public:
463  ExternalCall(const std::string& callee_name,
464  const Type ret_type,
465  const std::vector<const Value*>& arguments,
466  const std::string& label)
467  : Instruction(ret_type, label)
468  , callee_name_(callee_name)
469  , arguments_(arguments)
470  , cached_callee_(nullptr) {}
471 
472  bool external() const { return true; }
473 
474  const std::string& callee_name() const { return callee_name_; }
475 
476  const std::vector<const Value*>& arguments() const { return arguments_; }
477 
478  void run(ReductionInterpreterImpl* interpreter) override;
479 
480  void* cached_callee() const { return cached_callee_; }
481 
483 
484  private:
485  const std::string callee_name_;
486  const std::vector<const Value*> arguments_;
487  mutable void* cached_callee_;
488 };
489 
490 class Alloca : public Instruction {
491  public:
492  Alloca(const Type element_type, const Value* array_size, const std::string& label)
493  : Instruction(pointer_type(element_type), label), array_size_(array_size) {}
494 
495  const Value* array_size() const { return array_size_; }
496 
497  void run(ReductionInterpreterImpl* interpreter) override;
498 
499  private:
501 };
502 
503 class MemCpy : public Instruction {
504  public:
505  MemCpy(const Value* dest, const Value* source, const Value* size)
506  : Instruction(Type::Void, ""), dest_(dest), source_(source), size_(size) {}
507 
508  const Value* dest() const { return dest_; }
509 
510  const Value* source() const { return source_; }
511 
512  const Value* size() const { return size_; }
513 
514  void run(ReductionInterpreterImpl* interpreter) override;
515 
516  private:
517  const Value* dest_;
518  const Value* source_;
519  const Value* size_;
520 };
521 
522 // Returns from the current function with the given error code, if the provided condition
523 // is true. If the function return type is void, the error code is ignored.
524 class ReturnEarly : public Instruction {
525  public:
526  ReturnEarly(const Value* cond, const std::string& label)
527  : Instruction(Type::Void, label), cond_(cond), error_code_(nullptr) {}
528 
529  ReturnEarly(const Value* cond, const Value* error_code, const std::string& label)
530  : Instruction(Type::Void, label), cond_(cond), error_code_(error_code) {}
531 
532  const Value* cond() const { return cond_; }
533 
534  const Value* error_code() const { return error_code_; }
535 
536  void run(ReductionInterpreterImpl* interpreter) override;
537 
538  private:
539  const Value* cond_;
541 };
542 
543 // An operation which executes the provided body from the given start index to the end
544 // index (exclusive). Additionally, the iterator is added to the variables seen by the
545 // body.
546 class For : public Instruction {
547  public:
548  For(const Value* start, const Value* end, const std::string& label)
549  : Instruction(Type::Void, label)
550  , start_(start)
551  , end_(end)
552  , iter_(Type::Int64, label) {}
553 
554  const std::vector<std::unique_ptr<Instruction>>& body() const { return body_; }
555 
556  const Value* start() const { return start_; }
557 
558  const Value* end() const { return end_; }
559 
560  const Value* iter() const { return &iter_; }
561 
562  void run(ReductionInterpreterImpl* interpreter) override;
563 
564  template <typename Tp, typename... Args>
565  Value* add(Args&&... args) {
566  body_.emplace_back(new Tp(std::forward<Args>(args)...));
567  return body_.back().get();
568  }
569 
570  private:
571  std::vector<std::unique_ptr<Instruction>> body_;
572  const Value* start_;
573  const Value* end_;
574  // Since the iterator always moves between the start and the end, just store a dummy
575  // value. During codegen or interpretation, it will be mapped to the current value of
576  // the iterator.
577  const Value iter_;
578 };
const int64_t value_
const std::vector< std::unique_ptr< Constant > > & constants() const
Argument(const Type type, const std::string &label)
const std::vector< NamedArg > & arg_types() const
const Value * size() const
bool external() const
const std::string & name() const
const Value * array_size_
bool external() const
const Value * cond_
size_t id() const
const Value * error_code() const
const std::string & label() const
Ret(const Value *value)
ExternalCall(const std::string &callee_name, const Type ret_type, const std::vector< const Value * > &arguments, const std::string &label)
const std::vector< const Value * > arguments_
bool always_inline() const
ICmp(const Predicate predicate, const Value *lhs, const Value *rhs, const std::string &label)
const Value * value() const
const Value * index_
const Value * rhs() const
const Value * source_
const std::string callee_name_
const std::vector< std::unique_ptr< Instruction > > & body() const
#define LOG(tag)
Definition: Logger.h:216
std::ostream & operator<<(std::ostream &os, const SessionInfo &session_info)
Definition: SessionInfo.cpp:57
const std::string callee_name_
void run(ReductionInterpreterImpl *interpreter) override
Type ret_type() const
const std::vector< const Value * > arguments_
Argument * arg(const size_t idx) const
Type type() const
Instruction(const Type type, const std::string &label)
ConstantInt(const int64_t value, const Type target)
Type pointer_type(const Type pointee)
std::vector< std::unique_ptr< Argument > > arguments_
Alloca(const Type element_type, const Value *array_size, const std::string &label)
Constant(const Type type)
BinaryOperator(const BinaryOp op, const Value *lhs, const Value *rhs, const std::string &label)
void run(ReductionInterpreterImpl *interpreter) override
void run(ReductionInterpreterImpl *interpreter) override
const Value * base() const
Value * addConstant(Args &&...args)
Value * add(Args &&...args)
virtual void run(ReductionInterpreterImpl *interpreter)=0
const Value * lhs() const
void set_cached_callee(void *cached_callee) const
void * cached_callee() const
const Value * end_
thread_local size_t g_value_id
const Value * source() const
const Value * end() const
void * cached_callee_
const Value * start() const
const Value * rhs_
std::vector< std::unique_ptr< Instruction > > body_
const Value * rhs() const
Call(const std::string &callee_name, const Type returnType, const std::vector< const Value * > &arguments, const std::string &label)
const Value * source() const
ConstantFP(const double value, const Type target)
const std::string label_
const Value * dest() const
void run(ReductionInterpreterImpl *interpreter) override
const Value * start_
void run(ReductionInterpreterImpl *interpreter) override
Function(const std::string name, const std::vector< NamedArg > &arg_types, const Type ret_type, const bool always_inline)
GetElementPtr(const Value *base, const Value *index, const std::string &label)
const Value * value_
const std::vector< NamedArg > arg_types_
Type pointee_type(const Type pointer)
const Value * lhs_
Call(const Function *callee, const std::vector< const Value * > &arguments, const std::string &label)
const std::string & callee_name() const
const std::vector< const Value * > & arguments() const
BinaryOp op() const
Value * add(Args &&...args)
const Type type_
void run(ReductionInterpreterImpl *interpreter) override
Value(const Type type, const std::string &label)
MemCpy(const Value *dest, const Value *source, const Value *size)
void * cached_callee() const
const size_t id_
const Function * callee() const
const Value * cond() const
const Predicate predicate_
const Value * source() const
std::vector< std::unique_ptr< Instruction > > body_
const Value * error_code_
Cast(const CastOp op, const Value *source, const Type type, const std::string &label)
Load(const Value *source, const std::string &label)
const Value * index() const
const Value * array_size() const
const Value * size_
const bool always_inline_
const Value * lhs() const
virtual ~Value()=default
const Value * source_
const std::vector< std::unique_ptr< Instruction > > & body() const
For(const Value *start, const Value *end, const std::string &label)
int64_t value() const
double value() const
CastOp op() const
const Value * iter() const
std::vector< std::unique_ptr< Constant > > constants_
const Value * dest_
const Value * source_
const Value iter_
ReturnEarly(const Value *cond, const std::string &label)
const CastOp op_
const Function * callee_
void run(ReductionInterpreterImpl *interpreter) override
const std::string name_
const std::string & callee_name() const
Predicate predicate() const
void run(ReductionInterpreterImpl *interpreter) override
void run(ReductionInterpreterImpl *interpreter) override
void run(ReductionInterpreterImpl *interpreter) override
const double value_
Call(const std::string &callee_name, const std::vector< const Value * > &arguments, const std::string &label)
const Type ret_type_
void run(ReductionInterpreterImpl *interpreter) override
void set_cached_callee(void *cached_callee) const
void run(ReductionInterpreterImpl *interpreter) override
ReturnEarly(const Value *cond, const Value *error_code, const std::string &label)
const std::vector< const Value * > & arguments() const