reimplement codegen for indirect goto with the following advantages:

1. CGF now has fewer bytes of state (one pointer instead of a vector).
2. The generated code is determinstic, instead of getting labels in
   'map order' based on pointer addresses.
3. Clang now emits one 'indirect goto switch' for each function, instead
   of one for each indirect goto.  This fixes an M*N = N^2 IR size issue
   when there are lots of address-taken labels and lots of indirect gotos.
4. This also makes the default cause do something useful, reducing the
   size of the jump table needed (by one).



git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@83952 91177308-0d34-0410-b5e6-96231b3b80d8

3 files changed, 91 insertions, 44 deletions

diff --git a/lib/CodeGen/CGStmt.cpp b/lib/CodeGen/CGStmt.cpp
index 62e465d702..f58b579267 100644
--- a/lib/CodeGen/CGStmt.cpp
+++ b/lib/CodeGen/CGStmt.cpp
@@ -282,6 +282,7 @@ void CodeGenFunction::EmitGotoStmt(const GotoStmt &S) {
   EmitBranchThroughCleanup(getBasicBlockForLabel(S.getLabel()));
 }
 
+
 void CodeGenFunction::EmitIndirectGotoStmt(const IndirectGotoStmt &S) {
   // Emit initial switch which will be patched up later by
   // EmitIndirectSwitches(). We need a default dest, so we use the
@@ -289,11 +290,17 @@ void CodeGenFunction::EmitIndirectGotoStmt(const IndirectGotoStmt &S) {
   llvm::Value *V = Builder.CreatePtrToInt(EmitScalarExpr(S.getTarget()),
                                           llvm::Type::getInt32Ty(VMContext),
                                           "addr");
-  llvm::SwitchInst *I = Builder.CreateSwitch(V, Builder.GetInsertBlock());
-  IndirectSwitches.push_back(I);
-
-  // Clear the insertion point to indicate we are in unreachable code.
-  Builder.ClearInsertionPoint();
+  llvm::BasicBlock *CurBB = Builder.GetInsertBlock();
+  
+
+  // Get the basic block for the indirect goto.
+  llvm::BasicBlock *IndGotoBB = GetIndirectGotoBlock();
+  
+  // The first instruction in the block has to be the PHI for the switch dest,
+  // add an entry for this branch.
+  cast<llvm::PHINode>(IndGotoBB->begin())->addIncoming(V, CurBB);
+  
+  EmitBranch(IndGotoBB);
 }
 
 void CodeGenFunction::EmitIfStmt(const IfStmt &S) {
diff --git a/lib/CodeGen/CodeGenFunction.cpp b/lib/CodeGen/CodeGenFunction.cpp
index 2d4dc455f2..5206f447f8 100644
--- a/lib/CodeGen/CodeGenFunction.cpp
+++ b/lib/CodeGen/CodeGenFunction.cpp
@@ -27,7 +27,8 @@ CodeGenFunction::CodeGenFunction(CodeGenModule &cgm)
   : BlockFunction(cgm, *this, Builder), CGM(cgm),
     Target(CGM.getContext().Target),
     Builder(cgm.getModule().getContext()),
-    DebugInfo(0), SwitchInsn(0), CaseRangeBlock(0), InvokeDest(0),
+    DebugInfo(0), IndirectGotoSwitch(0),
+    SwitchInsn(0), CaseRangeBlock(0), InvokeDest(0),
     CXXThisDecl(0) {
   LLVMIntTy = ConvertType(getContext().IntTy);
   LLVMPointerWidth = Target.getPointerWidth(0);
@@ -111,9 +112,6 @@ void CodeGenFunction::EmitReturnBlock() {
 }
 
 void CodeGenFunction::FinishFunction(SourceLocation EndLoc) {
-  // Finish emission of indirect switches.
-  EmitIndirectSwitches();
-
   assert(BreakContinueStack.empty() &&
          "mismatched push/pop in break/continue stack!");
   assert(BlockScopes.empty() &&
@@ -442,11 +440,6 @@ void CodeGenFunction::ErrorUnsupported(const Stmt *S, const char *Type,
   CGM.ErrorUnsupported(S, Type, OmitOnError);
 }
 
-unsigned CodeGenFunction::GetIDForAddrOfLabel(const LabelStmt *L) {
-  // Use LabelIDs.size() as the new ID if one hasn't been assigned.
-  return LabelIDs.insert(std::make_pair(L, LabelIDs.size()+1)).first->second;
-}
-
 void CodeGenFunction::EmitMemSetToZero(llvm::Value *DestPtr, QualType Ty) {
   const llvm::Type *BP = llvm::Type::getInt8PtrTy(VMContext);
   if (DestPtr->getType() != BP)
@@ -471,33 +464,81 @@ void CodeGenFunction::EmitMemSetToZero(llvm::Value *DestPtr, QualType Ty) {
                                              TypeInfo.second/8));
 }
 
-void CodeGenFunction::EmitIndirectSwitches() {
-  llvm::BasicBlock *Default;
-
-  if (IndirectSwitches.empty())
-    return;
+unsigned CodeGenFunction::GetIDForAddrOfLabel(const LabelStmt *L) {
+  // Use LabelIDs.size()+1 as the new ID if one hasn't been assigned.
+  unsigned &Entry = LabelIDs[L];
+  if (Entry) return Entry;
+  
+  Entry = LabelIDs.size();
+  
+  // If this is the first "address taken" of a label and the indirect goto has
+  // already been seen, add this to it.
+  if (IndirectGotoSwitch) {
+    // If this is the first address-taken label, set it as the default dest.
+    if (Entry == 1)
+      IndirectGotoSwitch->setSuccessor(0, getBasicBlockForLabel(L));
+    else {
+      // Otherwise add it to the switch as a new dest.
+      const llvm::IntegerType *Int32Ty = llvm::Type::getInt32Ty(VMContext);
+      IndirectGotoSwitch->addCase(llvm::ConstantInt::get(Int32Ty, Entry),
+                                  getBasicBlockForLabel(L));
+    }
+  }
+  
+  return Entry;
+}
 
+llvm::BasicBlock *CodeGenFunction::GetIndirectGotoBlock() {
+  // If we already made the switch stmt for indirect goto, return its block.
+  if (IndirectGotoSwitch) return IndirectGotoSwitch->getParent();
+  
+  EmitBlock(createBasicBlock("indirectgoto"));
+  
+  // Create the PHI node that indirect gotos will add entries to.
+  llvm::Value *DestVal =
+    Builder.CreatePHI(llvm::Type::getInt32Ty(VMContext), "indirect.goto.dest");
+  
+  // Create the switch instruction.  For now, set the insert block to this block
+  // which will be fixed as labels are added.
+  IndirectGotoSwitch = Builder.CreateSwitch(DestVal, Builder.GetInsertBlock());
+  
+  // Clear the insertion point to indicate we are in unreachable code.
+  Builder.ClearInsertionPoint();
+  
+  // If we already have labels created, add them.
   if (!LabelIDs.empty()) {
-    Default = getBasicBlockForLabel(LabelIDs.begin()->first);
+    // Invert LabelID's so that the order is determinstic.
+    std::vector<const LabelStmt*> AddrTakenLabelsByID;
+    AddrTakenLabelsByID.resize(LabelIDs.size());
+    
+    for (std::map<const LabelStmt*,unsigned>::iterator 
+         LI = LabelIDs.begin(), LE = LabelIDs.end(); LI != LE; ++LI) {
+      assert(LI->second-1 < AddrTakenLabelsByID.size() &&
+             "Numbering inconsistent");
+      AddrTakenLabelsByID[LI->second-1] = LI->first;
+    }
+    
+    // Set the default entry as the first block.
+    IndirectGotoSwitch->setSuccessor(0,
+                                getBasicBlockForLabel(AddrTakenLabelsByID[0]));
+    
+    const llvm::IntegerType *Int32Ty = llvm::Type::getInt32Ty(VMContext);
+    
+    // FIXME: The iteration order of this is nondeterminstic!
+    for (unsigned i = 1, e = AddrTakenLabelsByID.size(); i != e; ++i)
+      IndirectGotoSwitch->addCase(llvm::ConstantInt::get(Int32Ty, i+1),
+                                 getBasicBlockForLabel(AddrTakenLabelsByID[i]));
   } else {
-    // No possible targets for indirect goto, just emit an infinite
-    // loop.
-    Default = createBasicBlock("indirectgoto.loop", CurFn);
-    llvm::BranchInst::Create(Default, Default);
+    // Otherwise, create a dead block and set it as the default dest.  This will
+    // be removed by the optimizers after the indirect goto is set up.
+    llvm::BasicBlock *Dummy = createBasicBlock("indgoto.dummy");
+    EmitBlock(Dummy);
+    IndirectGotoSwitch->setSuccessor(0, Dummy);
+    Builder.CreateUnreachable();
+    Builder.ClearInsertionPoint();
   }
 
-  for (std::vector<llvm::SwitchInst*>::iterator i = IndirectSwitches.begin(),
-         e = IndirectSwitches.end(); i != e; ++i) {
-    llvm::SwitchInst *I = *i;
-
-    I->setSuccessor(0, Default);
-    for (std::map<const LabelStmt*,unsigned>::iterator LI = LabelIDs.begin(),
-           LE = LabelIDs.end(); LI != LE; ++LI) {
-      I->addCase(llvm::ConstantInt::get(llvm::Type::getInt32Ty(VMContext),
-                                        LI->second),
-                 getBasicBlockForLabel(LI->first));
-    }
-  }
+  return IndirectGotoSwitch->getParent();
 }
 
 llvm::Value *CodeGenFunction::GetVLASize(const VariableArrayType *VAT) {
diff --git a/lib/CodeGen/CodeGenFunction.h b/lib/CodeGen/CodeGenFunction.h
index 42de9fb62e..722d002c19 100644
--- a/lib/CodeGen/CodeGenFunction.h
+++ b/lib/CodeGen/CodeGenFunction.h
@@ -189,10 +189,12 @@ private:
   /// labels inside getIDForAddrOfLabel().
   std::map<const LabelStmt*, unsigned> LabelIDs;
 
-  /// IndirectSwitches - Record the list of switches for indirect
-  /// gotos. Emission of the actual switching code needs to be delayed until all
-  /// AddrLabelExprs have been seen.
-  std::vector<llvm::SwitchInst*> IndirectSwitches;
+  /// IndirectGotoSwitch - The first time an indirect goto is seen we create a
+  /// block with the switch for the indirect gotos.  Every time we see the
+  /// address of a label taken, we add the label to the indirect goto.  Every
+  /// subsequent indirect goto is codegen'd as a jump to the
+  /// IndirectGotoSwitch's basic block.
+  llvm::SwitchInst *IndirectGotoSwitch;
 
   /// LocalDeclMap - This keeps track of the LLVM allocas or globals for local C
   /// decls.
@@ -555,6 +557,7 @@ public:
   static unsigned getAccessedFieldNo(unsigned Idx, const llvm::Constant *Elts);
 
   unsigned GetIDForAddrOfLabel(const LabelStmt *L);
+  llvm::BasicBlock *GetIndirectGotoBlock();
 
   /// EmitMemSetToZero - Generate code to memset a value of the given type to 0.
   void EmitMemSetToZero(llvm::Value *DestPtr, QualType Ty);
@@ -1014,10 +1017,6 @@ public:
                             llvm::BasicBlock *FalseBlock);
 private:
 
-  /// EmitIndirectSwitches - Emit code for all of the switch
-  /// instructions in IndirectSwitches.
-  void EmitIndirectSwitches();
-
   void EmitReturnOfRValue(RValue RV, QualType Ty);
 
   /// ExpandTypeFromArgs - Reconstruct a structure of type \arg Ty