Создаем свой собственный язык программирования с использованием LLVM. Часть 3: Генерация кода

Type* BuiltinTypeAST::getType() {
  static Type* builtinTypes[] = {
    Type::getVoidTy(getGlobalContext()),
    Type::getInt1Ty(getGlobalContext()),
    Type::getInt32Ty(getGlobalContext()),
    Type::getDoubleTy(getGlobalContext()),
    Type::getInt8Ty(getGlobalContext()),
    Type::getInt8PtrTy(getGlobalContext())
  };

  if (ThisType) {
    return ThisType;
  }

  return ThisType = builtinTypes[TypeKind];
}

Type* FuncTypeAST::getType() {
  // Генерируем тип только один раз
  if (ThisType) {
    return ThisType;
  }

  // Если ReturnType не указан, то указываем "void"
  Type* returnType = (ReturnType ? ReturnType->getType() : 
    Type::getVoidTy(getGlobalContext()));

  if (Params.empty()) {
    // Возвращаем функцию без параметров
    return ThisType = FunctionType::get(returnType, false);
  }
  
  std::vector< Type* > params;

  // Создаем список параметров
  for (ParameterList::iterator it = Params.begin(), 
    end = Params.end(); it != end; ++it) {
    params.push_back((*it)->Param->getType());
  }

  // Создаем тип для функции с параметрами
  return ThisType = FunctionType::get(returnType, params, false);
}

/// Сгенерировать код для целочисленной константы
ConstantInt* getConstInt(uint64_t value) {
  return ConstantInt::get(Type::getInt32Ty(getGlobalContext()),
                          value, true);
}

/// Конвертировать тип выражения в "bool"
/// param[in] val — значение для конвертации
/// param[in] type — тип изначального выражения
/// param[in] builder — конструктор LLVM IR
Value* promoteToBool(Value* val,
                     TypeAST* type,
                     IRBuilder< >& builder) {
  if (type == BuiltinTypeAST::get(TypeAST::TI_Bool)) {
    // Это уже "bool"
    return val;
  }

  if (type->isInt()) {
    // Для целочисленного типа генерируем сравнение с 0
    return builder.CreateICmpNE(val,
                                ConstantInt::get(
                                  type->getType(),
                                  0)
                               );
  } else {
    assert(type->isFloat());
    // Для числа с плавающей точкой генерируем сравнение с 0.0
    return builder.CreateFCmpUNE(val, ConstantFP::get(
      Type::getDoubleTy(getGlobalContext()), 0.0));
  }
}
Рассмотрим реализацию генерации кода для самих выражений:
Value* ExprAST::getLValue(SLContext& ) {
  assert(0 && "");
  return nullptr;
}

Value* IntExprAST::getRValue(SLContext& ) {
  // Создать целочисленную константу нужного типа с нужным 
  // значением
  return ConstantInt::get(ExprType->getType(), Val, true);
}

Value* FloatExprAST::getRValue(SLContext& ) {
  // Создать константу для числа с плавающей точкой нужного типа с 
  // нужным значением
  return ConstantFP::get(ExprType->getType(), Val);
}

Value* IdExprAST::getLValue(SLContext& Context) {
  // Получить адрес переменной (сам адрес сгенерирует SymbolAST, 
  // на который ссылается переменная)
  return ThisSym->getValue(Context);
}

Value* IdExprAST::getRValue(SLContext& Context) {
  if (isa<FuncDeclAST>(ThisSym)) {
    // Особая обработка для функций
    return ThisSym->getValue(Context);
  }

  // Для остальных вариантов нужно сгенерировать инструкцию "load"
  return Context.TheBuilder->CreateLoad(
    ExprType->getType(),
    ThisSym->getValue(Context), 
    StringRef(Val->Id, Val->Length)
  );
}

Value* CastExprAST::getRValue(SLContext& Context) {
  // Сначала проверяем, что это преобразование в целочисленный тип
  if (ExprType->isInt()) {
    if (Val->ExprType->isBool()) {
      // Если исходный тип "bool", то дополняем 0
      return Context.TheBuilder->CreateZExt(
        Val->getRValue(Context), 
        ExprType->getType()
      );
    }

    assert(Val->ExprType->isFloat());
    // Генерируем преобразование "float" в "int"
    return Context.TheBuilder->CreateFPToSI(
      Val->getRValue(Context), 
      ExprType->getType()
    );
  }

  if (ExprType->isBool()) {
    // Для преобразования в "bool"
    return promoteToBool(Val->getRValue(Context), Val->ExprType, 
      *Context.TheBuilder);
  } else if (Val->ExprType->isInt()) {
    // Преобразование "int" в "float" 
    return Context.TheBuilder->CreateSIToFP(
      Val->getRValue(Context), 
      ExprType->getType()
    );
  } else if (Val->ExprType->isBool()) {
    // Преобразование "bool" в "float"
    return Context.TheBuilder->CreateUIToFP(
      Val->getRValue(Context),
      ExprType->getType()
    );
  }

  assert(0 && "should never be reached");
  return nullptr;
}

Value* UnaryExprAST::getRValue(SLContext& Context) {
  assert(0 && "Should never happen");
  return nullptr;
}

Value* BinaryExprAST::getRValue(SLContext& Context) {
  // Сначала необходимо проверить все специальные случаи

  // =
  if (Op == tok::Assign) {
    
    // Генерируем код для правой части выражения
    Value* right = RightExpr->getRValue(Context);
    // Получаем адрес по которому нужно сохранить значение
    Value* res = LeftExpr->getLValue(Context);

    // Генерируем инструкцию "store"
    Context.TheBuilder->CreateStore(right, res);
    return right;
  }

  // ,
  if (Op == tok::Comma) {
    // Генерируем код для левого и правого операнда
    LeftExpr->getRValue(Context);
    Value* rhs = RightExpr->getRValue(Context);
    // Возвращаем правый операнд
    return rhs;
  }

  // Постфиксная версия операторов ++ и --
  if (Op == tok::PlusPlus || Op == tok::MinusMinus) {
    // Получаем адрес переменной, а так же ее значение
    Value* var = LeftExpr->getLValue(Context);
    Value* val = LeftExpr->getRValue(Context);

    if (Op == tok::PlusPlus) {
      // Создать целочисленную константу 1 и прибавить ее к 
      // загруженному ранее значению
      Value* tmp = getConstInt(1);
      tmp = Context.TheBuilder->CreateAdd(val, tmp, "inctmp");
      // Сохранить новое значение и вернуть старое значение
      Context.TheBuilder->CreateStore(tmp, var);
      return val;
    } else {
      // Создать целочисленную константу -1 и прибавить ее к 
      // загруженному ранее значению
      Value* tmp = getConstInt(~0ULL);
      tmp = Context.TheBuilder->CreateAdd(val, tmp, "dectmp");
      // Сохранить новое значение и вернуть старое значение
      Context.TheBuilder->CreateStore(tmp, var);
      return val;
    }
  }

  // ||
  if (Op == tok::LogOr) {
    // Псевдокод для оператора ||

    //if (bool result = (left != 0))
    //  return result;
    //else
    //  return (right != 0);

    // Генерация кода для левого операнда
    Value* lhs = LeftExpr->getRValue(Context);
    // Произвести преобразование в "bool"
    lhs = promoteToBool(lhs, LeftExpr->ExprType, 
                        *Context.TheBuilder);

    // Создать блоки для ветки "false" и "result" (куда будет 
    // возвращено управление для продолжения работы программы)
    BasicBlock* condBB = Context.TheBuilder->GetInsertBlock();
    BasicBlock* resultBB = BasicBlock::Create(
      getGlobalContext(),
      "result"
    );
    BasicBlock* falseBB = BasicBlock::Create(
      getGlobalContext(),
      "false"
    );

    // Создать условный переход к "result" или "false" в 
    // зависимости от истинности левого операнда
    Context.TheBuilder->CreateCondBr(lhs, resultBB, falseBB);

    // Добавить блок "false" к функции (для которой генерируем код) 
    // и переходим к генерации кода для нее
    Context.TheFunction->getBasicBlockList().push_back(falseBB);
    Context.TheBuilder->SetInsertPoint(falseBB);
    // Генерация кода для правого операнда
    Value* rhs = RightExpr->getRValue(Context);
    // Обновляем блок "false", т. к. код для правого операнда мог 
    // ее сменить
    falseBB = Context.TheBuilder->GetInsertBlock();
    // Произвести преобразование в "bool"
    rhs = promoteToBool(
      rhs,
      RightExpr->ExprType,
      *Context.TheBuilder
    );
    // Производим безусловный переход к "result"
    Context.TheBuilder->CreateBr(resultBB);

    // Добавить блок "result" к функции (для которой генерируем код)
    // и переходим к генерации кода для нее
    Context.TheFunction->getBasicBlockList().push_back(resultBB);
    Context.TheBuilder->SetInsertPoint(resultBB);

    // Создаем PHI значение, которое будет содержать значение в 
    // зависимости от того какая ветка была выбрана при обработке
    // изначального условия
    PHINode* PN = Context.TheBuilder->CreatePHI(
      Type::getInt1Ty(getGlobalContext()),
      2
    );

    PN->addIncoming(lhs, condBB);
    PN->addIncoming(rhs, falseBB);

    return PN;
  }

  // &&
  if (Op == tok::LogAnd) {
    // Псевдокод для оператора &&

    //if (left != 0 && right != 0)
    //    return true;
    //else
    //  return false;

    // Генерируем код для левой операнда
    Value* lhs = LeftExpr->getRValue(Context);
    // Произвести преобразование в "bool"
    lhs = promoteToBool(
      lhs,
      LeftExpr->ExprType,
      *Context.TheBuilder
    );

    // Создать блоки для ветки "true" и "result" (куда будет 
    // возвращено управление для продолжения работы программы)
    BasicBlock* condBB = Context.TheBuilder->GetInsertBlock();
    BasicBlock* resultBB = BasicBlock::Create(
      getGlobalContext(),
      "result"
    );
    BasicBlock* trueBB = BasicBlock::Create(
      getGlobalContext(),
      "true"
    );

    // Создать условный переход к "true" или "result" в 
    // зависимости от истинности левого операнда
    Context.TheBuilder->CreateCondBr(lhs, trueBB, resultBB);

    // Добавить блок "true" к функции (для которой генерируем код) 
    // и переходим к генерации кода для нее
    Context.TheFunction->getBasicBlockList().push_back(trueBB);
    Context.TheBuilder->SetInsertPoint(trueBB);
    // Генерация кода для правого операнда
    Value* rhs = RightExpr->getRValue(Context);
    // Обновляем блок "true", т. к. код для правого операнда мог 
    // ее сменить
    trueBB = Context.TheBuilder->GetInsertBlock();
    // Произвести преобразование в "bool"
    rhs = promoteToBool(
      rhs,
      RightExpr->ExprType,
      *Context.TheBuilder
    );
    // Производим безусловный переход к "result"
    Context.TheBuilder->CreateBr(resultBB);

    // Добавить блок "result" к функции (для которой генерируем 
    // код) и переходим к генерации кода для нее
    Context.TheFunction->getBasicBlockList().push_back(resultBB);
    Context.TheBuilder->SetInsertPoint(resultBB);

    // Создаем PHI значение, которое будет содержать значение в 
    // зависимости от того какая ветка была выбрана при обработке 
    // изначального условия
    PHINode* PN = Context.TheBuilder->CreatePHI(
      Type::getInt1Ty(getGlobalContext()),
      2
    );

    PN->addIncoming(lhs, condBB);
    PN->addIncoming(rhs, trueBB);

    return PN;
  }

  // Генерируем код для обоих операндов
  Value* lhs = LeftExpr->getRValue(Context);
  Value* rhs = RightExpr->getRValue(Context);

  // Проверяем тип выражения на то, что это "int"
  if (LeftExpr->ExprType == BuiltinTypeAST::get(TypeAST::TI_Int)) {
    // Генерация кода в соответствии с операцией
    switch (Op) {
      case tok::Plus:
        return Context.TheBuilder->CreateAdd(lhs, rhs, "addtmp");
      case tok::Minus:
        return Context.TheBuilder->CreateSub(lhs, rhs, "subtmp");
      case tok::Mul:
        return Context.TheBuilder->CreateMul(lhs, rhs, "multmp");
      case tok::Div:
        return Context.TheBuilder->CreateSDiv(lhs, rhs, "divtmp");
      case tok::Mod:
        return Context.TheBuilder->CreateSRem(lhs, rhs, "remtmp");
      case tok::BitOr:
        return Context.TheBuilder->CreateOr(lhs, rhs, "ortmp");
      case tok::BitAnd:
        return Context.TheBuilder->CreateAnd(lhs, rhs, "andtmp");
      case tok::BitXor:
        return Context.TheBuilder->CreateXor(lhs, rhs, "xortmp");
      case tok::LShift:
        return Context.TheBuilder->CreateShl(lhs, rhs, "shltmp");
      case tok::RShift:
        return Context.TheBuilder->CreateAShr(lhs, rhs, "shrtmp");
      case tok::Less:
        return Context.TheBuilder->CreateICmpSLT(lhs, rhs, "cmptmp");
      case tok::Greater:
        return Context.TheBuilder->CreateICmpSGT(lhs, rhs, "cmptmp");
      case tok::LessEqual:
        return Context.TheBuilder->CreateICmpSLE(lhs, rhs, "cmptmp");
      case tok::GreaterEqual:
        return Context.TheBuilder->CreateICmpSGE(lhs, rhs, "cmptmp");
      case tok::Equal:
        return Context.TheBuilder->CreateICmpEQ(lhs, rhs, "cmptmp");
      case tok::NotEqual:
        return Context.TheBuilder->CreateICmpNE(lhs, rhs, "cmptmp");
      default:
        assert(0 && "Invalid integral binary operator");
        return nullptr;
    }
  }
  
  // Генерация кода в соответствии с операцией
  switch (Op) {
    case tok::Plus:
      return Context.TheBuilder->CreateFAdd(lhs, rhs, "addtmp");
    case tok::Minus:
      return Context.TheBuilder->CreateFSub(lhs, rhs, "subtmp");
    case tok::Mul:
      return Context.TheBuilder->CreateFMul(lhs, rhs, "multmp");
    case tok::Div:
      return Context.TheBuilder->CreateFDiv(lhs, rhs, "divtmp");
    case tok::Mod:
      return Context.TheBuilder->CreateFRem(lhs, rhs, "remtmp");
    case tok::Less:
      return Context.TheBuilder->CreateFCmpULT(lhs, rhs, "cmptmp");
    case tok::Greater:
      return Context.TheBuilder->CreateFCmpUGT(lhs, rhs, "cmptmp");
    case tok::LessEqual:
      return Context.TheBuilder->CreateFCmpULE(lhs, rhs, "cmptmp");
    case tok::GreaterEqual:
      return Context.TheBuilder->CreateFCmpUGE(lhs, rhs, "cmptmp");
    case tok::Equal:
      return Context.TheBuilder->CreateFCmpUEQ(lhs, rhs, "cmptmp");
    case tok::NotEqual:
      return Context.TheBuilder->CreateFCmpUNE(lhs, rhs, "cmptmp");
    default:
      assert(0 && "Invalid floating point binary operator");
      return nullptr;
  }
}

/// Генерация кода для тернарного оператора (в отличии от "if" 
/// данный оператор возвращает результирующее значение и может 
/// быть использован в других выражениях)
/// param[in] Context - контекст
/// param[in] Cond — условное выражение
/// param[in] IfExpr — выражение, если условие истинно
/// param[in] ElseExpr — выражение, если условие ложно
/// param[in] isLValue - true — если нужен адрес (или lvalue)
Value* generateCondExpr(
  SLContext& Context,
  ExprAST* Cond,
  ExprAST* IfExpr, 
  ExprAST* ElseExpr,
  bool isLValue) {
  // Генерация кода для условия
  Value* cond = Cond->getRValue(Context);
  // Произвести преобразование в "bool"
  cond = promoteToBool(cond, Cond->ExprType, *Context.TheBuilder);

  // Создаем блоки для веток "then", "else" и "ifcont"
  BasicBlock* thenBB = BasicBlock::Create(
    getGlobalContext(),
    "then", 
    Context.TheFunction
  );
  BasicBlock* elseBB = BasicBlock::Create(
    getGlobalContext(), 
    "else"
  );
  BasicBlock* mergeBB = BasicBlock::Create(
    getGlobalContext(), 
    "ifcont"
  );

  // Создать условный переход на "then" или "else", в зависимости
  // от истинности условия
  Context.TheBuilder->CreateCondBr(cond, thenBB, elseBB);
  // Set insert point to a then branch
  Context.TheBuilder->SetInsertPoint(thenBB);

  // Генерация кода для ветки "then"
  Value* thenValue;
  
  // Генерируем lvalue или rvalue
  if (isLValue) {
    thenValue = IfExpr->getLValue(Context);
  } else {
    thenValue = IfExpr->getRValue(Context);
  }

  // Создаем безусловный переход на "ifcont" и обновляем блок 
  // "then", т. к. он мог смениться
  Context.TheBuilder->CreateBr(mergeBB);
  thenBB = Context.TheBuilder->GetInsertBlock();

  // Добавить блок "else" к функции (для которой генерируем код) 
  // и переходим к генерации кода для нее
  Context.TheFunction->getBasicBlockList().push_back(elseBB);
  Context.TheBuilder->SetInsertPoint(elseBB);

  Value* elseValue;
  
  // Генерируем lvalue или rvalue
  if (isLValue) {
    elseValue = ElseExpr->getLValue(Context);
  } else {
    elseValue = ElseExpr->getRValue(Context);
  }

  // Создаем безусловный переход на "ifcont" и обновляем блок 
  // "else", т. к. он мог смениться
  Context.TheBuilder->CreateBr(mergeBB);
  elseBB = Context.TheBuilder->GetInsertBlock();

  // Создаем безусловный переход на "ifcont" и обновляем блок 
  // "else", т. к. он мог смениться
  Context.TheFunction->getBasicBlockList().push_back(mergeBB);
  Context.TheBuilder->SetInsertPoint(mergeBB);

  // Если результат выражения имеет тип "void", то мы больше ничего
  // не делаем
  if (!IfExpr->ExprType || IfExpr->ExprType->isVoid()) {
    return nullptr;
  }

  // Создаем PHI значение, которое будет содержать значение в 
  // зависимости от того какая ветка была выбрана при обработке
  // изначального условия
  PHINode* PN;
  
  if (isLValue) {
    // Для lvalue тип выражения является указателем
    PN = Context.TheBuilder->CreatePHI(
      PointerType::get(IfExpr->ExprType->getType(), 0),
      2
    );
  } else {
    PN = Context.TheBuilder->CreatePHI(
      IfExpr->ExprType->getType(),
      2
    );
  }

  PN->addIncoming(thenValue, thenBB);
  PN->addIncoming(elseValue, elseBB);
  
  return PN;
}

Value* CondExprAST::getLValue(SLContext& Context) {
  return generateCondExpr(Context, Cond, IfExpr, ElseExpr, true);
}

Value* CondExprAST::getRValue(SLContext& Context) {
  return generateCondExpr(Context, Cond, IfExpr, ElseExpr, false);
}

Value* CallExprAST::getRValue(SLContext& Context) {
  Value* callee = nullptr;
  std::vector< Value* > args;
  ExprList::iterator it = Args.begin();

  assert(isa<FuncDeclAST>(CallFunc));
  FuncDeclAST* funcDecl = (FuncDeclAST*)CallFunc;
  Type* funcRawType = CallFunc->getType()->getType();
  assert(isa<FunctionType>(funcRawType));
  FunctionType* funcType = static_cast<FunctionType*>(funcRawType);

  // Получаем адрес функции
  callee = CallFunc->getValue(Context);

  // Производим генерацию кода для каждого аргумента функции и 
  // добавляем их к списку аргументов функции
  for (ExprList::iterator end = Args.end(); it != end; ++it) {
    Value* v = (*it)->getRValue(Context);
    args.push_back(v);
  }
  
  // Генерируем вызов функции
  return Context.TheBuilder->CreateCall(funcType, callee, args);
}

Value* StmtAST::generateCode(SLContext& Context) {
  assert(0 && "StmtAST::generateCode should never be reached");
  return nullptr;
}

Value* ExprStmtAST::generateCode(SLContext& Context) {
  if (Expr) {
    // Генерация кода для выражения
    return Expr->getRValue(Context);
  }
  
  return nullptr;
}

llvm::Value* BlockStmtAST::generatePartialCode(SLContext& Context, 
  StmtList::iterator it, StmtList::iterator end) {
  // Инициализируем блоки "break", "continue" и "return" для 
  // LandingPadAST текущего блока на основе родительского блока
  LandingPadAST* parent = LandingPad->Prev;
  LandingPad->BreakLoc = parent->BreakLoc;
  LandingPad->ContinueLoc = parent->ContinueLoc;
  LandingPad->ReturnLoc = parent->ReturnLoc;

  // Создаем новый блок FallthroughLoc (этот блок может быть 
  // использован в дочерних инструкциях, в качестве точки возврата 
  // (например для выхода из цикла))
  LandingPad->FallthroughLoc = BasicBlock::Create(
    getGlobalContext(),
    "block"
  );

  // Генерация кода для всех вложенных инструкций
  for (; it != end; ++it) {
    // Сохраняем FallthroughLoc (т. к. при использовании его 
    // вложенная инструкция должна будет его обнулить)
    BasicBlock* fallthroughBB = LandingPad->FallthroughLoc;
    lastFallThrough = LandingPad->FallthroughLoc;

    // Генерируем код для вложенной инструкции
    (*it)->generateCode(Context);

    // Проверяем была ли FallthroughLoc использована во вложенной 
    // инструкции или нет
    if (!LandingPad->FallthroughLoc) {
      // Была. Поэтому нужно добавить данный блок в конец функции, 
      // как ее часть и задать его в качестве точки для вставки
      // нового кода
      Context.TheFunction->getBasicBlockList().push_back(
        fallthroughBB
      );
      Context.TheBuilder->SetInsertPoint(fallthroughBB);

      // Записать в FallthroughLoc новый созданный блок, для 
      // последующего использования во вложенных инструкциях
      LandingPad->FallthroughLoc = BasicBlock::Create(
        getGlobalContext(),
        "block"
      );
    }
  }

  // Делаем подсчет количество "break" "continue" и "return" 
  // инструкций в данном блоке (в последующих статьях будет 
  // ясно зачем они нужны)
  parent->Breaks += LandingPad->Breaks;
  parent->Continues += LandingPad->Continues;
  parent->Returns += LandingPad->Returns;

  // Проверяем, что текущий блок имеет инструкцию завершения блока
  // (условный или безусловный переход)
  if (!Context.TheBuilder->GetInsertBlock()->getTerminator()) {
    // Нет. Генерируем инструкцию перехода на FallthroughLoc 
    // родительского блока и помечаем, ее как использованную 
    // (путем присвоения nullptr)
    Context.TheBuilder->CreateBr(parent->FallthroughLoc);
    parent->FallthroughLoc = nullptr;
    
    // Если FallthroughLoc, которую мы создали для вложенных 
    // инструкций не была использована, то производим ее очистку
    if (!LandingPad->FallthroughLoc->hasNUsesOrMore(1)) {
      delete LandingPad->FallthroughLoc;
    }
  // Проверяем, что  FallthroughLoc был использован во вложенных 
  // инструкциях
  } else if (LandingPad->FallthroughLoc->hasNUsesOrMore(1)) {
    // Был использован, нужно добавить его в конец функции, 
    // установить его в качестве места вставки нового кода, а 
    // также создаем безусловный переход на FallthroughLoc
    // родительского блока, а так же помечаем его как 
    // использованную (путем присвоения nullptr)
    Context.TheFunction->getBasicBlockList().push_back(
      LandingPad->FallthroughLoc
    );
    Context.TheBuilder->SetInsertPoint(LandingPad->FallthroughLoc);
    Context.TheBuilder->CreateBr(parent->FallthroughLoc);
    parent->FallthroughLoc = nullptr;
  } else {
    // Нет. Производим ее очистку
    delete LandingPad->FallthroughLoc;
  }

  return nullptr;
}

Value* BlockStmtAST::generateCode(SLContext& Context) {
  return generatePartialCode(Context, Body.begin(), Body.end());
}

Value* DeclStmtAST::generateCode(SLContext& Context) {
  // Генерируем код для каждого объявления
  for (SymbolList::iterator it = Decls.begin(), end = Decls.end();
    it != end; ++it) {
    (*it)->generateCode(Context);
  }

  return nullptr;
}

Value* LandingPadAST::getReturnValue() {
  LandingPadAST* prev = this;

  // Ищем LandingPadAST самого верхнего уровня (блок тела самой 
  // функции)
  while (prev->Prev) {
    prev = prev->Prev;
  }

  // Возвращаем (адрес переменной) возвращаемое значение функции
  return prev->ReturnValue;
}

Value* BreakStmtAST::generateCode(SLContext& Context) {
  // Создать безусловный переход на метку "break" текущего цикла
  Context.TheBuilder->CreateBr(BreakLoc->BreakLoc);
  return nullptr;
}

Value* ContinueStmtAST::generateCode(SLContext& Context) {
  // Создать безусловный переход на метку "continue" текущего цикла
  Context.TheBuilder->CreateBr(ContinueLoc->ContinueLoc);
  return nullptr;
}

Value* ReturnStmtAST::generateCode(SLContext& Context) {
  // Проверяем, что у нас есть возвращаемое значение
  if (Expr) {
    // Генерируем код для выражения с возвращаемым значением
    Value* retVal = Expr->getRValue(Context);
    // Создаем инструкцию "store" для сохранения возвращаемого 
    // значения в переменной, для хранения результата выполнения
    // функции
    Context.TheBuilder->CreateStore(
      retVal,
      ReturnLoc->getReturnValue()
    );
    // Создаем безусловный переход на метку с выходом из функции
    Context.TheBuilder->CreateBr(ReturnLoc->ReturnLoc);
    return nullptr;
  }

  // Создаем безусловный переход на метку с выходом из функции
  Context.TheBuilder->CreateBr(ReturnLoc->ReturnLoc);
  return nullptr;
}

Value* WhileStmtAST::generateCode(SLContext& Context) {
  LandingPadAST* prev = LandingPad->Prev;
  LandingPad->ReturnLoc = prev->ReturnLoc;

  // У нас есть оптимизация для варианта, если значение условия 
  // цикла известно на этапе компиляции (но мы не производим 
  // вычисление константных выражений вида 1 + 2, рассматриваем
  // только выражения вида 1)
  if (Cond->isConst()) {
    // Если условие имеет значение "false", то не генерируем код
    // вообще
    if (!Cond->isTrue()) {
      return nullptr;
    }

    // Создаем новые блоки для тела цикла и выхода из цикла, и 
    // устанавливаем их в качестве меток для "break" и "continue"
    BasicBlock* bodyBB = 
    LandingPad->ContinueLoc = BasicBlock::Create(
      getGlobalContext(),
      "loopbody",
      Context.TheFunction
    );
    BasicBlock* endBB = LandingPad->BreakLoc = BasicBlock::Create(
      getGlobalContext(), 
      "loopend"
    );

    if (PostExpr) {
      // Для циклов, которые были сделаны из цикла "for" и у 
      // которых есть блок для изменения переменных циклов, нам
      // нужно создать новый блок для этого кода и мы должны 
      // установить его в качестве метки "continue"
      LandingPad->ContinueLoc = BasicBlock::Create(
        getGlobalContext(),
        "postbody"
      );
    }

    // Создать безусловный переход на тело цикла и установить 
    // данный блок в качестве точки для генерации кода
    Context.TheBuilder->CreateBr(bodyBB);
    Context.TheBuilder->SetInsertPoint(bodyBB);

    // Устанавливаем точку для возврата из цикла в зависимости от 
    // того, есть ли блок для изменения переменных цикла или нет
    if (PostExpr) {
      LandingPad->FallthroughLoc = LandingPad->ContinueLoc;
    } else {
      LandingPad->FallthroughLoc = bodyBB;
    }

    // Генерируем код тела цикла
    Body->generateCode(Context);

    // У нас есть специальная обработка для циклов "for" с блоком 
    // для изменения переменных цикла
    if (PostExpr) {
      // Добавляем блок в конец функции и устанавливаем его в 
      // качестве точки генерации кода
      Context.TheFunction->getBasicBlockList().push_back(
        LandingPad->ContinueLoc
      );
      Context.TheBuilder->SetInsertPoint(LandingPad->ContinueLoc);

      // Генерируем код для выражения изменения переменных цикла
      PostExpr->getRValue(Context);
      // Генерируем безусловный переход на тело цикла
      Context.TheBuilder->CreateBr(bodyBB);
    }

    // Добавляем блок для возврата из цикла в конец функции и 
    // устанавливаем его в качестве точки генерации кода
    Context.TheFunction->getBasicBlockList().push_back(endBB);
    Context.TheBuilder->SetInsertPoint(endBB);
    prev->Returns += LandingPad->Returns;

    // Создаем безусловный переход на точку возврата родительского 
    // блока и помечаем ее как использованную (путем присвоения
    // nullptr)
    Context.TheBuilder->CreateBr(prev->FallthroughLoc);
    prev->FallthroughLoc = nullptr;

    return nullptr;
  }
  
  // Создаем новые блоки для условия цикла, его тела и выхода из 
  // него, и устанавливаем их в качестве меток для "break" 
  // и "continue"
  BasicBlock* condBB = LandingPad->ContinueLoc = BasicBlock::Create(
    getGlobalContext(), 
    "loopcond",
    Context.TheFunction
  );
  BasicBlock* bodyBB = BasicBlock::Create(
    getGlobalContext(), 
    "loopbody"
  );
  BasicBlock* endBB = LandingPad->BreakLoc = BasicBlock::Create(
    getGlobalContext(),
    "loopend"
  );

  if (PostExpr) {
    // Для циклов, которые были сделаны из цикла "for" и у которых 
    // есть блок для изменения переменных циклов, нам нужно создать
    // новый блок для этого кода и мы должны установить его в 
    // качестве метки "continue"
    LandingPad->ContinueLoc = BasicBlock::Create(
      getGlobalContext(),
      "postbody"
    );
  }

  // Создаем безусловный переход на блок с условием цикла и 
  // устанавливаем его в качестве точки генерации кода
  Context.TheBuilder->CreateBr(condBB);
  Context.TheBuilder->SetInsertPoint(condBB);

  // Генерируем код для условия цикла
  Value* cond = Cond->getRValue(Context);
  // Произвести преобразование в "bool"
  cond = promoteToBool(cond, Cond->ExprType, *Context.TheBuilder);
  // Создать условный переход на тело цикла или на выход из цикла 
  // в зависимости от истинности условия цикла
  Context.TheBuilder->CreateCondBr(cond, bodyBB, endBB);

  // Создать безусловный переход на тело цикла и установить данный
  // блок в качестве точки для генерации кода
  Context.TheFunction->getBasicBlockList().push_back(bodyBB);
  Context.TheBuilder->SetInsertPoint(bodyBB);

  // Устанавливаем точку для возврата из цикла в зависимости от
  // того, есть ли блок для изменения переменных цикла или нет
  if (PostExpr) {
    LandingPad->FallthroughLoc = LandingPad->ContinueLoc;
  } else {
    LandingPad->FallthroughLoc = condBB;
  }

  // Генерируем код тела цикла
  Body->generateCode(Context);

  // У нас есть специальная обработка для циклов "for" с блоком 
  // для изменения переменных цикла
  if (PostExpr) {
    // Добавляем блок в конец функции и устанавливаем его в 
    // качестве точки генерации кода
    Context.TheFunction->getBasicBlockList().push_back(
      LandingPad->ContinueLoc
    );
    Context.TheBuilder->SetInsertPoint(LandingPad->ContinueLoc);

    // Генерируем код для выражения изменения переменных цикла
    PostExpr->getRValue(Context);
    // Генерируем безусловный переход на условие цикла
    Context.TheBuilder->CreateBr(condBB);
  }

  // Добавляем блок для возврата из цикла в конец функции и 
  // устанавливаем его в качестве точки генерации кода
  Context.TheFunction->getBasicBlockList().push_back(endBB);
  Context.TheBuilder->SetInsertPoint(endBB);
  prev->Returns += LandingPad->Returns;

  // Создаем безусловный переход на точку возврата родительского 
  // блока и помечаем ее как использованную (путем присвоения 
  // nullptr)
  Context.TheBuilder->CreateBr(prev->FallthroughLoc);
  prev->FallthroughLoc = nullptr;

  return nullptr;
}

llvm::Value* ForStmtAST::generateCode(SLContext& Context) {
  assert(0 && "ForStmtAST::semantic should never be reached");
  return nullptr;
}

llvm::Value* IfStmtAST::generateCode(SLContext& Context) {
  // Инициализируем блоки "break", "continue" и "return" для 
  // LandingPadAST текущего блока на основе родительского блока
  LandingPadAST* prev = LandingPad->Prev;
  LandingPad->ReturnLoc = prev->ReturnLoc;
  LandingPad->FallthroughLoc = prev->FallthroughLoc;
  LandingPad->ContinueLoc = prev->ContinueLoc;
  LandingPad->BreakLoc = prev->BreakLoc;

  // У нас есть оптимизация для варианта, если значение условия 
  // известно на этапе компиляции (но мы не производим вычисление
  // константных выражений вида 1 + 2, рассматриваем только
  // выражения вида 1)
  if (Cond->isConst()) {
    // Если выражение истинно
    if (Cond->isTrue()) {
      // Генерируем код для ветки "then"
      ThenBody->generateCode(Context);

      // Делаем подсчет количество "break" "continue" и "return" 
      // инструкций в данном блоке (в последующих статьях будет
      // ясно зачем они нужны)
      prev->Returns += LandingPad->Returns;
      prev->Breaks += LandingPad->Breaks;
      prev->Continues += LandingPad->Continues;

      if (!Context.TheBuilder->GetInsertBlock()->getTerminator()) {
        // Если еще нет условного или безусловного перехода, то 
        // создаем безусловный переход на точку возврата 
        // родительского блока и помечаем ее как использованную 
        // (путем присвоения nullptr)
        Context.TheBuilder->CreateBr(prev->FallthroughLoc);
        prev->FallthroughLoc = nullptr;
      }

      return nullptr;
    }
      
    // Если выражение ложно и у нас есть ветка "else"
    if (ElseBody) {
      // Генерируем код для ветки "else"
      ElseBody->generateCode(Context);

      // Делаем подсчет количество "break" "continue" и "return" 
      // инструкций в данном блоке (в последующих статьях будет
      // ясно зачем они нужны)
      prev->Returns += LandingPad->Returns;
      prev->Breaks += LandingPad->Breaks;
      prev->Continues += LandingPad->Continues;

      if (!Context.TheBuilder->GetInsertBlock()->getTerminator()) {
        // Если еще нет условного или безусловного перехода, то
        // создаем безусловный переход на точку возврата 
        // родительского блока и помечаем ее как использованную
        // (путем присвоения nullptr)
        Context.TheBuilder->CreateBr(prev->FallthroughLoc);
        prev->FallthroughLoc = nullptr;
      }
    }

    return nullptr;
  }
   
  // Генерируем код для условного выражения
  Value* cond = Cond->getRValue(Context);
  // Произвести преобразование в "bool"
  cond = promoteToBool(cond, Cond->ExprType, *Context.TheBuilder);

  // Создаем блок для веток "then" и блока за инструкцией ветвления
  BasicBlock* thenBB = BasicBlock::Create(
    getGlobalContext(),
    "thenpart", 
    Context.TheFunction
  );
  BasicBlock* elseBB = nullptr;
  BasicBlock* endBB = BasicBlock::Create(
    getGlobalContext(),
    "ifcont"
  );

  // Проверяем наличие ветки "else"
  if (ElseBody) {
    // Создаем блок для ветки "else"
    elseBB = BasicBlock::Create(getGlobalContext(), "elsepart");
    // Создаем условный переход на "then" или "else" в зависимости 
    // от истинности условия
    Context.TheBuilder->CreateCondBr(cond, thenBB, elseBB);
  } else {
    // Создаем условный переход на "then" или блок за инструкцией 
    // ветвления в зависимости от истинности условия
    Context.TheBuilder->CreateCondBr(cond, thenBB, endBB);
  }

  // Устанавливаем точку для генерации кода на блок "then"
  Context.TheBuilder->SetInsertPoint(thenBB);
  
  // Устанавливаем точку для FallthroughLoc
  LandingPad->FallthroughLoc = endBB;

  // Генерируем код для ветви "then"
  ThenBody->generateCode(Context);

  // Устанавливаем точку для FallthroughLoc (т. к. она могла быть 
  // обнулена при генерации кода для ветки "then")
  LandingPad->FallthroughLoc = endBB;

  // Проверяем наличие ветки "else"
  if (ElseBody) {
    // Добавляем блок "else" в конец функции и устанавливаем его в 
    // качестве точки генерации кода
    Context.TheFunction->getBasicBlockList().push_back(elseBB);
    Context.TheBuilder->SetInsertPoint(elseBB);

    // Генерируем код для ветви "else"
    ElseBody->generateCode(Context);
  }

  // Проверяем был ли использован блок, который мы создали для 
  // продолжения выполнения после инструкции ветвления
  if (endBB->hasNUsesOrMore(1)) {
    // Добавляем данный блок в конец функции и устанавливаем его в 
    // качестве точки генерации кода
    Context.TheFunction->getBasicBlockList().push_back(endBB);
    Context.TheBuilder->SetInsertPoint(endBB);

    // Создаем безусловный переход на точку возврата родительского 
    // блока и помечаем ее как использованную (путем присвоения
    // nullptr)
    Context.TheBuilder->CreateBr(prev->FallthroughLoc);
    prev->FallthroughLoc = nullptr;
  } else {
    // Производим очистку
    delete endBB;
  }

  // Делаем подсчет количество "break" "continue" и "return" 
  // инструкций в данном блоке (в последующих статьях будет
  // ясно зачем они нужны)
  prev->Returns += LandingPad->Returns;
  prev->Breaks += LandingPad->Breaks;
  prev->Continues += LandingPad->Continues;

  return nullptr;
}

Value* SymbolAST::getValue(SLContext& ) {
  assert(0 && "SymbolAST::getValue should never be reached");
  return nullptr;
}

Value* SymbolAST::generateCode(SLContext& Context) {
  assert(0 && "SymbolAST::generateCode should never be reached");
  return nullptr;
}

Value* VarDeclAST::generateCode(SLContext& Context) {
  assert(SemaState >= 5);
  // Получаем адрес переменной (т. к. память под саму переменную 
  // уже должна была выделена ранее во время генерации кода для
  // функции)
  Value* val = getValue(Context);


  // Если у нас есть выражение инициализации, то нужно ее 
  // произвести
  if (Val) {
    // Генерация кода для инициализирующего выражения
    Value* init = Val->getRValue(Context);

    // Создание инструкции "store"
    return Context.TheBuilder->CreateStore(init, val);
  }

  return val;
}

Value* VarDeclAST::getValue(SLContext& Context) {
  // Генерируем код для объявления только один раз
  if (CodeValue) {
    return CodeValue;
  }

  // Создаем инструкцию "alloca" для переменной
  CodeValue = Context.TheBuilder->CreateAlloca(
    ThisType->getType(),
    0,
    StringRef(Id->Id, Id->Length)
  );
  return CodeValue;
}

llvm::Value* ParameterSymbolAST::getValue(SLContext& Context) {
  // Генерируем код для объявления только один раз
  if (Param->CodeValue) {
    return Param->CodeValue;
  }

  // Создаем инструкцию "alloca" для параметра функции
  Param->CodeValue = Context.TheBuilder->CreateAlloca(
    Param->Param->getType(),
    0U
  );
  return Param->CodeValue;
}

llvm::Value* ParameterSymbolAST::generateCode(SLContext& Context) {
  assert(SemaState >= 5);
  // Мы только генерируем адрес для переменной, все остальное при 
  // необходимости будет сгенерировано в  FuncDeclAST
  return getValue(Context);
}

Value* FuncDeclAST::getValue(SLContext& Context) {
  // Генерируем код для объявления только один раз
  if (CodeValue) {
    return CodeValue;
  }

  SmallString< 128 > str;
  raw_svector_ostream output(str);

  // Производим генерацию имени функции (для "main" у нас есть 
  // специальная обработка)
  if (!(Id->Length == 4 && memcmp(Id->Id, "main", 4) == 0)) {
    // Генерация уникального декорированного имени функции
    output << "_P" << Id->Length << StringRef(Id->Id, Id->Length);
    ThisType->toMangleBuffer(output);
  } else {
    output << "main";
  }

  // Создать функцию с внешним видом связанности для данного 
  // объявления
  CodeValue = Function::Create((FunctionType*)ThisType->getType(), 
    Function::ExternalLinkage, output.str(), nullptr);
  Context.TheModule->getFunctionList().push_back(CodeValue);

  return CodeValue;
}

Value* FuncDeclAST::generateCode(SLContext& Context) {
  if (Compiled) {
    return CodeValue;
  }

  assert(SemaState >= 5);
  // Создать объявление функции (ее прототип)
  getValue(Context);

  BasicBlock* oldBlock = Context.TheBuilder->GetInsertBlock();

  Function::arg_iterator AI = CodeValue->arg_begin();
  ParameterList::iterator PI = 
    ((FuncTypeAST*)ThisType)->Params.begin();
  ParameterList::iterator PE = 
    ((FuncTypeAST*)ThisType)->Params.end();

  // Создать блок "entry" для тела функции и установить его в 
  // качестве точки генерации кода
  BasicBlock* BB = BasicBlock::Create(
    getGlobalContext(), 
    "entry", 
    CodeValue
  );
  Context.TheBuilder->SetInsertPoint(BB);

  // Выделение памяти для всех объявленных переменных
  for (std::vector< SymbolAST* >::iterator it = FuncVars.begin(), 
    end = FuncVars.end(); it != end; ++it) {
    (*it)->getValue(Context);
  }

  // Произвести генерацию кода для всех параметров
  for ( ; PI != PE; ++PI, ++AI) {
    ParameterAST* p = *PI;

    // Нам важны только именованные параметры
    if (p->Id) {
      // Указание имени параметра
      AI->setName(StringRef(p->Id->Id, p->Id->Length));
      // Генерация инструкции "alloca", если это необходимо
      if (!p->CodeValue) {
        p->CodeValue = Context.TheBuilder->CreateAlloca(
          p->Param->getType(),
          0U
        );
      }
      // Генерируем инструкцию "store" для копирования значения 
      // переданного в функцию в качестве параметра в переменную
      // выделенную под этот параметр
      Context.TheBuilder->CreateStore(AI, p->CodeValue);
    }
  }

  // Если тип возвращаемого значения функции отличается от "void",
  // то выделяем память для переменной, которая будет хранить
  // значение данной функции
  if (!ReturnType->isVoid()) {
    LandingPad->ReturnValue = Context.TheBuilder->CreateAlloca(
      ReturnType->getType(),
      0U,
      "return.value"
    );
  }

  // Создать блок для возврата из функции и установить его в 
  // качестве FallthroughLoc
  LandingPad->ReturnLoc = BasicBlock::Create(
    getGlobalContext(),
    "return.block"
  );
  LandingPad->FallthroughLoc = LandingPad->ReturnLoc;

  Function* oldFunction = Context.TheFunction;
  Context.TheFunction = CodeValue;

  // Генерация кода для тела функции
  Body->generateCode(Context);
 
  Context.TheFunction = oldFunction;

  // Добавляем условный переход на блок выхода из функции, если 
  // он еще не был сгенерирован
  if (!Context.TheBuilder->GetInsertBlock()->getTerminator()) {
    Context.TheBuilder->CreateBr(LandingPad->ReturnLoc);
  }

  // Добавить блок для возврата из функции в конец функции и 
  // установить его в качестве точки генерации кода
  CodeValue->getBasicBlockList().push_back(LandingPad->ReturnLoc);
  Context.TheBuilder->SetInsertPoint(LandingPad->ReturnLoc);
  
  if (!ReturnType->isVoid()) {
    // Тип возвращаемого значение не "void". Создаем инструкцию 
    // "load" для загрузки возвращаемого значения
    Value* ret = Context.TheBuilder->CreateLoad(
      ReturnType->getType(),
      LandingPad->ReturnValue
    );
    // Генерация инструкции возврата из функции
    Context.TheBuilder->CreateRet(ret);
  } else {
    // Генерация инструкции возврата из функции для "void"
    Context.TheBuilder->CreateRetVoid();
  }

  // Восстановление предыдущей точки генерации кода (если нужно)
  if (oldBlock) {
    Context.TheBuilder->SetInsertPoint(oldBlock);
  }

  // Проверка кода функции и оптимизация (если она включена)
  verifyFunction(*CodeValue, &llvm::errs());
  
  Compiled = true;

  return CodeValue;
}

void ModuleDeclAST::generateCode() {
  SLContext& Context = getSLContext();
  
  // Генерируем код для всех объявлений
  for (SymbolList::iterator it = Members.begin(),
    end = Members.end(); it != end; ++it) {
    (*it)->generateCode(Context);
  }

  // Печать кода модуля на консоль
  Context.TheModule->dump();

  if (!OutputFilename.empty()) {
    std::error_code errorInfo;
    raw_fd_ostream fd(OutputFilename.c_str(), errorInfo);

    if (errorInfo) {
      llvm::errs()
        << "Can't write to ""
        << OutputFilename.c_str()
        << "" filen";
    }

    // Печать кода модуля в результирующий файл, если он был задан
    Context.TheModule->print(fd, 0);
  }

  // Получить адрес JIT функции для "main", которую можно вызвать 
  // для запуска приложения
  MainPtr = (double (*)())(intptr_t)getJITMain();
}