diff options
Diffstat (limited to 'include/llvm')
26 files changed, 376 insertions, 218 deletions
diff --git a/include/llvm/Analysis/CaptureTracking.h b/include/llvm/Analysis/CaptureTracking.h index b3390f4..4461564 100644 --- a/include/llvm/Analysis/CaptureTracking.h +++ b/include/llvm/Analysis/CaptureTracking.h @@ -14,9 +14,14 @@ #ifndef LLVM_ANALYSIS_CAPTURETRACKING_H #define LLVM_ANALYSIS_CAPTURETRACKING_H -namespace llvm { - class Value; +#include "llvm/Constants.h" +#include "llvm/Instructions.h" +#include "llvm/Analysis/AliasAnalysis.h" +#include "llvm/ADT/SmallSet.h" +#include "llvm/ADT/SmallVector.h" +#include "llvm/Support/CallSite.h" +namespace llvm { /// PointerMayBeCaptured - Return true if this pointer value may be captured /// by the enclosing function (which is required to exist). This routine can /// be expensive, so consider caching the results. The boolean ReturnCaptures @@ -28,6 +33,132 @@ namespace llvm { bool ReturnCaptures, bool StoreCaptures); + /// PointerMayBeCaptured - Visit the value and the values derived from it and + /// find values which appear to be capturing the pointer value. This feeds + /// results into and is controlled by the templated CaptureTracker object: + /// + /// struct YourCaptureTracker { + /// /// tooManyUses - The depth of traversal has breached a limit. + /// /// The tracker should conservatively assume that the value is captured. + /// void tooManyUses(); + /// + /// /// shouldExplore - This is the use of a value derived from the pointer. + /// /// Return false to prune the search (ie., assume that none of its users + /// /// could possibly capture) return false. To search it, return true. + /// /// + /// /// Also, U->getUser() is guaranteed to be an Instruction. + /// bool shouldExplore(Use *U); + /// + /// /// captured - The instruction I captured the pointer. Return true to + /// /// stop the traversal or false to continue looking for more capturing + /// /// instructions. + /// bool captured(Instruction *I); + /// + /// /// Provide your own getters for the state. + /// }; + template<typename CaptureTracker> + void PointerMayBeCaptured(const Value *V, CaptureTracker &Tracker); } // end namespace llvm +template<typename CaptureTracker> +void llvm::PointerMayBeCaptured(const llvm::Value *V, CaptureTracker &Tracker) { + assert(V->getType()->isPointerTy() && "Capture is for pointers only!"); + SmallVector<Use*, 20> Worklist; + SmallSet<Use*, 20> Visited; + int Count = 0; + + for (Value::const_use_iterator UI = V->use_begin(), UE = V->use_end(); + UI != UE; ++UI) { + // If there are lots of uses, conservatively say that the value + // is captured to avoid taking too much compile time. + if (Count++ >= 20) + return Tracker.tooManyUses(); + + Use *U = &UI.getUse(); + if (!Tracker.shouldExplore(U)) continue; + Visited.insert(U); + Worklist.push_back(U); + } + + while (!Worklist.empty()) { + Use *U = Worklist.pop_back_val(); + Instruction *I = cast<Instruction>(U->getUser()); + V = U->get(); + + switch (I->getOpcode()) { + case Instruction::Call: + case Instruction::Invoke: { + CallSite CS(I); + // Not captured if the callee is readonly, doesn't return a copy through + // its return value and doesn't unwind (a readonly function can leak bits + // by throwing an exception or not depending on the input value). + if (CS.onlyReadsMemory() && CS.doesNotThrow() && I->getType()->isVoidTy()) + break; + + // Not captured if only passed via 'nocapture' arguments. Note that + // calling a function pointer does not in itself cause the pointer to + // be captured. This is a subtle point considering that (for example) + // the callee might return its own address. It is analogous to saying + // that loading a value from a pointer does not cause the pointer to be + // captured, even though the loaded value might be the pointer itself + // (think of self-referential objects). + CallSite::arg_iterator B = CS.arg_begin(), E = CS.arg_end(); + for (CallSite::arg_iterator A = B; A != E; ++A) + if (A->get() == V && !CS.paramHasAttr(A - B + 1, Attribute::NoCapture)) + // The parameter is not marked 'nocapture' - captured. + if (Tracker.captured(I)) + return; + break; + } + case Instruction::Load: + // Loading from a pointer does not cause it to be captured. + break; + case Instruction::VAArg: + // "va-arg" from a pointer does not cause it to be captured. + break; + case Instruction::Store: + if (V == I->getOperand(0)) + // Stored the pointer - conservatively assume it may be captured. + if (Tracker.captured(I)) + return; + // Storing to the pointee does not cause the pointer to be captured. + break; + case Instruction::BitCast: + case Instruction::GetElementPtr: + case Instruction::PHI: + case Instruction::Select: + // The original value is not captured via this if the new value isn't. + for (Instruction::use_iterator UI = I->use_begin(), UE = I->use_end(); + UI != UE; ++UI) { + Use *U = &UI.getUse(); + if (Visited.insert(U)) + if (Tracker.shouldExplore(U)) + Worklist.push_back(U); + } + break; + case Instruction::ICmp: + // Don't count comparisons of a no-alias return value against null as + // captures. This allows us to ignore comparisons of malloc results + // with null, for example. + if (isNoAliasCall(V->stripPointerCasts())) + if (ConstantPointerNull *CPN = + dyn_cast<ConstantPointerNull>(I->getOperand(1))) + if (CPN->getType()->getAddressSpace() == 0) + break; + // Otherwise, be conservative. There are crazy ways to capture pointers + // using comparisons. + if (Tracker.captured(I)) + return; + break; + default: + // Something else - be conservative and say it is captured. + if (Tracker.captured(I)) + return; + break; + } + } + + // All uses examined. +} + #endif diff --git a/include/llvm/Analysis/InlineCost.h b/include/llvm/Analysis/InlineCost.h index 36a16e6..fdcd5a8 100644 --- a/include/llvm/Analysis/InlineCost.h +++ b/include/llvm/Analysis/InlineCost.h @@ -14,18 +14,16 @@ #ifndef LLVM_ANALYSIS_INLINECOST_H #define LLVM_ANALYSIS_INLINECOST_H -#include <cassert> -#include <climits> -#include <vector> +#include "llvm/Function.h" #include "llvm/ADT/DenseMap.h" #include "llvm/ADT/ValueMap.h" #include "llvm/Analysis/CodeMetrics.h" +#include <cassert> +#include <climits> +#include <vector> namespace llvm { - class Value; - class Function; - class BasicBlock; class CallSite; template<class PtrType, unsigned SmallSize> class SmallPtrSet; diff --git a/include/llvm/Analysis/MemoryDependenceAnalysis.h b/include/llvm/Analysis/MemoryDependenceAnalysis.h index e18d937..68ce364 100644 --- a/include/llvm/Analysis/MemoryDependenceAnalysis.h +++ b/include/llvm/Analysis/MemoryDependenceAnalysis.h @@ -324,6 +324,7 @@ namespace llvm { /// Current AA implementation, just a cache. AliasAnalysis *AA; TargetData *TD; + DominatorTree *DT; OwningPtr<PredIteratorCache> PredCache; public: MemoryDependenceAnalysis(); @@ -430,6 +431,9 @@ namespace llvm { void RemoveCachedNonLocalPointerDependencies(ValueIsLoadPair P); + AliasAnalysis::ModRefResult + getModRefInfo(const Instruction *Inst, const AliasAnalysis::Location &Loc); + /// verifyRemoved - Verify that the specified instruction does not occur /// in our internal data structures. void verifyRemoved(Instruction *Inst) const; diff --git a/include/llvm/Assembly/AssemblyAnnotationWriter.h b/include/llvm/Assembly/AssemblyAnnotationWriter.h index 6d1bc8c..fa8cdde 100644 --- a/include/llvm/Assembly/AssemblyAnnotationWriter.h +++ b/include/llvm/Assembly/AssemblyAnnotationWriter.h @@ -22,6 +22,7 @@ namespace llvm { class Function; class BasicBlock; class Instruction; +class Value; class raw_ostream; class formatted_raw_ostream; diff --git a/include/llvm/CodeGen/FastISel.h b/include/llvm/CodeGen/FastISel.h index 18202d9..5cb7d8a 100644 --- a/include/llvm/CodeGen/FastISel.h +++ b/include/llvm/CodeGen/FastISel.h @@ -21,9 +21,11 @@ namespace llvm { class AllocaInst; +class Constant; class ConstantFP; class FunctionLoweringInfo; class Instruction; +class LoadInst; class MachineBasicBlock; class MachineConstantPool; class MachineFunction; @@ -36,7 +38,8 @@ class TargetLowering; class TargetMachine; class TargetRegisterClass; class TargetRegisterInfo; -class LoadInst; +class User; +class Value; /// FastISel - This is a fast-path instruction selection class that /// generates poor code and doesn't support illegal types or non-trivial diff --git a/include/llvm/CodeGen/GCStrategy.h b/include/llvm/CodeGen/GCStrategy.h index cd760db..1cbd36a 100644 --- a/include/llvm/CodeGen/GCStrategy.h +++ b/include/llvm/CodeGen/GCStrategy.h @@ -37,6 +37,7 @@ #define LLVM_CODEGEN_GCSTRATEGY_H #include "llvm/CodeGen/GCMetadata.h" +#include "llvm/CodeGen/MachineFunction.h" #include "llvm/Support/Registry.h" #include <string> @@ -68,6 +69,8 @@ namespace llvm { bool CustomReadBarriers; //< Default is to insert loads. bool CustomWriteBarriers; //< Default is to insert stores. bool CustomRoots; //< Default is to pass through to backend. + bool CustomSafePoints; //< Default is to use NeededSafePoints + // to find safe points. bool InitRoots; //< If set, roots are nulled during lowering. bool UsesMetadata; //< If set, backend must emit metadata tables. @@ -87,7 +90,9 @@ namespace llvm { /// needsSafePoitns - True if safe points of any kind are required. By // default, none are recorded. - bool needsSafePoints() const { return NeededSafePoints != 0; } + bool needsSafePoints() const { + return CustomSafePoints || NeededSafePoints != 0; + } /// needsSafePoint(Kind) - True if the given kind of safe point is // required. By default, none are recorded. @@ -109,6 +114,11 @@ namespace llvm { /// can generate a stack map. If true, then // performCustomLowering must delete them. bool customRoots() const { return CustomRoots; } + + /// customSafePoints - By default, the GC analysis will find safe + /// points according to NeededSafePoints. If true, + /// then findCustomSafePoints must create them. + bool customSafePoints() const { return CustomSafePoints; } /// initializeRoots - If set, gcroot intrinsics should initialize their // allocas to null before the first use. This is @@ -135,6 +145,7 @@ namespace llvm { /// which the LLVM IR can be modified. virtual bool initializeCustomLowering(Module &F); virtual bool performCustomLowering(Function &F); + virtual bool findCustomSafePoints(GCFunctionInfo& FI, MachineFunction& MF); }; } diff --git a/include/llvm/CodeGen/LinkAllCodegenComponents.h b/include/llvm/CodeGen/LinkAllCodegenComponents.h index 4490490..a379a30 100644 --- a/include/llvm/CodeGen/LinkAllCodegenComponents.h +++ b/include/llvm/CodeGen/LinkAllCodegenComponents.h @@ -35,7 +35,6 @@ namespace { (void) llvm::createFastRegisterAllocator(); (void) llvm::createBasicRegisterAllocator(); - (void) llvm::createLinearScanRegisterAllocator(); (void) llvm::createGreedyRegisterAllocator(); (void) llvm::createDefaultPBQPRegisterAllocator(); diff --git a/include/llvm/CodeGen/LiveInterval.h b/include/llvm/CodeGen/LiveInterval.h index 2288c1a..f690243 100644 --- a/include/llvm/CodeGen/LiveInterval.h +++ b/include/llvm/CodeGen/LiveInterval.h @@ -381,7 +381,7 @@ namespace llvm { /// point is not contained in the half-open live range. It is usually the /// getDefIndex() slot following its last use. bool killedAt(SlotIndex index) const { - const_iterator r = find(index.getUseIndex()); + const_iterator r = find(index.getRegSlot(true)); return r != end() && r->end == index; } diff --git a/include/llvm/CodeGen/LiveIntervalAnalysis.h b/include/llvm/CodeGen/LiveIntervalAnalysis.h index 8ca58b8..30537b4 100644 --- a/include/llvm/CodeGen/LiveIntervalAnalysis.h +++ b/include/llvm/CodeGen/LiveIntervalAnalysis.h @@ -125,19 +125,6 @@ namespace llvm { return (unsigned)(IntervalPercentage * indexes_->getFunctionSize()); } - /// conflictsWithPhysReg - Returns true if the specified register is used or - /// defined during the duration of the specified interval. Copies to and - /// from li.reg are allowed. This method is only able to analyze simple - /// ranges that stay within a single basic block. Anything else is - /// considered a conflict. - bool conflictsWithPhysReg(const LiveInterval &li, VirtRegMap &vrm, - unsigned reg); - - /// conflictsWithAliasRef - Similar to conflictsWithPhysRegRef except - /// it checks for alias uses and defs. - bool conflictsWithAliasRef(LiveInterval &li, unsigned Reg, - SmallPtrSet<MachineInstr*,32> &JoinedCopies); - // Interval creation LiveInterval &getOrCreateInterval(unsigned reg) { Reg2IntervalMap::iterator I = r2iMap_.find(reg); @@ -271,20 +258,6 @@ namespace llvm { /// print - Implement the dump method. virtual void print(raw_ostream &O, const Module* = 0) const; - /// addIntervalsForSpills - Create new intervals for spilled defs / uses of - /// the given interval. FIXME: It also returns the weight of the spill slot - /// (if any is created) by reference. This is temporary. - std::vector<LiveInterval*> - addIntervalsForSpills(const LiveInterval& i, - const SmallVectorImpl<LiveInterval*> *SpillIs, - const MachineLoopInfo *loopInfo, VirtRegMap& vrm); - - /// spillPhysRegAroundRegDefsUses - Spill the specified physical register - /// around all defs and uses of the specified interval. Return true if it - /// was able to cut its interval. - bool spillPhysRegAroundRegDefsUses(const LiveInterval &li, - unsigned PhysReg, VirtRegMap &vrm); - /// isReMaterializable - Returns true if every definition of MI of every /// val# of the specified interval is re-materializable. Also returns true /// by reference if all of the defs are load instructions. @@ -292,20 +265,6 @@ namespace llvm { const SmallVectorImpl<LiveInterval*> *SpillIs, bool &isLoad); - /// isReMaterializable - Returns true if the definition MI of the specified - /// val# of the specified interval is re-materializable. - bool isReMaterializable(const LiveInterval &li, const VNInfo *ValNo, - MachineInstr *MI); - - /// getRepresentativeReg - Find the largest super register of the specified - /// physical register. - unsigned getRepresentativeReg(unsigned Reg) const; - - /// getNumConflictsWithPhysReg - Return the number of uses and defs of the - /// specified interval that conflicts with the specified physical register. - unsigned getNumConflictsWithPhysReg(const LiveInterval &li, - unsigned PhysReg) const; - /// intervalIsInOneMBB - Returns true if the specified interval is entirely /// within a single basic block. bool intervalIsInOneMBB(const LiveInterval &li) const; @@ -379,84 +338,6 @@ namespace llvm { const SmallVectorImpl<LiveInterval*> *SpillIs, bool &isLoad); - /// tryFoldMemoryOperand - Attempts to fold either a spill / restore from - /// slot / to reg or any rematerialized load into ith operand of specified - /// MI. If it is successul, MI is updated with the newly created MI and - /// returns true. - bool tryFoldMemoryOperand(MachineInstr* &MI, VirtRegMap &vrm, - MachineInstr *DefMI, SlotIndex InstrIdx, - SmallVector<unsigned, 2> &Ops, - bool isSS, int FrameIndex, unsigned Reg); - - /// canFoldMemoryOperand - Return true if the specified load / store - /// folding is possible. - bool canFoldMemoryOperand(MachineInstr *MI, - SmallVector<unsigned, 2> &Ops, - bool ReMatLoadSS) const; - - /// anyKillInMBBAfterIdx - Returns true if there is a kill of the specified - /// VNInfo that's after the specified index but is within the basic block. - bool anyKillInMBBAfterIdx(const LiveInterval &li, const VNInfo *VNI, - MachineBasicBlock *MBB, - SlotIndex Idx) const; - - /// hasAllocatableSuperReg - Return true if the specified physical register - /// has any super register that's allocatable. - bool hasAllocatableSuperReg(unsigned Reg) const; - - /// SRInfo - Spill / restore info. - struct SRInfo { - SlotIndex index; - unsigned vreg; - bool canFold; - SRInfo(SlotIndex i, unsigned vr, bool f) - : index(i), vreg(vr), canFold(f) {} - }; - - bool alsoFoldARestore(int Id, SlotIndex index, unsigned vr, - BitVector &RestoreMBBs, - DenseMap<unsigned,std::vector<SRInfo> >&RestoreIdxes); - void eraseRestoreInfo(int Id, SlotIndex index, unsigned vr, - BitVector &RestoreMBBs, - DenseMap<unsigned,std::vector<SRInfo> >&RestoreIdxes); - - /// handleSpilledImpDefs - Remove IMPLICIT_DEF instructions which are being - /// spilled and create empty intervals for their uses. - void handleSpilledImpDefs(const LiveInterval &li, VirtRegMap &vrm, - const TargetRegisterClass* rc, - std::vector<LiveInterval*> &NewLIs); - - /// rewriteImplicitOps - Rewrite implicit use operands of MI (i.e. uses of - /// interval on to-be re-materialized operands of MI) with new register. - void rewriteImplicitOps(const LiveInterval &li, - MachineInstr *MI, unsigned NewVReg, VirtRegMap &vrm); - - /// rewriteInstructionForSpills, rewriteInstructionsForSpills - Helper - /// functions for addIntervalsForSpills to rewrite uses / defs for the given - /// live range. - bool rewriteInstructionForSpills(const LiveInterval &li, const VNInfo *VNI, - bool TrySplit, SlotIndex index, SlotIndex end, - MachineInstr *MI, MachineInstr *OrigDefMI, MachineInstr *DefMI, - unsigned Slot, int LdSlot, - bool isLoad, bool isLoadSS, bool DefIsReMat, bool CanDelete, - VirtRegMap &vrm, const TargetRegisterClass* rc, - SmallVector<int, 4> &ReMatIds, const MachineLoopInfo *loopInfo, - unsigned &NewVReg, unsigned ImpUse, bool &HasDef, bool &HasUse, - DenseMap<unsigned,unsigned> &MBBVRegsMap, - std::vector<LiveInterval*> &NewLIs); - void rewriteInstructionsForSpills(const LiveInterval &li, bool TrySplit, - LiveInterval::Ranges::const_iterator &I, - MachineInstr *OrigDefMI, MachineInstr *DefMI, unsigned Slot, int LdSlot, - bool isLoad, bool isLoadSS, bool DefIsReMat, bool CanDelete, - VirtRegMap &vrm, const TargetRegisterClass* rc, - SmallVector<int, 4> &ReMatIds, const MachineLoopInfo *loopInfo, - BitVector &SpillMBBs, - DenseMap<unsigned,std::vector<SRInfo> > &SpillIdxes, - BitVector &RestoreMBBs, - DenseMap<unsigned,std::vector<SRInfo> > &RestoreIdxes, - DenseMap<unsigned,unsigned> &MBBVRegsMap, - std::vector<LiveInterval*> &NewLIs); - static LiveInterval* createInterval(unsigned Reg); void printInstrs(raw_ostream &O) const; diff --git a/include/llvm/CodeGen/MachineBlockFrequencyInfo.h b/include/llvm/CodeGen/MachineBlockFrequencyInfo.h index 416d40b..3d9d196 100644 --- a/include/llvm/CodeGen/MachineBlockFrequencyInfo.h +++ b/include/llvm/CodeGen/MachineBlockFrequencyInfo.h @@ -20,6 +20,7 @@ namespace llvm { +class MachineBasicBlock; class MachineBranchProbabilityInfo; template<class BlockT, class FunctionT, class BranchProbInfoT> class BlockFrequencyImpl; @@ -28,7 +29,8 @@ class BlockFrequencyImpl; /// machine basic block frequencies. class MachineBlockFrequencyInfo : public MachineFunctionPass { - BlockFrequencyImpl<MachineBasicBlock, MachineFunction, MachineBranchProbabilityInfo> *MBFI; + BlockFrequencyImpl<MachineBasicBlock, MachineFunction, + MachineBranchProbabilityInfo> *MBFI; public: static char ID; diff --git a/include/llvm/CodeGen/MachineBranchProbabilityInfo.h b/include/llvm/CodeGen/MachineBranchProbabilityInfo.h index d9673e2..e768874 100644 --- a/include/llvm/CodeGen/MachineBranchProbabilityInfo.h +++ b/include/llvm/CodeGen/MachineBranchProbabilityInfo.h @@ -34,9 +34,6 @@ class MachineBranchProbabilityInfo : public ImmutablePass { // weight to just "inherit" the non-zero weight of an adjacent successor. static const uint32_t DEFAULT_WEIGHT = 16; - // Get sum of the block successors' weights. - uint32_t getSumForBlock(MachineBasicBlock *MBB) const; - public: static char ID; @@ -53,15 +50,24 @@ public: // DEFAULT_WEIGHT. uint32_t getEdgeWeight(MachineBasicBlock *Src, MachineBasicBlock *Dst) const; + // Get sum of the block successors' weights, potentially scaling them to fit + // within 32-bits. If scaling is required, sets Scale based on the necessary + // adjustment. Any edge weights used with the sum should be divided by Scale. + uint32_t getSumForBlock(MachineBasicBlock *MBB, uint32_t &Scale) const; + // A 'Hot' edge is an edge which probability is >= 80%. bool isEdgeHot(MachineBasicBlock *Src, MachineBasicBlock *Dst) const; // Return a hot successor for the block BB or null if there isn't one. + // NB: This routine's complexity is linear on the number of successors. MachineBasicBlock *getHotSucc(MachineBasicBlock *MBB) const; // Return a probability as a fraction between 0 (0% probability) and // 1 (100% probability), however the value is never equal to 0, and can be 1 // only iff SRC block has only one successor. + // NB: This routine's complexity is linear on the number of successors of + // Src. Querying sequentially for each successor's probability is a quadratic + // query pattern. BranchProbability getEdgeProbability(MachineBasicBlock *Src, MachineBasicBlock *Dst) const; diff --git a/include/llvm/CodeGen/MachineMemOperand.h b/include/llvm/CodeGen/MachineMemOperand.h index c01597e..eed4a76 100644 --- a/include/llvm/CodeGen/MachineMemOperand.h +++ b/include/llvm/CodeGen/MachineMemOperand.h @@ -22,6 +22,7 @@ namespace llvm { class Value; class FoldingSetNodeID; +class MDNode; class raw_ostream; /// MachinePointerInfo - This class contains a discriminated union of diff --git a/include/llvm/CodeGen/Passes.h b/include/llvm/CodeGen/Passes.h index bf440f4..45b3353 100644 --- a/include/llvm/CodeGen/Passes.h +++ b/include/llvm/CodeGen/Passes.h @@ -118,11 +118,6 @@ namespace llvm { /// FunctionPass *createGreedyRegisterAllocator(); - /// LinearScanRegisterAllocation Pass - This pass implements the linear scan - /// register allocation algorithm, a global register allocator. - /// - FunctionPass *createLinearScanRegisterAllocator(); - /// PBQPRegisterAllocation Pass - This pass implements the Partitioned Boolean /// Quadratic Prograaming (PBQP) based register allocator. /// diff --git a/include/llvm/CodeGen/SelectionDAG.h b/include/llvm/CodeGen/SelectionDAG.h index e4de462..ccd35c4 100644 --- a/include/llvm/CodeGen/SelectionDAG.h +++ b/include/llvm/CodeGen/SelectionDAG.h @@ -112,9 +112,10 @@ public: }; enum CombineLevel { - Unrestricted, // Combine may create illegal operations and illegal types. - NoIllegalTypes, // Combine may create illegal operations but no illegal types. - NoIllegalOperations // Combine may only create legal operations and types. + BeforeLegalizeTypes, + AfterLegalizeTypes, + AfterLegalizeVectorOps, + AfterLegalizeDAG }; class SelectionDAG; diff --git a/include/llvm/CodeGen/SlotIndexes.h b/include/llvm/CodeGen/SlotIndexes.h index 2d98864..cb2baa6 100644 --- a/include/llvm/CodeGen/SlotIndexes.h +++ b/include/llvm/CodeGen/SlotIndexes.h @@ -83,7 +83,29 @@ namespace llvm { friend class SlotIndexes; friend struct DenseMapInfo<SlotIndex>; - enum Slot { LOAD, USE, DEF, STORE, NUM }; + enum Slot { + /// Basic block boundary. Used for live ranges entering and leaving a + /// block without being live in the layout neighbor. Also used as the + /// def slot of PHI-defs. + Slot_Block, + + /// Early-clobber register use/def slot. A live range defined at + /// Slot_EarlyCLobber interferes with normal live ranges killed at + /// Slot_Register. Also used as the kill slot for live ranges tied to an + /// early-clobber def. + Slot_EarlyClobber, + + /// Normal register use/def slot. Normal instructions kill and define + /// register live ranges at this slot. + Slot_Register, + + /// Dead def kill point. Kill slot for a live range that is defined by + /// the same instruction (Slot_Register or Slot_EarlyClobber), but isn't + /// used anywhere. + Slot_Dead, + + Slot_Count + }; PointerIntPair<IndexListEntry*, 2, unsigned> lie; @@ -113,7 +135,7 @@ namespace llvm { enum { /// The default distance between instructions as returned by distance(). /// This may vary as instructions are inserted and removed. - InstrDist = 4*NUM + InstrDist = 4 * Slot_Count }; static inline SlotIndex getEmptyKey() { @@ -191,64 +213,44 @@ namespace llvm { return other.getIndex() - getIndex(); } - /// isLoad - Return true if this is a LOAD slot. - bool isLoad() const { - return getSlot() == LOAD; - } + /// isBlock - Returns true if this is a block boundary slot. + bool isBlock() const { return getSlot() == Slot_Block; } - /// isDef - Return true if this is a DEF slot. - bool isDef() const { - return getSlot() == DEF; - } + /// isEarlyClobber - Returns true if this is an early-clobber slot. + bool isEarlyClobber() const { return getSlot() == Slot_EarlyClobber; } - /// isUse - Return true if this is a USE slot. - bool isUse() const { - return getSlot() == USE; - } + /// isRegister - Returns true if this is a normal register use/def slot. + /// Note that early-clobber slots may also be used for uses and defs. + bool isRegister() const { return getSlot() == Slot_Register; } - /// isStore - Return true if this is a STORE slot. - bool isStore() const { - return getSlot() == STORE; - } + /// isDead - Returns true if this is a dead def kill slot. + bool isDead() const { return getSlot() == Slot_Dead; } /// Returns the base index for associated with this index. The base index - /// is the one associated with the LOAD slot for the instruction pointed to - /// by this index. + /// is the one associated with the Slot_Block slot for the instruction + /// pointed to by this index. SlotIndex getBaseIndex() const { - return getLoadIndex(); + return SlotIndex(&entry(), Slot_Block); } /// Returns the boundary index for associated with this index. The boundary - /// index is the one associated with the LOAD slot for the instruction + /// index is the one associated with the Slot_Block slot for the instruction /// pointed to by this index. SlotIndex getBoundaryIndex() const { - return getStoreIndex(); + return SlotIndex(&entry(), Slot_Dead); } - /// Returns the index of the LOAD slot for the instruction pointed to by - /// this index. - SlotIndex getLoadIndex() const { - return SlotIndex(&entry(), SlotIndex::LOAD); - } - - /// Returns the index of the USE slot for the instruction pointed to by - /// this index. - SlotIndex getUseIndex() const { - return SlotIndex(&entry(), SlotIndex::USE); + /// Returns the register use/def slot in the current instruction for a + /// normal or early-clobber def. + SlotIndex getRegSlot(bool EC = false) const { + return SlotIndex(&entry(), EC ? Slot_EarlyClobber : Slot_Register); } - /// Returns the index of the DEF slot for the instruction pointed to by - /// this index. - SlotIndex getDefIndex() const { - return SlotIndex(&entry(), SlotIndex::DEF); + /// Returns the dead def kill slot for the current instruction. + SlotIndex getDeadSlot() const { + return SlotIndex(&entry(), Slot_Dead); } - /// Returns the index of the STORE slot for the instruction pointed to by - /// this index. - SlotIndex getStoreIndex() const { - return SlotIndex(&entry(), SlotIndex::STORE); - } - /// Returns the next slot in the index list. This could be either the /// next slot for the instruction pointed to by this index or, if this /// index is a STORE, the first slot for the next instruction. @@ -257,8 +259,8 @@ namespace llvm { /// use one of those methods. SlotIndex getNextSlot() const { Slot s = getSlot(); - if (s == SlotIndex::STORE) { - return SlotIndex(entry().getNext(), SlotIndex::LOAD); + if (s == Slot_Dead) { + return SlotIndex(entry().getNext(), Slot_Block); } return SlotIndex(&entry(), s + 1); } @@ -271,14 +273,14 @@ namespace llvm { /// Returns the previous slot in the index list. This could be either the /// previous slot for the instruction pointed to by this index or, if this - /// index is a LOAD, the last slot for the previous instruction. + /// index is a Slot_Block, the last slot for the previous instruction. /// WARNING: This method is considerably more expensive than the methods /// that return specific slots (getUseIndex(), etc). If you can - please /// use one of those methods. SlotIndex getPrevSlot() const { Slot s = getSlot(); - if (s == SlotIndex::LOAD) { - return SlotIndex(entry().getPrev(), SlotIndex::STORE); + if (s == Slot_Block) { + return SlotIndex(entry().getPrev(), Slot_Dead); } return SlotIndex(&entry(), s - 1); } @@ -677,7 +679,7 @@ namespace llvm { if (dist == 0) renumberIndexes(newEntry); - SlotIndex newIndex(newEntry, SlotIndex::LOAD); + SlotIndex newIndex(newEntry, SlotIndex::Slot_Block); mi2iMap.insert(std::make_pair(mi, newIndex)); return newIndex; } @@ -728,8 +730,8 @@ namespace llvm { insert(nextEntry, startEntry); insert(nextEntry, stopEntry); - SlotIndex startIdx(startEntry, SlotIndex::LOAD); - SlotIndex endIdx(nextEntry, SlotIndex::LOAD); + SlotIndex startIdx(startEntry, SlotIndex::Slot_Block); + SlotIndex endIdx(nextEntry, SlotIndex::Slot_Block); assert(unsigned(mbb->getNumber()) == MBBRanges.size() && "Blocks must be added in order"); diff --git a/include/llvm/Constants.h b/include/llvm/Constants.h index 6545a3f..41e451f 100644 --- a/include/llvm/Constants.h +++ b/include/llvm/Constants.h @@ -475,12 +475,6 @@ public: inline VectorType *getType() const { return reinterpret_cast<VectorType*>(Value::getType()); } - - /// This function will return true iff every element in this vector constant - /// is set to all ones. - /// @returns true iff this constant's emements are all set to all ones. - /// @brief Determine if the value is all ones. - bool isAllOnesValue() const; /// getSplatValue - If this is a splat constant, meaning that all of the /// elements have the same value, return that value. Otherwise return NULL. diff --git a/include/llvm/InitializePasses.h b/include/llvm/InitializePasses.h index 47a7779..a917d2e 100644 --- a/include/llvm/InitializePasses.h +++ b/include/llvm/InitializePasses.h @@ -192,7 +192,6 @@ void initializePathProfileVerifierPass(PassRegistry&); void initializeProfileVerifierPassPass(PassRegistry&); void initializePromotePassPass(PassRegistry&); void initializePruneEHPass(PassRegistry&); -void initializeRALinScanPass(PassRegistry&); void initializeReassociatePass(PassRegistry&); void initializeRegToMemPass(PassRegistry&); void initializeRegionInfoPass(PassRegistry&); diff --git a/include/llvm/MC/MCAsmLayout.h b/include/llvm/MC/MCAsmLayout.h index a4585d1..cf79216 100644 --- a/include/llvm/MC/MCAsmLayout.h +++ b/include/llvm/MC/MCAsmLayout.h @@ -10,6 +10,7 @@ #ifndef LLVM_MC_MCASMLAYOUT_H #define LLVM_MC_MCASMLAYOUT_H +#include "llvm/ADT/DenseMap.h" #include "llvm/ADT/SmallVector.h" namespace llvm { diff --git a/include/llvm/Support/Compiler.h b/include/llvm/Support/Compiler.h index cd2e4eb..14b55c1 100644 --- a/include/llvm/Support/Compiler.h +++ b/include/llvm/Support/Compiler.h @@ -62,11 +62,18 @@ #endif #if (__GNUC__ >= 4) +#define LLVM_ATTRIBUTE_WEAK __attribute__((__weak__)) +#else +#define LLVM_ATTRIBUTE_WEAK +#endif + +#if (__GNUC__ >= 4) #define BUILTIN_EXPECT(EXPR, VALUE) __builtin_expect((EXPR), (VALUE)) #else #define BUILTIN_EXPECT(EXPR, VALUE) (EXPR) #endif + // C++ doesn't support 'extern template' of template specializations. GCC does, // but requires __extension__ before it. In the header, use this: // EXTERN_TEMPLATE_INSTANTIATION(class foo<bar>); diff --git a/include/llvm/Support/ManagedStatic.h b/include/llvm/Support/ManagedStatic.h index 53e73ad..4171d1b 100644 --- a/include/llvm/Support/ManagedStatic.h +++ b/include/llvm/Support/ManagedStatic.h @@ -16,6 +16,7 @@ #include "llvm/Support/Atomic.h" #include "llvm/Support/Threading.h" +#include "llvm/Support/Valgrind.h" namespace llvm { @@ -65,6 +66,7 @@ public: void* tmp = Ptr; if (llvm_is_multithreaded()) sys::MemoryFence(); if (!tmp) RegisterManagedStatic(object_creator<C>, object_deleter<C>::call); + TsanHappensAfter(this); return *static_cast<C*>(Ptr); } @@ -72,6 +74,7 @@ public: void* tmp = Ptr; if (llvm_is_multithreaded()) sys::MemoryFence(); if (!tmp) RegisterManagedStatic(object_creator<C>, object_deleter<C>::call); + TsanHappensAfter(this); return static_cast<C*>(Ptr); } @@ -79,6 +82,7 @@ public: void* tmp = Ptr; if (llvm_is_multithreaded()) sys::MemoryFence(); if (!tmp) RegisterManagedStatic(object_creator<C>, object_deleter<C>::call); + TsanHappensAfter(this); return *static_cast<C*>(Ptr); } @@ -86,6 +90,7 @@ public: void* tmp = Ptr; if (llvm_is_multithreaded()) sys::MemoryFence(); if (!tmp) RegisterManagedStatic(object_creator<C>, object_deleter<C>::call); + TsanHappensAfter(this); return static_cast<C*>(Ptr); } diff --git a/include/llvm/Support/Valgrind.h b/include/llvm/Support/Valgrind.h index 7662eaa..9b8d277 100644 --- a/include/llvm/Support/Valgrind.h +++ b/include/llvm/Support/Valgrind.h @@ -16,8 +16,23 @@ #ifndef LLVM_SYSTEM_VALGRIND_H #define LLVM_SYSTEM_VALGRIND_H +#include "llvm/Support/Compiler.h" +#include "llvm/Config/config.h" #include <stddef.h> +#if ENABLE_THREADS != 0 && !defined(NDEBUG) +// tsan (Thread Sanitizer) is a valgrind-based tool that detects these exact +// functions by name. +extern "C" { +LLVM_ATTRIBUTE_WEAK void AnnotateHappensAfter(const char *file, int line, + const volatile void *cv); +LLVM_ATTRIBUTE_WEAK void AnnotateHappensBefore(const char *file, int line, + const volatile void *cv); +LLVM_ATTRIBUTE_WEAK void AnnotateIgnoreWritesBegin(const char *file, int line); +LLVM_ATTRIBUTE_WEAK void AnnotateIgnoreWritesEnd(const char *file, int line); +} +#endif + namespace llvm { namespace sys { // True if Valgrind is controlling this process. @@ -26,6 +41,34 @@ namespace sys { // Discard valgrind's translation of code in the range [Addr .. Addr + Len). // Otherwise valgrind may continue to execute the old version of the code. void ValgrindDiscardTranslations(const void *Addr, size_t Len); + +#if ENABLE_THREADS != 0 && !defined(NDEBUG) + // Thread Sanitizer is a valgrind tool that finds races in code. + // See http://code.google.com/p/data-race-test/wiki/DynamicAnnotations . + + // This marker is used to define a happens-before arc. The race detector will + // infer an arc from the begin to the end when they share the same pointer + // argument. + #define TsanHappensBefore(cv) \ + AnnotateHappensBefore(__FILE__, __LINE__, cv) + + // This marker defines the destination of a happens-before arc. + #define TsanHappensAfter(cv) \ + AnnotateHappensAfter(__FILE__, __LINE__, cv) + + // Ignore any races on writes between here and the next TsanIgnoreWritesEnd. + #define TsanIgnoreWritesBegin() \ + AnnotateIgnoreWritesBegin(__FILE__, __LINE__) + + // Resume checking for racy writes. + #define TsanIgnoreWritesEnd() \ + AnnotateIgnoreWritesEnd(__FILE__, __LINE__) +#else + #define TsanHappensBefore(cv) + #define TsanHappensAfter(cv) + #define TsanIgnoreWritesBegin() + #define TsanIgnoreWritesEnd() +#endif } } diff --git a/include/llvm/Target/TargetInstrInfo.h b/include/llvm/Target/TargetInstrInfo.h index 07f614d..590fc1e 100644 --- a/include/llvm/Target/TargetInstrInfo.h +++ b/include/llvm/Target/TargetInstrInfo.h @@ -718,6 +718,74 @@ public: /// virtual void setExecutionDomain(MachineInstr *MI, unsigned Domain) const {} + + /// getPartialRegUpdateClearance - Returns the preferred minimum clearance + /// before an instruction with an unwanted partial register update. + /// + /// Some instructions only write part of a register, and implicitly need to + /// read the other parts of the register. This may cause unwanted stalls + /// preventing otherwise unrelated instructions from executing in parallel in + /// an out-of-order CPU. + /// + /// For example, the x86 instruction cvtsi2ss writes its result to bits + /// [31:0] of the destination xmm register. Bits [127:32] are unaffected, so + /// the instruction needs to wait for the old value of the register to become + /// available: + /// + /// addps %xmm1, %xmm0 + /// movaps %xmm0, (%rax) + /// cvtsi2ss %rbx, %xmm0 + /// + /// In the code above, the cvtsi2ss instruction needs to wait for the addps + /// instruction before it can issue, even though the high bits of %xmm0 + /// probably aren't needed. + /// + /// This hook returns the preferred clearance before MI, measured in + /// instructions. Other defs of MI's operand OpNum are avoided in the last N + /// instructions before MI. It should only return a positive value for + /// unwanted dependencies. If the old bits of the defined register have + /// useful values, or if MI is determined to otherwise read the dependency, + /// the hook should return 0. + /// + /// The unwanted dependency may be handled by: + /// + /// 1. Allocating the same register for an MI def and use. That makes the + /// unwanted dependency identical to a required dependency. + /// + /// 2. Allocating a register for the def that has no defs in the previous N + /// instructions. + /// + /// 3. Calling breakPartialRegDependency() with the same arguments. This + /// allows the target to insert a dependency breaking instruction. + /// + virtual unsigned + getPartialRegUpdateClearance(const MachineInstr *MI, unsigned OpNum, + const TargetRegisterInfo *TRI) const { + // The default implementation returns 0 for no partial register dependency. + return 0; + } + + /// breakPartialRegDependency - Insert a dependency-breaking instruction + /// before MI to eliminate an unwanted dependency on OpNum. + /// + /// If it wasn't possible to avoid a def in the last N instructions before MI + /// (see getPartialRegUpdateClearance), this hook will be called to break the + /// unwanted dependency. + /// + /// On x86, an xorps instruction can be used as a dependency breaker: + /// + /// addps %xmm1, %xmm0 + /// movaps %xmm0, (%rax) + /// xorps %xmm0, %xmm0 + /// cvtsi2ss %rbx, %xmm0 + /// + /// An <imp-kill> operand should be added to MI if an instruction was + /// inserted. This ties the instructions together in the post-ra scheduler. + /// + virtual void + breakPartialRegDependency(MachineBasicBlock::iterator MI, unsigned OpNum, + const TargetRegisterInfo *TRI) const {} + private: int CallFrameSetupOpcode, CallFrameDestroyOpcode; }; diff --git a/include/llvm/Target/TargetLowering.h b/include/llvm/Target/TargetLowering.h index c81e839..3fe3a38 100644 --- a/include/llvm/Target/TargetLowering.h +++ b/include/llvm/Target/TargetLowering.h @@ -94,7 +94,7 @@ public: Custom // Use the LowerOperation hook to implement custom lowering. }; - /// LegalizeAction - This enum indicates whether a types are legal for a + /// LegalizeTypeAction - This enum indicates whether a types are legal for a /// target, and if not, what action should be used to make them valid. enum LegalizeTypeAction { TypeLegal, // The target natively supports this type. diff --git a/include/llvm/Transforms/Utils/SSAUpdater.h b/include/llvm/Transforms/Utils/SSAUpdater.h index 064e550..4c82149 100644 --- a/include/llvm/Transforms/Utils/SSAUpdater.h +++ b/include/llvm/Transforms/Utils/SSAUpdater.h @@ -14,16 +14,18 @@ #ifndef LLVM_TRANSFORMS_UTILS_SSAUPDATER_H #define LLVM_TRANSFORMS_UTILS_SSAUPDATER_H +#include "llvm/ADT/StringRef.h" + namespace llvm { - class Value; class BasicBlock; - class Use; - class PHINode; + class Instruction; + class LoadInst; template<typename T> class SmallVectorImpl; template<typename T> class SSAUpdaterTraits; - class DbgDeclareInst; - class DIBuilder; - class BumpPtrAllocator; + class PHINode; + class Type; + class Use; + class Value; /// SSAUpdater - This class updates SSA form for a set of values defined in /// multiple blocks. This is used when code duplication or another unstructured @@ -137,12 +139,7 @@ public: /// passed into the run method). Clients should implement this with a more /// efficient version if possible. virtual bool isInstInList(Instruction *I, - const SmallVectorImpl<Instruction*> &Insts) const { - for (unsigned i = 0, e = Insts.size(); i != e; ++i) - if (Insts[i] == I) - return true; - return false; - } + const SmallVectorImpl<Instruction*> &Insts) const; /// doExtraRewritesBeforeFinalDeletion - This hook is invoked after all the /// stores are found and inserted as available values, but diff --git a/include/llvm/Transforms/Utils/SSAUpdaterImpl.h b/include/llvm/Transforms/Utils/SSAUpdaterImpl.h index 5a03d22..15d65bc 100644 --- a/include/llvm/Transforms/Utils/SSAUpdaterImpl.h +++ b/include/llvm/Transforms/Utils/SSAUpdaterImpl.h @@ -15,8 +15,16 @@ #ifndef LLVM_TRANSFORMS_UTILS_SSAUPDATERIMPL_H #define LLVM_TRANSFORMS_UTILS_SSAUPDATERIMPL_H +#include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/SmallVector.h" +#include "llvm/Support/Allocator.h" +#include "llvm/Support/Debug.h" +#include "llvm/Support/ValueHandle.h" + namespace llvm { +class CastInst; +class PHINode; template<typename T> class SSAUpdaterTraits; template<typename UpdaterT> diff --git a/include/llvm/Transforms/Utils/SimplifyIndVar.h b/include/llvm/Transforms/Utils/SimplifyIndVar.h index 524cf5a..21d433a 100644 --- a/include/llvm/Transforms/Utils/SimplifyIndVar.h +++ b/include/llvm/Transforms/Utils/SimplifyIndVar.h @@ -17,17 +17,18 @@ #define LLVM_TRANSFORMS_UTILS_SIMPLIFYINDVAR_H #include "llvm/Support/CommandLine.h" +#include "llvm/Support/ValueHandle.h" namespace llvm { extern cl::opt<bool> DisableIVRewrite; +class CastInst; +class IVUsers; class Loop; -class LoopInfo; -class DominatorTree; -class ScalarEvolution; class LPPassManager; -class IVUsers; +class PHINode; +class ScalarEvolution; /// Interface for visiting interesting IV users that are recognized but not /// simplified by this utility. |