[LLVMdev] Transformations + Re-definitions in SSA + SSAUpdater

[Manish Gupta]

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>