[X86] Correct dwarf unwind information in function epilogue

CFI instructions that set appropriate cfa offset and cfa register are now
inserted in emitEpilogue() in X86FrameLowering.

Majority of the changes in this patch:

1. Ensure that CFI instructions do not affect code generation.
2. Enable maintaining correct information about cfa offset and cfa register
in a function when basic blocks are reordered, merged, split, duplicated.

These changes are target independent and described below.

Changed CFI instructions so that they:

1. are duplicable
2. are not counted as instructions when tail duplicating or tail merging
3. can be compared as equal

Add information to each MachineBasicBlock about cfa offset and cfa register
that are valid at its entry and exit (incoming and outgoing CFI info). Add
support for updating this information when basic blocks are merged, split,
duplicated, created. Add a verification pass (CFIInfoVerifier) that checks
that outgoing cfa offset and register of predecessor blocks match incoming
values of their successors.

Incoming and outgoing CFI information is used by a late pass
(CFIInstrInserter) that corrects CFA calculation rule for a basic block if
needed. That means that additional CFI instructions get inserted at basic
block beginning to correct the rule for calculating CFA. Having CFI
instructions in function epilogue can cause incorrect CFA calculation rule
for some basic blocks. This can happen if, due to basic block reordering,
or the existence of multiple epilogue blocks, some of the blocks have wrong
cfa offset and register values set by the epilogue block above them.

Patch by Violeta Vukobrat.

Differential Revision: https://reviews.llvm.org/D18046

llvm-svn: 306529

1 files changed, 227 insertions, 0 deletions

diff --git a/llvm/lib/CodeGen/MachineBasicBlock.cpp b/llvm/lib/CodeGen/MachineBasicBlock.cpp
index 81597afe6b0..c9976d7f2ff 100644
--- a/llvm/lib/CodeGen/MachineBasicBlock.cpp
+++ b/llvm/lib/CodeGen/MachineBasicBlock.cpp
@@ -35,6 +35,8 @@
 #include "llvm/Target/TargetRegisterInfo.h"
 #include "llvm/Target/TargetSubtargetInfo.h"
 #include <algorithm>
+#include <queue>
+#include <set>
 using namespace llvm;
 
 #define DEBUG_TYPE "codegen"
@@ -1343,3 +1345,228 @@ MachineBasicBlock::livein_iterator MachineBasicBlock::livein_begin() const {
       "Liveness information is accurate");
   return LiveIns.begin();
 }
+
+void MachineBasicBlock::updateCFIInfo(MachineBasicBlock::iterator Pos) {
+  // Used for calculating outgoing cfa offset when CFI instruction added at Pos
+  // is def_cfa or def_cfa_offset.
+  /* For example:
+     ...
+     .cfi_adjust_cfa_offset 4
+     ...
+     .cfi_adjust_cfa_offset 4
+     ...
+     .cfi_def_cfa_offset 16  <---- newly added CFI instruction at Pos
+     ...
+     .cfi_adjust_cfa_offset 4
+     ...
+     Once def_cfa_offset is inserted, outgoing cfa offset is no longer
+     calculated as incoming offset incremented by the sum of all adjustments
+     (12). It becomes equal to the offset set by the added CFI instruction (16)
+     incremented by the sum of adjustments below it (4). Adjustments above the
+     added def_cfa_offset directive don't have effect below it anymore and
+     therefore don't affect the value of outgoing cfa offset.
+  */
+  int AdjustAmount = 0;
+  // Used to check if outgoing cfa offset should be updated or not (when def_cfa
+  // is inserted).
+  bool ShouldSetOffset = true;
+  // Used to check if outgoing cfa register should be updated or not (when
+  // def_cfa is inserted).
+  bool ShouldSetRegister = true;
+  const std::vector<MCCFIInstruction> CFIInstructions =
+      getParent()->getFrameInstructions();
+  MCCFIInstruction CFI = CFIInstructions[Pos->getOperand(0).getCFIIndex()];
+  // Type of the CFI instruction that was inserted.
+  MCCFIInstruction::OpType CFIType = CFI.getOperation();
+
+  // Check if there are already existing CFI instructions below Pos and see if
+  // outgoing CFI info should be updated or not.
+  for (MachineBasicBlock::reverse_iterator RI = rbegin();
+       RI != Pos.getReverse(); ++RI) {
+    if (RI->isCFIInstruction()) {
+      MCCFIInstruction::OpType RIType =
+          CFIInstructions[RI->getOperand(0).getCFIIndex()].getOperation();
+      switch (RIType) {
+        case MCCFIInstruction::OpAdjustCfaOffset:
+          AdjustAmount +=
+              CFIInstructions[RI->getOperand(0).getCFIIndex()].getOffset();
+          break;
+        case MCCFIInstruction::OpDefCfaOffset:
+          // CFI instruction doesn't affect outgoing cfa offset if there is
+          // already a def_cfa_offset instruction below it.
+          if (CFIType == MCCFIInstruction::OpDefCfaOffset ||
+              CFIType == MCCFIInstruction::OpAdjustCfaOffset)
+            return;
+          if (CFIType == MCCFIInstruction::OpDefCfa) {
+            // CFI instruction doesn't affect outgoing cfa offset and register
+            // if there are both def_cfa_offset and def_cfa_register
+            // instructions below it.
+            if (!ShouldSetRegister) return;
+            ShouldSetOffset = false;
+          }
+          break;
+        case MCCFIInstruction::OpDefCfaRegister:
+          // CFI instruction doesn't affect outgoing cfa register if there is
+          // already a def_cfa_register instruction below it.
+          if (CFIType == MCCFIInstruction::OpDefCfaRegister) return;
+          if (CFIType == MCCFIInstruction::OpDefCfa) {
+            // CFI instruction doesn't affect outgoing cfa offset and register
+            // if there are both def_cfa_offset and def_cfa_register
+            // instructions below it.
+            if (!ShouldSetOffset) return;
+            ShouldSetRegister = false;
+          }
+          break;
+        case MCCFIInstruction::OpDefCfa:
+          // CFI instruction doesn't affect outgoing cfa offset and register if
+          // there is already a def_cfa instruction below it.
+          if (CFIType == MCCFIInstruction::OpDefCfaRegister ||
+              CFIType == MCCFIInstruction::OpDefCfaOffset ||
+              CFIType == MCCFIInstruction::OpDefCfa ||
+              CFIType == MCCFIInstruction::OpAdjustCfaOffset)
+            return;
+          break;
+        default:
+          break;
+      }
+    }
+  }
+
+  // Update the outgoing CFI info based on the added CFI instruction.
+  switch (CFIType) {
+    case MCCFIInstruction::OpAdjustCfaOffset:
+      setOutgoingCFAOffset(getOutgoingCFAOffset() + CFI.getOffset());
+      break;
+    case MCCFIInstruction::OpDefCfaOffset:
+      setOutgoingCFAOffset(CFI.getOffset() + AdjustAmount);
+      break;
+    case MCCFIInstruction::OpDefCfaRegister:
+      setOutgoingCFARegister(CFI.getRegister());
+      break;
+    case MCCFIInstruction::OpDefCfa:
+      if (ShouldSetOffset) setOutgoingCFAOffset(CFI.getOffset() + AdjustAmount);
+      if (ShouldSetRegister) setOutgoingCFARegister(CFI.getRegister());
+      break;
+    default:
+      break;
+  }
+}
+
+void MachineBasicBlock::updateCFIInfoSucc() {
+  // Blocks whose successors' CFI info should be updated.
+  std::queue<MachineBasicBlock *> Successors;
+  // Keep track of basic blocks that have already been put in the Successors
+  // queue.
+  std::set<MachineBasicBlock *> ProcessedMBBs;
+  // Start with updating CFI info for direct successors of this block.
+  Successors.push(this);
+  ProcessedMBBs.insert(this);
+
+  // Go through the successors and update their CFI info if needed.
+  while (!Successors.empty()) {
+    MachineBasicBlock *CurrSucc = Successors.front();
+    Successors.pop();
+
+    // Update CFI info for CurrSucc's successors.
+    for (auto Succ : CurrSucc->successors()) {
+      if (ProcessedMBBs.find(Succ) != ProcessedMBBs.end()) continue;
+      if (Succ->getIncomingCFAOffset() == CurrSucc->getOutgoingCFAOffset() &&
+          Succ->getIncomingCFARegister() == CurrSucc->getOutgoingCFARegister())
+        continue;
+      bool ChangedOutgoingInfo = false;
+      // Do not update cfa offset if the existing value matches the new.
+      if (Succ->getIncomingCFAOffset() != CurrSucc->getOutgoingCFAOffset()) {
+        // If the block doesn't have a def_cfa_offset or def_cfa directive,
+        // update its outgoing offset.
+        if (!Succ->hasDefOffset()) {
+          // Succ block doesn't set absolute offset, so the difference between
+          // outgoing and incoming offset remains the same. This difference is
+          // the sum of offsets set by adjust_cfa_offset directives.
+          int AdjustAmount =
+              Succ->getOutgoingCFAOffset() - Succ->getIncomingCFAOffset();
+          Succ->setOutgoingCFAOffset(CurrSucc->getOutgoingCFAOffset() +
+                                     AdjustAmount);
+          ChangedOutgoingInfo = true;
+        }
+        Succ->setIncomingCFAOffset(CurrSucc->getOutgoingCFAOffset());
+      }
+      // Do not update cfa register if the existing value matches the new.
+      if (Succ->getIncomingCFARegister() !=
+          CurrSucc->getOutgoingCFARegister()) {
+        Succ->setIncomingCFARegister(CurrSucc->getOutgoingCFARegister());
+        // If the block doesn't have a def_cfa_register or def_cfa directive,
+        // update its outgoing register.
+        if (!Succ->hasDefRegister()) {
+          Succ->setOutgoingCFARegister(Succ->getIncomingCFARegister());
+          ChangedOutgoingInfo = true;
+        }
+      }
+      // If Succ's outgoing CFI info has been changed, it's successors should be
+      // updated as well.
+      if (ChangedOutgoingInfo) {
+        Successors.push(Succ);
+        ProcessedMBBs.insert(Succ);
+      }
+    }
+  }
+}
+
+void MachineBasicBlock::recalculateCFIInfo(bool UseExistingIncoming,
+                                           int NewIncomingOffset,
+                                           unsigned NewIncomingRegister) {
+  // Outgoing cfa offset set by the block.
+  int SetOffset;
+  // Outgoing cfa register set by the block.
+  unsigned SetRegister;
+  const std::vector<MCCFIInstruction> &Instrs =
+      getParent()->getFrameInstructions();
+
+  // Set initial values to SetOffset and SetRegister. Use existing incoming
+  // values or values passed as arguments.
+  if (!UseExistingIncoming) {
+    // Set new incoming cfa offset and register values.
+    setIncomingCFAOffset(NewIncomingOffset);
+    setIncomingCFARegister(NewIncomingRegister);
+  }
+
+  SetOffset = getIncomingCFAOffset();
+  SetRegister = getIncomingCFARegister();
+
+  setDefOffset(false);
+  setDefRegister(false);
+
+  // Determine cfa offset and register set by the block.
+  for (MachineBasicBlock::iterator MI = begin(); MI != end(); ++MI) {
+    if (MI->isCFIInstruction()) {
+      unsigned CFIIndex = MI->getOperand(0).getCFIIndex();
+      const MCCFIInstruction &CFI = Instrs[CFIIndex];
+      if (CFI.getOperation() == MCCFIInstruction::OpDefCfaRegister) {
+        SetRegister = CFI.getRegister();
+        setDefRegister(true);
+      } else if (CFI.getOperation() == MCCFIInstruction::OpDefCfaOffset) {
+        SetOffset = CFI.getOffset();
+        setDefOffset(true);
+      } else if (CFI.getOperation() == MCCFIInstruction::OpAdjustCfaOffset) {
+        SetOffset = SetOffset + CFI.getOffset();
+      } else if (CFI.getOperation() == MCCFIInstruction::OpDefCfa) {
+        SetRegister = CFI.getRegister();
+        SetOffset = CFI.getOffset();
+        setDefOffset(true);
+        setDefRegister(true);
+      }
+    }
+  }
+
+  // Update outgoing CFI info.
+  setOutgoingCFAOffset(SetOffset);
+  setOutgoingCFARegister(SetRegister);
+}
+
+void MachineBasicBlock::mergeCFIInfo(MachineBasicBlock *MBB) {
+  // Update CFI info. This basic block acquires MBB's outgoing cfa offset and
+  // register values.
+  setOutgoingCFAOffset(MBB->getOutgoingCFAOffset());
+  setOutgoingCFARegister(MBB->getOutgoingCFARegister());
+  setDefOffset(hasDefOffset() || MBB->hasDefOffset());
+  setDefRegister(hasDefRegister() || MBB->hasDefRegister());
+}