OmniSciDB  1dac507f6e
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
LogicalIR.cpp
Go to the documentation of this file.
1 /*
2  * Copyright 2017 MapD Technologies, 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 #include "CodeGenerator.h"
18 #include "Execute.h"
19 #include "NullableValue.h"
20 
21 #include <llvm/IR/MDBuilder.h>
22 
23 namespace {
24 
26  auto is_div = [](const Analyzer::Expr* e) -> bool {
27  auto bin_oper = dynamic_cast<const Analyzer::BinOper*>(e);
28  if (bin_oper && bin_oper->get_optype() == kDIVIDE) {
29  auto rhs = bin_oper->get_right_operand();
30  auto rhs_constant = dynamic_cast<const Analyzer::Constant*>(rhs);
31  if (!rhs_constant || rhs_constant->get_is_null()) {
32  return true;
33  }
34  const auto& datum = rhs_constant->get_constval();
35  const auto& ti = rhs_constant->get_type_info();
36  const auto type = ti.is_decimal() ? decimal_to_int_type(ti) : ti.get_type();
37  if ((type == kBOOLEAN && datum.boolval == 0) ||
38  (type == kTINYINT && datum.tinyintval == 0) ||
39  (type == kSMALLINT && datum.smallintval == 0) ||
40  (type == kINT && datum.intval == 0) ||
41  (type == kBIGINT && datum.bigintval == 0LL) ||
42  (type == kFLOAT && datum.floatval == 0.0) ||
43  (type == kDOUBLE && datum.doubleval == 0.0)) {
44  return true;
45  }
46  }
47  return false;
48  };
49  std::list<const Analyzer::Expr*> binoper_list;
50  expr->find_expr(is_div, binoper_list);
51  return !binoper_list.empty();
52 }
53 
54 bool should_defer_eval(const std::shared_ptr<Analyzer::Expr> expr) {
55  if (std::dynamic_pointer_cast<Analyzer::LikeExpr>(expr)) {
56  return true;
57  }
58  if (std::dynamic_pointer_cast<Analyzer::RegexpExpr>(expr)) {
59  return true;
60  }
61  if (std::dynamic_pointer_cast<Analyzer::FunctionOper>(expr)) {
62  return true;
63  }
64  if (!std::dynamic_pointer_cast<Analyzer::BinOper>(expr)) {
65  return false;
66  }
67  const auto bin_expr = std::static_pointer_cast<Analyzer::BinOper>(expr);
68  if (contains_unsafe_division(bin_expr.get())) {
69  return true;
70  }
71  if (bin_expr->is_overlaps_oper()) {
72  return false;
73  }
74  const auto rhs = bin_expr->get_right_operand();
75  return rhs->get_type_info().is_array();
76 }
77 
79  Likelihood truth{1.0};
80  auto likelihood_expr = dynamic_cast<const Analyzer::LikelihoodExpr*>(expr);
81  if (likelihood_expr) {
82  return Likelihood(likelihood_expr->get_likelihood());
83  }
84  auto u_oper = dynamic_cast<const Analyzer::UOper*>(expr);
85  if (u_oper) {
86  Likelihood oper_likelihood = get_likelihood(u_oper->get_operand());
87  if (oper_likelihood.isInvalid()) {
88  return Likelihood();
89  }
90  if (u_oper->get_optype() == kNOT) {
91  return truth - oper_likelihood;
92  }
93  return oper_likelihood;
94  }
95  auto bin_oper = dynamic_cast<const Analyzer::BinOper*>(expr);
96  if (bin_oper) {
97  auto lhs = bin_oper->get_left_operand();
98  auto rhs = bin_oper->get_right_operand();
99  Likelihood lhs_likelihood = get_likelihood(lhs);
100  Likelihood rhs_likelihood = get_likelihood(rhs);
101  if (lhs_likelihood.isInvalid() && rhs_likelihood.isInvalid()) {
102  return Likelihood();
103  }
104  const auto optype = bin_oper->get_optype();
105  if (optype == kOR) {
106  auto both_false = (truth - lhs_likelihood) * (truth - rhs_likelihood);
107  return truth - both_false;
108  }
109  if (optype == kAND) {
110  return lhs_likelihood * rhs_likelihood;
111  }
112  return (lhs_likelihood + rhs_likelihood) / 2.0;
113  }
114 
115  return Likelihood();
116 }
117 
118 Weight get_weight(const Analyzer::Expr* expr, int depth = 0) {
119  auto like_expr = dynamic_cast<const Analyzer::LikeExpr*>(expr);
120  if (like_expr) {
121  // heavy weight expr, start valid weight propagation
122  return Weight((like_expr->get_is_simple()) ? 200 : 1000);
123  }
124  auto regexp_expr = dynamic_cast<const Analyzer::RegexpExpr*>(expr);
125  if (regexp_expr) {
126  // heavy weight expr, start valid weight propagation
127  return Weight(2000);
128  }
129  auto u_oper = dynamic_cast<const Analyzer::UOper*>(expr);
130  if (u_oper) {
131  auto weight = get_weight(u_oper->get_operand(), depth + 1);
132  return weight + 1;
133  }
134  auto bin_oper = dynamic_cast<const Analyzer::BinOper*>(expr);
135  if (bin_oper) {
136  auto lhs = bin_oper->get_left_operand();
137  auto rhs = bin_oper->get_right_operand();
138  auto lhs_weight = get_weight(lhs, depth + 1);
139  auto rhs_weight = get_weight(rhs, depth + 1);
140  if (rhs->get_type_info().is_array()) {
141  // heavy weight expr, start valid weight propagation
142  rhs_weight = rhs_weight + Weight(100);
143  }
144  auto weight = lhs_weight + rhs_weight;
145  return weight + 1;
146  }
147 
148  if (depth > 4) {
149  return Weight(1);
150  }
151 
152  return Weight();
153 }
154 
155 } // namespace
156 
158  std::vector<Analyzer::Expr*>& primary_quals,
159  std::vector<Analyzer::Expr*>& deferred_quals) {
160  for (auto expr : ra_exe_unit.simple_quals) {
161  if (should_defer_eval(expr)) {
162  deferred_quals.push_back(expr.get());
163  continue;
164  }
165  primary_quals.push_back(expr.get());
166  }
167 
168  bool short_circuit = false;
169 
170  for (auto expr : ra_exe_unit.quals) {
171  if (get_likelihood(expr.get()) < 0.10 && !contains_unsafe_division(expr.get())) {
172  if (!short_circuit) {
173  primary_quals.push_back(expr.get());
174  short_circuit = true;
175  continue;
176  }
177  }
178  if (short_circuit || should_defer_eval(expr)) {
179  deferred_quals.push_back(expr.get());
180  continue;
181  }
182  primary_quals.push_back(expr.get());
183  }
184 
185  return short_circuit;
186 }
187 
189  const CompilationOptions& co) {
190  const auto optype = bin_oper->get_optype();
191  auto lhs = bin_oper->get_left_operand();
192  auto rhs = bin_oper->get_right_operand();
193 
194  if (contains_unsafe_division(rhs)) {
195  // rhs contains a possible div-by-0: short-circuit
196  } else if (contains_unsafe_division(lhs)) {
197  // lhs contains a possible div-by-0: swap and short-circuit
198  std::swap(rhs, lhs);
199  } else if (((optype == kOR && get_likelihood(lhs) > 0.90) ||
200  (optype == kAND && get_likelihood(lhs) < 0.10)) &&
201  get_weight(rhs) > 10) {
202  // short circuit if we're likely to see either (trueA || heavyB) or (falseA && heavyB)
203  } else if (((optype == kOR && get_likelihood(rhs) > 0.90) ||
204  (optype == kAND && get_likelihood(rhs) < 0.10)) &&
205  get_weight(lhs) > 10) {
206  // swap and short circuit if we're likely to see either (heavyA || trueB) or (heavyA
207  // && falseB)
208  std::swap(rhs, lhs);
209  } else {
210  // no motivation to short circuit
211  return nullptr;
212  }
213 
214  const auto& ti = bin_oper->get_type_info();
215  auto lhs_lv = codegen(lhs, true, co).front();
216 
217  // Here the linear control flow will diverge and expressions cached during the
218  // code branch code generation (currently just column decoding) are not going
219  // to be available once we're done generating the short-circuited logic.
220  // Take a snapshot of the cache with FetchCacheAnchor and restore it once
221  // the control flow converges.
223 
224  auto rhs_bb =
225  llvm::BasicBlock::Create(cgen_state_->context_, "rhs_bb", cgen_state_->row_func_);
226  auto ret_bb =
227  llvm::BasicBlock::Create(cgen_state_->context_, "ret_bb", cgen_state_->row_func_);
228  llvm::BasicBlock* nullcheck_ok_bb{nullptr};
229  llvm::BasicBlock* nullcheck_fail_bb{nullptr};
230 
231  if (!ti.get_notnull()) {
232  // need lhs nullcheck before short circuiting
233  nullcheck_ok_bb = llvm::BasicBlock::Create(
234  cgen_state_->context_, "nullcheck_ok_bb", cgen_state_->row_func_);
235  nullcheck_fail_bb = llvm::BasicBlock::Create(
236  cgen_state_->context_, "nullcheck_fail_bb", cgen_state_->row_func_);
237  if (lhs_lv->getType()->isIntegerTy(1)) {
238  lhs_lv = cgen_state_->castToTypeIn(lhs_lv, 8);
239  }
240  auto lhs_nullcheck =
241  cgen_state_->ir_builder_.CreateICmpEQ(lhs_lv, cgen_state_->inlineIntNull(ti));
242  cgen_state_->ir_builder_.CreateCondBr(
243  lhs_nullcheck, nullcheck_fail_bb, nullcheck_ok_bb);
244  cgen_state_->ir_builder_.SetInsertPoint(nullcheck_ok_bb);
245  }
246 
247  auto sc_check_bb = cgen_state_->ir_builder_.GetInsertBlock();
248  auto cnst_lv = llvm::ConstantInt::get(lhs_lv->getType(), (optype == kOR));
249  // Branch to codegen rhs if NOT getting (true || rhs) or (false && rhs), likelihood of
250  // the branch is < 0.10
251  cgen_state_->ir_builder_.CreateCondBr(
252  cgen_state_->ir_builder_.CreateICmpNE(lhs_lv, cnst_lv),
253  rhs_bb,
254  ret_bb,
255  llvm::MDBuilder(cgen_state_->context_).createBranchWeights(10, 90));
256 
257  // Codegen rhs when unable to short circuit.
258  cgen_state_->ir_builder_.SetInsertPoint(rhs_bb);
259  auto rhs_lv = codegen(rhs, true, co).front();
260  if (!ti.get_notnull()) {
261  // need rhs nullcheck as well
262  if (rhs_lv->getType()->isIntegerTy(1)) {
263  rhs_lv = cgen_state_->castToTypeIn(rhs_lv, 8);
264  }
265  auto rhs_nullcheck =
266  cgen_state_->ir_builder_.CreateICmpEQ(rhs_lv, cgen_state_->inlineIntNull(ti));
267  cgen_state_->ir_builder_.CreateCondBr(rhs_nullcheck, nullcheck_fail_bb, ret_bb);
268  } else {
269  cgen_state_->ir_builder_.CreateBr(ret_bb);
270  }
271  auto rhs_codegen_bb = cgen_state_->ir_builder_.GetInsertBlock();
272 
273  if (!ti.get_notnull()) {
274  cgen_state_->ir_builder_.SetInsertPoint(nullcheck_fail_bb);
275  cgen_state_->ir_builder_.CreateBr(ret_bb);
276  }
277 
278  cgen_state_->ir_builder_.SetInsertPoint(ret_bb);
279  auto result_phi =
280  cgen_state_->ir_builder_.CreatePHI(lhs_lv->getType(), (!ti.get_notnull()) ? 3 : 2);
281  if (!ti.get_notnull()) {
282  result_phi->addIncoming(cgen_state_->inlineIntNull(ti), nullcheck_fail_bb);
283  }
284  result_phi->addIncoming(cnst_lv, sc_check_bb);
285  result_phi->addIncoming(rhs_lv, rhs_codegen_bb);
286  return result_phi;
287 }
288 
290  const CompilationOptions& co) {
291  const auto optype = bin_oper->get_optype();
292  CHECK(IS_LOGIC(optype));
293 
294  if (llvm::Value* short_circuit = codegenLogicalShortCircuit(bin_oper, co)) {
295  return short_circuit;
296  }
297 
298  const auto lhs = bin_oper->get_left_operand();
299  const auto rhs = bin_oper->get_right_operand();
300  auto lhs_lv = codegen(lhs, true, co).front();
301  auto rhs_lv = codegen(rhs, true, co).front();
302  const auto& ti = bin_oper->get_type_info();
303  if (ti.get_notnull()) {
304  switch (optype) {
305  case kAND:
306  return cgen_state_->ir_builder_.CreateAnd(toBool(lhs_lv), toBool(rhs_lv));
307  case kOR:
308  return cgen_state_->ir_builder_.CreateOr(toBool(lhs_lv), toBool(rhs_lv));
309  default:
310  CHECK(false);
311  }
312  }
313  CHECK(lhs_lv->getType()->isIntegerTy(1) || lhs_lv->getType()->isIntegerTy(8));
314  CHECK(rhs_lv->getType()->isIntegerTy(1) || rhs_lv->getType()->isIntegerTy(8));
315  if (lhs_lv->getType()->isIntegerTy(1)) {
316  lhs_lv = cgen_state_->castToTypeIn(lhs_lv, 8);
317  }
318  if (rhs_lv->getType()->isIntegerTy(1)) {
319  rhs_lv = cgen_state_->castToTypeIn(rhs_lv, 8);
320  }
321  switch (optype) {
322  case kAND:
323  return cgen_state_->emitCall("logical_and",
324  {lhs_lv, rhs_lv, cgen_state_->inlineIntNull(ti)});
325  case kOR:
326  return cgen_state_->emitCall("logical_or",
327  {lhs_lv, rhs_lv, cgen_state_->inlineIntNull(ti)});
328  default:
329  abort();
330  }
331 }
332 
333 llvm::Value* CodeGenerator::toBool(llvm::Value* lv) {
334  CHECK(lv->getType()->isIntegerTy());
335  if (static_cast<llvm::IntegerType*>(lv->getType())->getBitWidth() > 1) {
336  return cgen_state_->ir_builder_.CreateICmp(
337  llvm::ICmpInst::ICMP_SGT, lv, llvm::ConstantInt::get(lv->getType(), 0));
338  }
339  return lv;
340 }
341 
342 namespace {
343 
345  const auto bin_oper = dynamic_cast<const Analyzer::BinOper*>(expr);
346  return bin_oper && bin_oper->get_qualifier() != kONE;
347 }
348 
349 } // namespace
350 
352  const CompilationOptions& co) {
353  const auto optype = uoper->get_optype();
354  CHECK_EQ(kNOT, optype);
355  const auto operand = uoper->get_operand();
356  const auto& operand_ti = operand->get_type_info();
357  CHECK(operand_ti.is_boolean());
358  const auto operand_lv = codegen(operand, true, co).front();
359  CHECK(operand_lv->getType()->isIntegerTy());
360  const bool not_null = (operand_ti.get_notnull() || is_qualified_bin_oper(operand));
361  CHECK(not_null || operand_lv->getType()->isIntegerTy(8));
362  return not_null
363  ? cgen_state_->ir_builder_.CreateNot(toBool(operand_lv))
365  "logical_not", {operand_lv, cgen_state_->inlineIntNull(operand_ti)});
366 }
367 
369  const CompilationOptions& co) {
370  const auto operand = uoper->get_operand();
371  if (dynamic_cast<const Analyzer::Constant*>(operand) &&
372  dynamic_cast<const Analyzer::Constant*>(operand)->get_is_null()) {
373  // for null constants, short-circuit to true
374  return llvm::ConstantInt::get(get_int_type(1, cgen_state_->context_), 1);
375  }
376  const auto& ti = operand->get_type_info();
377  CHECK(ti.is_integer() || ti.is_boolean() || ti.is_decimal() || ti.is_time() ||
378  ti.is_string() || ti.is_fp() || ti.is_array() || ti.is_geometry());
379  // if the type is inferred as non null, short-circuit to false
380  if (ti.get_notnull()) {
381  return llvm::ConstantInt::get(get_int_type(1, cgen_state_->context_), 0);
382  }
383  // There is currently no NULL geo in existing tables, short-circuit to false
384  // TODO: update for NULL geo support, codegen geo_is_null call
385  if (ti.is_geometry()) {
386  return llvm::ConstantInt::get(get_int_type(1, cgen_state_->context_), 0);
387  }
388  const auto operand_lv = codegen(operand, true, co).front();
389  if (ti.is_array()) {
390  return cgen_state_->emitExternalCall("array_is_null",
392  {operand_lv, posArg(operand)});
393  }
394  return codegenIsNullNumber(operand_lv, ti);
395 }
396 
397 llvm::Value* CodeGenerator::codegenIsNullNumber(llvm::Value* operand_lv,
398  const SQLTypeInfo& ti) {
399  if (ti.is_fp()) {
400  return cgen_state_->ir_builder_.CreateFCmp(llvm::FCmpInst::FCMP_OEQ,
401  operand_lv,
402  ti.get_type() == kFLOAT
405  }
406  return cgen_state_->ir_builder_.CreateICmp(
407  llvm::ICmpInst::ICMP_EQ, operand_lv, cgen_state_->inlineIntNull(ti));
408 }
bool is_fp() const
Definition: sqltypes.h:481
#define CHECK_EQ(x, y)
Definition: Logger.h:198
llvm::Value * castToTypeIn(llvm::Value *val, const size_t bit_width)
Definition: CgenState.cpp:103
#define IS_LOGIC(X)
Definition: sqldefs.h:60
#define NULL_DOUBLE
Definition: sqltypes.h:179
bool should_defer_eval(const std::shared_ptr< Analyzer::Expr > expr)
Definition: LogicalIR.cpp:54
CgenState * cgen_state_
const Expr * get_right_operand() const
Definition: Analyzer.h:437
llvm::IRBuilder ir_builder_
Definition: CgenState.h:269
llvm::Value * posArg(const Analyzer::Expr *) const
Definition: ColumnIR.cpp:503
Definition: sqldefs.h:38
llvm::Type * get_int_type(const int width, llvm::LLVMContext &context)
static bool prioritizeQuals(const RelAlgExecutionUnit &ra_exe_unit, std::vector< Analyzer::Expr * > &primary_quals, std::vector< Analyzer::Expr * > &deferred_quals)
Definition: LogicalIR.cpp:157
llvm::Function * row_func_
Definition: CgenState.h:265
llvm::Value * codegenIsNull(const Analyzer::UOper *, const CompilationOptions &)
Definition: LogicalIR.cpp:368
SQLOps get_optype() const
Definition: Analyzer.h:433
Likelihood get_likelihood(const Analyzer::Expr *expr)
Definition: LogicalIR.cpp:78
llvm::LLVMContext & context_
Definition: CgenState.h:267
CHECK(cgen_state)
bool is_array() const
Definition: sqltypes.h:485
bool is_qualified_bin_oper(const Analyzer::Expr *expr)
Definition: LogicalIR.cpp:344
HOST DEVICE SQLTypes get_type() const
Definition: sqltypes.h:326
llvm::ConstantInt * inlineIntNull(const SQLTypeInfo &)
Definition: CgenState.cpp:24
#define NULL_FLOAT
Definition: sqltypes.h:178
Weight get_weight(const Analyzer::Expr *expr, int depth=0)
Definition: LogicalIR.cpp:118
bool isInvalid() const
Definition: NullableValue.h:34
Definition: sqldefs.h:37
NullableValue< float > Likelihood
llvm::ConstantFP * llFp(const float v) const
Definition: CgenState.h:252
const SQLTypeInfo & get_type_info() const
Definition: Analyzer.h:78
llvm::Value * emitCall(const std::string &fname, const std::vector< llvm::Value * > &args)
Definition: CgenState.cpp:134
SQLTypes decimal_to_int_type(const SQLTypeInfo &ti)
Definition: Datum.cpp:268
std::vector< llvm::Value * > codegen(const Analyzer::Expr *, const bool fetch_columns, const CompilationOptions &)
Definition: IRCodegen.cpp:25
llvm::Value * emitExternalCall(const std::string &fname, llvm::Type *ret_type, const std::vector< llvm::Value * > args, const std::vector< llvm::Attribute::AttrKind > &fnattrs={})
Definition: CgenState.h:205
Definition: sqldefs.h:69
const Expr * get_operand() const
Definition: Analyzer.h:365
Datum get_constval() const
Definition: Analyzer.h:329
llvm::Value * toBool(llvm::Value *)
Definition: LogicalIR.cpp:333
virtual void find_expr(bool(*f)(const Expr *), std::list< const Expr * > &expr_list) const
Definition: Analyzer.h:159
std::list< std::shared_ptr< Analyzer::Expr > > quals
llvm::Value * codegenIsNullNumber(llvm::Value *, const SQLTypeInfo &)
Definition: LogicalIR.cpp:397
llvm::Value * codegenLogical(const Analyzer::BinOper *, const CompilationOptions &)
Definition: LogicalIR.cpp:289
bool contains_unsafe_division(const Analyzer::Expr *expr)
Definition: LogicalIR.cpp:25
const Expr * get_left_operand() const
Definition: Analyzer.h:436
Definition: sqltypes.h:48
llvm::Value * codegenLogicalShortCircuit(const Analyzer::BinOper *, const CompilationOptions &)
Definition: LogicalIR.cpp:188
Definition: sqldefs.h:39
SQLOps get_optype() const
Definition: Analyzer.h:364
NullableValue< uint64_t > Weight
std::list< std::shared_ptr< Analyzer::Expr > > simple_quals
SQLQualifier get_qualifier() const
Definition: Analyzer.h:435