This is an archive of the discontinued LLVM Phabricator instance.

Add a value field to memory accesses for a related value
ClosedPublic

Authored by jdoerfert on Aug 16 2015, 1:45 AM.

Details

Summary
Add a value field to memory accesses for a related value.
 
  A new field in the memory accesses allows us to track a value related
  to that access.
    - For real memory accesses the value is the loaded result or the
      stored value.
    - For straigt line scalar accesses it is the access instruction
      itself.
    - For PHI operand accesses it is the operand value.
  
  We use this value to simplify code which deduced information about the value
  later in the Polly pipeline and was known to be error prone.

Diff Detail

Event Timeline

jdoerfert updated this revision to Diff 32235.Aug 16 2015, 1:45 AM
jdoerfert retitled this revision from to Allow values to cause memory accesses.
jdoerfert added reviewers: grosser, Meinersbur.
jdoerfert updated this object.
jdoerfert added a subscriber: Restricted Project.
Meinersbur edited edge metadata.Aug 16 2015, 10:23 AM

Can you please explain what "hacks" you are referring to?

include/polly/ScopInfo.h
246–247

llvm::Value (e.g. a constant) cannot "cause" accesses.

I think this is bad modelling. A memory access is an effect that happens at some point. Non-instructions do not have such a property. there're passive.

lib/Analysis/ScopInfo.cpp
974

Why is this suddenly necessary?

lib/Analysis/TempScopInfo.cpp
148

I don't see how removing this can work. The .phiops location needs to be written somewhere in the incoming block. If not the terminator, who is it?

lib/CodeGen/BlockGenerators.cpp
1135

Why did PHIIdx < 0 become possible here, but not in the non-NonAffine case?

Can you please explain what "hacks" you are referring to?

The fact that a terminator is the cause of an access and the type of the branch condition as some kind of access type.

lib/Analysis/ScopInfo.cpp
974

Because getAccessInstruction in line 910 can become null now.

lib/Analysis/TempScopInfo.cpp
148

This works because the codegen doesn't work the way you think it does. Except for non-affine regions (which are different as explained below) the codegen will not look at the original instruction for scalar write operations but simply insert them at the end of a basic block if they were part of the corresponding ScopStmt.

lib/CodeGen/BlockGenerators.cpp
1135

Because this is a non-affine region and we do not reschedule it. Here all scalar accesses are summarized in one ScopStmt and we have to figure out where to actually put them while iterating over the actual basic blocks.

But we can actually remove the PHIIdx stuff from the affine case now. Thanks, I'll update the patch.

jdoerfert updated this revision to Diff 32243.Aug 16 2015, 11:34 AM
jdoerfert edited edge metadata.

Remove the PHIIdx stuff from the codegen in case of affine regions

Btw. this passes all lnt tests and I think this removes a lot of complicated code in exchange for some simple conditions.

grosser edited edge metadata.Aug 16 2015, 11:59 PM

Hi Johannes,

I looked through this patch and saw a couple of the code simplifications you mention in the commit message, but also got the feeling that several changes introduced change behaviour in a way that is somehow confusing to me. Overall, I am not convinced this patch is an improvement as it is.

Best,
Tobias

include/polly/ScopInfo.h
246–247

Similar to Michael, the idea of an "AccessValue" is not understandable to me. The idea of an access instruction was that the access happend at the given instruction. Obviously, a llvm::Value does not have a location and consequently does not trigger a memory access.

You probably have some ideas in mind, but without an explanation of what the AccessValue is meant to be this is unfortunately not understandable to me.

649

My feeling is that this function now changes behavior.

Bevor, for a given instruction the memory accesses we model for this instruction were returned.

Now, look at this example:

bb1:
  sum = add i64 ...  
  br bb2

bb2:
  br bb3             

bb3
  merge = phi [%sum, %bb2], ...

If I now call getAccessFor("%sum"), it will also return the write of %sum into "merge.phiops", even though this memory access is not really performed by the instruction %sum, but it just uses the value %sum.

Besides being unintuitive, I am afraid this change has a risk of breaking other (unrelated parts) of Polly. Specifically, if a value
loaded by a "load" instruction is used in a PHI node, Stmt.getAccessFor("load") will return only one out of two memory accesses. As the PHI access is likely to be constructed later
and will be inserted at the front, the first access is most likely the wrong one.

void VectorBlockGenerator::generateLoad(ScopStmt &Stmt, const LoadInst *Load,    
                                        ValueMapT &VectorMap,                    
                                        VectorValueMapT &ScalarMaps) {           
  if (!VectorType::isValidElementType(Load->getType())) {                        
    for (int i = 0; i < getVectorWidth(); i++)                                   
      ScalarMaps[i][Load] =                                                      
          generateScalarLoad(Stmt, Load, ScalarMaps[i], GlobalMaps[i], VLTS[i]); 
    return;                                                                      
  }                                                                              
                                                                                 
  const MemoryAccess &Access = Stmt.getAccessFor(Load);
lib/Analysis/ScopInfo.cpp
974

This change is also confusing. Does this mean we will not support scalar reductions any more?

We could have both, an access instruction as well as an access value, that way we keep the best of both worlds. I will update the patch as I think it might be worth it.

lib/Analysis/ScopInfo.cpp
974

We never did in upstream Polly.

jdoerfert updated this revision to Diff 32285.Aug 17 2015, 3:26 AM
jdoerfert edited edge metadata.

Introduce a value additionally to the access instruction

jdoerfert retitled this revision from Allow values to cause memory accesses to Add a value field to memory accesses for a related value.Aug 17 2015, 3:26 AM
jdoerfert updated this object.
jdoerfert marked 11 inline comments as done.

I updated the patch and marked the outdated comments as done.

This version just adds a value field in order to simplify some stuff later on.

grosser accepted this revision.Aug 17 2015, 3:39 AM
grosser edited edge metadata.

LGTM.

include/polly/ScopInfo.h
249

Maybe expand the comment a little (add some info from the commit message?).

This revision is now accepted and ready to land.Aug 17 2015, 3:39 AM
This revision was automatically updated to reflect the committed changes.