Chris Lattner wrote:> The select instruction is basically an SSA-form "conditional move", or a > very simple form of predication. Integer codes often have very complex > CFG's which are usually doing simple things. For example, it's not > uncommon to see something like this: > > if (blah) > X = 14; > > If the body of the if statement is simple enough, it's usually cheaper to > unconditionally execute the body than it is to execute the branch.Yes, I understand that. Though I though such optimization is usually done somewhere in backend, that's why I was surprised that it's commonly used in LLVM.> > "if" can be either take or not. In reality, both "if" can't be taked at > > the same time -- and that's why I'm trying to automatically figure out > > working on LLVM representation. However, the LLVM code: > > > > int %logsch(int %ih, int %nbh) { > > entry: > > %tmp.1 = setlt int %nbh, 0 > > %ih_addr.1 = select bool %tmp.1, int 10, int %ih > > %nbh_addr.1 = select bool %tmp.1, int 0, int %nbh > > %tmp.4 = setgt int %nbh_addr.1, 22528 > > %ih_addr.0 = select bool %tmp.4, int 7, int %ih_addr.1 > > %nbh_addr.0 = select bool %tmp.4, int 22528, int %nbh_addr.1 > > %tmp.8 = add int %nbh_addr.0, %ih_addr.0 > > ret int %tmp.8 > > } > > > > Has 'select' instructions and a single path, which makes my task harder. > > What are you trying to do? It looks like there is some correlation in the > branches that could be optimized away, is that what you're going after?No, not exactly. I need to find the path with the maximum execution time (in assembler for specific processor). Do to so, I must also find paths which cannot be executed no matter what input is (like one of the paths in the C example). I'm trying to do that using LLVM intermediate representation.> In the very worst case, you can always use the SelectLowering pass to turn > the select instructions into branches, but it would be preferable to find > another way if possible. :)In fact, I think this might be enough for me, since for now I'm only going to evaluate the algorithms for detecting infeasible paths. Thanks, Volodya
On Thu, 22 Apr 2004, Vladimir Prus wrote:> > > int %logsch(int %ih, int %nbh) { > > > entry: > > > %tmp.1 = setlt int %nbh, 0 > > > %ih_addr.1 = select bool %tmp.1, int 10, int %ih > > > %nbh_addr.1 = select bool %tmp.1, int 0, int %nbh > > > %tmp.4 = setgt int %nbh_addr.1, 22528 > > > %ih_addr.0 = select bool %tmp.4, int 7, int %ih_addr.1 > > > %nbh_addr.0 = select bool %tmp.4, int 22528, int %nbh_addr.1 > > > %tmp.8 = add int %nbh_addr.0, %ih_addr.0 > > > ret int %tmp.8 > > > } > > > > > > Has 'select' instructions and a single path, which makes my task harder. > > > > What are you trying to do? It looks like there is some correlation in the > > branches that could be optimized away, is that what you're going after? > > No, not exactly. I need to find the path with the maximum execution time (in > assembler for specific processor). Do to so, I must also find paths which > cannot be executed no matter what input is (like one of the paths in the C > example). I'm trying to do that using LLVM intermediate representation.In that case, the above is a simple straight-line sequence of code, which has exactly one path through it. I don't think you should need to break it up into multiple paths. If the control flow has been flattened like this, does it matter if some combination of predicates is impossible?> > In the very worst case, you can always use the SelectLowering pass to turn > > the select instructions into branches, but it would be preferable to find > > another way if possible. :) > > In fact, I think this might be enough for me, since for now I'm only going to > evaluate the algorithms for detecting infeasible paths.Okay, that works. :) -Chris -- http://llvm.cs.uiuc.edu/ http://www.nondot.org/~sabre/Projects/
Chris Lattner wrote:> > No, not exactly. I need to find the path with the maximum execution time > > (in assembler for specific processor). Do to so, I must also find paths > > which cannot be executed no matter what input is (like one of the paths > > in the C example). I'm trying to do that using LLVM intermediate > > representation. > > In that case, the above is a simple straight-line sequence of code, which > has exactly one path through it. I don't think you should need to break > it up into multiple paths. If the control flow has been flattened like > this, does it matter if some combination of predicates is impossible?Yes, because the target processor does not have any equivivalent of the 'select' statement. Generally speaking, I have to search for paths in assembler for that processor and, devise a way to map them back into LLVM and run analysis then, but that's more work (and research). For a start, lowering selects will do. - Volodya