StackColoring.cpp revision dd29df06fa72de9e370cdd9d8e32ac5437a578c7
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 24c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem#define DEBUG_TYPE "stackcoloring" 25d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/CodeGen/Passes.h" 26c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem#include "llvm/ADT/BitVector.h" 27c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem#include "llvm/ADT/DepthFirstIterator.h" 28c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem#include "llvm/ADT/PostOrderIterator.h" 29c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem#include "llvm/ADT/SetVector.h" 30c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem#include "llvm/ADT/SmallPtrSet.h" 31c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem#include "llvm/ADT/SparseSet.h" 32c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem#include "llvm/ADT/Statistic.h" 33d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/Analysis/Dominators.h" 34d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/Analysis/ValueTracking.h" 35c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem#include "llvm/CodeGen/LiveInterval.h" 36d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/CodeGen/MachineBasicBlock.h" 37c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem#include "llvm/CodeGen/MachineBranchProbabilityInfo.h" 38c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem#include "llvm/CodeGen/MachineDominators.h" 39d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/CodeGen/MachineFrameInfo.h" 40c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem#include "llvm/CodeGen/MachineFunctionPass.h" 41d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/CodeGen/MachineLoopInfo.h" 42d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/CodeGen/MachineMemOperand.h" 43c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem#include "llvm/CodeGen/MachineModuleInfo.h" 44c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem#include "llvm/CodeGen/MachineRegisterInfo.h" 45dd29df06fa72de9e370cdd9d8e32ac5437a578c7Akira Hatanaka#include "llvm/CodeGen/PseudoSourceValue.h" 46c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem#include "llvm/CodeGen/SlotIndexes.h" 47c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem#include "llvm/DebugInfo.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 60c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotemstatic cl::opt<bool> 61c05d30601ced172b55be81bb529df6be91d6ae15Nadav RotemDisableColoring("no-stack-coloring", 62d76f6eadc8c8511e1c5cd089a8a54e429c19aa60Nadav Rotem cl::init(false), cl::Hidden, 63d76f6eadc8c8511e1c5cd089a8a54e429c19aa60Nadav Rotem cl::desc("Disable stack coloring")); 64c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 6518e2c290940b67c9dc1196e3c2234e7a20f60ae4Nadav Rotem/// The user may write code that uses allocas outside of the declared lifetime 6618e2c290940b67c9dc1196e3c2234e7a20f60ae4Nadav Rotem/// zone. This can happen when the user returns a reference to a local 6718e2c290940b67c9dc1196e3c2234e7a20f60ae4Nadav Rotem/// data-structure. We can detect these cases and decide not to optimize the 6818e2c290940b67c9dc1196e3c2234e7a20f60ae4Nadav Rotem/// code. If this flag is enabled, we try to save the user. 69d76f6eadc8c8511e1c5cd089a8a54e429c19aa60Nadav Rotemstatic cl::opt<bool> 7018e2c290940b67c9dc1196e3c2234e7a20f60ae4Nadav RotemProtectFromEscapedAllocas("protect-from-escaped-allocas", 71259021a5621fd3837db79934ea5880cb846bfc44Eric Christopher cl::init(false), cl::Hidden, 72259021a5621fd3837db79934ea5880cb846bfc44Eric Christopher cl::desc("Do not optimize lifetime zones that " 73259021a5621fd3837db79934ea5880cb846bfc44Eric Christopher "are broken")); 74d76f6eadc8c8511e1c5cd089a8a54e429c19aa60Nadav Rotem 75d76f6eadc8c8511e1c5cd089a8a54e429c19aa60Nadav RotemSTATISTIC(NumMarkerSeen, "Number of lifetime markers found."); 76c05d30601ced172b55be81bb529df6be91d6ae15Nadav RotemSTATISTIC(StackSpaceSaved, "Number of bytes saved due to merging slots."); 77c05d30601ced172b55be81bb529df6be91d6ae15Nadav RotemSTATISTIC(StackSlotMerged, "Number of stack slot merged."); 78259021a5621fd3837db79934ea5880cb846bfc44Eric ChristopherSTATISTIC(EscapedAllocas, "Number of allocas that escaped the lifetime region"); 79d76f6eadc8c8511e1c5cd089a8a54e429c19aa60Nadav Rotem 80c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem//===----------------------------------------------------------------------===// 81c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem// StackColoring Pass 82c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem//===----------------------------------------------------------------------===// 83c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 84c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotemnamespace { 85c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem/// StackColoring - A machine pass for merging disjoint stack allocations, 86c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem/// marked by the LIFETIME_START and LIFETIME_END pseudo instructions. 87c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotemclass StackColoring : public MachineFunctionPass { 88c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem MachineFrameInfo *MFI; 89c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem MachineFunction *MF; 90c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 91c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem /// A class representing liveness information for a single basic block. 92c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem /// Each bit in the BitVector represents the liveness property 93c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem /// for a different stack slot. 94c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem struct BlockLifetimeInfo { 95c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem /// Which slots BEGINs in each basic block. 96c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem BitVector Begin; 97c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem /// Which slots ENDs in each basic block. 98c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem BitVector End; 99c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem /// Which slots are marked as LIVE_IN, coming into each basic block. 100c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem BitVector LiveIn; 101c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem /// Which slots are marked as LIVE_OUT, coming out of each basic block. 102c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem BitVector LiveOut; 103c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem }; 104c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 105c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem /// Maps active slots (per bit) for each basic block. 10604fbcb59432c085bb284501dcea9693f435a417bCraig Topper typedef DenseMap<const MachineBasicBlock*, BlockLifetimeInfo> LivenessMap; 10704fbcb59432c085bb284501dcea9693f435a417bCraig Topper LivenessMap BlockLiveness; 108c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 109c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem /// Maps serial numbers to basic blocks. 11004fbcb59432c085bb284501dcea9693f435a417bCraig Topper DenseMap<const MachineBasicBlock*, int> BasicBlocks; 111c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem /// Maps basic blocks to a serial number. 11204fbcb59432c085bb284501dcea9693f435a417bCraig Topper SmallVector<const MachineBasicBlock*, 8> BasicBlockNumbering; 113c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 114c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem /// Maps liveness intervals for each slot. 115c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem SmallVector<LiveInterval*, 16> Intervals; 116c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem /// VNInfo is used for the construction of LiveIntervals. 117c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem VNInfo::Allocator VNInfoAllocator; 118c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem /// SlotIndex analysis object. 119d76f6eadc8c8511e1c5cd089a8a54e429c19aa60Nadav Rotem SlotIndexes *Indexes; 120c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 121c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem /// The list of lifetime markers found. These markers are to be removed 122c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem /// once the coloring is done. 123c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem SmallVector<MachineInstr*, 8> Markers; 124c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 125c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem /// SlotSizeSorter - A Sort utility for arranging stack slots according 126c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem /// to their size. 127c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem struct SlotSizeSorter { 128c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem MachineFrameInfo *MFI; 129c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem SlotSizeSorter(MachineFrameInfo *mfi) : MFI(mfi) { } 130c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem bool operator()(int LHS, int RHS) { 131c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem // We use -1 to denote a uninteresting slot. Place these slots at the end. 132c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem if (LHS == -1) return false; 133c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem if (RHS == -1) return true; 134c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem // Sort according to size. 135c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem return MFI->getObjectSize(LHS) > MFI->getObjectSize(RHS); 136c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem } 137c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem}; 138c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 139c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotempublic: 140c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem static char ID; 141c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem StackColoring() : MachineFunctionPass(ID) { 142c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem initializeStackColoringPass(*PassRegistry::getPassRegistry()); 143c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem } 144c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem void getAnalysisUsage(AnalysisUsage &AU) const; 145c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem bool runOnMachineFunction(MachineFunction &MF); 146c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 147c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotemprivate: 148c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem /// Debug. 149cbc6d797054a2bf2a641031f270d38804a6f2295Craig Topper void dump() const; 150c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 151c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem /// Removes all of the lifetime marker instructions from the function. 152c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem /// \returns true if any markers were removed. 153c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem bool removeAllMarkers(); 154c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 155c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem /// Scan the machine function and find all of the lifetime markers. 156c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem /// Record the findings in the BEGIN and END vectors. 157c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem /// \returns the number of markers found. 158c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem unsigned collectMarkers(unsigned NumSlot); 159c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 160c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem /// Perform the dataflow calculation and calculate the lifetime for each of 161c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem /// the slots, based on the BEGIN/END vectors. Set the LifetimeLIVE_IN and 162c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem /// LifetimeLIVE_OUT maps that represent which stack slots are live coming 163c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem /// in and out blocks. 164c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem void calculateLocalLiveness(); 165c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 166c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem /// Construct the LiveIntervals for the slots. 167c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem void calculateLiveIntervals(unsigned NumSlots); 168c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 169c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem /// Go over the machine function and change instructions which use stack 170c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem /// slots to use the joint slots. 171c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem void remapInstructions(DenseMap<int, int> &SlotRemap); 172c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 1730a16da445740ca6fcd7a7ca571c1917e77315904Nadav Rotem /// The input program may contain intructions which are not inside lifetime 1740a16da445740ca6fcd7a7ca571c1917e77315904Nadav Rotem /// markers. This can happen due to a bug in the compiler or due to a bug in 1750a16da445740ca6fcd7a7ca571c1917e77315904Nadav Rotem /// user code (for example, returning a reference to a local variable). 1760a16da445740ca6fcd7a7ca571c1917e77315904Nadav Rotem /// This procedure checks all of the instructions in the function and 1770a16da445740ca6fcd7a7ca571c1917e77315904Nadav Rotem /// invalidates lifetime ranges which do not contain all of the instructions 1780a16da445740ca6fcd7a7ca571c1917e77315904Nadav Rotem /// which access that frame slot. 1790a16da445740ca6fcd7a7ca571c1917e77315904Nadav Rotem void removeInvalidSlotRanges(); 1800a16da445740ca6fcd7a7ca571c1917e77315904Nadav Rotem 181c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem /// Map entries which point to other entries to their destination. 182c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem /// A->B->C becomes A->C. 183c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem void expungeSlotMap(DenseMap<int, int> &SlotRemap, unsigned NumSlots); 184c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem}; 185c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem} // end anonymous namespace 186c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 187c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotemchar StackColoring::ID = 0; 188c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotemchar &llvm::StackColoringID = StackColoring::ID; 189c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 190c05d30601ced172b55be81bb529df6be91d6ae15Nadav RotemINITIALIZE_PASS_BEGIN(StackColoring, 191c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem "stack-coloring", "Merge disjoint stack slots", false, false) 192c05d30601ced172b55be81bb529df6be91d6ae15Nadav RotemINITIALIZE_PASS_DEPENDENCY(MachineDominatorTree) 193c05d30601ced172b55be81bb529df6be91d6ae15Nadav RotemINITIALIZE_PASS_DEPENDENCY(SlotIndexes) 194c05d30601ced172b55be81bb529df6be91d6ae15Nadav RotemINITIALIZE_PASS_END(StackColoring, 195c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem "stack-coloring", "Merge disjoint stack slots", false, false) 196c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 197c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotemvoid StackColoring::getAnalysisUsage(AnalysisUsage &AU) const { 198c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem AU.addRequired<MachineDominatorTree>(); 199c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem AU.addPreserved<MachineDominatorTree>(); 200c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem AU.addRequired<SlotIndexes>(); 201c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem MachineFunctionPass::getAnalysisUsage(AU); 202c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem} 203c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 204cbc6d797054a2bf2a641031f270d38804a6f2295Craig Toppervoid StackColoring::dump() const { 205c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem for (df_iterator<MachineFunction*> FI = df_begin(MF), FE = df_end(MF); 206c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem FI != FE; ++FI) { 207cbc6d797054a2bf2a641031f270d38804a6f2295Craig Topper DEBUG(dbgs()<<"Inspecting block #"<<BasicBlocks.lookup(*FI)<< 208f1af1feeee0f0ec797410762c006211f9c1e2a0fEdwin Vane " ["<<FI->getName()<<"]\n"); 209cbc6d797054a2bf2a641031f270d38804a6f2295Craig Topper 21004fbcb59432c085bb284501dcea9693f435a417bCraig Topper LivenessMap::const_iterator BI = BlockLiveness.find(*FI); 211cbc6d797054a2bf2a641031f270d38804a6f2295Craig Topper assert(BI != BlockLiveness.end() && "Block not found"); 212cbc6d797054a2bf2a641031f270d38804a6f2295Craig Topper const BlockLifetimeInfo &BlockInfo = BI->second; 213cbc6d797054a2bf2a641031f270d38804a6f2295Craig Topper 214c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem DEBUG(dbgs()<<"BEGIN : {"); 215cbc6d797054a2bf2a641031f270d38804a6f2295Craig Topper for (unsigned i=0; i < BlockInfo.Begin.size(); ++i) 216cbc6d797054a2bf2a641031f270d38804a6f2295Craig Topper DEBUG(dbgs()<<BlockInfo.Begin.test(i)<<" "); 217c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem DEBUG(dbgs()<<"}\n"); 218c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 219c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem DEBUG(dbgs()<<"END : {"); 220cbc6d797054a2bf2a641031f270d38804a6f2295Craig Topper for (unsigned i=0; i < BlockInfo.End.size(); ++i) 221cbc6d797054a2bf2a641031f270d38804a6f2295Craig Topper DEBUG(dbgs()<<BlockInfo.End.test(i)<<" "); 222c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 223c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem DEBUG(dbgs()<<"}\n"); 224c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 225c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem DEBUG(dbgs()<<"LIVE_IN: {"); 226cbc6d797054a2bf2a641031f270d38804a6f2295Craig Topper for (unsigned i=0; i < BlockInfo.LiveIn.size(); ++i) 227cbc6d797054a2bf2a641031f270d38804a6f2295Craig Topper DEBUG(dbgs()<<BlockInfo.LiveIn.test(i)<<" "); 228c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 229c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem DEBUG(dbgs()<<"}\n"); 230c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem DEBUG(dbgs()<<"LIVEOUT: {"); 231cbc6d797054a2bf2a641031f270d38804a6f2295Craig Topper for (unsigned i=0; i < BlockInfo.LiveOut.size(); ++i) 232cbc6d797054a2bf2a641031f270d38804a6f2295Craig Topper DEBUG(dbgs()<<BlockInfo.LiveOut.test(i)<<" "); 233c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem DEBUG(dbgs()<<"}\n"); 234c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem } 235c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem} 236c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 237c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotemunsigned StackColoring::collectMarkers(unsigned NumSlot) { 238c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem unsigned MarkersFound = 0; 239c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem // Scan the function to find all lifetime markers. 240c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem // NOTE: We use the a reverse-post-order iteration to ensure that we obtain a 241c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem // deterministic numbering, and because we'll need a post-order iteration 242c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem // later for solving the liveness dataflow problem. 243c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem for (df_iterator<MachineFunction*> FI = df_begin(MF), FE = df_end(MF); 244c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem FI != FE; ++FI) { 245c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 246c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem // Assign a serial number to this basic block. 2472de0572caec55e3779857cae0bbcd962af2e495dDmitri Gribenko BasicBlocks[*FI] = BasicBlockNumbering.size(); 248c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem BasicBlockNumbering.push_back(*FI); 249c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 250252d798fc302ed78bc4b11e66a2382015a25c6e0Craig Topper // Keep a reference to avoid repeated lookups. 251252d798fc302ed78bc4b11e66a2382015a25c6e0Craig Topper BlockLifetimeInfo &BlockInfo = BlockLiveness[*FI]; 252252d798fc302ed78bc4b11e66a2382015a25c6e0Craig Topper 253252d798fc302ed78bc4b11e66a2382015a25c6e0Craig Topper BlockInfo.Begin.resize(NumSlot); 254252d798fc302ed78bc4b11e66a2382015a25c6e0Craig Topper BlockInfo.End.resize(NumSlot); 255c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 256c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem for (MachineBasicBlock::iterator BI = (*FI)->begin(), BE = (*FI)->end(); 257c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem BI != BE; ++BI) { 258c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 259c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem if (BI->getOpcode() != TargetOpcode::LIFETIME_START && 260c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem BI->getOpcode() != TargetOpcode::LIFETIME_END) 261c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem continue; 262c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 263c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem Markers.push_back(BI); 264c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 265c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem bool IsStart = BI->getOpcode() == TargetOpcode::LIFETIME_START; 266261abf5f4011e5b1e8949d7404190a4f4eaff8d8Craig Topper const MachineOperand &MI = BI->getOperand(0); 267c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem unsigned Slot = MI.getIndex(); 268c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 269c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem MarkersFound++; 270c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 27183ba06afa8503dc97a0aa5ec033022286959956cSebastian Pop const AllocaInst *Allocation = MFI->getObjectAllocation(Slot); 272c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem if (Allocation) { 2730cd19b93017fcaba737b15ea4da39c460feb5670Nadav Rotem DEBUG(dbgs()<<"Found a lifetime marker for slot #"<<Slot<< 2740cd19b93017fcaba737b15ea4da39c460feb5670Nadav Rotem " with allocation: "<< Allocation->getName()<<"\n"); 275c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem } 276c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 277c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem if (IsStart) { 278252d798fc302ed78bc4b11e66a2382015a25c6e0Craig Topper BlockInfo.Begin.set(Slot); 279c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem } else { 280252d798fc302ed78bc4b11e66a2382015a25c6e0Craig Topper if (BlockInfo.Begin.test(Slot)) { 281c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem // Allocas that start and end within a single block are handled 282c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem // specially when computing the LiveIntervals to avoid pessimizing 283c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem // the liveness propagation. 284252d798fc302ed78bc4b11e66a2382015a25c6e0Craig Topper BlockInfo.Begin.reset(Slot); 285c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem } else { 286252d798fc302ed78bc4b11e66a2382015a25c6e0Craig Topper BlockInfo.End.set(Slot); 287c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem } 288c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem } 289c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem } 290c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem } 291c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 292c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem // Update statistics. 293c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem NumMarkerSeen += MarkersFound; 294c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem return MarkersFound; 295c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem} 296c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 297c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotemvoid StackColoring::calculateLocalLiveness() { 298c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem // Perform a standard reverse dataflow computation to solve for 299c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem // global liveness. The BEGIN set here is equivalent to KILL in the standard 300c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem // formulation, and END is equivalent to GEN. The result of this computation 301c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem // is a map from blocks to bitvectors where the bitvectors represent which 302c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem // allocas are live in/out of that block. 30304fbcb59432c085bb284501dcea9693f435a417bCraig Topper SmallPtrSet<const MachineBasicBlock*, 8> BBSet(BasicBlockNumbering.begin(), 30404fbcb59432c085bb284501dcea9693f435a417bCraig Topper BasicBlockNumbering.end()); 305c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem unsigned NumSSMIters = 0; 306c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem bool changed = true; 307c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem while (changed) { 308c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem changed = false; 309c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem ++NumSSMIters; 310c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 31104fbcb59432c085bb284501dcea9693f435a417bCraig Topper SmallPtrSet<const MachineBasicBlock*, 8> NextBBSet; 312c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 31304fbcb59432c085bb284501dcea9693f435a417bCraig Topper for (SmallVector<const MachineBasicBlock*, 8>::iterator 314c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem PI = BasicBlockNumbering.begin(), PE = BasicBlockNumbering.end(); 315c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem PI != PE; ++PI) { 316c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 31704fbcb59432c085bb284501dcea9693f435a417bCraig Topper const MachineBasicBlock *BB = *PI; 318c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem if (!BBSet.count(BB)) continue; 319c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 320cede03886712e18b697f9ec91311d4a8df60c734Craig Topper // Use an iterator to avoid repeated lookups. 32104fbcb59432c085bb284501dcea9693f435a417bCraig Topper LivenessMap::iterator BI = BlockLiveness.find(BB); 322cede03886712e18b697f9ec91311d4a8df60c734Craig Topper assert(BI != BlockLiveness.end() && "Block not found"); 323cede03886712e18b697f9ec91311d4a8df60c734Craig Topper BlockLifetimeInfo &BlockInfo = BI->second; 324cede03886712e18b697f9ec91311d4a8df60c734Craig Topper 325c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem BitVector LocalLiveIn; 326c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem BitVector LocalLiveOut; 327c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 328c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem // Forward propagation from begins to ends. 329cede03886712e18b697f9ec91311d4a8df60c734Craig Topper for (MachineBasicBlock::const_pred_iterator PI = BB->pred_begin(), 330cede03886712e18b697f9ec91311d4a8df60c734Craig Topper PE = BB->pred_end(); PI != PE; ++PI) { 33104fbcb59432c085bb284501dcea9693f435a417bCraig Topper LivenessMap::const_iterator I = BlockLiveness.find(*PI); 332cede03886712e18b697f9ec91311d4a8df60c734Craig Topper assert(I != BlockLiveness.end() && "Predecessor not found"); 333cede03886712e18b697f9ec91311d4a8df60c734Craig Topper LocalLiveIn |= I->second.LiveOut; 334cede03886712e18b697f9ec91311d4a8df60c734Craig Topper } 335cede03886712e18b697f9ec91311d4a8df60c734Craig Topper LocalLiveIn |= BlockInfo.End; 336cede03886712e18b697f9ec91311d4a8df60c734Craig Topper LocalLiveIn.reset(BlockInfo.Begin); 337c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 338c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem // Reverse propagation from ends to begins. 339cede03886712e18b697f9ec91311d4a8df60c734Craig Topper for (MachineBasicBlock::const_succ_iterator SI = BB->succ_begin(), 340cede03886712e18b697f9ec91311d4a8df60c734Craig Topper SE = BB->succ_end(); SI != SE; ++SI) { 34104fbcb59432c085bb284501dcea9693f435a417bCraig Topper LivenessMap::const_iterator I = BlockLiveness.find(*SI); 342cede03886712e18b697f9ec91311d4a8df60c734Craig Topper assert(I != BlockLiveness.end() && "Successor not found"); 343cede03886712e18b697f9ec91311d4a8df60c734Craig Topper LocalLiveOut |= I->second.LiveIn; 344cede03886712e18b697f9ec91311d4a8df60c734Craig Topper } 345cede03886712e18b697f9ec91311d4a8df60c734Craig Topper LocalLiveOut |= BlockInfo.Begin; 346cede03886712e18b697f9ec91311d4a8df60c734Craig Topper LocalLiveOut.reset(BlockInfo.End); 347c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 348c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem LocalLiveIn |= LocalLiveOut; 349c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem LocalLiveOut |= LocalLiveIn; 350c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 351c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem // After adopting the live bits, we need to turn-off the bits which 352c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem // are de-activated in this block. 353cede03886712e18b697f9ec91311d4a8df60c734Craig Topper LocalLiveOut.reset(BlockInfo.End); 354cede03886712e18b697f9ec91311d4a8df60c734Craig Topper LocalLiveIn.reset(BlockInfo.Begin); 355c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 3566165dba25f3374ce340b420ab9a360623c26fdc3Nadav Rotem // If we have both BEGIN and END markers in the same basic block then 3576165dba25f3374ce340b420ab9a360623c26fdc3Nadav Rotem // we know that the BEGIN marker comes after the END, because we already 3586165dba25f3374ce340b420ab9a360623c26fdc3Nadav Rotem // handle the case where the BEGIN comes before the END when collecting 3596165dba25f3374ce340b420ab9a360623c26fdc3Nadav Rotem // the markers (and building the BEGIN/END vectore). 3606165dba25f3374ce340b420ab9a360623c26fdc3Nadav Rotem // Want to enable the LIVE_IN and LIVE_OUT of slots that have both 3616165dba25f3374ce340b420ab9a360623c26fdc3Nadav Rotem // BEGIN and END because it means that the value lives before and after 3626165dba25f3374ce340b420ab9a360623c26fdc3Nadav Rotem // this basic block. 363cede03886712e18b697f9ec91311d4a8df60c734Craig Topper BitVector LocalEndBegin = BlockInfo.End; 364cede03886712e18b697f9ec91311d4a8df60c734Craig Topper LocalEndBegin &= BlockInfo.Begin; 3656165dba25f3374ce340b420ab9a360623c26fdc3Nadav Rotem LocalLiveIn |= LocalEndBegin; 3666165dba25f3374ce340b420ab9a360623c26fdc3Nadav Rotem LocalLiveOut |= LocalEndBegin; 3676165dba25f3374ce340b420ab9a360623c26fdc3Nadav Rotem 368cede03886712e18b697f9ec91311d4a8df60c734Craig Topper if (LocalLiveIn.test(BlockInfo.LiveIn)) { 369c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem changed = true; 370cede03886712e18b697f9ec91311d4a8df60c734Craig Topper BlockInfo.LiveIn |= LocalLiveIn; 371c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 37204fbcb59432c085bb284501dcea9693f435a417bCraig Topper for (MachineBasicBlock::const_pred_iterator PI = BB->pred_begin(), 373c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem PE = BB->pred_end(); PI != PE; ++PI) 374c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem NextBBSet.insert(*PI); 375c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem } 376c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 377cede03886712e18b697f9ec91311d4a8df60c734Craig Topper if (LocalLiveOut.test(BlockInfo.LiveOut)) { 378c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem changed = true; 379cede03886712e18b697f9ec91311d4a8df60c734Craig Topper BlockInfo.LiveOut |= LocalLiveOut; 380c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 38104fbcb59432c085bb284501dcea9693f435a417bCraig Topper for (MachineBasicBlock::const_succ_iterator SI = BB->succ_begin(), 382c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem SE = BB->succ_end(); SI != SE; ++SI) 383c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem NextBBSet.insert(*SI); 384c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem } 385c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem } 386c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 387c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem BBSet = NextBBSet; 388c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem }// while changed. 389c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem} 390c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 391c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotemvoid StackColoring::calculateLiveIntervals(unsigned NumSlots) { 392c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem SmallVector<SlotIndex, 16> Starts; 393c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem SmallVector<SlotIndex, 16> Finishes; 394c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 395c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem // For each block, find which slots are active within this block 396c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem // and update the live intervals. 397c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem for (MachineFunction::iterator MBB = MF->begin(), MBBe = MF->end(); 398c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem MBB != MBBe; ++MBB) { 399c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem Starts.clear(); 400c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem Starts.resize(NumSlots); 401c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem Finishes.clear(); 402c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem Finishes.resize(NumSlots); 403c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 404e47feeb823ebf496e82db6a666d4c0fbaeb158b4Nadav Rotem // Create the interval for the basic blocks with lifetime markers in them. 405261abf5f4011e5b1e8949d7404190a4f4eaff8d8Craig Topper for (SmallVectorImpl<MachineInstr*>::const_iterator it = Markers.begin(), 406c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem e = Markers.end(); it != e; ++it) { 407261abf5f4011e5b1e8949d7404190a4f4eaff8d8Craig Topper const MachineInstr *MI = *it; 408e47feeb823ebf496e82db6a666d4c0fbaeb158b4Nadav Rotem if (MI->getParent() != MBB) 409e47feeb823ebf496e82db6a666d4c0fbaeb158b4Nadav Rotem continue; 410e47feeb823ebf496e82db6a666d4c0fbaeb158b4Nadav Rotem 411c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem assert((MI->getOpcode() == TargetOpcode::LIFETIME_START || 412c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem MI->getOpcode() == TargetOpcode::LIFETIME_END) && 413c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem "Invalid Lifetime marker"); 414c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 415e47feeb823ebf496e82db6a666d4c0fbaeb158b4Nadav Rotem bool IsStart = MI->getOpcode() == TargetOpcode::LIFETIME_START; 416261abf5f4011e5b1e8949d7404190a4f4eaff8d8Craig Topper const MachineOperand &Mo = MI->getOperand(0); 417e47feeb823ebf496e82db6a666d4c0fbaeb158b4Nadav Rotem int Slot = Mo.getIndex(); 418e47feeb823ebf496e82db6a666d4c0fbaeb158b4Nadav Rotem assert(Slot >= 0 && "Invalid slot"); 419e47feeb823ebf496e82db6a666d4c0fbaeb158b4Nadav Rotem 420e47feeb823ebf496e82db6a666d4c0fbaeb158b4Nadav Rotem SlotIndex ThisIndex = Indexes->getInstructionIndex(MI); 421e47feeb823ebf496e82db6a666d4c0fbaeb158b4Nadav Rotem 422e47feeb823ebf496e82db6a666d4c0fbaeb158b4Nadav Rotem if (IsStart) { 423e47feeb823ebf496e82db6a666d4c0fbaeb158b4Nadav Rotem if (!Starts[Slot].isValid() || Starts[Slot] > ThisIndex) 424e47feeb823ebf496e82db6a666d4c0fbaeb158b4Nadav Rotem Starts[Slot] = ThisIndex; 425e47feeb823ebf496e82db6a666d4c0fbaeb158b4Nadav Rotem } else { 426e47feeb823ebf496e82db6a666d4c0fbaeb158b4Nadav Rotem if (!Finishes[Slot].isValid() || Finishes[Slot] < ThisIndex) 427e47feeb823ebf496e82db6a666d4c0fbaeb158b4Nadav Rotem Finishes[Slot] = ThisIndex; 428e47feeb823ebf496e82db6a666d4c0fbaeb158b4Nadav Rotem } 429e47feeb823ebf496e82db6a666d4c0fbaeb158b4Nadav Rotem } 430e47feeb823ebf496e82db6a666d4c0fbaeb158b4Nadav Rotem 431e47feeb823ebf496e82db6a666d4c0fbaeb158b4Nadav Rotem // Create the interval of the blocks that we previously found to be 'alive'. 432e47feeb823ebf496e82db6a666d4c0fbaeb158b4Nadav Rotem BitVector Alive = BlockLiveness[MBB].LiveIn; 433e47feeb823ebf496e82db6a666d4c0fbaeb158b4Nadav Rotem Alive |= BlockLiveness[MBB].LiveOut; 434e47feeb823ebf496e82db6a666d4c0fbaeb158b4Nadav Rotem 435e47feeb823ebf496e82db6a666d4c0fbaeb158b4Nadav Rotem if (Alive.any()) { 436e47feeb823ebf496e82db6a666d4c0fbaeb158b4Nadav Rotem for (int pos = Alive.find_first(); pos != -1; 437e47feeb823ebf496e82db6a666d4c0fbaeb158b4Nadav Rotem pos = Alive.find_next(pos)) { 438e47feeb823ebf496e82db6a666d4c0fbaeb158b4Nadav Rotem if (!Starts[pos].isValid()) 439e47feeb823ebf496e82db6a666d4c0fbaeb158b4Nadav Rotem Starts[pos] = Indexes->getMBBStartIdx(MBB); 440e47feeb823ebf496e82db6a666d4c0fbaeb158b4Nadav Rotem if (!Finishes[pos].isValid()) 441e47feeb823ebf496e82db6a666d4c0fbaeb158b4Nadav Rotem Finishes[pos] = Indexes->getMBBEndIdx(MBB); 442c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem } 443c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem } 444c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 445c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem for (unsigned i = 0; i < NumSlots; ++i) { 446e47feeb823ebf496e82db6a666d4c0fbaeb158b4Nadav Rotem assert(Starts[i].isValid() == Finishes[i].isValid() && "Unmatched range"); 447e47feeb823ebf496e82db6a666d4c0fbaeb158b4Nadav Rotem if (!Starts[i].isValid()) 448c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem continue; 449c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 450c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem assert(Starts[i] && Finishes[i] && "Invalid interval"); 451c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem VNInfo *ValNum = Intervals[i]->getValNumInfo(0); 452c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem SlotIndex S = Starts[i]; 453c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem SlotIndex F = Finishes[i]; 454c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem if (S < F) { 455c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem // We have a single consecutive region. 456c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem Intervals[i]->addRange(LiveRange(S, F, ValNum)); 457c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem } else { 458c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem // We have two non consecutive regions. This happens when 459c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem // LIFETIME_START appears after the LIFETIME_END marker. 460c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem SlotIndex NewStart = Indexes->getMBBStartIdx(MBB); 461c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem SlotIndex NewFin = Indexes->getMBBEndIdx(MBB); 462c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem Intervals[i]->addRange(LiveRange(NewStart, F, ValNum)); 463c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem Intervals[i]->addRange(LiveRange(S, NewFin, ValNum)); 464c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem } 465c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem } 466c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem } 467c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem} 468c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 469c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotembool StackColoring::removeAllMarkers() { 470c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem unsigned Count = 0; 471c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem for (unsigned i = 0; i < Markers.size(); ++i) { 472c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem Markers[i]->eraseFromParent(); 473c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem Count++; 474c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem } 475c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem Markers.clear(); 476c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 477c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem DEBUG(dbgs()<<"Removed "<<Count<<" markers.\n"); 478c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem return Count; 479c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem} 480c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 481c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotemvoid StackColoring::remapInstructions(DenseMap<int, int> &SlotRemap) { 482c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem unsigned FixedInstr = 0; 483c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem unsigned FixedMemOp = 0; 484c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem unsigned FixedDbg = 0; 485c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem MachineModuleInfo *MMI = &MF->getMMI(); 486c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 487c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem // Remap debug information that refers to stack slots. 488c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem MachineModuleInfo::VariableDbgInfoMapTy &VMap = MMI->getVariableDbgInfo(); 489c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem for (MachineModuleInfo::VariableDbgInfoMapTy::iterator VI = VMap.begin(), 490c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem VE = VMap.end(); VI != VE; ++VI) { 491c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem const MDNode *Var = VI->first; 492c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem if (!Var) continue; 493c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem std::pair<unsigned, DebugLoc> &VP = VI->second; 494c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem if (SlotRemap.count(VP.first)) { 495c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem DEBUG(dbgs()<<"Remapping debug info for ["<<Var->getName()<<"].\n"); 496c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem VP.first = SlotRemap[VP.first]; 497c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem FixedDbg++; 498c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem } 499c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem } 500c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 501c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem // Keep a list of *allocas* which need to be remapped. 50283ba06afa8503dc97a0aa5ec033022286959956cSebastian Pop DenseMap<const AllocaInst*, const AllocaInst*> Allocas; 503261abf5f4011e5b1e8949d7404190a4f4eaff8d8Craig Topper for (DenseMap<int, int>::const_iterator it = SlotRemap.begin(), 504c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem e = SlotRemap.end(); it != e; ++it) { 50583ba06afa8503dc97a0aa5ec033022286959956cSebastian Pop const AllocaInst *From = MFI->getObjectAllocation(it->first); 50683ba06afa8503dc97a0aa5ec033022286959956cSebastian Pop const AllocaInst *To = MFI->getObjectAllocation(it->second); 507c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem assert(To && From && "Invalid allocation object"); 508c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem Allocas[From] = To; 509c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem } 510c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 511c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem // Remap all instructions to the new stack slots. 512c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem MachineFunction::iterator BB, BBE; 513c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem MachineBasicBlock::iterator I, IE; 514c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem for (BB = MF->begin(), BBE = MF->end(); BB != BBE; ++BB) 515c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem for (I = BB->begin(), IE = BB->end(); I != IE; ++I) { 516c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 5170aa52ee04e3060974474f6b3f824517c088f07d8Nadav Rotem // Skip lifetime markers. We'll remove them soon. 5180aa52ee04e3060974474f6b3f824517c088f07d8Nadav Rotem if (I->getOpcode() == TargetOpcode::LIFETIME_START || 5190aa52ee04e3060974474f6b3f824517c088f07d8Nadav Rotem I->getOpcode() == TargetOpcode::LIFETIME_END) 5200aa52ee04e3060974474f6b3f824517c088f07d8Nadav Rotem continue; 5210aa52ee04e3060974474f6b3f824517c088f07d8Nadav Rotem 522c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem // Update the MachineMemOperand to use the new alloca. 523c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem for (MachineInstr::mmo_iterator MM = I->memoperands_begin(), 524c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem E = I->memoperands_end(); MM != E; ++MM) { 525c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem MachineMemOperand *MMO = *MM; 526c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 527c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem const Value *V = MMO->getValue(); 528c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 529c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem if (!V) 530c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem continue; 531c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 532dd29df06fa72de9e370cdd9d8e32ac5437a578c7Akira Hatanaka const PseudoSourceValue *PSV = dyn_cast<const PseudoSourceValue>(V); 533dd29df06fa72de9e370cdd9d8e32ac5437a578c7Akira Hatanaka if (PSV && PSV->isConstant(MFI)) 534dd29df06fa72de9e370cdd9d8e32ac5437a578c7Akira Hatanaka continue; 535dd29df06fa72de9e370cdd9d8e32ac5437a578c7Akira Hatanaka 536c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem // Climb up and find the original alloca. 537c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem V = GetUnderlyingObject(V); 538c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem // If we did not find one, or if the one that we found is not in our 539c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem // map, then move on. 54083ba06afa8503dc97a0aa5ec033022286959956cSebastian Pop if (!V || !isa<AllocaInst>(V)) { 54183ba06afa8503dc97a0aa5ec033022286959956cSebastian Pop // Clear mem operand since we don't know for sure that it doesn't 54283ba06afa8503dc97a0aa5ec033022286959956cSebastian Pop // alias a merged alloca. 54383ba06afa8503dc97a0aa5ec033022286959956cSebastian Pop MMO->setValue(0); 54483ba06afa8503dc97a0aa5ec033022286959956cSebastian Pop continue; 54583ba06afa8503dc97a0aa5ec033022286959956cSebastian Pop } 54683ba06afa8503dc97a0aa5ec033022286959956cSebastian Pop const AllocaInst *AI= cast<AllocaInst>(V); 54783ba06afa8503dc97a0aa5ec033022286959956cSebastian Pop if (!Allocas.count(AI)) 548c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem continue; 549c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 55083ba06afa8503dc97a0aa5ec033022286959956cSebastian Pop MMO->setValue(Allocas[AI]); 551c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem FixedMemOp++; 552c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem } 553c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 554c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem // Update all of the machine instruction operands. 555c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem for (unsigned i = 0 ; i < I->getNumOperands(); ++i) { 556c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem MachineOperand &MO = I->getOperand(i); 557c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 558c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem if (!MO.isFI()) 559c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem continue; 560c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem int FromSlot = MO.getIndex(); 561c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 562c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem // Don't touch arguments. 563c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem if (FromSlot<0) 564c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem continue; 565c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 566c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem // Only look at mapped slots. 567c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem if (!SlotRemap.count(FromSlot)) 568c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem continue; 569c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 5708cc14949053ea4fcba34afc68b30137eff408d66Nadav Rotem // In a debug build, check that the instruction that we are modifying is 5718cc14949053ea4fcba34afc68b30137eff408d66Nadav Rotem // inside the expected live range. If the instruction is not inside 5720aa52ee04e3060974474f6b3f824517c088f07d8Nadav Rotem // the calculated range then it means that the alloca usage moved 57318e2c290940b67c9dc1196e3c2234e7a20f60ae4Nadav Rotem // outside of the lifetime markers, or that the user has a bug. 5740cd19b93017fcaba737b15ea4da39c460feb5670Nadav Rotem // NOTE: Alloca address calculations which happen outside the lifetime 5750cd19b93017fcaba737b15ea4da39c460feb5670Nadav Rotem // zone are are okay, despite the fact that we don't have a good way 5760cd19b93017fcaba737b15ea4da39c460feb5670Nadav Rotem // for validating all of the usages of the calculation. 5770aa52ee04e3060974474f6b3f824517c088f07d8Nadav Rotem#ifndef NDEBUG 5780cd19b93017fcaba737b15ea4da39c460feb5670Nadav Rotem bool TouchesMemory = I->mayLoad() || I->mayStore(); 57918e2c290940b67c9dc1196e3c2234e7a20f60ae4Nadav Rotem // If we *don't* protect the user from escaped allocas, don't bother 58018e2c290940b67c9dc1196e3c2234e7a20f60ae4Nadav Rotem // validating the instructions. 58118e2c290940b67c9dc1196e3c2234e7a20f60ae4Nadav Rotem if (!I->isDebugValue() && TouchesMemory && ProtectFromEscapedAllocas) { 5828754bbbe672450689a5bdc8a198af90144e56f31Nadav Rotem SlotIndex Index = Indexes->getInstructionIndex(I); 583d76f6eadc8c8511e1c5cd089a8a54e429c19aa60Nadav Rotem LiveInterval *Interval = Intervals[FromSlot]; 5848754bbbe672450689a5bdc8a198af90144e56f31Nadav Rotem assert(Interval->find(Index) != Interval->end() && 58557d76078ae8ecd16b995cc6a9f9bc57bdde4a20eEric Christopher "Found instruction usage outside of live range."); 5868754bbbe672450689a5bdc8a198af90144e56f31Nadav Rotem } 5870aa52ee04e3060974474f6b3f824517c088f07d8Nadav Rotem#endif 5880aa52ee04e3060974474f6b3f824517c088f07d8Nadav Rotem 589c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem // Fix the machine instructions. 590c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem int ToSlot = SlotRemap[FromSlot]; 591c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem MO.setIndex(ToSlot); 592c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem FixedInstr++; 593c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem } 594c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem } 595c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 596c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem DEBUG(dbgs()<<"Fixed "<<FixedMemOp<<" machine memory operands.\n"); 597c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem DEBUG(dbgs()<<"Fixed "<<FixedDbg<<" debug locations.\n"); 598c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem DEBUG(dbgs()<<"Fixed "<<FixedInstr<<" machine instructions.\n"); 599c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem} 600c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 6010a16da445740ca6fcd7a7ca571c1917e77315904Nadav Rotemvoid StackColoring::removeInvalidSlotRanges() { 602261abf5f4011e5b1e8949d7404190a4f4eaff8d8Craig Topper MachineFunction::const_iterator BB, BBE; 603261abf5f4011e5b1e8949d7404190a4f4eaff8d8Craig Topper MachineBasicBlock::const_iterator I, IE; 6040a16da445740ca6fcd7a7ca571c1917e77315904Nadav Rotem for (BB = MF->begin(), BBE = MF->end(); BB != BBE; ++BB) 6050a16da445740ca6fcd7a7ca571c1917e77315904Nadav Rotem for (I = BB->begin(), IE = BB->end(); I != IE; ++I) { 6060a16da445740ca6fcd7a7ca571c1917e77315904Nadav Rotem 6070a16da445740ca6fcd7a7ca571c1917e77315904Nadav Rotem if (I->getOpcode() == TargetOpcode::LIFETIME_START || 6080a16da445740ca6fcd7a7ca571c1917e77315904Nadav Rotem I->getOpcode() == TargetOpcode::LIFETIME_END || I->isDebugValue()) 6090a16da445740ca6fcd7a7ca571c1917e77315904Nadav Rotem continue; 6100a16da445740ca6fcd7a7ca571c1917e77315904Nadav Rotem 6110cd19b93017fcaba737b15ea4da39c460feb5670Nadav Rotem // Some intervals are suspicious! In some cases we find address 6120cd19b93017fcaba737b15ea4da39c460feb5670Nadav Rotem // calculations outside of the lifetime zone, but not actual memory 6130cd19b93017fcaba737b15ea4da39c460feb5670Nadav Rotem // read or write. Memory accesses outside of the lifetime zone are a clear 6140cd19b93017fcaba737b15ea4da39c460feb5670Nadav Rotem // violation, but address calculations are okay. This can happen when 6150cd19b93017fcaba737b15ea4da39c460feb5670Nadav Rotem // GEPs are hoisted outside of the lifetime zone. 616faf31d01db913b477b749c9f11f18a9471c0a672Nadav Rotem // So, in here we only check instructions which can read or write memory. 6170cd19b93017fcaba737b15ea4da39c460feb5670Nadav Rotem if (!I->mayLoad() && !I->mayStore()) 6180cd19b93017fcaba737b15ea4da39c460feb5670Nadav Rotem continue; 6190cd19b93017fcaba737b15ea4da39c460feb5670Nadav Rotem 6200a16da445740ca6fcd7a7ca571c1917e77315904Nadav Rotem // Check all of the machine operands. 6210a16da445740ca6fcd7a7ca571c1917e77315904Nadav Rotem for (unsigned i = 0 ; i < I->getNumOperands(); ++i) { 622261abf5f4011e5b1e8949d7404190a4f4eaff8d8Craig Topper const MachineOperand &MO = I->getOperand(i); 6230a16da445740ca6fcd7a7ca571c1917e77315904Nadav Rotem 6240a16da445740ca6fcd7a7ca571c1917e77315904Nadav Rotem if (!MO.isFI()) 6250a16da445740ca6fcd7a7ca571c1917e77315904Nadav Rotem continue; 6260a16da445740ca6fcd7a7ca571c1917e77315904Nadav Rotem 6270a16da445740ca6fcd7a7ca571c1917e77315904Nadav Rotem int Slot = MO.getIndex(); 6280a16da445740ca6fcd7a7ca571c1917e77315904Nadav Rotem 6290a16da445740ca6fcd7a7ca571c1917e77315904Nadav Rotem if (Slot<0) 6300a16da445740ca6fcd7a7ca571c1917e77315904Nadav Rotem continue; 6310a16da445740ca6fcd7a7ca571c1917e77315904Nadav Rotem 6320a16da445740ca6fcd7a7ca571c1917e77315904Nadav Rotem if (Intervals[Slot]->empty()) 6330a16da445740ca6fcd7a7ca571c1917e77315904Nadav Rotem continue; 6340a16da445740ca6fcd7a7ca571c1917e77315904Nadav Rotem 6350a16da445740ca6fcd7a7ca571c1917e77315904Nadav Rotem // Check that the used slot is inside the calculated lifetime range. 6360a16da445740ca6fcd7a7ca571c1917e77315904Nadav Rotem // If it is not, warn about it and invalidate the range. 6370a16da445740ca6fcd7a7ca571c1917e77315904Nadav Rotem LiveInterval *Interval = Intervals[Slot]; 6380a16da445740ca6fcd7a7ca571c1917e77315904Nadav Rotem SlotIndex Index = Indexes->getInstructionIndex(I); 6390a16da445740ca6fcd7a7ca571c1917e77315904Nadav Rotem if (Interval->find(Index) == Interval->end()) { 6400a16da445740ca6fcd7a7ca571c1917e77315904Nadav Rotem Intervals[Slot]->clear(); 6410a16da445740ca6fcd7a7ca571c1917e77315904Nadav Rotem DEBUG(dbgs()<<"Invalidating range #"<<Slot<<"\n"); 642d76f6eadc8c8511e1c5cd089a8a54e429c19aa60Nadav Rotem EscapedAllocas++; 6430a16da445740ca6fcd7a7ca571c1917e77315904Nadav Rotem } 6440a16da445740ca6fcd7a7ca571c1917e77315904Nadav Rotem } 6450a16da445740ca6fcd7a7ca571c1917e77315904Nadav Rotem } 6460a16da445740ca6fcd7a7ca571c1917e77315904Nadav Rotem} 6470a16da445740ca6fcd7a7ca571c1917e77315904Nadav Rotem 648c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotemvoid StackColoring::expungeSlotMap(DenseMap<int, int> &SlotRemap, 649c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem unsigned NumSlots) { 650c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem // Expunge slot remap map. 651c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem for (unsigned i=0; i < NumSlots; ++i) { 652c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem // If we are remapping i 653c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem if (SlotRemap.count(i)) { 654c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem int Target = SlotRemap[i]; 655c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem // As long as our target is mapped to something else, follow it. 656c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem while (SlotRemap.count(Target)) { 657c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem Target = SlotRemap[Target]; 658c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem SlotRemap[i] = Target; 659c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem } 660c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem } 661c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem } 662c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem} 663c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 664c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotembool StackColoring::runOnMachineFunction(MachineFunction &Func) { 665c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem DEBUG(dbgs() << "********** Stack Coloring **********\n" 666c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem << "********** Function: " 6675177b3a8c48adec2acf284fcb8e00775a705a7e2Roman Divacky << ((const Value*)Func.getFunction())->getName() << '\n'); 668c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem MF = &Func; 669c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem MFI = MF->getFrameInfo(); 670c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem Indexes = &getAnalysis<SlotIndexes>(); 671c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem BlockLiveness.clear(); 672c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem BasicBlocks.clear(); 673c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem BasicBlockNumbering.clear(); 674c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem Markers.clear(); 675c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem Intervals.clear(); 676c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem VNInfoAllocator.Reset(); 677c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 678c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem unsigned NumSlots = MFI->getObjectIndexEnd(); 679c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 680c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem // If there are no stack slots then there are no markers to remove. 681c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem if (!NumSlots) 682c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem return false; 683c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 684c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem SmallVector<int, 8> SortedSlots; 685c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 686c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem SortedSlots.reserve(NumSlots); 687c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem Intervals.reserve(NumSlots); 688c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 689c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem unsigned NumMarkers = collectMarkers(NumSlots); 690c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 691c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem unsigned TotalSize = 0; 692c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem DEBUG(dbgs()<<"Found "<<NumMarkers<<" markers and "<<NumSlots<<" slots\n"); 693c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem DEBUG(dbgs()<<"Slot structure:\n"); 694c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 695c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem for (int i=0; i < MFI->getObjectIndexEnd(); ++i) { 696c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem DEBUG(dbgs()<<"Slot #"<<i<<" - "<<MFI->getObjectSize(i)<<" bytes.\n"); 697c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem TotalSize += MFI->getObjectSize(i); 698c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem } 699c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 700c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem DEBUG(dbgs()<<"Total Stack size: "<<TotalSize<<" bytes\n\n"); 701c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 702c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem // Don't continue because there are not enough lifetime markers, or the 7030cd19b93017fcaba737b15ea4da39c460feb5670Nadav Rotem // stack is too small, or we are told not to optimize the slots. 704c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem if (NumMarkers < 2 || TotalSize < 16 || DisableColoring) { 705c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem DEBUG(dbgs()<<"Will not try to merge slots.\n"); 706c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem return removeAllMarkers(); 707c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem } 708c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 709c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem for (unsigned i=0; i < NumSlots; ++i) { 710c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem LiveInterval *LI = new LiveInterval(i, 0); 711c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem Intervals.push_back(LI); 712c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem LI->getNextValue(Indexes->getZeroIndex(), VNInfoAllocator); 713c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem SortedSlots.push_back(i); 714c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem } 715c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 716c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem // Calculate the liveness of each block. 717c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem calculateLocalLiveness(); 718c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 719c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem // Propagate the liveness information. 720c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem calculateLiveIntervals(NumSlots); 721c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 722d76f6eadc8c8511e1c5cd089a8a54e429c19aa60Nadav Rotem // Search for allocas which are used outside of the declared lifetime 723d76f6eadc8c8511e1c5cd089a8a54e429c19aa60Nadav Rotem // markers. 72418e2c290940b67c9dc1196e3c2234e7a20f60ae4Nadav Rotem if (ProtectFromEscapedAllocas) 725d76f6eadc8c8511e1c5cd089a8a54e429c19aa60Nadav Rotem removeInvalidSlotRanges(); 7260a16da445740ca6fcd7a7ca571c1917e77315904Nadav Rotem 727c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem // Maps old slots to new slots. 728c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem DenseMap<int, int> SlotRemap; 729c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem unsigned RemovedSlots = 0; 730c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem unsigned ReducedSize = 0; 731c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 732c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem // Do not bother looking at empty intervals. 733c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem for (unsigned I = 0; I < NumSlots; ++I) { 734c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem if (Intervals[SortedSlots[I]]->empty()) 735c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem SortedSlots[I] = -1; 736c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem } 737c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 738c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem // This is a simple greedy algorithm for merging allocas. First, sort the 739c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem // slots, placing the largest slots first. Next, perform an n^2 scan and look 740c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem // for disjoint slots. When you find disjoint slots, merge the samller one 741c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem // into the bigger one and update the live interval. Remove the small alloca 742c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem // and continue. 743c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 744c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem // Sort the slots according to their size. Place unused slots at the end. 745f38aa4272c2fcebae4ad10b21ea29874d0edef80Ulrich Weigand // Use stable sort to guarantee deterministic code generation. 746f38aa4272c2fcebae4ad10b21ea29874d0edef80Ulrich Weigand std::stable_sort(SortedSlots.begin(), SortedSlots.end(), 747f38aa4272c2fcebae4ad10b21ea29874d0edef80Ulrich Weigand SlotSizeSorter(MFI)); 748c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 74957d76078ae8ecd16b995cc6a9f9bc57bdde4a20eEric Christopher bool Changed = true; 75057d76078ae8ecd16b995cc6a9f9bc57bdde4a20eEric Christopher while (Changed) { 75157d76078ae8ecd16b995cc6a9f9bc57bdde4a20eEric Christopher Changed = false; 752c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem for (unsigned I = 0; I < NumSlots; ++I) { 753c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem if (SortedSlots[I] == -1) 754c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem continue; 755c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 756a7de8a61dfae69885203137f3c712ab3d0cd75a4Nadav Rotem for (unsigned J=I+1; J < NumSlots; ++J) { 757c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem if (SortedSlots[J] == -1) 758c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem continue; 759c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 760c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem int FirstSlot = SortedSlots[I]; 761c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem int SecondSlot = SortedSlots[J]; 762c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem LiveInterval *First = Intervals[FirstSlot]; 763c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem LiveInterval *Second = Intervals[SecondSlot]; 764c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem assert (!First->empty() && !Second->empty() && "Found an empty range"); 765c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 766c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem // Merge disjoint slots. 767c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem if (!First->overlaps(*Second)) { 76857d76078ae8ecd16b995cc6a9f9bc57bdde4a20eEric Christopher Changed = true; 769c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem First->MergeRangesInAsValue(*Second, First->getValNumInfo(0)); 770c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem SlotRemap[SecondSlot] = FirstSlot; 771c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem SortedSlots[J] = -1; 7729438d1e3514ab8801e9c488d9723241af7f4dc91Nadav Rotem DEBUG(dbgs()<<"Merging #"<<FirstSlot<<" and slots #"<< 7739438d1e3514ab8801e9c488d9723241af7f4dc91Nadav Rotem SecondSlot<<" together.\n"); 774c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem unsigned MaxAlignment = std::max(MFI->getObjectAlignment(FirstSlot), 775c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem MFI->getObjectAlignment(SecondSlot)); 776c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 777c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem assert(MFI->getObjectSize(FirstSlot) >= 778c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem MFI->getObjectSize(SecondSlot) && 779c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem "Merging a small object into a larger one"); 780c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 781c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem RemovedSlots+=1; 782c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem ReducedSize += MFI->getObjectSize(SecondSlot); 783c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem MFI->setObjectAlignment(FirstSlot, MaxAlignment); 784c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem MFI->RemoveStackObject(SecondSlot); 785c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem } 786c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem } 787c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem } 788c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem }// While changed. 789c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 790c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem // Record statistics. 791c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem StackSpaceSaved += ReducedSize; 792c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem StackSlotMerged += RemovedSlots; 793c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem DEBUG(dbgs()<<"Merge "<<RemovedSlots<<" slots. Saved "<< 794c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem ReducedSize<<" bytes\n"); 795c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 796c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem // Scan the entire function and update all machine operands that use frame 797c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem // indices to use the remapped frame index. 798c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem expungeSlotMap(SlotRemap, NumSlots); 799c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem remapInstructions(SlotRemap); 800c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 801c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem // Release the intervals. 802c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem for (unsigned I = 0; I < NumSlots; ++I) { 803c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem delete Intervals[I]; 804c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem } 805c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem 806c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem return removeAllMarkers(); 807c05d30601ced172b55be81bb529df6be91d6ae15Nadav Rotem} 808