1c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem//===-- StackColoring.cpp -------------------------------------------------===// 2c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem// 3c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem// The LLVM Compiler Infrastructure 4c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem// 5c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem// This file is distributed under the University of Illinois Open Source 6c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem// License. See LICENSE.TXT for details. 7c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem// 8c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem//===----------------------------------------------------------------------===// 9c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem// 10c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem// This pass implements the stack-coloring optimization that looks for 11c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem// lifetime markers machine instructions (LIFESTART_BEGIN and LIFESTART_END), 12c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem// which represent the possible lifetime of stack slots. It attempts to 13c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem// merge disjoint stack slots and reduce the used stack space. 14c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem// NOTE: This pass is not StackSlotColoring, which optimizes spill slots. 15c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem// 16c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem// TODO: In the future we plan to improve stack coloring in the following ways: 17c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem// 1. Allow merging multiple small slots into a single larger slot at different 18c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem// offsets. 19c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem// 2. Merge this pass with StackSlotColoring and allow merging of allocas with 20c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem// spill slots. 21c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem// 22c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem//===----------------------------------------------------------------------===// 23c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 24d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/CodeGen/Passes.h" 25c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem#include "llvm/ADT/BitVector.h" 26c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem#include "llvm/ADT/DepthFirstIterator.h" 27c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem#include "llvm/ADT/PostOrderIterator.h" 28c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem#include "llvm/ADT/SetVector.h" 29c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem#include "llvm/ADT/SmallPtrSet.h" 30c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem#include "llvm/ADT/SparseSet.h" 31c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem#include "llvm/ADT/Statistic.h" 32d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/Analysis/ValueTracking.h" 33c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem#include "llvm/CodeGen/LiveInterval.h" 34d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/CodeGen/MachineBasicBlock.h" 35c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem#include "llvm/CodeGen/MachineBranchProbabilityInfo.h" 36c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem#include "llvm/CodeGen/MachineDominators.h" 37d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/CodeGen/MachineFrameInfo.h" 38c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem#include "llvm/CodeGen/MachineFunctionPass.h" 39d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/CodeGen/MachineLoopInfo.h" 40d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/CodeGen/MachineMemOperand.h" 41c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem#include "llvm/CodeGen/MachineModuleInfo.h" 42c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem#include "llvm/CodeGen/MachineRegisterInfo.h" 43dd29df06fa72de9e370cdd9d8e32ac5437a578c7Akira Hatanaka#include "llvm/CodeGen/PseudoSourceValue.h" 44c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem#include "llvm/CodeGen/SlotIndexes.h" 4536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#include "llvm/CodeGen/StackProtector.h" 4636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#include "llvm/IR/DebugInfo.h" 4736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#include "llvm/IR/Dominators.h" 480b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Function.h" 490b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Instructions.h" 500b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Module.h" 51c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem#include "llvm/MC/MCInstrItineraries.h" 52c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem#include "llvm/Support/CommandLine.h" 53c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem#include "llvm/Support/Debug.h" 54c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem#include "llvm/Support/raw_ostream.h" 55d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/Target/TargetInstrInfo.h" 56d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/Target/TargetRegisterInfo.h" 57c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 58c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotemusing namespace llvm; 59c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 60dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines#define DEBUG_TYPE "stackcoloring" 61dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 62c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotemstatic cl::opt<bool> 63c05d30601ced172b55be81bb529df6be91d6ae15Nadav RotemDisableColoring("no-stack-coloring", 64d76f6eadc8c8511e1c5cd089a8a54e429c19aa60Nadav Rotem cl::init(false), cl::Hidden, 65d76f6eadc8c8511e1c5cd089a8a54e429c19aa60Nadav Rotem cl::desc("Disable stack coloring")); 66c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 6718e2c290940b67c9dc1196e3c2234e7a20f60ae4Nadav Rotem/// The user may write code that uses allocas outside of the declared lifetime 6818e2c290940b67c9dc1196e3c2234e7a20f60ae4Nadav Rotem/// zone. This can happen when the user returns a reference to a local 6918e2c290940b67c9dc1196e3c2234e7a20f60ae4Nadav Rotem/// data-structure. We can detect these cases and decide not to optimize the 7018e2c290940b67c9dc1196e3c2234e7a20f60ae4Nadav Rotem/// code. If this flag is enabled, we try to save the user. 71d76f6eadc8c8511e1c5cd089a8a54e429c19aa60Nadav Rotemstatic cl::opt<bool> 7218e2c290940b67c9dc1196e3c2234e7a20f60ae4Nadav RotemProtectFromEscapedAllocas("protect-from-escaped-allocas", 73259021a5621fd3837db79934ea5880cb846bfc44Eric Christopher cl::init(false), cl::Hidden, 74259021a5621fd3837db79934ea5880cb846bfc44Eric Christopher cl::desc("Do not optimize lifetime zones that " 75259021a5621fd3837db79934ea5880cb846bfc44Eric Christopher "are broken")); 76d76f6eadc8c8511e1c5cd089a8a54e429c19aa60Nadav Rotem 77d76f6eadc8c8511e1c5cd089a8a54e429c19aa60Nadav RotemSTATISTIC(NumMarkerSeen, "Number of lifetime markers found."); 78c05d30601ced172b55be81bb529df6be91d6ae15Nadav RotemSTATISTIC(StackSpaceSaved, "Number of bytes saved due to merging slots."); 79c05d30601ced172b55be81bb529df6be91d6ae15Nadav RotemSTATISTIC(StackSlotMerged, "Number of stack slot merged."); 80259021a5621fd3837db79934ea5880cb846bfc44Eric ChristopherSTATISTIC(EscapedAllocas, "Number of allocas that escaped the lifetime region"); 81d76f6eadc8c8511e1c5cd089a8a54e429c19aa60Nadav Rotem 82c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem//===----------------------------------------------------------------------===// 83c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem// StackColoring Pass 84c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem//===----------------------------------------------------------------------===// 85c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 86c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotemnamespace { 87c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem/// StackColoring - A machine pass for merging disjoint stack allocations, 88c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem/// marked by the LIFETIME_START and LIFETIME_END pseudo instructions. 89c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotemclass StackColoring : public MachineFunctionPass { 90c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem MachineFrameInfo *MFI; 91c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem MachineFunction *MF; 92c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 93c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem /// A class representing liveness information for a single basic block. 94c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem /// Each bit in the BitVector represents the liveness property 95c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem /// for a different stack slot. 96c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem struct BlockLifetimeInfo { 97c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem /// Which slots BEGINs in each basic block. 98c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem BitVector Begin; 99c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem /// Which slots ENDs in each basic block. 100c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem BitVector End; 101c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem /// Which slots are marked as LIVE_IN, coming into each basic block. 102c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem BitVector LiveIn; 103c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem /// Which slots are marked as LIVE_OUT, coming out of each basic block. 104c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem BitVector LiveOut; 105c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem }; 106c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 107c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem /// Maps active slots (per bit) for each basic block. 10804fbcb59432c085bb284501dcea9693f435a417bCraig Topper typedef DenseMap<const MachineBasicBlock*, BlockLifetimeInfo> LivenessMap; 10904fbcb59432c085bb284501dcea9693f435a417bCraig Topper LivenessMap BlockLiveness; 110c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 111c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem /// Maps serial numbers to basic blocks. 11204fbcb59432c085bb284501dcea9693f435a417bCraig Topper DenseMap<const MachineBasicBlock*, int> BasicBlocks; 113c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem /// Maps basic blocks to a serial number. 11404fbcb59432c085bb284501dcea9693f435a417bCraig Topper SmallVector<const MachineBasicBlock*, 8> BasicBlockNumbering; 115c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 116c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem /// Maps liveness intervals for each slot. 11736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines SmallVector<std::unique_ptr<LiveInterval>, 16> Intervals; 118c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem /// VNInfo is used for the construction of LiveIntervals. 119c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem VNInfo::Allocator VNInfoAllocator; 120c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem /// SlotIndex analysis object. 121d76f6eadc8c8511e1c5cd089a8a54e429c19aa60Nadav Rotem SlotIndexes *Indexes; 12236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// The stack protector object. 12336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines StackProtector *SP; 124c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 125c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem /// The list of lifetime markers found. These markers are to be removed 126c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem /// once the coloring is done. 127c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem SmallVector<MachineInstr*, 8> Markers; 128c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 129c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotempublic: 130c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem static char ID; 131c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem StackColoring() : MachineFunctionPass(ID) { 132c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem initializeStackColoringPass(*PassRegistry::getPassRegistry()); 133c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem } 13436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines void getAnalysisUsage(AnalysisUsage &AU) const override; 13536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines bool runOnMachineFunction(MachineFunction &MF) override; 136c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 137c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotemprivate: 138c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem /// Debug. 139cbc6d797054a2bf2a641031f270d38804a6f2295Craig Topper void dump() const; 140c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 141c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem /// Removes all of the lifetime marker instructions from the function. 142c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem /// \returns true if any markers were removed. 143c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem bool removeAllMarkers(); 144c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 145c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem /// Scan the machine function and find all of the lifetime markers. 146c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem /// Record the findings in the BEGIN and END vectors. 147c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem /// \returns the number of markers found. 148c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem unsigned collectMarkers(unsigned NumSlot); 149c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 150c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem /// Perform the dataflow calculation and calculate the lifetime for each of 151c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem /// the slots, based on the BEGIN/END vectors. Set the LifetimeLIVE_IN and 152c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem /// LifetimeLIVE_OUT maps that represent which stack slots are live coming 153c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem /// in and out blocks. 154c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem void calculateLocalLiveness(); 155c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 156c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem /// Construct the LiveIntervals for the slots. 157c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem void calculateLiveIntervals(unsigned NumSlots); 158c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 159c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem /// Go over the machine function and change instructions which use stack 160c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem /// slots to use the joint slots. 161c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem void remapInstructions(DenseMap<int, int> &SlotRemap); 162c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 163f80a63fa23862e578de919f4b44d4fcdee68fd0dRobert Wilhelm /// The input program may contain instructions which are not inside lifetime 1640a16da445740ca6fcd7a7ca571c1917e77315904Nadav Rotem /// markers. This can happen due to a bug in the compiler or due to a bug in 1650a16da445740ca6fcd7a7ca571c1917e77315904Nadav Rotem /// user code (for example, returning a reference to a local variable). 1660a16da445740ca6fcd7a7ca571c1917e77315904Nadav Rotem /// This procedure checks all of the instructions in the function and 1670a16da445740ca6fcd7a7ca571c1917e77315904Nadav Rotem /// invalidates lifetime ranges which do not contain all of the instructions 1680a16da445740ca6fcd7a7ca571c1917e77315904Nadav Rotem /// which access that frame slot. 1690a16da445740ca6fcd7a7ca571c1917e77315904Nadav Rotem void removeInvalidSlotRanges(); 1700a16da445740ca6fcd7a7ca571c1917e77315904Nadav Rotem 171c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem /// Map entries which point to other entries to their destination. 172c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem /// A->B->C becomes A->C. 173c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem void expungeSlotMap(DenseMap<int, int> &SlotRemap, unsigned NumSlots); 174c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem}; 175c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem} // end anonymous namespace 176c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 177c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotemchar StackColoring::ID = 0; 178c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotemchar &llvm::StackColoringID = StackColoring::ID; 179c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 180c05d30601ced172b55be81bb529df6be91d6ae15Nadav RotemINITIALIZE_PASS_BEGIN(StackColoring, 181c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem "stack-coloring", "Merge disjoint stack slots", false, false) 182c05d30601ced172b55be81bb529df6be91d6ae15Nadav RotemINITIALIZE_PASS_DEPENDENCY(MachineDominatorTree) 183c05d30601ced172b55be81bb529df6be91d6ae15Nadav RotemINITIALIZE_PASS_DEPENDENCY(SlotIndexes) 18436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen HinesINITIALIZE_PASS_DEPENDENCY(StackProtector) 185c05d30601ced172b55be81bb529df6be91d6ae15Nadav RotemINITIALIZE_PASS_END(StackColoring, 186c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem "stack-coloring", "Merge disjoint stack slots", false, false) 187c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 188c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotemvoid StackColoring::getAnalysisUsage(AnalysisUsage &AU) const { 189c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem AU.addRequired<MachineDominatorTree>(); 190c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem AU.addPreserved<MachineDominatorTree>(); 191c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem AU.addRequired<SlotIndexes>(); 19236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines AU.addRequired<StackProtector>(); 193c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem MachineFunctionPass::getAnalysisUsage(AU); 194c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem} 195c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 196cbc6d797054a2bf2a641031f270d38804a6f2295Craig Toppervoid StackColoring::dump() const { 197dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines for (MachineBasicBlock *MBB : depth_first(MF)) { 198dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines DEBUG(dbgs() << "Inspecting block #" << BasicBlocks.lookup(MBB) << " [" 199dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines << MBB->getName() << "]\n"); 200cbc6d797054a2bf2a641031f270d38804a6f2295Craig Topper 201dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines LivenessMap::const_iterator BI = BlockLiveness.find(MBB); 202cbc6d797054a2bf2a641031f270d38804a6f2295Craig Topper assert(BI != BlockLiveness.end() && "Block not found"); 203cbc6d797054a2bf2a641031f270d38804a6f2295Craig Topper const BlockLifetimeInfo &BlockInfo = BI->second; 204cbc6d797054a2bf2a641031f270d38804a6f2295Craig Topper 205c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem DEBUG(dbgs()<<"BEGIN : {"); 206cbc6d797054a2bf2a641031f270d38804a6f2295Craig Topper for (unsigned i=0; i < BlockInfo.Begin.size(); ++i) 207cbc6d797054a2bf2a641031f270d38804a6f2295Craig Topper DEBUG(dbgs()<<BlockInfo.Begin.test(i)<<" "); 208c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem DEBUG(dbgs()<<"}\n"); 209c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 210c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem DEBUG(dbgs()<<"END : {"); 211cbc6d797054a2bf2a641031f270d38804a6f2295Craig Topper for (unsigned i=0; i < BlockInfo.End.size(); ++i) 212cbc6d797054a2bf2a641031f270d38804a6f2295Craig Topper DEBUG(dbgs()<<BlockInfo.End.test(i)<<" "); 213c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 214c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem DEBUG(dbgs()<<"}\n"); 215c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 216c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem DEBUG(dbgs()<<"LIVE_IN: {"); 217cbc6d797054a2bf2a641031f270d38804a6f2295Craig Topper for (unsigned i=0; i < BlockInfo.LiveIn.size(); ++i) 218cbc6d797054a2bf2a641031f270d38804a6f2295Craig Topper DEBUG(dbgs()<<BlockInfo.LiveIn.test(i)<<" "); 219c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 220c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem DEBUG(dbgs()<<"}\n"); 221c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem DEBUG(dbgs()<<"LIVEOUT: {"); 222cbc6d797054a2bf2a641031f270d38804a6f2295Craig Topper for (unsigned i=0; i < BlockInfo.LiveOut.size(); ++i) 223cbc6d797054a2bf2a641031f270d38804a6f2295Craig Topper DEBUG(dbgs()<<BlockInfo.LiveOut.test(i)<<" "); 224c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem DEBUG(dbgs()<<"}\n"); 225c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem } 226c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem} 227c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 228c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotemunsigned StackColoring::collectMarkers(unsigned NumSlot) { 229c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem unsigned MarkersFound = 0; 230c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem // Scan the function to find all lifetime markers. 231c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem // NOTE: We use the a reverse-post-order iteration to ensure that we obtain a 232c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem // deterministic numbering, and because we'll need a post-order iteration 233c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem // later for solving the liveness dataflow problem. 234dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines for (MachineBasicBlock *MBB : depth_first(MF)) { 235c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 236c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem // Assign a serial number to this basic block. 237dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines BasicBlocks[MBB] = BasicBlockNumbering.size(); 238dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines BasicBlockNumbering.push_back(MBB); 239c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 240252d798fc302ed78bc4b11e66a2382015a25c6e0Craig Topper // Keep a reference to avoid repeated lookups. 241dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines BlockLifetimeInfo &BlockInfo = BlockLiveness[MBB]; 242252d798fc302ed78bc4b11e66a2382015a25c6e0Craig Topper 243252d798fc302ed78bc4b11e66a2382015a25c6e0Craig Topper BlockInfo.Begin.resize(NumSlot); 244252d798fc302ed78bc4b11e66a2382015a25c6e0Craig Topper BlockInfo.End.resize(NumSlot); 245c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 246dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines for (MachineInstr &MI : *MBB) { 24736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (MI.getOpcode() != TargetOpcode::LIFETIME_START && 24836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines MI.getOpcode() != TargetOpcode::LIFETIME_END) 249c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem continue; 250c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 25136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Markers.push_back(&MI); 252c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 25336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines bool IsStart = MI.getOpcode() == TargetOpcode::LIFETIME_START; 25436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines const MachineOperand &MO = MI.getOperand(0); 25536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines unsigned Slot = MO.getIndex(); 256c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 257c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem MarkersFound++; 258c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 25983ba06afa8503dc97a0aa5ec033022286959956cSebastian Pop const AllocaInst *Allocation = MFI->getObjectAllocation(Slot); 260c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem if (Allocation) { 2610cd19b93017fcaba737b15ea4da39c460feb5670Nadav Rotem DEBUG(dbgs()<<"Found a lifetime marker for slot #"<<Slot<< 2620cd19b93017fcaba737b15ea4da39c460feb5670Nadav Rotem " with allocation: "<< Allocation->getName()<<"\n"); 263c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem } 264c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 265c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem if (IsStart) { 266252d798fc302ed78bc4b11e66a2382015a25c6e0Craig Topper BlockInfo.Begin.set(Slot); 267c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem } else { 268252d798fc302ed78bc4b11e66a2382015a25c6e0Craig Topper if (BlockInfo.Begin.test(Slot)) { 269c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem // Allocas that start and end within a single block are handled 270c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem // specially when computing the LiveIntervals to avoid pessimizing 271c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem // the liveness propagation. 272252d798fc302ed78bc4b11e66a2382015a25c6e0Craig Topper BlockInfo.Begin.reset(Slot); 273c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem } else { 274252d798fc302ed78bc4b11e66a2382015a25c6e0Craig Topper BlockInfo.End.set(Slot); 275c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem } 276c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem } 277c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem } 278c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem } 279c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 280c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem // Update statistics. 281c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem NumMarkerSeen += MarkersFound; 282c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem return MarkersFound; 283c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem} 284c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 285c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotemvoid StackColoring::calculateLocalLiveness() { 286c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem // Perform a standard reverse dataflow computation to solve for 287c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem // global liveness. The BEGIN set here is equivalent to KILL in the standard 288c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem // formulation, and END is equivalent to GEN. The result of this computation 289c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem // is a map from blocks to bitvectors where the bitvectors represent which 290c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem // allocas are live in/out of that block. 29104fbcb59432c085bb284501dcea9693f435a417bCraig Topper SmallPtrSet<const MachineBasicBlock*, 8> BBSet(BasicBlockNumbering.begin(), 29204fbcb59432c085bb284501dcea9693f435a417bCraig Topper BasicBlockNumbering.end()); 293c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem unsigned NumSSMIters = 0; 294c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem bool changed = true; 295c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem while (changed) { 296c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem changed = false; 297c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem ++NumSSMIters; 298c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 29904fbcb59432c085bb284501dcea9693f435a417bCraig Topper SmallPtrSet<const MachineBasicBlock*, 8> NextBBSet; 300c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 30136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines for (const MachineBasicBlock *BB : BasicBlockNumbering) { 302c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem if (!BBSet.count(BB)) continue; 303c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 304cede03886712e18b697f9ec91311d4a8df60c734Craig Topper // Use an iterator to avoid repeated lookups. 30504fbcb59432c085bb284501dcea9693f435a417bCraig Topper LivenessMap::iterator BI = BlockLiveness.find(BB); 306cede03886712e18b697f9ec91311d4a8df60c734Craig Topper assert(BI != BlockLiveness.end() && "Block not found"); 307cede03886712e18b697f9ec91311d4a8df60c734Craig Topper BlockLifetimeInfo &BlockInfo = BI->second; 308cede03886712e18b697f9ec91311d4a8df60c734Craig Topper 309c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem BitVector LocalLiveIn; 310c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem BitVector LocalLiveOut; 311c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 312c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem // Forward propagation from begins to ends. 313cede03886712e18b697f9ec91311d4a8df60c734Craig Topper for (MachineBasicBlock::const_pred_iterator PI = BB->pred_begin(), 314cede03886712e18b697f9ec91311d4a8df60c734Craig Topper PE = BB->pred_end(); PI != PE; ++PI) { 31504fbcb59432c085bb284501dcea9693f435a417bCraig Topper LivenessMap::const_iterator I = BlockLiveness.find(*PI); 316cede03886712e18b697f9ec91311d4a8df60c734Craig Topper assert(I != BlockLiveness.end() && "Predecessor not found"); 317cede03886712e18b697f9ec91311d4a8df60c734Craig Topper LocalLiveIn |= I->second.LiveOut; 318cede03886712e18b697f9ec91311d4a8df60c734Craig Topper } 319cede03886712e18b697f9ec91311d4a8df60c734Craig Topper LocalLiveIn |= BlockInfo.End; 320cede03886712e18b697f9ec91311d4a8df60c734Craig Topper LocalLiveIn.reset(BlockInfo.Begin); 321c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 322c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem // Reverse propagation from ends to begins. 323cede03886712e18b697f9ec91311d4a8df60c734Craig Topper for (MachineBasicBlock::const_succ_iterator SI = BB->succ_begin(), 324cede03886712e18b697f9ec91311d4a8df60c734Craig Topper SE = BB->succ_end(); SI != SE; ++SI) { 32504fbcb59432c085bb284501dcea9693f435a417bCraig Topper LivenessMap::const_iterator I = BlockLiveness.find(*SI); 326cede03886712e18b697f9ec91311d4a8df60c734Craig Topper assert(I != BlockLiveness.end() && "Successor not found"); 327cede03886712e18b697f9ec91311d4a8df60c734Craig Topper LocalLiveOut |= I->second.LiveIn; 328cede03886712e18b697f9ec91311d4a8df60c734Craig Topper } 329cede03886712e18b697f9ec91311d4a8df60c734Craig Topper LocalLiveOut |= BlockInfo.Begin; 330cede03886712e18b697f9ec91311d4a8df60c734Craig Topper LocalLiveOut.reset(BlockInfo.End); 331c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 332c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem LocalLiveIn |= LocalLiveOut; 333c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem LocalLiveOut |= LocalLiveIn; 334c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 335c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem // After adopting the live bits, we need to turn-off the bits which 336c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem // are de-activated in this block. 337cede03886712e18b697f9ec91311d4a8df60c734Craig Topper LocalLiveOut.reset(BlockInfo.End); 338cede03886712e18b697f9ec91311d4a8df60c734Craig Topper LocalLiveIn.reset(BlockInfo.Begin); 339c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 3406165dba25f3374ce340b420ab9a360623c26fdc3Nadav Rotem // If we have both BEGIN and END markers in the same basic block then 3416165dba25f3374ce340b420ab9a360623c26fdc3Nadav Rotem // we know that the BEGIN marker comes after the END, because we already 3426165dba25f3374ce340b420ab9a360623c26fdc3Nadav Rotem // handle the case where the BEGIN comes before the END when collecting 3436165dba25f3374ce340b420ab9a360623c26fdc3Nadav Rotem // the markers (and building the BEGIN/END vectore). 3446165dba25f3374ce340b420ab9a360623c26fdc3Nadav Rotem // Want to enable the LIVE_IN and LIVE_OUT of slots that have both 3456165dba25f3374ce340b420ab9a360623c26fdc3Nadav Rotem // BEGIN and END because it means that the value lives before and after 3466165dba25f3374ce340b420ab9a360623c26fdc3Nadav Rotem // this basic block. 347cede03886712e18b697f9ec91311d4a8df60c734Craig Topper BitVector LocalEndBegin = BlockInfo.End; 348cede03886712e18b697f9ec91311d4a8df60c734Craig Topper LocalEndBegin &= BlockInfo.Begin; 3496165dba25f3374ce340b420ab9a360623c26fdc3Nadav Rotem LocalLiveIn |= LocalEndBegin; 3506165dba25f3374ce340b420ab9a360623c26fdc3Nadav Rotem LocalLiveOut |= LocalEndBegin; 3516165dba25f3374ce340b420ab9a360623c26fdc3Nadav Rotem 352cede03886712e18b697f9ec91311d4a8df60c734Craig Topper if (LocalLiveIn.test(BlockInfo.LiveIn)) { 353c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem changed = true; 354cede03886712e18b697f9ec91311d4a8df60c734Craig Topper BlockInfo.LiveIn |= LocalLiveIn; 355c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 35636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines NextBBSet.insert(BB->pred_begin(), BB->pred_end()); 357c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem } 358c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 359cede03886712e18b697f9ec91311d4a8df60c734Craig Topper if (LocalLiveOut.test(BlockInfo.LiveOut)) { 360c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem changed = true; 361cede03886712e18b697f9ec91311d4a8df60c734Craig Topper BlockInfo.LiveOut |= LocalLiveOut; 362c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 36336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines NextBBSet.insert(BB->succ_begin(), BB->succ_end()); 364c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem } 365c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem } 366c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 367c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem BBSet = NextBBSet; 368c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem }// while changed. 369c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem} 370c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 371c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotemvoid StackColoring::calculateLiveIntervals(unsigned NumSlots) { 372c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem SmallVector<SlotIndex, 16> Starts; 373c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem SmallVector<SlotIndex, 16> Finishes; 374c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 375c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem // For each block, find which slots are active within this block 376c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem // and update the live intervals. 37736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines for (const MachineBasicBlock &MBB : *MF) { 378c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem Starts.clear(); 379c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem Starts.resize(NumSlots); 380c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem Finishes.clear(); 381c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem Finishes.resize(NumSlots); 382c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 383e47feeb823ebf496e82db6a666d4c0fbaeb158b4Nadav Rotem // Create the interval for the basic blocks with lifetime markers in them. 38436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines for (const MachineInstr *MI : Markers) { 38536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (MI->getParent() != &MBB) 386e47feeb823ebf496e82db6a666d4c0fbaeb158b4Nadav Rotem continue; 387e47feeb823ebf496e82db6a666d4c0fbaeb158b4Nadav Rotem 388c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem assert((MI->getOpcode() == TargetOpcode::LIFETIME_START || 389c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem MI->getOpcode() == TargetOpcode::LIFETIME_END) && 390c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem "Invalid Lifetime marker"); 391c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 392e47feeb823ebf496e82db6a666d4c0fbaeb158b4Nadav Rotem bool IsStart = MI->getOpcode() == TargetOpcode::LIFETIME_START; 393261abf5f4011e5b1e8949d7404190a4f4eaff8d8Craig Topper const MachineOperand &Mo = MI->getOperand(0); 394e47feeb823ebf496e82db6a666d4c0fbaeb158b4Nadav Rotem int Slot = Mo.getIndex(); 395e47feeb823ebf496e82db6a666d4c0fbaeb158b4Nadav Rotem assert(Slot >= 0 && "Invalid slot"); 396e47feeb823ebf496e82db6a666d4c0fbaeb158b4Nadav Rotem 397e47feeb823ebf496e82db6a666d4c0fbaeb158b4Nadav Rotem SlotIndex ThisIndex = Indexes->getInstructionIndex(MI); 398e47feeb823ebf496e82db6a666d4c0fbaeb158b4Nadav Rotem 399e47feeb823ebf496e82db6a666d4c0fbaeb158b4Nadav Rotem if (IsStart) { 400e47feeb823ebf496e82db6a666d4c0fbaeb158b4Nadav Rotem if (!Starts[Slot].isValid() || Starts[Slot] > ThisIndex) 401e47feeb823ebf496e82db6a666d4c0fbaeb158b4Nadav Rotem Starts[Slot] = ThisIndex; 402e47feeb823ebf496e82db6a666d4c0fbaeb158b4Nadav Rotem } else { 403e47feeb823ebf496e82db6a666d4c0fbaeb158b4Nadav Rotem if (!Finishes[Slot].isValid() || Finishes[Slot] < ThisIndex) 404e47feeb823ebf496e82db6a666d4c0fbaeb158b4Nadav Rotem Finishes[Slot] = ThisIndex; 405e47feeb823ebf496e82db6a666d4c0fbaeb158b4Nadav Rotem } 406e47feeb823ebf496e82db6a666d4c0fbaeb158b4Nadav Rotem } 407e47feeb823ebf496e82db6a666d4c0fbaeb158b4Nadav Rotem 408e47feeb823ebf496e82db6a666d4c0fbaeb158b4Nadav Rotem // Create the interval of the blocks that we previously found to be 'alive'. 40936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines BlockLifetimeInfo &MBBLiveness = BlockLiveness[&MBB]; 410c22cdb7203e4aad8e6491487f224efff7a3e58c0Derek Schuff for (int pos = MBBLiveness.LiveIn.find_first(); pos != -1; 411c22cdb7203e4aad8e6491487f224efff7a3e58c0Derek Schuff pos = MBBLiveness.LiveIn.find_next(pos)) { 41236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Starts[pos] = Indexes->getMBBStartIdx(&MBB); 413c22cdb7203e4aad8e6491487f224efff7a3e58c0Derek Schuff } 414c22cdb7203e4aad8e6491487f224efff7a3e58c0Derek Schuff for (int pos = MBBLiveness.LiveOut.find_first(); pos != -1; 415c22cdb7203e4aad8e6491487f224efff7a3e58c0Derek Schuff pos = MBBLiveness.LiveOut.find_next(pos)) { 41636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Finishes[pos] = Indexes->getMBBEndIdx(&MBB); 417c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem } 418c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 419c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem for (unsigned i = 0; i < NumSlots; ++i) { 420e47feeb823ebf496e82db6a666d4c0fbaeb158b4Nadav Rotem assert(Starts[i].isValid() == Finishes[i].isValid() && "Unmatched range"); 421e47feeb823ebf496e82db6a666d4c0fbaeb158b4Nadav Rotem if (!Starts[i].isValid()) 422c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem continue; 423c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 424c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem assert(Starts[i] && Finishes[i] && "Invalid interval"); 425c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem VNInfo *ValNum = Intervals[i]->getValNumInfo(0); 426c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem SlotIndex S = Starts[i]; 427c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem SlotIndex F = Finishes[i]; 428c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem if (S < F) { 429c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem // We have a single consecutive region. 430331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun Intervals[i]->addSegment(LiveInterval::Segment(S, F, ValNum)); 431c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem } else { 43236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // We have two non-consecutive regions. This happens when 433c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem // LIFETIME_START appears after the LIFETIME_END marker. 43436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines SlotIndex NewStart = Indexes->getMBBStartIdx(&MBB); 43536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines SlotIndex NewFin = Indexes->getMBBEndIdx(&MBB); 436331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun Intervals[i]->addSegment(LiveInterval::Segment(NewStart, F, ValNum)); 437331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun Intervals[i]->addSegment(LiveInterval::Segment(S, NewFin, ValNum)); 438c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem } 439c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem } 440c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem } 441c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem} 442c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 443c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotembool StackColoring::removeAllMarkers() { 444c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem unsigned Count = 0; 44536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines for (MachineInstr *MI : Markers) { 44636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines MI->eraseFromParent(); 447c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem Count++; 448c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem } 449c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem Markers.clear(); 450c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 451c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem DEBUG(dbgs()<<"Removed "<<Count<<" markers.\n"); 452c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem return Count; 453c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem} 454c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 455c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotemvoid StackColoring::remapInstructions(DenseMap<int, int> &SlotRemap) { 456c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem unsigned FixedInstr = 0; 457c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem unsigned FixedMemOp = 0; 458c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem unsigned FixedDbg = 0; 459c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem MachineModuleInfo *MMI = &MF->getMMI(); 460c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 461c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem // Remap debug information that refers to stack slots. 46236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines for (auto &VI : MMI->getVariableDbgInfo()) { 46336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (!VI.Var) 46436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines continue; 46536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (SlotRemap.count(VI.Slot)) { 46636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines DEBUG(dbgs()<<"Remapping debug info for ["<<VI.Var->getName()<<"].\n"); 46736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines VI.Slot = SlotRemap[VI.Slot]; 468c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem FixedDbg++; 469c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem } 470c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem } 471c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 472c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem // Keep a list of *allocas* which need to be remapped. 47383ba06afa8503dc97a0aa5ec033022286959956cSebastian Pop DenseMap<const AllocaInst*, const AllocaInst*> Allocas; 47436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines for (const std::pair<int, int> &SI : SlotRemap) { 47536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines const AllocaInst *From = MFI->getObjectAllocation(SI.first); 47636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines const AllocaInst *To = MFI->getObjectAllocation(SI.second); 477c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem assert(To && From && "Invalid allocation object"); 478c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem Allocas[From] = To; 47936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 48036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // AA might be used later for instruction scheduling, and we need it to be 48136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // able to deduce the correct aliasing releationships between pointers 48236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // derived from the alloca being remapped and the target of that remapping. 48336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // The only safe way, without directly informing AA about the remapping 48436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // somehow, is to directly update the IR to reflect the change being made 48536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // here. 48636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Instruction *Inst = const_cast<AllocaInst *>(To); 48736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (From->getType() != To->getType()) { 48836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines BitCastInst *Cast = new BitCastInst(Inst, From->getType()); 48936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Cast->insertAfter(Inst); 49036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Inst = Cast; 49136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 49236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 49336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // Allow the stack protector to adjust its value map to account for the 49436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // upcoming replacement. 49536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines SP->adjustForColoring(From, To); 49636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 49736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // Note that this will not replace uses in MMOs (which we'll update below), 49836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // or anywhere else (which is why we won't delete the original 49936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // instruction). 50036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines const_cast<AllocaInst *>(From)->replaceAllUsesWith(Inst); 501c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem } 502c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 503c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem // Remap all instructions to the new stack slots. 50436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines for (MachineBasicBlock &BB : *MF) 50536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines for (MachineInstr &I : BB) { 5060aa52ee04e3060974474f6b3f824517c088f07d8Nadav Rotem // Skip lifetime markers. We'll remove them soon. 50736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (I.getOpcode() == TargetOpcode::LIFETIME_START || 50836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines I.getOpcode() == TargetOpcode::LIFETIME_END) 5090aa52ee04e3060974474f6b3f824517c088f07d8Nadav Rotem continue; 5100aa52ee04e3060974474f6b3f824517c088f07d8Nadav Rotem 511c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem // Update the MachineMemOperand to use the new alloca. 51236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines for (MachineMemOperand *MMO : I.memoperands()) { 51336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // FIXME: In order to enable the use of TBAA when using AA in CodeGen, 51436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // we'll also need to update the TBAA nodes in MMOs with values 51536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // derived from the merged allocas. When doing this, we'll need to use 51636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // the same variant of GetUnderlyingObjects that is used by the 51736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // instruction scheduler (that can look through ptrtoint/inttoptr 51836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // pairs). 519dd29df06fa72de9e370cdd9d8e32ac5437a578c7Akira Hatanaka 52036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // We've replaced IR-level uses of the remapped allocas, so we only 52136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // need to replace direct uses here. 522dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines const AllocaInst *AI = dyn_cast_or_null<AllocaInst>(MMO->getValue()); 523dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (!AI) 52483ba06afa8503dc97a0aa5ec033022286959956cSebastian Pop continue; 52536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 52683ba06afa8503dc97a0aa5ec033022286959956cSebastian Pop if (!Allocas.count(AI)) 527c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem continue; 528c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 52983ba06afa8503dc97a0aa5ec033022286959956cSebastian Pop MMO->setValue(Allocas[AI]); 530c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem FixedMemOp++; 531c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem } 532c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 533c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem // Update all of the machine instruction operands. 53436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines for (MachineOperand &MO : I.operands()) { 535c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem if (!MO.isFI()) 536c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem continue; 537c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem int FromSlot = MO.getIndex(); 538c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 539c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem // Don't touch arguments. 540c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem if (FromSlot<0) 541c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem continue; 542c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 543c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem // Only look at mapped slots. 544c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem if (!SlotRemap.count(FromSlot)) 545c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem continue; 546c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 5478cc14949053ea4fcba34afc68b30137eff408d66Nadav Rotem // In a debug build, check that the instruction that we are modifying is 5488cc14949053ea4fcba34afc68b30137eff408d66Nadav Rotem // inside the expected live range. If the instruction is not inside 5490aa52ee04e3060974474f6b3f824517c088f07d8Nadav Rotem // the calculated range then it means that the alloca usage moved 55018e2c290940b67c9dc1196e3c2234e7a20f60ae4Nadav Rotem // outside of the lifetime markers, or that the user has a bug. 5510cd19b93017fcaba737b15ea4da39c460feb5670Nadav Rotem // NOTE: Alloca address calculations which happen outside the lifetime 5520cd19b93017fcaba737b15ea4da39c460feb5670Nadav Rotem // zone are are okay, despite the fact that we don't have a good way 5530cd19b93017fcaba737b15ea4da39c460feb5670Nadav Rotem // for validating all of the usages of the calculation. 5540aa52ee04e3060974474f6b3f824517c088f07d8Nadav Rotem#ifndef NDEBUG 55536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines bool TouchesMemory = I.mayLoad() || I.mayStore(); 55618e2c290940b67c9dc1196e3c2234e7a20f60ae4Nadav Rotem // If we *don't* protect the user from escaped allocas, don't bother 55718e2c290940b67c9dc1196e3c2234e7a20f60ae4Nadav Rotem // validating the instructions. 55836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (!I.isDebugValue() && TouchesMemory && ProtectFromEscapedAllocas) { 55936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines SlotIndex Index = Indexes->getInstructionIndex(&I); 56036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines const LiveInterval *Interval = &*Intervals[FromSlot]; 5618754bbbe672450689a5bdc8a198af90144e56f31Nadav Rotem assert(Interval->find(Index) != Interval->end() && 56257d76078ae8ecd16b995cc6a9f9bc57bdde4a20eEric Christopher "Found instruction usage outside of live range."); 5638754bbbe672450689a5bdc8a198af90144e56f31Nadav Rotem } 5640aa52ee04e3060974474f6b3f824517c088f07d8Nadav Rotem#endif 5650aa52ee04e3060974474f6b3f824517c088f07d8Nadav Rotem 566c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem // Fix the machine instructions. 567c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem int ToSlot = SlotRemap[FromSlot]; 568c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem MO.setIndex(ToSlot); 569c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem FixedInstr++; 570c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem } 571c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem } 572c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 573c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem DEBUG(dbgs()<<"Fixed "<<FixedMemOp<<" machine memory operands.\n"); 574c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem DEBUG(dbgs()<<"Fixed "<<FixedDbg<<" debug locations.\n"); 575c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem DEBUG(dbgs()<<"Fixed "<<FixedInstr<<" machine instructions.\n"); 576c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem} 577c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 5780a16da445740ca6fcd7a7ca571c1917e77315904Nadav Rotemvoid StackColoring::removeInvalidSlotRanges() { 57936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines for (MachineBasicBlock &BB : *MF) 58036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines for (MachineInstr &I : BB) { 58136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (I.getOpcode() == TargetOpcode::LIFETIME_START || 58236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines I.getOpcode() == TargetOpcode::LIFETIME_END || I.isDebugValue()) 5830a16da445740ca6fcd7a7ca571c1917e77315904Nadav Rotem continue; 5840a16da445740ca6fcd7a7ca571c1917e77315904Nadav Rotem 5850cd19b93017fcaba737b15ea4da39c460feb5670Nadav Rotem // Some intervals are suspicious! In some cases we find address 5860cd19b93017fcaba737b15ea4da39c460feb5670Nadav Rotem // calculations outside of the lifetime zone, but not actual memory 5870cd19b93017fcaba737b15ea4da39c460feb5670Nadav Rotem // read or write. Memory accesses outside of the lifetime zone are a clear 5880cd19b93017fcaba737b15ea4da39c460feb5670Nadav Rotem // violation, but address calculations are okay. This can happen when 5890cd19b93017fcaba737b15ea4da39c460feb5670Nadav Rotem // GEPs are hoisted outside of the lifetime zone. 590faf31d01db913b477b749c9f11f18a9471c0a672Nadav Rotem // So, in here we only check instructions which can read or write memory. 59136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (!I.mayLoad() && !I.mayStore()) 5920cd19b93017fcaba737b15ea4da39c460feb5670Nadav Rotem continue; 5930cd19b93017fcaba737b15ea4da39c460feb5670Nadav Rotem 5940a16da445740ca6fcd7a7ca571c1917e77315904Nadav Rotem // Check all of the machine operands. 59536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines for (const MachineOperand &MO : I.operands()) { 5960a16da445740ca6fcd7a7ca571c1917e77315904Nadav Rotem if (!MO.isFI()) 5970a16da445740ca6fcd7a7ca571c1917e77315904Nadav Rotem continue; 5980a16da445740ca6fcd7a7ca571c1917e77315904Nadav Rotem 5990a16da445740ca6fcd7a7ca571c1917e77315904Nadav Rotem int Slot = MO.getIndex(); 6000a16da445740ca6fcd7a7ca571c1917e77315904Nadav Rotem 6010a16da445740ca6fcd7a7ca571c1917e77315904Nadav Rotem if (Slot<0) 6020a16da445740ca6fcd7a7ca571c1917e77315904Nadav Rotem continue; 6030a16da445740ca6fcd7a7ca571c1917e77315904Nadav Rotem 6040a16da445740ca6fcd7a7ca571c1917e77315904Nadav Rotem if (Intervals[Slot]->empty()) 6050a16da445740ca6fcd7a7ca571c1917e77315904Nadav Rotem continue; 6060a16da445740ca6fcd7a7ca571c1917e77315904Nadav Rotem 6070a16da445740ca6fcd7a7ca571c1917e77315904Nadav Rotem // Check that the used slot is inside the calculated lifetime range. 6080a16da445740ca6fcd7a7ca571c1917e77315904Nadav Rotem // If it is not, warn about it and invalidate the range. 60936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines LiveInterval *Interval = &*Intervals[Slot]; 61036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines SlotIndex Index = Indexes->getInstructionIndex(&I); 6110a16da445740ca6fcd7a7ca571c1917e77315904Nadav Rotem if (Interval->find(Index) == Interval->end()) { 61236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Interval->clear(); 6130a16da445740ca6fcd7a7ca571c1917e77315904Nadav Rotem DEBUG(dbgs()<<"Invalidating range #"<<Slot<<"\n"); 614d76f6eadc8c8511e1c5cd089a8a54e429c19aa60Nadav Rotem EscapedAllocas++; 6150a16da445740ca6fcd7a7ca571c1917e77315904Nadav Rotem } 6160a16da445740ca6fcd7a7ca571c1917e77315904Nadav Rotem } 6170a16da445740ca6fcd7a7ca571c1917e77315904Nadav Rotem } 6180a16da445740ca6fcd7a7ca571c1917e77315904Nadav Rotem} 6190a16da445740ca6fcd7a7ca571c1917e77315904Nadav Rotem 620c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotemvoid StackColoring::expungeSlotMap(DenseMap<int, int> &SlotRemap, 621c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem unsigned NumSlots) { 622c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem // Expunge slot remap map. 623c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem for (unsigned i=0; i < NumSlots; ++i) { 624c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem // If we are remapping i 625c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem if (SlotRemap.count(i)) { 626c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem int Target = SlotRemap[i]; 627c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem // As long as our target is mapped to something else, follow it. 628c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem while (SlotRemap.count(Target)) { 629c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem Target = SlotRemap[Target]; 630c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem SlotRemap[i] = Target; 631c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem } 632c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem } 633c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem } 634c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem} 635c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 636c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotembool StackColoring::runOnMachineFunction(MachineFunction &Func) { 63736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (skipOptnoneFunction(*Func.getFunction())) 63836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return false; 63936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 640c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem DEBUG(dbgs() << "********** Stack Coloring **********\n" 641c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem << "********** Function: " 6425177b3a8c48adec2acf284fcb8e00775a705a7e2Roman Divacky << ((const Value*)Func.getFunction())->getName() << '\n'); 643c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem MF = &Func; 644c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem MFI = MF->getFrameInfo(); 645c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem Indexes = &getAnalysis<SlotIndexes>(); 64636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines SP = &getAnalysis<StackProtector>(); 647c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem BlockLiveness.clear(); 648c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem BasicBlocks.clear(); 649c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem BasicBlockNumbering.clear(); 650c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem Markers.clear(); 651c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem Intervals.clear(); 652c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem VNInfoAllocator.Reset(); 653c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 654c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem unsigned NumSlots = MFI->getObjectIndexEnd(); 655c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 656c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem // If there are no stack slots then there are no markers to remove. 657c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem if (!NumSlots) 658c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem return false; 659c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 660c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem SmallVector<int, 8> SortedSlots; 661c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 662c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem SortedSlots.reserve(NumSlots); 663c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem Intervals.reserve(NumSlots); 664c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 665c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem unsigned NumMarkers = collectMarkers(NumSlots); 666c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 667c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem unsigned TotalSize = 0; 668c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem DEBUG(dbgs()<<"Found "<<NumMarkers<<" markers and "<<NumSlots<<" slots\n"); 669c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem DEBUG(dbgs()<<"Slot structure:\n"); 670c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 671c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem for (int i=0; i < MFI->getObjectIndexEnd(); ++i) { 672c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem DEBUG(dbgs()<<"Slot #"<<i<<" - "<<MFI->getObjectSize(i)<<" bytes.\n"); 673c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem TotalSize += MFI->getObjectSize(i); 674c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem } 675c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 676c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem DEBUG(dbgs()<<"Total Stack size: "<<TotalSize<<" bytes\n\n"); 677c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 678c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem // Don't continue because there are not enough lifetime markers, or the 6790cd19b93017fcaba737b15ea4da39c460feb5670Nadav Rotem // stack is too small, or we are told not to optimize the slots. 680c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem if (NumMarkers < 2 || TotalSize < 16 || DisableColoring) { 681c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem DEBUG(dbgs()<<"Will not try to merge slots.\n"); 682c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem return removeAllMarkers(); 683c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem } 684c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 685c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem for (unsigned i=0; i < NumSlots; ++i) { 68636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines std::unique_ptr<LiveInterval> LI(new LiveInterval(i, 0)); 687c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem LI->getNextValue(Indexes->getZeroIndex(), VNInfoAllocator); 68836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Intervals.push_back(std::move(LI)); 689c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem SortedSlots.push_back(i); 690c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem } 691c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 692c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem // Calculate the liveness of each block. 693c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem calculateLocalLiveness(); 694c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 695c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem // Propagate the liveness information. 696c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem calculateLiveIntervals(NumSlots); 697c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 698d76f6eadc8c8511e1c5cd089a8a54e429c19aa60Nadav Rotem // Search for allocas which are used outside of the declared lifetime 699d76f6eadc8c8511e1c5cd089a8a54e429c19aa60Nadav Rotem // markers. 70018e2c290940b67c9dc1196e3c2234e7a20f60ae4Nadav Rotem if (ProtectFromEscapedAllocas) 701d76f6eadc8c8511e1c5cd089a8a54e429c19aa60Nadav Rotem removeInvalidSlotRanges(); 7020a16da445740ca6fcd7a7ca571c1917e77315904Nadav Rotem 703c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem // Maps old slots to new slots. 704c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem DenseMap<int, int> SlotRemap; 705c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem unsigned RemovedSlots = 0; 706c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem unsigned ReducedSize = 0; 707c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 708c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem // Do not bother looking at empty intervals. 709c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem for (unsigned I = 0; I < NumSlots; ++I) { 710c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem if (Intervals[SortedSlots[I]]->empty()) 711c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem SortedSlots[I] = -1; 712c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem } 713c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 714c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem // This is a simple greedy algorithm for merging allocas. First, sort the 715c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem // slots, placing the largest slots first. Next, perform an n^2 scan and look 716c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem // for disjoint slots. When you find disjoint slots, merge the samller one 717c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem // into the bigger one and update the live interval. Remove the small alloca 718c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem // and continue. 719c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 720c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem // Sort the slots according to their size. Place unused slots at the end. 721f38aa4272c2fcebae4ad10b21ea29874d0edef80Ulrich Weigand // Use stable sort to guarantee deterministic code generation. 722f38aa4272c2fcebae4ad10b21ea29874d0edef80Ulrich Weigand std::stable_sort(SortedSlots.begin(), SortedSlots.end(), 72336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines [this](int LHS, int RHS) { 72436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // We use -1 to denote a uninteresting slot. Place these slots at the end. 72536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (LHS == -1) return false; 72636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (RHS == -1) return true; 72736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // Sort according to size. 72836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return MFI->getObjectSize(LHS) > MFI->getObjectSize(RHS); 72936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines }); 730c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 73157d76078ae8ecd16b995cc6a9f9bc57bdde4a20eEric Christopher bool Changed = true; 73257d76078ae8ecd16b995cc6a9f9bc57bdde4a20eEric Christopher while (Changed) { 73357d76078ae8ecd16b995cc6a9f9bc57bdde4a20eEric Christopher Changed = false; 734c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem for (unsigned I = 0; I < NumSlots; ++I) { 735c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem if (SortedSlots[I] == -1) 736c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem continue; 737c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 738a7de8a61dfae69885203137f3c712ab3d0cd75a4Nadav Rotem for (unsigned J=I+1; J < NumSlots; ++J) { 739c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem if (SortedSlots[J] == -1) 740c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem continue; 741c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 742c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem int FirstSlot = SortedSlots[I]; 743c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem int SecondSlot = SortedSlots[J]; 74436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines LiveInterval *First = &*Intervals[FirstSlot]; 74536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines LiveInterval *Second = &*Intervals[SecondSlot]; 746c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem assert (!First->empty() && !Second->empty() && "Found an empty range"); 747c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 748c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem // Merge disjoint slots. 749c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem if (!First->overlaps(*Second)) { 75057d76078ae8ecd16b995cc6a9f9bc57bdde4a20eEric Christopher Changed = true; 751331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun First->MergeSegmentsInAsValue(*Second, First->getValNumInfo(0)); 752c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem SlotRemap[SecondSlot] = FirstSlot; 753c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem SortedSlots[J] = -1; 7549438d1e3514ab8801e9c488d9723241af7f4dc91Nadav Rotem DEBUG(dbgs()<<"Merging #"<<FirstSlot<<" and slots #"<< 7559438d1e3514ab8801e9c488d9723241af7f4dc91Nadav Rotem SecondSlot<<" together.\n"); 756c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem unsigned MaxAlignment = std::max(MFI->getObjectAlignment(FirstSlot), 757c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem MFI->getObjectAlignment(SecondSlot)); 758c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 759c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem assert(MFI->getObjectSize(FirstSlot) >= 760c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem MFI->getObjectSize(SecondSlot) && 761c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem "Merging a small object into a larger one"); 762c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 763c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem RemovedSlots+=1; 764c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem ReducedSize += MFI->getObjectSize(SecondSlot); 765c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem MFI->setObjectAlignment(FirstSlot, MaxAlignment); 766c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem MFI->RemoveStackObject(SecondSlot); 767c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem } 768c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem } 769c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem } 770c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem }// While changed. 771c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 772c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem // Record statistics. 773c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem StackSpaceSaved += ReducedSize; 774c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem StackSlotMerged += RemovedSlots; 775c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem DEBUG(dbgs()<<"Merge "<<RemovedSlots<<" slots. Saved "<< 776c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem ReducedSize<<" bytes\n"); 777c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 778c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem // Scan the entire function and update all machine operands that use frame 779c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem // indices to use the remapped frame index. 780c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem expungeSlotMap(SlotRemap, NumSlots); 781c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem remapInstructions(SlotRemap); 782c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 783c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem return removeAllMarkers(); 784c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem} 785