Transformations + Re-definitions in SSA + SSAUpdater

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
2 messages Options
Reply | Threaded
Open this post in threaded view
|

Transformations + Re-definitions in SSA + SSAUpdater

Manish Gupta-8
Hi All,

I am transforming  LLVM IR, by adding new BasicBlocks. The new BasicBlock is called based on some condition say %re.def.bb. If the condition %re.def.bb is true I re-define some SSA variables in new BB re.def.true ow. I copy old instructions in re.def.false basicblock. The SSA needs to be updated for all the successors basic-blocks because of this re-definitions. I am tying to explain the problem using an example below:

ORIGINAL BB:
if.end:                       ; preds = %if.end, %entry
  %j.07 = phi i32 [ %shl, %if.end ], [ 1, %entry ]
  %i.06 = phi i32 [ %inc, %if.end ], [ 0, %entry ]
  %shl = shl i32 %j.07, 1
  %inc = add nsw i32 %i.06, 1
  %cmp = icmp sgt i32 %i.06, 13
  %cmp1 = icmp sgt i32 %shl, %val
  %or.cond = or i1 %cmp, %cmp1
  br i1 %or.cond, label %for.end, label %if.end

%for.end: ...

TRANSFORMATION:
if.end:                                           ; preds = %orig.brInst, %entry
  %j.07 = phi i32 [ %shl, %orig.brInst ], [ 1, %entry ]
  %i.06 = phi i32 [ %inc, %orig.brInst ], [ 0, %entry ]
  ....
  %re.def.bb = call i1 (i32, i64, ...)* isCond()
  br i1 %re.def.bb, label %re.def.true, label %re.def.false

re.def.false:
  //Original Code                                    ; preds = %if.end
  %shl = shl i32 %j.07, 1
  %inc = add nsw i32 %i.06, 1
  %cmp = icmp sgt i32 %i.06, 13
  %cmp1 = icmp sgt i32 %shl, %val
  %or.cond = or i1 %cmp, %cmp1
  br label %orig.brInst

re.def.true:
 //re-definitions of %shl, %inc, %or.cond
 %4 = re-define(%shl)
 %5 = re-define(%inc)
 %6 = re-define(%or.cond)

orig.brInst: 
  br i1 %or.cond, label %for.end, label %if.end

%for.end: ...

Code added by transformation is highlight above. And it is not complete yet as phinodes are messed up. orig.brInst is the branch instruction from original code. Which should execute the same way to keep the control flow intact. To fix the phinodes I used SSAUpdater class the same way instruction sink function is using it in LICM. 

SSAUpdate: 
Step 1: Add one more def. available for %inc, %shl and %or.cond  using AddAvailableValue in new BasicBlock myCond.true.
SSA.AddAvailableValue(myCond.true:, NewDefInsts(shl));
SSA.AddAvailableValue(myCond.true:, NewDefInsts(inc));
SSA.AddAvailableValue(myCond.true:, NewDefInsts(or.cond));

Step 2: Rewrite all the uses of %shl, %inc %or.cond to update SSA/PHI nodes
SSA.RewriteUseAfterInsertions(Users of %shl);
SSA.RewriteUseAfterInsertions(Users of %inc);
SSA.RewriteUseAfterInsertions(Users of %or.cond);

This adds some phi nodes but they are not correct. RewriteUseAfterInsertions is not able to update existing PHINodes in if.end BasicBlock. Any leads on how to fix it. Am I going the right direction or is there some other way as well. 

Thanks!
Manish





_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Transformations + Re-definitions in SSA + SSAUpdater

Manish Gupta-8



On Fri, Sep 5, 2014 at 2:53 PM, Manish Gupta <[hidden email]> wrote:
Hi All,

I am transforming  LLVM IR, by adding new BasicBlocks. The new BasicBlock is called based on some condition say %re.def.bb. If the condition %re.def.bb is true I re-define some SSA variables in new BB re.def.true ow. I copy old instructions in re.def.false basicblock. The SSA needs to be updated for all the successors basic-blocks because of this re-definitions. I am tying to explain the problem using an example below:

ORIGINAL BB:
if.end:                       ; preds = %if.end, %entry
  %j.07 = phi i32 [ %shl, %if.end ], [ 1, %entry ]
  %i.06 = phi i32 [ %inc, %if.end ], [ 0, %entry ]
  %shl = shl i32 %j.07, 1
  %inc = add nsw i32 %i.06, 1
  %cmp = icmp sgt i32 %i.06, 13
  %cmp1 = icmp sgt i32 %shl, %val
  %or.cond = or i1 %cmp, %cmp1
  br i1 %or.cond, label %for.end, label %if.end

%for.end: ...

TRANSFORMATION:
if.end:                                           ; preds = %orig.brInst, %entry
  %j.07 = phi i32 [ %shl, %orig.brInst ], [ 1, %entry ]
  %i.06 = phi i32 [ %inc, %orig.brInst ], [ 0, %entry ]
  ....
  %re.def.bb = call i1 (i32, i64, ...)* isCond()
  br i1 %re.def.bb, label %re.def.true, label %re.def.false

re.def.false:
  //Original Code                                    ; preds = %if.end
  %shl = shl i32 %j.07, 1
  %inc = add nsw i32 %i.06, 1
  %cmp = icmp sgt i32 %i.06, 13
  %cmp1 = icmp sgt i32 %shl, %val
  %or.cond = or i1 %cmp, %cmp1
  br label %orig.brInst

re.def.true:
 //re-definitions of %shl, %inc, %or.cond
 %4 = re-define(%shl)
 %5 = re-define(%inc)
 %6 = re-define(%or.cond)

orig.brInst: 
  br i1 %or.cond, label %for.end, label %if.end

%for.end: ...

Code added by transformation is highlight above. And it is not complete yet as phinodes are messed up. orig.brInst is the branch instruction from original code. Which should execute the same way to keep the control flow intact. To fix the phinodes I used SSAUpdater class the same way instruction sink function is using it in LICM. 

SSAUpdate: 
Step 1: Add one more def. available for %inc, %shl and %or.cond  using AddAvailableValue in new BasicBlock re.def.true.
SSA.AddAvailableValue(re.def.true:, NewDefInsts(shl));
SSA.AddAvailableValue(re.def.true:, NewDefInsts(inc));
SSA.AddAvailableValue(re.def.true:, NewDefInsts(or.cond));

Step 2: Rewrite all the uses of %shl, %inc %or.cond to update SSA/PHI nodes
SSA.RewriteUseAfterInsertions(Users of %shl);
SSA.RewriteUseAfterInsertions(Users of %inc);
SSA.RewriteUseAfterInsertions(Users of %or.cond);

This adds some phi nodes but they are not correct. RewriteUseAfterInsertions is not able to update existing PHINodes in if.end BasicBlock. Any leads on how to fix it. Am I going the right direction or is there some other way as well. 

Thanks!
Manish






_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev