[clang] Implement Intercal compatibility feature

[lpereira]

Summary

This commit is part of a grand series of changes that aims to reduce
the amount of evil in the world. The "goto" statement is one of such
evils that must be fought; however, due to both compatibility reasons,
and lack of support in mainstream compilers, it can't be removed just
now.

This patch implements Intercal's "comefrom" statement in both C and C++
modes.

When comparing to the original implementation, the astute reader will
note that behavior such as producing an error when more than one line
comes from another label or not properly handling when a line comes
from a label and goes to a label. This is to keep the tone of both C
and C++ languages, with regards to undefined behavior.

[lebedev.ri]

Please add docs, release notes entry, and most importantly, tests!

include/clang-c/Index.h

enum CXCursorKind {
   /** \brief OpenMP target teams distribute parallel for simd directive.
    */
   CXCursor_OMPTargetTeamsDistributeParallelForSimdDirective = 278,
 
   /** \brief OpenMP target teams distribute simd directive.
    */
   CXCursor_OMPTargetTeamsDistributeSimdDirective = 279,
 
-  CXCursor_LastStmt = CXCursor_OMPTargetTeamsDistributeSimdDirective,
+  /** \brief Intercal compatibility.
+   */
+  CXCursor_ComeFromStmt = 280,
+
+  CXCursor_LastStmt = CXCursor_ComeFromStmt,
 
   /**
    * \brief Cursor that represents the translation unit itself.
    *
    * The translation unit cursor exists primarily to act as the root
    * cursor for traversing the contents of a translation unit.
    */
   CXCursor_TranslationUnit               = 300,

include/clang/AST/RecursiveASTVisitor.h

 DEF_TRAVERSE_STMT(CXXTryStmt, {})
 DEF_TRAVERSE_STMT(CaseStmt, {})
 DEF_TRAVERSE_STMT(CompoundStmt, {})
 DEF_TRAVERSE_STMT(ContinueStmt, {})
 DEF_TRAVERSE_STMT(DefaultStmt, {})
 DEF_TRAVERSE_STMT(DoStmt, {})
 DEF_TRAVERSE_STMT(ForStmt, {})
 DEF_TRAVERSE_STMT(GotoStmt, {})
+DEF_TRAVERSE_STMT(ComeFromStmt, {})
 DEF_TRAVERSE_STMT(IfStmt, {})
 DEF_TRAVERSE_STMT(IndirectGotoStmt, {})
 DEF_TRAVERSE_STMT(LabelStmt, {})
 DEF_TRAVERSE_STMT(AttributedStmt, {})
 DEF_TRAVERSE_STMT(NullStmt, {})
 DEF_TRAVERSE_STMT(ObjCAtCatchStmt, {})
 DEF_TRAVERSE_STMT(ObjCAtFinallyStmt, {})
 DEF_TRAVERSE_STMT(ObjCAtSynchronizedStmt, {})

include/clang/AST/Stmt.h

public:
   }
 
   // Iterators
   child_range children() {
     return child_range(&SubExprs[0], &SubExprs[0]+END_EXPR);
   }
 };
 
+/// ComeFromStmt - This represents a comefrom statement.
+///
+class ComeFromStmt : public Stmt {
+  LabelDecl *Label;
+  SourceLocation ComeFromLoc;
+  SourceLocation LabelLoc;
+public:
+  ComeFromStmt(LabelDecl *label, SourceLocation CFL, SourceLocation LL)
+    : Stmt(ComeFromStmtClass), Label(label), ComeFromLoc(CFL), LabelLoc(LL) {}
+
+  /// \brief Build an empty comefrom statement.
+  explicit ComeFromStmt(EmptyShell Empty) : Stmt(ComeFromStmtClass, Empty) { }
+
+  LabelDecl *getLabel() const { return Label; }
+  void setLabel(LabelDecl *D) { Label = D; }
+
+  SourceLocation getComeFromLoc() const { return ComeFromLoc; }
+  void setComeFromLoc(SourceLocation L) { ComeFromLoc = L; }
+  SourceLocation getLabelLoc() const { return LabelLoc; }
+  void setLabelLoc(SourceLocation L) { LabelLoc = L; }
+
+  SourceLocation getLocStart() const LLVM_READONLY { return ComeFromLoc; }
+  SourceLocation getLocEnd() const LLVM_READONLY { return LabelLoc; }
+
+  static bool classof(const Stmt *T) {
+    return T->getStmtClass() == ComeFromStmtClass;
+  }
+
+  // Iterators
+  child_range children() {
+    return child_range(child_iterator(), child_iterator());
+  }
+};
+
 /// GotoStmt - This represents a direct goto.
 class GotoStmt : public Stmt {
   LabelDecl *Label;
   SourceLocation GotoLoc;
   SourceLocation LabelLoc;
 
 public:
   GotoStmt(LabelDecl *label, SourceLocation GL, SourceLocation LL)

include/clang/Basic/StmtNodes.td

 def AttributedStmt : Stmt;
 def IfStmt : Stmt;
 def SwitchStmt : Stmt;
 def WhileStmt : Stmt;
 def DoStmt : Stmt;
 def ForStmt : Stmt;
 def GotoStmt : Stmt;
 def IndirectGotoStmt : Stmt;
+def ComeFromStmt : Stmt;
 def ContinueStmt : Stmt;
 def BreakStmt : Stmt;
 def ReturnStmt : Stmt;
 def DeclStmt  : Stmt;
 def SwitchCase : Stmt<1>;
 def CaseStmt : DStmt<SwitchCase>;
 def DefaultStmt : DStmt<SwitchCase>;
 def CapturedStmt : Stmt;

include/clang/Basic/TokenKinds.def

 KEYWORD(do                          , KEYALL)
 KEYWORD(double                      , KEYALL)
 KEYWORD(else                        , KEYALL)
 KEYWORD(enum                        , KEYALL)
 KEYWORD(extern                      , KEYALL)
 KEYWORD(float                       , KEYALL)
 KEYWORD(for                         , KEYALL)
 KEYWORD(goto                        , KEYALL)
+KEYWORD(comefrom                    , KEYALL)
 KEYWORD(if                          , KEYALL)
 KEYWORD(inline                      , KEYC99|KEYCXX|KEYGNU)
 KEYWORD(int                         , KEYALL)
 KEYWORD(long                        , KEYALL)
 KEYWORD(register                    , KEYALL)
 KEYWORD(restrict                    , KEYC99)
 KEYWORD(return                      , KEYALL)
 KEYWORD(short                       , KEYALL)

include/clang/Parse/Parser.h

bool ParseParenExprOrCondition(StmtResult *InitStmt,
                                  Sema::ConditionResult &CondResult,
                                  SourceLocation Loc,
                                  Sema::ConditionKind CK);
   StmtResult ParseIfStatement(SourceLocation *TrailingElseLoc);
   StmtResult ParseSwitchStatement(SourceLocation *TrailingElseLoc);
   StmtResult ParseWhileStatement(SourceLocation *TrailingElseLoc);
   StmtResult ParseDoStatement();
   StmtResult ParseForStatement(SourceLocation *TrailingElseLoc);
+  StmtResult ParseComeFromStatement();
   StmtResult ParseGotoStatement();
   StmtResult ParseContinueStatement();
   StmtResult ParseBreakStatement();
   StmtResult ParseReturnStatement();
   StmtResult ParseAsmStatement(bool &msAsm);
   StmtResult ParseMicrosoftAsmStatement(SourceLocation AsmLoc);
   StmtResult ParsePragmaLoopHint(StmtVector &Stmts,
                                  AllowedConstructsKind Allowed,

include/clang/Sema/Sema.h

StmtResult BuildCXXForRangeStmt(SourceLocation ForLoc,
                                   SourceLocation ColonLoc,
                                   Stmt *RangeDecl, Stmt *Begin, Stmt *End,
                                   Expr *Cond, Expr *Inc,
                                   Stmt *LoopVarDecl,
                                   SourceLocation RParenLoc,
                                   BuildForRangeKind Kind);
   StmtResult FinishCXXForRangeStmt(Stmt *ForRange, Stmt *Body);
 
+  StmtResult ActOnComeFromStmt(SourceLocation GotoLoc,
+                               SourceLocation LabelLoc,
+                               LabelDecl *TheDecl);
   StmtResult ActOnGotoStmt(SourceLocation GotoLoc,
                            SourceLocation LabelLoc,
                            LabelDecl *TheDecl);
   StmtResult ActOnIndirectGotoStmt(SourceLocation GotoLoc,
                                    SourceLocation StarLoc,
                                    Expr *DestExp);
   StmtResult ActOnContinueStmt(SourceLocation ContinueLoc, Scope *CurScope);
   StmtResult ActOnBreakStmt(SourceLocation BreakLoc, Scope *CurScope);

lib/AST/StmtPrinter.cpp

if (NestedNameSpecifier *Qualifier
         = Node->getQualifierLoc().getNestedNameSpecifier())
     Qualifier->print(OS, Policy);
   
   OS << Node->getNameInfo() << ") ";
   
   PrintRawCompoundStmt(Node->getSubStmt());
 }
 
+void StmtPrinter::VisitComeFromStmt(ComeFromStmt *Node) {
+  Indent() << "comefrom " << Node->getLabel()->getName() << ";";
+  if (Policy.IncludeNewlines) OS << "\n";
+}
+
 void StmtPrinter::VisitGotoStmt(GotoStmt *Node) {
   Indent() << "goto " << Node->getLabel()->getName() << ";";
   if (Policy.IncludeNewlines) OS << "\n";
 }
 
 void StmtPrinter::VisitIndirectGotoStmt(IndirectGotoStmt *Node) {
   Indent() << "goto *";
   PrintExpr(Node->getTarget());

lib/CodeGen/CGStmt.cpp

void CodeGenFunction::EmitStmt(const Stmt *S, ArrayRef<const Attr *> Attrs) {
   case Stmt::MSDependentExistsStmtClass:
     llvm_unreachable("invalid statement class to emit generically");
   case Stmt::NullStmtClass:
   case Stmt::CompoundStmtClass:
   case Stmt::DeclStmtClass:
   case Stmt::LabelStmtClass:
   case Stmt::AttributedStmtClass:
   case Stmt::GotoStmtClass:
+  case Stmt::ComeFromStmtClass:
   case Stmt::BreakStmtClass:
   case Stmt::ContinueStmtClass:
   case Stmt::DefaultStmtClass:
   case Stmt::CaseStmtClass:
   case Stmt::SEHLeaveStmtClass:
     llvm_unreachable("should have emitted these statements as simple");
 
 #define STMT(Type, Base)
bool CodeGenFunction::EmitSimpleStmt(const Stmt *S) {
   default: return false;
   case Stmt::NullStmtClass: break;
   case Stmt::CompoundStmtClass: EmitCompoundStmt(cast<CompoundStmt>(*S)); break;
   case Stmt::DeclStmtClass:     EmitDeclStmt(cast<DeclStmt>(*S));         break;
   case Stmt::LabelStmtClass:    EmitLabelStmt(cast<LabelStmt>(*S));       break;
   case Stmt::AttributedStmtClass:
                             EmitAttributedStmt(cast<AttributedStmt>(*S)); break;
   case Stmt::GotoStmtClass:     EmitGotoStmt(cast<GotoStmt>(*S));         break;
+  case Stmt::ComeFromStmtClass: EmitComeFromStmt(cast<ComeFromStmt>(*S)); break;
   case Stmt::BreakStmtClass:    EmitBreakStmt(cast<BreakStmt>(*S));       break;
   case Stmt::ContinueStmtClass: EmitContinueStmt(cast<ContinueStmt>(*S)); break;
   case Stmt::DefaultStmtClass:  EmitDefaultStmt(cast<DefaultStmt>(*S));   break;
   case Stmt::CaseStmtClass:     EmitCaseStmt(cast<CaseStmt>(*S));         break;
   case Stmt::SEHLeaveStmtClass: EmitSEHLeaveStmt(cast<SEHLeaveStmt>(*S)); break;
   }
 
   return true;
void CodeGenFunction::LexicalScope::rescopeLabels() {
   // Reparent the labels if the new scope also has cleanups.
   if (innermostScope != EHScopeStack::stable_end() && ParentScope) {
     ParentScope->Labels.append(Labels.begin(), Labels.end());
   }
 }
 
 
 void CodeGenFunction::EmitLabelStmt(const LabelStmt &S) {
+  JumpDest &Dest = ComeFromMap[S.getDecl()];
+  if (Dest.isValid()) {
+    EmitBranchThroughCleanup(Dest);
+  } else {
     EmitLabel(S.getDecl());
     EmitStmt(S.getSubStmt());
   }
+}
 
 void CodeGenFunction::EmitAttributedStmt(const AttributedStmt &S) {
   EmitStmt(S.getSubStmt(), S.getAttrs());
 }
 
 void CodeGenFunction::EmitGotoStmt(const GotoStmt &S) {
   // If this code is reachable then emit a stop point (if generating
   // debug info). We have to do this ourselves because we are on the
   // "simple" statement path.
   if (HaveInsertPoint())
     EmitStopPoint(&S);
 
   EmitBranchThroughCleanup(getJumpDestForLabel(S.getLabel()));
 }
 
+void CodeGenFunction::EmitComeFromStmt(const ComeFromStmt &S) {
+  auto L = S.getLabel();
+  EmitLabel(L);
+  ComeFromMap[L] = getJumpDestForLabel(L);
+}
 
 void CodeGenFunction::EmitIndirectGotoStmt(const IndirectGotoStmt &S) {
   if (const LabelDecl *Target = S.getConstantTarget()) {
     EmitBranchThroughCleanup(getJumpDestForLabel(Target));
     return;
   }
 
   // Ensure that we have an i8* for our PHI node.

lib/CodeGen/CodeGenFunction.h

private:
 
   /// Track escaped local variables with auto storage. Used during SEH
   /// outlining to produce a call to llvm.localescape.
   llvm::DenseMap<llvm::AllocaInst *, int> EscapedLocals;
 
   /// LabelMap - This keeps track of the LLVM basic block for each C label.
   llvm::DenseMap<const LabelDecl*, JumpDest> LabelMap;
 
+  /// ComeFromMap - This keeps track of the LLVM basic block for each comefrom stmt.
+  llvm::DenseMap<const LabelDecl*, JumpDest> ComeFromMap;
+
   // BreakContinueStack - This keeps track of where break and continue
   // statements should jump to.
   struct BreakContinue {
     BreakContinue(JumpDest Break, JumpDest Continue)
       : BreakBlock(Break), ContinueBlock(Continue) {}
 
     JumpDest BreakBlock;
     JumpDest ContinueBlock;
Address EmitCompoundStmtWithoutScope(const CompoundStmt &S,
                                                 AggValueSlot::ignored());
 
   /// EmitLabel - Emit the block for the given label. It is legal to call this
   /// function even if there is no current insertion point.
   void EmitLabel(const LabelDecl *D); // helper for EmitLabelStmt.
 
   void EmitLabelStmt(const LabelStmt &S);
   void EmitAttributedStmt(const AttributedStmt &S);
+  void EmitComeFromStmt(const ComeFromStmt &S);
   void EmitGotoStmt(const GotoStmt &S);
   void EmitIndirectGotoStmt(const IndirectGotoStmt &S);
   void EmitIfStmt(const IfStmt &S);
 
   void EmitWhileStmt(const WhileStmt &S,
                      ArrayRef<const Attr *> Attrs = None);
   void EmitDoStmt(const DoStmt &S, ArrayRef<const Attr *> Attrs = None);
   void EmitForStmt(const ForStmt &S,

lib/Parse/ParseStmt.cpp

case tok::kw_do:                  // C99 6.8.5.2: do-statement
     break;
   case tok::kw_for:                 // C99 6.8.5.3: for-statement
     return ParseForStatement(TrailingElseLoc);
 
   case tok::kw_goto:                // C99 6.8.6.1: goto-statement
     Res = ParseGotoStatement();
     SemiError = "goto";
     break;
+  case tok::kw_comefrom:            // Intercal compatibility
+    Res = ParseComeFromStatement();
+    SemiError = "comefrom";
+    break;
   case tok::kw_continue:            // C99 6.8.6.2: continue-statement
     Res = ParseContinueStatement();
     SemiError = "continue";
     break;
   case tok::kw_break:               // C99 6.8.6.3: break-statement
     Res = ParseBreakStatement();
     SemiError = "break";
     break;
StmtResult Parser::ParseGotoStatement() {
   } else {
     Diag(Tok, diag::err_expected) << tok::identifier;
     return StmtError();
   }
 
   return Res;
 }
 
+/// ParseComeFromStatement
+///       jump-statement:
+///         'comefrom' identifier ';'
+///
+/// Note: this lets the caller parse the end ';'.
+///
+StmtResult Parser::ParseComeFromStatement() {
+  assert(Tok.is(tok::kw_comefrom) && "Not a comefrom stmt!");
+  SourceLocation ComeFromLoc = ConsumeToken();  // eat the 'comefrom'.
+
+  StmtResult Res;
+  if (Tok.is(tok::identifier)) {
+    LabelDecl *LD = Actions.LookupOrCreateLabel(Tok.getIdentifierInfo(),
+                                                Tok.getLocation());
+    Res = Actions.ActOnComeFromStmt(ComeFromLoc, Tok.getLocation(), LD);
+    ConsumeToken();
+  } else {
+    Diag(Tok, diag::err_expected) << tok::identifier;
+    return StmtError();
+  }
+
+  return Res;
+}
+
+
 /// ParseContinueStatement
 ///       jump-statement:
 ///         'continue' ';'
 ///
 /// Note: this lets the caller parse the end ';'.
 ///
 StmtResult Parser::ParseContinueStatement() {
   SourceLocation ContinueLoc = ConsumeToken();  // eat the 'continue'.

lib/Sema/SemaStmt.cpp

public:
     void VisitBreakStmt(BreakStmt *S) {
       FoundDecl = true;
     }
 
     void VisitGotoStmt(GotoStmt *S) {
       FoundDecl = true;
     }
 
+    void VisitComeFromStmt(ComeFromStmt *S) {
+      FoundDecl = true;
+    }
+
     void VisitCastExpr(CastExpr *E) {
       if (E->getCastKind() == CK_LValueToRValue)
         CheckLValueToRValueCast(E->getSubExpr());
       else
         Visit(E->getSubExpr());
     }
 
     void CheckLValueToRValueCast(Expr *E) {

 StmtResult Sema::ActOnGotoStmt(SourceLocation GotoLoc,
                                SourceLocation LabelLoc,
                                LabelDecl *TheDecl) {
   setFunctionHasBranchIntoScope();
   TheDecl->markUsed(Context);
   return new (Context) GotoStmt(TheDecl, GotoLoc, LabelLoc);
 }
 
+StmtResult Sema::ActOnComeFromStmt(SourceLocation ComeFromLoc,
+                                   SourceLocation LabelLoc,
+                                   LabelDecl *TheDecl) {
+  getCurFunction()->setHasBranchIntoScope();
+  TheDecl->markUsed(Context);
+  return new (Context) ComeFromStmt(TheDecl, ComeFromLoc, LabelLoc);
+}
+
 StmtResult
 Sema::ActOnIndirectGotoStmt(SourceLocation GotoLoc, SourceLocation StarLoc,
                             Expr *E) {
   // Convert operand to void*
   if (!E->isTypeDependent()) {
     QualType ETy = E->getType();
     QualType DestTy = Context.getPointerType(Context.VoidTy.withConst());
     ExprResult ExprRes = E;

lib/Sema/TreeTransform.h

TreeTransform<Derived>::TransformForStmt(ForStmt *S) {
 
   return getDerived().RebuildForStmt(S->getForLoc(), S->getLParenLoc(),
                                      Init.get(), Cond, FullInc,
                                      S->getRParenLoc(), Body.get());
 }
 
 template<typename Derived>
 StmtResult
+TreeTransform<Derived>::TransformComeFromStmt(ComeFromStmt *S) {
+  return S;
+}
+
+template<typename Derived>
+StmtResult
 TreeTransform<Derived>::TransformGotoStmt(GotoStmt *S) {
   Decl *LD = getDerived().TransformDecl(S->getLabel()->getLocation(),
                                         S->getLabel());
   if (!LD)
     return StmtError();
 
   // Goto statements must always be rebuilt, to resolve the label.
   return getDerived().RebuildGotoStmt(S->getGotoLoc(), S->getLabelLoc(),

lib/StaticAnalyzer/Core/ExprEngine.cpp

switch (S->getStmtClass()) {
     case Stmt::CaseStmtClass:
     case Stmt::CompoundStmtClass:
     case Stmt::ContinueStmtClass:
     case Stmt::CXXForRangeStmtClass:
     case Stmt::DefaultStmtClass:
     case Stmt::DoStmtClass:
     case Stmt::ForStmtClass:
     case Stmt::GotoStmtClass:
+    case Stmt::ComeFromStmtClass:
     case Stmt::IfStmtClass:
     case Stmt::IndirectGotoStmtClass:
     case Stmt::LabelStmtClass:
     case Stmt::NoStmtClass:
     case Stmt::NullStmtClass:
     case Stmt::SwitchStmtClass:
     case Stmt::WhileStmtClass:
     case Expr::MSDependentExistsStmtClass:

tools/libclang/CXCursor.cpp

CXCursor cxcursor::MakeCXCursor(const Stmt *S, const Decl *Parent,
   case Stmt::DoStmtClass:
     K = CXCursor_DoStmt;
     break;
   
   case Stmt::ForStmtClass:
     K = CXCursor_ForStmt;
     break;
   
+  case Stmt::ComeFromStmtClass:
+    K = CXCursor_ComeFromStmt;
+    break;
+
   case Stmt::GotoStmtClass:
     K = CXCursor_GotoStmt;
     break;
   
   case Stmt::IndirectGotoStmtClass:
     K = CXCursor_IndirectGotoStmt;
     break;