codegen_llvm.cc 37.1 KB
Newer Older
1 2 3 4 5
/*!
 *  Copyright (c) 2017 by Contributors
 * \file codegen_llvm.cc
 */
#ifdef TVM_LLVM_VERSION
6
// Part of the code are adapted from Halide's CodeGen_LLVM
7

8
#include <tvm/runtime/device_api.h>
9
#include <tvm/runtime/c_runtime_api.h>
10
#include "./codegen_llvm.h"
11
#include "./codegen_cpu.h"
12
#include "../../pass/ir_util.h"
13 14 15 16 17
#include "../../arithmetic/compute_expr.h"

namespace tvm {
namespace codegen {

18 19 20 21 22 23 24 25
std::unique_ptr<CodeGenLLVM> CodeGenLLVM::Create(llvm::TargetMachine *tm) {
  std::string target = tm->getTarget().getName();
  std::string factory_name = "tvm.codegen.llvm.target_" + target;
  const PackedFunc* f = runtime::Registry::Get(factory_name);
  if (f != nullptr) {
    void* handle = (*f)();
    return std::unique_ptr<CodeGenLLVM>(static_cast<CodeGenLLVM*>(handle));
  } else {
26
    return std::unique_ptr<CodeGenLLVM>(new CodeGenCPU());
27 28 29
  }
}

30
void CodeGenLLVM::Init(const std::string& module_name,
31
                       llvm::TargetMachine* tm,
32
                       llvm::LLVMContext* ctx,
33 34
                       bool system_lib,
                       bool dynamic_lookup) {
35 36
  InitializeLLVM();
  ctx_ = ctx;
37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53
  builder_.reset(new IRBuilder(*ctx_));
  module_.reset(new llvm::Module(module_name, *ctx_));
  md_builder_.reset(new llvm::MDBuilder(*ctx_));
  // types
  t_void_ = llvm::Type::getVoidTy(*ctx_);
  t_void_p_ = llvm::Type::getInt8Ty(*ctx_)->getPointerTo();
  t_int_ = llvm::Type::getInt32Ty(*ctx_);
  t_char_ = llvm::Type::getInt8Ty(*ctx_);
  t_int8_ = llvm::Type::getInt8Ty(*ctx_);
  t_int16_ = llvm::Type::getInt16Ty(*ctx_);
  t_int32_ = llvm::Type::getInt32Ty(*ctx_);
  t_int64_ = llvm::Type::getInt64Ty(*ctx_);
  t_float64_ = llvm::Type::getDoubleTy(*ctx_);
  // meta data
  md_very_likely_branch_ = md_builder_->createBranchWeights(1<<20, 1);
  md_tbaa_root_ = md_builder_->createTBAARoot("tvm-tbaa");
  md_tbaa_alias_set_ = md_builder_->createTBAANode("tvm-alias", md_tbaa_root_);
54
  this->InitTarget(tm);
55 56
}

57 58
void CodeGenLLVM::InitTarget(llvm::TargetMachine* tm) {
  module_->setTargetTriple(tm->getTargetTriple().str());
59 60
  module_->setDataLayout(tm->createDataLayout());
  data_layout_.reset(new llvm::DataLayout(module_.get()));
61
  target_machine_ = tm;
62 63 64 65 66 67 68 69 70 71 72 73 74
  if (native_vector_bits_ == 0) {
    const auto& arch = tm->getTargetTriple().getArch();
    if (arch == llvm::Triple::x86_64) {
      // for avx512
      native_vector_bits_ = 512;
    } else if (arch == llvm::Triple::x86) {
      native_vector_bits_ = 256;
    } else if (arch == llvm::Triple::arm || arch == llvm::Triple::aarch64) {
      native_vector_bits_ = 128;
    } else {
      native_vector_bits_ = 128;
      std::string arch_name = tm->getTargetTriple().getArchName();
      LOG(WARNING) << "Set native vector bits to be 128 for " << arch_name;
75
    }
76
  }
77 78
}

79 80 81 82
void CodeGenLLVM::AddFunction(const LoweredFunc& f) {
  this->AddFunctionInternal(f, false);
}

83
void CodeGenLLVM::InitFuncState() {
84
  var_map_.clear();
85
  alias_var_set_.clear();
86
  align_map_.clear();
87
  alloc_storage_info_.clear();
88
  volatile_buf_.clear();
89 90 91
}

void CodeGenLLVM::AddFunctionInternal(const LoweredFunc& f, bool ret_void) {
92
  this->InitFuncState();
93
  std::vector<llvm::Type*> arg_types;
94
  is_restricted_ = f->is_restricted;
95 96
  for (Var arg : f->args) {
    Type t = arg.type();
97 98 99 100 101 102 103 104
    if (t.is_handle()) {
      auto it = f->handle_data_type.find(arg);
      if (it != f->handle_data_type.end()) {
        arg_types.push_back(LLVMType((*it).second.type())
                            ->getPointerTo(GetGlobalAddressSpace()));
      } else {
        arg_types.push_back(t_int8_->getPointerTo(GetGlobalAddressSpace()));
      }
105 106 107
      if (!is_restricted_) {
        alias_var_set_.insert(arg.get());
      }
108
    } else {
109
      arg_types.push_back(LLVMType(arg.type()));
110 111
    }
  }
112
  llvm::FunctionType* ftype = llvm::FunctionType::get(
113 114 115 116 117 118
      ret_void ? t_void_ : t_int_, arg_types, false);
  CHECK(module_->getFunction(f->name) == nullptr)
      << "Function " << f->name << " already exist in module";
  function_ = llvm::Function::Create(
      ftype, llvm::Function::ExternalLinkage,
      f->name, module_.get());
119
  function_->setCallingConv(llvm::CallingConv::C);
Hu Shiwen committed
120
  function_->setDLLStorageClass(llvm::GlobalValue::DLLStorageClassTypes::DLLExportStorageClass);
121 122 123 124 125 126 127 128 129
  // set var map and align information
  auto arg_it = function_->arg_begin();
  for (size_t i = 0; i < f->args.size(); ++i, ++arg_it) {
    llvm::Argument* v = &(*arg_it);
    const Var& var = f->args[i];
    var_map_[var.get()] = v;
    if (is_restricted_) {
      if (var.type().is_handle() && !alias_var_set_.count(var.get())) {
        // set non alias.
130 131 132
#if TVM_LLVM_VERSION >= 50
        function_->addParamAttr(i, llvm::Attribute::NoAlias);
#else
133
        function_->setDoesNotAlias(i + 1);
134
#endif
135 136 137
      }
    }
  }
138 139
  llvm::BasicBlock* entry = llvm::BasicBlock::Create(*ctx_, "entry", function_);
  builder_->SetInsertPoint(entry);
140
  this->VisitStmt(f->body);
141 142 143 144 145
  if (ret_void) {
    builder_->CreateRetVoid();
  } else {
    builder_->CreateRet(ConstInt32(0));
  }
146 147
}

148 149
std::unique_ptr<llvm::Module> CodeGenLLVM::Finish() {
  this->AddStartupFunction();
150 151 152 153 154 155 156
  // link modules
  for (size_t i = 0; i < link_modules_.size(); ++i) {
    CHECK(!llvm::Linker::linkModules(*module_, std::move(link_modules_[i])))
        << "Failed to link modules";
  }
  link_modules_.clear();
  // optimize
157 158 159 160
  this->Optimize();
  return std::move(module_);
}

161 162 163 164
void CodeGenLLVM::AddLinkModule(std::unique_ptr<llvm::Module>&& mod) {
  link_modules_.emplace_back(std::move(mod));
}

165
void CodeGenLLVM::AddMainFunction(const std::string& entry_func_name) {
166 167 168 169 170 171 172 173 174 175 176
  LOG(FATAL) << "not implemented";
}

llvm::Value* CodeGenLLVM::GetThreadIndex(const IterVar& iv) {
  LOG(FATAL) << "not implemented";
  return nullptr;
}

llvm::Value* CodeGenLLVM::CreateStorageSync(const Call* op) {
  LOG(FATAL) << "not implemented";
  return nullptr;
177 178
}

179 180 181 182 183 184 185 186 187
class FPassManager : public llvm::legacy::FunctionPassManager {
 public:
  explicit FPassManager(llvm::Module* m)
      : llvm::legacy::FunctionPassManager(m) {}
  // override add to allow messaging
  void add(llvm::Pass* p) final {
    llvm::legacy::FunctionPassManager::add(p);
  }
};
188

189 190 191 192 193 194 195 196
class MPassManager : public llvm::legacy::PassManager {
 public:
  // override add to allow messaging
  void add(llvm::Pass* p) final {
    llvm::legacy::PassManager::add(p);
  }
};

197 198 199
void CodeGenLLVM::InitPassManagerBuilder(llvm::PassManagerBuilder* builder) {
}

200 201 202 203
void CodeGenLLVM::Optimize() {
  // place optimization pass
  llvm::PassManagerBuilder builder;
  builder.OptLevel = 3;
204 205 206 207

#if TVM_LLVM_VERSION >= 50
  builder.Inliner = llvm::createFunctionInliningPass(builder.OptLevel, 0, false);
#else
208
  builder.Inliner = llvm::createFunctionInliningPass(builder.OptLevel, 0);
209
#endif
210 211
  builder.LoopVectorize = true;
  builder.SLPVectorize = true;
212 213 214 215 216 217
  this->InitPassManagerBuilder(&builder);

#if TVM_LLVM_VERSION >= 50
  target_machine_->adjustPassManager(builder);
#endif

218 219 220 221 222 223 224 225 226 227 228 229 230 231
  // pass manager
  FPassManager fpass(module_.get());
  MPassManager mpass;
  builder.populateFunctionPassManager(fpass);
  builder.populateModulePassManager(mpass);

  fpass.doInitialization();
  for (auto it = module_->begin(); it != module_->end(); ++it) {
    fpass.run(*it);
  }
  fpass.doFinalization();
  mpass.run(*module_);
}

232 233 234 235 236 237
int CodeGenLLVM::NativeVectorBits(const runtime::StorageScope& storage_scope) const {
  return native_vector_bits_;
}

unsigned CodeGenLLVM::GetGlobalAddressSpace() {
  return 0;
238 239 240
}

llvm::Type* CodeGenLLVM::LLVMType(const Type& t) const {
241 242 243 244
  if (t.is_handle()) {
    CHECK_EQ(t.lanes(), 1);
    return t_void_p_;
  }
245
  llvm::Type* etype = nullptr;
246 247
  if (t.is_int() || t.is_uint()) {
    etype = llvm::Type::getIntNTy(*ctx_, t.bits());
248 249
  } else if (t.is_float()) {
    switch (t.bits()) {
250 251 252 253
      case 16: etype = llvm::Type::getHalfTy(*ctx_); break;
      case 32: etype = llvm::Type::getFloatTy(*ctx_); break;
      case 64: etype = llvm::Type::getDoubleTy(*ctx_); break;
      default: LOG(FATAL) << "do not support " << t;
254 255 256
    }
  }
  if (t.lanes() != 1) {
257 258 259
    return llvm::VectorType::get(etype, t.lanes());
  } else {
    return etype;
260 261 262
  }
}

263 264 265 266 267 268 269 270 271 272 273
// Add tbaa alias information for load
//
// use a binary tree typed system to declare information
// and allow alias to be distinguished across nodes.
//
// This trick comes from Halide's CodeGen_LLVM
//
void CodeGenLLVM::AddAliasInfo(llvm::Instruction* inst,
                               const Variable* buffer,
                               Expr index,
                               Type type) {
274 275 276 277 278 279 280 281
  if (alias_var_set_.count(buffer) != 0) {
    // Mark all possibly aliased pointer as same type.
    llvm::MDNode* meta = md_tbaa_alias_set_;
    inst->setMetadata(
        "tbaa",
        md_builder_->createTBAAStructTagNode(meta, meta, 0));
    return;
  }
282 283
  int base = 0, width = 0;
  // create meta-data for alias analysis
284
  // Use a group of binary tree ranges of memory banks.
285 286 287 288 289 290 291 292 293 294 295 296 297 298 299
  if (index.defined()) {
    const Ramp* ramp = index.as<Ramp>();
    if (ramp) {
      int base, stride;
      if (arith::GetConstInt(ramp->base, &base) &&
          arith::GetConstInt(ramp->stride, &stride)) {
        int xwith = ramp->lanes * stride;
        width = 1;
        while (width < xwith) {
          width *= 2;
        }
        while (base % width) {
          base -= base % width;
          width *= 2;
        }
300
      }
301 302
    } else {
      if (arith::GetConstInt(index, &base)) width = 1;
303 304 305
    }
  }
  llvm::MDNode* meta = md_tbaa_root_;
306
  std::ostringstream buffer_addr, buffer_type;
307 308
  buffer_addr << buffer;
  meta = md_builder_->createTBAAScalarTypeNode(buffer_addr.str(), meta);
309
  buffer_type << type.element_of();
310
  meta = md_builder_->createTBAAScalarTypeNode(buffer_type.str(), meta);
311 312 313 314 315 316 317 318 319 320 321 322
  // create a tree-shape access structure.
  if (width != 0) {
    for (int w = 1024; w >= width; w /= 2) {
      int b = (base / w) * w;
      std::stringstream os;
      os << buffer << ".w" << w << ".b" << b;
      meta = md_builder_->createTBAAScalarTypeNode(os.str(), meta);
    }
  }
  inst->setMetadata(
      "tbaa",
      md_builder_->createTBAAStructTagNode(meta, meta, 0));
323 324
}

325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354
void CodeGenLLVM::GetAlignment(Type t,
                               const Variable* buf_var,
                               const Expr& index,
                               int* p_alignment,
                               int* p_native_bits) {
  int max_align_bits = t.bits();
  auto it = alloc_storage_info_.find(buf_var);
  if (it != alloc_storage_info_.end()) {
    const StorageInfo& info = it->second;
    *p_native_bits = NativeVectorBits(info.scope);
    max_align_bits = info.alignment * 8;
  } else {
    *p_native_bits = native_vector_bits_;
  }

  arith::ModularEntry me = arith::EvalModular(index, align_map_);
  int align_bits = t.bits();
  while (align_bits < max_align_bits &&
         me.base % 2  == 0 &&
         me.coeff %2 == 0) {
    me.base =  me.base / 2;
    me.coeff =  me.coeff / 2;
    align_bits *= 2;
  }
  if (align_bits < 8) {
    align_bits = 8;
  }
  *p_alignment = align_bits / 8;
}

355
llvm::Value* CodeGenLLVM::CreateBroadcast(llvm::Value* value, int lanes) {
356
  llvm::Constant* undef = llvm::UndefValue::get(
357 358
      llvm::VectorType::get(value->getType(), lanes));
  llvm::Constant* zero = ConstInt32(0);
359
  value = builder_->CreateInsertElement(undef, value, zero);
360
  llvm::Constant* mask = llvm::ConstantVector::getSplat(lanes, zero);
361
  return builder_->CreateShuffleVector(value, undef, mask);
362 363
}

364 365 366 367 368 369 370 371 372 373
llvm::Value* CodeGenLLVM::CreateVecSlice(llvm::Value* vec, int begin, int extent) {
  int num_elems = static_cast<int>(vec->getType()->getVectorNumElements());
  if (extent == num_elems && begin == 0) return vec;
  CHECK_LT(begin + extent, num_elems);
  std::vector<unsigned> indices;
  for (int i = 0; i < extent; ++i) {
    indices.push_back(begin + i);
  }
  return builder_->CreateShuffleVector(vec, vec, indices);
}
374

375 376 377 378 379
llvm::Value* CodeGenLLVM::CreateVecFlip(llvm::Value* vec) {
  int num_elems = static_cast<int>(vec->getType()->getVectorNumElements());
  std::vector<unsigned> indices;
  for (int i = 0; i < num_elems; ++i) {
    indices.push_back(num_elems - i - 1);
380
  }
381 382 383 384 385 386 387 388 389 390
  return builder_->CreateShuffleVector(vec, vec, indices);
}

llvm::Value* CodeGenLLVM::CreateVecPad(llvm::Value* vec, int target_lanes) {
  llvm::Value* mask = llvm::UndefValue::get(LLVMType(Int(32, target_lanes)));
  int num_elems = static_cast<int>(vec->getType()->getVectorNumElements());
  if (num_elems == target_lanes) return vec;
  CHECK_LT(num_elems, target_lanes);
  for (int i = 0; i < num_elems; ++i) {
    mask = builder_->CreateInsertElement(mask, ConstInt32(i), ConstInt32(i));
391
  }
392
  return builder_->CreateShuffleVector(vec, vec, mask);
393 394
}

395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456
llvm::Value* CodeGenLLVM::CreateVecConcat(std::vector<llvm::Value*> vecs) {
  // concat vector, tree shape reduction
  int total_lanes = 0;
  for (llvm::Value* v : vecs) {
    total_lanes += static_cast<int>(
        v->getType()->getVectorNumElements());
  }
  while (vecs.size() > 1) {
    for (size_t i = 0; i < vecs.size(); i+=2) {
      if (i + 1 >= vecs.size()) {
        vecs[i / 2] = vecs[i]; continue;
      }
      llvm::Value* lhs = vecs[i];
      llvm::Value* rhs = vecs[i + 1];
      int lanes = static_cast<int>(std::max(
          lhs->getType()->getVectorNumElements(),
          rhs->getType()->getVectorNumElements()));
      lhs = CreateVecPad(lhs, lanes);
      rhs = CreateVecPad(lhs, lanes);
      std::vector<unsigned> mask;
      for (int i = 0; i < lanes * 2; ++i) {
        mask.push_back(i);
      }
      vecs[i / 2] = builder_->CreateShuffleVector(lhs, rhs, mask);
    }
    vecs.resize((vecs.size() + 1) / 2);
  }
  return CreateVecSlice(vecs[0], 0, total_lanes);
}


void CodeGenLLVM::CreateSerialFor(llvm::Value* begin,
                                  llvm::Value* end,
                                  llvm::Value* stride,
                                  const VarExpr& loop_var,
                                  const Stmt& body) {
  using llvm::BasicBlock;
  BasicBlock* pre_block = builder_->GetInsertBlock();
  BasicBlock* for_begin = BasicBlock::Create(
      *ctx_, "for_begin", function_);
  BasicBlock* for_body = BasicBlock::Create(
      *ctx_, "for_body", function_);
  BasicBlock* for_end = BasicBlock::Create(
      *ctx_, "for_end", function_);
  builder_->CreateBr(for_begin);
  builder_->SetInsertPoint(for_begin);
  llvm::PHINode* loop_value = builder_->CreatePHI(begin->getType(), 2);
  loop_value->addIncoming(begin, pre_block);
  CHECK(!var_map_.count(loop_var.get()));
  var_map_[loop_var.get()] = loop_value;
  builder_->CreateCondBr(CreateLT(loop_var.type(), loop_value, end),
                         for_body, for_end, md_very_likely_branch_);
  builder_->SetInsertPoint(for_body);
  this->VisitStmt(body);
  var_map_.erase(loop_var.get());
  llvm::Value* loop_next = CreateAdd(loop_var.type(), loop_value, stride);
  loop_value->addIncoming(loop_next, builder_->GetInsertBlock());
  builder_->CreateBr(for_begin);
  builder_->SetInsertPoint(for_end);
}

// cast operatpr
457 458 459
llvm::Value* CodeGenLLVM::CreateCast(Type from, Type to, llvm::Value* value) {
  llvm::Type * target = LLVMType(to);
  if (value->getType() == target) return value;
460
  if (to.is_handle()) {
461 462 463 464 465 466 467 468 469 470 471 472 473 474 475 476 477 478 479 480
    return builder_->CreateBitCast(value, target);
  } else if (!from.is_float() && !to.is_float()) {
    return builder_->CreateIntCast(value, target, from.is_int());
  } else if (from.is_float() && to.is_int()) {
    return builder_->CreateFPToSI(value, target);
  } else if (from.is_float() && to.is_uint()) {
    if (to.bits() < 8) {
      value = builder_->CreateFPToUI(value, LLVMType(to.with_bits(8)));
      return builder_->CreateIntCast(value, target, false);
    } else {
      return builder_->CreateFPToUI(value, target);
    }
  } else if (from.is_int() && to.is_float()) {
    return builder_->CreateSIToFP(value, target);
  } else if (from.is_uint() && to.is_float()) {
    return builder_->CreateUIToFP(value, target);
  } else {
    CHECK(from.is_float() && to.is_float());
    return builder_->CreateFPCast(value, target);
  }
481 482
}

483 484 485 486 487 488 489 490 491 492 493 494 495 496
llvm::Value* CodeGenLLVM::GetConstString(const std::string& str) {
  auto it = str_map_.find(str);
  if (it != str_map_.end()) return it->second;
  llvm::Type* type = llvm::ArrayType::get(t_char_, str.length() + 1);
  llvm::GlobalVariable *global = new llvm::GlobalVariable(
      *module_, type, true, llvm::GlobalValue::PrivateLinkage, 0, ".str");
  global->setAlignment(1);
  global->setInitializer(llvm::ConstantDataArray::getString(*ctx_, str));
  llvm::Constant* zero = ConstInt32(0);
  llvm::Constant* indices[] = {zero, zero};
  llvm::Constant* ptr = llvm::ConstantExpr::getGetElementPtr(
      type, global, indices);
  str_map_[str] = ptr;
  return ptr;
497 498
}

499 500 501 502 503 504 505 506
llvm::Value* CodeGenLLVM::CreateBufferPtr(
    Type t, llvm::Value* buffer, llvm::Value* index) {
  CHECK_EQ(t.lanes(), 1);
  llvm::PointerType* btype = llvm::dyn_cast<llvm::PointerType>(buffer->getType());
  CHECK(btype != nullptr);
  llvm::PointerType* ptype = LLVMType(t)->getPointerTo(btype->getAddressSpace());
  if (btype != ptype) {
    buffer = builder_->CreatePointerCast(buffer, ptype);
507
  }
508

509
  return builder_->CreateInBoundsGEP(buffer, index);
510 511
}

512 513
llvm::Value* CodeGenLLVM::GetVarValue(const Variable* v) const {
  auto it = var_map_.find(v);
514
  CHECK(it != var_map_.end()) << "cannot find variable " << v->name_hint;
515
  return it->second;
516 517
}

518 519 520
llvm::Value* CodeGenLLVM::CreateCallExtern(const Call* op) {
  std::vector<llvm::Value*> arg_value;
  std::vector<llvm::Type*> arg_type;
521 522
  for (size_t i = 0; i < op->args.size(); ++i) {
    arg_value.push_back(MakeValue(op->args[i]));
523
    arg_type.push_back(arg_value.back()->getType());
524
  }
525 526 527 528 529 530 531 532 533 534
  llvm::FunctionType* ftype = llvm::FunctionType::get(
      LLVMType(op->type), arg_type, false);
  llvm::Function* f = module_->getFunction(op->name);
  if (f == nullptr) {
    f = llvm::Function::Create(
        ftype, llvm::Function::ExternalLinkage,
        op->name, module_.get());
  }
  llvm::CallInst* call = builder_->CreateCall(f, arg_value);
  return call;
535 536
}

537
llvm::Value* CodeGenLLVM::CreateIntrinsic(const Call* op) {
538
  if (op->is_intrinsic("llvm_intrin")) {
539
    CHECK_GE(op->args.size(), 2U);
540 541
    llvm::Intrinsic::ID id = static_cast<llvm::Intrinsic::ID>(
        op->args[0].as<UIntImm>()->value);
542
    uint64_t num_signature = op->args[1].as<UIntImm>()->value;
543
    std::vector<llvm::Value*> arg_value;
544 545
    std::vector<llvm::Type*> sig_type;
    for (size_t i = 2; i < op->args.size(); ++i) {
546
      arg_value.push_back(MakeValue(op->args[i]));
547 548 549
      if (i - 2 < num_signature) {
        sig_type.push_back(arg_value.back()->getType());
      }
550 551
    }
    llvm::Function* f = llvm::Intrinsic::getDeclaration(
552
        module_.get(), id, sig_type);
553
    return builder_->CreateCall(f, arg_value);
554
  } else if (op->is_intrinsic(Call::bitwise_and)) {
555
    return builder_->CreateAnd(MakeValue(op->args[0]), MakeValue(op->args[1]));
556
  } else if (op->is_intrinsic(Call::bitwise_or)) {
557
    return builder_->CreateOr(MakeValue(op->args[0]), MakeValue(op->args[1]));
558 559
  } else if (op->is_intrinsic(Call::bitwise_not)) {
    return builder_->CreateNot(MakeValue(op->args[0]));
560 561
  } else if (op->is_intrinsic(Call::bitwise_xor)) {
    return builder_->CreateXor(MakeValue(op->args[0]), MakeValue(op->args[1]));
562
  } else if (op->is_intrinsic(Call::shift_left)) {
563
    return builder_->CreateShl(MakeValue(op->args[0]), MakeValue(op->args[1]));
564
  } else if (op->is_intrinsic(Call::shift_right)) {
565 566
    if (op->args[0].type().is_int()) {
      return builder_->CreateAShr(MakeValue(op->args[0]), MakeValue(op->args[1]));
567
    } else {
568
      return builder_->CreateLShr(MakeValue(op->args[0]), MakeValue(op->args[1]));
569
    }
570 571
  } else if (op->is_intrinsic(intrinsic::tvm_storage_sync)) {
    return CreateStorageSync(op);
572
  } else if (op->is_intrinsic(intrinsic::tvm_address_of)) {
573 574
    const Load *l = op->args[0].as<Load>();
    CHECK(op->args.size() == 1 && l);
575 576 577 578 579 580 581
    llvm::Value* ptr = CreateBufferPtr(
        l->type, MakeValue(l->buffer_var), MakeValue(l->index));
    unsigned addrspace = llvm::dyn_cast<llvm::PointerType>(
        ptr->getType())->getAddressSpace();
    return builder_->CreatePointerCast(ptr, t_void_->getPointerTo(addrspace));
  } else if (op->is_intrinsic(Call::reinterpret) && is_zero(op->args[0])) {
    return llvm::Constant::getNullValue(t_void_p_);
582
  } else if (op->is_intrinsic(intrinsic::tvm_handle_is_null)) {
583
    return builder_->CreateIsNull(MakeValue(op->args[0]));
584 585 586 587 588 589 590 591
  } else if (op->is_intrinsic(intrinsic::tvm_if_then_else)) {
    using llvm::BasicBlock;
    BasicBlock* then_block = BasicBlock::Create(
        *ctx_, "if_then", function_);
    BasicBlock* else_block = BasicBlock::Create(
        *ctx_, "if_else", function_);
    BasicBlock* end_block = BasicBlock::Create(
        *ctx_, "if_end", function_);
592
    builder_->CreateCondBr(MakeValue(op->args[0]), then_block, else_block);
593 594
    builder_->SetInsertPoint(then_block);
    llvm::Value* then_value = MakeValue(op->args[1]);
595
    BasicBlock* then_value_block = builder_->GetInsertBlock();
596 597 598
    builder_->CreateBr(end_block);
    builder_->SetInsertPoint(else_block);
    llvm::Value* else_value = MakeValue(op->args[2]);
599
    BasicBlock* else_value_block = builder_->GetInsertBlock();
600 601
    builder_->CreateBr(end_block);
    builder_->SetInsertPoint(end_block);
602
    llvm::PHINode* value = builder_->CreatePHI(then_value->getType(), 2);
603 604
    value->addIncoming(then_value, then_value_block);
    value->addIncoming(else_value, else_value_block);
605
    return value;
606
  } else {
607 608
    LOG(FATAL) << "unknown intrinsic " << op->name;
    return nullptr;
609
  }
610 611
}

612 613 614 615 616 617 618 619 620 621 622 623 624 625
void CodeGenLLVM::Scalarize(const Expr& e,
                            std::function<void(int i, llvm::Value* v)> f) {
  if (const Ramp* ramp = e.as<Ramp>()) {
    for (int i = 0; i < ramp->type.lanes(); ++i) {
      Expr offset = arith::ComputeExpr<Add>(
          ramp->base,
          arith::ComputeExpr<Mul>(ramp->stride, i));
      f(i, MakeValue(offset));
    }
  } else {
    llvm::Value* value = MakeValue(e);
    for (int i = 0; i < e.type().lanes(); ++i) {
      f(i, builder_->CreateExtractElement(value, i));
    }
626 627 628
  }
}

629 630

// Visitors
631 632
llvm::Value* CodeGenLLVM::VisitExpr_(const Variable* op) {
  return GetVarValue(op);
633
}
634 635 636

llvm::Value* CodeGenLLVM::VisitExpr_(const Cast* op) {
  return CreateCast(op->value.type(), op->type, MakeValue(op->value));
637
}
638 639
llvm::Value* CodeGenLLVM::VisitExpr_(const IntImm* op) {
  return llvm::ConstantInt::getSigned(LLVMType(op->type), op->value);
640 641
}

642 643 644 645 646 647 648 649 650 651 652 653
llvm::Value* CodeGenLLVM::VisitExpr_(const UIntImm* op) {
  return llvm::ConstantInt::get(LLVMType(op->type), op->value);
}

llvm::Value* CodeGenLLVM::VisitExpr_(const FloatImm* op) {
  return llvm::ConstantFP::get(LLVMType(op->type), op->value);
}

llvm::Value* CodeGenLLVM::VisitExpr_(const StringImm* op) {
  return GetConstString(op->value);
}

654 655
#define DEFINE_CODEGEN_BINARY_OP(Op)                                    \
  llvm::Value* CodeGenLLVM::Create ## Op(                               \
656
      Type t, llvm::Value* a, llvm::Value *b) {                         \
657 658 659 660 661 662 663 664 665 666 667 668
    if (t.is_int()) {                                                   \
      if (t.bits() >= 32) {                                             \
        return builder_->CreateNSW ## Op (a, b);                        \
      } else {                                                          \
        return builder_->Create ## Op (a, b);                           \
      }                                                                 \
    } else if (t.is_uint()) {                                           \
      if (t.bits() >= 32) {                                             \
        return builder_->CreateNUW ## Op (a, b);                        \
      } else {                                                          \
        return builder_->Create ## Op (a, b);                           \
      }                                                                 \
669
    } else {                                                            \
670 671
      CHECK(t.is_float());                                              \
      return builder_->CreateF ## Op (a, b);                            \
672 673
    }                                                                   \
  }                                                                     \
674 675 676
  llvm::Value* CodeGenLLVM::VisitExpr_(const Op* op) {                  \
    return Create ## Op(op->type, MakeValue(op->a), MakeValue(op->b));  \
  }
677 678 679 680 681

DEFINE_CODEGEN_BINARY_OP(Add);
DEFINE_CODEGEN_BINARY_OP(Sub);
DEFINE_CODEGEN_BINARY_OP(Mul);

682 683 684 685 686 687 688 689 690 691 692 693 694 695 696
#define DEFINE_CODEGEN_CMP_OP(Op)                                       \
  llvm::Value* CodeGenLLVM::Create ## Op(                               \
      Type t, llvm::Value* a, llvm::Value* b) {                         \
    if (t.is_int()) {                                                   \
      return builder_->CreateICmpS ## Op (a, b);                        \
    } else if (t.is_uint()) {                                           \
      return builder_->CreateICmpU ## Op (a, b);                        \
    } else {                                                            \
      CHECK(t.is_float());                                              \
      return builder_->CreateFCmpO ## Op (a, b);                        \
    }                                                                   \
}                                                                       \
  llvm::Value* CodeGenLLVM::VisitExpr_(const Op* op) {                  \
    return Create ## Op(op->a.type(), MakeValue(op->a), MakeValue(op->b)); \
  }
697

698 699 700 701
DEFINE_CODEGEN_CMP_OP(LT);
DEFINE_CODEGEN_CMP_OP(LE);
DEFINE_CODEGEN_CMP_OP(GT);
DEFINE_CODEGEN_CMP_OP(GE);
702 703 704

llvm::Value* CodeGenLLVM::VisitExpr_(const Div* op) {
  llvm::Value* a = MakeValue(op->a);
705
  llvm::Value* b = MakeValue(op->b);
706
  int shift;
707 708
  if ((op->type.is_int() || op->type.is_uint()) &&
      is_const_power_of_two_integer(op->b, &shift)) {
709
    return builder_->CreateAShr(a, shift);
710 711 712 713
  } else if (op->type.is_int()) {
    return builder_->CreateSDiv(a, b);
  } else if (op->type.is_uint()) {
    return builder_->CreateUDiv(a, b);
714
  } else {
715 716
    CHECK(op->type.is_float());
    return builder_->CreateFDiv(a, b);
717 718 719 720
  }
}

llvm::Value* CodeGenLLVM::VisitExpr_(const Mod* op) {
721 722
  llvm::Value* a = MakeValue(op->a);
  llvm::Value* b = MakeValue(op->b);
723
  if (op->type.is_int()) {
724 725 726
    return builder_->CreateSRem(a, b);
  } else if (op->type.is_uint()) {
    return builder_->CreateURem(a, b);
727
  } else {
728 729
    CHECK(op->type.is_float());
    return builder_->CreateFRem(a, b);
730 731 732 733 734 735
  }
}

llvm::Value* CodeGenLLVM::VisitExpr_(const Min* op) {
  llvm::Value* a = MakeValue(op->a);
  llvm::Value* b = MakeValue(op->b);
736
  return builder_->CreateSelect(CreateLT(op->a.type(), a, b), a, b);
737 738 739 740 741
}

llvm::Value* CodeGenLLVM::VisitExpr_(const Max* op) {
  llvm::Value* a = MakeValue(op->a);
  llvm::Value* b = MakeValue(op->b);
742
  return builder_->CreateSelect(CreateGT(op->a.type(), a, b), a, b);
743 744 745
}

llvm::Value* CodeGenLLVM::VisitExpr_(const EQ* op) {
746 747 748 749
  llvm::Value* a = MakeValue(op->a);
  llvm::Value* b = MakeValue(op->b);
  if (op->a.type().is_int() || op->a.type().is_uint()) {
    return builder_->CreateICmpEQ(a, b);
750
  } else {
751
    return builder_->CreateFCmpOEQ(a, b);
752 753 754 755
  }
}

llvm::Value* CodeGenLLVM::VisitExpr_(const NE* op) {
756 757 758 759
  llvm::Value* a = MakeValue(op->a);
  llvm::Value* b = MakeValue(op->b);
  if (op->a.type().is_int() || op->a.type().is_uint()) {
    return builder_->CreateICmpNE(a, b);
760
  } else {
761
    return builder_->CreateFCmpONE(a, b);
762 763 764 765 766 767 768 769 770 771 772 773 774 775 776 777 778 779 780 781 782 783 784 785
  }
}

llvm::Value* CodeGenLLVM::VisitExpr_(const And* op) {
  return builder_->CreateAnd(MakeValue(op->a), MakeValue(op->b));
}

llvm::Value* CodeGenLLVM::VisitExpr_(const Or* op) {
  return builder_->CreateOr(MakeValue(op->a), MakeValue(op->b));
}

llvm::Value* CodeGenLLVM::VisitExpr_(const Not* op) {
  return builder_->CreateNot(MakeValue(op->a));
}

llvm::Value* CodeGenLLVM::VisitExpr_(const Select* op) {
  return builder_->CreateSelect(
      MakeValue(op->condition),
      MakeValue(op->true_value),
      MakeValue(op->false_value));
}

llvm::Value* CodeGenLLVM::VisitExpr_(const Let* op) {
  CHECK(!var_map_.count(op->var.get()));
786 787
  var_map_[op->var.get()] = MakeValue(op->value);
  align_map_[op->var.get()] = EvalModular(op->value, align_map_);
788 789 790
  return MakeValue(op->body);
}

791
llvm::Value* CodeGenLLVM::VisitExpr_(const Load* op) {
792
  Type t = op->type;
793 794 795 796 797 798 799 800 801 802 803
  int alignment, native_bits;
  bool is_volatile = volatile_buf_.count(op->buffer_var.get());
  GetAlignment(t, op->buffer_var.get(), op->index, &alignment, &native_bits);
  llvm::Value* buffer = MakeValue(op->buffer_var);
  llvm::Value* index = MakeValue(op->index);

  if (t.lanes() == 1) {
    llvm::Value* ptr = CreateBufferPtr(t, buffer, index);
    llvm::LoadInst* load = builder_->CreateAlignedLoad(ptr, alignment, is_volatile);
    AddAliasInfo(load, op->buffer_var.get(), op->index, t);
    return load;
804
  } else {
805 806 807 808 809 810 811 812 813 814 815 816 817
    // vector load
    unsigned addrspace = llvm::dyn_cast<llvm::PointerType>(
      buffer->getType())->getAddressSpace();
    if (const Ramp* ramp = op->index.as<Ramp>()) {
      if (is_one(ramp->stride)) {
        CHECK_EQ(ramp->lanes, t.lanes());
        llvm::Value* ptr = CreateBufferPtr(
            t.element_of(), buffer, MakeValue(ramp->base));
        ptr = builder_->CreatePointerCast(ptr, LLVMType(t)->getPointerTo(addrspace));
        llvm::LoadInst* load = builder_->CreateAlignedLoad(ptr, alignment, is_volatile);
        AddAliasInfo(load, op->buffer_var.get(), op->index, t);
        return load;
      }
818 819
    }
  }
820 821 822 823 824 825 826 827 828 829 830 831
  // scalarized load.
  int basic_align = t.bits() / 8;
  llvm::Value* ret = llvm::UndefValue::get(LLVMType(t));
  auto f = [&](int i, llvm::Value* index) {
    llvm::Value* ptr = CreateBufferPtr(t.element_of(), buffer, index);
    llvm::LoadInst* load = builder_->CreateAlignedLoad(
        ptr, basic_align, is_volatile);
    ret = builder_->CreateInsertElement(ret, load, ConstInt32(i));
    AddAliasInfo(load, op->buffer_var.get(), Expr(), t);
  };
  this->Scalarize(op->index, f);
  return ret;
832 833
}

834 835 836 837 838 839 840 841 842 843
llvm::Value* CodeGenLLVM::VisitExpr_(const Call* op) {
  if (op->call_type == Call::Intrinsic ||
      op->call_type == Call::PureIntrinsic) {
    return CreateIntrinsic(op);
  } else if (op->call_type == Call::Extern ||
             op->call_type == Call::PureExtern) {
    return CreateCallExtern(op);
  } else {
    LOG(FATAL) << "Unknown call type ";
    return nullptr;
844 845 846
  }
}

847 848 849 850 851 852
llvm::Value* CodeGenLLVM::VisitExpr_(const Ramp* op) {
  llvm::Value* vec = llvm::UndefValue::get(LLVMType(op->type));
  for (int i = 0; i < op->lanes; ++i) {
    vec = builder_->CreateInsertElement(
        vec, MakeValue(op->base + op->stride * make_const(op->stride.type(), i)),
        ConstInt32(i));
853
  }
854
  return vec;
855 856
}

857 858
llvm::Value* CodeGenLLVM::VisitExpr_(const Broadcast* op) {
  return CreateBroadcast(MakeValue(op->value), op->lanes);
859 860 861
}

void CodeGenLLVM::VisitStmt_(const Store* op) {
862
  CHECK(is_one(op->predicate));
863
  Type t = op->value.type();
864 865 866 867 868 869
  int alignment, native_bits;
  bool is_volatile = volatile_buf_.count(op->buffer_var.get());
  GetAlignment(t, op->buffer_var.get(), op->index, &alignment, &native_bits);
  llvm::Value* buffer = MakeValue(op->buffer_var);
  llvm::Value* index = MakeValue(op->index);
  llvm::Value* value = MakeValue(op->value);
870

871 872 873 874 875
  if (t.lanes() == 1) {
    llvm::Value* ptr = CreateBufferPtr(t, buffer, index);
    llvm::StoreInst* store = builder_->CreateAlignedStore(value, ptr, alignment, is_volatile);
    AddAliasInfo(store, op->buffer_var.get(), op->index, op->value.type());
    return;
876
  } else {
877 878 879 880 881 882 883 884 885 886 887 888 889 890
    // vector store
    unsigned addrspace = llvm::dyn_cast<llvm::PointerType>(
        buffer->getType())->getAddressSpace();
    if (const Ramp* ramp = op->index.as<Ramp>()) {
      if (is_one(ramp->stride)) {
        CHECK_EQ(ramp->lanes, t.lanes());
        llvm::Value* ptr = CreateBufferPtr(
            t.element_of(), buffer, MakeValue(ramp->base));
        ptr = builder_->CreatePointerCast(ptr, LLVMType(t)->getPointerTo(addrspace));
        llvm::StoreInst* store = builder_->CreateAlignedStore(value, ptr, alignment, is_volatile);
        AddAliasInfo(store, op->buffer_var.get(), op->index, op->value.type());
        return;
      }
    }
891
  }
892 893 894 895 896 897 898 899 900 901 902
  CHECK_GE(t.bits(), 8);
  // scalarized store.
  int basic_align = t.bits() / 8;
  auto f = [&](int i, llvm::Value* index) {
    llvm::Value* ptr = CreateBufferPtr(t.element_of(), buffer, index);
    llvm::StoreInst* store = builder_->CreateAlignedStore(
        builder_->CreateExtractElement(value, i),
        ptr, basic_align, is_volatile);
    AddAliasInfo(store, op->buffer_var.get(), Expr(), op->value.type());
  };
  this->Scalarize(op->index, f);
903 904 905 906
}

void CodeGenLLVM::VisitStmt_(const For* op) {
  CHECK(is_zero(op->min));
907 908 909 910 911 912
  if (op->for_type == ForType::Unrolled) {
    LOG(WARNING) << "Unroll hint get ignore at CodeGenLLVM backend, "
                 << " consider set unroll_explicit=True";
  } else {
    CHECK(op->for_type == ForType::Serial);
  }
913 914
  CreateSerialFor(MakeValue(op->min), MakeValue(op->extent),
                  ConstInt32(1), op->loop_var, op->body);
915 916
}

917

918 919
void CodeGenLLVM::VisitStmt_(const IfThenElse* op) {
  using llvm::BasicBlock;
920
  llvm::Value* cond = MakeValue(op->condition);
921 922 923 924 925
  BasicBlock* then_block = BasicBlock::Create(
      *ctx_, "if_then", function_);
  BasicBlock* end_block = BasicBlock::Create(
      *ctx_, "if_end", function_);
  if (op->else_case.defined()) {
926 927 928 929 930 931
    BasicBlock* else_block = BasicBlock::Create(
        *ctx_, "if_else", function_);
    builder_->CreateCondBr(cond, then_block, else_block);
    builder_->SetInsertPoint(then_block);
    this->VisitStmt(op->then_case);
    builder_->CreateBr(end_block);
932 933 934
    builder_->SetInsertPoint(else_block);
    this->VisitStmt(op->else_case);
    builder_->CreateBr(end_block);
935 936 937 938 939
  } else {
    builder_->CreateCondBr(cond, then_block, end_block, md_very_likely_branch_);
    builder_->SetInsertPoint(then_block);
    this->VisitStmt(op->then_case);
    builder_->CreateBr(end_block);
940 941 942 943
  }
  builder_->SetInsertPoint(end_block);
}

944

945 946 947
void CodeGenLLVM::VisitStmt_(const Allocate* op) {
  CHECK(!is_zero(op->condition));
  llvm::Value* buf = nullptr;
948 949 950 951 952 953
  if (op->new_expr.defined()) {
    CHECK_EQ(op->free_function, "nop");
    buf = MakeValue(op->new_expr);
  } else {
    int32_t constant_size = op->constant_allocation_size();
    CHECK_GT(constant_size, 0)
954
        << "Can only handle constant size stack allocation";
955 956
    StorageInfo& info = alloc_storage_info_[op->buffer_var.get()];
    if (constant_size % 4 == 0 && info.alignment == 0) {
957
      info.alignment = GetTempAllocaAlignment(op->type, constant_size);
958
    }
959 960 961 962 963 964
    // maximum necessary alignment in the NV devices
    if (info.alignment > 16) {
      info.alignment = 16;
    }
    llvm::AllocaInst* alloca = builder_->CreateAlloca(
        LLVMType(op->type), ConstInt32(constant_size));
965 966 967 968
    if (alloca->getAlignment() < static_cast<uint32_t>(info.alignment)) {
      alloca->setAlignment(info.alignment);
    }
    info.alignment = alloca->getAlignment();
969
    buf = alloca;
970
  }
971 972 973
  buf = builder_->CreatePointerCast(
      buf, LLVMType(op->type)->getPointerTo(
          buf->getType()->getPointerAddressSpace()));
974 975
  CHECK(!var_map_.count(op->buffer_var.get()));
  var_map_[op->buffer_var.get()] = buf;
976
  this->VisitStmt(op->body);
977 978
}

979
void CodeGenLLVM::VisitStmt_(const AttrStmt* op) {
980
  if (op->attr_key == attr::thread_extent) {
981 982 983 984 985 986 987
    IterVar iv(op->node.node_);
    if (iv->thread_tag.length() != 0) {
      if (!var_map_.count(iv->var.get())) {
        var_map_[iv->var.get()] = GetThreadIndex(iv);
      }
    }
  } else if (op->attr_key == ir::attr::storage_scope) {
988 989
    const Variable* v = op->node.as<Variable>();
    CHECK(v);
990 991
    alloc_storage_info_[v].scope =
        runtime::StorageScope::make(op->value.as<StringImm>()->value);
992 993 994 995 996
  } else if (op->attr_key == ir::attr::storage_alignment) {
    const Variable* v = op->node.as<Variable>();
    CHECK(v);
    alloc_storage_info_[v].alignment =
        static_cast<int>(op->value.as<IntImm>()->value);
997 998 999 1000
  } else if (op->attr_key == ir::attr::volatile_scope) {
    const Variable* v = op->node.as<Variable>();
    CHECK(v);
    volatile_buf_.insert(v);
1001
  }
1002
  this->VisitStmt(op->body);
1003 1004
}

1005
void CodeGenLLVM::VisitStmt_(const AssertStmt* op) {
1006 1007 1008 1009 1010
  // Detect useful invariant pattern and use them to visit child.
  // Pattern: Var % const  == 0
  // TODO(tqchen) move these pattern to a generic scope info visitor.
  if (const EQ* eq = op->condition.as<EQ>()) {
    const Mod* mod = eq->a.as<Mod>();
1011
    int64_t factor = 0, offset = 0;
1012 1013 1014 1015 1016 1017 1018 1019 1020 1021 1022 1023 1024 1025 1026 1027 1028 1029 1030
    if (mod && arith::GetConst(eq->b, &offset)) {
      const Variable *var = mod->a.as<Variable>();
      if (var && arith::GetConst(mod->b, &factor)) {
        arith::ModularEntry old = align_map_[var];
        if (factor > old.coeff) {
          arith::ModularEntry e;
          e.coeff = static_cast<int>(factor);
          e.base = static_cast<int>(offset);
          // new alignment info,
          align_map_[var] = e;
          this->VisitStmt(op->body);
          // restore old info
          align_map_[var] = old;
          return;
        }
      }
    }
  }
  this->VisitStmt(op->body);
1031 1032
}

1033
void CodeGenLLVM::VisitStmt_(const LetStmt* op) {
1034
  CHECK(!var_map_.count(op->var.get()));
1035
  CHECK(!align_map_.count(op->var.get()));
1036 1037 1038 1039 1040
  if (op->var.type().is_handle()) {
    if (!is_restricted_) {
      alias_var_set_.insert(op->var.get());
    }
  }
1041 1042
  var_map_[op->var.get()] = MakeValue(op->value);
  align_map_[op->var.get()] = EvalModular(op->value, align_map_);
1043
  this->VisitStmt(op->body);
1044
}
1045

1046
void CodeGenLLVM::VisitStmt_(const Block* op) {
1047 1048 1049 1050
  this->VisitStmt(op->first);
  if (op->rest.defined()) {
    this->VisitStmt(op->rest);
  }
1051
}
1052

1053
void CodeGenLLVM::VisitStmt_(const Evaluate* op) {
1054 1055
  MakeValue(op->value);
}
1056

1057
void CodeGenLLVM::VisitStmt_(const ProducerConsumer* op) {
1058
  this->VisitStmt(op->body);
1059 1060 1061 1062
}
}  // namespace codegen
}  // namespace tvm
#endif  // TVM_LLVM_VERSION