Light

salekinsirajus / loop-analysis-pass-llvm Goto Github PK

View Code? Open in Web Editor NEW

0.0 2.0 0.0 78.6 MB

Vim Script 0.01% CMake 0.01% Dockerfile 0.02% Makefile 0.39% C++ 0.26% C 97.59% Shell 1.49% Roff 0.06% M4 0.07% Python 0.10%

loop-analysis-pass-llvm's Introduction

LLVM Analysis Pass: Loop

This pass analyzes and report a few aspects of a Loop. Specifically, this pass:

Adds metadata to the IR branch instruction representing the back edge for each loop
Adds metadata to the IR instruction that generates the loop induction variable update used for loop termination check.

Acceptance Criteria

All Metadata should include corresponding filename and line number in the C++ code
Test case may include 2 or 3 level embedded loops as well as multiple loops at same level.
Pass source code should be compilable at our end using llvm 8.0 version.
The pass should define any dependencies on other passes automatically. It is not expected that we run multiple llvm clang and/or opt passes prior to running this pass. The output of the pass is an .ll file. It is expected that this Meta-data annotated IR should be able to compile to executable and be functional. There should be no functional difference in executable when compiled with and without this pass.

Running Locally

Build a docker container using the docker file provided.

docker build -t llvmp3:latest .

Build Executable

Get into the docker container

docker run -v $(pwd):/ece566 -it llvmp3:latest /bin/bash

Create a build directory

mkdir build

Run cmake

cmake .

Now run make

make

Building Test

Create a test directory in the root folder and cd into it

mkdir test
cd test

Configure the benchmark tool to find the executable that we built earlier

/ece566/wolfbench/wolfbench/configure --enable-customtool=/ece566/build/p3

Running Test

while you are in the test directory, run the following command to compile all the benchmark.

make all test

To ensure that our optimization pass did not break things, run the following:

make test compare

Manual Test

Let's say you have a file named test.c

/usr/bin/clang-8 -O0 -Xclang -disable-O0-optnone -w -std=c89 -emit-llvm -c -o test.bc test.c
/usr/bin/llvm-link-8 -o test.link.bc test.bc
/usr/bin/opt-8  -o test.opt.bc test.link.bc
./cla  test.opt.bc test.tune.bc

loop-analysis-pass-llvm's People

Contributors

Watchers

loop-analysis-pass-llvm's Issues

Tracking Edge Cases

Multiple Loop Latches

  /// Returns true if \p BB is a loop-latch.
  /// A latch block is a block that contains a branch back to the header.
  /// This function is useful when there are multiple latches in a loop
  /// because \fn getLoopLatch will return nullptr in that case.
  bool isLoopLatch(const BlockT *BB) const {
    assert(!isInvalid() && "Loop not in a valid state!");
    assert(contains(BB) && "block does not belong to the loop");

    BlockT *Header = getHeader();
    auto PredBegin = GraphTraits<Inverse<BlockT *>>::child_begin(Header);
    auto PredEnd = GraphTraits<Inverse<BlockT *>>::child_end(Header);
    return std::find(PredBegin, PredEnd, BB) != PredEnd;
  }

Single-level multiple loops
Multiple-level loops

Implement like a regular pass

so it is testable without your framework/setup

Detect IR instruction that generates the loop induction variable update used for loop termination check.

Find the instruction that generates the update

Initial guess:

It should be in the loop header, make sure this applies to all the cases

for loop
while loop
do-while loop

Any arithmatic op is a candidate, narrow down further
Is the use of the instruction a comparison
And is the comparison ends in exit block?

Perhaps a slightly better way would be:

consider only comparisons in the "suspect" block
find the operands, if it's not a constant, find the instruction
if the last instruction contains an induction variable, you have your result.

Implement the Skeleton

This is what we'll use to perform develop further analysis. Use the LLVM LoopInfo API.

TODO:

Make sure to declare any dependency pass (ideally keep it at one)

Implement Branch Instruction Detection that's a Back Edge to the Loop

Implement for a 1-level deep loop
Implement nested loop

Edge Cases:

1
2
3... etc

Pass Implementation

This should be compatible with llvm-8.0. Follow here

Change the make/cmake files to ensure that we are using llvm-8.0

Recommend Projects

React

A declarative, efficient, and flexible JavaScript library for building user interfaces.
Vue.js

🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
Typescript

TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
TensorFlow

An Open Source Machine Learning Framework for Everyone
Django

The Web framework for perfectionists with deadlines.
Laravel

A PHP framework for web artisans
D3

Bring data to life with SVG, Canvas and HTML. 📊📈🎉

Recommend Topics

javascript

JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
web

Some thing interesting about web. New door for the world.
server

A server is a program made to process requests and deliver data to clients.
Machine learning

Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Visualization

Some thing interesting about visualization, use data art
Game

Some thing interesting about game, make everyone happy.

Recommend Org

Facebook

We are working to build community through open source technology. NB: members must have two-factor auth.
Microsoft

Open source projects and samples from Microsoft.
Google

Google ❤️ Open Source for everyone.
Alibaba

Alibaba Open Source for everyone
D3

Data-Driven Documents codes.
Tencent

China tencent open source team.