JumpDiagnostics.cpp revision 221345
138889Sjdp//===--- JumpDiagnostics.cpp - Analyze Jump Targets for VLA issues --------===// 238889Sjdp// 338889Sjdp// The LLVM Compiler Infrastructure 438889Sjdp// 538889Sjdp// This file is distributed under the University of Illinois Open Source 638889Sjdp// License. See LICENSE.TXT for details. 760484Sobrien// 838889Sjdp//===----------------------------------------------------------------------===// 960484Sobrien// 1038889Sjdp// This file implements the JumpScopeChecker class, which is used to diagnose 1138889Sjdp// jumps that enter a VLA scope in an invalid way. 1238889Sjdp// 1338889Sjdp//===----------------------------------------------------------------------===// 1438889Sjdp 1577298Sobrien#include "clang/Sema/SemaInternal.h" 1677298Sobrien#include "clang/AST/DeclCXX.h" 1777298Sobrien#include "clang/AST/Expr.h" 1838889Sjdp#include "clang/AST/StmtObjC.h" 1938889Sjdp#include "clang/AST/StmtCXX.h" 2038889Sjdp#include "llvm/ADT/BitVector.h" 2138889Sjdpusing namespace clang; 2238889Sjdp 2338889Sjdpnamespace { 2438889Sjdp 2538889Sjdp/// JumpScopeChecker - This object is used by Sema to diagnose invalid jumps 2638889Sjdp/// into VLA and other protected scopes. For example, this rejects: 2738889Sjdp/// goto L; 2889857Sobrien/// int a[n]; 2938889Sjdp/// L: 3038889Sjdp/// 3138889Sjdpclass JumpScopeChecker { 3277298Sobrien Sema &S; 3389857Sobrien 3438889Sjdp /// GotoScope - This is a record that we use to keep track of all of the 3589857Sobrien /// scopes that are introduced by VLAs and other things that scope jumps like 3689857Sobrien /// gotos. This scope tree has nothing to do with the source scope tree, 3789857Sobrien /// because you can have multiple VLA scopes per compound statement, and most 3838889Sjdp /// compound statements don't introduce any scopes. 3938889Sjdp struct GotoScope { 4038889Sjdp /// ParentScope - The index in ScopeMap of the parent scope. This is 0 for 4177298Sobrien /// the parent scope is the function body. 4289857Sobrien unsigned ParentScope; 4338889Sjdp 4489857Sobrien /// InDiag - The diagnostic to emit if there is a jump into this scope. 4589857Sobrien unsigned InDiag; 4638889Sjdp 4738889Sjdp /// OutDiag - The diagnostic to emit if there is an indirect jump out 4838889Sjdp /// of this scope. Direct jumps always clean up their current scope 4938889Sjdp /// in an orderly way. 5038889Sjdp unsigned OutDiag; 5138889Sjdp 5238889Sjdp /// Loc - Location to emit the diagnostic. 5360484Sobrien SourceLocation Loc; 5477298Sobrien 5538889Sjdp GotoScope(unsigned parentScope, unsigned InDiag, unsigned OutDiag, 5660484Sobrien SourceLocation L) 5760484Sobrien : ParentScope(parentScope), InDiag(InDiag), OutDiag(OutDiag), Loc(L) {} 5838889Sjdp }; 5938889Sjdp 6038889Sjdp llvm::SmallVector<GotoScope, 48> Scopes; 6177298Sobrien llvm::DenseMap<Stmt*, unsigned> LabelAndGotoScopes; 6260484Sobrien llvm::SmallVector<Stmt*, 16> Jumps; 6338889Sjdp 6438889Sjdp llvm::SmallVector<IndirectGotoStmt*, 4> IndirectJumps; 6538889Sjdp llvm::SmallVector<LabelDecl*, 4> IndirectJumpTargets; 6638889Sjdppublic: 6777298Sobrien JumpScopeChecker(Stmt *Body, Sema &S); 6877298Sobrienprivate: 6938889Sjdp void BuildScopeInformation(Decl *D, unsigned &ParentScope); 7038889Sjdp void BuildScopeInformation(Stmt *S, unsigned ParentScope); 7138889Sjdp void VerifyJumps(); 7238889Sjdp void VerifyIndirectJumps(); 7360484Sobrien void DiagnoseIndirectJump(IndirectGotoStmt *IG, unsigned IGScope, 7460484Sobrien LabelDecl *Target, unsigned TargetScope); 7589857Sobrien void CheckJump(Stmt *From, Stmt *To, 7691041Sobrien SourceLocation DiagLoc, unsigned JumpDiag); 7738889Sjdp 7889857Sobrien unsigned GetDeepestCommonScope(unsigned A, unsigned B); 7989857Sobrien}; 8060484Sobrien} // end anonymous namespace 8138889Sjdp 8238889Sjdp 8389857SobrienJumpScopeChecker::JumpScopeChecker(Stmt *Body, Sema &s) : S(s) { 8438889Sjdp // Add a scope entry for function scope. 8538889Sjdp Scopes.push_back(GotoScope(~0U, ~0U, ~0U, SourceLocation())); 8638889Sjdp 8777298Sobrien // Build information for the top level compound statement, so that we have a 8860484Sobrien // defined scope record for every "goto" and label. 8938889Sjdp BuildScopeInformation(Body, 0); 9038889Sjdp 9138889Sjdp // Check that all jumps we saw are kosher. 9238889Sjdp VerifyJumps(); 9389857Sobrien VerifyIndirectJumps(); 9438889Sjdp} 9538889Sjdp 9638889Sjdp/// GetDeepestCommonScope - Finds the innermost scope enclosing the 9738889Sjdp/// two scopes. 9838889Sjdpunsigned JumpScopeChecker::GetDeepestCommonScope(unsigned A, unsigned B) { 9938889Sjdp while (A != B) { 10038889Sjdp // Inner scopes are created after outer scopes and therefore have 10160484Sobrien // higher indices. 10277298Sobrien if (A < B) { 10360484Sobrien assert(Scopes[B].ParentScope < B); 10460484Sobrien B = Scopes[B].ParentScope; 10560484Sobrien } else { 10638889Sjdp assert(Scopes[A].ParentScope < A); 10738889Sjdp A = Scopes[A].ParentScope; 10838889Sjdp } 10977298Sobrien } 11060484Sobrien return A; 11138889Sjdp} 11238889Sjdp 11338889Sjdp/// GetDiagForGotoScopeDecl - If this decl induces a new goto scope, return a 11438889Sjdp/// diagnostic that should be emitted if control goes over it. If not, return 0. 11577298Sobrienstatic std::pair<unsigned,unsigned> 11677298Sobrien GetDiagForGotoScopeDecl(const Decl *D, bool isCPlusPlus) { 11738889Sjdp if (const VarDecl *VD = dyn_cast<VarDecl>(D)) { 11838889Sjdp unsigned InDiag = 0, OutDiag = 0; 11938889Sjdp if (VD->getType()->isVariablyModifiedType()) 12038889Sjdp InDiag = diag::note_protected_by_vla; 12160484Sobrien 12260484Sobrien if (VD->hasAttr<BlocksAttr>()) { 12389857Sobrien InDiag = diag::note_protected_by___block; 12491041Sobrien OutDiag = diag::note_exits___block; 12538889Sjdp } else if (VD->hasAttr<CleanupAttr>()) { 12689857Sobrien InDiag = diag::note_protected_by_cleanup; 12789857Sobrien OutDiag = diag::note_exits_cleanup; 12860484Sobrien } else if (isCPlusPlus) { 12938889Sjdp // FIXME: In C++0x, we have to check more conditions than "did we 13038889Sjdp // just give it an initializer?". See 6.7p3. 13189857Sobrien if (VD->hasLocalStorage() && VD->hasInit()) 13238889Sjdp InDiag = diag::note_protected_by_variable_init; 13338889Sjdp 13438889Sjdp CanQualType T = VD->getType()->getCanonicalTypeUnqualified(); 13577298Sobrien if (!T->isDependentType()) { 13660484Sobrien while (CanQual<ArrayType> AT = T->getAs<ArrayType>()) 13738889Sjdp T = AT->getElementType(); 13838889Sjdp if (CanQual<RecordType> RT = T->getAs<RecordType>()) 13938889Sjdp if (!cast<CXXRecordDecl>(RT->getDecl())->hasTrivialDestructor()) 14038889Sjdp OutDiag = diag::note_exits_dtor; 14189857Sobrien } 14238889Sjdp } 14338889Sjdp 14438889Sjdp return std::make_pair(InDiag, OutDiag); 14538889Sjdp } 14638889Sjdp 14738889Sjdp if (const TypedefDecl *TD = dyn_cast<TypedefDecl>(D)) { 14838889Sjdp if (TD->getUnderlyingType()->isVariablyModifiedType()) 14977298Sobrien return std::make_pair((unsigned) diag::note_protected_by_vla_typedef, 0); 15038889Sjdp } 15138889Sjdp 15238889Sjdp if (const TypeAliasDecl *TD = dyn_cast<TypeAliasDecl>(D)) { 15338889Sjdp if (TD->getUnderlyingType()->isVariablyModifiedType()) 15438889Sjdp return std::make_pair((unsigned) diag::note_protected_by_vla_type_alias, 0); 15560484Sobrien } 15638889Sjdp 15738889Sjdp return std::make_pair(0U, 0U); 15838889Sjdp} 15938889Sjdp 16038889Sjdp/// \brief Build scope information for a declaration that is part of a DeclStmt. 16138889Sjdpvoid JumpScopeChecker::BuildScopeInformation(Decl *D, unsigned &ParentScope) { 16238889Sjdp bool isCPlusPlus = this->S.getLangOptions().CPlusPlus; 16338889Sjdp 16438889Sjdp // If this decl causes a new scope, push and switch to it. 16538889Sjdp std::pair<unsigned,unsigned> Diags 16638889Sjdp = GetDiagForGotoScopeDecl(D, isCPlusPlus); 16738889Sjdp if (Diags.first || Diags.second) { 16838889Sjdp Scopes.push_back(GotoScope(ParentScope, Diags.first, Diags.second, 16938889Sjdp D->getLocation())); 17038889Sjdp ParentScope = Scopes.size()-1; 17138889Sjdp } 17238889Sjdp 17391041Sobrien // If the decl has an initializer, walk it with the potentially new 17438889Sjdp // scope we just installed. 17538889Sjdp if (VarDecl *VD = dyn_cast<VarDecl>(D)) 17638889Sjdp if (Expr *Init = VD->getInit()) 17738889Sjdp BuildScopeInformation(Init, ParentScope); 17838889Sjdp} 17938889Sjdp 18077298Sobrien/// BuildScopeInformation - The statements from CI to CE are known to form a 18160484Sobrien/// coherent VLA scope with a specified parent node. Walk through the 18238889Sjdp/// statements, adding any labels or gotos to LabelAndGotoScopes and recursively 18338889Sjdp/// walking the AST as needed. 18438889Sjdpvoid JumpScopeChecker::BuildScopeInformation(Stmt *S, unsigned ParentScope) { 18538889Sjdp bool SkipFirstSubStmt = false; 18638889Sjdp 18760484Sobrien // If we found a label, remember that it is in ParentScope scope. 18838889Sjdp switch (S->getStmtClass()) { 18938889Sjdp case Stmt::AddrLabelExprClass: 19077298Sobrien IndirectJumpTargets.push_back(cast<AddrLabelExpr>(S)->getLabel()); 19138889Sjdp break; 19238889Sjdp 19360484Sobrien case Stmt::IndirectGotoStmtClass: 19460484Sobrien // "goto *&&lbl;" is a special case which we treat as equivalent 19560484Sobrien // to a normal goto. In addition, we don't calculate scope in the 19677298Sobrien // operand (to avoid recording the address-of-label use), which 19738889Sjdp // works only because of the restricted set of expressions which 19860484Sobrien // we detect as constant targets. 19960484Sobrien if (cast<IndirectGotoStmt>(S)->getConstantTarget()) { 20038889Sjdp LabelAndGotoScopes[S] = ParentScope; 20189857Sobrien Jumps.push_back(S); 20277298Sobrien return; 20360484Sobrien } 20438889Sjdp 20538889Sjdp LabelAndGotoScopes[S] = ParentScope; 20660484Sobrien IndirectJumps.push_back(cast<IndirectGotoStmt>(S)); 20777298Sobrien break; 20838889Sjdp 20977298Sobrien case Stmt::SwitchStmtClass: 21077298Sobrien // Evaluate the condition variable before entering the scope of the switch 21138889Sjdp // statement. 21238889Sjdp if (VarDecl *Var = cast<SwitchStmt>(S)->getConditionVariable()) { 21338889Sjdp BuildScopeInformation(Var, ParentScope); 21438889Sjdp SkipFirstSubStmt = true; 21560484Sobrien } 21660484Sobrien // Fall through 21789857Sobrien 21891041Sobrien case Stmt::GotoStmtClass: 21960484Sobrien // Remember both what scope a goto is in as well as the fact that we have 22038889Sjdp // it. This makes the second scan not have to walk the AST again. 22189857Sobrien LabelAndGotoScopes[S] = ParentScope; 22238889Sjdp Jumps.push_back(S); 22377298Sobrien break; 22491041Sobrien 22589857Sobrien default: 22638889Sjdp break; 22738889Sjdp } 22889857Sobrien 22938889Sjdp for (Stmt::child_range CI = S->children(); CI; ++CI) { 23038889Sjdp if (SkipFirstSubStmt) { 23189857Sobrien SkipFirstSubStmt = false; 23289857Sobrien continue; 23360484Sobrien } 23460484Sobrien 23538889Sjdp Stmt *SubStmt = *CI; 23638889Sjdp if (SubStmt == 0) continue; 23738889Sjdp 23838889Sjdp // Cases, labels, and defaults aren't "scope parents". It's also 23938889Sjdp // important to handle these iteratively instead of recursively in 24038889Sjdp // order to avoid blowing out the stack. 24138889Sjdp while (true) { 24238889Sjdp Stmt *Next; 24338889Sjdp if (CaseStmt *CS = dyn_cast<CaseStmt>(SubStmt)) 24438889Sjdp Next = CS->getSubStmt(); 24538889Sjdp else if (DefaultStmt *DS = dyn_cast<DefaultStmt>(SubStmt)) 24638889Sjdp Next = DS->getSubStmt(); 24738889Sjdp else if (LabelStmt *LS = dyn_cast<LabelStmt>(SubStmt)) 24838889Sjdp Next = LS->getSubStmt(); 24938889Sjdp else 25038889Sjdp break; 25138889Sjdp 25238889Sjdp LabelAndGotoScopes[SubStmt] = ParentScope; 25338889Sjdp SubStmt = Next; 25438889Sjdp } 25538889Sjdp 25638889Sjdp // If this is a declstmt with a VLA definition, it defines a scope from here 25738889Sjdp // to the end of the containing context. 25838889Sjdp if (DeclStmt *DS = dyn_cast<DeclStmt>(SubStmt)) { 25938889Sjdp // The decl statement creates a scope if any of the decls in it are VLAs 26038889Sjdp // or have the cleanup attribute. 26138889Sjdp for (DeclStmt::decl_iterator I = DS->decl_begin(), E = DS->decl_end(); 26238889Sjdp I != E; ++I) 26338889Sjdp BuildScopeInformation(*I, ParentScope); 26489857Sobrien continue; 26538889Sjdp } 26638889Sjdp 26738889Sjdp // Disallow jumps into any part of an @try statement by pushing a scope and 26838889Sjdp // walking all sub-stmts in that scope. 26960484Sobrien if (ObjCAtTryStmt *AT = dyn_cast<ObjCAtTryStmt>(SubStmt)) { 27060484Sobrien // Recursively walk the AST for the @try part. 27138889Sjdp Scopes.push_back(GotoScope(ParentScope, 27238889Sjdp diag::note_protected_by_objc_try, 27360484Sobrien diag::note_exits_objc_try, 27460484Sobrien AT->getAtTryLoc())); 27560484Sobrien if (Stmt *TryPart = AT->getTryBody()) 27660484Sobrien BuildScopeInformation(TryPart, Scopes.size()-1); 27760484Sobrien 27838889Sjdp // Jump from the catch to the finally or try is not valid. 27938889Sjdp for (unsigned I = 0, N = AT->getNumCatchStmts(); I != N; ++I) { 28038889Sjdp ObjCAtCatchStmt *AC = AT->getCatchStmt(I); 28138889Sjdp Scopes.push_back(GotoScope(ParentScope, 28238889Sjdp diag::note_protected_by_objc_catch, 28338889Sjdp diag::note_exits_objc_catch, 28438889Sjdp AC->getAtCatchLoc())); 28538889Sjdp // @catches are nested and it isn't 28638889Sjdp BuildScopeInformation(AC->getCatchBody(), Scopes.size()-1); 28760484Sobrien } 28860484Sobrien 28960484Sobrien // Jump from the finally to the try or catch is not valid. 29060484Sobrien if (ObjCAtFinallyStmt *AF = AT->getFinallyStmt()) { 29160484Sobrien Scopes.push_back(GotoScope(ParentScope, 29238889Sjdp diag::note_protected_by_objc_finally, 29338889Sjdp diag::note_exits_objc_finally, 29438889Sjdp AF->getAtFinallyLoc())); 29538889Sjdp BuildScopeInformation(AF, Scopes.size()-1); 29638889Sjdp } 29777298Sobrien 29838889Sjdp continue; 29938889Sjdp } 30038889Sjdp 30138889Sjdp // Disallow jumps into the protected statement of an @synchronized, but 30238889Sjdp // allow jumps into the object expression it protects. 30360484Sobrien if (ObjCAtSynchronizedStmt *AS = dyn_cast<ObjCAtSynchronizedStmt>(SubStmt)){ 30438889Sjdp // Recursively walk the AST for the @synchronized object expr, it is 30538889Sjdp // evaluated in the normal scope. 30638889Sjdp BuildScopeInformation(AS->getSynchExpr(), ParentScope); 30738889Sjdp 30838889Sjdp // Recursively walk the AST for the @synchronized part, protected by a new 30938889Sjdp // scope. 31038889Sjdp Scopes.push_back(GotoScope(ParentScope, 31138889Sjdp diag::note_protected_by_objc_synchronized, 31238889Sjdp diag::note_exits_objc_synchronized, 31338889Sjdp AS->getAtSynchronizedLoc())); 31438889Sjdp BuildScopeInformation(AS->getSynchBody(), Scopes.size()-1); 31538889Sjdp continue; 31638889Sjdp } 31738889Sjdp 31838889Sjdp // Disallow jumps into any part of a C++ try statement. This is pretty 31938889Sjdp // much the same as for Obj-C. 32038889Sjdp if (CXXTryStmt *TS = dyn_cast<CXXTryStmt>(SubStmt)) { 32191041Sobrien Scopes.push_back(GotoScope(ParentScope, 32238889Sjdp diag::note_protected_by_cxx_try, 32338889Sjdp diag::note_exits_cxx_try, 32438889Sjdp TS->getSourceRange().getBegin())); 32538889Sjdp if (Stmt *TryBlock = TS->getTryBlock()) 32638889Sjdp BuildScopeInformation(TryBlock, Scopes.size()-1); 32738889Sjdp 32877298Sobrien // Jump from the catch into the try is not allowed either. 32960484Sobrien for (unsigned I = 0, E = TS->getNumHandlers(); I != E; ++I) { 33038889Sjdp CXXCatchStmt *CS = TS->getHandler(I); 33138889Sjdp Scopes.push_back(GotoScope(ParentScope, 33238889Sjdp diag::note_protected_by_cxx_catch, 33338889Sjdp diag::note_exits_cxx_catch, 33438889Sjdp CS->getSourceRange().getBegin())); 33560484Sobrien BuildScopeInformation(CS->getHandlerBlock(), Scopes.size()-1); 33638889Sjdp } 33738889Sjdp 33877298Sobrien continue; 33938889Sjdp } 34038889Sjdp 34160484Sobrien // Recursively walk the AST. 34260484Sobrien BuildScopeInformation(SubStmt, ParentScope); 34360484Sobrien } 34477298Sobrien} 34538889Sjdp 34660484Sobrien/// VerifyJumps - Verify each element of the Jumps array to see if they are 34760484Sobrien/// valid, emitting diagnostics if not. 34838889Sjdpvoid JumpScopeChecker::VerifyJumps() { 34989857Sobrien while (!Jumps.empty()) { 35077298Sobrien Stmt *Jump = Jumps.pop_back_val(); 35160484Sobrien 35238889Sjdp // With a goto, 35338889Sjdp if (GotoStmt *GS = dyn_cast<GotoStmt>(Jump)) { 35460484Sobrien CheckJump(GS, GS->getLabel()->getStmt(), GS->getGotoLoc(), 35538889Sjdp diag::err_goto_into_protected_scope); 35638889Sjdp continue; 35777298Sobrien } 35877298Sobrien 35938889Sjdp // We only get indirect gotos here when they have a constant target. 36038889Sjdp if (IndirectGotoStmt *IGS = dyn_cast<IndirectGotoStmt>(Jump)) { 36138889Sjdp LabelDecl *Target = IGS->getConstantTarget(); 36260484Sobrien CheckJump(IGS, Target->getStmt(), IGS->getGotoLoc(), 36360484Sobrien diag::err_goto_into_protected_scope); 36489857Sobrien continue; 36591041Sobrien } 36660484Sobrien 36738889Sjdp SwitchStmt *SS = cast<SwitchStmt>(Jump); 36891041Sobrien for (SwitchCase *SC = SS->getSwitchCaseList(); SC; 36989857Sobrien SC = SC->getNextSwitchCase()) { 37038889Sjdp assert(LabelAndGotoScopes.count(SC) && "Case not visited?"); 37177298Sobrien CheckJump(SS, SC, SC->getLocStart(), 37289857Sobrien diag::err_switch_into_protected_scope); 37338889Sjdp } 37438889Sjdp } 37589857Sobrien} 37638889Sjdp 37738889Sjdp/// VerifyIndirectJumps - Verify whether any possible indirect jump 37889857Sobrien/// might cross a protection boundary. Unlike direct jumps, indirect 37989857Sobrien/// jumps count cleanups as protection boundaries: since there's no 38060484Sobrien/// way to know where the jump is going, we can't implicitly run the 38160484Sobrien/// right cleanups the way we can with direct jumps. 38238889Sjdp/// 38338889Sjdp/// Thus, an indirect jump is "trivial" if it bypasses no 38438889Sjdp/// initializations and no teardowns. More formally, an indirect jump 38538889Sjdp/// from A to B is trivial if the path out from A to DCA(A,B) is 38638889Sjdp/// trivial and the path in from DCA(A,B) to B is trivial, where 38738889Sjdp/// DCA(A,B) is the deepest common ancestor of A and B. 38838889Sjdp/// Jump-triviality is transitive but asymmetric. 38938889Sjdp/// 39038889Sjdp/// A path in is trivial if none of the entered scopes have an InDiag. 39138889Sjdp/// A path out is trivial is none of the exited scopes have an OutDiag. 39238889Sjdp/// 39338889Sjdp/// Under these definitions, this function checks that the indirect 39438889Sjdp/// jump between A and B is trivial for every indirect goto statement A 39538889Sjdp/// and every label B whose address was taken in the function. 39638889Sjdpvoid JumpScopeChecker::VerifyIndirectJumps() { 39738889Sjdp if (IndirectJumps.empty()) return; 39838889Sjdp 39938889Sjdp // If there aren't any address-of-label expressions in this function, 40038889Sjdp // complain about the first indirect goto. 40138889Sjdp if (IndirectJumpTargets.empty()) { 40238889Sjdp S.Diag(IndirectJumps[0]->getGotoLoc(), 40338889Sjdp diag::err_indirect_goto_without_addrlabel); 40438889Sjdp return; 40538889Sjdp } 40638889Sjdp 40738889Sjdp // Collect a single representative of every scope containing an 40838889Sjdp // indirect goto. For most code bases, this substantially cuts 40938889Sjdp // down on the number of jump sites we'll have to consider later. 41038889Sjdp typedef std::pair<unsigned, IndirectGotoStmt*> JumpScope; 41189857Sobrien llvm::SmallVector<JumpScope, 32> JumpScopes; 41238889Sjdp { 41338889Sjdp llvm::DenseMap<unsigned, IndirectGotoStmt*> JumpScopesMap; 41438889Sjdp for (llvm::SmallVectorImpl<IndirectGotoStmt*>::iterator 41538889Sjdp I = IndirectJumps.begin(), E = IndirectJumps.end(); I != E; ++I) { 41660484Sobrien IndirectGotoStmt *IG = *I; 41760484Sobrien assert(LabelAndGotoScopes.count(IG) && 41838889Sjdp "indirect jump didn't get added to scopes?"); 41938889Sjdp unsigned IGScope = LabelAndGotoScopes[IG]; 42060484Sobrien IndirectGotoStmt *&Entry = JumpScopesMap[IGScope]; 42160484Sobrien if (!Entry) Entry = IG; 42260484Sobrien } 42360484Sobrien JumpScopes.reserve(JumpScopesMap.size()); 42438889Sjdp for (llvm::DenseMap<unsigned, IndirectGotoStmt*>::iterator 42538889Sjdp I = JumpScopesMap.begin(), E = JumpScopesMap.end(); I != E; ++I) 42638889Sjdp JumpScopes.push_back(*I); 42738889Sjdp } 42838889Sjdp 42938889Sjdp // Collect a single representative of every scope containing a 43038889Sjdp // label whose address was taken somewhere in the function. 43138889Sjdp // For most code bases, there will be only one such scope. 43238889Sjdp llvm::DenseMap<unsigned, LabelDecl*> TargetScopes; 43360484Sobrien for (llvm::SmallVectorImpl<LabelDecl*>::iterator 43460484Sobrien I = IndirectJumpTargets.begin(), E = IndirectJumpTargets.end(); 43560484Sobrien I != E; ++I) { 43660484Sobrien LabelDecl *TheLabel = *I; 43760484Sobrien assert(LabelAndGotoScopes.count(TheLabel->getStmt()) && 43838889Sjdp "Referenced label didn't get added to scopes?"); 43938889Sjdp unsigned LabelScope = LabelAndGotoScopes[TheLabel->getStmt()]; 44038889Sjdp LabelDecl *&Target = TargetScopes[LabelScope]; 44138889Sjdp if (!Target) Target = TheLabel; 44238889Sjdp } 44338889Sjdp 44438889Sjdp // For each target scope, make sure it's trivially reachable from 44538889Sjdp // every scope containing a jump site. 44677298Sobrien // 44738889Sjdp // A path between scopes always consists of exitting zero or more 44877298Sobrien // scopes, then entering zero or more scopes. We build a set of 44977298Sobrien // of scopes S from which the target scope can be trivially 45038889Sjdp // entered, then verify that every jump scope can be trivially 45177298Sobrien // exitted to reach a scope in S. 45277298Sobrien llvm::BitVector Reachable(Scopes.size(), false); 45338889Sjdp for (llvm::DenseMap<unsigned,LabelDecl*>::iterator 45438889Sjdp TI = TargetScopes.begin(), TE = TargetScopes.end(); TI != TE; ++TI) { 45589857Sobrien unsigned TargetScope = TI->first; 45691041Sobrien LabelDecl *TargetLabel = TI->second; 45789857Sobrien 45889857Sobrien Reachable.reset(); 45938889Sjdp 46038889Sjdp // Mark all the enclosing scopes from which you can safely jump 46189857Sobrien // into the target scope. 'Min' will end up being the index of 46238889Sjdp // the shallowest such scope. 46378828Sobrien unsigned Min = TargetScope; 46478828Sobrien while (true) { 46538889Sjdp Reachable.set(Min); 46638889Sjdp 46738889Sjdp // Don't go beyond the outermost scope. 46838889Sjdp if (Min == 0) break; 46977298Sobrien 47038889Sjdp // Stop if we can't trivially enter the current scope. 47177298Sobrien if (Scopes[Min].InDiag) break; 47277298Sobrien 47338889Sjdp Min = Scopes[Min].ParentScope; 47477298Sobrien } 47538889Sjdp 47638889Sjdp // Walk through all the jump sites, checking that they can trivially 47789857Sobrien // reach this label scope. 47889857Sobrien for (llvm::SmallVectorImpl<JumpScope>::iterator 47989857Sobrien I = JumpScopes.begin(), E = JumpScopes.end(); I != E; ++I) { 48091041Sobrien unsigned Scope = I->first; 48138889Sjdp 48238889Sjdp // Walk out the "scope chain" for this scope, looking for a scope 48389857Sobrien // we've marked reachable. For well-formed code this amortizes 48438889Sjdp // to O(JumpScopes.size() / Scopes.size()): we only iterate 48538889Sjdp // when we see something unmarked, and in well-formed code we 48638889Sjdp // mark everything we iterate past. 48738889Sjdp bool IsReachable = false; 48838889Sjdp while (true) { 48938889Sjdp if (Reachable.test(Scope)) { 49038889Sjdp // If we find something reachable, mark all the scopes we just 49138889Sjdp // walked through as reachable. 49238889Sjdp for (unsigned S = I->first; S != Scope; S = Scopes[S].ParentScope) 49360484Sobrien Reachable.set(S); 49438889Sjdp IsReachable = true; 49538889Sjdp break; 49638889Sjdp } 49738889Sjdp 49838889Sjdp // Don't walk out if we've reached the top-level scope or we've 49938889Sjdp // gotten shallower than the shallowest reachable scope. 50038889Sjdp if (Scope == 0 || Scope < Min) break; 50138889Sjdp 50238889Sjdp // Don't walk out through an out-diagnostic. 50360484Sobrien if (Scopes[Scope].OutDiag) break; 50438889Sjdp 50538889Sjdp Scope = Scopes[Scope].ParentScope; 50638889Sjdp } 50738889Sjdp 50838889Sjdp // Only diagnose if we didn't find something. 50938889Sjdp if (IsReachable) continue; 51038889Sjdp 51189857Sobrien DiagnoseIndirectJump(I->second, I->first, TargetLabel, TargetScope); 51238889Sjdp } 51338889Sjdp } 51438889Sjdp} 51560484Sobrien 51638889Sjdp/// Diagnose an indirect jump which is known to cross scopes. 51738889Sjdpvoid JumpScopeChecker::DiagnoseIndirectJump(IndirectGotoStmt *Jump, 51878828Sobrien unsigned JumpScope, 51989857Sobrien LabelDecl *Target, 52089857Sobrien unsigned TargetScope) { 52138889Sjdp assert(JumpScope != TargetScope); 52238889Sjdp 52338889Sjdp S.Diag(Jump->getGotoLoc(), diag::err_indirect_goto_in_protected_scope); 52438889Sjdp S.Diag(Target->getStmt()->getIdentLoc(), diag::note_indirect_goto_target); 52538889Sjdp 52678828Sobrien unsigned Common = GetDeepestCommonScope(JumpScope, TargetScope); 52778828Sobrien 52878828Sobrien // Walk out the scope chain until we reach the common ancestor. 52978828Sobrien for (unsigned I = JumpScope; I != Common; I = Scopes[I].ParentScope) 53078828Sobrien if (Scopes[I].OutDiag) 53160484Sobrien S.Diag(Scopes[I].Loc, Scopes[I].OutDiag); 53260484Sobrien 53377298Sobrien // Now walk into the scopes containing the label whose address was taken. 53477298Sobrien for (unsigned I = TargetScope; I != Common; I = Scopes[I].ParentScope) 53577298Sobrien if (Scopes[I].InDiag) 53677298Sobrien S.Diag(Scopes[I].Loc, Scopes[I].InDiag); 53777298Sobrien} 53889857Sobrien 53989857Sobrien/// CheckJump - Validate that the specified jump statement is valid: that it is 54038889Sjdp/// jumping within or out of its current scope, not into a deeper one. 54178828Sobrienvoid JumpScopeChecker::CheckJump(Stmt *From, Stmt *To, 54278828Sobrien SourceLocation DiagLoc, unsigned JumpDiag) { 54378828Sobrien assert(LabelAndGotoScopes.count(From) && "Jump didn't get added to scopes?"); 54460484Sobrien unsigned FromScope = LabelAndGotoScopes[From]; 54578828Sobrien 54660484Sobrien assert(LabelAndGotoScopes.count(To) && "Jump didn't get added to scopes?"); 54778828Sobrien unsigned ToScope = LabelAndGotoScopes[To]; 54878828Sobrien 54960484Sobrien // Common case: exactly the same scope, which is fine. 55078828Sobrien if (FromScope == ToScope) return; 55189857Sobrien 55289857Sobrien unsigned CommonScope = GetDeepestCommonScope(FromScope, ToScope); 55378828Sobrien 55478828Sobrien // It's okay to jump out from a nested scope. 55589857Sobrien if (CommonScope == ToScope) return; 55689857Sobrien 55778828Sobrien // Pull out (and reverse) any scopes we might need to diagnose skipping. 55878828Sobrien llvm::SmallVector<unsigned, 10> ToScopes; 55978828Sobrien for (unsigned I = ToScope; I != CommonScope; I = Scopes[I].ParentScope) 56078828Sobrien if (Scopes[I].InDiag) 56178828Sobrien ToScopes.push_back(I); 56278828Sobrien 56378828Sobrien // If the only scopes present are cleanup scopes, we're okay. 56478828Sobrien if (ToScopes.empty()) return; 56578828Sobrien 56678828Sobrien S.Diag(DiagLoc, JumpDiag); 56778828Sobrien 56838889Sjdp // Emit diagnostics for whatever is left in ToScopes. 56938889Sjdp for (unsigned i = 0, e = ToScopes.size(); i != e; ++i) 57038889Sjdp S.Diag(Scopes[ToScopes[i]].Loc, Scopes[ToScopes[i]].InDiag); 57138889Sjdp} 57238889Sjdp 57338889Sjdpvoid Sema::DiagnoseInvalidJumps(Stmt *Body) { 57438889Sjdp (void)JumpScopeChecker(Body, *this); 57538889Sjdp} 57638889Sjdp