OmniSciDB  85c2d10cdc
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
ResultSetReductionInterpreter.cpp
Go to the documentation of this file.
1 /*
2  * Copyright 2019 OmniSci, 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 
19 
20 thread_local size_t g_value_id;
21 
22 namespace {
23 
24 // Extract types of the given values.
25 std::vector<Type> get_value_types(const std::vector<const Value*>& values) {
26  std::vector<Type> value_types;
27  value_types.reserve(value_types.size());
28  std::transform(values.begin(),
29  values.end(),
30  std::back_inserter(value_types),
31  [](const Value* value) { return value->type(); });
32  return value_types;
33 }
34 
35 // For an alloca buffer, return the element size.
36 size_t get_element_size(const Type element_type) {
37  switch (element_type) {
38  case Type::Int8Ptr: {
39  return sizeof(int8_t);
40  }
41  case Type::Int64PtrPtr: {
42  return sizeof(int64_t*);
43  }
44  default: {
45  LOG(FATAL) << "Base pointer type not supported: " << static_cast<int>(element_type);
46  break;
47  }
48  }
49  return 0;
50 }
51 
52 } // namespace
53 
54 // Implements execution for all the operators. Caller is responsible for stopping
55 // evaluation when the return value is set.
57  public:
58  ReductionInterpreterImpl(const std::vector<ReductionInterpreter::EvalValue>& vars)
59  : vars_(vars) {}
60 
61  std::optional<ReductionInterpreter::EvalValue> ret() const { return ret_; }
62 
63  public:
64  static void runGetElementPtr(const Instruction* instruction,
65  ReductionInterpreterImpl* interpreter) {
66  CHECK(!interpreter->ret_) << "Function has already returned";
67  const auto gep = static_cast<const GetElementPtr*>(instruction);
68  const auto element_size = get_element_size(gep->base()->type());
69  const auto base = interpreter->vars_[gep->base()->id()];
70  const auto index = interpreter->vars_[gep->index()->id()];
71  auto result_ptr =
72  reinterpret_cast<const int8_t*>(base.ptr) + index.int_val * element_size;
73  interpreter->setVar(gep, ReductionInterpreter::MakeEvalValue(result_ptr));
74  }
75 
76  static void runLoad(const Instruction* instruction,
77  ReductionInterpreterImpl* interpreter) {
78  CHECK(!interpreter->ret_) << "Function has already returned";
79  const auto load = static_cast<const Load*>(instruction);
80  const auto source_type = load->source()->type();
81  CHECK(is_pointer_type(source_type));
82  const auto source = interpreter->vars_[load->source()->id()];
83  switch (source_type) {
84  case Type::Int8Ptr: {
85  const auto int_val = *reinterpret_cast<const int8_t*>(source.ptr);
86  interpreter->setVar(load, ReductionInterpreter::MakeEvalValue(int_val));
87  break;
88  }
89  case Type::Int32Ptr: {
90  const auto int_val = *reinterpret_cast<const int32_t*>(source.ptr);
91  interpreter->setVar(load, ReductionInterpreter::MakeEvalValue(int_val));
92  break;
93  }
94  case Type::Int64Ptr: {
95  const auto int_val = *reinterpret_cast<const int64_t*>(source.ptr);
96  interpreter->setVar(load, ReductionInterpreter::MakeEvalValue(int_val));
97  break;
98  }
99  case Type::FloatPtr: {
100  const auto float_val = *reinterpret_cast<const float*>(source.ptr);
101  interpreter->setVar(load, ReductionInterpreter::MakeEvalValue(float_val));
102  break;
103  }
104  case Type::DoublePtr: {
105  const auto double_val = *reinterpret_cast<const double*>(source.ptr);
106  interpreter->setVar(load, ReductionInterpreter::MakeEvalValue(double_val));
107  break;
108  }
109  case Type::Int64PtrPtr: {
110  const auto int_ptr_val = *reinterpret_cast<const int64_t* const*>(source.ptr);
111  interpreter->setVar(load, ReductionInterpreter::MakeEvalValue(int_ptr_val));
112  break;
113  }
114  default: {
115  LOG(FATAL) << "Source pointer type not supported: "
116  << static_cast<int>(source_type);
117  }
118  }
119  }
120 
121  static void runICmp(const Instruction* instruction,
122  ReductionInterpreterImpl* interpreter) {
123  CHECK(!interpreter->ret_) << "Function has already returned";
124  const auto icmp = static_cast<const ICmp*>(instruction);
125  CHECK(is_integer_type(icmp->lhs()->type()));
126  CHECK(is_integer_type(icmp->rhs()->type()));
127  const auto lhs = interpreter->vars_[icmp->lhs()->id()];
128  const auto rhs = interpreter->vars_[icmp->rhs()->id()];
129  bool result = false;
130  switch (icmp->predicate()) {
131  case ICmp::Predicate::EQ: {
132  result = lhs.int_val == rhs.int_val;
133  break;
134  }
135  case ICmp::Predicate::NE: {
136  result = lhs.int_val != rhs.int_val;
137  break;
138  }
139  default: {
140  LOG(FATAL) << "Predicate not supported: " << static_cast<int>(icmp->predicate());
141  }
142  }
143  interpreter->setVar(icmp, ReductionInterpreter::MakeEvalValue(result));
144  }
145 
146  static void runBinaryOperator(const Instruction* instruction,
147  ReductionInterpreterImpl* interpreter) {
148  CHECK(!interpreter->ret_) << "Function has already returned";
149  const auto binary_operator = static_cast<const BinaryOperator*>(instruction);
150  CHECK(is_integer_type(binary_operator->type()));
151  const auto lhs = interpreter->vars_[binary_operator->lhs()->id()];
152  const auto rhs = interpreter->vars_[binary_operator->rhs()->id()];
153  int64_t result = 0;
154  switch (binary_operator->op()) {
156  result = lhs.int_val + rhs.int_val;
157  break;
158  }
160  result = lhs.int_val * rhs.int_val;
161  break;
162  }
163  default: {
164  LOG(FATAL) << "Binary operator not supported: "
165  << static_cast<int>(binary_operator->op());
166  }
167  }
168  interpreter->setVar(binary_operator, ReductionInterpreter::MakeEvalValue(result));
169  }
170 
171  static void runCast(const Instruction* instruction,
172  ReductionInterpreterImpl* interpreter) {
173  CHECK(!interpreter->ret_) << "Function has already returned";
174  const auto cast = static_cast<const Cast*>(instruction);
175  const auto source = interpreter->vars_[cast->source()->id()];
176  // Given that evaluated values store all values as int64_t or void*, Trunc and SExt
177  // are no-op. The information about the type is already part of the destination.
178  switch (cast->op()) {
179  case Cast::CastOp::Trunc:
180  case Cast::CastOp::SExt: {
181  CHECK(is_integer_type(cast->source()->type()));
182  interpreter->setVar(cast, ReductionInterpreter::MakeEvalValue(source.int_val));
183  break;
184  }
185  case Cast::CastOp::BitCast: {
186  CHECK(is_pointer_type(cast->source()->type()));
187  interpreter->setVar(cast, ReductionInterpreter::MakeEvalValue(source.ptr));
188  break;
189  }
190  default: {
191  LOG(FATAL) << "Cast operator not supported: " << static_cast<int>(cast->op());
192  }
193  }
194  }
195 
196  static void runRet(const Instruction* instruction,
197  ReductionInterpreterImpl* interpreter) {
198  CHECK(!interpreter->ret_) << "Function has already returned";
199  const auto ret = static_cast<const Ret*>(instruction);
200  if (ret->type() == Type::Void) {
201  // Even if the returned type is void, the return value still needs to be set to
202  // something to inform the caller that it should stop evaluating.
203  interpreter->ret_ = ReductionInterpreter::EvalValue{};
204  } else {
205  interpreter->ret_ = interpreter->vars_[ret->value()->id()];
206  }
207  }
208 
209  static void runCall(const Instruction* instruction,
210  ReductionInterpreterImpl* interpreter) {
211  CHECK(!interpreter->ret_) << "Function has already returned";
212  const auto call = static_cast<const Call*>(instruction);
213  if (call->callee()) {
214  // Call one of the functions generated to implement reduction.
215  const auto inputs = getCallInputs(call, interpreter);
216  auto ret = ReductionInterpreter::run(call->callee(), inputs);
217  if (call->type() != Type::Void) {
218  // Assign the returned value.
219  interpreter->setVar(call, ret);
220  }
221  } else {
222  // Call an internal runtime function.
223  const auto func_ptr = bindStub(call);
224  const auto inputs = getCallInputs(call, interpreter);
226  func_ptr(&ret, &inputs);
227  if (call->type() != Type::Void) {
228  // Assign the returned value.
229  interpreter->setVar(call, ret);
230  }
231  }
232  return;
233  }
234 
235  static void runExternalCall(const Instruction* instruction,
236  ReductionInterpreterImpl* interpreter) {
237  CHECK(!interpreter->ret_) << "Function has already returned";
238  const auto external_call = static_cast<const ExternalCall*>(instruction);
239  const auto& arguments = external_call->arguments();
240  const auto argument_types = get_value_types(arguments);
241  const auto func_ptr = bindStub(external_call);
242  const auto inputs = getCallInputs(external_call, interpreter);
244  func_ptr(&output, &inputs);
245  interpreter->setVar(external_call, output);
246  }
247 
248  static void runAlloca(const Instruction* instruction,
249  ReductionInterpreterImpl* interpreter) {
250  CHECK(!interpreter->ret_) << "Function has already returned";
251  const auto alloca = static_cast<const Alloca*>(instruction);
252  const auto element_size = get_element_size(alloca->type());
253  CHECK(is_integer_type(alloca->array_size()->type()));
254  const auto array_size = interpreter->vars_[alloca->array_size()->id()];
255  interpreter->alloca_buffers_.emplace_back(element_size * array_size.int_val);
257  eval_value.mutable_ptr = interpreter->alloca_buffers_.back().data();
258  interpreter->setVar(alloca, eval_value);
259  }
260 
261  static void runMemCpy(const Instruction* instruction,
262  ReductionInterpreterImpl* interpreter) {
263  CHECK(!interpreter->ret_) << "Function has already returned";
264  const auto memcpy = static_cast<const MemCpy*>(instruction);
265  CHECK(is_pointer_type(memcpy->dest()->type()));
266  CHECK(is_pointer_type(memcpy->source()->type()));
267  CHECK(is_integer_type(memcpy->size()->type()));
268  const auto dest = interpreter->vars_[memcpy->dest()->id()];
269  const auto source = interpreter->vars_[memcpy->source()->id()];
270  const auto size = interpreter->vars_[memcpy->size()->id()];
271  ::memcpy(dest.mutable_ptr, source.ptr, size.int_val);
272  }
273 
274  static void runReturnEarly(const Instruction* instruction,
275  ReductionInterpreterImpl* interpreter) {
276  CHECK(!interpreter->ret_) << "Function has already returned";
277  const auto ret_early = static_cast<const ReturnEarly*>(instruction);
278  CHECK(ret_early->cond()->type() == Type::Int1);
279  const auto cond = interpreter->vars_[ret_early->cond()->id()];
280 
281  auto error_code = ret_early->error_code();
282 
283  if (cond.int_val) {
284  auto rc = interpreter->vars_[error_code->id()].int_val;
285  interpreter->ret_ = ReductionInterpreter::MakeEvalValue(rc);
286  }
287  }
288 
289  static void runFor(const Instruction* instruction,
290  ReductionInterpreterImpl* interpreter) {
291  CHECK(!interpreter->ret_) << "Function has already returned";
292  const size_t saved_alloca_count = interpreter->alloca_buffers_.size();
293  const auto for_loop = static_cast<const For*>(instruction);
294  CHECK(is_integer_type(for_loop->start()->type()));
295  CHECK(is_integer_type(for_loop->end()->type()));
296  const auto start = interpreter->vars_[for_loop->start()->id()];
297  const auto end = interpreter->vars_[for_loop->end()->id()];
298  for (int64_t i = start.int_val; i < end.int_val; ++i) {
299  // The start and end indices are absolute, but the iteration happens from 0.
300  // Subtract the start index before setting the iterator.
301  interpreter->vars_[for_loop->iter()->id()].int_val = i - start.int_val;
302  auto ret = ReductionInterpreter::run(for_loop->body(), interpreter->vars_);
303  if (ret) {
304  interpreter->ret_ = *ret;
305  break;
306  }
307  }
308  // Pop all the alloca buffers allocated by the code in the loop.
309  interpreter->alloca_buffers_.resize(saved_alloca_count);
310  }
311 
312  private:
313  // Set the variable based on its id.
314  void setVar(const Value* var, ReductionInterpreter::EvalValue value) {
315  vars_[var->id()] = value;
316  }
317 
318  // Seed the parameters of the callee.
319  template <class Call>
320  static std::vector<ReductionInterpreter::EvalValue> getCallInputs(
321  const Call* call,
322  const ReductionInterpreterImpl* interpreter) {
323  std::vector<ReductionInterpreter::EvalValue> inputs;
324  inputs.reserve(interpreter->vars_.size());
325  for (const auto argument : call->arguments()) {
326  inputs.push_back(interpreter->vars_[argument->id()]);
327  }
328  return inputs;
329  }
330 
331  // Bind and cache a stub call.
332  template <class Call>
333  static StubGenerator::Stub bindStub(const Call* call) {
334  const auto func_ptr =
335  call->cached_callee()
336  ? reinterpret_cast<StubGenerator::Stub>(call->cached_callee())
338  get_value_types(call->arguments()),
339  call->type(),
340  call->external());
341  CHECK(func_ptr);
342  call->set_cached_callee(reinterpret_cast<void*>(func_ptr));
343  return func_ptr;
344  }
345 
346  // Holds the evaluated values.
347  std::vector<ReductionInterpreter::EvalValue> vars_;
348  // Holds buffers allocated by the alloca instruction.
349  std::vector<std::vector<int8_t>> alloca_buffers_;
350  // Holds the value returned by the function.
351  std::optional<ReductionInterpreter::EvalValue> ret_ = std::nullopt;
352 };
353 
356 }
357 
359  ReductionInterpreterImpl::runLoad(this, interpreter);
360 }
361 
363  ReductionInterpreterImpl::runICmp(this, interpreter);
364 }
365 
368 }
369 
371  ReductionInterpreterImpl::runCast(this, interpreter);
372 }
373 
374 void Ret::run(ReductionInterpreterImpl* interpreter) {
375  ReductionInterpreterImpl::runRet(this, interpreter);
376 }
377 
379  ReductionInterpreterImpl::runCall(this, interpreter);
380 }
381 
384 }
385 
387  ReductionInterpreterImpl::runAlloca(this, interpreter);
388 }
389 
391  ReductionInterpreterImpl::runMemCpy(this, interpreter);
392 }
393 
395  ReductionInterpreterImpl::runReturnEarly(this, interpreter);
396 }
397 
398 void For::run(ReductionInterpreterImpl* interpreter) {
399  ReductionInterpreterImpl::runFor(this, interpreter);
400 }
401 
402 namespace {
403 
404 // Create an evaluated constant.
406  switch (constant->type()) {
407  case Type::Int8:
408  case Type::Int32:
409  case Type::Int64: {
411  static_cast<const ConstantInt*>(constant)->value());
412  }
413  case Type::Float: {
415  static_cast<float>(static_cast<const ConstantFP*>(constant)->value()));
416  }
417  case Type::Double: {
419  static_cast<const ConstantFP*>(constant)->value());
420  }
421  default: {
422  LOG(FATAL) << "Constant type not supported: " << static_cast<int>(constant->type());
423  break;
424  }
425  }
426  return {};
427 }
428 
429 } // namespace
430 
432  const Function* function,
433  const std::vector<ReductionInterpreter::EvalValue>& inputs) {
434  const auto last_id = function->body().back()->id();
435  const auto& arg_types = function->arg_types();
436  std::vector<ReductionInterpreter::EvalValue> vars(last_id + 1);
437  // Add the arguments to the variable map.
438  for (size_t i = 0; i < arg_types.size(); ++i) {
439  vars[function->arg(i)->id()] = inputs[i];
440  }
441  // Add constants to the variable map.
442  for (const auto& constant : function->constants()) {
443  vars[constant->id()] = eval_constant(constant.get());
444  }
445  const auto maybe_ret = run(function->body(), vars);
446  CHECK(maybe_ret);
447  return *maybe_ret;
448 }
449 
450 std::optional<ReductionInterpreter::EvalValue> ReductionInterpreter::run(
451  const std::vector<std::unique_ptr<Instruction>>& body,
452  const std::vector<ReductionInterpreter::EvalValue>& vars) {
453  ReductionInterpreterImpl interp_impl(vars);
454  for (const auto& instr : body) {
455  instr->run(&interp_impl);
456  const auto ret = interp_impl.ret();
457  if (ret) {
458  return *ret;
459  }
460  }
461  return interp_impl.ret();
462 }
static void runReturnEarly(const Instruction *instruction, ReductionInterpreterImpl *interpreter)
ReductionInterpreterImpl(const std::vector< ReductionInterpreter::EvalValue > &vars)
bool external() const
size_t id() const
static void runFor(const Instruction *instruction, ReductionInterpreterImpl *interpreter)
void setVar(const Value *var, ReductionInterpreter::EvalValue value)
#define const
#define LOG(tag)
Definition: Logger.h:188
std::vector< ReductionInterpreter::EvalValue > vars_
void run(ReductionInterpreterImpl *interpreter) override
Type type() const
void run(ReductionInterpreterImpl *interpreter) override
void run(ReductionInterpreterImpl *interpreter) override
static void runBinaryOperator(const Instruction *instruction, ReductionInterpreterImpl *interpreter)
static void runCall(const Instruction *instruction, ReductionInterpreterImpl *interpreter)
static std::vector< ReductionInterpreter::EvalValue > getCallInputs(const Call *call, const ReductionInterpreterImpl *interpreter)
thread_local size_t g_value_id
static void runLoad(const Instruction *instruction, ReductionInterpreterImpl *interpreter)
const Value * source() const
static EvalValue run(const Function *function, const std::vector< EvalValue > &inputs)
void run(ReductionInterpreterImpl *interpreter) override
void run(ReductionInterpreterImpl *interpreter) override
static Stub generateStub(const std::string &name, const std::vector< Type > &arg_types, const Type ret_type, const bool is_external)
static EvalValue MakeEvalValue(const T &val)
const std::string & callee_name() const
ReductionInterpreter::EvalValue eval_constant(const Constant *constant)
const std::vector< const Value * > & arguments() const
std::vector< Type > get_value_types(const std::vector< const Value * > &values)
void run(ReductionInterpreterImpl *interpreter) override
void * cached_callee() const
std::optional< ReductionInterpreter::EvalValue > ret() const
ReductionInterpreter::EvalValue(*)(void *output_handle, const void *inputs_handle) Stub
static void runExternalCall(const Instruction *instruction, ReductionInterpreterImpl *interpreter)
static void runICmp(const Instruction *instruction, ReductionInterpreterImpl *interpreter)
std::optional< ReductionInterpreter::EvalValue > ret_
#define CHECK(condition)
Definition: Logger.h:197
static void runAlloca(const Instruction *instruction, ReductionInterpreterImpl *interpreter)
std::vector< std::vector< int8_t > > alloca_buffers_
void run(ReductionInterpreterImpl *interpreter) override
void run(ReductionInterpreterImpl *interpreter) override
bool is_pointer_type(const Type type)
void run(ReductionInterpreterImpl *interpreter) override
static void runCast(const Instruction *instruction, ReductionInterpreterImpl *interpreter)
static void runMemCpy(const Instruction *instruction, ReductionInterpreterImpl *interpreter)
void run(ReductionInterpreterImpl *interpreter) override
static void runGetElementPtr(const Instruction *instruction, ReductionInterpreterImpl *interpreter)
static void runRet(const Instruction *instruction, ReductionInterpreterImpl *interpreter)
bool is_integer_type(const Type type)
void run(ReductionInterpreterImpl *interpreter) override
void set_cached_callee(void *cached_callee) const
void run(ReductionInterpreterImpl *interpreter) override
static StubGenerator::Stub bindStub(const Call *call)
const std::vector< const Value * > & arguments() const