Index: include/llvm/Analysis/IVUsers.h =================================================================== --- include/llvm/Analysis/IVUsers.h +++ include/llvm/Analysis/IVUsers.h @@ -100,6 +100,9 @@ ScalarEvolution *SE; SmallPtrSet Processed; + // Set of instrucions for which AddUsersImpl returned true. + SmallPtrSet AddUsersMemoTrue; + /// IVUses - A list of all tracked IV uses of induction variable expressions /// we are interested in. ilist IVUses; Index: lib/Analysis/IVUsers.cpp =================================================================== --- lib/Analysis/IVUsers.cpp +++ lib/Analysis/IVUsers.cpp @@ -170,8 +170,13 @@ // Add this IV user to the Processed set before returning false to ensure that // all IV users are members of the set. See IVUsers::isIVUserOrOperand. - if (!Processed.insert(I).second) - return true; // Instruction already handled. + if (!Processed.insert(I).second) { + // Instruction already handled + // If the instruction is in AddUsersMemoTrue, then we returned + // true for the instruction the last time we saw it, and should + // do so again. + return AddUsersMemoTrue.count(I) != 0; + } if (!SE->isSCEVable(I->getType())) return false; // Void and FP expressions cannot be reduced. @@ -209,7 +214,13 @@ continue; // Do not infinitely recurse on PHI nodes. - if (isa(User) && Processed.count(User)) + // Also, do not visit phi's in the loop header; these will be searched + // from later as the root of a DFT, and doing so now would make it + // possible to re-encounter the same instruction twice in the same + // DFT stack (i.e. we're still in the middle of trying to resolve + // the instruction) + if (isa(User) && + (Processed.count(User) || (User->getParent() == L->getHeader()))) continue; // Only consider IVUsers that are dominated by simplified loop @@ -228,17 +239,14 @@ // It's important to see the entire expression outside the loop to get // choices that depend on addressing mode use right, although we won't // consider references outside the loop in all cases. - // If User is already in Processed, we don't want to recurse into it again, - // but do want to record a second reference in the same instruction. bool AddUserToIVUsers = false; if (LI->getLoopFor(User->getParent()) != L) { - if (isa(User) || Processed.count(User) || - !AddUsersImpl(User, SimpleLoopNests)) { + if (isa(User) || !AddUsersImpl(User, SimpleLoopNests)) { DEBUG(dbgs() << "FOUND USER in other loop: " << *User << '\n' << " OF SCEV: " << *ISE << '\n'); AddUserToIVUsers = true; } - } else if (Processed.count(User) || !AddUsersImpl(User, SimpleLoopNests)) { + } else if (!AddUsersImpl(User, SimpleLoopNests)) { DEBUG(dbgs() << "FOUND USER: " << *User << '\n' << " OF SCEV: " << *ISE << '\n'); AddUserToIVUsers = true; @@ -283,10 +291,33 @@ dbgs() << " NORMALIZED TO: " << *ISE << '\n'); } } + AddUsersMemoTrue.insert(I); return true; } bool IVUsers::AddUsersIfInteresting(Instruction *I) { + // (( Note: This comment block is reconstructed from reverse engineering + // the implementation. Do not take it to be the gospel, but instead take + // it as a framework from which to understand the implementation. Please + // add-to or correct as you see fit. )) + // + // AddUsersIfInteresting performs a depth-first traversal (DFT) of def-use + // chains starting with the given I. Each DFT path is a def-use chain: + // I -> ... -> S -> T + // such that: + // * The chain starts with some I that is a phi in the loop header. + // * The chain ends with some instruction T such that AddUsersImpl(T) + // returns false. i.e. T does not have an interesting SCEV, or is + // an ephemeral value, or... etc. + // * All instructions in the chain except for T have interesting SCEVs, + // and AddUsersImpl() for these instructions will return true. + // + // Given such a def-use chain found via this DFT, we add to the IVUsers set: + // T as a user of the SCEV of S + + assert(isa(I) && "Expected a phi node to start the DFT"); + assert(I->getParent() == L->getHeader() && "Expected I in the loop header"); + // SCEVExpander can only handle users that are dominated by simplified loop // entries. Keep track of all loops that are only dominated by other simple // loops so we don't traverse the domtree for each user. @@ -346,6 +377,7 @@ void IVUsers::releaseMemory() { Processed.clear(); + AddUsersMemoTrue.clear(); IVUses.clear(); } Index: test/Analysis/IVUsers/invariant-out.ll =================================================================== --- /dev/null +++ test/Analysis/IVUsers/invariant-out.ll @@ -0,0 +1,86 @@ +; This tests to make sure that the IV-Users analysis's results are +; invariant of input order. We have the same IR with some small differences +; in the ordering of instructions, and ensure that all variants generate +; the same set of IVUsers. + +; RUN: opt -analyze -iv-users -S < %s | grep -e '%.*=' | sort | FileCheck %s +; CHECK: %2 = {{.*}} in %3 = sitofp i32 %2 to double +; CHECK: %2 = {{.*}} in %3 = sitofp i32 %2 to double +; CHECK: %2 = {{.*}} in %3 = sitofp i32 %2 to double +; CHECK: %iv.inc = {{.*}} in store i64 %iv.inc, i64* %addr, align 8 +; CHECK: %iv.inc = {{.*}} in store i64 %iv.inc, i64* %addr, align 8 +; CHECK: %iv.inc = {{.*}} in store i64 %iv.inc, i64* %addr, align 8 + +target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128-ni:1" +target triple = "x86_64-unknown-linux-gnu" + +define void @order1(i64 %v1, i32 %v2, i64* %addr) { +entry: + br label %loop + +loop: + %iv = phi i64 [%v1, %entry], [%iv.inc, %loop] + %iv2 = phi i32 [%v2, %entry], [%6, %loop] + %0 = add nuw i64 %iv, 1 + %1 = trunc i64 %0 to i32 + %2 = sub i32 %iv2, %1 + %3 = sitofp i32 %2 to double + %4 = sub i64 1, %iv + %5 = trunc i64 %4 to i32 + %6 = sub i32 %2, %5 + %iv.inc = add i64 %iv, 1 + store i64 %iv.inc, i64* %addr, align 8 + br i1 undef, label %loop, label %exit + +exit: + ret void +} + +; Reorder the phi instructions from @order1 +define void @order2(i64 %v1, i32 %v2, i64* %addr) { +entry: + br label %loop + +loop: + %iv2 = phi i32 [%v2, %entry], [%6, %loop] + %iv = phi i64 [%v1, %entry], [%iv.inc, %loop] + %0 = add nuw i64 %iv, 1 + %1 = trunc i64 %0 to i32 + %2 = sub i32 %iv2, %1 + %3 = sitofp i32 %2 to double + %4 = sub i64 1, %iv + %5 = trunc i64 %4 to i32 + %6 = sub i32 %2, %5 + %iv.inc = add i64 %iv, 1 + store i64 %iv.inc, i64* %addr, align 8 + br i1 undef, label %loop, label %exit + +exit: + ret void +} + +; Reorder the uselist in %iv's phi compared to @order1 +define void @order3(i64 %v1, i32 %v2, i64* %addr) { +entry: + br label %loop + +loop: + %iv = phi i64 [%v1, %entry], [%iv.inc, %loop] + %iv2 = phi i32 [%v2, %entry], [%6, %loop] + %0 = add nuw i64 %iv, 1 + %1 = trunc i64 %0 to i32 + %2 = sub i32 %iv2, %1 + %3 = sitofp i32 %2 to double + %4 = sub i64 1, %iv + %5 = trunc i64 %4 to i32 + %6 = sub i32 %2, %5 + %iv.inc = add i64 %iv, 1 + store i64 %iv.inc, i64* %addr, align 8 + br i1 undef, label %loop, label %exit + +exit: + ret void + +; uselistorder directives ---- + uselistorder i64 %iv, {2, 1, 0} +}