[llvm-dev] Generating a loop from llvm bitcode

[Cranmer, Joshua via llvm-dev]

The term for what you are trying to do in general is known as “control-flow graph structuring,” and you can find a bevy of papers on the topic. As David pointed out already, you can’t necessarily structure a generic CFG using goto, but I will caution that there are some constructs that are basically gotos for the purpose of structuring, namely break and continue (indeed, with multilevel break and continue statements, you can structure any non-irreducible graph without a goto). Figuring out which edges should be handled as gotos/breaks/continues and which edges should not is something that is not yet settled research.

As for your actual goal, you might have a better time of things if you start by generating an infinite loop, with breaks for exiting edges and continues for backedges, and then try to remove those via refinement steps (which might work better to handle situations such as loop conditions involving short-circuiting operators). In the case of loops with exactly one exiting block terminating with a conditional branch, the exiting condition is exactly the branch condition (up to negation) of that basic block. In general, doing this sort of analysis safely for generic CFGs is quite difficult, and you should approach the problem from the perspective that you might only sometimes be able to get this information.


From: llvm-dev [mailto:llvm-dev-bounces at lists.llvm.org] On Behalf Of Ejjeh, Adel via llvm-dev
Sent: Tuesday, August 7, 2018 12:52
To: llvm-dev at lists.llvm.org
Subject: [llvm-dev] Generating a loop from llvm bitcode

Hello

I am developing a backend that generates OpenCL from llvm bitcode. I start with a revived fork of the original LLVM C-Backend and have been modifying it. One thing that the backend lacked was generating proper loop structures; instead it relied on labels and goto statements. Therefore, I am trying to find a way to identify the loop structure and print it out in the backend. So far, the main issue I’ve been having trouble with is identifying the loop induction variable in a straight forward manner; getCanonicalInductionVariable doesn’t always succeed, and I’ve tried using InductionDescriptor, but it fails in cases where the CFG doesn’t include a loop preheader. Also, in both cases, I couldn’t find a direct way of determining the loop exit condition. I am wondering if there are any passes or data structures that would be able to help me accomplish what I am trying to do that I might be missing? Or does the community have any other ideas as to how I should approach this issue?

Any input is much appreciated.

Regards
Adel
--
Adel Ejjeh
PhD Candidate | Computer Science
University of Illinois at Urbana-Champaign
Siebel Center for Computer Science
201 N Goodwin Ave, Urbana, IL 61801
aejjeh at illinois.edu<mailto:aejjeh at illinois.edu> | adel.ejjeh at gmail.com<mailto:adel.ejjeh at gmail.com>



-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20180807/21250e37/attachment.html>