lib/CodeGen/CodeGenFunction.cpp

   1 //===--- CodeGenFunction.cpp - Emit LLVM Code from ASTs for a Function ----===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This coordinates the per-function state used while generating code.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #include "CodeGenFunction.h"
  15 #include "CodeGenModule.h"
  16 #include "CGDebugInfo.h"
  17 #include "clang/Basic/TargetInfo.h"
  18 #include "clang/AST/APValue.h"
  19 #include "clang/AST/ASTContext.h"
  20 #include "clang/AST/Decl.h"
  21 #include "clang/AST/DeclCXX.h"
  22 #include "llvm/Target/TargetData.h"
  23 using namespace clang;
  24 using namespace CodeGen;
  25
  26 CodeGenFunction::CodeGenFunction(CodeGenModule &cgm)
  27   : BlockFunction(cgm, *this, Builder), CGM(cgm),
  28     Target(CGM.getContext().Target),
  29     Builder(cgm.getModule().getContext()),
  30 #ifndef USEINDIRECTBRANCH
  31     DebugInfo(0), IndirectGotoSwitch(0),
  32 #else
  33     DebugInfo(0), IndirectBranch(0),
  34 #endif
  35     SwitchInsn(0), CaseRangeBlock(0), InvokeDest(0),
  36     CXXThisDecl(0) {
  37   LLVMIntTy = ConvertType(getContext().IntTy);
  38   LLVMPointerWidth = Target.getPointerWidth(0);
  39 }
  40
  41 ASTContext &CodeGenFunction::getContext() const {
  42   return CGM.getContext();
  43 }
  44
  45
  46 llvm::BasicBlock *CodeGenFunction::getBasicBlockForLabel(const LabelStmt *S) {
  47   llvm::BasicBlock *&BB = LabelMap[S];
  48   if (BB) return BB;
  49
  50   // Create, but don't insert, the new block.
  51   return BB = createBasicBlock(S->getName());
  52 }
  53
  54 llvm::Value *CodeGenFunction::GetAddrOfLocalVar(const VarDecl *VD) {
  55   llvm::Value *Res = LocalDeclMap[VD];
  56   assert(Res && "Invalid argument to GetAddrOfLocalVar(), no decl!");
  57   return Res;
  58 }
  59
  60 llvm::Constant *
  61 CodeGenFunction::GetAddrOfStaticLocalVar(const VarDecl *BVD) {
  62   return cast<llvm::Constant>(GetAddrOfLocalVar(BVD));
  63 }
  64
  65 const llvm::Type *CodeGenFunction::ConvertTypeForMem(QualType T) {
  66   return CGM.getTypes().ConvertTypeForMem(T);
  67 }
  68
  69 const llvm::Type *CodeGenFunction::ConvertType(QualType T) {
  70   return CGM.getTypes().ConvertType(T);
  71 }
  72
  73 bool CodeGenFunction::hasAggregateLLVMType(QualType T) {
  74   return T->isRecordType() || T->isArrayType() || T->isAnyComplexType() ||
  75     T->isMemberFunctionPointerType();
  76 }
  77
  78 void CodeGenFunction::EmitReturnBlock() {
  79   // For cleanliness, we try to avoid emitting the return block for
  80   // simple cases.
  81   llvm::BasicBlock *CurBB = Builder.GetInsertBlock();
  82
  83   if (CurBB) {
  84     assert(!CurBB->getTerminator() && "Unexpected terminated block.");
  85
  86     // We have a valid insert point, reuse it if it is empty or there are no
  87     // explicit jumps to the return block.
  88     if (CurBB->empty() || ReturnBlock->use_empty()) {
  89       ReturnBlock->replaceAllUsesWith(CurBB);
  90       delete ReturnBlock;
  91     } else
  92       EmitBlock(ReturnBlock);
  93     return;
  94   }
  95
  96   // Otherwise, if the return block is the target of a single direct
  97   // branch then we can just put the code in that block instead. This
  98   // cleans up functions which started with a unified return block.
  99   if (ReturnBlock->hasOneUse()) {
 100     llvm::BranchInst *BI =
 101       dyn_cast<llvm::BranchInst>(*ReturnBlock->use_begin());
 102     if (BI && BI->isUnconditional() && BI->getSuccessor(0) == ReturnBlock) {
 103       // Reset insertion point and delete the branch.
 104       Builder.SetInsertPoint(BI->getParent());
 105       BI->eraseFromParent();
 106       delete ReturnBlock;
 107       return;
 108     }
 109   }
 110
 111   // FIXME: We are at an unreachable point, there is no reason to emit the block
 112   // unless it has uses. However, we still need a place to put the debug
 113   // region.end for now.
 114
 115   EmitBlock(ReturnBlock);
 116 }
 117
 118 void CodeGenFunction::FinishFunction(SourceLocation EndLoc) {
 119   assert(BreakContinueStack.empty() &&
 120          "mismatched push/pop in break/continue stack!");
 121   assert(BlockScopes.empty() &&
 122          "did not remove all blocks from block scope map!");
 123   assert(CleanupEntries.empty() &&
 124          "mismatched push/pop in cleanup stack!");
 125
 126   // Emit function epilog (to return).
 127   EmitReturnBlock();
 128
 129   // Emit debug descriptor for function end.
 130   if (CGDebugInfo *DI = getDebugInfo()) {
 131     DI->setLocation(EndLoc);
 132     DI->EmitRegionEnd(CurFn, Builder);
 133   }
 134
 135   EmitFunctionEpilog(*CurFnInfo, ReturnValue);
 136
 137 #ifdef USEINDIRECTBRANCH
 138   // If someone did an indirect goto, emit the indirect goto block at the end of
 139   // the function.
 140   if (IndirectBranch) {
 141     EmitBlock(IndirectBranch->getParent());
 142     Builder.ClearInsertionPoint();
 143   }
 144
 145
 146 #endif
 147   // Remove the AllocaInsertPt instruction, which is just a convenience for us.
 148   llvm::Instruction *Ptr = AllocaInsertPt;
 149   AllocaInsertPt = 0;
 150   Ptr->eraseFromParent();
 151 #ifdef USEINDIRECTBRANCH
 152
 153   // If someone took the address of a label but never did an indirect goto, we
 154   // made a zero entry PHI node, which is illegal, zap it now.
 155   if (IndirectBranch) {
 156     llvm::PHINode *PN = cast<llvm::PHINode>(IndirectBranch->getAddress());
 157     if (PN->getNumIncomingValues() == 0) {
 158       PN->replaceAllUsesWith(llvm::UndefValue::get(PN->getType()));
 159       PN->eraseFromParent();
 160     }
 161   }
 162
 163 #endif
 164 }
 165
 166 void CodeGenFunction::StartFunction(GlobalDecl GD, QualType RetTy,
 167                                     llvm::Function *Fn,
 168                                     const FunctionArgList &Args,
 169                                     SourceLocation StartLoc) {
 170   const Decl *D = GD.getDecl();
 171
 172   DidCallStackSave = false;
 173   CurCodeDecl = CurFuncDecl = D;
 174   FnRetTy = RetTy;
 175   CurFn = Fn;
 176   assert(CurFn->isDeclaration() && "Function already has body?");
 177
 178   llvm::BasicBlock *EntryBB = createBasicBlock("entry", CurFn);
 179
 180   // Create a marker to make it easy to insert allocas into the entryblock
 181   // later.  Don't create this with the builder, because we don't want it
 182   // folded.
 183   llvm::Value *Undef = llvm::UndefValue::get(llvm::Type::getInt32Ty(VMContext));
 184   AllocaInsertPt = new llvm::BitCastInst(Undef,
 185                                          llvm::Type::getInt32Ty(VMContext), "",
 186                                          EntryBB);
 187   if (Builder.isNamePreserving())
 188     AllocaInsertPt->setName("allocapt");
 189
 190   ReturnBlock = createBasicBlock("return");
 191   ReturnValue = 0;
 192   if (!RetTy->isVoidType())
 193     ReturnValue = CreateTempAlloca(ConvertType(RetTy), "retval");
 194
 195   Builder.SetInsertPoint(EntryBB);
 196
 197   QualType FnType = getContext().getFunctionType(RetTy, 0, 0, false, 0);
 198
 199   // Emit subprogram debug descriptor.
 200   // FIXME: The cast here is a huge hack.
 201   if (CGDebugInfo *DI = getDebugInfo()) {
 202     DI->setLocation(StartLoc);
 203     if (isa<FunctionDecl>(D)) {
 204       DI->EmitFunctionStart(CGM.getMangledName(GD), FnType, CurFn, Builder);
 205     } else {
 206       // Just use LLVM function name.
 207
 208       // FIXME: Remove unnecessary conversion to std::string when API settles.
 209       DI->EmitFunctionStart(std::string(Fn->getName()).c_str(),
 210                             FnType, CurFn, Builder);
 211     }
 212   }
 213
 214   // FIXME: Leaked.
 215   CurFnInfo = &CGM.getTypes().getFunctionInfo(FnRetTy, Args);
 216   EmitFunctionProlog(*CurFnInfo, CurFn, Args);
 217
 218   // If any of the arguments have a variably modified type, make sure to
 219   // emit the type size.
 220   for (FunctionArgList::const_iterator i = Args.begin(), e = Args.end();
 221        i != e; ++i) {
 222     QualType Ty = i->second;
 223
 224     if (Ty->isVariablyModifiedType())
 225       EmitVLASize(Ty);
 226   }
 227 }
 228
 229 void CodeGenFunction::GenerateCode(GlobalDecl GD,
 230                                    llvm::Function *Fn) {
 231   const FunctionDecl *FD = cast<FunctionDecl>(GD.getDecl());
 232
 233   // Check if we should generate debug info for this function.
 234   if (CGM.getDebugInfo() && !FD->hasAttr<NoDebugAttr>())
 235     DebugInfo = CGM.getDebugInfo();
 236
 237   FunctionArgList Args;
 238
 239   if (const CXXMethodDecl *MD = dyn_cast<CXXMethodDecl>(FD)) {
 240     if (MD->isInstance()) {
 241       // Create the implicit 'this' decl.
 242       // FIXME: I'm not entirely sure I like using a fake decl just for code
 243       // generation. Maybe we can come up with a better way?
 244       CXXThisDecl = ImplicitParamDecl::Create(getContext(), 0, SourceLocation(),
 245                                               &getContext().Idents.get("this"),
 246                                               MD->getThisType(getContext()));
 247       Args.push_back(std::make_pair(CXXThisDecl, CXXThisDecl->getType()));
 248     }
 249   }
 250
 251   if (FD->getNumParams()) {
 252     const FunctionProtoType* FProto = FD->getType()->getAs<FunctionProtoType>();
 253     assert(FProto && "Function def must have prototype!");
 254
 255     for (unsigned i = 0, e = FD->getNumParams(); i != e; ++i)
 256       Args.push_back(std::make_pair(FD->getParamDecl(i),
 257                                     FProto->getArgType(i)));
 258   }
 259
 260   // FIXME: Support CXXTryStmt here, too.
 261   if (const CompoundStmt *S = FD->getCompoundBody()) {
 262     StartFunction(GD, FD->getResultType(), Fn, Args, S->getLBracLoc());
 263     const CXXDestructorDecl *DD = dyn_cast<CXXDestructorDecl>(FD);
 264     llvm::BasicBlock *DtorEpilogue = 0;
 265     if (DD) {
 266       DtorEpilogue = createBasicBlock("dtor.epilogue");
 267
 268       PushCleanupBlock(DtorEpilogue);
 269     }
 270
 271     if (const CXXConstructorDecl *CD = dyn_cast<CXXConstructorDecl>(FD))
 272       EmitCtorPrologue(CD, GD.getCtorType());
 273     EmitStmt(S);
 274
 275     if (DD) {
 276       CleanupBlockInfo Info = PopCleanupBlock();
 277
 278       assert(Info.CleanupBlock == DtorEpilogue && "Block mismatch!");
 279       EmitBlock(DtorEpilogue);
 280       EmitDtorEpilogue(DD, GD.getDtorType());
 281
 282       if (Info.SwitchBlock)
 283         EmitBlock(Info.SwitchBlock);
 284       if (Info.EndBlock)
 285         EmitBlock(Info.EndBlock);
 286     }
 287     FinishFunction(S->getRBracLoc());
 288   } else if (FD->isImplicit()) {
 289     const CXXRecordDecl *ClassDecl =
 290       cast<CXXRecordDecl>(FD->getDeclContext());
 291     (void) ClassDecl;
 292     if (const CXXConstructorDecl *CD = dyn_cast<CXXConstructorDecl>(FD)) {
 293       // FIXME: For C++0x, we want to look for implicit *definitions* of
 294       // these special member functions, rather than implicit *declarations*.
 295       if (CD->isCopyConstructor(getContext())) {
 296         assert(!ClassDecl->hasUserDeclaredCopyConstructor() &&
 297                "Cannot synthesize a non-implicit copy constructor");
 298         SynthesizeCXXCopyConstructor(CD, GD.getCtorType(), Fn, Args);
 299       } else if (CD->isDefaultConstructor()) {
 300         assert(!ClassDecl->hasUserDeclaredConstructor() &&
 301                "Cannot synthesize a non-implicit default constructor.");
 302         SynthesizeDefaultConstructor(CD, GD.getCtorType(), Fn, Args);
 303       } else {
 304         assert(false && "Implicit constructor cannot be synthesized");
 305       }
 306     } else if (const CXXDestructorDecl *CD = dyn_cast<CXXDestructorDecl>(FD)) {
 307       assert(!ClassDecl->hasUserDeclaredDestructor() &&
 308              "Cannot synthesize a non-implicit destructor");
 309       SynthesizeDefaultDestructor(CD, GD.getDtorType(), Fn, Args);
 310     } else if (const CXXMethodDecl *MD = dyn_cast<CXXMethodDecl>(FD)) {
 311       assert(MD->isCopyAssignment() &&
 312              !ClassDecl->hasUserDeclaredCopyAssignment() &&
 313              "Cannot synthesize a method that is not an implicit-defined "
 314              "copy constructor");
 315       SynthesizeCXXCopyAssignment(MD, Fn, Args);
 316     } else {
 317       assert(false && "Cannot synthesize unknown implicit function");
 318     }
 319   }
 320
 321   // Destroy the 'this' declaration.
 322   if (CXXThisDecl)
 323     CXXThisDecl->Destroy(getContext());
 324 }
 325
 326 /// ContainsLabel - Return true if the statement contains a label in it.  If
 327 /// this statement is not executed normally, it not containing a label means
 328 /// that we can just remove the code.
 329 bool CodeGenFunction::ContainsLabel(const Stmt *S, bool IgnoreCaseStmts) {
 330   // Null statement, not a label!
 331   if (S == 0) return false;
 332
 333   // If this is a label, we have to emit the code, consider something like:
 334   // if (0) {  ...  foo:  bar(); }  goto foo;
 335   if (isa<LabelStmt>(S))
 336     return true;
 337
 338   // If this is a case/default statement, and we haven't seen a switch, we have
 339   // to emit the code.
 340   if (isa<SwitchCase>(S) && !IgnoreCaseStmts)
 341     return true;
 342
 343   // If this is a switch statement, we want to ignore cases below it.
 344   if (isa<SwitchStmt>(S))
 345     IgnoreCaseStmts = true;
 346
 347   // Scan subexpressions for verboten labels.
 348   for (Stmt::const_child_iterator I = S->child_begin(), E = S->child_end();
 349        I != E; ++I)
 350     if (ContainsLabel(*I, IgnoreCaseStmts))
 351       return true;
 352
 353   return false;
 354 }
 355
 356
 357 /// ConstantFoldsToSimpleInteger - If the sepcified expression does not fold to
 358 /// a constant, or if it does but contains a label, return 0.  If it constant
 359 /// folds to 'true' and does not contain a label, return 1, if it constant folds
 360 /// to 'false' and does not contain a label, return -1.
 361 int CodeGenFunction::ConstantFoldsToSimpleInteger(const Expr *Cond) {
 362   // FIXME: Rename and handle conversion of other evaluatable things
 363   // to bool.
 364   Expr::EvalResult Result;
 365   if (!Cond->Evaluate(Result, getContext()) || !Result.Val.isInt() ||
 366       Result.HasSideEffects)
 367     return 0;  // Not foldable, not integer or not fully evaluatable.
 368
 369   if (CodeGenFunction::ContainsLabel(Cond))
 370     return 0;  // Contains a label.
 371
 372   return Result.Val.getInt().getBoolValue() ? 1 : -1;
 373 }
 374
 375
 376 /// EmitBranchOnBoolExpr - Emit a branch on a boolean condition (e.g. for an if
 377 /// statement) to the specified blocks.  Based on the condition, this might try
 378 /// to simplify the codegen of the conditional based on the branch.
 379 ///
 380 void CodeGenFunction::EmitBranchOnBoolExpr(const Expr *Cond,
 381                                            llvm::BasicBlock *TrueBlock,
 382                                            llvm::BasicBlock *FalseBlock) {
 383   if (const ParenExpr *PE = dyn_cast<ParenExpr>(Cond))
 384     return EmitBranchOnBoolExpr(PE->getSubExpr(), TrueBlock, FalseBlock);
 385
 386   if (const BinaryOperator *CondBOp = dyn_cast<BinaryOperator>(Cond)) {
 387     // Handle X && Y in a condition.
 388     if (CondBOp->getOpcode() == BinaryOperator::LAnd) {
 389       // If we have "1 && X", simplify the code.  "0 && X" would have constant
 390       // folded if the case was simple enough.
 391       if (ConstantFoldsToSimpleInteger(CondBOp->getLHS()) == 1) {
 392         // br(1 && X) -> br(X).
 393         return EmitBranchOnBoolExpr(CondBOp->getRHS(), TrueBlock, FalseBlock);
 394       }
 395
 396       // If we have "X && 1", simplify the code to use an uncond branch.
 397       // "X && 0" would have been constant folded to 0.
 398       if (ConstantFoldsToSimpleInteger(CondBOp->getRHS()) == 1) {
 399         // br(X && 1) -> br(X).
 400         return EmitBranchOnBoolExpr(CondBOp->getLHS(), TrueBlock, FalseBlock);
 401       }
 402
 403       // Emit the LHS as a conditional.  If the LHS conditional is false, we
 404       // want to jump to the FalseBlock.
 405       llvm::BasicBlock *LHSTrue = createBasicBlock("land.lhs.true");
 406       EmitBranchOnBoolExpr(CondBOp->getLHS(), LHSTrue, FalseBlock);
 407       EmitBlock(LHSTrue);
 408
 409       EmitBranchOnBoolExpr(CondBOp->getRHS(), TrueBlock, FalseBlock);
 410       return;
 411     } else if (CondBOp->getOpcode() == BinaryOperator::LOr) {
 412       // If we have "0 || X", simplify the code.  "1 || X" would have constant
 413       // folded if the case was simple enough.
 414       if (ConstantFoldsToSimpleInteger(CondBOp->getLHS()) == -1) {
 415         // br(0 || X) -> br(X).
 416         return EmitBranchOnBoolExpr(CondBOp->getRHS(), TrueBlock, FalseBlock);
 417       }
 418
 419       // If we have "X || 0", simplify the code to use an uncond branch.
 420       // "X || 1" would have been constant folded to 1.
 421       if (ConstantFoldsToSimpleInteger(CondBOp->getRHS()) == -1) {
 422         // br(X || 0) -> br(X).
 423         return EmitBranchOnBoolExpr(CondBOp->getLHS(), TrueBlock, FalseBlock);
 424       }
 425
 426       // Emit the LHS as a conditional.  If the LHS conditional is true, we
 427       // want to jump to the TrueBlock.
 428       llvm::BasicBlock *LHSFalse = createBasicBlock("lor.lhs.false");
 429       EmitBranchOnBoolExpr(CondBOp->getLHS(), TrueBlock, LHSFalse);
 430       EmitBlock(LHSFalse);
 431
 432       EmitBranchOnBoolExpr(CondBOp->getRHS(), TrueBlock, FalseBlock);
 433       return;
 434     }
 435   }
 436
 437   if (const UnaryOperator *CondUOp = dyn_cast<UnaryOperator>(Cond)) {
 438     // br(!x, t, f) -> br(x, f, t)
 439     if (CondUOp->getOpcode() == UnaryOperator::LNot)
 440       return EmitBranchOnBoolExpr(CondUOp->getSubExpr(), FalseBlock, TrueBlock);
 441   }
 442
 443   if (const ConditionalOperator *CondOp = dyn_cast<ConditionalOperator>(Cond)) {
 444     // Handle ?: operator.
 445
 446     // Just ignore GNU ?: extension.
 447     if (CondOp->getLHS()) {
 448       // br(c ? x : y, t, f) -> br(c, br(x, t, f), br(y, t, f))
 449       llvm::BasicBlock *LHSBlock = createBasicBlock("cond.true");
 450       llvm::BasicBlock *RHSBlock = createBasicBlock("cond.false");
 451       EmitBranchOnBoolExpr(CondOp->getCond(), LHSBlock, RHSBlock);
 452       EmitBlock(LHSBlock);
 453       EmitBranchOnBoolExpr(CondOp->getLHS(), TrueBlock, FalseBlock);
 454       EmitBlock(RHSBlock);
 455       EmitBranchOnBoolExpr(CondOp->getRHS(), TrueBlock, FalseBlock);
 456       return;
 457     }
 458   }
 459
 460   // Emit the code with the fully general case.
 461   llvm::Value *CondV = EvaluateExprAsBool(Cond);
 462   Builder.CreateCondBr(CondV, TrueBlock, FalseBlock);
 463 }
 464
 465 /// ErrorUnsupported - Print out an error that codegen doesn't support the
 466 /// specified stmt yet.
 467 void CodeGenFunction::ErrorUnsupported(const Stmt *S, const char *Type,
 468                                        bool OmitOnError) {
 469   CGM.ErrorUnsupported(S, Type, OmitOnError);
 470 }
 471
 472 void CodeGenFunction::EmitMemSetToZero(llvm::Value *DestPtr, QualType Ty) {
 473   const llvm::Type *BP = llvm::Type::getInt8PtrTy(VMContext);
 474   if (DestPtr->getType() != BP)
 475     DestPtr = Builder.CreateBitCast(DestPtr, BP, "tmp");
 476
 477   // Get size and alignment info for this aggregate.
 478   std::pair<uint64_t, unsigned> TypeInfo = getContext().getTypeInfo(Ty);
 479
 480   // Don't bother emitting a zero-byte memset.
 481   if (TypeInfo.first == 0)
 482     return;
 483
 484   // FIXME: Handle variable sized types.
 485   const llvm::Type *IntPtr = llvm::IntegerType::get(VMContext,
 486                                                     LLVMPointerWidth);
 487
 488   Builder.CreateCall4(CGM.getMemSetFn(), DestPtr,
 489                  llvm::Constant::getNullValue(llvm::Type::getInt8Ty(VMContext)),
 490                       // TypeInfo.first describes size in bits.
 491                       llvm::ConstantInt::get(IntPtr, TypeInfo.first/8),
 492                       llvm::ConstantInt::get(llvm::Type::getInt32Ty(VMContext),
 493                                              TypeInfo.second/8));
 494 }
 495
 496 #ifndef USEINDIRECTBRANCH
 497 unsigned CodeGenFunction::GetIDForAddrOfLabel(const LabelStmt *L) {
 498   // Use LabelIDs.size()+1 as the new ID if one hasn't been assigned.
 499   unsigned &Entry = LabelIDs[L];
 500   if (Entry) return Entry;
 501 #else
 502
 503 llvm::BlockAddress *CodeGenFunction::GetAddrOfLabel(const LabelStmt *L) {
 504   // Make sure that there is a block for the indirect goto.
 505   if (IndirectBranch == 0)
 506     GetIndirectGotoBlock();
 507 #endif
 508
 509 #ifndef USEINDIRECTBRANCH
 510   Entry = LabelIDs.size();
 511 #else
 512   llvm::BasicBlock *BB = getBasicBlockForLabel(L);
 513 #endif
 514
 515 #ifndef USEINDIRECTBRANCH
 516   // If this is the first "address taken" of a label and the indirect goto has
 517   // already been seen, add this to it.
 518   if (IndirectGotoSwitch) {
 519     // If this is the first address-taken label, set it as the default dest.
 520     if (Entry == 1)
 521       IndirectGotoSwitch->setSuccessor(0, getBasicBlockForLabel(L));
 522     else {
 523       // Otherwise add it to the switch as a new dest.
 524       const llvm::IntegerType *Int32Ty = llvm::Type::getInt32Ty(VMContext);
 525       IndirectGotoSwitch->addCase(llvm::ConstantInt::get(Int32Ty, Entry),
 526                                   getBasicBlockForLabel(L));
 527     }
 528   }
 529
 530   return Entry;
 531 #else
 532   // Make sure the indirect branch includes all of the address-taken blocks.
 533   IndirectBranch->addDestination(BB);
 534   return llvm::BlockAddress::get(CurFn, BB);
 535 #endif
 536 }
 537
 538 llvm::BasicBlock *CodeGenFunction::GetIndirectGotoBlock() {
 539 #ifndef USEINDIRECTBRANCH
 540   // If we already made the switch stmt for indirect goto, return its block.
 541   if (IndirectGotoSwitch) return IndirectGotoSwitch->getParent();
 542 #else
 543   // If we already made the indirect branch for indirect goto, return its block.
 544   if (IndirectBranch) return IndirectBranch->getParent();
 545 #endif
 546
 547 #ifndef USEINDIRECTBRANCH
 548   EmitBlock(createBasicBlock("indirectgoto"));
 549 #else
 550   CGBuilderTy TmpBuilder(createBasicBlock("indirectgoto"));
 551 #endif
 552
 553 #ifndef USEINDIRECTBRANCH
 554   const llvm::IntegerType *Int32Ty = llvm::Type::getInt32Ty(VMContext);
 555 #else
 556   const llvm::Type *Int8PtrTy = llvm::Type::getInt8PtrTy(VMContext);
 557 #endif
 558
 559   // Create the PHI node that indirect gotos will add entries to.
 560 #ifndef USEINDIRECTBRANCH
 561   llvm::Value *DestVal = Builder.CreatePHI(Int32Ty, "indirect.goto.dest");
 562 #else
 563   llvm::Value *DestVal = TmpBuilder.CreatePHI(Int8PtrTy, "indirect.goto.dest");
 564 #endif
 565
 566 #ifndef USEINDIRECTBRANCH
 567   // Create the switch instruction.  For now, set the insert block to this block
 568   // which will be fixed as labels are added.
 569   IndirectGotoSwitch = Builder.CreateSwitch(DestVal, Builder.GetInsertBlock());
 570
 571   // Clear the insertion point to indicate we are in unreachable code.
 572   Builder.ClearInsertionPoint();
 573
 574   // If we already have labels created, add them.
 575   if (!LabelIDs.empty()) {
 576     // Invert LabelID's so that the order is determinstic.
 577     std::vector<const LabelStmt*> AddrTakenLabelsByID;
 578     AddrTakenLabelsByID.resize(LabelIDs.size());
 579
 580     for (std::map<const LabelStmt*,unsigned>::iterator
 581          LI = LabelIDs.begin(), LE = LabelIDs.end(); LI != LE; ++LI) {
 582       assert(LI->second-1 < AddrTakenLabelsByID.size() &&
 583              "Numbering inconsistent");
 584       AddrTakenLabelsByID[LI->second-1] = LI->first;
 585     }
 586
 587     // Set the default entry as the first block.
 588     IndirectGotoSwitch->setSuccessor(0,
 589                                 getBasicBlockForLabel(AddrTakenLabelsByID[0]));
 590
 591     // FIXME: The iteration order of this is nondeterminstic!
 592     for (unsigned i = 1, e = AddrTakenLabelsByID.size(); i != e; ++i)
 593       IndirectGotoSwitch->addCase(llvm::ConstantInt::get(Int32Ty, i+1),
 594                                  getBasicBlockForLabel(AddrTakenLabelsByID[i]));
 595   } else {
 596     // Otherwise, create a dead block and set it as the default dest.  This will
 597     // be removed by the optimizers after the indirect goto is set up.
 598     llvm::BasicBlock *Dummy = createBasicBlock("indgoto.dummy");
 599     EmitBlock(Dummy);
 600     IndirectGotoSwitch->setSuccessor(0, Dummy);
 601     Builder.CreateUnreachable();
 602     Builder.ClearInsertionPoint();
 603   }
 604
 605   return IndirectGotoSwitch->getParent();
 606 #else
 607   // Create the indirect branch instruction.
 608   IndirectBranch = TmpBuilder.CreateIndirectBr(DestVal);
 609   return IndirectBranch->getParent();
 610 #endif
 611 }
 612
 613 llvm::Value *CodeGenFunction::GetVLASize(const VariableArrayType *VAT) {
 614   llvm::Value *&SizeEntry = VLASizeMap[VAT->getSizeExpr()];
 615
 616   assert(SizeEntry && "Did not emit size for type");
 617   return SizeEntry;
 618 }
 619
 620 llvm::Value *CodeGenFunction::EmitVLASize(QualType Ty) {
 621   assert(Ty->isVariablyModifiedType() &&
 622          "Must pass variably modified type to EmitVLASizes!");
 623
 624   EnsureInsertPoint();
 625
 626   if (const VariableArrayType *VAT = getContext().getAsVariableArrayType(Ty)) {
 627     llvm::Value *&SizeEntry = VLASizeMap[VAT->getSizeExpr()];
 628
 629     if (!SizeEntry) {
 630       const llvm::Type *SizeTy = ConvertType(getContext().getSizeType());
 631
 632       // Get the element size;
 633       QualType ElemTy = VAT->getElementType();
 634       llvm::Value *ElemSize;
 635       if (ElemTy->isVariableArrayType())
 636         ElemSize = EmitVLASize(ElemTy);
 637       else
 638         ElemSize = llvm::ConstantInt::get(SizeTy,
 639                                           getContext().getTypeSize(ElemTy) / 8);
 640
 641       llvm::Value *NumElements = EmitScalarExpr(VAT->getSizeExpr());
 642       NumElements = Builder.CreateIntCast(NumElements, SizeTy, false, "tmp");
 643
 644       SizeEntry = Builder.CreateMul(ElemSize, NumElements);
 645     }
 646
 647     return SizeEntry;
 648   }
 649
 650   if (const ArrayType *AT = dyn_cast<ArrayType>(Ty)) {
 651     EmitVLASize(AT->getElementType());
 652     return 0;
 653   }
 654
 655   const PointerType *PT = Ty->getAs<PointerType>();
 656   assert(PT && "unknown VM type!");
 657   EmitVLASize(PT->getPointeeType());
 658   return 0;
 659 }
 660
 661 llvm::Value* CodeGenFunction::EmitVAListRef(const Expr* E) {
 662   if (CGM.getContext().getBuiltinVaListType()->isArrayType()) {
 663     return EmitScalarExpr(E);
 664   }
 665   return EmitLValue(E).getAddress();
 666 }
 667
 668 void CodeGenFunction::PushCleanupBlock(llvm::BasicBlock *CleanupEntryBlock,
 669                                        llvm::BasicBlock *CleanupExitBlock) {
 670   CleanupEntries.push_back(CleanupEntry(CleanupEntryBlock, CleanupExitBlock));
 671 }
 672
 673 void CodeGenFunction::EmitCleanupBlocks(size_t OldCleanupStackSize) {
 674   assert(CleanupEntries.size() >= OldCleanupStackSize &&
 675          "Cleanup stack mismatch!");
 676
 677   while (CleanupEntries.size() > OldCleanupStackSize)
 678     EmitCleanupBlock();
 679 }
 680
 681 CodeGenFunction::CleanupBlockInfo CodeGenFunction::PopCleanupBlock() {
 682   CleanupEntry &CE = CleanupEntries.back();
 683
 684   llvm::BasicBlock *CleanupEntryBlock = CE.CleanupEntryBlock;
 685
 686   std::vector<llvm::BasicBlock *> Blocks;
 687   std::swap(Blocks, CE.Blocks);
 688
 689   std::vector<llvm::BranchInst *> BranchFixups;
 690   std::swap(BranchFixups, CE.BranchFixups);
 691
 692   CleanupEntries.pop_back();
 693
 694   // Check if any branch fixups pointed to the scope we just popped. If so,
 695   // we can remove them.
 696   for (size_t i = 0, e = BranchFixups.size(); i != e; ++i) {
 697     llvm::BasicBlock *Dest = BranchFixups[i]->getSuccessor(0);
 698     BlockScopeMap::iterator I = BlockScopes.find(Dest);
 699
 700     if (I == BlockScopes.end())
 701       continue;
 702
 703     assert(I->second <= CleanupEntries.size() && "Invalid branch fixup!");
 704
 705     if (I->second == CleanupEntries.size()) {
 706       // We don't need to do this branch fixup.
 707       BranchFixups[i] = BranchFixups.back();
 708       BranchFixups.pop_back();
 709       i--;
 710       e--;
 711       continue;
 712     }
 713   }
 714
 715   llvm::BasicBlock *SwitchBlock = CE.CleanupExitBlock;
 716   llvm::BasicBlock *EndBlock = 0;
 717   if (!BranchFixups.empty()) {
 718     if (!SwitchBlock)
 719       SwitchBlock = createBasicBlock("cleanup.switch");
 720     EndBlock = createBasicBlock("cleanup.end");
 721
 722     llvm::BasicBlock *CurBB = Builder.GetInsertBlock();
 723
 724     Builder.SetInsertPoint(SwitchBlock);
 725
 726     llvm::Value *DestCodePtr = CreateTempAlloca(llvm::Type::getInt32Ty(VMContext),
 727                                                 "cleanup.dst");
 728     llvm::Value *DestCode = Builder.CreateLoad(DestCodePtr, "tmp");
 729
 730     // Create a switch instruction to determine where to jump next.
 731     llvm::SwitchInst *SI = Builder.CreateSwitch(DestCode, EndBlock,
 732                                                 BranchFixups.size());
 733
 734     // Restore the current basic block (if any)
 735     if (CurBB) {
 736       Builder.SetInsertPoint(CurBB);
 737
 738       // If we had a current basic block, we also need to emit an instruction
 739       // to initialize the cleanup destination.
 740       Builder.CreateStore(llvm::Constant::getNullValue(llvm::Type::getInt32Ty(VMContext)),
 741                           DestCodePtr);
 742     } else
 743       Builder.ClearInsertionPoint();
 744
 745     for (size_t i = 0, e = BranchFixups.size(); i != e; ++i) {
 746       llvm::BranchInst *BI = BranchFixups[i];
 747       llvm::BasicBlock *Dest = BI->getSuccessor(0);
 748
 749       // Fixup the branch instruction to point to the cleanup block.
 750       BI->setSuccessor(0, CleanupEntryBlock);
 751
 752       if (CleanupEntries.empty()) {
 753         llvm::ConstantInt *ID;
 754
 755         // Check if we already have a destination for this block.
 756         if (Dest == SI->getDefaultDest())
 757           ID = llvm::ConstantInt::get(llvm::Type::getInt32Ty(VMContext), 0);
 758         else {
 759           ID = SI->findCaseDest(Dest);
 760           if (!ID) {
 761             // No code found, get a new unique one by using the number of
 762             // switch successors.
 763             ID = llvm::ConstantInt::get(llvm::Type::getInt32Ty(VMContext),
 764                                         SI->getNumSuccessors());
 765             SI->addCase(ID, Dest);
 766           }
 767         }
 768
 769         // Store the jump destination before the branch instruction.
 770         new llvm::StoreInst(ID, DestCodePtr, BI);
 771       } else {
 772         // We need to jump through another cleanup block. Create a pad block
 773         // with a branch instruction that jumps to the final destination and
 774         // add it as a branch fixup to the current cleanup scope.
 775
 776         // Create the pad block.
 777         llvm::BasicBlock *CleanupPad = createBasicBlock("cleanup.pad", CurFn);
 778
 779         // Create a unique case ID.
 780         llvm::ConstantInt *ID = llvm::ConstantInt::get(llvm::Type::getInt32Ty(VMContext),
 781                                                        SI->getNumSuccessors());
 782
 783         // Store the jump destination before the branch instruction.
 784         new llvm::StoreInst(ID, DestCodePtr, BI);
 785
 786         // Add it as the destination.
 787         SI->addCase(ID, CleanupPad);
 788
 789         // Create the branch to the final destination.
 790         llvm::BranchInst *BI = llvm::BranchInst::Create(Dest);
 791         CleanupPad->getInstList().push_back(BI);
 792
 793         // And add it as a branch fixup.
 794         CleanupEntries.back().BranchFixups.push_back(BI);
 795       }
 796     }
 797   }
 798
 799   // Remove all blocks from the block scope map.
 800   for (size_t i = 0, e = Blocks.size(); i != e; ++i) {
 801     assert(BlockScopes.count(Blocks[i]) &&
 802            "Did not find block in scope map!");
 803
 804     BlockScopes.erase(Blocks[i]);
 805   }
 806
 807   return CleanupBlockInfo(CleanupEntryBlock, SwitchBlock, EndBlock);
 808 }
 809
 810 void CodeGenFunction::EmitCleanupBlock() {
 811   CleanupBlockInfo Info = PopCleanupBlock();
 812
 813   llvm::BasicBlock *CurBB = Builder.GetInsertBlock();
 814   if (CurBB && !CurBB->getTerminator() &&
 815       Info.CleanupBlock->getNumUses() == 0) {
 816     CurBB->getInstList().splice(CurBB->end(), Info.CleanupBlock->getInstList());
 817     delete Info.CleanupBlock;
 818   } else
 819     EmitBlock(Info.CleanupBlock);
 820
 821   if (Info.SwitchBlock)
 822     EmitBlock(Info.SwitchBlock);
 823   if (Info.EndBlock)
 824     EmitBlock(Info.EndBlock);
 825 }
 826
 827 void CodeGenFunction::AddBranchFixup(llvm::BranchInst *BI) {
 828   assert(!CleanupEntries.empty() &&
 829          "Trying to add branch fixup without cleanup block!");
 830
 831   // FIXME: We could be more clever here and check if there's already a branch
 832   // fixup for this destination and recycle it.
 833   CleanupEntries.back().BranchFixups.push_back(BI);
 834 }
 835
 836 void CodeGenFunction::EmitBranchThroughCleanup(llvm::BasicBlock *Dest) {
 837   if (!HaveInsertPoint())
 838     return;
 839
 840   llvm::BranchInst* BI = Builder.CreateBr(Dest);
 841
 842   Builder.ClearInsertionPoint();
 843
 844   // The stack is empty, no need to do any cleanup.
 845   if (CleanupEntries.empty())
 846     return;
 847
 848   if (!Dest->getParent()) {
 849     // We are trying to branch to a block that hasn't been inserted yet.
 850     AddBranchFixup(BI);
 851     return;
 852   }
 853
 854   BlockScopeMap::iterator I = BlockScopes.find(Dest);
 855   if (I == BlockScopes.end()) {
 856     // We are trying to jump to a block that is outside of any cleanup scope.
 857     AddBranchFixup(BI);
 858     return;
 859   }
 860
 861   assert(I->second < CleanupEntries.size() &&
 862          "Trying to branch into cleanup region");
 863
 864   if (I->second == CleanupEntries.size() - 1) {
 865     // We have a branch to a block in the same scope.
 866     return;
 867   }
 868
 869   AddBranchFixup(BI);
 870 }