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

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)

so it is testable without your framework/setup

• Implement for a 1-level deep loop
• Implement nested loop

Edge Cases:

• 1
• 2
• 3... etc

This should be compatible with llvm-8.0. Follow here

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

1. 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;
  }

2. Single-level multiple loops
3. Multiple-level loops

Find the instruction that generates the update

Initial guess:

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

• for loop
• while loop
• do-while loop

2. Any arithmatic op is a candidate, narrow down further
3. Is the use of the instruction a comparison
4. 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.