OmniSciDB  ba1bac9284
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
JoinLoop Class Reference

#include <JoinLoop.h>

Public Types

using HoistedFiltersCallback = std::function< llvm::BasicBlock *(llvm::BasicBlock *, llvm::BasicBlock *, const std::string &, llvm::Function *, CgenState *)>
 

Public Member Functions

 JoinLoop (const JoinLoopKind, const JoinType, const std::function< JoinLoopDomain(const std::vector< llvm::Value * > &)> &iteration_domain_codegen, const std::function< llvm::Value *(const std::vector< llvm::Value * > &)> &outer_condition_match, const std::function< void(llvm::Value *)> &found_outer_matches, const HoistedFiltersCallback &hoisted_filters, const std::function< llvm::Value *(const std::vector< llvm::Value * > &prev_iters, llvm::Value *)> &is_deleted, const std::string &name="")
 

Static Public Member Functions

static llvm::BasicBlock * codegen (const std::vector< JoinLoop > &join_loops, const std::function< llvm::BasicBlock *(const std::vector< llvm::Value * > &)> &body_codegen, llvm::Value *outer_iter, llvm::BasicBlock *exit_bb, CgenState *cgen_state)
 

Static Private Member Functions

static std::pair
< llvm::BasicBlock
*, llvm::Value * > 
evaluateOuterJoinCondition (const JoinLoop &join_loop, const JoinLoopDomain &iteration_domain, const std::vector< llvm::Value * > &iterators, llvm::Value *iteration_counter, llvm::Value *have_more_inner_rows, llvm::Value *found_an_outer_match_ptr, llvm::Value *current_condition_match_ptr, CgenState *cgen_state)
 

Private Attributes

const JoinLoopKind kind_
 
const JoinType type_
 
const std::function
< JoinLoopDomain(const
std::vector< llvm::Value * > &)> 
iteration_domain_codegen_
 
const std::function
< llvm::Value *(const
std::vector< llvm::Value * > &)> 
outer_condition_match_
 
const std::function< void(llvm::Value *)> found_outer_matches_
 
const HoistedFiltersCallback hoisted_filters_
 
const std::function
< llvm::Value *(const
std::vector< llvm::Value * >
&prev_iters, llvm::Value *)> 
is_deleted_
 
const std::string name_
 

Detailed Description

Definition at line 54 of file JoinLoop.h.

Member Typedef Documentation

using JoinLoop::HoistedFiltersCallback = std::function<llvm::BasicBlock*(llvm::BasicBlock*, llvm::BasicBlock*, const std::string&, llvm::Function*, CgenState*)>

Definition at line 60 of file JoinLoop.h.

Constructor & Destructor Documentation

JoinLoop::JoinLoop ( const JoinLoopKind  ,
const JoinType  ,
const std::function< JoinLoopDomain(const std::vector< llvm::Value * > &)> &  iteration_domain_codegen,
const std::function< llvm::Value *(const std::vector< llvm::Value * > &)> &  outer_condition_match,
const std::function< void(llvm::Value *)> &  found_outer_matches,
const HoistedFiltersCallback hoisted_filters,
const std::function< llvm::Value *(const std::vector< llvm::Value * > &prev_iters, llvm::Value *)> &  is_deleted,
const std::string &  name = "" 
)

Definition at line 25 of file JoinLoop.cpp.

References CHECK, CHECK_EQ, and LEFT.

36  : kind_(kind)
37  , type_(type)
38  , iteration_domain_codegen_(iteration_domain_codegen)
39  , outer_condition_match_(outer_condition_match)
40  , found_outer_matches_(found_outer_matches)
41  , hoisted_filters_(hoisted_filters)
42  , is_deleted_(is_deleted)
43  , name_(name) {
44  CHECK(outer_condition_match == nullptr || type == JoinType::LEFT);
45  CHECK_EQ(static_cast<bool>(found_outer_matches), (type == JoinType::LEFT));
46 }
#define CHECK_EQ(x, y)
Definition: Logger.h:214
string name
Definition: setup.in.py:72
const std::function< llvm::Value *(const std::vector< llvm::Value * > &)> outer_condition_match_
Definition: JoinLoop.h:103
const JoinType type_
Definition: JoinLoop.h:95
const JoinLoopKind kind_
Definition: JoinLoop.h:93
const std::function< JoinLoopDomain(const std::vector< llvm::Value * > &)> iteration_domain_codegen_
Definition: JoinLoop.h:99
const std::function< void(llvm::Value *)> found_outer_matches_
Definition: JoinLoop.h:106
const std::string name_
Definition: JoinLoop.h:117
const std::function< llvm::Value *(const std::vector< llvm::Value * > &prev_iters, llvm::Value *)> is_deleted_
Definition: JoinLoop.h:116
#define CHECK(condition)
Definition: Logger.h:206
const HoistedFiltersCallback hoisted_filters_
Definition: JoinLoop.h:109

Member Function Documentation

llvm::BasicBlock * JoinLoop::codegen ( const std::vector< JoinLoop > &  join_loops,
const std::function< llvm::BasicBlock *(const std::vector< llvm::Value * > &)> &  body_codegen,
llvm::Value *  outer_iter,
llvm::BasicBlock *  exit_bb,
CgenState cgen_state 
)
static

Definition at line 48 of file JoinLoop.cpp.

References AUTOMATIC_IR_METADATA, CHECK, evaluateOuterJoinCondition(), get_int_type(), INNER, INVALID, CgenState::ir_builder_, LEFT, ll_bool(), ll_int(), Set, Singleton, and UpperBound.

Referenced by Executor::codegenJoinLoops(), anonymous_namespace{JoinLoopTest.cpp}::create_loop_test_function(), and anonymous_namespace{ResultSetReductionCodegen.cpp}::translate_for().

54  {
55  AUTOMATIC_IR_METADATA(cgen_state);
56  llvm::IRBuilder<>& builder = cgen_state->ir_builder_;
57  llvm::BasicBlock* prev_exit_bb{exit_bb};
58  llvm::BasicBlock* prev_iter_advance_bb{nullptr};
59  llvm::BasicBlock* last_head_bb{nullptr};
60  auto& context = builder.getContext();
61  const auto parent_func = builder.GetInsertBlock()->getParent();
62  llvm::Value* prev_comparison_result{nullptr};
63  llvm::BasicBlock* entry{nullptr};
64  std::vector<llvm::Value*> iterators;
65  iterators.push_back(outer_iter);
66  JoinType prev_join_type{JoinType::INVALID};
67  for (const auto& join_loop : join_loops) {
68  switch (join_loop.kind_) {
70  case JoinLoopKind::Set: {
71  const auto preheader_bb = llvm::BasicBlock::Create(
72  context, "ub_iter_preheader_" + join_loop.name_, parent_func);
73 
74  llvm::BasicBlock* filter_bb{nullptr};
75  if (join_loop.hoisted_filters_) {
76  filter_bb = join_loop.hoisted_filters_(
77  preheader_bb, prev_exit_bb, join_loop.name_, parent_func, cgen_state);
78  }
79 
80  if (!entry) {
81  entry = filter_bb ? filter_bb : preheader_bb;
82  }
83 
84  if (prev_comparison_result) {
85  builder.CreateCondBr(
86  prev_comparison_result,
87  filter_bb ? filter_bb : preheader_bb,
88  prev_join_type == JoinType::LEFT ? prev_iter_advance_bb : prev_exit_bb);
89  }
90  prev_exit_bb = prev_iter_advance_bb ? prev_iter_advance_bb : exit_bb;
91  builder.SetInsertPoint(preheader_bb);
92 
93  const auto iteration_counter_ptr = builder.CreateAlloca(
94  get_int_type(64, context), nullptr, "ub_iter_counter_ptr_" + join_loop.name_);
95  llvm::Value* found_an_outer_match_ptr{nullptr};
96  llvm::Value* current_condition_match_ptr{nullptr};
97  if (join_loop.type_ == JoinType::LEFT) {
98  found_an_outer_match_ptr = builder.CreateAlloca(
99  get_int_type(1, context), nullptr, "found_an_outer_match");
100  builder.CreateStore(ll_bool(false, context), found_an_outer_match_ptr);
101  current_condition_match_ptr = builder.CreateAlloca(
102  get_int_type(1, context), nullptr, "outer_condition_current_match");
103  }
104  builder.CreateStore(ll_int(int64_t(0), context), iteration_counter_ptr);
105  const auto iteration_domain = join_loop.iteration_domain_codegen_(iterators);
106  const auto head_bb = llvm::BasicBlock::Create(
107  context, "ub_iter_head_" + join_loop.name_, parent_func);
108  builder.CreateBr(head_bb);
109  builder.SetInsertPoint(head_bb);
110  llvm::Value* iteration_counter = builder.CreateLoad(
111  iteration_counter_ptr, "ub_iter_counter_val_" + join_loop.name_);
112  auto iteration_val = iteration_counter;
113  CHECK(join_loop.kind_ == JoinLoopKind::Set || !iteration_domain.values_buffer);
114  if (join_loop.kind_ == JoinLoopKind::Set) {
115  iteration_val =
116  builder.CreateGEP(iteration_domain.values_buffer, iteration_counter);
117  }
118  iterators.push_back(iteration_val);
119  const auto have_more_inner_rows = builder.CreateICmpSLT(
120  iteration_counter,
121  join_loop.kind_ == JoinLoopKind::UpperBound ? iteration_domain.upper_bound
122  : iteration_domain.element_count,
123  "have_more_inner_rows");
124  const auto iter_advance_bb = llvm::BasicBlock::Create(
125  context, "ub_iter_advance_" + join_loop.name_, parent_func);
126  llvm::BasicBlock* row_not_deleted_bb{nullptr};
127  if (join_loop.is_deleted_) {
128  row_not_deleted_bb = llvm::BasicBlock::Create(
129  context, "row_not_deleted_" + join_loop.name_, parent_func);
130  const auto row_is_deleted =
131  join_loop.is_deleted_(iterators, have_more_inner_rows);
132  builder.CreateCondBr(row_is_deleted, iter_advance_bb, row_not_deleted_bb);
133  builder.SetInsertPoint(row_not_deleted_bb);
134  }
135  if (join_loop.type_ == JoinType::LEFT) {
136  std::tie(last_head_bb, prev_comparison_result) =
137  evaluateOuterJoinCondition(join_loop,
138  iteration_domain,
139  iterators,
140  iteration_counter,
141  have_more_inner_rows,
142  found_an_outer_match_ptr,
143  current_condition_match_ptr,
144  cgen_state);
145  } else {
146  prev_comparison_result = have_more_inner_rows;
147  last_head_bb = row_not_deleted_bb ? row_not_deleted_bb : head_bb;
148  }
149  builder.SetInsertPoint(iter_advance_bb);
150  const auto iteration_counter_next_val =
151  builder.CreateAdd(iteration_counter, ll_int(int64_t(1), context));
152  builder.CreateStore(iteration_counter_next_val, iteration_counter_ptr);
153  if (join_loop.type_ == JoinType::LEFT) {
154  const auto no_more_inner_rows =
155  builder.CreateICmpSGT(iteration_counter_next_val,
156  join_loop.kind_ == JoinLoopKind::UpperBound
157  ? iteration_domain.upper_bound
158  : iteration_domain.element_count,
159  "no_more_inner_rows");
160  builder.CreateCondBr(no_more_inner_rows, prev_exit_bb, head_bb);
161  } else {
162  builder.CreateBr(head_bb);
163  }
164  builder.SetInsertPoint(last_head_bb);
165  prev_iter_advance_bb = iter_advance_bb;
166  break;
167  }
169  const auto true_bb = llvm::BasicBlock::Create(
170  context, "singleton_true_" + join_loop.name_, parent_func);
171 
172  llvm::BasicBlock* filter_bb{nullptr};
173  if (join_loop.hoisted_filters_) {
174  filter_bb = join_loop.hoisted_filters_(
175  true_bb, prev_exit_bb, join_loop.name_, parent_func, cgen_state);
176  }
177 
178  if (!entry) {
179  entry = filter_bb ? filter_bb : true_bb;
180  }
181 
182  if (prev_comparison_result) {
183  builder.CreateCondBr(
184  prev_comparison_result,
185  filter_bb ? filter_bb : true_bb,
186  prev_join_type == JoinType::LEFT ? prev_iter_advance_bb : prev_exit_bb);
187  }
188  prev_exit_bb = prev_iter_advance_bb ? prev_iter_advance_bb : exit_bb;
189 
190  builder.SetInsertPoint(true_bb);
191  const auto iteration_domain = join_loop.iteration_domain_codegen_(iterators);
192  CHECK(!iteration_domain.values_buffer);
193  iterators.push_back(iteration_domain.slot_lookup_result);
194  auto match_found = builder.CreateICmpSGE(iteration_domain.slot_lookup_result,
195  ll_int<int64_t>(0, context));
196  if (join_loop.is_deleted_) {
197  match_found = builder.CreateAnd(
198  match_found, builder.CreateNot(join_loop.is_deleted_(iterators, nullptr)));
199  }
200  auto match_found_bb = builder.GetInsertBlock();
201  switch (join_loop.type_) {
202  case JoinType::INNER: {
203  prev_comparison_result = match_found;
204  break;
205  }
206  case JoinType::LEFT: {
207  join_loop.found_outer_matches_(match_found);
208  // For outer joins, do the iteration regardless of the result of the match.
209  prev_comparison_result = ll_bool(true, context);
210  break;
211  }
212  default:
213  CHECK(false);
214  }
215  if (!prev_iter_advance_bb) {
216  prev_iter_advance_bb = prev_exit_bb;
217  }
218  last_head_bb = match_found_bb;
219  break;
220  }
221  default:
222  CHECK(false);
223  }
224  prev_join_type = join_loop.type_;
225  }
226  const auto body_bb = body_codegen(iterators);
227  builder.CreateBr(prev_iter_advance_bb);
228  builder.SetInsertPoint(last_head_bb);
229  builder.CreateCondBr(
230  prev_comparison_result,
231  body_bb,
232  prev_join_type == JoinType::LEFT ? prev_iter_advance_bb : prev_exit_bb);
233  return entry;
234 }
JoinType
Definition: sqldefs.h:108
llvm::ConstantInt * ll_int(const T v, llvm::LLVMContext &context)
llvm::IRBuilder ir_builder_
Definition: CgenState.h:335
llvm::Type * get_int_type(const int width, llvm::LLVMContext &context)
#define AUTOMATIC_IR_METADATA(CGENSTATE)
#define CHECK(condition)
Definition: Logger.h:206
llvm::ConstantInt * ll_bool(const bool v, llvm::LLVMContext &context)
static std::pair< llvm::BasicBlock *, llvm::Value * > evaluateOuterJoinCondition(const JoinLoop &join_loop, const JoinLoopDomain &iteration_domain, const std::vector< llvm::Value * > &iterators, llvm::Value *iteration_counter, llvm::Value *have_more_inner_rows, llvm::Value *found_an_outer_match_ptr, llvm::Value *current_condition_match_ptr, CgenState *cgen_state)
Definition: JoinLoop.cpp:236

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

std::pair< llvm::BasicBlock *, llvm::Value * > JoinLoop::evaluateOuterJoinCondition ( const JoinLoop join_loop,
const JoinLoopDomain iteration_domain,
const std::vector< llvm::Value * > &  iterators,
llvm::Value *  iteration_counter,
llvm::Value *  have_more_inner_rows,
llvm::Value *  found_an_outer_match_ptr,
llvm::Value *  current_condition_match_ptr,
CgenState cgen_state 
)
staticprivate

Definition at line 236 of file JoinLoop.cpp.

References AUTOMATIC_IR_METADATA, JoinLoopDomain::element_count, found_outer_matches_, CgenState::ir_builder_, kind_, ll_bool(), name_, outer_condition_match_, JoinLoopDomain::upper_bound, and UpperBound.

Referenced by codegen().

244  {
245  AUTOMATIC_IR_METADATA(cgen_state);
246  llvm::IRBuilder<>& builder = cgen_state->ir_builder_;
247  auto& context = builder.getContext();
248  const auto parent_func = builder.GetInsertBlock()->getParent();
249  builder.CreateStore(ll_bool(false, context), current_condition_match_ptr);
250  const auto evaluate_outer_condition_bb = llvm::BasicBlock::Create(
251  context, "eval_outer_cond_" + join_loop.name_, parent_func);
252  const auto after_evaluate_outer_condition_bb = llvm::BasicBlock::Create(
253  context, "after_eval_outer_cond_" + join_loop.name_, parent_func);
254  builder.CreateCondBr(have_more_inner_rows,
255  evaluate_outer_condition_bb,
256  after_evaluate_outer_condition_bb);
257  builder.SetInsertPoint(evaluate_outer_condition_bb);
258  const auto current_condition_match = join_loop.outer_condition_match_
259  ? join_loop.outer_condition_match_(iterators)
260  : ll_bool(true, context);
261  builder.CreateStore(current_condition_match, current_condition_match_ptr);
262  const auto updated_condition_match = builder.CreateOr(
263  current_condition_match, builder.CreateLoad(found_an_outer_match_ptr));
264  builder.CreateStore(updated_condition_match, found_an_outer_match_ptr);
265  builder.CreateBr(after_evaluate_outer_condition_bb);
266  builder.SetInsertPoint(after_evaluate_outer_condition_bb);
267  const auto no_matches_found =
268  builder.CreateNot(builder.CreateLoad(found_an_outer_match_ptr));
269  const auto no_more_inner_rows = builder.CreateICmpEQ(
270  iteration_counter,
271  join_loop.kind_ == JoinLoopKind::UpperBound ? iteration_domain.upper_bound
272  : iteration_domain.element_count);
273  // Do the iteration if the outer condition is true or it's the last iteration and no
274  // matches have been found.
275  const auto do_iteration =
276  builder.CreateOr(builder.CreateLoad(current_condition_match_ptr),
277  builder.CreateAnd(no_matches_found, no_more_inner_rows));
278  join_loop.found_outer_matches_(builder.CreateLoad(current_condition_match_ptr));
279  return {after_evaluate_outer_condition_bb, do_iteration};
280 }
llvm::Value * element_count
Definition: JoinLoop.h:45
llvm::IRBuilder ir_builder_
Definition: CgenState.h:335
const std::function< llvm::Value *(const std::vector< llvm::Value * > &)> outer_condition_match_
Definition: JoinLoop.h:103
const JoinLoopKind kind_
Definition: JoinLoop.h:93
const std::function< void(llvm::Value *)> found_outer_matches_
Definition: JoinLoop.h:106
const std::string name_
Definition: JoinLoop.h:117
#define AUTOMATIC_IR_METADATA(CGENSTATE)
llvm::Value * upper_bound
Definition: JoinLoop.h:44
llvm::ConstantInt * ll_bool(const bool v, llvm::LLVMContext &context)

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

Member Data Documentation

const std::function<void(llvm::Value*)> JoinLoop::found_outer_matches_
private

Definition at line 106 of file JoinLoop.h.

Referenced by evaluateOuterJoinCondition().

const HoistedFiltersCallback JoinLoop::hoisted_filters_
private

Definition at line 109 of file JoinLoop.h.

const std::function<llvm::Value*(const std::vector<llvm::Value*>& prev_iters, llvm::Value*)> JoinLoop::is_deleted_
private

Definition at line 116 of file JoinLoop.h.

const std::function<JoinLoopDomain(const std::vector<llvm::Value*>&)> JoinLoop::iteration_domain_codegen_
private

Definition at line 99 of file JoinLoop.h.

const JoinLoopKind JoinLoop::kind_
private

Definition at line 93 of file JoinLoop.h.

Referenced by evaluateOuterJoinCondition().

const std::string JoinLoop::name_
private

Definition at line 117 of file JoinLoop.h.

Referenced by evaluateOuterJoinCondition().

const std::function<llvm::Value*(const std::vector<llvm::Value*>&)> JoinLoop::outer_condition_match_
private

Definition at line 103 of file JoinLoop.h.

Referenced by evaluateOuterJoinCondition().

const JoinType JoinLoop::type_
private

Definition at line 95 of file JoinLoop.h.


The documentation for this class was generated from the following files: