# Instruction Dependency Information in Register Allocation

Hello,

I have added a new function in register allocation stage (AllocationOrder.h) file to define the physical register allocation order. There i require the information of instructions dependency.

For example:

if my register allocationorder is {R_0_Reg_0, R_0_Reg_1, R_0_Reg_2, R_0_Reg_3, R_0_Reg_4, R_0_Reg_5, R_0_Reg_6, R_0_Reg_7, R_1_Reg_0, R_1_Reg_1, R_1_Reg_2, R_1_Reg_3, R_1_Reg_4, R_1_Reg_5, R_1_Reg_6, R_1_Reg_7…R_31_Reg_7}

then my algorithm should do;

if there exists dependency between instruction (or if 2 independent instructions are predecessors of another instruction) then
PhysReg=(PhysReg+1) mod 8.
otherwise, if there is no dependency then PhysReg=(PhysReg+8) mod 32 i.e new R

for now i make this function in AllocationOrder.h

unsigned nextP(int count) {

unsigned Limit = 0;
int Prev;
Prev=Pos;
if (Pos < 0)
{

if (count%2==0) ///here i need the dependency information
{

Pos=Pos+8;
}

else
{
Pos=Pos-7;

}
return Hints.end()[Prev];}
if (!Limit)
Limit = Order.size();
while (Pos < int(Limit)) {
if (count%2==0)
{

Pos=Pos+8;
}

else
{
Pos=Pos-7;

}
unsigned Reg = Order[Prev];
if (!isHint(Reg))
return Reg;
}
return 0;
}

This is called in RegAllocGreedy.cpp.

while ((PhysReg = Order.nextP(count)))
{
count++;
if (!Matrix->checkInterference(VirtReg, PhysReg))
break;

}

so after correct implementation my emitted assembly should be;

1. P_256B_LOAD_DWORD R_0_Reg_0, Pword ptr [rip + b]
2. P_256B_LOAD_DWORD R_1_Reg_0, Pword ptr [rip + b+256] // instruction 2 is not dependent on instruction 1 here increment order index by 8 and get R_1
3. P_256B_LOAD_DWORD R_0_Reg_1, Pword ptr [rip + c] // // instruction 3 is not dependent on instruction 1 but both will contribute towards ADD so here increment order index by 1 and get Reg_1
4. P_256B_LOAD_DWORD R_1_Reg_1, Pword ptr [rip + c+256] // instruction 4 is not dependent on instruction 2 but both will contribute towards ADD so here increment order index by 1 and get Reg_1
5. P_256B_VADD R_0_Reg_0, R_0_Reg_1, R_0_Reg_0 // instruction 5 is dependent on instruction 1 and 3 here keep R_0
6. P_256B_VADD R_1_Reg_0, R_1_Reg_1, R_1_Reg_0 // instruction 6 is dependent on instruction 2 and 4 here keep R_1

I think I am close the only information i need is instruction dependency information such that instruction 1, 3, 5 lie in 1 group while 2, 4, 6 lie in another.

Can someone point me any data structure, function? that i can use at this point to get dependency information??