OmniSciDB  2b310ab3b2
 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) {
191  const auto optype = bin_oper->get_optype();
192  auto lhs = bin_oper->get_left_operand();
193  auto rhs = bin_oper->get_right_operand();
194 
195  if (contains_unsafe_division(rhs)) {
196  // rhs contains a possible div-by-0: short-circuit
197  } else if (contains_unsafe_division(lhs)) {
198  // lhs contains a possible div-by-0: swap and short-circuit
199  std::swap(rhs, lhs);
200  } else if (((optype == kOR && get_likelihood(lhs) > 0.90) ||
201  (optype == kAND && get_likelihood(lhs) < 0.10)) &&
202  get_weight(rhs) > 10) {
203  // short circuit if we're likely to see either (trueA || heavyB) or (falseA && heavyB)
204  } else if (((optype == kOR && get_likelihood(rhs) > 0.90) ||
205  (optype == kAND && get_likelihood(rhs) < 0.10)) &&
206  get_weight(lhs) > 10) {
207  // swap and short circuit if we're likely to see either (heavyA || trueB) or (heavyA
208  // && falseB)
209  std::swap(rhs, lhs);
210  } else {
211  // no motivation to short circuit
212  return nullptr;
213  }
214 
215  const auto& ti = bin_oper->get_type_info();
216  auto lhs_lv = codegen(lhs, true, co).front();
217 
218  // Here the linear control flow will diverge and expressions cached during the
219  // code branch code generation (currently just column decoding) are not going
220  // to be available once we're done generating the short-circuited logic.
221  // Take a snapshot of the cache with FetchCacheAnchor and restore it once
222  // the control flow converges.
224 
225  auto rhs_bb = llvm::BasicBlock::Create(
227  auto ret_bb = llvm::BasicBlock::Create(
229  llvm::BasicBlock* nullcheck_ok_bb{nullptr};
230  llvm::BasicBlock* nullcheck_fail_bb{nullptr};
231 
232  if (!ti.get_notnull()) {
233  // need lhs nullcheck before short circuiting
234  nullcheck_ok_bb = llvm::BasicBlock::Create(
235  cgen_state_->context_, "nullcheck_ok_bb", cgen_state_->current_func_);
236  nullcheck_fail_bb = llvm::BasicBlock::Create(
237  cgen_state_->context_, "nullcheck_fail_bb", cgen_state_->current_func_);
238  if (lhs_lv->getType()->isIntegerTy(1)) {
239  lhs_lv = cgen_state_->castToTypeIn(lhs_lv, 8);
240  }
241  auto lhs_nullcheck =
242  cgen_state_->ir_builder_.CreateICmpEQ(lhs_lv, cgen_state_->inlineIntNull(ti));
243  cgen_state_->ir_builder_.CreateCondBr(
244  lhs_nullcheck, nullcheck_fail_bb, nullcheck_ok_bb);
245  cgen_state_->ir_builder_.SetInsertPoint(nullcheck_ok_bb);
246  }
247 
248  auto sc_check_bb = cgen_state_->ir_builder_.GetInsertBlock();
249  auto cnst_lv = llvm::ConstantInt::get(lhs_lv->getType(), (optype == kOR));
250  // Branch to codegen rhs if NOT getting (true || rhs) or (false && rhs), likelihood of
251  // the branch is < 0.10
252  cgen_state_->ir_builder_.CreateCondBr(
253  cgen_state_->ir_builder_.CreateICmpNE(lhs_lv, cnst_lv),
254  rhs_bb,
255  ret_bb,
256  llvm::MDBuilder(cgen_state_->context_).createBranchWeights(10, 90));
257 
258  // Codegen rhs when unable to short circuit.
259  cgen_state_->ir_builder_.SetInsertPoint(rhs_bb);
260  auto rhs_lv = codegen(rhs, true, co).front();
261  if (!ti.get_notnull()) {
262  // need rhs nullcheck as well
263  if (rhs_lv->getType()->isIntegerTy(1)) {
264  rhs_lv = cgen_state_->castToTypeIn(rhs_lv, 8);
265  }
266  auto rhs_nullcheck =
267  cgen_state_->ir_builder_.CreateICmpEQ(rhs_lv, cgen_state_->inlineIntNull(ti));
268  cgen_state_->ir_builder_.CreateCondBr(rhs_nullcheck, nullcheck_fail_bb, ret_bb);
269  } else {
270  cgen_state_->ir_builder_.CreateBr(ret_bb);
271  }
272  auto rhs_codegen_bb = cgen_state_->ir_builder_.GetInsertBlock();
273 
274  if (!ti.get_notnull()) {
275  cgen_state_->ir_builder_.SetInsertPoint(nullcheck_fail_bb);
276  cgen_state_->ir_builder_.CreateBr(ret_bb);
277  }
278 
279  cgen_state_->ir_builder_.SetInsertPoint(ret_bb);
280  auto result_phi =
281  cgen_state_->ir_builder_.CreatePHI(lhs_lv->getType(), (!ti.get_notnull()) ? 3 : 2);
282  if (!ti.get_notnull()) {
283  result_phi->addIncoming(cgen_state_->inlineIntNull(ti), nullcheck_fail_bb);
284  }
285  result_phi->addIncoming(cnst_lv, sc_check_bb);
286  result_phi->addIncoming(rhs_lv, rhs_codegen_bb);
287  return result_phi;
288 }
289 
291  const CompilationOptions& co) {
293  const auto optype = bin_oper->get_optype();
294  CHECK(IS_LOGIC(optype));
295 
296  if (llvm::Value* short_circuit = codegenLogicalShortCircuit(bin_oper, co)) {
297  return short_circuit;
298  }
299 
300  const auto lhs = bin_oper->get_left_operand();
301  const auto rhs = bin_oper->get_right_operand();
302  auto lhs_lv = codegen(lhs, true, co).front();
303  auto rhs_lv = codegen(rhs, true, co).front();
304  const auto& ti = bin_oper->get_type_info();
305  if (ti.get_notnull()) {
306  switch (optype) {
307  case kAND:
308  return cgen_state_->ir_builder_.CreateAnd(toBool(lhs_lv), toBool(rhs_lv));
309  case kOR:
310  return cgen_state_->ir_builder_.CreateOr(toBool(lhs_lv), toBool(rhs_lv));
311  default:
312  CHECK(false);
313  }
314  }
315  CHECK(lhs_lv->getType()->isIntegerTy(1) || lhs_lv->getType()->isIntegerTy(8));
316  CHECK(rhs_lv->getType()->isIntegerTy(1) || rhs_lv->getType()->isIntegerTy(8));
317  if (lhs_lv->getType()->isIntegerTy(1)) {
318  lhs_lv = cgen_state_->castToTypeIn(lhs_lv, 8);
319  }
320  if (rhs_lv->getType()->isIntegerTy(1)) {
321  rhs_lv = cgen_state_->castToTypeIn(rhs_lv, 8);
322  }
323  switch (optype) {
324  case kAND:
325  return cgen_state_->emitCall("logical_and",
326  {lhs_lv, rhs_lv, cgen_state_->inlineIntNull(ti)});
327  case kOR:
328  return cgen_state_->emitCall("logical_or",
329  {lhs_lv, rhs_lv, cgen_state_->inlineIntNull(ti)});
330  default:
331  abort();
332  }
333 }
334 
335 llvm::Value* CodeGenerator::toBool(llvm::Value* lv) {
337  CHECK(lv->getType()->isIntegerTy());
338  if (static_cast<llvm::IntegerType*>(lv->getType())->getBitWidth() > 1) {
339  return cgen_state_->ir_builder_.CreateICmp(
340  llvm::ICmpInst::ICMP_SGT, lv, llvm::ConstantInt::get(lv->getType(), 0));
341  }
342  return lv;
343 }
344 
345 namespace {
346 
348  const auto bin_oper = dynamic_cast<const Analyzer::BinOper*>(expr);
349  return bin_oper && bin_oper->get_qualifier() != kONE;
350 }
351 
352 } // namespace
353 
355  const CompilationOptions& co) {
357  const auto optype = uoper->get_optype();
358  CHECK_EQ(kNOT, optype);
359  const auto operand = uoper->get_operand();
360  const auto& operand_ti = operand->get_type_info();
361  CHECK(operand_ti.is_boolean());
362  const auto operand_lv = codegen(operand, true, co).front();
363  CHECK(operand_lv->getType()->isIntegerTy());
364  const bool not_null = (operand_ti.get_notnull() || is_qualified_bin_oper(operand));
365  CHECK(not_null || operand_lv->getType()->isIntegerTy(8));
366  return not_null
367  ? cgen_state_->ir_builder_.CreateNot(toBool(operand_lv))
369  "logical_not", {operand_lv, cgen_state_->inlineIntNull(operand_ti)});
370 }
371 
373  const CompilationOptions& co) {
375  const auto operand = uoper->get_operand();
376  if (dynamic_cast<const Analyzer::Constant*>(operand) &&
377  dynamic_cast<const Analyzer::Constant*>(operand)->get_is_null()) {
378  // for null constants, short-circuit to true
379  return llvm::ConstantInt::get(get_int_type(1, cgen_state_->context_), 1);
380  }
381  const auto& ti = operand->get_type_info();
382  CHECK(ti.is_integer() || ti.is_boolean() || ti.is_decimal() || ti.is_time() ||
383  ti.is_string() || ti.is_fp() || ti.is_array() || ti.is_geometry());
384  // if the type is inferred as non null, short-circuit to false
385  if (ti.get_notnull()) {
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  // NULL-check array or geo's coords array
390  if (ti.is_array() || ti.is_geometry()) {
391  // POINT [un]compressed coord check requires custom checker and chunk iterator
392  // Non-POINT NULL geographies will have a normally encoded null coord array
393  auto fname =
394  (ti.get_type() == kPOINT) ? "point_coord_array_is_null" : "array_is_null";
396  fname, get_int_type(1, cgen_state_->context_), {operand_lv, posArg(operand)});
397  }
398  return codegenIsNullNumber(operand_lv, ti);
399 }
400 
401 llvm::Value* CodeGenerator::codegenIsNullNumber(llvm::Value* operand_lv,
402  const SQLTypeInfo& ti) {
404  if (ti.is_fp()) {
405  return cgen_state_->ir_builder_.CreateFCmp(llvm::FCmpInst::FCMP_OEQ,
406  operand_lv,
407  ti.get_type() == kFLOAT
410  }
411  return cgen_state_->ir_builder_.CreateICmp(
412  llvm::ICmpInst::ICMP_EQ, operand_lv, cgen_state_->inlineIntNull(ti));
413 }
#define CHECK_EQ(x, y)
Definition: Logger.h:205
llvm::Value * castToTypeIn(llvm::Value *val, const size_t bit_width)
Definition: CgenState.cpp:106
#define IS_LOGIC(X)
Definition: sqldefs.h:60
#define NULL_DOUBLE
Definition: sqltypes.h:186
bool should_defer_eval(const std::shared_ptr< Analyzer::Expr > expr)
Definition: LogicalIR.cpp:54
CgenState * cgen_state_
bool is_fp() const
Definition: sqltypes.h:420
llvm::Value * emitExternalCall(const std::string &fname, llvm::Type *ret_type, const std::vector< llvm::Value * > args, const std::vector< llvm::Attribute::AttrKind > &fnattrs={}, const bool has_struct_return=false)
Definition: CgenState.h:213
const Expr * get_right_operand() const
Definition: Analyzer.h:443
llvm::IRBuilder ir_builder_
Definition: CgenState.h:332
llvm::Value * posArg(const Analyzer::Expr *) const
Definition: ColumnIR.cpp:515
Definition: sqldefs.h:38
HOST DEVICE SQLTypes get_type() const
Definition: sqltypes.h:259
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::Value * codegenIsNull(const Analyzer::UOper *, const CompilationOptions &)
Definition: LogicalIR.cpp:372
SQLOps get_optype() const
Definition: Analyzer.h:439
Likelihood get_likelihood(const Analyzer::Expr *expr)
Definition: LogicalIR.cpp:78
llvm::LLVMContext & context_
Definition: CgenState.h:330
llvm::Function * current_func_
Definition: CgenState.h:324
CHECK(cgen_state)
bool is_qualified_bin_oper(const Analyzer::Expr *expr)
Definition: LogicalIR.cpp:347
llvm::ConstantInt * inlineIntNull(const SQLTypeInfo &)
Definition: CgenState.cpp:27
#define NULL_FLOAT
Definition: sqltypes.h:185
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:307
#define AUTOMATIC_IR_METADATA(CGENSTATE)
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:137
SQLTypes decimal_to_int_type(const SQLTypeInfo &ti)
Definition: Datum.cpp:298
std::vector< llvm::Value * > codegen(const Analyzer::Expr *, const bool fetch_columns, const CompilationOptions &)
Definition: IRCodegen.cpp:26
Definition: sqldefs.h:69
const Expr * get_operand() const
Definition: Analyzer.h:371
Datum get_constval() const
Definition: Analyzer.h:335
llvm::Value * toBool(llvm::Value *)
Definition: LogicalIR.cpp:335
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:401
llvm::Value * codegenLogical(const Analyzer::BinOper *, const CompilationOptions &)
Definition: LogicalIR.cpp:290
bool contains_unsafe_division(const Analyzer::Expr *expr)
Definition: LogicalIR.cpp:25
const Expr * get_left_operand() const
Definition: Analyzer.h:442
Definition: sqltypes.h:47
llvm::Value * codegenLogicalShortCircuit(const Analyzer::BinOper *, const CompilationOptions &)
Definition: LogicalIR.cpp:188
Definition: sqldefs.h:39
SQLOps get_optype() const
Definition: Analyzer.h:370
bool is_array() const
Definition: sqltypes.h:424
NullableValue< uint64_t > Weight
std::list< std::shared_ptr< Analyzer::Expr > > simple_quals
SQLQualifier get_qualifier() const
Definition: Analyzer.h:441