Add the llvm.frameallocate and llvm.recoverframeallocation intrinsics

[rnk]

Summary

These intrinsics allow multiple functions to share a single stack
allocation from one function's call frame. The function with the
allocation may only perform one allocation, and it must be in the entry
block.

Functions accessing the allocation call llvm.recoverframeallocation with
the function whose frame they are accessing and a frame pointer from an
active call frame of that function.

These intrinsics are very difficult to inline correctly, so the
intention is that they be introduced rarely, or at least very late
during EH preparation.

The patch is still a work in progress, but I wanted to send some code
along. It needs more comments, probably some name bikeshedding, and a
change to the inliner.

[andrew.w.kaylor]

The implementation looks OK to me. It also looks like this will meet our needs for outlining functions for exception handling. My comments are pretty much documentation and error handling nits.

docs/LangRef.rst

7238 ↗

(On Diff #16844)

You should say something about how (or at least where) this "fixed offset" is determined.

7246 ↗

(On Diff #16844)

What happens if 'size' is zero?

7263 ↗

(On Diff #16844)

The phrase "the stack memory allocation" is a bit ambiguous. You only mean for it to refer to the part of stack memory allocated by this intrinsic, right? So if the function contains other allocas is addition to this intrinsic the descendant functions can't access that alloca (without rolling it into this frame allocation), yes?

7267 ↗

(On Diff #16844)

Can the call be anywhere in the entry block? Can there be allocas before or after this call?

7271 ↗

(On Diff #16844)

I think it would be helpful to describe the exception handling case here as an example of why this is useful. With everything kept abstract like this it is hard to understand why anyone would want to do this.

lib/CodeGen/MachineFunction.cpp

594 ↗

(On Diff #16844)

Will this round zero up to a non-zero value? If not, then the call to setFrameAddressIsTaken may be incorrect. Also, it seems like a good idea to verify here that FrameAllocationSize is zero before it is set by this function.

lib/IR/Verifier.cpp

2584 ↗

(On Diff #16844)

Is there a reasonable way to verify that fp is at least a pointer? Looking at your test case made me think that at the very least null should be flagged as an error, and it seems like any constant is likely to be an error.

test/Verifier/frameallocate.ll

5 ↗

(On Diff #16844)

Checking for expected behavior if llvm.frameallocate is called with a zero argument would be nice. You should also have a test for a non-constant argument.

33 ↗

(On Diff #16844)

The second argument here looks like an error also.

[rnk]

Thanks! I'll upload the doc tweaks and DCE.

docs/LangRef.rst

7238 ↗

(On Diff #16844)

Sure.

7246 ↗

(On Diff #16844)

Same thing as with normal allocas, which is apparently: Allocating zero bytes is legal, but the result is undefined.

7263 ↗

(On Diff #16844)

Yeah, I should probably say "one stack memory allocation".

7267 ↗

(On Diff #16844)

Anywhere. The same is true for normal allocas. Hypothetically you could call another function that recovers the allocation prior to making the allocation, but that seems like obvious UB not worth mentioning.

7271 ↗

(On Diff #16844)

I think that should probably go in the ExceptionHandling document, not LangRef. I suppose I can write something up.

lib/CodeGen/MachineFunction.cpp

594 ↗

(On Diff #16844)

I don't think it will round zero up.

Actually, FrameAllocationSize is dead, I just forgot to delete it...

lib/IR/Verifier.cpp

2584 ↗

(On Diff #16844)

This should already be handled automatically in VerifyIntrinsicType based on the types in Intrinsics.td.

test/Verifier/frameallocate.ll

5 ↗

(On Diff #16844)

Sure, non-constant test makes sense. I'm not particularly interested in the zero size case, as long as making it UB is OK.

33 ↗

(On Diff #16844)

Passing null here is just UB at runtime, not a verifier error. This code might never be executed, but it should assemble.

[rnk]

• Tweak docs and delete dead code.

[echristo]

Few comments, plus some bits inline:

a) Would be nice if the verifier would look and see if the function passed to recover frame allocation actually has a frame allocation intrinisic listed. Otherwise you'll get segfault/assert during assembly time.

b) The documentation appears a bit misleading, what seems to be happening in the code is that you're recording where you put a particular allocation which is different than allocating at a specific fixed address. The allocations are getting merged.

c) some reason to have the symbol in the same function rather than a load of a symbol off to the side? e.g.
.data
.Lallocation_foo
.long -144

Otherwise it seems to be a reasonable way to pass back and forth some specific data for outlining etc via symbol values.

-eric

docs/LangRef.rst

7301 ↗

(On Diff #17088)

This doesn't appear to be true? The allocas seem to be merged and after alignment.

include/llvm/CodeGen/ISDOpcodes.h

75 ↗

(On Diff #17088)

Needs docs.

include/llvm/Target/Target.td

868 ↗

(On Diff #17088)

Might want to comment why both of these are true.

include/llvm/Target/TargetOpcodes.h

121 ↗

(On Diff #17088)

Comments.

lib/CodeGen/MachineFunction.cpp

591 ↗

(On Diff #17088)

If this is for a specific use you probably want to reference the intrinsic more directly in the name. Right now CreateFrameAllocation(size) sounds like something I'd call in general :)

lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp

5582 ↗

(On Diff #17088)

Elaborate?

5605 ↗

(On Diff #17088)

Unused.

5606 ↗

(On Diff #17088)

Unused.

test/CodeGen/X86/frameallocate.ll

25 ↗

(On Diff #17088)

How about a couple tests that have both allocations and/or alignment requirements?

[rnk]

• comments

docs/LangRef.rst

7301 ↗

(On Diff #17088)

This is how I would *like* it to work. It isn't implemented. I'll weaken this to say it *may* be allocated prior to realignment.

include/llvm/CodeGen/ISDOpcodes.h

75 ↗

(On Diff #17088)

done

include/llvm/Target/Target.td

868 ↗

(On Diff #17088)

done

lib/CodeGen/MachineFunction.cpp

591 ↗

(On Diff #17088)

It is named directly after the intrinsic, llvm.frameallocate. Can you propose a more specific name?

lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp

5582 ↗

(On Diff #17088)

Every SSA value live across mutliple BBs has an associated virtual register except for static allocas. The address of a static alloca is essentially always rematerialized at the point of use by doing arithmetic on the stack pointer. The same could be done for the result of llvm.frameallocate in many cases. As it is, the code will be less optimal than it could be, but that seems OK.

5605 ↗

(On Diff #17088)

done

test/CodeGen/X86/frameallocate.ll

25 ↗

(On Diff #17088)

I could do that, but it wouldn't work since it's not implemented. :)

[sanjoy]

How is this expected to interact with nounwind? Specifically, can a nounwind eventually invoke recoverframeallocation?

[silvas]

Sorry I'm totally clueless, but can you explain the motivation for this? Perhaps there has been an llvmdev RFC for this feature yet? (I don't see anything in my email, but with the mailing lists lately I'm not sure if I trust my inbox).

In the past there have been communication failures without a formal RFC/design discussion on llvmdev to make sure everybody is on the same page (e.g. r209007, although admittedly that was a much more intrusive change than this one), so you probably want to shoot a message there to give everyone a chance to take a look at the design.

[rnk]

In D6493#103064, @sanjoy wrote:

How is this expected to interact with nounwind? Specifically, can a nounwind eventually invoke recoverframeallocation?

Yes, all you need is a frame pointer. In the CodeGen/X86/frameallocate.ll test, you can see how this is done with llvm.frameaddress and without throwing any exceptions.

In D6493#103101, @silvas wrote:

Sorry I'm totally clueless, but can you explain the motivation for this? Perhaps there has been an llvmdev RFC for this feature yet? (I don't see anything in my email, but with the mailing lists lately I'm not sure if I trust my inbox).

The idea came up in the SEH RFC thread here:
http://lists.cs.uiuc.edu/pipermail/llvmdev/2014-November/078771.html
I called it llvm.eh.set_capture_block / llvm.eh.get_capture_block at the time, but it generalizes into basically "allocate something relative to the FP" and "recover that allocation from this specific FP".

The motivation is that various handlers such as cleanups in MSVC C++ and SEH have to be separate functions, and they need to be able to access some local variables in the parent function frame via the frame pointer. Various schemes have been proposed, but so far frameallocate is the least intrusive on the rest of LLVM.

In the past there have been communication failures without a formal RFC/design discussion on llvmdev to make sure everybody is on the same page (e.g. r209007, although admittedly that was a much more intrusive change than this one), so you probably want to shoot a message there to give everyone a chance to take a look at the design.

I need to recap the original SEH RFC thread, but the design is all out there already.

[rnk]

Does anyone have any high-level feedback on this idea? I think the code is in reasonable shape, and it would be good to get this in and iterate.

llvm/trunk/docs/LangRef.rst

 cannot be identified. The value returned by this intrinsic is likely to
 be incorrect or 0 for arguments other than zero, so it should only be
 used for debugging purposes.
 
 Note that calling this intrinsic does not prevent function inlining or
 other aggressive transformations, so the value returned may not be that
 of the obvious source-language caller.
 
+'``llvm.frameallocate``' and '``llvm.recoverframeallocation``' Intrinsics
+^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
+
+Syntax:
+"""""""
+
+::
+
+      declare i8* @llvm.frameallocate(i32 %size)
+      declare i8* @llvm.recoverframeallocation(i8* %func, i8* %fp)
+
+Overview:
+"""""""""
+
+The '``llvm.frameallocate``' intrinsic allocates stack memory at some fixed
+offset from the frame pointer, and the '``llvm.recoverframeallocation``'
+intrinsic applies that offset to a live frame pointer to recover the address of
+the allocation. The offset is computed during frame layout of the caller of
+``llvm.frameallocate``.
+
+Arguments:
+""""""""""
+
+The ``size`` argument to '``llvm.frameallocate``' must be a constant integer
+indicating the amount of stack memory to allocate. As with allocas, allocating
+zero bytes is legal, but the result is undefined.
+
+The ``func`` argument to '``llvm.recoverframeallocation``' must be a constant
+bitcasted pointer to a function defined in the current module. The code
+generator cannot determine the frame allocation offset of functions defined in
+other modules.
+
+The ``fp`` argument to '``llvm.recoverframeallocation``' must be a frame
+pointer of a call frame that is currently live. The return value of
+'``llvm.frameaddress``' is one way to produce such a value, but most platforms
+also expose the frame pointer through stack unwinding mechanisms.
+
+Semantics:
+""""""""""
+
+These intrinsics allow a group of functions to access one stack memory
+allocation in an ancestor stack frame. The memory returned from
+'``llvm.frameallocate``' may be allocated prior to stack realignment, so the
+memory is only aligned to the ABI-required stack alignment.  Each function may
+only call '``llvm.frameallocate``' one or zero times from the function entry
+block.  The frame allocation intrinsic inhibits inlining, as any frame
+allocations in the inlined function frame are likely to be at a different
+offset from the one used by '``llvm.recoverframeallocation``' called with the
+uninlined function.
+
 .. _int_read_register:
 .. _int_write_register:
 
 '``llvm.read_register``' and '``llvm.write_register``' Intrinsics
 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
 
 Syntax:
 """""""

llvm/trunk/include/llvm/CodeGen/AsmPrinter.h

public:
   /// This method emits the header for the current function.
   void EmitFunctionHeader();
 
   /// This method emits the body and trailer for a function.
   void EmitFunctionBody();
 
   void emitCFIInstruction(const MachineInstr &MI);
 
+  void emitFrameAlloc(const MachineInstr &MI);
+
   enum CFIMoveType { CFI_M_None, CFI_M_EH, CFI_M_Debug };
   CFIMoveType needsCFIMoves();
 
   bool needsSEHMoves();
 
   /// Print to the current output stream assembly representations of the
   /// constants in the constant pool MCP. This is used to print out constants
   /// which have been "spilled to memory" by the code generator.

llvm/trunk/include/llvm/CodeGen/ISDOpcodes.h

enum NodeType {
 
     /// FRAMEADDR, RETURNADDR - These nodes represent llvm.frameaddress and
     /// llvm.returnaddress on the DAG.  These nodes take one operand, the index
     /// of the frame or return address to return.  An index of zero corresponds
     /// to the current function's frame or return address, an index of one to
     /// the parent's frame or return address, and so on.
     FRAMEADDR, RETURNADDR,
 
+    /// RECOVER_FRAME_ALLOC - Represents the llvm.recoverframeallocation
+    /// intrinsic. Materializes the offset from the frame pointer of another
+    /// function to the result of llvm.frameallocate.
+    RECOVER_FRAME_ALLOC,
+
     /// READ_REGISTER, WRITE_REGISTER - This node represents llvm.register on
     /// the DAG, which implements the named register global variables extension.
     READ_REGISTER,
     WRITE_REGISTER,
 
     /// FRAME_TO_ARGS_OFFSET - This node represents offset from frame pointer to
     /// first (possible) on-stack argument. This is needed for correct stack
     /// adjustment during unwind.

llvm/trunk/include/llvm/CodeGen/MachineFrameInfo.h

public:
   ///
   int CreateFixedObject(uint64_t Size, int64_t SPOffset, bool Immutable,
                         bool isAliased = false);
 
   /// CreateFixedSpillStackObject - Create a spill slot at a fixed location
   /// on the stack.  Returns an index with a negative value.
   int CreateFixedSpillStackObject(uint64_t Size, int64_t SPOffset);
 
+  /// Allocates memory at a fixed, target-specific offset from the frame
+  /// pointer. Marks the function as having its frame address taken.
+  int CreateFrameAllocation(uint64_t Size);
+
   /// isFixedObjectIndex - Returns true if the specified index corresponds to a
   /// fixed stack object.
   bool isFixedObjectIndex(int ObjectIdx) const {
     return ObjectIdx < 0 && (ObjectIdx >= -(int)NumFixedObjects);
   }
 
   /// isAliasedObjectIndex - Returns true if the specified index corresponds
   /// to an object that might be pointed to by an LLVM IR value.

llvm/trunk/include/llvm/IR/Intrinsics.td

 def int_gcwrite : Intrinsic<[],
                             [llvm_ptr_ty, llvm_ptr_ty, llvm_ptrptr_ty],
                             [IntrReadWriteArgMem, NoCapture<1>, NoCapture<2>]>;
 
 //===--------------------- Code Generator Intrinsics ----------------------===//
 //
 def int_returnaddress : Intrinsic<[llvm_ptr_ty], [llvm_i32_ty], [IntrNoMem]>;
 def int_frameaddress  : Intrinsic<[llvm_ptr_ty], [llvm_i32_ty], [IntrNoMem]>;
+def int_frameallocate : Intrinsic<[llvm_ptr_ty], [llvm_i32_ty]>;
+def int_recoverframeallocation : Intrinsic<[llvm_ptr_ty],
+                                             [llvm_ptr_ty, llvm_ptr_ty],
+                                             [IntrNoMem]>;
 def int_read_register  : Intrinsic<[llvm_anyint_ty], [llvm_metadata_ty],
                                    [IntrNoMem], "llvm.read_register">;
 def int_write_register : Intrinsic<[], [llvm_metadata_ty, llvm_anyint_ty],
                                    [], "llvm.write_register">;
 
 // Note: we treat stacksave/stackrestore as writemem because we don't otherwise
 // model their dependencies on allocas.
 def int_stacksave     : Intrinsic<[llvm_ptr_ty]>,

llvm/trunk/include/llvm/MC/MCContext.h

public:
     /// reference and return it.
     ///
     /// @param Name - The symbol name, which must be unique across all symbols.
     MCSymbol *GetOrCreateSymbol(StringRef Name);
     MCSymbol *GetOrCreateSymbol(const Twine &Name);
 
     MCSymbol *getOrCreateSectionSymbol(const MCSectionELF &Section);
 
+    MCSymbol *getOrCreateFrameAllocSymbol(StringRef FuncName);
+
     /// LookupSymbol - Get the symbol for \p Name, or null.
     MCSymbol *LookupSymbol(StringRef Name) const;
     MCSymbol *LookupSymbol(const Twine &Name) const;
 
     /// getSymbols - Get a reference for the symbol table for clients that
     /// want to, for example, iterate over all symbols. 'const' because we
     /// still want any modifications to the table itself to use the MCContext
     /// APIs.

llvm/trunk/include/llvm/Target/Target.td

 def LOAD_STACK_GUARD : Instruction {
   let OutOperandList = (outs ptr_rc:$dst);
   let InOperandList = (ins);
   let mayLoad = 1;
   bit isReMaterializable = 1;
   let hasSideEffects = 0;
   bit isPseudo = 1;
 }
+def FRAME_ALLOC : Instruction {
+  // This instruction is really just a label. It has to be part of the chain so
+  // that it doesn't get dropped from the DAG, but it produces nothing and has
+  // no side effects.
+  let OutOperandList = (outs);
+  let InOperandList = (ins ptr_rc:$symbol, i32imm:$id);
+  let hasSideEffects = 0;
+  let hasCtrlDep = 1;
+}
 }
 
 //===----------------------------------------------------------------------===//
 // AsmParser - This class can be implemented by targets that wish to implement
 // .s file parsing.
 //
 // Subtargets can have multiple different assembly parsers (e.g. AT&T vs Intel
 // syntax on X86 for example).

llvm/trunk/include/llvm/Target/TargetFrameLowering.h

public:
   /// Adjust the prologue to have the function use segmented stacks. This works
   /// by adding a check even before the "normal" function prologue.
   virtual void adjustForSegmentedStacks(MachineFunction &MF) const { }
 
   /// Adjust the prologue to add Erlang Run-Time System (ERTS) specific code in
   /// the assembly prologue to explicitly handle the stack.
   virtual void adjustForHiPEPrologue(MachineFunction &MF) const { }
 
+  /// Adjust the prologue to add an allocation at a fixed offset from the frame
+  /// pointer.
+  virtual void adjustForFrameAllocatePrologue(MachineFunction &MF) const { }
+
   /// spillCalleeSavedRegisters - Issues instruction(s) to spill all callee
   /// saved registers and returns true if it isn't possible / profitable to do
   /// so by issuing a series of store instructions via
   /// storeRegToStackSlot(). Returns false otherwise.
   virtual bool spillCalleeSavedRegisters(MachineBasicBlock &MBB,
                                          MachineBasicBlock::iterator MI,
                                         const std::vector<CalleeSavedInfo> &CSI,
                                          const TargetRegisterInfo *TRI) const {

llvm/trunk/include/llvm/Target/TargetOpcodes.h

enum {
   /// stack should override TargetLowering::emitLoadStackGuardNode and
   /// additionally expand this pseudo after register allocation.
   LOAD_STACK_GUARD = 19,
 
   /// Call instruction with associated vm state for deoptimization and list
   /// of live pointers for relocation by the garbage collector.  It is
   /// intended to support garbage collection with fully precise relocating
   /// collectors and deoptimizations in either the callee or caller.
-  STATEPOINT = 20
+  STATEPOINT = 20,
+
+  /// Instruction that records the offset of a function's frame allocation in a
+  /// label. Created by the llvm.frameallocate intrinsic. It has two arguments:
+  /// the symbol for the label and the frame index of the stack allocation.
+  FRAME_ALLOC = 21,
 };
 } // end namespace TargetOpcode
 } // end namespace llvm
 
 #endif

llvm/trunk/lib/CodeGen/AsmPrinter/AsmPrinter.cpp

void AsmPrinter::emitCFIInstruction(const MachineInstr &MI) {
 
   const MachineModuleInfo &MMI = MF->getMMI();
   const std::vector<MCCFIInstruction> &Instrs = MMI.getFrameInstructions();
   unsigned CFIIndex = MI.getOperand(0).getCFIIndex();
   const MCCFIInstruction &CFI = Instrs[CFIIndex];
   emitCFIInstruction(CFI);
 }
 
+void AsmPrinter::emitFrameAlloc(const MachineInstr &MI) {
+  // The operands are the MCSymbol and the frame offset of the allocation.
+  MCSymbol *FrameAllocSym = MI.getOperand(0).getMCSymbol();
+  int FrameOffset = MI.getOperand(1).getImm();
+
+  // Emit a symbol assignment.
+  OutStreamer.EmitAssignment(FrameAllocSym,
+                             MCConstantExpr::Create(FrameOffset, OutContext));
+}
+
 /// EmitFunctionBody - This method emits the body and trailer for a
 /// function.
 void AsmPrinter::EmitFunctionBody() {
   // Emit target-specific gunk before the function body.
   EmitFunctionBodyStart();
 
   bool ShouldPrintDebugScopes = MMI->hasDebugInfo();
 
for (auto &MI : MBB) {
       if (isVerbose())
         emitComments(MI, OutStreamer.GetCommentOS());
 
       switch (MI.getOpcode()) {
       case TargetOpcode::CFI_INSTRUCTION:
         emitCFIInstruction(MI);
         break;
 
+      case TargetOpcode::FRAME_ALLOC:
+        emitFrameAlloc(MI);
+        break;
+
       case TargetOpcode::EH_LABEL:
       case TargetOpcode::GC_LABEL:
         OutStreamer.EmitLabel(MI.getOperand(0).getMCSymbol());
         break;
       case TargetOpcode::INLINEASM:
         EmitInlineAsm(&MI);
         break;
       case TargetOpcode::DBG_VALUE:

llvm/trunk/lib/CodeGen/DeadMachineInstructionElim.cpp

 
 bool DeadMachineInstructionElim::isDead(const MachineInstr *MI) const {
   // Technically speaking inline asm without side effects and no defs can still
   // be deleted. But there is so much bad inline asm code out there, we should
   // let them be.
   if (MI->isInlineAsm())
     return false;
 
+  // Don't delete frame allocation labels.
+  if (MI->getOpcode() == TargetOpcode::FRAME_ALLOC)
+    return false;
+
   // Don't delete instructions with side effects.
   bool SawStore = false;
   if (!MI->isSafeToMove(TII, nullptr, SawStore) && !MI->isPHI())
     return false;
 
   // Examine each operand.
   for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
     const MachineOperand &MO = MI->getOperand(i);

llvm/trunk/lib/CodeGen/MachineFunction.cpp

int MachineFrameInfo::CreateFixedSpillStackObject(uint64_t Size,
   Objects.insert(Objects.begin(), StackObject(Size, Align, SPOffset,
                                               /*Immutable*/ true,
                                               /*isSS*/ true,
                                               /*Alloca*/ nullptr,
                                               /*isAliased*/ false));
   return -++NumFixedObjects;
 }
 
+int MachineFrameInfo::CreateFrameAllocation(uint64_t Size) {
+  // Force the use of a frame pointer. The intention is that this intrinsic be
+  // used in conjunction with unwind mechanisms that leak the frame pointer.
+  setFrameAddressIsTaken(true);
+  Size = RoundUpToAlignment(Size, StackAlignment);
+  return CreateStackObject(Size, StackAlignment, false);
+}
+
 BitVector
 MachineFrameInfo::getPristineRegs(const MachineBasicBlock *MBB) const {
   assert(MBB && "MBB must be valid");
   const MachineFunction *MF = MBB->getParent();
   assert(MF && "MBB must be part of a MachineFunction");
   const TargetMachine &TM = MF->getTarget();
   const TargetRegisterInfo *TRI = TM.getSubtargetImpl()->getRegisterInfo();
   BitVector BV(TRI->getNumRegs());

llvm/trunk/lib/CodeGen/PrologEpilogInserter.cpp

for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
           TFI->getFrameIndexReferenceFromSP(Fn, MI->getOperand(i).getIndex(),
                                             Reg);
 
         Offset.setImm(Offset.getImm() + refOffset);
         MI->getOperand(i).ChangeToRegister(Reg, false /*isDef*/);
         continue;
       }
 
+      // Frame allocations are target independent. Simply swap the index with
+      // the offset.
+      if (MI->getOpcode() == TargetOpcode::FRAME_ALLOC) {
+        assert(TFI->hasFP(Fn) && "frame alloc requires FP");
+        MachineOperand &FI = MI->getOperand(i);
+        unsigned Reg;
+        int FrameOffset = TFI->getFrameIndexReference(Fn, FI.getIndex(), Reg);
+        FI.ChangeToImmediate(FrameOffset);
+        continue;
+      }
+
       // Some instructions (e.g. inline asm instructions) can have
       // multiple frame indices and/or cause eliminateFrameIndex
       // to insert more than one instruction. We need the register
       // scavenger to go through all of these instructions so that
       // it can update its register information. We keep the
       // iterator at the point before insertion so that we can
       // revisit them in full.
       bool AtBeginning = (I == BB->begin());

llvm/trunk/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp

 #include "llvm/IR/GlobalVariable.h"
 #include "llvm/IR/InlineAsm.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/IntrinsicInst.h"
 #include "llvm/IR/Intrinsics.h"
 #include "llvm/IR/LLVMContext.h"
 #include "llvm/IR/Module.h"
 #include "llvm/IR/Statepoint.h"
+#include "llvm/MC/MCSymbol.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/ErrorHandling.h"
 #include "llvm/Support/MathExtras.h"
 #include "llvm/Support/raw_ostream.h"
 #include "llvm/Target/TargetFrameLowering.h"
 #include "llvm/Target/TargetInstrInfo.h"
 #include "llvm/Target/TargetIntrinsicInfo.h"
case Intrinsic::experimental_gc_result_ptr: {
     return nullptr;
   }
   case Intrinsic::experimental_gc_relocate: {
     visitGCRelocate(I);
     return nullptr;
   }
   case Intrinsic::instrprof_increment:
     llvm_unreachable("instrprof failed to lower an increment");
+
+  case Intrinsic::frameallocate: {
+    MachineFunction &MF = DAG.getMachineFunction();
+    const TargetInstrInfo *TII = DAG.getSubtarget().getInstrInfo();
+
+    // Do the allocation and map it as a normal value.
+    // FIXME: Maybe we should add this to the alloca map so that we don't have
+    // to register allocate it?
+    uint64_t Size = cast<ConstantInt>(I.getArgOperand(0))->getZExtValue();
+    int Alloc = MF.getFrameInfo()->CreateFrameAllocation(Size);
+    MVT PtrVT = TLI.getPointerTy(0);
+    SDValue FIVal = DAG.getFrameIndex(Alloc, PtrVT);
+    setValue(&I, FIVal);
+
+    // Directly emit a FRAME_ALLOC machine instr. Label assignment emission is
+    // the same on all targets.
+    MCSymbol *FrameAllocSym =
+        MF.getMMI().getContext().getOrCreateFrameAllocSymbol(MF.getName());
+    BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, dl,
+            TII->get(TargetOpcode::FRAME_ALLOC))
+        .addSym(FrameAllocSym)
+        .addFrameIndex(Alloc);
+
+    return nullptr;
+  }
+
+  case Intrinsic::recoverframeallocation: {
+    // i8* @llvm.recoverframeallocation(i8* %fn, i8* %fp)
+    MachineFunction &MF = DAG.getMachineFunction();
+    MVT PtrVT = TLI.getPointerTy(0);
+
+    // Get the symbol that defines the frame offset.
+    Function *Fn = cast<Function>(I.getArgOperand(0)->stripPointerCasts());
+    MCSymbol *FrameAllocSym =
+        MF.getMMI().getContext().getOrCreateFrameAllocSymbol(Fn->getName());
+
+    // Create a TargetExternalSymbol for the label to avoid any target lowering
+    // that would make this PC relative.
+    StringRef Name = FrameAllocSym->getName();
+    assert(Name.size() == strlen(Name.data()) && "not null terminated");
+    SDValue OffsetSym = DAG.getTargetExternalSymbol(Name.data(), PtrVT);
+    SDValue OffsetVal =
+        DAG.getNode(ISD::RECOVER_FRAME_ALLOC, sdl, PtrVT, OffsetSym);
+
+    // Add the offset to the FP.
+    Value *FP = I.getArgOperand(1);
+    SDValue FPVal = getValue(FP);
+    SDValue Add = DAG.getNode(ISD::ADD, sdl, PtrVT, FPVal, OffsetVal);
+    setValue(&I, Add);
+
+    return nullptr;
+  }
   }
 }
 
 std::pair<SDValue, SDValue>
 SelectionDAGBuilder::lowerInvokable(TargetLowering::CallLoweringInfo &CLI,
                                     MachineBasicBlock *LandingPad) {
   MachineModuleInfo &MMI = DAG.getMachineFunction().getMMI();
   MCSymbol *BeginLabel = nullptr;

llvm/trunk/lib/IR/Verifier.cpp

class Verifier : public InstVisitor<Verifier>, VerifierSupport {
   /// \brief Keep track of the metadata nodes that have been checked already.
   SmallPtrSet<Metadata *, 32> MDNodes;
 
   /// \brief The personality function referenced by the LandingPadInsts.
   /// All LandingPadInsts within the same function must use the same
   /// personality function.
   const Value *PersonalityFn;
 
+  /// \brief Whether we've seen a call to @llvm.frameallocate in this function
+  /// already.
+  bool SawFrameAllocate;
+
 public:
   explicit Verifier(raw_ostream &OS = dbgs())
-      : VerifierSupport(OS), Context(nullptr), PersonalityFn(nullptr) {}
+      : VerifierSupport(OS), Context(nullptr), PersonalityFn(nullptr),
+        SawFrameAllocate(false) {}
 
   bool verify(const Function &F) {
     M = F.getParent();
     Context = &M->getContext();
 
     // First ensure the function is well-enough formed to compute dominance
     // information.
     if (F.empty()) {
bool verify(const Function &F) {
     // FIXME: It's really gross that we have to cast away constness here.
     DT.recalculate(const_cast<Function &>(F));
 
     Broken = false;
     // FIXME: We strip const here because the inst visitor strips const.
     visit(const_cast<Function &>(F));
     InstsInThisBlock.clear();
     PersonalityFn = nullptr;
+    SawFrameAllocate = false;
 
     return !Broken;
   }
 
   bool verify(const Module &M) {
     this->M = &M;
     Context = &M.getContext();
     Broken = false;
case Intrinsic::invariant_start:
     Assert1(isa<ConstantInt>(CI.getArgOperand(0)),
             "size argument of memory use markers must be a constant integer",
             &CI);
     break;
   case Intrinsic::invariant_end:
     Assert1(isa<ConstantInt>(CI.getArgOperand(1)),
             "llvm.invariant.end parameter #2 must be a constant integer", &CI);
     break;
- 
+  case Intrinsic::frameallocate: {
+    BasicBlock *BB = CI.getParent();
+    Assert1(BB == &BB->getParent()->front(),
+            "llvm.frameallocate used outside of entry block", &CI);
+    Assert1(!SawFrameAllocate,
+            "multiple calls to llvm.frameallocate in one function", &CI);
+    SawFrameAllocate = true;
+    Assert1(isa<ConstantInt>(CI.getArgOperand(0)),
+            "llvm.frameallocate argument must be constant integer size", &CI);
+    break;
+  }
+  case Intrinsic::recoverframeallocation: {
+    Value *FnArg = CI.getArgOperand(0)->stripPointerCasts();
+    Function *Fn = dyn_cast<Function>(FnArg);
+    Assert1(Fn && !Fn->isDeclaration(), "llvm.recoverframeallocation first "
+            "argument must be function defined in this module", &CI);
+    break;
+  }
+
   case Intrinsic::experimental_gc_statepoint: {
     Assert1(!CI.doesNotAccessMemory() &&
             !CI.onlyReadsMemory(),
             "gc.statepoint must read and write memory to preserve "
             "reordering restrictions required by safepoint semantics", &CI);
     Assert1(!CI.isInlineAsm(),
             "gc.statepoint support for inline assembly unimplemented", &CI);
     

llvm/trunk/lib/MC/MCContext.cpp

MCSymbol *MCContext::getOrCreateSectionSymbol(const MCSectionELF &Section) {
   Sym = new (*this) MCSymbol(NameIter->getKey(), /*isTemporary*/ false);
 
   if (!OldSym)
     OldSym = Sym;
 
   return Sym;
 }
 
+MCSymbol *MCContext::getOrCreateFrameAllocSymbol(StringRef FuncName) {
+  return GetOrCreateSymbol(Twine(MAI->getPrivateGlobalPrefix()) +
+                           "frameallocation_" + FuncName);
+}
+
 MCSymbol *MCContext::CreateSymbol(StringRef Name) {
   // Determine whether this is an assembler temporary or normal label, if used.
   bool isTemporary = false;
   if (AllowTemporaryLabels)
     isTemporary = Name.startswith(MAI->getPrivateGlobalPrefix());
 
   auto NameEntry = UsedNames.insert(std::make_pair(Name, true));
   if (!NameEntry.second) {

llvm/trunk/lib/Target/X86/X86InstrCompiler.td

def : Pat<(store (i64 (X86Wrapper tglobaladdr:$src)), addr:$dst),
           Requires<[NearData, IsStatic]>;
 def : Pat<(store (i64 (X86Wrapper texternalsym:$src)), addr:$dst),
           (MOV64mi32 addr:$dst, texternalsym:$src)>,
           Requires<[NearData, IsStatic]>;
 def : Pat<(store (i64 (X86Wrapper tblockaddress:$src)), addr:$dst),
           (MOV64mi32 addr:$dst, tblockaddress:$src)>,
           Requires<[NearData, IsStatic]>;
 
+def : Pat<(i32 (X86RecoverFrameAlloc texternalsym:$dst)), (MOV32ri texternalsym:$dst)>;
+def : Pat<(i64 (X86RecoverFrameAlloc texternalsym:$dst)), (MOV64ri texternalsym:$dst)>;
+
 // Calls
 
 // tls has some funny stuff here...
 // This corresponds to movabs $foo@tpoff, %rax
 def : Pat<(i64 (X86Wrapper tglobaltlsaddr :$dst)),
           (MOV64ri32 tglobaltlsaddr :$dst)>;
 // This corresponds to add $foo@tpoff, %rax
 def : Pat<(add GR64:$src1, (X86Wrapper tglobaltlsaddr :$dst)),

llvm/trunk/lib/Target/X86/X86InstrInfo.td

 def X86rdtscp  : SDNode<"X86ISD::RDTSCP_DAG", SDTX86Void,
                         [SDNPHasChain, SDNPOutGlue, SDNPSideEffect]>;
 def X86rdpmc   : SDNode<"X86ISD::RDPMC_DAG", SDTX86Void,
                         [SDNPHasChain, SDNPOutGlue, SDNPSideEffect]>;
 
 def X86Wrapper    : SDNode<"X86ISD::Wrapper",     SDTX86Wrapper>;
 def X86WrapperRIP : SDNode<"X86ISD::WrapperRIP",  SDTX86Wrapper>;
 
+def X86RecoverFrameAlloc : SDNode<"ISD::RECOVER_FRAME_ALLOC",
+                                  SDTypeProfile<1, 1, [SDTCisSameAs<0, 1>,
+                                                       SDTCisInt<1>]>>;
+
 def X86tlsaddr : SDNode<"X86ISD::TLSADDR", SDT_X86TLSADDR,
                         [SDNPHasChain, SDNPOptInGlue, SDNPOutGlue]>;
 
 def X86tlsbaseaddr : SDNode<"X86ISD::TLSBASEADDR", SDT_X86TLSBASEADDR,
                         [SDNPHasChain, SDNPOptInGlue, SDNPOutGlue]>;
 
 def X86ehret : SDNode<"X86ISD::EH_RETURN", SDT_X86EHRET,
                         [SDNPHasChain]>;

llvm/trunk/test/CodeGen/X86/frameallocate.ll

+; RUN: llc -mtriple=x86_64-windows-msvc < %s | FileCheck %s
+
+declare i8* @llvm.frameallocate(i32)
+declare i8* @llvm.frameaddress(i32)
+declare i8* @llvm.recoverframeallocation(i8*, i8*)
+declare i32 @printf(i8*, ...)
+
+@str = internal constant [10 x i8] c"asdf: %d\0A\00"
+
+define void @print_framealloc_from_fp(i8* %fp) {
+  %alloc = call i8* @llvm.recoverframeallocation(i8* bitcast (void(i32*, i32*)* @alloc_func to i8*), i8* %fp)
+  %alloc_i32 = bitcast i8* %alloc to i32*
+  %r = load i32* %alloc_i32
+  call i32 (i8*, ...)* @printf(i8* getelementptr ([10 x i8]* @str, i32 0, i32 0), i32 %r)
+  ret void
+}
+
+; CHECK-LABEL: print_framealloc_from_fp:
+; CHECK: movabsq $.Lframeallocation_alloc_func, %[[offs:[a-z]+]]
+; CHECK: movl (%rcx,%[[offs]]), %edx
+; CHECK: leaq {{.*}}(%rip), %rcx
+; CHECK: callq printf
+; CHECK: retq
+
+define void @alloc_func(i32* %s, i32* %d) {
+  %alloc = call i8* @llvm.frameallocate(i32 16)
+  %alloc_i32 = bitcast i8* %alloc to i32*
+  store i32 42, i32* %alloc_i32
+  %fp = call i8* @llvm.frameaddress(i32 0)
+  call void @print_framealloc_from_fp(i8* %fp)
+  ret void
+}
+
+; CHECK-LABEL: alloc_func:
+; CHECK: .Lframeallocation_alloc_func = -[[offs:[0-9]+]]
+; CHECK: movl $42, -[[offs]](%rbp)
+; CHECK: movq %rbp, %rcx
+; CHECK: callq print_framealloc_from_fp
+; CHECK: retq

llvm/trunk/test/Verifier/frameallocate.ll

+; RUN: not llvm-as %s -o /dev/null 2>&1 | FileCheck %s
+
+declare i8* @llvm.frameallocate(i32)
+declare i8* @llvm.recoverframeallocation(i8*, i8*)
+
+define internal void @f() {
+  call i8* @llvm.frameallocate(i32 4)
+  call i8* @llvm.frameallocate(i32 4)
+  ret void
+}
+; CHECK: multiple calls to llvm.frameallocate in one function
+
+define internal void @f_a(i32 %n) {
+  call i8* @llvm.frameallocate(i32 %n)
+  ret void
+}
+; CHECK: llvm.frameallocate argument must be constant integer size
+
+define internal void @g() {
+entry:
+  br label %not_entry
+not_entry:
+  call i8* @llvm.frameallocate(i32 4)
+  ret void
+}
+; CHECK: llvm.frameallocate used outside of entry block
+
+define internal void @h() {
+  call i8* @llvm.recoverframeallocation(i8* null, i8* null)
+  ret void
+}
+; CHECK: llvm.recoverframeallocation first argument must be function defined in this module
+
+@global = constant i8 0
+
+declare void @declaration()
+
+define internal void @i() {
+  call i8* @llvm.recoverframeallocation(i8* @global, i8* null)
+  ret void
+}
+; CHECK: llvm.recoverframeallocation first argument must be function defined in this module
+
+define internal void @j() {
+  call i8* @llvm.recoverframeallocation(i8* bitcast(void()* @declaration to i8*), i8* null)
+  ret void
+}
+; CHECK: llvm.recoverframeallocation first argument must be function defined in this module

llvm/trunk/utils/TableGen/CodeGenTarget.cpp

 void CodeGenTarget::ComputeInstrsByEnum() const {
   // The ordering here must match the ordering in TargetOpcodes.h.
   static const char *const FixedInstrs[] = {
       "PHI",          "INLINEASM",     "CFI_INSTRUCTION",  "EH_LABEL",
       "GC_LABEL",     "KILL",          "EXTRACT_SUBREG",   "INSERT_SUBREG",
       "IMPLICIT_DEF", "SUBREG_TO_REG", "COPY_TO_REGCLASS", "DBG_VALUE",
       "REG_SEQUENCE", "COPY",          "BUNDLE",           "LIFETIME_START",
       "LIFETIME_END", "STACKMAP",      "PATCHPOINT",       "LOAD_STACK_GUARD",
-      "STATEPOINT",
+      "STATEPOINT",   "FRAME_ALLOC",
       nullptr};
   const auto &Insts = getInstructions();
   for (const char *const *p = FixedInstrs; *p; ++p) {
     const CodeGenInstruction *Instr = GetInstByName(*p, Insts, Records);
     assert(Instr && "Missing target independent instruction");
     assert(Instr->Namespace == "TargetOpcode" && "Bad namespace");
     InstrsByEnum.push_back(Instr);
   }