[DependenceAnalysis][PR56275] Normalize dependence analysis results to be non-negative when required

[congzhe]

Summary

This is the fix to PR56275 (https://github.com/llvm/llvm-project/issues/56275) which is a missed opportunity, where a perfrectly valid case for loop interchange failed interchange legality. More specifically, loop interchange does not interpret the direction vector correctly.

Regarding PR56275, this patch is the first of the two-patch series that resolve the problem: D130188, D130189

As we discussed on the PR page as well as in the loopopt meeting, the root problem is that the distance/direction vector produced by dependence analysis (DA) needs to be normalized (reversed), if the vector is negative. We've determined to provide helper functions in DA that does the normalization, and clients can ask DA to do normalization if needed.

In this patch I've added the helper functions isDirectionNegative() and normalize() such that DA results can get normalized if the direction is negative. Whether we call those function or not is based on a flag newly introduced, i.e., NeedsNormalization. Client passes (loop interchange for example) can set this flag to true (like the following) when they query DA, if they want DA results to be normalized. Please also refer to the follow-up loop interchange patch https://reviews.llvm.org/D130189 where DA is queried in loop interchange. It looks to me that this is the most clean way to do so, after experimenting with several alternatives.

DependenceInfo DI(&F, &AR.AA, &AR.SE, &AR.LI, /*NeedsNormalize=*/true);
// use DI anywhere in client passes.

I've also added an opt option -da-normalize-results such that we can run DA directly with NeedsNormalization being true, and update DA test cases to make sure of test coverage. The test cases added in Banerjee.ll shows that negative vectors are normalized with -da-normalize-results=true.

[kawashima-fj]

Thanks @congzhe . Though I'm not familiar with DA, it looks good to me. I'll leave the detailed review to the experts.

[bmahjour]

Since the normalize() function is conceptually an operation that applies to the result (as opposed to the analysis itself), it makes more sense for it to be a member of the Dependence class. Client code, such as loop interchange, would then do something like this:

if (auto D = DI->depends(Src, Dst, true).normalize()) {
   ...

This way the analysis can be done once, but the results can be interpreted differently if the need arises.

[bmahjour]

llvm/include/llvm/Analysis/DependenceAnalysis.h

982

It would be good for the normalize() function to return a boolean indicating if it changed the result or not. This could come in handy, for example, when printing the results (please see my comment about the printer pass).

llvm/test/Analysis/DependenceAnalysis/Banerjee.ll

248

Since the printer pass (using dumpExampleDependence) prints the Src and Dst instructions in a fixed order, these results could easily be misinterpreted. To avoid confusion can we flag the results that have been normalized with a special marker? eg:

Src: store....
Dst: ...load
  da analyze - anti [< <]! **normalized**

[Meinersbur]

llvm/lib/Analysis/DependenceAnalysis.cpp

4207–4209

The code falls into the final return false anyway, i.e. this condition is redundant.

You could also use a switch statement.

4229

Can we avoid bit-operations with magic constants? 0x01 is LT, 0x02 is EQ, 0x04 is GT. 0x07 is ALL.

4231

.Direction is a bitfield. The compiler already does the masking for you.

[Meinersbur]

I think I would prefer the request for normalization on the depends() call, rather that the DependenceInfo constructor. This keeps it closer to the code that either expects normalized dependencies, or dependencies that expect it to correspond to which instructions were passed as either Src or Dst. Also, If DependenceInfo would be used as an analysis in a pass manager, having a NeedsNormalize=true instance of DependenceInfo in the analysis cache will break any pass that expect the other interpretation.

llvm/lib/Analysis/DependenceAnalysis.cpp

124–127

[serious] This flag breaks any code that expects non-normalized dependences.

[Meinersbur]

llvm/lib/Analysis/DependenceAnalysis.cpp

124–127

An option for the print-da pass would be the better approach. Alternatively, if a dependency is normalized, also print the normalized dependence using a different output format. For instance:

da analyze - flow [> <>]!
da normalized - anti [< <>]!

[congzhe]

In D130188#3669842, @bmahjour wrote:

Since the normalize() function is conceptually an operation that applies to the result (as opposed to the analysis itself), it makes more sense for it to be a member of the Dependence class. Client code, such as loop interchange, would then do something like this:

if (auto D = DI->depends(Src, Dst, true).normalize()) {
   ...

This way the analysis can be done once, but the results can be interpreted differently if the need arises.

Thanks for the comment, I've updated the patch accordingly, i.e., make normalize() a member function of the Dependence/FullDependence class and hence it can be called as you suggested. Please refer to the loop interchange patch D130189 as well.

llvm/include/llvm/Analysis/DependenceAnalysis.h

982

Thanks for the comment, I understand your point. In fact the "normalization" process is implemented in two-parts - isDirectionNegative() and normalize(). What isDirectionNegative() returns is already a boolean (which is the funcationality you requested), and the client can know whether or not the depenedence vector is negative, and can further decide whether or not it wants to call normalize().

Please also refer to the most recent change in dumpExampleDependence() for the uses of isDirectionNegative() and normalize(). I thought about merging those two function into one, but I thought keep them as two segement functions can make it easier if clients merely want to check if the direction is negative but do not want to normalize the result.

llvm/lib/Analysis/DependenceAnalysis.cpp

124–127

Thanks a lot, considering both Bardia's and your comment, I've updated the patch such that the DependenceInfo constructor is not changed. Now the NormalizeResults option is only used in print-da pass. Also the output for the printer pass is also updated according to both of your comments.

4207–4209

Thanks, I've removed this redundant condition.

4229

Thanks for the comment. I've added more detailed source code comments to describe the funtionality here, please refer to the updated patch.

I'd like to mention that those 0x01, 0x02, 0x04 are not directly related to LT/EQ/GT. They serve as the purpose of extracting the 1st, 2nd and 3rd bit (to the right), and then reversing the 1st and 3rd bits. This inherently reverses the direction vector, however complex it is, e.g., banerjee6() in the test file banerjee.ll.

4231

Thanks, updated accordingly.

llvm/test/Analysis/DependenceAnalysis/Banerjee.ll

248

Thanks, I've done the change accordingly. Please also refer to the most recent NORMALIZE lines in tests.

[bmahjour]

llvm/include/llvm/Analysis/DependenceAnalysis.h

982

Sure, but normalize() could still return a boolean indicating if it changed the Dependence object.

llvm/lib/Analysis/DependenceAnalysis.cpp

125

Suggestion:
NormalizeResults -> NormalizePrintedResults
da-normalize-results -> da-print-normalized-results

194

Suggestion for better readability: " normalized "

292

This function should call isDirectionNegative() to determine if reversing of the direction vector is necessary. If the direction is not negative, then it should not make any changes and return false. Otherwise proceed and return true.

[congzhe]

Thanks @bmahjour, I've tried to address all your comments in the updated version.

[Meinersbur]

llvm/include/llvm/Analysis/DependenceAnalysis.h

254–255

Please also mention the case that a dependency object can represent a lexicographically forward and reversed dependency at the same time, as discussed in https://github.com/llvm/llvm-project/issues/56275#issuecomment-1183363002 and what the expected behaviour for this case is.

llvm/lib/Analysis/DependenceAnalysis.cpp

124–127

While cl::opt setting is acceptable, NPM explicitly have the possibility to parse pass options. Why not use it?

277

[style] avoid Almost-Always-Auto

288

[serious] This should return a new FullDependence object. Modifying the existing object will also modify the object in the pass manager's analysis cache and potentially break any code using it and not expect it to be normalized.

299

.Direction is a bitfield. The compiler already does the masking for you.

430

[nit] unrelated change

4229

LT/EQ/GT are directly related to those bits. Swapping the LT <=> GT flags directly corresponds to swapping the 1st and 3rd bit. If it did not, the bit swapping would not work either and one would need to map all 2^6 possibilities separately. Note that <> is possible as well: 0x5.

This is an alternative with less bit magic:

// reverse direction vector
// less flag becomes greater flag -- greater flag becomes less flag
unsigned char RevDirection = Direction & Dependence::DVEntry::EQ;
if (Direction & Dependence::DVEntry::LT)
    RevDirection |= Dependence::DVEntry::GT;
if (Direction & Dependence::DVEntry::GT)
    RevDirection |= Dependence::DVEntry::LT;

[congzhe]

llvm/include/llvm/Analysis/DependenceAnalysis.h

254–255

Thanks, I've added the corresponding description in the comment of isDirectionNegative() in DependenceAnalysis.cpp.

llvm/lib/Analysis/DependenceAnalysis.cpp

124–127

Thanks for this -- I'm not very clear of this functionality, I'm wondering if you could point me to some references?

277

Thanks, updated accordingly.

288

Thanks, I've updated to make normalize() return a new FullDependence object (although copy constructor of FullDependence is not allowed), please refer to the most recent update.

4229

Thanks a lot for the suggestion, I've updated the code as per your suggestion.

[bmahjour]

llvm/lib/Analysis/DependenceAnalysis.cpp

288

No Dependence object is being cached anywhere. A new object is constructed every time DependenceInfo::depends() gets called.

[congzhe]

Hi @bmahjour @Meinersbur, I've updated the patch such that normalize() changes the Dependence object in place, and I've also leveraged the capability of the NPM to parse pass options instead of using cl::opt. I'd appreciate it if you could take a look at this version, thanks a lot!

[Meinersbur]

LGTM, but with a renaming suggestion.

llvm/lib/Passes/PassBuilder.cpp

854

I think the da-print- prefix is unnecessary since this is parsed for print<da> pass only.

[congzhe]

Addressed comments, will land soon.

llvm/include/llvm/Analysis/DependenceAnalysis.h

public:
     /// getDirection - Returns the direction associated with a particular
     /// level.
     virtual unsigned getDirection(unsigned Level) const { return DVEntry::ALL; }
 
     /// getDistance - Returns the distance (or NULL) associated with a
     /// particular level.
     virtual const SCEV *getDistance(unsigned Level) const { return nullptr; }
 
+    /// Check if the direction vector is negative. A negative direction
+    /// vector means Src and Dst are reversed in the actual program.
+    virtual bool isDirectionNegative() const { return false; }
+
+    /// If the direction vector is negative, normalize the direction
+    /// vector to make it non-negative. Normalization is done by reversing
+    /// Src and Dst, plus reversing the dependence directions and distances
+    /// in the vector.
+    virtual bool normalize(ScalarEvolution *SE) { return false; }
+
     /// isPeelFirst - Returns true if peeling the first iteration from
     /// this loop will break this dependence.
     virtual bool isPeelFirst(unsigned Level) const { return false; }
 
     /// isPeelLast - Returns true if peeling the last iteration from
     /// this loop will break this dependence.
     virtual bool isPeelLast(unsigned Level) const { return false; }
 
public:
     /// setNextSuccessor - Sets the value of the NextSuccessor
     /// field.
     void setNextSuccessor(const Dependence *succ) { NextSuccessor = succ; }
 
     /// dump - For debugging purposes, dumps a dependence to OS.
     ///
     void dump(raw_ostream &OS) const;
 
-  private:
+  protected:
     Instruction *Src, *Dst;
+
+  private:
     const Dependence *NextPredecessor = nullptr, *NextSuccessor = nullptr;
     friend class DependenceInfo;
   };
 
   /// FullDependence - This class represents a dependence between two memory
   /// references in a function. It contains detailed information about the
   /// dependence (direction vectors, etc.) and is used when the compiler is
   /// able to accurately analyze the interaction of the references; that is,
public:
     /// getDirection - Returns the direction associated with a particular
     /// level.
     unsigned getDirection(unsigned Level) const override;
 
     /// getDistance - Returns the distance (or NULL) associated with a
     /// particular level.
     const SCEV *getDistance(unsigned Level) const override;
 
+    /// Check if the direction vector is negative. A negative direction
+    /// vector means Src and Dst are reversed in the actual program.
+    bool isDirectionNegative() const override;
+
+    /// If the direction vector is negative, normalize the direction
+    /// vector to make it non-negative. Normalization is done by reversing
+    /// Src and Dst, plus reversing the dependence directions and distances
+    /// in the vector.
+    bool normalize(ScalarEvolution *SE) override;
+
     /// isPeelFirst - Returns true if peeling the first iteration from
     /// this loop will break this dependence.
     bool isPeelFirst(unsigned Level) const override;
 
     /// isPeelLast - Returns true if peeling the last iteration from
     /// this loop will break this dependence.
     bool isPeelLast(unsigned Level) const override;
 
namespace llvm {
 
   /// AnalysisPass to compute dependence information in a function
   class DependenceAnalysis : public AnalysisInfoMixin<DependenceAnalysis> {
   public:
     typedef DependenceInfo Result;
     Result run(Function &F, FunctionAnalysisManager &FAM);
 
   private:
     static AnalysisKey Key;
     friend struct AnalysisInfoMixin<DependenceAnalysis>;
   }; // class DependenceAnalysis
 
   /// Printer pass to dump DA results.
   struct DependenceAnalysisPrinterPass
       : public PassInfoMixin<DependenceAnalysisPrinterPass> {
-    DependenceAnalysisPrinterPass(raw_ostream &OS) : OS(OS) {}
+    DependenceAnalysisPrinterPass(raw_ostream &OS,
+                                  bool NormalizeResults = false)
+        : OS(OS), NormalizeResults(NormalizeResults) {}
 
     PreservedAnalyses run(Function &F, FunctionAnalysisManager &FAM);
 
   private:
     raw_ostream &OS;
+    bool NormalizeResults;
   }; // class DependenceAnalysisPrinterPass
 
   /// Legacy pass manager pass to access dependence information
   class DependenceAnalysisWrapperPass : public FunctionPass {
   public:
     static char ID; // Class identification, replacement for typeinfo
     DependenceAnalysisWrapperPass();
 

llvm/lib/Analysis/DependenceAnalysis.cpp

cl::desc(
         "dependence vectors for languages that allow the subscript of one "
         "dimension to underflow or overflow into another dimension."));
 
 static cl::opt<unsigned> MIVMaxLevelThreshold(
     "da-miv-max-level-threshold", cl::init(7), cl::Hidden,
     cl::desc("Maximum depth allowed for the recursive algorithm used to "
              "explore MIV direction vectors."));
 
 //===----------------------------------------------------------------------===//
 // basics
 
 DependenceAnalysis::Result
 DependenceAnalysis::run(Function &F, FunctionAnalysisManager &FAM) {
   auto &AA = FAM.getResult<AAManager>(F);
   auto &SE = FAM.getResult<ScalarEvolutionAnalysis>(F);
   auto &LI = FAM.getResult<LoopAnalysis>(F);
   return DependenceInfo(&F, &AA, &SE, &LI);
 }
 
 AnalysisKey DependenceAnalysis::Key;
void DependenceAnalysisWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
   AU.addRequiredTransitive<ScalarEvolutionWrapperPass>();
   AU.addRequiredTransitive<LoopInfoWrapperPass>();
 }
 
 // Used to test the dependence analyzer.
 // Looks through the function, noting instructions that may access memory.
 // Calls depends() on every possible pair and prints out the result.
 // Ignores all other instructions.
-static void dumpExampleDependence(raw_ostream &OS, DependenceInfo *DA) {
+static void dumpExampleDependence(raw_ostream &OS, DependenceInfo *DA,
+                                  ScalarEvolution &SE, bool NormalizeResults) {
   auto *F = DA->getFunction();
   for (inst_iterator SrcI = inst_begin(F), SrcE = inst_end(F); SrcI != SrcE;
        ++SrcI) {
     if (SrcI->mayReadOrWriteMemory()) {
       for (inst_iterator DstI = SrcI, DstE = inst_end(F);
            DstI != DstE; ++DstI) {
         if (DstI->mayReadOrWriteMemory()) {
           OS << "Src:" << *SrcI << " --> Dst:" << *DstI << "\n";
           OS << "  da analyze - ";
           if (auto D = DA->depends(&*SrcI, &*DstI, true)) {
+            // Normalize negative direction vectors if required by clients.
+            if (NormalizeResults && D->normalize(&SE))
+                OS << "normalized - ";
             D->dump(OS);
             for (unsigned Level = 1; Level <= D->getLevels(); Level++) {
               if (D->isSplitable(Level)) {
                 OS << "  da analyze - split level = " << Level;
                 OS << ", iteration = " << *DA->getSplitIteration(*D, Level);
                 OS << "!\n";
               }
             }
           }
           else
             OS << "none!\n";
         }
       }
     }
   }
 }
 
 void DependenceAnalysisWrapperPass::print(raw_ostream &OS,
                                           const Module *) const {
-  dumpExampleDependence(OS, info.get());
+  dumpExampleDependence(OS, info.get(),
+                        getAnalysis<ScalarEvolutionWrapperPass>().getSE(), false);
 }
 
 PreservedAnalyses
 DependenceAnalysisPrinterPass::run(Function &F, FunctionAnalysisManager &FAM) {
   OS << "'Dependence Analysis' for function '" << F.getName() << "':\n";
-  dumpExampleDependence(OS, &FAM.getResult<DependenceAnalysis>(F));
+  dumpExampleDependence(OS, &FAM.getResult<DependenceAnalysis>(F),
+                        FAM.getResult<ScalarEvolutionAnalysis>(F),
+                        NormalizeResults);
   return PreservedAnalyses::all();
 }
 
 //===----------------------------------------------------------------------===//
 // Dependence methods
 
 // Returns true if this is an input dependence.
 bool Dependence::isInput() const {
FullDependence::FullDependence(Instruction *Source, Instruction *Destination,
                                unsigned CommonLevels)
     : Dependence(Source, Destination), Levels(CommonLevels),
       LoopIndependent(PossiblyLoopIndependent) {
   Consistent = true;
   if (CommonLevels)
     DV = std::make_unique<DVEntry[]>(CommonLevels);
 }
 
+// FIXME: in some cases the meaning of a negative direction vector
+// may not be straightforward, e.g.,
+// for (int i = 0; i < 32; ++i) {
+//   Src:    A[i] = ...;
+//   Dst:    use(A[31 - i]);
+// }
+// The dependency is
+//   flow { Src[i] -> Dst[31 - i] : when i >= 16 } and
+//   anti { Dst[i] -> Src[31 - i] : when i < 16 },
+// -- hence a [<>].
+// As long as a dependence result contains '>' ('<>', '<=>', "*"), it
+// means that a reversed/normalized dependence needs to be considered
+// as well. Nevertheless, current isDirectionNegative() only returns
+// true with a '>' or '>=' dependency for ease of canonicalizing the
+// dependency vector, since the reverse of '<>', '<=>' and "*" is itself.
+bool FullDependence::isDirectionNegative() const {
+  for (unsigned Level = 1; Level <= Levels; ++Level) {
+    unsigned char Direction = DV[Level - 1].Direction;
+    if (Direction == Dependence::DVEntry::EQ)
+      continue;
+    if (Direction == Dependence::DVEntry::GT ||
+        Direction == Dependence::DVEntry::GE)
+      return true;
+    return false;
+  }
+  return false;
+}
+
+bool FullDependence::normalize(ScalarEvolution *SE) {
+  if (!isDirectionNegative())
+    return false;
+
+  LLVM_DEBUG(dbgs() << "Before normalizing negative direction vectors:\n";
+             dump(dbgs()););
+  std::swap(Src, Dst);
+  for (unsigned Level = 1; Level <= Levels; ++Level) {
+    unsigned char Direction = DV[Level - 1].Direction;
+    // Reverse the direction vector, this means LT becomes GT
+    // and GT becomes LT.
+    unsigned char RevDirection = Direction & Dependence::DVEntry::EQ;
+    if (Direction & Dependence::DVEntry::LT)
+      RevDirection |= Dependence::DVEntry::GT;
+    if (Direction & Dependence::DVEntry::GT)
+      RevDirection |= Dependence::DVEntry::LT;
+    DV[Level - 1].Direction = RevDirection;
+    // Reverse the dependence distance as well.
+    if (DV[Level - 1].Distance != nullptr)
+      DV[Level - 1].Distance =
+          SE->getNegativeSCEV(DV[Level - 1].Distance);
+  }
+
+  LLVM_DEBUG(dbgs() << "After normalizing negative direction vectors:\n";
+             dump(dbgs()););
+  return true;
+}
+
 // The rest are simple getters that hide the implementation.
 
 // getDirection - Returns the direction associated with a particular level.
 unsigned FullDependence::getDirection(unsigned Level) const {
   assert(0 < Level && Level <= Levels && "Level out of range");
   return DV[Level - 1].Direction;
 }
 
LLVM_DUMP_METHOD void DependenceInfo::Constraint::dump(raw_ostream &OS) const {
   else if (isLine())
     OS << " Line is " << *getA() << "*X + " <<
       *getB() << "*Y = " << *getC() << "\n";
   else
     llvm_unreachable("unknown constraint type in Constraint::dump");
 }
 #endif
 
 
 // Updates X with the intersection
 // of the Constraints X and Y. Returns true if X has changed.
 // Corresponds to Figure 4 from the paper
 //
 //            Practical Dependence Testing
 //            Goff, Kennedy, Tseng
 //            PLDI 1991
 bool DependenceInfo::intersectConstraints(Constraint *X, const Constraint *Y) {
for (unsigned SI : Coupled.set_bits()) {
             }
           }
         }
       }
     }
   }
   llvm_unreachable("somehow reached end of routine");
   return nullptr;
 }

llvm/lib/Passes/PassBuilder.cpp

if (ParamName == "may") {
       return make_error<StringError>(
           formatv("invalid StackLifetime parameter '{0}' ", ParamName).str(),
           inconvertibleErrorCode());
     }
   }
   return Result;
 }
 
+Expected<bool> parseDependenceAnalysisPrinterOptions(StringRef Params) {
+  return parseSinglePassOption(Params, "da-print-normalized-results",
+                               "DependenceAnalysisPrinter");
+}
+
 } // namespace
 
 /// Tests whether a pass name starts with a valid prefix for a default pipeline
 /// alias.
 static bool startsWithDefaultPipelineAliasPrefix(StringRef Name) {
   return Name.startswith("default") || Name.startswith("thinlto") ||
          Name.startswith("lto");
 }

llvm/lib/Passes/PassRegistry.def

FUNCTION_PASS_WITH_PARAMS("gvn",
                           "no-memdep;memdep")
 FUNCTION_PASS_WITH_PARAMS("print<stack-lifetime>",
                           "StackLifetimePrinterPass",
                            [](StackLifetime::LivenessType Type) {
                              return StackLifetimePrinterPass(dbgs(), Type);
                            },
                           parseStackLifetimeOptions,
                           "may;must")
+FUNCTION_PASS_WITH_PARAMS("print<da>",
+                          "DependenceAnalysisPrinterPass",
+                           [](bool NormalizeResults) {
+                             return DependenceAnalysisPrinterPass(dbgs(), NormalizeResults);
+                           },
+                          parseDependenceAnalysisPrinterOptions,
+                          "da-print-normalized-results")
 #undef FUNCTION_PASS_WITH_PARAMS
 
 #ifndef LOOPNEST_PASS
 #define LOOPNEST_PASS(NAME, CREATE_PASS)
 #endif
 LOOPNEST_PASS("loop-flatten", LoopFlattenPass())
 LOOPNEST_PASS("loop-interchange", LoopInterchangePass())
 LOOPNEST_PASS("loop-unroll-and-jam", LoopUnrollAndJamPass())

llvm/test/Analysis/DependenceAnalysis/Banerjee.ll

 ; RUN: opt < %s -disable-output -da-delinearize=false "-passes=print<da>"      \
 ; RUN: -aa-pipeline=basic-aa 2>&1 | FileCheck %s
+; RUN: opt < %s -disable-output -da-delinearize=false -passes='print<da><da-print-normalized-results>'      \
+; RUN: -aa-pipeline=basic-aa 2>&1 | FileCheck %s -check-prefix=NORMALIZE
 ; RUN: opt < %s -disable-output "-passes=print<da>" -aa-pipeline=basic-aa 2>&1 \
 ; RUN: | FileCheck %s -check-prefix=DELIN
 
 target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64-S128"
 target triple = "x86_64-apple-macosx10.6.0"
 
 
 ;;  for (long int i = 1; i <= 10; i++)
 ;;    for (long int j = 1; j <= 10; j++) {
 ;;      A[10*i + j] = 0;
 ;;      *B++ = A[10*i + j - 1];
 
 define void @banerjee0(i64* %A, i64* %B, i64 %m, i64 %n) nounwind uwtable ssp {
 entry:
   br label %for.cond1.preheader
 ; CHECK: 'Dependence Analysis' for function 'banerjee0':
 ; CHECK: da analyze - none!
 ; CHECK: da analyze - flow [<= <>]!
 ; CHECK: da analyze - confused!
 ; CHECK: da analyze - none!
 ; CHECK: da analyze - confused!
 ; CHECK: da analyze - none!
 
+; NORMALIZE: 'Dependence Analysis' for function 'banerjee0':
+; NORMALIZE: da analyze - none!
+; NORMALIZE: da analyze - flow [<= <>]!
+; NORMALIZE: da analyze - confused!
+; NORMALIZE: da analyze - none!
+; NORMALIZE: da analyze - confused!
+; NORMALIZE: da analyze - none!
+
 ; DELIN: 'Dependence Analysis' for function 'banerjee0':
 ; DELIN: da analyze - none!
 ; DELIN: da analyze - flow [<= <>]!
 ; DELIN: da analyze - confused!
 ; DELIN: da analyze - none!
 ; DELIN: da analyze - confused!
 ; DELIN: da analyze - none!
 

 ; CHECK: 'Dependence Analysis' for function 'banerjee1':
 ; CHECK: da analyze - output [* *]!
 ; CHECK: da analyze - flow [* <>]!
 ; CHECK: da analyze - confused!
 ; CHECK: da analyze - input [* *]!
 ; CHECK: da analyze - confused!
 ; CHECK: da analyze - output [* *]!
 
+; NORMALIZE: 'Dependence Analysis' for function 'banerjee1':
+; NORMALIZE: da analyze - output [* *]!
+; NORMALIZE: da analyze - flow [* <>]!
+; NORMALIZE: da analyze - confused!
+; NORMALIZE: da analyze - input [* *]!
+; NORMALIZE: da analyze - confused!
+; NORMALIZE: da analyze - output [* *]!
+
 ; DELIN: 'Dependence Analysis' for function 'banerjee1':
 ; DELIN: da analyze - output [* *]!
 ; DELIN: da analyze - flow [* <>]!
 ; DELIN: da analyze - confused!
 ; DELIN: da analyze - input [* *]!
 ; DELIN: da analyze - confused!
 ; DELIN: da analyze - output [* *]!
 

 ; CHECK: 'Dependence Analysis' for function 'banerjee2':
 ; CHECK: da analyze - none!
 ; CHECK: da analyze - none!
 ; CHECK: da analyze - confused!
 ; CHECK: da analyze - none!
 ; CHECK: da analyze - confused!
 ; CHECK: da analyze - none!
 
+; NORMALIZE: 'Dependence Analysis' for function 'banerjee2':
+; NORMALIZE: da analyze - none!
+; NORMALIZE: da analyze - none!
+; NORMALIZE: da analyze - confused!
+; NORMALIZE: da analyze - none!
+; NORMALIZE: da analyze - confused!
+; NORMALIZE: da analyze - none!
+
 ; DELIN: 'Dependence Analysis' for function 'banerjee2':
 ; DELIN: da analyze - none!
 ; DELIN: da analyze - none!
 ; DELIN: da analyze - confused!
 ; DELIN: da analyze - none!
 ; DELIN: da analyze - confused!
 ; DELIN: da analyze - none!
 

 ; CHECK: 'Dependence Analysis' for function 'banerjee3':
 ; CHECK: da analyze - none!
 ; CHECK: da analyze - flow [> >]!
 ; CHECK: da analyze - confused!
 ; CHECK: da analyze - none!
 ; CHECK: da analyze - confused!
 ; CHECK: da analyze - none!
 
+; NORMALIZE: 'Dependence Analysis' for function 'banerjee3':
+; NORMALIZE: da analyze - none!
+; NORMALIZE: da analyze - normalized - anti [< <]!
+; NORMALIZE: da analyze - confused!
+; NORMALIZE: da analyze - none!
+; NORMALIZE: da analyze - confused!
+; NORMALIZE: da analyze - none!
+
 ; DELIN: 'Dependence Analysis' for function 'banerjee3':
 ; DELIN: da analyze - none!
 ; DELIN: da analyze - flow [> >]!
 ; DELIN: da analyze - confused!
 ; DELIN: da analyze - none!
 ; DELIN: da analyze - confused!
 ; DELIN: da analyze - none!
 

 ; CHECK: 'Dependence Analysis' for function 'banerjee4':
 ; CHECK: da analyze - none!
 ; CHECK: da analyze - none!
 ; CHECK: da analyze - confused!
 ; CHECK: da analyze - none!
 ; CHECK: da analyze - confused!
 ; CHECK: da analyze - none!
 
+; NORMALIZE: 'Dependence Analysis' for function 'banerjee4':
+; NORMALIZE: da analyze - none!
+; NORMALIZE: da analyze - none!
+; NORMALIZE: da analyze - confused!
+; NORMALIZE: da analyze - none!
+; NORMALIZE: da analyze - confused!
+; NORMALIZE: da analyze - none!
+
 ; DELIN: 'Dependence Analysis' for function 'banerjee4':
 ; DELIN: da analyze - none!
 ; DELIN: da analyze - none!
 ; DELIN: da analyze - confused!
 ; DELIN: da analyze - none!
 ; DELIN: da analyze - confused!
 ; DELIN: da analyze - none!
 

 ; CHECK: 'Dependence Analysis' for function 'banerjee5':
 ; CHECK: da analyze - none!
 ; CHECK: da analyze - flow [< <]!
 ; CHECK: da analyze - confused!
 ; CHECK: da analyze - none!
 ; CHECK: da analyze - confused!
 ; CHECK: da analyze - none!
 
+; NORMALIZE: 'Dependence Analysis' for function 'banerjee5':
+; NORMALIZE: da analyze - none!
+; NORMALIZE: da analyze - flow [< <]!
+; NORMALIZE: da analyze - confused!
+; NORMALIZE: da analyze - none!
+; NORMALIZE: da analyze - confused!
+; NORMALIZE: da analyze - none!
+
 ; DELIN: 'Dependence Analysis' for function 'banerjee5':
 ; DELIN: da analyze - none!
 ; DELIN: da analyze - flow [< <]!
 ; DELIN: da analyze - confused!
 ; DELIN: da analyze - none!
 ; DELIN: da analyze - confused!
 ; DELIN: da analyze - none!
 

 ; CHECK: 'Dependence Analysis' for function 'banerjee6':
 ; CHECK: da analyze - none!
 ; CHECK: da analyze - flow [=> <>]!
 ; CHECK: da analyze - confused!
 ; CHECK: da analyze - none!
 ; CHECK: da analyze - confused!
 ; CHECK: da analyze - none!
 
+; NORMALIZE: 'Dependence Analysis' for function 'banerjee6':
+; NORMALIZE: da analyze - none!
+; NORMALIZE: da analyze - normalized - anti [<= <>]!
+; NORMALIZE: da analyze - confused!
+; NORMALIZE: da analyze - none!
+; NORMALIZE: da analyze - confused!
+; NORMALIZE: da analyze - none!
+
 ; DELIN: 'Dependence Analysis' for function 'banerjee6':
 ; DELIN: da analyze - none!
 ; DELIN: da analyze - flow [=> <>]!
 ; DELIN: da analyze - confused!
 ; DELIN: da analyze - none!
 ; DELIN: da analyze - confused!
 ; DELIN: da analyze - none!
 

 ; CHECK: 'Dependence Analysis' for function 'banerjee7':
 ; CHECK: da analyze - none!
 ; CHECK: da analyze - flow [> <=]!
 ; CHECK: da analyze - confused!
 ; CHECK: da analyze - none!
 ; CHECK: da analyze - confused!
 ; CHECK: da analyze - none!
 
+; NORMALIZE: 'Dependence Analysis' for function 'banerjee7':
+; NORMALIZE: da analyze - none!
+; NORMALIZE: da analyze - normalized - anti [< =>]!
+; NORMALIZE: da analyze - confused!
+; NORMALIZE: da analyze - none!
+; NORMALIZE: da analyze - confused!
+; NORMALIZE: da analyze - none!
+
 ; DELIN: 'Dependence Analysis' for function 'banerjee7':
 ; DELIN: da analyze - none!
 ; DELIN: da analyze - flow [> <=]!
 ; DELIN: da analyze - confused!
 ; DELIN: da analyze - none!
 ; DELIN: da analyze - confused!
 ; DELIN: da analyze - none!
 

 ; CHECK: 'Dependence Analysis' for function 'banerjee8':
 ; CHECK: da analyze - none!
 ; CHECK: da analyze - flow [> <>]!
 ; CHECK: da analyze - confused!
 ; CHECK: da analyze - none!
 ; CHECK: da analyze - confused!
 ; CHECK: da analyze - none!
 
+; NORMALIZE: 'Dependence Analysis' for function 'banerjee8':
+; NORMALIZE: da analyze - none!
+; NORMALIZE: da analyze - normalized - anti [< <>]!
+; NORMALIZE: da analyze - confused!
+; NORMALIZE: da analyze - none!
+; NORMALIZE: da analyze - confused!
+; NORMALIZE: da analyze - none!
+
 ; DELIN: 'Dependence Analysis' for function 'banerjee8':
 ; DELIN: da analyze - none!
 ; DELIN: da analyze - flow [> <>]!
 ; DELIN: da analyze - confused!
 ; DELIN: da analyze - none!
 ; DELIN: da analyze - confused!
 ; DELIN: da analyze - none!
 

 ; CHECK: 'Dependence Analysis' for function 'banerjee9':
 ; CHECK: da analyze - output [* *]!
 ; CHECK: da analyze - flow [<= =|<]!
 ; CHECK: da analyze - confused!
 ; CHECK: da analyze - none!
 ; CHECK: da analyze - confused!
 ; CHECK: da analyze - none!
 
+; NORMALIZE: 'Dependence Analysis' for function 'banerjee9':
+; NORMALIZE: da analyze - output [* *]!
+; NORMALIZE: da analyze - flow [<= =|<]!
+; NORMALIZE: da analyze - confused!
+; NORMALIZE: da analyze - none!
+; NORMALIZE: da analyze - confused!
+; NORMALIZE: da analyze - none!
+
 ; DELIN: 'Dependence Analysis' for function 'banerjee9':
 ; DELIN: da analyze - output [* *]!
 ; DELIN: da analyze - flow [<= =|<]!
 ; DELIN: da analyze - confused!
 ; DELIN: da analyze - none!
 ; DELIN: da analyze - confused!
 ; DELIN: da analyze - none!
 

 ; CHECK: 'Dependence Analysis' for function 'banerjee10':
 ; CHECK: da analyze - none!
 ; CHECK: da analyze - flow [<> =]!
 ; CHECK: da analyze - confused!
 ; CHECK: da analyze - none!
 ; CHECK: da analyze - confused!
 ; CHECK: da analyze - none!
 
+; NORMALIZE: 'Dependence Analysis' for function 'banerjee10':
+; NORMALIZE: da analyze - none!
+; NORMALIZE: da analyze - flow [<> =]!
+; NORMALIZE: da analyze - confused!
+; NORMALIZE: da analyze - none!
+; NORMALIZE: da analyze - confused!
+; NORMALIZE: da analyze - none!
+
 ; DELIN: 'Dependence Analysis' for function 'banerjee10':
 ; DELIN: da analyze - none!
 ; DELIN: da analyze - flow [<> =]!
 ; DELIN: da analyze - confused!
 ; DELIN: da analyze - none!
 ; DELIN: da analyze - confused!
 ; DELIN: da analyze - none!
 

 ; CHECK: 'Dependence Analysis' for function 'banerjee11':
 ; CHECK: da analyze - none!
 ; CHECK: da analyze - flow [<= <>]!
 ; CHECK: da analyze - confused!
 ; CHECK: da analyze - none!
 ; CHECK: da analyze - confused!
 ; CHECK: da analyze - none!
 
+; NORMALIZE: 'Dependence Analysis' for function 'banerjee11':
+; NORMALIZE: da analyze - none!
+; NORMALIZE: da analyze - flow [<= <>]!
+; NORMALIZE: da analyze - confused!
+; NORMALIZE: da analyze - none!
+; NORMALIZE: da analyze - confused!
+; NORMALIZE: da analyze - none!
+
 ; DELIN: 'Dependence Analysis' for function 'banerjee11':
 ; DELIN: da analyze - none!
 ; DELIN: da analyze - flow [<= <>]!
 ; DELIN: da analyze - confused!
 ; DELIN: da analyze - none!
 ; DELIN: da analyze - confused!
 ; DELIN: da analyze - none!
 

 ; CHECK: 'Dependence Analysis' for function 'banerjee12':
 ; CHECK: da analyze - none!
 ; CHECK: da analyze - flow [= <>]!
 ; CHECK: da analyze - confused!
 ; CHECK: da analyze - none!
 ; CHECK: da analyze - confused!
 ; CHECK: da analyze - none!
 
+; NORMALIZE: 'Dependence Analysis' for function 'banerjee12':
+; NORMALIZE: da analyze - none!
+; NORMALIZE: da analyze - flow [= <>]!
+; NORMALIZE: da analyze - confused!
+; NORMALIZE: da analyze - none!
+; NORMALIZE: da analyze - confused!
+; NORMALIZE: da analyze - none!
+
 ; DELIN: 'Dependence Analysis' for function 'banerjee12':
 ; DELIN: da analyze - none!
 ; DELIN: da analyze - flow [= <>]!
 ; DELIN: da analyze - confused!
 ; DELIN: da analyze - none!
 ; DELIN: da analyze - confused!
 ; DELIN: da analyze - none!