X-Git-Url: http://plrg.eecs.uci.edu/git/?p=oota-llvm.git;a=blobdiff_plain;f=include%2Fllvm%2FCodeGen%2FScheduleDAG.h;h=bda9dbd51fff7aca91b4aea5e18bfc3ff50f2014;hp=58a3a9cb59143014af4a5461698954995236c738;hb=20a42bb20d43b80e322c95dd99b64a5a4566fe08;hpb=e5dafc395656645c3a5d90e7c1b55477800f2ab1 diff --git a/include/llvm/CodeGen/ScheduleDAG.h b/include/llvm/CodeGen/ScheduleDAG.h index 58a3a9cb591..bda9dbd51ff 100644 --- a/include/llvm/CodeGen/ScheduleDAG.h +++ b/include/llvm/CodeGen/ScheduleDAG.h @@ -8,28 +8,29 @@ //===----------------------------------------------------------------------===// // // This file implements the ScheduleDAG class, which is used as the common -// base class for instruction schedulers. +// base class for instruction schedulers. This encapsulates the scheduling DAG, +// which is shared between SelectionDAG and MachineInstr scheduling. // //===----------------------------------------------------------------------===// #ifndef LLVM_CODEGEN_SCHEDULEDAG_H #define LLVM_CODEGEN_SCHEDULEDAG_H -#include "llvm/CodeGen/MachineBasicBlock.h" -#include "llvm/Target/TargetLowering.h" -#include "llvm/ADT/DenseMap.h" #include "llvm/ADT/BitVector.h" #include "llvm/ADT/GraphTraits.h" -#include "llvm/ADT/SmallVector.h" #include "llvm/ADT/PointerIntPair.h" +#include "llvm/ADT/SmallVector.h" +#include "llvm/Analysis/AliasAnalysis.h" +#include "llvm/CodeGen/MachineInstr.h" +#include "llvm/Target/TargetLowering.h" namespace llvm { - class AliasAnalysis; class SUnit; class MachineConstantPool; class MachineFunction; class MachineRegisterInfo; class MachineInstr; + struct MCSchedClassDesc; class TargetRegisterInfo; class ScheduleDAG; class SDNode; @@ -51,6 +52,24 @@ namespace llvm { Order ///< Any other ordering dependency. }; + // Strong dependencies must be respected by the scheduler. Artificial + // dependencies may be removed only if they are redundant with another + // strong depedence. + // + // Weak dependencies may be violated by the scheduling strategy, but only if + // the strategy can prove it is correct to do so. + // + // Strong OrderKinds must occur before "Weak". + // Weak OrderKinds must occur after "Weak". + enum OrderKind { + Barrier, ///< An unknown scheduling barrier. + MayAliasMem, ///< Nonvolatile load/Store instructions that may alias. + MustAliasMem, ///< Nonvolatile load/Store instructions that must alias. + Artificial, ///< Arbitrary strong DAG edge (no real dependence). + Weak, ///< Arbitrary weak DAG edge. + Cluster ///< Weak DAG edge linking a chain of clustered instrs. + }; + private: /// Dep - A pointer to the depending/depended-on SUnit, and an enum /// indicating the kind of the dependency. @@ -64,20 +83,7 @@ namespace llvm { unsigned Reg; /// Order - Additional information about Order dependencies. - struct { - /// isNormalMemory - True if both sides of the dependence - /// access memory in non-volatile and fully modeled ways. - bool isNormalMemory : 1; - - /// isMustAlias - True if both sides of the dependence are known to - /// access the same memory. - bool isMustAlias : 1; - - /// isArtificial - True if this is an artificial dependency, meaning - /// it is not necessary for program correctness, and may be safely - /// deleted if necessary. - bool isArtificial : 1; - } Order; + unsigned OrdKind; // enum OrderKind } Contents; /// Latency - The time associated with this edge. Often this is just @@ -89,48 +95,37 @@ namespace llvm { /// SDep - Construct a null SDep. This is only for use by container /// classes which require default constructors. SUnits may not /// have null SDep edges. - SDep() : Dep(0, Data) {} + SDep() : Dep(nullptr, Data) {} /// SDep - Construct an SDep with the specified values. - SDep(SUnit *S, Kind kind, unsigned latency = 1, unsigned Reg = 0, - bool isNormalMemory = false, bool isMustAlias = false, - bool isArtificial = false) - : Dep(S, kind), Contents(), Latency(latency) { + SDep(SUnit *S, Kind kind, unsigned Reg) + : Dep(S, kind), Contents() { switch (kind) { + default: + llvm_unreachable("Reg given for non-register dependence!"); case Anti: case Output: assert(Reg != 0 && "SDep::Anti and SDep::Output must use a non-zero Reg!"); - // fall through - case Data: - assert(!isMustAlias && "isMustAlias only applies with SDep::Order!"); - assert(!isArtificial && "isArtificial only applies with SDep::Order!"); Contents.Reg = Reg; + Latency = 0; break; - case Order: - assert(Reg == 0 && "Reg given for non-register dependence!"); - Contents.Order.isNormalMemory = isNormalMemory; - Contents.Order.isMustAlias = isMustAlias; - Contents.Order.isArtificial = isArtificial; + case Data: + Contents.Reg = Reg; + Latency = 1; break; } } + SDep(SUnit *S, OrderKind kind) + : Dep(S, Order), Contents(), Latency(0) { + Contents.OrdKind = kind; + } + + /// Return true if the specified SDep is equivalent except for latency. + bool overlaps(const SDep &Other) const; bool operator==(const SDep &Other) const { - if (Dep != Other.Dep || Latency != Other.Latency) return false; - switch (Dep.getInt()) { - case Data: - case Anti: - case Output: - return Contents.Reg == Other.Contents.Reg; - case Order: - return Contents.Order.isNormalMemory == - Other.Contents.Order.isNormalMemory && - Contents.Order.isMustAlias == Other.Contents.Order.isMustAlias && - Contents.Order.isArtificial == Other.Contents.Order.isArtificial; - } - assert(0 && "Invalid dependency kind!"); - return false; + return overlaps(Other) && Latency == Other.Latency; } bool operator!=(const SDep &Other) const { @@ -151,19 +146,13 @@ namespace llvm { } //// getSUnit - Return the SUnit to which this edge points. - SUnit *getSUnit() const { - return Dep.getPointer(); - } + SUnit *getSUnit() const; //// setSUnit - Assign the SUnit to which this edge points. - void setSUnit(SUnit *SU) { - Dep.setPointer(SU); - } + void setSUnit(SUnit *SU); /// getKind - Return an enum value representing the kind of the dependence. - Kind getKind() const { - return Dep.getInt(); - } + Kind getKind() const; /// isCtrl - Shorthand for getKind() != SDep::Data. bool isCtrl() const { @@ -174,20 +163,47 @@ namespace llvm { /// memory accesses where both sides of the dependence access memory /// in non-volatile and fully modeled ways. bool isNormalMemory() const { - return getKind() == Order && Contents.Order.isNormalMemory; + return getKind() == Order && (Contents.OrdKind == MayAliasMem + || Contents.OrdKind == MustAliasMem); + } + + /// isBarrier - Test if this is an Order dependence that is marked + /// as a barrier. + bool isBarrier() const { + return getKind() == Order && Contents.OrdKind == Barrier; + } + + /// isNormalMemoryOrBarrier - Test if this is could be any kind of memory + /// dependence. + bool isNormalMemoryOrBarrier() const { + return (isNormalMemory() || isBarrier()); } /// isMustAlias - Test if this is an Order dependence that is marked /// as "must alias", meaning that the SUnits at either end of the edge /// have a memory dependence on a known memory location. bool isMustAlias() const { - return getKind() == Order && Contents.Order.isMustAlias; + return getKind() == Order && Contents.OrdKind == MustAliasMem; + } + + /// isWeak - Test if this a weak dependence. Weak dependencies are + /// considered DAG edges for height computation and other heuristics, but do + /// not force ordering. Breaking a weak edge may require the scheduler to + /// compensate, for example by inserting a copy. + bool isWeak() const { + return getKind() == Order && Contents.OrdKind >= Weak; } /// isArtificial - Test if this is an Order dependence that is marked /// as "artificial", meaning it isn't necessary for correctness. bool isArtificial() const { - return getKind() == Order && Contents.Order.isArtificial; + return getKind() == Order && Contents.OrdKind == Artificial; + } + + /// isCluster - Test if this is an Order dependence that is marked + /// as "cluster", meaning it is artificial and wants to be adjacent. + bool isCluster() const { + return getKind() == Order && Contents.OrdKind == Cluster; } /// isAssignedRegDep - Test if this is a Data dependence that is @@ -227,20 +243,25 @@ namespace llvm { /// SUnit - Scheduling unit. This is a node in the scheduling DAG. class SUnit { private: + enum : unsigned { BoundaryID = ~0u }; + SDNode *Node; // Representative node. MachineInstr *Instr; // Alternatively, a MachineInstr. public: SUnit *OrigNode; // If not this, the node from which // this node was cloned. + // (SD scheduling only) + + const MCSchedClassDesc *SchedClass; // NULL or resolved SchedClass. // Preds/Succs - The SUnits before/after us in the graph. SmallVector Preds; // All sunit predecessors. SmallVector Succs; // All sunit successors. - typedef SmallVector::iterator pred_iterator; - typedef SmallVector::iterator succ_iterator; - typedef SmallVector::const_iterator const_pred_iterator; - typedef SmallVector::const_iterator const_succ_iterator; + typedef SmallVectorImpl::iterator pred_iterator; + typedef SmallVectorImpl::iterator succ_iterator; + typedef SmallVectorImpl::const_iterator const_pred_iterator; + typedef SmallVectorImpl::const_iterator const_succ_iterator; unsigned NodeNum; // Entry # of node in the node vector. unsigned NodeQueueId; // Queue id of node. @@ -248,6 +269,8 @@ namespace llvm { unsigned NumSuccs; // # of SDep::Data sucss. unsigned NumPredsLeft; // # of preds not scheduled. unsigned NumSuccsLeft; // # of succs not scheduled. + unsigned WeakPredsLeft; // # of weak preds not scheduled. + unsigned WeakSuccsLeft; // # of weak succs not scheduled. unsigned short NumRegDefsLeft; // # of reg defs with no scheduled use. unsigned short Latency; // Node latency. bool isVRegCycle : 1; // May use and def the same vreg. @@ -255,6 +278,7 @@ namespace llvm { bool isCallOp : 1; // Is a function call operand. bool isTwoAddress : 1; // Is a two-address instruction. bool isCommutable : 1; // Is a commutable instruction. + bool hasPhysRegUses : 1; // Has physreg uses. bool hasPhysRegDefs : 1; // Has physreg defs that are being used. bool hasPhysRegClobbers : 1; // Has any physreg defs, used or not. bool isPending : 1; // True once pending. @@ -263,6 +287,8 @@ namespace llvm { bool isScheduleHigh : 1; // True if preferable to schedule high. bool isScheduleLow : 1; // True if preferable to schedule low. bool isCloned : 1; // True if this node has been cloned. + bool isUnbuffered : 1; // Uses an unbuffered resource. + bool hasReservedResource : 1; // Uses a reserved resource. Sched::Preference SchedulingPref; // Scheduling preference. private: @@ -271,49 +297,67 @@ namespace llvm { unsigned Depth; // Node depth. unsigned Height; // Node height. public: + unsigned TopReadyCycle; // Cycle relative to start when node is ready. + unsigned BotReadyCycle; // Cycle relative to end when node is ready. + const TargetRegisterClass *CopyDstRC; // Is a special copy node if not null. const TargetRegisterClass *CopySrcRC; /// SUnit - Construct an SUnit for pre-regalloc scheduling to represent /// an SDNode and any nodes flagged to it. SUnit(SDNode *node, unsigned nodenum) - : Node(node), Instr(0), OrigNode(0), NodeNum(nodenum), - NodeQueueId(0), NumPreds(0), NumSuccs(0), NumPredsLeft(0), - NumSuccsLeft(0), NumRegDefsLeft(0), Latency(0), - isVRegCycle(false), isCall(false), isCallOp(false), isTwoAddress(false), - isCommutable(false), hasPhysRegDefs(false), hasPhysRegClobbers(false), + : Node(node), Instr(nullptr), OrigNode(nullptr), SchedClass(nullptr), + NodeNum(nodenum), NodeQueueId(0), NumPreds(0), NumSuccs(0), + NumPredsLeft(0), NumSuccsLeft(0), WeakPredsLeft(0), WeakSuccsLeft(0), + NumRegDefsLeft(0), Latency(0), isVRegCycle(false), isCall(false), + isCallOp(false), isTwoAddress(false), isCommutable(false), + hasPhysRegUses(false), hasPhysRegDefs(false), hasPhysRegClobbers(false), isPending(false), isAvailable(false), isScheduled(false), isScheduleHigh(false), isScheduleLow(false), isCloned(false), - SchedulingPref(Sched::None), - isDepthCurrent(false), isHeightCurrent(false), Depth(0), Height(0), - CopyDstRC(NULL), CopySrcRC(NULL) {} + isUnbuffered(false), hasReservedResource(false), + SchedulingPref(Sched::None), isDepthCurrent(false), + isHeightCurrent(false), Depth(0), Height(0), TopReadyCycle(0), + BotReadyCycle(0), CopyDstRC(nullptr), CopySrcRC(nullptr) {} /// SUnit - Construct an SUnit for post-regalloc scheduling to represent /// a MachineInstr. SUnit(MachineInstr *instr, unsigned nodenum) - : Node(0), Instr(instr), OrigNode(0), NodeNum(nodenum), - NodeQueueId(0), NumPreds(0), NumSuccs(0), NumPredsLeft(0), - NumSuccsLeft(0), NumRegDefsLeft(0), Latency(0), - isVRegCycle(false), isCall(false), isCallOp(false), isTwoAddress(false), - isCommutable(false), hasPhysRegDefs(false), hasPhysRegClobbers(false), + : Node(nullptr), Instr(instr), OrigNode(nullptr), SchedClass(nullptr), + NodeNum(nodenum), NodeQueueId(0), NumPreds(0), NumSuccs(0), + NumPredsLeft(0), NumSuccsLeft(0), WeakPredsLeft(0), WeakSuccsLeft(0), + NumRegDefsLeft(0), Latency(0), isVRegCycle(false), isCall(false), + isCallOp(false), isTwoAddress(false), isCommutable(false), + hasPhysRegUses(false), hasPhysRegDefs(false), hasPhysRegClobbers(false), isPending(false), isAvailable(false), isScheduled(false), isScheduleHigh(false), isScheduleLow(false), isCloned(false), - SchedulingPref(Sched::None), - isDepthCurrent(false), isHeightCurrent(false), Depth(0), Height(0), - CopyDstRC(NULL), CopySrcRC(NULL) {} + isUnbuffered(false), hasReservedResource(false), + SchedulingPref(Sched::None), isDepthCurrent(false), + isHeightCurrent(false), Depth(0), Height(0), TopReadyCycle(0), + BotReadyCycle(0), CopyDstRC(nullptr), CopySrcRC(nullptr) {} /// SUnit - Construct a placeholder SUnit. SUnit() - : Node(0), Instr(0), OrigNode(0), NodeNum(~0u), - NodeQueueId(0), NumPreds(0), NumSuccs(0), NumPredsLeft(0), - NumSuccsLeft(0), NumRegDefsLeft(0), Latency(0), - isVRegCycle(false), isCall(false), isCallOp(false), isTwoAddress(false), - isCommutable(false), hasPhysRegDefs(false), hasPhysRegClobbers(false), + : Node(nullptr), Instr(nullptr), OrigNode(nullptr), SchedClass(nullptr), + NodeNum(BoundaryID), NodeQueueId(0), NumPreds(0), NumSuccs(0), + NumPredsLeft(0), NumSuccsLeft(0), WeakPredsLeft(0), WeakSuccsLeft(0), + NumRegDefsLeft(0), Latency(0), isVRegCycle(false), isCall(false), + isCallOp(false), isTwoAddress(false), isCommutable(false), + hasPhysRegUses(false), hasPhysRegDefs(false), hasPhysRegClobbers(false), isPending(false), isAvailable(false), isScheduled(false), isScheduleHigh(false), isScheduleLow(false), isCloned(false), - SchedulingPref(Sched::None), - isDepthCurrent(false), isHeightCurrent(false), Depth(0), Height(0), - CopyDstRC(NULL), CopySrcRC(NULL) {} + isUnbuffered(false), hasReservedResource(false), + SchedulingPref(Sched::None), isDepthCurrent(false), + isHeightCurrent(false), Depth(0), Height(0), TopReadyCycle(0), + BotReadyCycle(0), CopyDstRC(nullptr), CopySrcRC(nullptr) {} + + /// \brief Boundary nodes are placeholders for the boundary of the + /// scheduling region. + /// + /// BoundaryNodes can have DAG edges, including Data edges, but they do not + /// correspond to schedulable entities (e.g. instructions) and do not have a + /// valid ID. Consequently, always check for boundary nodes before accessing + /// an assoicative data structure keyed on node ID. + bool isBoundaryNode() const { return NodeNum == BoundaryID; } /// setNode - Assign the representative SDNode for this SUnit. /// This may be used during pre-regalloc scheduling. @@ -350,7 +394,7 @@ namespace llvm { /// addPred - This adds the specified edge as a pred of the current node if /// not already. It also adds the current node as a successor of the /// specified node. - bool addPred(const SDep &D); + bool addPred(const SDep &D, bool Required = true); /// removePred - This removes the specified edge as a pred of the current /// node if it exists. It also removes the current node as a successor of @@ -409,6 +453,17 @@ namespace llvm { return false; } + bool isTopReady() const { + return NumPredsLeft == 0; + } + bool isBottomReady() const { + return NumSuccsLeft == 0; + } + + /// \brief Order this node's predecessor edges such that the critical path + /// edge occurs first. + void biasCriticalPath(); + void dump(const ScheduleDAG *G) const; void dumpAll(const ScheduleDAG *G) const; void print(raw_ostream &O, const ScheduleDAG *G) const; @@ -418,6 +473,30 @@ namespace llvm { void ComputeHeight(); }; + /// Return true if the specified SDep is equivalent except for latency. + inline bool SDep::overlaps(const SDep &Other) const { + if (Dep != Other.Dep) + return false; + switch (Dep.getInt()) { + case Data: + case Anti: + case Output: + return Contents.Reg == Other.Contents.Reg; + case Order: + return Contents.OrdKind == Other.Contents.OrdKind; + } + llvm_unreachable("Invalid dependency kind!"); + } + + //// getSUnit - Return the SUnit to which this edge points. + inline SUnit *SDep::getSUnit() const { return Dep.getPointer(); } + + //// setSUnit - Assign the SUnit to which this edge points. + inline void SDep::setSUnit(SUnit *SU) { Dep.setPointer(SU); } + + /// getKind - Return an enum value representing the kind of the dependence. + inline SDep::Kind SDep::getKind() const { return Dep.getInt(); } + //===--------------------------------------------------------------------===// /// SchedulingPriorityQueue - This interface is used to plug different /// priorities computation algorithms into the list scheduler. It implements @@ -466,13 +545,13 @@ namespace llvm { virtual void dump(ScheduleDAG *) const {} - /// ScheduledNode - As each node is scheduled, this method is invoked. This + /// scheduledNode - As each node is scheduled, this method is invoked. This /// allows the priority function to adjust the priority of related /// unscheduled nodes, for example. /// - virtual void ScheduledNode(SUnit *) {} + virtual void scheduledNode(SUnit *) {} - virtual void UnscheduledNode(SUnit *) {} + virtual void unscheduledNode(SUnit *) {} void setCurCycle(unsigned Cycle) { CurCycle = Cycle; @@ -485,15 +564,11 @@ namespace llvm { class ScheduleDAG { public: - MachineBasicBlock *BB; // The block in which to insert instructions - MachineBasicBlock::iterator InsertPos;// The position to insert instructions const TargetMachine &TM; // Target processor const TargetInstrInfo *TII; // Target instruction information const TargetRegisterInfo *TRI; // Target processor register info MachineFunction &MF; // Machine function MachineRegisterInfo &MRI; // Virtual/real register map - std::vector Sequence; // The schedule. Null SUnit*'s - // represent noop instructions. std::vector SUnits; // The scheduling units. SUnit EntrySU; // Special node for the region entry. SUnit ExitSU; // Special node for the region exit. @@ -508,6 +583,9 @@ namespace llvm { virtual ~ScheduleDAG(); + /// clearDAG - clear the DAG state (between regions). + void clearDAG(); + /// getInstrDesc - Return the MCInstrDesc of this SUnit. /// Return NULL for SDNodes without a machine opcode. const MCInstrDesc *getInstrDesc(const SUnit *SU) const { @@ -518,14 +596,8 @@ namespace llvm { /// viewGraph - Pop up a GraphViz/gv window with the ScheduleDAG rendered /// using 'dot'. /// - void viewGraph(); - - /// EmitSchedule - Insert MachineInstrs into the MachineBasicBlock - /// according to the order specified in Sequence. - /// - virtual MachineBasicBlock *EmitSchedule() = 0; - - void dumpSchedule() const; + virtual void viewGraph(const Twine &Name, const Twine &Title); + virtual void viewGraph(); virtual void dumpNode(const SUnit *SU) const = 0; @@ -533,52 +605,19 @@ namespace llvm { /// of the ScheduleDAG. virtual std::string getGraphNodeLabel(const SUnit *SU) const = 0; + /// getDAGLabel - Return a label for the region of code covered by the DAG. + virtual std::string getDAGName() const = 0; + /// addCustomGraphFeatures - Add custom features for a visualization of /// the ScheduleDAG. virtual void addCustomGraphFeatures(GraphWriter &) const {} #ifndef NDEBUG - /// VerifySchedule - Verify that all SUnits were scheduled and that - /// their state is consistent. - void VerifySchedule(bool isBottomUp); + /// VerifyScheduledDAG - Verify that all SUnits were scheduled and that + /// their state is consistent. Return the number of scheduled SUnits. + unsigned VerifyScheduledDAG(bool isBottomUp); #endif - protected: - /// Run - perform scheduling. - /// - void Run(MachineBasicBlock *bb, MachineBasicBlock::iterator insertPos); - - /// BuildSchedGraph - Build SUnits and set up their Preds and Succs - /// to form the scheduling dependency graph. - /// - virtual void BuildSchedGraph(AliasAnalysis *AA) = 0; - - /// ComputeLatency - Compute node latency. - /// - virtual void ComputeLatency(SUnit *SU) = 0; - - /// ComputeOperandLatency - Override dependence edge latency using - /// operand use/def information - /// - virtual void ComputeOperandLatency(SUnit *, SUnit *, - SDep&) const { } - - /// Schedule - Order nodes according to selected style, filling - /// in the Sequence member. - /// - virtual void Schedule() = 0; - - /// ForceUnitLatencies - Return true if all scheduling edges should be given - /// a latency value of one. The default is to return false; schedulers may - /// override this as needed. - virtual bool ForceUnitLatencies() const { return false; } - - /// EmitNoop - Emit a noop instruction. - /// - void EmitNoop(); - - void EmitPhysRegCopy(SUnit *SU, DenseMap &VRBaseMap); - private: // Return the MCInstrDesc of this SDNode or NULL. const MCInstrDesc *getNodeDesc(const SDNode *Node) const; @@ -596,12 +635,6 @@ namespace llvm { } bool operator!=(const SUnitIterator& x) const { return !operator==(x); } - const SUnitIterator &operator=(const SUnitIterator &I) { - assert(I.Node==Node && "Cannot assign iterators to two different nodes!"); - Operand = I.Operand; - return *this; - } - pointer operator*() const { return Node->Preds[Operand].getSUnit(); } @@ -665,6 +698,7 @@ namespace llvm { class ScheduleDAGTopologicalSort { /// SUnits - A reference to the ScheduleDAG's SUnits. std::vector &SUnits; + SUnit *ExitSU; /// Index2Node - Maps topological index to the node number. std::vector Index2Node; @@ -686,7 +720,7 @@ namespace llvm { void Allocate(int n, int index); public: - explicit ScheduleDAGTopologicalSort(std::vector &SUnits); + ScheduleDAGTopologicalSort(std::vector &SUnits, SUnit *ExitSU); /// InitDAGTopologicalSorting - create the initial topological /// ordering from the DAG to be scheduled. @@ -695,9 +729,8 @@ namespace llvm { /// IsReachable - Checks if SU is reachable from TargetSU. bool IsReachable(const SUnit *SU, const SUnit *TargetSU); - /// WillCreateCycle - Returns true if adding an edge from SU to TargetSU - /// will create a cycle. - bool WillCreateCycle(SUnit *SU, SUnit *TargetSU); + /// WillCreateCycle - Return true if addPred(TargetSU, SU) creates a cycle. + bool WillCreateCycle(SUnit *TargetSU, SUnit *SU); /// AddPred - Updates the topological ordering to accommodate an edge /// to be added from SUnit X to SUnit Y.