Reducing the Computational Complexity of RegionInfo

Nandini Singhal, Pratik Bhatu, Aditya Kumar, Tobias Grosser and Ramakrishna Upadrasta

Presented at US LLVM Developers’ Meeting, 2016


This talk was on reducing the Computational Complexity of RegionInfo. Part of CFG which satisfies certain properties can be optimised without affecting rest of CFG. The proposed algorithm traverses nodes from entry until exit while skipping detected regions and already traversed regions which failed other checks. It then identifies innermost loops in which all edges to entry reside. If none, no back edge i.e. passes check. If more than 2 different innermost loops, then fails region check. Else store the loop and compare with exit later.