Manish Gupta
2014-Sep-05 21:53 UTC
[LLVMdev] Transformations + Re-definitions in SSA + SSAUpdater
Hi All, I am transforming LLVM IR, by adding new BasicBlocks. The new BasicBlock is called based on some condition say *%re.def.bb <http://re.def.bb>*. If the condition* %re.def.bb <http://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 <http://re.def.bb> = call i1 (i32, i64, ...)* isCond()* * br i1 %re.def.bb <http://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 -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20140905/c068149b/attachment.html>
Manish Gupta
2014-Sep-05 21:55 UTC
[LLVMdev] Transformations + Re-definitions in SSA + SSAUpdater
On Fri, Sep 5, 2014 at 2:53 PM, Manish Gupta <manishg at cs.ucsd.edu> 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 <http://re.def.bb>*. If > the condition* %re.def.bb <http://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 <http://re.def.bb> = call i1 (i32, i64, ...)* isCond()* > * br i1 %re.def.bb <http://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 > > > > >-------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20140905/4f27eea1/attachment.html>